classycle.graph
Class StrongComponentProcessor

java.lang.Object
  extended by classycle.graph.GraphProcessor
      extended by classycle.graph.StrongComponentProcessor

public class StrongComponentProcessor
extends GraphProcessor

A processor which extracts the strong components of a directed graph. A strong component is a maximal strongly connected subgraph of a directed graph. The implementation is based on Tarjan's algorithm.

Author:
Franz-Josef Elmer

Constructor Summary
StrongComponentProcessor(boolean calculateAttributes)
          Creates an instance.
 
Method Summary
protected  void finishProcessing(Vertex[] graph)
          Adds all arcs to the strong components.
 StrongComponent[] getStrongComponents()
          Returns the result of GraphProcessor.deepSearchFirst(classycle.graph.Vertex[]).
protected  void initializeProcessing(Vertex[] graph)
          Initializes processing.
protected  void processAfter(Vertex vertex)
          Processes the specified vertex after all its outgoing arcs are processed.
protected  void processArc(Vertex tail, Vertex head)
          Processes the arc specified by tail and head vertices.
protected  void processBefore(Vertex vertex)
          Processes the specified vertex before its outgoing arcs are processed.
 
Methods inherited from class classycle.graph.GraphProcessor
deepSearchFirst, process
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

StrongComponentProcessor

public StrongComponentProcessor(boolean calculateAttributes)
Creates an instance.

Parameters:
calculateAttributes - If true the attributes of the strong components will be calculated. Otherwise not.
Method Detail

getStrongComponents

public StrongComponent[] getStrongComponents()
Returns the result of GraphProcessor.deepSearchFirst(classycle.graph.Vertex[]).


initializeProcessing

protected void initializeProcessing(Vertex[] graph)
Description copied from class: GraphProcessor
Initializes processing. Will be called in method GraphProcessor.deepSearchFirst(classycle.graph.Vertex[]).

Specified by:
initializeProcessing in class GraphProcessor

processBefore

protected void processBefore(Vertex vertex)
Description copied from class: GraphProcessor
Processes the specified vertex before its outgoing arcs are processed.

Specified by:
processBefore in class GraphProcessor
Parameters:
vertex - Vertex to be processed.
Throws:
java.lang.IllegalArgumentException - if vertex is not an instance of AtomicVertex.

processArc

protected void processArc(Vertex tail,
                          Vertex head)
Description copied from class: GraphProcessor
Processes the arc specified by tail and head vertices.

Specified by:
processArc in class GraphProcessor
Parameters:
tail - Tail vertex of the arc.
head - Head vertex of the arc.
Throws:
java.lang.IllegalArgumentException - if tail and head are not an instances of AtomicVertex.

processAfter

protected void processAfter(Vertex vertex)
Processes the specified vertex after all its outgoing arcs are processed.

Specified by:
processAfter in class GraphProcessor
Parameters:
vertex - Vertex to be processed.
Throws:
java.lang.IllegalArgumentException - if vertex is not an instance of AtomicVertex.

finishProcessing

protected void finishProcessing(Vertex[] graph)
Adds all arcs to the strong components. There is an arc from a strong component to another one if there is at least one arc from a vertex of one component to a vertex the other one.

Specified by:
finishProcessing in class GraphProcessor