jpaul.Graphs
Class TopSortedCompDiGraph<Vertex>

java.lang.Object
  extended by jpaul.Graphs.DiGraph<SCComponent<Vertex>>
      extended by jpaul.Graphs.TopSortedCompDiGraph<Vertex>

public class TopSortedCompDiGraph<Vertex>
extends DiGraph<SCComponent<Vertex>>

TopSortedCompDiGraph is a topologically-sorted component digraph. Given a digraph, its component digraph is the (acyclic!) digraph having as vertices the strongly-connected components of the original digraph (its arcs are trivially induced by the original arcs). Being acyclic, the component digraph admits a topological ordering.

Version:
$Id: TopSortedCompDiGraph.java,v 1.8 2006/03/14 02:29:31 salcianu Exp $
Author:
Alexandru Salcianu - salcianu@alum.mit.edu

Field Summary
 
Fields inherited from class jpaul.Graphs.DiGraph
CACHING
 
Constructor Summary
TopSortedCompDiGraph(DiGraph<Vertex> graph)
          Constructs the topologically sorted component digraph of digraph.
 
Method Summary
 java.util.List<SCComponent<Vertex>> decrOrder()
           
 BiDiNavigator<SCComponent<Vertex>> getBiDiNavigator()
          Returns the (bi-directional) navigator for this digraph.
 java.util.Collection<SCComponent<Vertex>> getRoots()
          Returns the roots of this directed graph.
 SCComponent<Vertex> getScc(Vertex v)
           
 java.util.Map<Vertex,SCComponent<Vertex>> getVertex2SccMap()
           
 java.util.List<SCComponent<Vertex>> incrOrder()
           
 
Methods inherited from class jpaul.Graphs.DiGraph
constructBiDiNavigator, dfs, dfs2, diGraph, diGraph, findPath, findPath, findPath, forAllVertices, getComponentDiGraph, getForwardNavigator, numArcs, numVertices, reverseDiGraph, subDiGraph, toString, transitivePred, transitivePred, transitivePredWithFrontier, transitiveSucc, transitiveSucc, transitiveSuccWithFrontier, union, vertices
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

TopSortedCompDiGraph

public TopSortedCompDiGraph(DiGraph<Vertex> graph)
Constructs the topologically sorted component digraph of digraph.

Method Detail

getRoots

public java.util.Collection<SCComponent<Vertex>> getRoots()
Description copied from class: DiGraph
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.

Specified by:
getRoots in class DiGraph<SCComponent<Vertex>>

getBiDiNavigator

public BiDiNavigator<SCComponent<Vertex>> getBiDiNavigator()
Description copied from class: DiGraph
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.

Overrides:
getBiDiNavigator in class DiGraph<SCComponent<Vertex>>
Returns:
Bi-directional navigator for the component graph.

decrOrder

public java.util.List<SCComponent<Vertex>> decrOrder()
Returns:
List of the strongly-connected components of the underlying digraph, in decreasing topologic order, i.e., starting with the SCCs with no incoming arcs.

incrOrder

public java.util.List<SCComponent<Vertex>> incrOrder()
Returns:
List of the strongly-connected components of the underlying digraph, in increasing topologic order, i.e., starting with the SCCs with no outgoing arcs.

getScc

public SCComponent<Vertex> getScc(Vertex v)
Returns:
Strongly-connected component that v belongs to; returns null iff v does not appear in the original dag.

For space-savings purposes, we do NOT construct a map from vertices to SCCs; instead, each getScc query takes time linear in the number of SCCs. If you do many calls to this method, you may want to use getVertex2SccMap().


getVertex2SccMap

public java.util.Map<Vertex,SCComponent<Vertex>> getVertex2SccMap()
Returns:
Map from each vertex from the original dag to its corresponding strongly-connected component. You should use this method in case you want to do many getScc-like queries (getScc is quite expensive). The returned map has a predictve iteration order (it's a LinkedHashMap).
See Also:
getScc(Vertex)


Copyright 2005 Alexandru Salcianu - salcianu@alum.mit.edu