BidirectionalAdjacencyList

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

extension BidirectionalAdjacencyList: BidirectionalGraph

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.

Show on GitHub

VertexId
The name of a vertex in this graph.

Note: VertexId‘s are not stable across some graph mutation operations.
Declaration
Swift

public typealias VertexId = RawId
Show on GitHub
EdgeId
The name of an edge in this graph.

Note: EdgeId‘s are not stable across some graph mutation operations.
Declaration
Swift

public typealias EdgeId = _AdjacencyList_DirectedEdgeId<RawId>
Show on GitHub
VertexCollection
A collection of all VertexId‘s in self.
Declaration
Swift

public typealias VertexCollection = Range<RawId>
Show on GitHub


                    
                    
                    _EdgeData

Data structure storing per-edge information.

Declaration

Swift

public typealias _EdgeData = _AdjacencyList_BidirectionalPerEdge<VertexId, Edge>

Show on GitHub


                    
                    
                    _VertexData

Data structure storing per-vertex data.

Declaration

Swift

public typealias _VertexData = _AdjacencyList_BidirectionalPerVertex<Vertex, _EdgeData>

Show on GitHub


                    
                    
                    EdgeCollection

The collection of all edges in self.

Declaration

Swift

public typealias EdgeCollection = _AdjacencyList_DirectedEdgeCollection<_Storage>

Show on GitHub

VertexEdgeCollection
The collection of all edges whose origin is a given vertex.
Declaration
Swift

public typealias VertexEdgeCollection = _AdjacencyList_DirectedVertexEdgeCollection<_EdgeData>
Show on GitHub


                    
                    
                    ParallelProjection

The parallel projection of self.

Declaration

Swift

public typealias ParallelProjection = _DirectedAdjacencyList_ParallelProjection<_VertexData>

Show on GitHub

_storage
The graph’s storage!
Declaration
Swift

public var _storage: _Storage
Show on GitHub
init()
Initialize an empty BidirectionalAdjacencyList.
Declaration
Swift

public init()
Show on GitHub
vertices
All VertexId‘s in self.
Declaration
Swift

public var vertices: Range<RawId> { get }
Show on GitHub

Incidence graph

edges(from:)
All edges originating from vertex.
Declaration
Swift

public func edges(from vertex: VertexId) -> VertexEdgeCollection
Show on GitHub
outDegree(of:)
The number of edges originating from vertex.
Declaration
Swift

public func outDegree(of vertex: VertexId) -> Int
Show on GitHub
subscript(vertex:)
Accesses the arbitrary data associated with vertex.
Declaration
Swift

public subscript(vertex vertex: VertexId) -> Vertex { get set }
Show on GitHub
subscript(edge:)
Accesses the arbitrary data associated with edge.
Declaration
Swift

public subscript(edge edge: EdgeId) -> Edge { get set }
Show on GitHub

SearchDefaultsGraph


                    
                    
                    DefaultColorMap

A reasonable color map implementation.

Declaration

Swift

public typealias DefaultColorMap = TablePropertyMap<`Self`, VertexId, VertexColor>

Show on GitHub

makeDefaultColorMap(repeating:)
Makes a default color map where every vertex is set to color.
Declaration
Swift

public func makeDefaultColorMap(repeating color: VertexColor) -> DefaultColorMap
Show on GitHub


                    
                    
                    makeDefaultVertexIntMap(repeating:)

Makes a default int map for every vertex.

Declaration

Swift

public func makeDefaultVertexIntMap(repeating value: Int) -> TablePropertyMap<`Self`, VertexId, Int>

Show on GitHub


                    
                    
                    makeDefaultVertexVertexMap(repeating:)

Makes a default vertex property map mapping vertices.

Declaration

Swift

public func makeDefaultVertexVertexMap(repeating vertex: VertexId) -> TablePropertyMap<`Self`, VertexId, VertexId>

Show on GitHub

Mutable graph operations

reserveCapacity(vertexCount:)
Hints self to reserve space for a total of vertexCount vertices.
Declaration
Swift

public mutating func reserveCapacity(vertexCount: Int)
Show on GitHub
removeEdge(from:to:)
Removes all edges from u to v.

If there are parallel edges, it removes all edges.

Precondition
u and v are vertices in self.

Complexity
worst case O(|E|)
Declaration
Swift

@discardableResult public mutating func removeEdge(from u: VertexId, to v: VertexId) -> Bool
Return Value

true if one or more edges were removed; false otherwise.

Show on GitHub
remove(_:)
Removes edge.

Precondition
edge is a valid EdgeId from self.
Declaration
Swift

public mutating func remove(_ edge: EdgeId)
Show on GitHub


                    
                    
                    removeEdges(where:)

Removes all edges that shouldBeRemoved.

Declaration

Swift

public mutating func removeEdges(where shouldBeRemoved: (EdgeId, `Self`) -> Bool)

Show on GitHub

removeEdges(from:where:)
Remove all out edges of vertex that satisfy the given predicate.

Complexity
O(|E|)
Declaration
Swift

public mutating func removeEdges( from vertex: VertexId, where shouldBeRemoved: (EdgeId, Self) -> Bool )
Show on GitHub
clear(vertex:)
Removes all edges from vertex.

Complexity
O(|E|)
Declaration
Swift

public mutating func clear(vertex: VertexId)
Show on GitHub
remove(_:)
Removes vertex from the graph.

Precondition
vertex is a valid VertexId for self.

Complexity
O(|E| + |V|)
Declaration
Swift

public mutating func remove(_ vertex: VertexId)
Show on GitHub

MutablePropertyGraph

addVertex(storing:)
Adds a new vertex with associated vertexProperty, returning its identifier.

Complexity
O(1) (amortized)
Declaration
Swift

public mutating func addVertex(storing vertexProperty: Vertex) -> VertexId
Show on GitHub
addEdge(from:to:storing:)
Adds a new edge from source to destination and associated edgeProperty, returning its identifier.

Complexity
O(1) (amortized)
Declaration
Swift

public mutating func addEdge( from source: VertexId, to destination: VertexId, storing edgeProperty: Edge ) -> EdgeId
Show on GitHub