soot.toolkits.graph
Class StronglyConnectedComponentsFast<N>

java.lang.Object
  soot.toolkits.graph.StronglyConnectedComponentsFast<N>

public class StronglyConnectedComponentsFast<N>
extends Object

Identifies and provides an interface to query the strongly-connected components of DirectedGraph instances. Uses Tarjan's algorithm.

Author:

Eric Bodden

See Also:

DirectedGraph

Field Summary

protected List<List<N>>	componentList
protected DirectedGraph<N>	g
protected int	index
protected Map<N,Integer>	indexForNode
protected Map<N,Integer>	lowlinkForNode
protected Stack<N>	s
protected List<List<N>>	trueComponentList

Constructor Summary

StronglyConnectedComponentsFast(DirectedGraph<N> g)

Method Summary

List<List<N>>	getComponents()
List<List<N>>	getTrueComponents()
protected void	recurse(N v)

Methods inherited from class java.lang.Object

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

Field Detail

componentList

protected final List<List<N>> componentList

trueComponentList

protected final List<List<N>> trueComponentList

index

protected int index

indexForNode

protected Map<N,Integer> indexForNode

lowlinkForNode

protected Map<N,Integer> lowlinkForNode

s

protected Stack<N> s

g

protected DirectedGraph<N> g

Constructor Detail

StronglyConnectedComponentsFast

public StronglyConnectedComponentsFast(DirectedGraph<N> g)

Parameters:

g - a graph for which we want to compute the strongly connected components.

See Also:

DirectedGraph

Method Detail

recurse

protected void recurse(N v)

getComponents

public List<List<N>> getComponents()

Returns:

the list of the strongly-connected components

getTrueComponents

public List<List<N>> getTrueComponents()

Returns:

the list of the strongly-connected components, but only those that are true components, i.e. components which have more than one element or consists of one node that has itself as a successor