[−][src]Trait abstractgraph::DirectedGraph

pub trait DirectedGraph where
    Self: Sized,
    Self::Node: Clone,
    Self::Edge: OutEdge<Self::Node>,
    Self::Edges: IntoIterator<Item = Self::Edge>, {
    type Node;
    type Edge;
    type Edges;
    fn edges_from(&self, from: Self::Node) -> Self::Edges;

    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,
    { ... }
}

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 SimpleEdge<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 SimpleEdges 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.

Associated Types

type Node

Represents a node in the graph.

type Edge

Represents an edge in the graph.

Implements the OutEdge<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).

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.

Loading content...

Required methods

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

Returns the list of edges originating from node from

Loading content...

Provided methods

ⓘImportant traits for Neighbors<G>
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.

ⓘImportant traits for BreadthFirstSearch<'a, G>
fn bfs(&self, start: Self::Node) -> BreadthFirstSearch<Self> where
    Self::Node: Eq + Hash, 

Traverse self in breadth-first order from start

ⓘImportant traits for DepthFirstSearch<'a, G>
fn dfs(&self, start: Self::Node) -> DepthFirstSearch<Self> where
    Self::Node: Eq + Hash, 

Traverse self in depth-first order from start

Loading content...

Implementors

Loading content...