In the first post of a series of posts, I would like to introduce some elementary graph traversal techniques and discuss the abstract tricolor algorithm. While there are several resources on graph traversals on the internet, most resources either get bogged down with terminology or go straight to the code.
Topics
Abstractly, graph traversal algorithms can be expressed in terms of the tricolor algorithm. In the tricolor algorithm each node of the graph is assigned a color that changes over time:
A typical graph traversal algorithm starts with no black nodes and the root is gray. As the algorithm proceeds, white nodes turn into gray nodes and gray nodes convert to black ones. Eventually there are no gray nodes left and the algorithm is done. The tricolor algorithm maintains a key invariant at all times: there are no edges from white nodes to black nodes. This is clearly true at the beginning (root is gray,all others are white) and it is also true at the end because we know that any remaining white nodes cannot be reached from the black nodes (a node turns black only when it has been fully explored).
The Algorithm
This algorithm is abstract. It is up to the implementation of a particular specialized traversal algorithm to :
One key advantage in defining graph search/traversal in terms of the tricolor algorithm is that the tricolor algorithm works even when gray nodes are worked on concurrently, as long as the black-white invariant is maintained.
Topics
- tricolor algorithm
- breadth-first search
- depth-first search
- cycle detection
- topological sort
- connected components
Abstractly, graph traversal algorithms can be expressed in terms of the tricolor algorithm. In the tricolor algorithm each node of the graph is assigned a color that changes over time:
- White nodes are undiscovered nodes that have not yet been seen in the current traversal and may even be unreachable.
- Black nodes are nodes that are reachable and that the algorithm is done with.
- Gray nodes are nodes that have been discovered but that the algorithm is not done with yet. They are at the frontier between the white ad black nodes.
A typical graph traversal algorithm starts with no black nodes and the root is gray. As the algorithm proceeds, white nodes turn into gray nodes and gray nodes convert to black ones. Eventually there are no gray nodes left and the algorithm is done. The tricolor algorithm maintains a key invariant at all times: there are no edges from white nodes to black nodes. This is clearly true at the beginning (root is gray,all others are white) and it is also true at the end because we know that any remaining white nodes cannot be reached from the black nodes (a node turns black only when it has been fully explored).
The Algorithm
- Initially color all nodes white (unexplored)
- Color the root gray.
- while some gray node x exist
- color some white successors of x gray
- if x has no successors left, color it black
This algorithm is abstract. It is up to the implementation of a particular specialized traversal algorithm to :
- Decide which gray node(s) x to start with
- Decide which neighbors of a gray node to color gray
- Delay coloring a node black.
One key advantage in defining graph search/traversal in terms of the tricolor algorithm is that the tricolor algorithm works even when gray nodes are worked on concurrently, as long as the black-white invariant is maintained.