Module graph

Traits and implementations for directed and undirected graphs and useful graph wrappers.

Low-level graphs and TaggedGraph

Some graph libraries allow customized types of vertices and edges. But for algorithm authors, these customized types are hard to deal with. Can we copy a vertex? What is the cost of doing that copying?

In this crate, there are traits and implementations of low level graphs. Vertices and edges in low level graphs are lightweight ID’s. They are essentially usize. Algorithm authors may feel free to copy and store these ID’s.

There is also TaggedGraph to let vertices and edges be tagged. Users may usually experience TaggedGraph as easy as those with customized vertice types and edge types in other crates.

Graph wrappers

ShadowedSubgraph and SelectedSubgraph

They can form subgraphs with shadowed/selected vertices and edges. Futhermore, these subgraphs are shrinkable. While they are shrinking, their underlying graphs are kept unchanged.

MappedGraph

It wraps a graph and how its vertices and edges are mapped from another graph.

Modules

directed

Implementations of low-level directed graph

undirected

Implementations of low-level undirected graph

Structs

Edge

Information about a low-level edge.

EdgeId

ID for edges, which are essentially usize.

EdgeIdFactory

A factory to generate EdgeId uniquely.

MappedGraph

This wraps a graph and mappings of vertices and edges from another graph.

SelectedSubgraph

A subgraph with selected vertices and edges.

ShadowedSubgraph

A subgraph by shadowing some of vertices and edges in the underlying graph.

VertexId

ID for vertices, which are essentially usize.

VertexIdFactory

A factory to generate VertexId uniquely.

Traits

DirectedOrNot

Whether a graph is directed or not.

DumpInGraphviz

A trait with default implementation for dumping a (directed or not) graph in graphviz format.

EdgeShrinkableGraph

A trait for low-level graphs whose edges can be removed.

GrowableGraph

A trait for low-level growable graphs.

QueryableGraph

A trait for querying vertices and edges about low-level graphs.

Subgraph

A trait for subgraphs.

VertexShrinkableGraph

A trait for low-level graphs whose vertices can be removed.