Graph Algorithm State

VertexColor is used to represent which vertices have been seen during graph searches.

Note: although there are vague interpretations for what each color means, their exact properties are dependent upon the kind of graph search algorithm being executed.

The events that occur during breadth first search within a graph.

The events that occur during depth first search within a graph.

The events that occur during Dijkstra’s search within a graph.

Represents a distance measure on a graph.

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 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) }

Errors that can be thrown during graph processing.