classycle.graph

Class GraphProcessor

java.lang.Object

classycle.graph.GraphProcessor

Direct Known Subclasses:

LongestWalkProcessor, PackageProcessor, StrongComponentProcessor

public abstract class GraphProcessor
extends java.lang.Object

Abstract class for all algorithms based on deep search first. This class is designed in accordance with the Template Method pattern. The basic algorithm (implemented in the method process(classycle.graph.Vertex)) reads:

    vertex.visit();
    processBefore(vertex);
    for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i < n; i++) {
      processArc(vertex, vertex.getHeadVertex(i));
    }
    processAfter(vertex);
  

The methods initializeProcessing(), processBefore(), processArc(), and processAfter() have to be implemented by concrete classes.

The class will be used by creating an instance and invoking deepSearchFirst() one or several times. Either the graph will be modified or some result objects are created which can be obtained by special methods defined in concrete subclasses. Note, that a GraphProcessor is not thread-safe.

Author:

Franz-Josef Elmer

Constructor Summary

Constructors

Constructor and Description
GraphProcessor()

Method Summary

Methods

Modifier and Type	Method and Description
void	deepSearchFirst(Vertex[] graph) Performs a deep search first of the specified graph.
protected abstract void	finishProcessing(Vertex[] graph) Finishes processing.
protected abstract void	initializeProcessing(Vertex[] graph) Initializes processing.
protected void	process(Vertex vertex) Processes the specified vertex.
protected abstract void	processAfter(Vertex vertex) Processes the specified vertex after its arcs have been processed.
protected abstract void	processArc(Vertex tail, Vertex head) Processes the arc specified by tail and head vertices.
protected abstract void	processBefore(Vertex vertex) Processes the specified vertex before its outgoing arcs are processed.

Methods inherited from class java.lang.Object

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

Constructor Detail

GraphProcessor

public GraphProcessor()

Method Detail

deepSearchFirst

public void deepSearchFirst(Vertex[] graph)

Performs a deep search first of the specified graph. First, processing will be initialized and all vertices of the graph will be reset. Then for all unvisited vertices the method process(Vertex) will be invoked. At last, processing will be finished.

Parameters:

graph - A directed graph.

process

protected void process(Vertex vertex)

Processes the specified vertex.

initializeProcessing

protected abstract void initializeProcessing(Vertex[] graph)

Initializes processing. Will be called in method deepSearchFirst(classycle.graph.Vertex[]).

processBefore

protected abstract void processBefore(Vertex vertex)

Processes the specified vertex before its outgoing arcs are processed.

Parameters:

vertex - Vertex to be processed.

processArc

protected abstract void processArc(Vertex tail,
              Vertex head)

Processes the arc specified by tail and head vertices.

Parameters:

tail - Tail vertex of the arc.

head - Head vertex of the arc.

processAfter

protected abstract void processAfter(Vertex vertex)

Processes the specified vertex after its arcs have been processed.

Parameters:

vertex - Vertex to be processed.

finishProcessing

protected abstract void finishProcessing(Vertex[] graph)

Finishes processing. Will be called in method deepSearchFirst(classycle.graph.Vertex[]).