Module 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.

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:

	Graph	StableGraph	GraphMap	MatrixGraph	Csr	List
GraphBase	x	x	x	x	x	x
GraphProp	x	x	x	x	x	x
NodeCount	x	x	x	x	x	x
NodeIndexable	x	x	x	x	x	x
NodeCompactIndexable	x		x		x	x
EdgeCount	x	x	x	x	x	x
EdgeIndexable	x	x	x
Data	x	x	x	x	x	x
IntoNodeIdentifiers	x	x	x	x	x	x
IntoNodeReferences	x	x	x	x	x	x
IntoEdgeReferences	x	x	x	x	x	x
IntoNeighbors	x	x	x	x	x	x
IntoNeighborsDirected	x	x	x	x
IntoEdges	x	x	x	x	x	x
IntoEdgesDirected	x	x	x	x
Visitable	x	x	x	x	x	x
GetAdjacencyMatrix	x	x	x	x	x	x

Structs

• Bfs
  A breadth first search (BFS) of a graph.
• Dfs
  Visit nodes of a graph in a depth-first-search (DFS) emitting nodes in preorder (when they are first discovered).
• DfsPostOrder
  Visit nodes in a depth-first-search (DFS) emitting nodes in postorder (each node after all its descendants have been emitted).
• EdgeFiltered
  An edge-filtering graph adaptor.
• EdgeFilteredEdges
  A filtered edges iterator.
• EdgeFilteredNeighbors
  A filtered neighbors iterator.
• EdgeFilteredNeighborsDirected
  A filtered neighbors-directed iterator.
• NodeFiltered
  A node-filtering graph adaptor.
• NodeFilteredEdgeReferences
  A filtered edges iterator.
• NodeFilteredEdges
  A filtered edges iterator.
• NodeFilteredNeighbors
  A filtered neighbors iterator.
• NodeFilteredNodes
  A filtered node references iterator.
• Reversed
  An edge-reversing graph adaptor.
• ReversedEdgeReference
  A reversed edge reference
• ReversedEdgeReferences
  A reversed edge references iterator.
• ReversedEdges
  A reversed edges iterator.
• Time
  Strictly monotonically increasing event time for a depth first search.
• Topo
  A topological order traversal for a graph.
• WalkerIter
  A walker and its context wrapped into an iterator.

Enums

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

Traits

• ControlFlow
  Control flow for callbacks.
• Data
  Define associated data for nodes and edges
• EdgeCount
  A graph with a known edge count.
• EdgeIndexable
  The graph’s NodeIds map to indices
• EdgeRef
  An edge reference.
• FilterEdge
  A graph filter for edges
• 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.
• GraphProp
  Edge kind property (directed or undirected edges)
• GraphRef
  A copyable reference to a graph.
• IntoEdgeReferences
  Access to the sequence of the graph’s edges
• IntoEdges
  Access to the edges of each node.
• IntoEdgesDirected
  Access to all edges of each node, in the specified direction.
• 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.
• IntoNodeReferences
  Access to the sequence of the graph’s nodes
• NodeCompactIndexable
  The graph’s NodeIds map to indices, in a range without holes.
• NodeCount
  A graph with a known node count.
• NodeIndexable
  The graph’s NodeIds map to indices
• NodeRef
  A node reference.
• 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.
• Walker
  A walker is a traversal state, but where part of the traversal information is supplied manually to each next call.

Functions

• depth_first_search
  A recursive depth first search.