## 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

- A breadth first search (BFS) of a graph.
- Visit nodes of a graph in a depth-first-search (DFS) emitting nodes in preorder (when they are first discovered).
- Visit nodes in a depth-first-search (DFS) emitting nodes in postorder (each node after all its descendants have been emitted).
- An edge-filtering graph adaptor.
- A filtered edges iterator.
- A filtered neighbors iterator.
- A filtered neighbors-directed iterator.
- A node-filtering graph adaptor.
- A filtered edges iterator.
- A filtered edges iterator.
- A filtered neighbors iterator.
- A filtered node references iterator.
- An edge-reversing graph adaptor.
- A reversed edge reference
- A reversed edge references iterator.
- A reversed edges iterator.
- Strictly monotonically increasing event time for a depth first search.
- A topological order traversal for a graph.
- A walker and its context wrapped into an iterator.

## Enums

- Control flow for
`depth_first_search`

callbacks. - A depth first search (DFS) visitor event.

## Traits

- Control flow for callbacks.
- Define associated data for nodes and edges
- A graph with a known edge count.
- The graph’s
`NodeId`

s map to indices - An edge reference.
- A graph filter for edges
- A graph filter for nodes.
- Create or access the adjacency matrix of a graph.
- Base graph trait: defines the associated node identifier and edge identifier types.
- Edge kind property (directed or undirected edges)
- A copyable reference to a graph.
- Access to the sequence of the graph’s edges
- Access to the edges of each node.
- Access to all edges of each node, in the specified direction.
- Access to the neighbors of each node
- Access to the neighbors of each node, through incoming or outgoing edges.
- Access to the sequence of the graph’s
`NodeId`

s. - Access to the sequence of the graph’s nodes
- The graph’s
`NodeId`

s map to indices, in a range without holes. - A graph with a known node count.
- The graph’s
`NodeId`

s map to indices - A node reference.
- A mapping for storing the visited status for NodeId
`N`

. - A graph that can create a map that tracks the visited status of its nodes.
- A walker is a traversal state, but where part of the traversal information is supplied manually to each next call.

## Functions

- A recursive depth first search.