Adjacency List Implementation Internals Reference

AdjacencyListProtocol

AdjacencyListProtocol
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:
- VertexListGraph
- EdgeListGraph
- IncidenceGraph
- MutableGraph (implied by MutablePropertyGraph)
- PropertyGraph (implied by MutablePropertyGraph)
And can additionally conform to:
- BidirectionalGraph
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
See more
Declaration
Swift

public protocol AdjacencyListProtocol: VertexListGraph, EdgeListGraph, IncidenceGraph, MutablePropertyGraph, DefaultInitializable where VertexCollection == Range<RawId>
Show on GitHub
_AdjacencyListPerEdge
Data associated with each edge in an AdjacencyList.
See more
Declaration
Swift

public protocol _AdjacencyListPerEdge
Show on GitHub
_AdjacencyListPerVertex
Data associated with each vertex in an AdjacencyList.
See more
Declaration
Swift

public protocol _AdjacencyListPerVertex
Show on GitHub


                    
                    
                    _AdjacencyList_DirectedEdgeId

An identifier for an edge.

Declaration

Swift

public struct _AdjacencyList_DirectedEdgeId<RawId> : Equatable, Hashable, Comparable where RawId : BinaryInteger

extension _AdjacencyList_DirectedEdgeId: CustomStringConvertible

Show on GitHub

AdjacencyListProtocol: VertexListGraph


                    
                    
                    DirectedAdjacencyListProtocol

Adjacency lists whose edges are directed.

Declaration

Swift

public protocol DirectedAdjacencyListProtocol: AdjacencyListProtocol, ParallelGraph
where
  VertexEdgeCollection == _AdjacencyList_DirectedVertexEdgeCollection<_EdgeData>,
  ParallelProjection == _DirectedAdjacencyList_ParallelProjection<_VertexData>,
  EdgeCollection == _AdjacencyList_DirectedEdgeCollection<_Storage>

Show on GitHub

UndirectedAdjacencyListProtocol


                    
                    
                    UndirectedAdjacencyListProtocol

Undocumented

Declaration

Swift

public protocol UndirectedAdjacencyListProtocol: AdjacencyListProtocol
where
  VertexEdgeCollection == _AdjacencyList_UndirectedVertexEdgeCollection<_EdgeData>,
  EdgeCollection == _AdjacencyList_UndirectedEdgeCollection<_Storage>,
  _VertexData: _AdjacencyListPerVertexUndirected

Show on GitHub

BidirectionalAdjacencyList

_AdjacencyListPerEdgeBidirectional
Augments _AdjacencyListPerEdge by adding reverse-edge information.
See more
Declaration
Swift

public protocol _AdjacencyListPerEdgeBidirectional : _AdjacencyListPerEdge
Show on GitHub
_AdjacencyListPerVertexBidirectional
Augments _AdjacencyListPerVertex with reverse edge information.
See more
Declaration
Swift

public protocol _AdjacencyListPerVertexBidirectional: _AdjacencyListPerVertex where EdgeData: _AdjacencyListPerEdgeBidirectional
Show on GitHub


                    
                    
                    _AdjacencyList_BidirectionalPerEdge

All internal information stored within a bidirectional graph for each edge.

Declaration

Swift

public struct _AdjacencyList_BidirectionalPerEdge<
  RawId: BinaryInteger,
  Edge: DefaultInitializable
>: _AdjacencyListPerEdgeBidirectional

Show on GitHub


                    
                    
                    _AdjacencyList_BidirectionalPerVertex

Undocumented

Declaration

Swift

public struct _AdjacencyList_BidirectionalPerVertex<
  Vertex: DefaultInitializable,
  EdgeData: _AdjacencyListPerEdgeBidirectional
>: _AdjacencyListPerVertexBidirectional

Show on GitHub

UndirectedAdjacencyListProtocol: IncidenceGraph


                    
                    
                    _AdjacencyListPerVertexUndirected

Undocumented

Declaration

Swift

public protocol _AdjacencyListPerVertexUndirected: _AdjacencyListPerVertex
where EdgeData: _AdjacencyListPerEdgeBidirectional

Show on GitHub

DirectedAdjacencyListProtocol: EdgeListGraph


                    
                    
                    _AdjacencyList_DirectedEdgeCollection

A collection of all edges in an AdjacencyList.

Declaration

Swift

public struct _AdjacencyList_DirectedEdgeCollection<Storage: Collection>: Collection
where Storage.Element: _AdjacencyListPerVertex, Storage.Index == Int

Show on GitHub

DirectedAdjacencyList

_AdjacencyList_DirectedPerEdge
Stores all relevant information for an edge within a directed adjacency list.
See more
Declaration
Swift

public struct _AdjacencyList_DirectedPerEdge<VertexId, Edge> : _AdjacencyListPerEdge where VertexId : BinaryInteger
Show on GitHub
_AdjacencyList_DirectedPerVertex
Stores all relevant information for a vertex within a directed adjacency list.
See more
Declaration
Swift

public struct _AdjacencyList_DirectedPerVertex<Vertex, EdgeData> : _AdjacencyListPerVertex where EdgeData : _AdjacencyListPerEdge
Show on GitHub

DirectedAdjacencyListProtocol: IncidenceGraph

_AdjacencyList_DirectedVertexEdgeCollection
All edges from a single vertex in an AdjacencyList graph.
See more
Declaration
Swift

public struct _AdjacencyList_DirectedVertexEdgeCollection<EdgeData> : Collection where EdgeData : _AdjacencyListPerEdge
Show on GitHub

UndirectedAdjacencyList


                    
                    
                    _AdjacencyList_UndirectedEdgeCollection

Undocumented

Declaration

Swift

public struct _AdjacencyList_UndirectedEdgeCollection<Storage: Collection>: Collection
where Storage.Element: _AdjacencyListPerVertex, Storage.Index == Int

Show on GitHub


                    
                    
                    _AdjacencyList_UndirectedEdgeId

An identifier for an edge.

Declaration

Swift

public struct _AdjacencyList_UndirectedEdgeId<RawId> where RawId : BinaryInteger

extension _AdjacencyList_UndirectedEdgeId: Equatable, Hashable, Comparable

Show on GitHub


                    
                    
                    _AdjacencyList_UndirectedPerVertex

Undocumented

Declaration

Swift

public struct _AdjacencyList_UndirectedPerVertex<
  Vertex: DefaultInitializable,
  EdgeData: _AdjacencyListPerEdgeBidirectional
>: _AdjacencyListPerVertexUndirected

Show on GitHub


                    
                    
                    _AdjacencyList_UndirectedVertexEdgeCollection

Undocumented

Declaration

Swift

public struct _AdjacencyList_UndirectedVertexEdgeCollection<
  EdgeData: _AdjacencyListPerEdgeBidirectional
>: Collection

Show on GitHub

DirectedAdjacencyListProtocol: Parallel graph operations


                    
                    
                    _DirectedAdjacencyList_ParallelProjection

A parallel representation of a DirectedAdjacencyList.

Declaration

Swift

public struct _DirectedAdjacencyList_ParallelProjection<PerVertex: _AdjacencyListPerVertex>:
  GraphProtocol,
  IncidenceGraph,
  PropertyGraph

Show on GitHub