DictionaryPredecessorRecorder

public struct DictionaryPredecessorRecorder<Graph: IncidenceGraph>: DefaultInitializable
where Graph.VertexId: Hashable

A dictionary that records the parents of every discovered vertex in a graph search algorithm.

Example:

var g = CompleteInfiniteGrid()
let preds = DictionaryPredecessorRecorder(for: g)
g.breadthFirstSearch(startingAt: .origin) { e, g in preds.record(e, graph: g) }
Show on GitHub

  • A dictionary of the predecessor for a vertex.

    Declaration

    Swift

    public private(set) var predecessors: [Graph.VertexId : Graph.VertexId]
    Show on GitHub

  • Creates an empty predecessor recorder.

    Declaration

    Swift

    public init()
    Show on GitHub

  • Creates an empty predecessor recorder (uses graph for type inference).

    Declaration

    Swift

    public init(for graph: Graph)
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public subscript(vertex: Graph.VertexId) -> Graph.VertexId? { get }
    Show on GitHub

  • Captures predecessor information during depth first search.

    Declaration

    Swift

    public mutating func record(_ event: DFSEvent<Graph>, graph: Graph)
    Show on GitHub

  • Captures predecessor information during Dijkstra’s search.

    Declaration

    Swift

    public mutating func record(_ event: DijkstraSearchEvent<Graph>, graph: Graph)
    Show on GitHub

  • Captures predecessor information during breadth first search.

    Declaration

    Swift

    public mutating func record(_ event: BFSEvent<Graph>, graph: Graph)
    Show on GitHub

  • Returns the sequence of vertices on the recorded path to vertex.

    Declaration

    Swift

    public func path(to vertex: Graph.VertexId) -> ReversedCollection<[Graph.VertexId]>?
    Show on GitHub