Module dograph::traversal

Structs

BfsVerticesIterator

See iter_vertices_bfs.

DfsPostOrderEdgesIterator

See iter_edges_dfs_post_order.

DfsPostOrderVerticesIterator

See iter_vertices_dfs_post_order.

DfsVerticesIterator

See iter_vertices_dfs.

Functions

get_topologically_ordered_vertices

Combines iter_vertices_dfs_post_order, Iterator::collect() and slice::reverse() to get a topologically ordered sequence of vertices of a DAG.

get_vertices_without_incoming_edges

Returns a set “seed” vertices of a DAG from which a traversal may start so that the process covers all vertices in the graph.

iter_descendants_bfs

Visit all vertices reachable from vertex in a breadth-first-search (BFS) order.

iter_descendants_dfs

Visit all vertices reachable from vertex in a depth-first-search (DFS) order.

iter_descendants_dfs_post_order

Visit all vertices reachable from vertex in a depth-first-search postorder, i.e. emitting vertices only after all their descendants have been emitted first.

iter_edges_dfs_post_order

Visit nodes in a depth-first-search (DFS) emitting edges in postorder, i.e. each node after all its descendants have been emitted.

iter_vertices_bfs

Visit all vertices of a DAG in a breadth-first-search (BFS) order.

iter_vertices_dfs

Visit all vertices of a DAG in a depth-first-search (DFS) order.

iter_vertices_dfs_post_order

Visit all vertices of a DAG in a depth-first-search postorder, i.e. emitting vertices only after all their descendants have been emitted first.