Graph Protocols & Algorithms

Represents a Graph data structure.

This is modeled off of the Boost Graph Library; see https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/Graph.html.

A graph that allows retrieval of edges from each vertex.

A graph that provides defaults for graph searching algorithms.

Implementations of Graph algorithms often demand a variety of associated data structures. A graph that conforms to SearchDefaultsGraph provides default types that make using these graph data structures more convenient.

To conform an IncidenceGraph to SearchDefaultsGraph, simpliy implement the required methods. Reasonable choices for IdIndexable VertexId’s often use TablePropertyMaps. For graphs with hashable VertexId’s, the DictionaryPropertyMap is often a good choice.

Note: we have to spell out each of these associated PropertyMaps explicitly, because associated types cannot be generic in Swift, and we want to avoid existentials.

A graph that allows retrieval of edges incoming to each vertex (the “in-edges”).

A VertexListGraph is a graph that can enumerate all the vertices within it.

An EdgeListGraph is a graph that can enumerate all edges within it.

A MutableGraph can be changed via the addition and removal of edges and vertices.

In the documentation of complexity guarantees, |V| is the number of nodes, and |E| is the number of edges.

A PropertyGraph stores additional information along with the graph structure.

A MutablePropertyGraph keeps track of additional metadata for each vertex and edge.