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 with vertexCount 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)

Available where Graph: VertexListGraph

  • Creates a PredecessorVisitor for use on graph.

    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)