Module petgraph::visit

source ·
Expand description

Graph traits and graph traversals.

§The Into- Traits

Graph traits like IntoNeighbors create iterators and use the same pattern that IntoIterator does: the trait takes a reference to a graph, and produces an iterator. These traits are quite composable, but with the limitation that they only use shared references to graphs.

§Graph Traversal

Dfs, Bfs, DfsPostOrder and Topo are basic visitors and they use “walker” methods: the visitors don’t hold the graph as borrowed during traversal, only for the .next() call on the walker. They can be converted to iterators through the Walker trait.

There is also the callback based traversal depth_first_search.

§Other Graph Traits

The traits are rather loosely coupled at the moment (which is intentional, but will develop a bit), and there are traits missing that could be added.

Not much is needed to be able to use the visitors on a graph. A graph needs to define GraphBase, IntoNeighbors and Visitable as a minimum.

§Graph Trait Implementations

The following table lists the traits that are implemented for each graph type:

GraphStableGraphGraphMapMatrixGraphCsrList
GraphBasexxxxxx
GraphPropxxxxxx
NodeCountxxxxxx
NodeIndexablexxxxxx
NodeCompactIndexablexxxx
EdgeCountxxxxxx
EdgeIndexablexxx
Dataxxxxxx
IntoNodeIdentifiersxxxxxx
IntoNodeReferencesxxxxxx
IntoEdgeReferencesxxxxxx
IntoNeighborsxxxxxx
IntoNeighborsDirectedxxxx
IntoEdgesxxxxxx
IntoEdgesDirectedxxxx
Visitablexxxxxx
GetAdjacencyMatrixxxxxxx

Structs§

Enums§

  • Control flow for depth_first_search callbacks.
  • A depth first search (DFS) visitor event.

Traits§

Functions§