KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > classycle > graph > GraphProcessor


1 /*
2  * Copyright (c) 2003-2006, Franz-Josef Elmer, All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are met:
6  *
7  * - Redistributions of source code must retain the above copyright notice,
8  * this list of conditions and the following disclaimer.
9  * - Redistributions in binary form must reproduce the above copyright notice,
10  * this list of conditions and the following disclaimer in the documentation
11  * and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
14  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
15  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
20  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
21  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
22  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
23  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25 package classycle.graph;
26
27 /**
28  * Abstract class for all algorithms based on deep search first.
29  * This class is designed in accordance with the Template Method pattern.
30  * The basic algorithm (implemented in the method
31  * {@link #process}) reads:
32  * <pre>
33  * vertex.visit();
34  * processBefore(vertex);
35  * for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i &lt; n; i++) {
36  * processArc(vertex, vertex.getHeadVertex(i));
37  * }
38  * processAfter(vertex);
39  * </pre>
40  * The methods {@link #initializeProcessing initializeProcessing()},
41  * {@link #processBefore processBefore()},
42  * {@link #processArc processArc()}, and
43  * {@link #processAfter processAfter()} have to be implemented
44  * by concrete classes.
45  * <p>
46  * The class will be used by creating an instance and invoking
47  * {@link #deepSearchFirst deepSearchFirst()} one or several times.
48  * Either the graph will be
49  * modified or some result objects are created which can be obtained
50  * by special methods defined in concrete subclasses. Note, that
51  * a <tt>GraphProcessor</tt> is not thread-safe.
52  *
53  * @author Franz-Josef Elmer
54  */
55 public abstract class GraphProcessor {
56   /**
57    * Performs a deep search first of the specified graph.
58    * First, processing will be initialized and all vertices of the graph
59    * will be reset. Then for all unvisited vertices the
60    * method <tt>process(Vertex)</tt> will be invoked. At last,
61    * processing will be finished.
62    * @param graph A directed graph.
63    */
64   public void deepSearchFirst(Vertex[] graph) {
65     initializeProcessing(graph);
66     for (int i = 0; i < graph.length; i++) {
67       graph[i].reset();
68     }
69
70     for (int i = 0; i < graph.length; i++) {
71       if (!graph[i].isVisited()) {
72         process(graph[i]);
73       }
74     }
75     finishProcessing(graph);
76   }
77
78   /** Processes the specified vertex. */
79   protected void process(Vertex vertex) {
80     vertex.visit();
81     processBefore(vertex);
82     for (int i = 0, n = vertex.getNumberOfOutgoingArcs(); i < n; i++) {
83       processArc(vertex, vertex.getHeadVertex(i));
84     }
85     processAfter(vertex);
86   }
87
88   /**
89    * Initializes processing. Will be called in method
90    * {@link #deepSearchFirst}.
91    */
92   protected abstract void initializeProcessing(Vertex[] graph);
93
94   /**
95    * Processes the specified vertex before its outgoing arcs are processed.
96    * @param vertex Vertex to be processed.
97    */
98   protected abstract void processBefore(Vertex vertex);
99
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 }
Popular Tags