Overview  Package   Class  Use  Deprecated  Index
Home >> All >> Util >> [ Graphs overview ]	PREV CLASS  NEXT CLASS
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD	DETAIL: FIELD | CONSTR | METHOD

---

Util.Graphs
Class SCCTopSortedGraph  

java.lang.Object
  Util.Graphs.SCCTopSortedGraph

All Implemented Interfaces:

Graph, java.io.Serializable

---

public class SCCTopSortedGraph

extends java.lang.Object

implements Graph, java.io.Serializable

SCCTopSortedGraph represents a graph of strongly connected components topologically sorted in decreasing order. To obtain such a graph, use the topSort static method. It uses a Depth First Search to do the sortting in linear time (see Section 23.4 in Cormen and co for the exact algorithm).

Version:

$Id: SCCTopSortedGraph.java,v 1.3 2003/07/23 02:26:57 joewhaley Exp $

---

Field Summary
private  SCComponent	first
private static SCComponent	first_scc
private  SCComponent	last
private static SCComponent	last_scc
private static java.util.Set	reached_sccs

 

Constructor Summary
private	SCCTopSortedGraph(SCComponent first, SCComponent last)

 

Method Summary
private static void	DFS_topsort(SCComponent scc)
SCComponent	getFirst()           Returns the first (i.e.
SCComponent	getLast()           Returns the last (i.e.
Navigator	getNavigator()
java.util.Collection	getRoots()
static SCCTopSortedGraph	topSort(SCComponent root)           Sorts all the strongly connected component reachable from root in decreasing topological order.
static SCCTopSortedGraph	topSort(java.util.Set roots)           Sorts all the strongly connected component reachable from one of the SCComponents from roots in decreasing topological order.

 

Methods inherited from class java.lang.Object

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

 

Field Detail

first

private SCComponent first

---

last

private SCComponent last

---

reached_sccs

private static java.util.Set reached_sccs

---

first_scc

private static SCComponent first_scc

---

last_scc

private static SCComponent last_scc

Constructor Detail

SCCTopSortedGraph

private SCCTopSortedGraph(SCComponent first,
                          SCComponent last)

Method Detail

getFirst

public final SCComponent getFirst()

Returns the first (i.e. one of the topologically biggest) SCComponent

---

getLast

public final SCComponent getLast()

Returns the last (i.e. one of the topologically smallest) SCComponent

---

topSort

public static SCCTopSortedGraph topSort(SCComponent root)

Sorts all the strongly connected component reachable from root in decreasing topological order. This method sets the nextTopSort and prevTopSort fields of the SCComponents, arranging then in a double linked list according to the aforementioned order.
It returns a SCCTopSortedGraph containing the first and the last elements of this list. Note: This is just a convenient function, for more than one root, please use the more general topSort(Set).

---

topSort

public static SCCTopSortedGraph topSort(java.util.Set roots)

Sorts all the strongly connected component reachable from one of the SCComponents from roots in decreasing topological order. This method sets the nextTopSort and prevTopSort fields of the SCComponents, arranging then in a double linked list according to the aforementioned order.
It returns a SCCTopSortedGraph containing the first and the last elements of this list. Note: the roots parameter must contain only root Sccomponents (ie SCComponents without any entering edge.

---

DFS_topsort

private static void DFS_topsort(SCComponent scc)

---

getRoots

public java.util.Collection getRoots()

Specified by:

getRoots in interface Graph

---

getNavigator

public Navigator getNavigator()

Specified by:

getNavigator in interface Graph

---

Overview  Package   Class  Use  Deprecated  Index
Home >> All >> Util >> [ Graphs overview ]	PREV CLASS  NEXT CLASS
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD	DETAIL: FIELD | CONSTR | METHOD

---