jwutil.graphs.SCComponent
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||
java.lang.Object
public final class SCComponent
SCComponent models a Strongly connected component of a
graph. The only way to split a graph into SCComponent s is
though buildSCC. That method is quite flexible: all it needs
is a root node (or a set of root nodes) and a Navigator : an object
implementing the Navigator interface that provides the edges
coming into/going out of a given Object. So, it can build
strongly connected components even for graphs that are not built up from
CFGraphable nodes, a good example being the set of methods
where the edges represent the caller-callee relation (in this case, the
strongly connected components group together sets of mutually recursive
methods).
| Field Summary | |
|---|---|
static boolean |
DETERMINISTIC
|
static Navigator |
SCC_NAVIGATOR
Default navigator through a component graph (a dag of strongly connected components). |
| Method Summary | |
|---|---|
static java.util.Set |
buildSCC(java.util.Collection roots,
Navigator navigator)
Constructs the strongly connected components of the graph containing all the nodes reachable on paths that originate in nodes from roots. |
static java.util.Set |
buildSCC(Graph graph)
Convenient version of buildSCC(Object[],Navigator) |
static SCComponent |
buildSCC(java.lang.Object root,
Navigator navigator)
Convenient version for the single root case (see the other buildSCC for details). |
int |
compareTo(java.lang.Object o)
|
boolean |
contains(java.lang.Object node)
Checks whether node belongs to this\
strongly connected component. |
java.lang.Object[] |
entries()
Returns the entry nodes of this strongly connected
component. |
boolean |
equals(java.lang.Object o)
|
java.lang.Object[] |
exits()
Returns the exit nodes of this strongly connected
component. |
void |
fillEntriesAndExits(Navigator nav)
|
int |
getId()
Returns the numeric ID of this SCComponent. |
int |
hashCode()
|
boolean |
isLoop()
Checks whether this strongly connected component
corresponds to a loop, ie it has at least one arc to itself. |
java.util.List |
listTopSort()
Returns the list of SCComponent s in topologically-sorted
order. |
SCComponent[] |
next()
|
SCComponent |
next(int i)
Returns the i th successor. |
int |
nextLength()
Returns the number of successors. |
SCComponent |
nextTopSort()
Returns the next SCComponent according to the decreasing
topological order |
java.lang.Object[] |
nodes()
Returns the nodes of this strongly connected component;
array version - good for iterating over the elements of the SCC. |
java.util.Set |
nodeSet()
Returns the nodes of this strongly connected component
(set version). |
SCComponent[] |
prev()
|
SCComponent |
prev(int i)
Returns the i th predecessor. |
int |
prevLength()
Returns the number of predecessors. |
SCComponent |
prevTopSort()
Returns the previous SCComponent according to the
decreasing topological order |
int |
size()
Returns the number of nodes in this strongly connected
component. |
java.lang.String |
toString()
Pretty print debug function. |
| Methods inherited from class java.lang.Object |
|---|
clone, finalize, getClass, notify, notifyAll, wait, wait, wait |
| Field Detail |
|---|
public static final Navigator SCC_NAVIGATOR
public static final boolean DETERMINISTIC
| Method Detail |
|---|
public static final java.util.Set buildSCC(Graph graph)
buildSCC(Object[],Navigator)
graph - directed graph
graph's strongly connected components
public static final SCComponent buildSCC(java.lang.Object root,
Navigator navigator)
buildSCC for details). Returns the single element of the
set of top level SCCs.
public static final java.util.Set buildSCC(java.util.Collection roots,
Navigator navigator)
roots. The edges are indicated by navigator.
Returns the set of the root SCComponents, the components
that are not pointed by any other component. This constraint is actively
used in the topological sorting agorithm (see
SCCTopSortedGraph).
public final void fillEntriesAndExits(Navigator nav)
public int getId()
this SCComponent.
Just for debug purposes ...
public final boolean isLoop()
this strongly connected component
corresponds to a loop, ie it has at least one arc to itself.
public int compareTo(java.lang.Object o)
compareTo in interface java.lang.Comparablepublic final int nextLength()
public final SCComponent next(int i)
i th successor.
public final SCComponent[] next()
public final int prevLength()
public final SCComponent prev(int i)
i th predecessor.
public final SCComponent[] prev()
public final java.util.Set nodeSet()
this strongly connected component
(set version).
public final java.lang.Object[] nodes()
this strongly connected component;
array version - good for iterating over the elements of the SCC.
public final int size()
this strongly connected
component.
public final boolean contains(java.lang.Object node)
node belongs to this\
strongly connected component.
public final java.lang.Object[] entries()
this strongly connected
component. These are the nodes taht are reachable from outside the
component.
public final java.lang.Object[] exits()
this strongly connected
component. These are the nodes that have arcs toward nodes outside the
component.
public final SCComponent nextTopSort()
SCComponent according to the decreasing
topological order
public final SCComponent prevTopSort()
SCComponent according to the
decreasing topological order
public final java.util.List listTopSort()
SCComponent s in topologically-sorted
order.
public final java.lang.String toString()
toString in class java.lang.Objectpublic int hashCode()
hashCode in class java.lang.Objectpublic boolean equals(java.lang.Object o)
equals in class java.lang.Object
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||