jpaul.Graphs
Class TopSortedCompDiGraph<Vertex>

java.lang.Object
  jpaul.Graphs.DiGraph<SCComponent<Vertex>>
      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)