jpaul.Graphs
Class DiGraph<Vertex>

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

Direct Known Subclasses:

ArcBasedDiGraph, BasicBlockDiGraph, LDiGraph, 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 Navigators (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 getNavigator() 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 nodes 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,Navigator) 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 nodes: " + SCC.nodes());
            // potentially, do something more intresting with "scc" :)
        }

Version:

$Id: DiGraph.java,v 1.21 2005/10/31 04:42:23 salcianu Exp $

Author:

Alexandru Salcianu - salcianu@alum.mit.edu

See Also:

ForwardNavigator, Navigator

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 Navigator<Vertex>	constructNavigator(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.
static <Vertex> DiGraph<Vertex>	diGraph(java.util.Collection<Vertex> roots, ForwardNavigator<Vertex> fnavigator) Constructs a DiGraph object.
static <Vertex> DiGraph<Vertex>	diGraph(java.util.Collection<Vertex> roots, Navigator<Vertex> navigator) Constructs a DiGraph object.
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 exactly once for each vertex from this directed graph.
TopSortedCompDiGraph<Vertex>	getComponentDiGraph() Returns the component graph for this graph.
ForwardNavigator<Vertex>	getForwardNavigator() Returns the forward navigator for this digraph.
Navigator<Vertex>	getNavigator() Returns the (bi-directional) 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.util.Set<Vertex>	transitivePred(java.util.Collection<Vertex> roots)
java.util.Set<Vertex>	transitivePred(Vertex vertex)
java.util.Set<Vertex>	transitiveSucc(java.util.Collection<Vertex> roots)
java.util.Set<Vertex>	transitiveSucc(Vertex vertex)
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, toString, 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.

getNavigator

public Navigator<Vertex> getNavigator()

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 getNavigator and getForwardNavigator.

constructNavigator

protected Navigator<Vertex> constructNavigator(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, getNavigator 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 getNavigator 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 getNavigator).

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

diGraph

public static <Vertex> DiGraph<Vertex> diGraph(java.util.Collection<Vertex> roots,
                                               Navigator<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.

transitiveSucc

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

Returns:

Set of all transitive and reflexive successors of vertices from roots.

transitivePred

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

Returns:

Set of all transitive and reflexive predecessors of vertex

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.

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.

findPath

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

Returns:

One shortest path of vertices from source to dest, along arcs from this graph; returns null if no such path exists. The length of the path is the number of arcs.

dfs

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

DFS traversal of this digraph.

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.

forAllVertices

public void forAllVertices(Action<Vertex> action)

Executes an action exactly once for each vertex from this directed graph.

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 has a deterministic iteration order (it's 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.

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.