chord.util.graph
Class RPOBuilder<Node>

java.lang.Object
  chord.util.graph.RPOBuilder<Node>

public final class RPOBuilder<Node>
extends java.lang.Object

Algorithm for computing the Reverse Post Order (RPO) of the nodes in a directed graph.

Notes:

• Any parts of the directed graph unreachable from its root nodes are silently ignored.
• If the graph is acyclic (i.e. it is a DAG) then the RPO is a Topological Order.

Author:

Mayur Naik (mhn@cs.stanford.edu)

Method Summary

static <Node> java.util.List<Node>

build(IGraph<Node> graph) Provides all nodes of a given directed graph reachable from its root nodes and ordered in Reverse Post Order (RPO).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

build

public static <Node> java.util.List<Node> build(IGraph<Node> graph)

Provides all nodes of a given directed graph reachable from its root nodes and ordered in Reverse Post Order (RPO).

Parameters:

graph - A directed graph.

Returns:

All nodes of the given directed graph reachable from its root nodes and ordered in RPO.