Package classycle.graph

Class GraphProcessor

java.lang.Object
classycle.graph.GraphProcessor
Direct Known Subclasses:
LongestWalkProcessor, PackageProcessor, StrongComponentProcessor
public abstract class GraphProcessor extends 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 Details

    • GraphProcessor

      public GraphProcessor()

  • Method Details

    • 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[]).