jpaul.Graphs
Class DiGraph<Vertex>

java.lang.Object
  jpaul.Graphs.DiGraph<Vertex>

Direct Known Subclasses:

ArcBasedDiGraph, BasicBlockDiGraph, LabeledDiGraph, TopSortedCompDiGraph

public abstract class DiGraph<Vertex>
extends java.lang.Object

DiGraph models a directed graph. A directed graph is defined by a set of root vertices and a navigator. The navigator is an iterator over the graph: given a vertex v, it gives v's direct successors (i.e., vertices pointed to by arcs that start in v), and (optionally), v's direct predecessors. The digraph contains all (transitive and reflexive) successors of the root vertices.

This design allows the use of many graph algorithms (e.g., construction of strongly connected components) even for very general graphs where the arcs model only a subtle semantic relation (e.g., caller-callee) that is not explicitly stored in the vertices.

There are two kinds of navigators: ForwardNavigators (give only successors) and bi-directional BiDiNavigators (both successors and predecessors). For a given graph you should define at least one of them, i.e., you should override at least one of the methods getBiDiNavigator() and getForwardNavigator() from DiGraph. The standard implementation of these methods is able to construct one navigator starting from the other one. First, a bi-directional navigator is trivially a forward one too. Next, we can use the roots and the forward navigator to build the successor relation, and next revert it to build the predecessor relation (linear in the size of the graph).

If you decide to implement both navigators (e.g., for efficiency) you should make sure the two navigators are consistent. To see what this means, let fnav and nav be the forward, respectively the full navigator associated with a digraph. For any vertex v, fnav.next(v) should return the same vertices as nav.next(v). In addition, nav itself should be consistent, i.e., for any vertices v1, v2 from the digraph, if v1 appears in nav.next(v2), then v2 should appear in nav.prev(v1).

To create a DiGraph, you can use of the following two static methods: diGraph(Collection,BiDiNavigator) and diGraph(Collection,ForwardNavigator). For fancier things, you can also subclass DiGraph.

Most of the algorithms are implemented as instance methods; very few are also implemented as static methods. Here is some sample code:

        // set of arcs as a relation vertex -> set of succs
        final jpaul.DataStructs.Relation arcs = ...;
        // construct a directed graph based on the relation arcs
        DiGraph diGraph = DiGraph.diGraph
            (// [ ... ]  some set of roots,
             new ForwardNavigator() {
                 public List next(Vertex v) {
                     return new ArrayList(arcs.getValues(v));
                 }
             });

        // iterate over the list of strongly connected components
        // in incremental topological order
        for(SCComponent scc : diGraph.getComponentDiGraph().incrOrder()) {
            System.out.println("SCC vertices: " + scc.vertices());
            // potentially, do something more interesting with "scc" :)
        }

Version:

$Id: DiGraph.java,v 1.36 2006/03/21 17:37:30 adam_kiezun Exp $

Author:

Alexandru Salcianu - salcianu@alum.mit.edu

See Also:

ForwardNavigator, BiDiNavigator

Field Summary

protected boolean

CACHING

Constructor Summary

	DiGraph() Constructs a DiGraph with no caching (the safest choice).
protected	DiGraph(boolean CACHING) Constructs a DiGraph.

Method Summary

protected BiDiNavigator<Vertex>	constructBiDiNavigator(RelationFactory<Vertex,Vertex> relFact) Construct a full navigator, starting from the forward navigator, as given by the method getForwardNavigator.
java.util.Set<Vertex>	dfs(Action<Vertex> onEntry, Action<Vertex> onExit) DFS traversal of this digraph.
java.util.Set<Vertex>	dfs2(ActionPredicate<Vertex> onEntry, Action<Vertex> onExit) More customizable dfs traversal than that performed by the method dfs.
static <Vertex> DiGraph<Vertex>	diGraph(java.util.Collection<Vertex> roots, BiDiNavigator<Vertex> navigator) Constructs a DiGraph object.
static <Vertex> DiGraph<Vertex>	diGraph(java.util.Collection<Vertex> roots, ForwardNavigator<Vertex> fnavigator) Constructs a DiGraph object.
java.util.List<Vertex>	findPath(java.util.Collection<Vertex> sources, Predicate<Vertex> predDest)
java.util.List<Vertex>	findPath(Vertex source, Vertex dest)
static <Vertex> java.util.List<Vertex>	findPath(Vertex source, Vertex dest, ForwardNavigator<Vertex> navigator)
void	forAllVertices(Action<Vertex> action) Executes an action at most once for each vertex from this directed graph.
BiDiNavigator<Vertex>	getBiDiNavigator() Returns the (bi-directional) navigator for this digraph.
TopSortedCompDiGraph<Vertex>	getComponentDiGraph() Returns the component graph for this graph.
ForwardNavigator<Vertex>	getForwardNavigator() Returns the forward navigator for this digraph.
abstract java.util.Collection<Vertex>	getRoots() Returns the roots of this directed graph.
long	numArcs() Returns the number of arcs in this directed graph.
int	numVertices() Returns the number of vertices in this directed graph.
DiGraph<Vertex>	reverseDiGraph() Returns a reverse form of this directed graph: a directed graph with the same set of vertices, that contains an arc from v1 to v2 iff this graph contains an arc from v2 to v1.
DiGraph<Vertex>	subDiGraph(java.util.Collection<Vertex> verts) Returns a subgraph of this directed graph containing only the vertices from verts.
java.lang.String	toString() Returns a string representation of this DiGraph.
java.util.Set<Vertex>	transitivePred(java.util.Collection<Vertex> roots)
java.util.Set<Vertex>	transitivePred(Vertex vertex)
java.util.Set<Vertex>	transitivePredWithFrontier(java.util.Collection<Vertex> roots, Predicate<Vertex> frontier, boolean includeFrontier)
java.util.Set<Vertex>	transitiveSucc(java.util.Collection<Vertex> roots)
java.util.Set<Vertex>	transitiveSucc(Vertex vertex)
java.util.Set<Vertex>	transitiveSuccWithFrontier(java.util.Collection<Vertex> roots, Predicate<Vertex> frontier, boolean includeFrontier)
static <V> DiGraph<V>	union(DiGraph<V> dg1, DiGraph<V> dg2) Computes the union of two directed graphs.
java.util.Set<Vertex>	vertices() Returns the set of all vertices from this digraph: vertices that are (trasitively and reflexively) reachable from the root vertices by following the forward arcs provided by the navigator.

Methods inherited from class java.lang.Object

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

Field Detail

CACHING

protected final boolean CACHING

Constructor Detail

DiGraph

public DiGraph()

Constructs a DiGraph with no caching (the safest choice).

DiGraph

protected DiGraph(boolean CACHING)

Constructs a DiGraph.

Parameters:

CACHING - If true, the implementation of the various methods of this DiGraph assume that the graph does not change in time. Therefore, caching is used for performance reasons: e.g., once the set of vertices is computed, it is cached and used ever after.

Method Detail

getRoots

public abstract java.util.Collection<Vertex> getRoots()

Returns the roots of this directed graph. By "roots of a digraph" we mean any set of vertices such that one can explore the entire graph by (transitively) navigating on their outgoing arcs (using the next method of the navigator). Notice that this set is not uniquely defined; also, it is OK to return ALL the vertices from the digraph. The caller is not supposed to mutate the returned collection.

getBiDiNavigator

public BiDiNavigator<Vertex> getBiDiNavigator()

Returns the (bi-directional) navigator for this digraph. The default implementation gets the forward navigator by calling getForwardNavigator, explores the entire digraph and constructs the predecessor relation. Clearly, this is quite costly, and does not terminate for infinite digraphs.

Note: You MUST overwrite at least one of getBiDiNavigator and getForwardNavigator.

constructBiDiNavigator

protected BiDiNavigator<Vertex> constructBiDiNavigator(RelationFactory<Vertex,Vertex> relFact)

Construct a full navigator, starting from the forward navigator, as given by the method getForwardNavigator. To construct the list of prdecessors, we reverse the edges by with the help of a relation constructed using the forward naviator. By default, getBiDiNavigator calls this method using the default (hash-map and hash-set based) jpaul.DataStructs.MapSetRelationFactory. For a graph with a small degree, a subclass may choose to override getBiDiNavigator to use some other RelationFactory.

getForwardNavigator

public ForwardNavigator<Vertex> getForwardNavigator()

Returns the forward navigator for this digraph. The default implementations returns the bi-directional navigator (obtained by calling getBiDiNavigator).

Note: You MUST overwrite at least one of getBiDiNavigator and getForwardNavigator.

diGraph

public static <Vertex> DiGraph<Vertex> diGraph(java.util.Collection<Vertex> roots,
                                               BiDiNavigator<Vertex> navigator)

Constructs a DiGraph object.

Parameters:

roots - Collection of root vertices. This collection will be used directly, without being cloned or copied into another collection; none of the graph algoritrhms will mutate it.

navigator - Bi-directional digraph navigator

diGraph

public static <Vertex> DiGraph<Vertex> diGraph(java.util.Collection<Vertex> roots,
                                               ForwardNavigator<Vertex> fnavigator)

Constructs a DiGraph object.

Parameters:

roots - Collection of root vertices. This collection will be used directly, without being cloned or copied into another collection; none of the graph algorithms will mutate it.

fnavigator - forward digraph navigator

transitiveSucc

public java.util.Set<Vertex> transitiveSucc(Vertex vertex)

Returns:

Set of all transitive and reflexive successors of vertex. The caller is free to mutate the returned set.

transitiveSucc

public java.util.Set<Vertex> transitiveSucc(java.util.Collection<Vertex> roots)

Returns:

Set of all transitive and reflexive successors of vertices from roots. The caller is free to mutate the returned set.

transitiveSuccWithFrontier

public java.util.Set<Vertex> transitiveSuccWithFrontier(java.util.Collection<Vertex> roots,
                                                        Predicate<Vertex> frontier,
                                                        boolean includeFrontier)

Returns:

Set of all transitive and reflexive successors of vertices from roots, but not navigating through the frontier vertices indicated by the predicate frontier. This is equivalent to the classic transitiveSucc(Collection) in a directed graph identical to this one, except that no arc exits the frontier vertices. The boolean parameter includeFrontier indicates whether to include the reachable frontier vertices in the returned set.

transitivePred

public java.util.Set<Vertex> transitivePred(Vertex vertex)

Returns:

Set of all transitive and reflexive predecessors of vertex. The caller is free to mutate the returned set.

transitivePred

public java.util.Set<Vertex> transitivePred(java.util.Collection<Vertex> roots)

Returns:

Set of all transitive and reflexive predecessors of the vertices from roots. The caller is free to mutate the returned set.

transitivePredWithFrontier

public java.util.Set<Vertex> transitivePredWithFrontier(java.util.Collection<Vertex> roots,
                                                        Predicate<Vertex> frontier,
                                                        boolean includeFrontier)

Returns:

Set of all transitive and reflexive predecessors of vertices from roots, but not navigating through the frontier vertices indicated by the predicate frontier. This is equivalent to the classic transitivePred(Collection) in a directed graph identical to this one, except that no arc enters the frontier vertices. The boolean parameter includeFrontier indicates whether to include the reachable frontier vertices in the returned set.

findPath

public static <Vertex> java.util.List<Vertex> findPath(Vertex source,
                                                       Vertex dest,
                                                       ForwardNavigator<Vertex> navigator)

Returns:

One shortest path of vertices from source to dest, along arcs indicated by navigator; returns null if no such path exists. The caller is free to mutate the returned list.

findPath

public java.util.List<Vertex> findPath(Vertex source,
                                       Vertex dest)

Returns:

One shortest path (as number of arcs) from source to dest, along arcs from this graph; returns null if no such path exists. The caller is free to mutate the returned list.

findPath

public java.util.List<Vertex> findPath(java.util.Collection<Vertex> sources,
                                       Predicate<Vertex> predDest)

Returns:

One shortest path (as number of arcs) from one of the vertices from sources to a vertex that satisfies the predDest predicate, along arcs from this graph; returns null if no such path exists. The caller is free to mutate the returned list.

dfs

public java.util.Set<Vertex> dfs(Action<Vertex> onEntry,
                                 Action<Vertex> onExit)

DFS traversal of this digraph. The traversal may be stoped at any point by throwing an InterruptTraversalException from one of the visitors (the arguments of this method); the exception is caught internally by the implementation of this method.

Parameters:

onEntry - action executed when a node is first time visited by the DFS traversal

onExit - action executed after the DFS traversal of a node finished

Returns:

Set of visited vertices. The caller is free to mutate the returned set.

dfs2

public java.util.Set<Vertex> dfs2(ActionPredicate<Vertex> onEntry,
                                  Action<Vertex> onExit)

More customizable dfs traversal than that performed by the method dfs. On entry to a specific (yet-unvisited) vertex v, the traversal adds the node to the set of visited vertices and performs the onEntry ActionPredicate. If the value returned by onEntry is true, the visit of the vertex continues as in the case of the simple traversal dfs(jpaul.Misc.Action, jpaul.Misc.Action) with the (recursive) visit of the children and the execution of the action onExit. OTHERWISE, the visit of the current vertex v stops immediately: no recursive visit of its children, no execution of the exit action.

Notice that the onEntry parameter is a combination of a predicate and an action. Initially, we thought about having two parameters: a predicate and an action. Still, that solution would left unspecified the problem of the order between the predicate and the action. Worse still, one can imagine the action being split into two parts: one executed (unconditionally) before the predicate, and the second one executed (conditionally) after the predicate. To simplify things, we decided to allow the client to specify the desired combination of an action and a predicate.

As in the case of the "simple" {#dfs dfs}, the traversal may be stoped at any point by throwing an InterruptTraversalException from one of the visitors (the arguments of this method); the exception is caught internally by the implementation of this method. Notice the difference between the case when onEntry returns false and the case when onEntry or onExit throws an InterruptTraversalException: in the first case, we skip only the (recursive) visit of the current vertex's children; in the second case, we skip the visit of all the remaining vertices.

Parameters:

onEntry - action executed when a node is first time visited by the DFS traversal

onExit - action executed after the DFS traversal of a node finished

Returns:

Set of visited vertices. The caller is free to mutate the returned set.

forAllVertices

public void forAllVertices(Action<Vertex> action)

Executes an action at most once for each vertex from this directed graph. The traversal may be terminated at each moment by throwing an InterruptTraversalException. If no such exception is thrown, then action is applied exactly once to each vertex from this digraph. The InterruptTraversalException (if any) is caught inside this method.

See Also:

vertices()

getComponentDiGraph

public TopSortedCompDiGraph<Vertex> getComponentDiGraph()

Returns the component graph for this graph. The "component graph" of a graph G is the directed, acyclic graph consisting of the strongly connected components of G. As it doesn't affect the asymptotic complexity, we also sort it topologically.

vertices

public java.util.Set<Vertex> vertices()

Returns the set of all vertices from this digraph: vertices that are (trasitively and reflexively) reachable from the root vertices by following the forward arcs provided by the navigator.

The returned set is unmodifiable and has a deterministic iteration order (it's based on a LinkedHashSet). Moreover, if the following conditions are met, different calls to vertices() return equal sets of vertices, with the same deterministic iteration order; here are the conditions: (1) the navigator and the set of graph roots do not change, (2) for each node, the forward graph navigator always returns the same list of neighbors (instead of re-arragements of them), (3) the set of roots has a deterministic iteration order.

reverseDiGraph

public DiGraph<Vertex> reverseDiGraph()

Returns a reverse form of this directed graph: a directed graph with the same set of vertices, that contains an arc from v1 to v2 iff this graph contains an arc from v2 to v1.

subDiGraph

public DiGraph<Vertex> subDiGraph(java.util.Collection<Vertex> verts)

Returns a subgraph of this directed graph containing only the vertices from verts.

numVertices

public int numVertices()

Returns the number of vertices in this directed graph. Complexity: linear in the size of the graph. Cached if the CACHING argument to the constructor was true.

numArcs

public long numArcs()

Returns the number of arcs in this directed graph. Complexity: linear in the size of the graph. Cached if the CACHING argument to the constructor was true.

toString

public java.lang.String toString()

Returns a string representation of this DiGraph. This string representation is adequate for debugging small graphs. For more complex graphs, try to output a dot representation of the graph and use an external tool to visualize it.

Overrides:

toString in class java.lang.Object

union

public static <V> DiGraph<V> union(DiGraph<V> dg1,
                                   DiGraph<V> dg2)

Computes the union of two directed graphs. The resulting directed graph contains all the arcs of the two original directed arcs. The union DiGraph is not computed explicitly; instead, the lists of predecessors/successors are generated on-demand.