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

java.lang.Object
  extended by 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


Copyright © 2003-2009 Anders Møller, Aske Simon Christensen, Asger Feldthaus.