001: /*
002: * Copyright (c) 2003-2008, Franz-Josef Elmer, All rights reserved.
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, are permitted provided that the following conditions are met:
006: *
007: * - Redistributions of source code must retain the above copyright notice,
008: * this list of conditions and the following disclaimer.
009: * - Redistributions in binary form must reproduce the above copyright notice,
010: * this list of conditions and the following disclaimer in the documentation
011: * and/or other materials provided with the distribution.
012: *
013: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
014: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
015: * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
016: * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
017: * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
018: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
019: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
020: * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
021: * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
022: * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
023: * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
024: */
025: package classycle.graph;
026:
027: /**
028: * Abstract class for all algorithms based on deep search first.
029: * This class is designed in accordance with the Template Method pattern.
030: * The basic algorithm (implemented in the method
031: * {@link #process}) reads:
032: * <pre>
033: * vertex.visit();
034: * processBefore(vertex);
035: * for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i < n; i++) {
036: * processArc(vertex, vertex.getHeadVertex(i));
037: * }
038: * processAfter(vertex);
039: * </pre>
040: * The methods {@link #initializeProcessing initializeProcessing()},
041: * {@link #processBefore processBefore()},
042: * {@link #processArc processArc()}, and
043: * {@link #processAfter processAfter()} have to be implemented
044: * by concrete classes.
045: * <p>
046: * The class will be used by creating an instance and invoking
047: * {@link #deepSearchFirst deepSearchFirst()} one or several times.
048: * Either the graph will be
049: * modified or some result objects are created which can be obtained
050: * by special methods defined in concrete subclasses. Note, that
051: * a <tt>GraphProcessor</tt> is not thread-safe.
052: *
053: * @author Franz-Josef Elmer
054: */
055: public abstract class GraphProcessor {
056: /**
057: * Performs a deep search first of the specified graph.
058: * First, processing will be initialized and all vertices of the graph
059: * will be reset. Then for all unvisited vertices the
060: * method <tt>process(Vertex)</tt> will be invoked. At last,
061: * processing will be finished.
062: * @param graph A directed graph.
063: */
064: public void deepSearchFirst(Vertex[] graph) {
065: initializeProcessing(graph);
066: for (int i = 0; i < graph.length; i++) {
067: graph[i].reset();
068: }
069:
070: for (int i = 0; i < graph.length; i++) {
071: if (!graph[i].isVisited()) {
072: process(graph[i]);
073: }
074: }
075: finishProcessing(graph);
076: }
077:
078: /** Processes the specified vertex. */
079: protected void process(Vertex vertex) {
080: vertex.visit();
081: processBefore(vertex);
082: for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i < n; i++) {
083: processArc(vertex, vertex.getHeadVertex(i));
084: }
085: processAfter(vertex);
086: }
087:
088: /**
089: * Initializes processing. Will be called in method
090: * {@link #deepSearchFirst}.
091: */
092: protected abstract void initializeProcessing(Vertex[] graph);
093:
094: /**
095: * Processes the specified vertex before its outgoing arcs are processed.
096: * @param vertex Vertex to be processed.
097: */
098: protected abstract void processBefore(Vertex vertex);
099:
100: /**
101: * Processes the arc specified by tail and head vertices.
102: * @param tail Tail vertex of the arc.
103: * @param head Head vertex of the arc.
104: */
105: protected abstract void processArc(Vertex tail, Vertex head);
106:
107: /**
108: * Processes the specified vertex after its arcs have been processed.
109: * @param vertex Vertex to be processed.
110: */
111: protected abstract void processAfter(Vertex vertex);
112:
113: /**
114: * Finishes processing. Will be called in method
115: * {@link #deepSearchFirst}.
116: */
117: protected abstract void finishProcessing(Vertex[] graph);
118: }
|