DirectedGraph

abstractgraph::directedgraph

Trait DirectedGraph 

Source 
pub trait DirectedGraph
where
    Self: Sized,
    Self::Node: Clone,
    Self::Edge: OutboundEdge<Self::Node>,
    Self::Edges: IntoIterator<Item = Self::Edge>,
{
    type Node;
    type Edge;
    type Edges;

    // Required method
    fn edges_from(&self, from: &Self::Node) -> Self::Edges;

    // Provided methods
    fn neighbors(&self, from: &Self::Node) -> Neighbors<Self> ⓘ { ... }
    fn bfs(&self, start: Self::Node) -> BreadthFirstSearch<'_, Self> ⓘ
       where Self::Node: Eq + Hash { ... }
    fn dfs(&self, start: Self::Node) -> DepthFirstSearch<'_, Self> ⓘ
       where Self::Node: Eq + Hash { ... }
}
Expand description

The trait for types (implicitly or explicitly) representing a directed graph structure

To implement this trait:

  • Set the Node associated type to a convenient representation for graph nodes

  • Set the Edge associated types to a convenient representation for an edge in your graph. For simple cases you can use SimpleOutboundEdge<Self::Node>, which is a trivial representation of an (unweighted, directed) edge by its destination.

  • Set the Edges associated type to a convenient representation of a list of edges (usually an iterator or collection). For simple cases you can use SimpleOutboundEdges which transforms an iterator over nodes (an adjacency list) into an iterator over edges.

  • Implement edges_from() to return the list of edges originating at a specific node.

Theoretically infinite graphs are permitted, though you obviously won’t be able to fully traverse them.

Required Associated Types§

Source

type Node

Represents a node in the graph.

Source

type Edge

Represents an edge in the graph.

Implements the OutboundEdge<Self::Node> trait. Only needs to represent an edge given it’s origin node, so it need not be globally unique (or even locally, you can return the same Edge twice from edges_from if you want and the algorithms will treat them as distinct edges).

Source

type Edges

Represents a list of graph edges (with a common origin) in the graph

Implements IntoIterator<Item=Self::Edge>, with that iterator stepping through each ednge outgoing from a single node.

Required Methods§

Source

fn edges_from(&self, from: &Self::Node) -> Self::Edges

Returns the list of edges originating from node from

Provided Methods§

Source

fn neighbors(&self, from: &Self::Node) -> Neighbors<Self> ⓘ

Returns the (outgoing) adjacency list for node from

This is the list (represented by an iterator) of nodes reachable from from by exactly one edge transition.

Source

fn bfs(&self, start: Self::Node) -> BreadthFirstSearch<'_, Self> ⓘ
where Self::Node: Eq + Hash,

Traverse self in breadth-first order from start

Source

fn dfs(&self, start: Self::Node) -> DepthFirstSearch<'_, Self> ⓘ
where Self::Node: Eq + Hash,

Traverse self in depth-first order from start

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§