Module traitgraph_algo::traversal

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

• AllowedNodesForbiddenSubgraph
  A type implementing ForbiddenSubgraph that allows all nodes set to true in a boolean vector.
• BackwardNeighborStrategy
  A neighbor strategy that traverses all incoming edges of a node.
• BfsQueueStrategy
  A queue strategy that works by the first-in first-out principle.
• DfsPostOrderTraversal
  A generic depth first postorder graph traversal. The traversal is generic over the graph implementation, as well as the direction of the search (NeighborStrategy) and the queue implementation (Queue).
• DfsQueueStrategy
  A queue strategy that works by the last-in first-out principle.
• ForbiddenEdge
  A ForbiddenSubgraph that forbids a single edge.
• ForbiddenNode
  A ForbiddenSubgraph that forbids a single node.
• ForwardNeighborStrategy
  A neighbor strategy that traverses all outgoing edges of a node.
• NoForbiddenSubgraph
  A type implementing ForbiddenSubgraph that allows all nodes in a graph traversal.
• PreOrderTraversal
  A generic preorder graph traversal. The traversal is generic over the graph implementation, as well as the direction of the search (NeighborStrategy), the order of processing (QueueStrategy) and the queue implementation itself (Queue).
• UndirectedNeighborStrategy
  A neighbor strategy that traverses all incoming and all outgoing edges of a node.

Traits

• ForbiddenSubgraph
  A type with this trait can tell if a node or edge is forbidden in a graph traversal.
• TraversalNeighborStrategy
  A type that defines the strategy for computing the neighborhood of a node or edge, i.e. forward, backward or undirected.
• TraversalQueueStrategy
  A type that defines the order of node processing in a traversal, i.e. queue-based or stack-based.

Type Definitions

• PostOrderBackwardDfs
  A post-order forward DFS in a directed graph.
• PostOrderForwardDfs
  A post-order forward DFS in a directed graph.
• PostOrderUndirectedDfs
  A post-order forward DFS in a directed graph.
• PreOrderBackwardBfs
  A normal backward BFS in a directed graph.
• PreOrderBackwardDfs
  A normal backward DFS in a directed graph.
• PreOrderForwardBfs
  A normal forward BFS in a directed graph.
• PreOrderForwardDfs
  A normal forward DFS in a directed graph.
• PreOrderUndirectedBfs
  A BFS that treats each directed edge as an undirected edge, i.e. that traverses edge both in forward and backward direction.
• PreOrderUndirectedDfs
  A DFS that treats each directed edge as an undirected edge, i.e. that traverses edge both in forward and backward direction.