AdjacencyListProtocol

public protocol AdjacencyListProtocol:
  VertexListGraph,
  EdgeListGraph,
  IncidenceGraph,
  MutablePropertyGraph,
  DefaultInitializable 
where
  VertexCollection == Range<RawId>

A general purpose adjacency list graph.

Adjacency list representations of graphs are flexible and common. This protocol abstracts over the specific underlying storage of the data structure, and implements a variety of graph APIs on top of the basic storage:

And can additionally conform to:

Types conforming to AdjacencyList can implement directed, bidirectional, or undirected graphs.

AdjacencyList types allow 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 instead of Void.

AdjacencyList 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.

See also

DirectedAdjacencyList

See also

BidirectionalAdjacencyList

See also

UndirectedAdjacencyList
Show on GitHub

  • Storage for indices into arrays within self.

    Indices into arrays in Swift are always Int. But because a graph often needs to store a lot of indices, it can be valuable to store only a subset of the bits (e.g. only the lower 32), so long as the user promises there won’t be an overflow. As long as no parallel edges are used, and the total number of vertices in self is below 2^31, then UInt32 is sufficient, resulting in a ~2x increase in graph memory efficiency.

    Declaration

    Swift

    associatedtype RawId where Self.RawId == Self._EdgeData.VertexId, Self.VertexCollection == Range<Self.RawId>, Self.RawId.Stride : SignedInteger
    Show on GitHub

  • Storage associated with each edge in self.

    Declaration

    Swift

    associatedtype _EdgeData  // _EdgeData: _AdjacencyListPerEdge is implied.
  where _EdgeData.VertexId == VertexId, _EdgeData.Edge == Edge
    Show on GitHub

  • Storage associated with each vertex in self.

    Declaration

    Swift

    associatedtype _VertexData: _AdjacencyListPerVertex
  where _VertexData.Vertex == Vertex, _VertexData.EdgeData == _EdgeData
    Show on GitHub

  • The data structure containing all of the information in self.

    Declaration

    Swift

    typealias _Storage = [_VertexData]
    Show on GitHub

  • The data structure containing all of the information in self.

    Declaration

    Swift

    var _storage: _Storage { get set }
    Show on GitHub

AdjacencyListProtocol: VertexListGraph

  • vertexCount Extension method

    The total number of vertices in the graph.

    Declaration

    Swift

    public var vertexCount: Int { get }
    Show on GitHub