Adjacency Lists

A general purpose directed adjacency list graph.

DirectedAdjacencyList implements a directed graph, and supports parallel edges.

DirectedAdjacencyList also allows storing arbitrary additional data with each vertex and edge. If you select a zero-sized type (such as Empty), all overhead is optimized away by the Swift compiler.

Note: because tuples cannot yet conform to protocols, we have to use a separate type (Empty) instead of Void.

Operations that do not modify the graph structure occur in O(1) time. Additional operations that run in O(1) (amortized) time include: adding a new edge, and adding a new vertex. Operations that remove either vertices or edges invalidate existing VertexIds and EdgeIds. Adding new vertices or edges do not invalidate previously retrieved ids.

DirectedAdjacencyList is parameterized by the RawId which can be carefully tuned to save memory. A good default is UInt32, unless you are trying to represent more than 2^31 vertices, or a lot of parallel edges.

See more

public struct DirectedAdjacencyList<
  Vertex: DefaultInitializable,
  Edge: DefaultInitializable,
  RawId: BinaryInteger & IdIndexable
>: DirectedAdjacencyListProtocol, SearchDefaultsGraph where RawId.Stride: SignedInteger

A general purpose, bidirectional adjacency list graph.

BidirectionalAdjacencyList implements a bidirectional graph. Additionally, parallel edges are supported.

BidirectionalAdjacencyList also allows storing arbitrary additional data with each vertex and edge. If you select a zero-sized type (such as Empty), all overhead is optimized away by the Swift compiler.

Note: because tuples cannot yet conform to protocols, we have to use a separate type (Empty) instead of Void.

Operations that do not modify the graph structure occur in O(1) time. Additional operations that run in O(1) (amortized) time include: adding a new edge, and adding a new vertex. Operations that remove either vertices or edges invalidate existing VertexIds and EdgeIds. Adding new vertices or edges do not invalidate previously retrieved ids.

BidirectionalAdjacencyList is parameterized by the RawId which can be carefully tuned to save memory. A good default is Int32, unless you are trying to represent more than 2^32 vertices.

See more

public struct BidirectionalAdjacencyList<
  Vertex: DefaultInitializable,
  Edge: DefaultInitializable,
  RawId: BinaryInteger & IdIndexable
>: DirectedAdjacencyListProtocol, SearchDefaultsGraph where RawId.Stride: SignedInteger

extension BidirectionalAdjacencyList: BidirectionalGraph

Undocumented

See more

public struct UndirectedAdjacencyList<
  Vertex: DefaultInitializable,
  Edge: DefaultInitializable,
  RawId: BinaryInteger & IdIndexable
>: UndirectedAdjacencyListProtocol, SearchDefaultsGraph where RawId.Stride: SignedInteger

A simple AdjacencyList with no data associated with each vertex or edge, and a maximum of 2^63-1 vertices.

public typealias SimpleAdjacencyList = DirectedAdjacencyList<Empty, Empty, Int>