Module petgraph::visit

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.

Visitors

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.

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.

Structs

AsUndirected	Wrapper type for walking the graph as if it is undirected
Bfs	A breadth first search (BFS) of a graph.
BfsIter	An iterator for a breadth first traversal of a graph.
Dfs	Visit nodes of a graph in a depth-first-search (DFS) emitting nodes in preorder (when they are first discovered).
DfsIter	An iterator for a depth first traversal of a graph.
DfsPostOrder	Visit nodes in a depth-first-search (DFS) emitting nodes in postorder (each node after all its decendants have been emitted).
Filtered	A filtered adaptor of a graph.
FilteredNeighbors	A filtered neighbors iterator.
Reversed	Wrapper type for walking the graph as if all edges are reversed.
ReversedEdgeRef	An edge reference for Reversed.
ReversedEdgeReferences	An iterator of edge references for Reversed.
Time	Strictly monotonically increasing event time for a depth first search.
Topo	A topological order traversal for a graph.

Enums

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

Traits

ControlFlow	Control flow for visitor callbacks.
EdgeRef	An edge reference
FilterNode	A graph filter for nodes.
GetAdjacencyMatrix	Create or access the adjacency matrix of a graph.
GraphBase	Base graph trait: defines the associated node identifier and edge identifier types.
GraphEdgeRef	A graph that defines edge references
GraphRef	A copyable reference to a graph.
IntoEdgeReferences	Access to the sequence of the graph’s edges
IntoExternals	Access to the graph’s nodes without edges to them (Incoming) or from them (Outgoing).
IntoNeighbors	Access to the neighbors of each node
IntoNeighborsDirected	Access to the neighbors of each node, through incoming or outgoing edges.
IntoNodeIdentifiers	Access to the sequence of the graph’s NodeIds.
NodeCompactIndexable	The graph’s NodeIds map to indices, in a range without holes.
NodeIndexable	The graph’s NodeIds map to indices
VisitMap	A mapping for storing the visited status for NodeId N.
Visitable	A graph that can create a map that tracks the visited status of its nodes.

Functions

depth_first_search

A recursive depth first search.