Expand description
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).
- DfsPost
Order - Visit nodes in a depth-first-search (DFS) emitting nodes in postorder (each node after all its descendants have been emitted).
- Edge
Filtered - An edge-filtering graph adaptor.
- Edge
Filtered Edges - A filtered edges iterator.
- Edge
Filtered Neighbors - A filtered neighbors iterator.
- Edge
Filtered Neighbors Directed - A filtered neighbors-directed iterator.
- Node
Filtered - A node-filtering graph adaptor.
- Node
Filtered Edge References - A filtered edges iterator.
- Node
Filtered Edges - A filtered edges iterator.
- Node
Filtered Neighbors - A filtered neighbors iterator.
- Node
Filtered Nodes - A filtered node references iterator.
- Reversed
- An edge-reversing graph adaptor.
- Reversed
Edge Reference - A reversed edge reference
- Reversed
Edge References - A reversed edge references iterator.
- Reversed
Edges - A reversed edges iterator.
- Time
- Strictly monotonically increasing event time for a depth first search.
- Topo
- A topological order traversal for a graph.
- Undirected
Adaptor - An edge direction removing graph adaptor.
- Walker
Iter - A walker and its context wrapped into an iterator.
Enums§
- Control
- Control flow for
depth_first_searchcallbacks. - DfsEvent
- A depth first search (DFS) visitor event.
Traits§
- Control
Flow - Control flow for callbacks.
- Data
- Define associated data for nodes and edges
- Edge
Count - A graph with a known edge count.
- Edge
Indexable - The graph’s
NodeIds map to indices - EdgeRef
- An edge reference.
- Filter
Edge - A graph filter for edges
- Filter
Node - A graph filter for nodes.
- GetAdjacency
Matrix - Create or access the adjacency matrix of a graph.
- Graph
Base - Base graph trait: defines the associated node identifier and edge identifier types.
- Graph
Prop - Edge kind property (directed or undirected edges)
- Graph
Ref - A copyable reference to a graph.
- Into
Edge References - Access to the sequence of the graph’s edges
- Into
Edges - Access to the edges of each node.
- Into
Edges Directed - Access to all edges of each node, in the specified direction.
- Into
Neighbors - Access to the neighbors of each node
- Into
Neighbors Directed - Access to the neighbors of each node, through incoming or outgoing edges.
- Into
Node Identifiers - Access to the sequence of the graph’s
NodeIds. - Into
Node References - Access to the sequence of the graph’s nodes
- Node
Compact Indexable - The graph’s
NodeIds map to indices, in a range without holes. - Node
Count - A graph with a known node count.
- Node
Indexable - The graph’s
NodeIds map to indices - NodeRef
- A node reference.
- Visit
Map - 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.