(algorithm)
Definition: A class of algorithms to mark all reachable nodes in a directed graph by reversing pointers on the way down, then restoring them upon leaving. It uses only a few bits of extra space per node and a few work pointers.
Aggregate child (... is a part of or used in me.)
directed graph, binary tree representation of trees.
See also depth-first search.
Note: The graph must be a binary graph, that is, nodes have out-degree at most two. Any graph may be represented as a binary graph using a technique like binary tree representation of trees. This algorithm works for graphs with cycles, so is not limited to binary trees.
This is used in garbage collection to mark all nodes in use. Any node still unmarked after the algorithm finishes is unused and may be collected. Although a depth-first search to mark nodes is easy to write, it takes extra space proportional to the maximum search depth, which could be all nodes.
Author: PEB
Herbert Schorr and William M. Waite, An efficient machine-independent procedure for garbage collection in various list structures, CACM, 10(8):501-506, August 1967.
There are many variants, better presentations, and proofs of correctness, such as David Gries, Schorr-Waite Graph Marking Algorithm - Developed With Style, 2007.
Historical Note
Knuth says this method was "discovered independently by Peter Deutsch and by Herbert Schorr and W. M. Waite in 1965" [Knuth97, 1:418, Sect. 2.3.5], but I cannot find any other documentation crediting Deutsch.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 20 November 2008.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Paul E. Black, "Schorr-Waite graph marking algorithm", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 20 November 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/SchorrWaiteGraphMarking.html