TablePredecessorRecorder
public struct TablePredecessorRecorder<Graph> where Graph : IncidenceGraph
A table that records the parents of every discovered vertex in a graph search algorithm.
Example:
var g = makeAdjacencyList()
let predecessors = TablePredecessorRecorder(for: g)
g.breadthFirstSearch(startingAt: g.vertices.first!) { e, g in
predecessors.record(e, graph: g)
}
-
A table of the predecessor for a vertex, organized by
Graph.VertexId.index
.Declaration
Swift
public private(set) var predecessors: [Graph.VertexId?]
-
Creates a PredecessorVisitor for use on graph
Graph
withvertexCount
verticies.Declaration
Swift
public init(vertexCount: Int)
-
Returns the sequence of vertices on the recorded path to
vertex
.Declaration
Swift
public func path(to vertex: Graph.VertexId) -> ReversedCollection<[Graph.VertexId]>?
-
Captures predecessor information during depth first search.
Declaration
Swift
public mutating func record(_ event: DFSEvent<Graph>, graph: Graph)
-
Captures predecessor information during Dijkstra’s search.
Declaration
Swift
public mutating func record(_ event: DijkstraSearchEvent<Graph>, graph: Graph)
-
Captures predecessor information during breadth first search.
Declaration
Swift
public mutating func record(_ event: BFSEvent<Graph>, graph: Graph)
-
Creates a
PredecessorVisitor
for use ongraph
.Note: use this initializer to avoid spelling out the types, as this initializer helps along type inference nicely.
Declaration
Swift
public init(for graph: Graph)