dk.brics.string.directedgraph
Class StronglyConnectedComponents<N extends GraphNode,C extends GraphComponent<N>>

java.lang.Object
  dk.brics.string.directedgraph.StronglyConnectedComponents<N,C>

public class StronglyConnectedComponents<N extends GraphNode,C extends GraphComponent<N>>
extends Object

Finds strongly connected components of a directed graph.

Constructor Summary

StronglyConnectedComponents(DirectedGraph<N,C> g)
Finds strongly connected components using Tarjan's algorithm.

Method Summary

void	add(N n, C c) Adds a new node to a component.
C	getComponent(N n) Returns the component of the given node.
Collection<C>	getComponents() Returns the (unmodifiable) collection of components.
String	toString()

Methods inherited from class java.lang.Object

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

Constructor Detail

StronglyConnectedComponents

public StronglyConnectedComponents(DirectedGraph<N,C> g)

Finds strongly connected components using Tarjan's algorithm. Components are ordered bottom-up, i.e. leaves in the SCC tree appear first and roots last.

Method Detail

add

public void add(N n,
                C c)

Adds a new node to a component.

getComponent

public C getComponent(N n)

Returns the component of the given node.

getComponents

public Collection<C> getComponents()

Returns the (unmodifiable) collection of components.

toString

public String toString()

Overrides:

toString in class Object