Package classycle.graph

Class 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 Description
      GraphProcessor()  

    • Method Summary

      All Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method 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.

      • 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.