DirectedAdjacencyList

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

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.

Show on GitHub

VertexId
Undocumented
Declaration
Swift

public typealias VertexId = RawId
Show on GitHub


                    
                    
                    EdgeId

Undocumented

Declaration

Swift

public typealias EdgeId = _AdjacencyList_DirectedEdgeId<RawId>

Show on GitHub

VertexCollection
Undocumented
Declaration
Swift

public typealias VertexCollection = Range<RawId>
Show on GitHub


                    
                    
                    _EdgeData

Undocumented

Declaration

Swift

public typealias _EdgeData = _AdjacencyList_DirectedPerEdge<VertexId, Edge>

Show on GitHub


                    
                    
                    _VertexData

Undocumented

Declaration

Swift

public typealias _VertexData = _AdjacencyList_DirectedPerVertex<Vertex, _EdgeData>

Show on GitHub


                    
                    
                    VertexEdgeCollection

Undocumented

Declaration

Swift

public typealias VertexEdgeCollection = _AdjacencyList_DirectedVertexEdgeCollection<_EdgeData>

Show on GitHub


                    
                    
                    EdgeCollection

The collection of all edges in self.

Declaration

Swift

public typealias EdgeCollection = _AdjacencyList_DirectedEdgeCollection<_Storage>

Show on GitHub

ParallelProjection
A parallel representation of self that can be used in parallel algorithms.
Declaration
Swift

public typealias ParallelProjection = _DirectedAdjacencyList_ParallelProjection<_VertexData>
Show on GitHub
_storage
Undocumented
Declaration
Swift

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

public init()
Show on GitHub
vertices
All vertex identifiers.
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

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

Property graph

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

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

DirectedAdjacencyList

Declaration

Declaration

Declaration

Declaration

Declaration

Declaration

Declaration

Declaration

Declaration

Declaration

Declaration

Incidence graph

Declaration

Declaration

SearchDefaultsGraph

Declaration

Declaration

Declaration

Declaration

Property graph

Declaration

Declaration

Mutable graph operations

Declaration

Declaration

Return Value

Declaration

Declaration

Declaration

Declaration

Declaration

MutablePropertyGraph

Declaration

Declaration