Expand description
Algorithms for graph traversals, i.e. preorder breadth or depth first search as well as postorder depth first search.
Modules§
- univocal_
traversal - Functions and structures related to univocal traversals. Univocal traversals are traversals along unique out-edges or unique in-edges in a graph.
Structs§
- Allowed
Nodes Forbidden Subgraph - A type implementing ForbiddenSubgraph that allows all nodes set to true in a boolean vector.
- Backward
Neighbor Strategy - A neighbor strategy that traverses all incoming edges of a node.
- BfsQueue
Strategy - A queue strategy that works by the first-in first-out principle.
- DfsPost
Order Traversal - A generic depth first postorder graph traversal.
- DfsQueue
Strategy - A queue strategy that works by the last-in first-out principle.
- Forbidden
Edge - A ForbiddenSubgraph that forbids a single edge.
- Forbidden
Node - A ForbiddenSubgraph that forbids a single node.
- Forward
Neighbor Strategy - A neighbor strategy that traverses all outgoing edges of a node.
- NoForbidden
Subgraph - A type implementing ForbiddenSubgraph that allows all nodes in a graph traversal.
- PreOrder
Traversal - A generic preorder graph traversal.
- Undirected
Neighbor Strategy - A neighbor strategy that traverses all incoming and all outgoing edges of a node.
Traits§
- Forbidden
Subgraph - A type with this trait can tell if a node or edge is forbidden in a graph traversal.
- Traversal
Neighbor Strategy - A type that defines the strategy for computing the neighborhood of a node or edge, i.e. forward, backward or undirected.
- Traversal
Queue Strategy - A type that defines the order of node processing in a traversal, i.e. queue-based or stack-based.
Type Aliases§
- Post
Order Backward Dfs - A post-order forward DFS in a directed graph.
- Post
Order Forward Dfs - A post-order forward DFS in a directed graph.
- Post
Order Undirected Dfs - A post-order forward DFS in a directed graph.
- PreOrder
Backward Bfs - A normal backward BFS in a directed graph.
- PreOrder
Backward Dfs - A normal backward DFS in a directed graph.
- PreOrder
Forward Bfs - A normal forward BFS in a directed graph.
- PreOrder
Forward Dfs - A normal forward DFS in a directed graph.
- PreOrder
Undirected Bfs - A BFS that treats each directed edge as an undirected edge, i.e. that traverses edge both in forward and backward direction.
- PreOrder
Undirected Dfs - A DFS that treats each directed edge as an undirected edge, i.e. that traverses edge both in forward and backward direction.