KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > classycle > graph > LongestWalkProcessor


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 import java.util.Arrays JavaDoc;
28 import java.util.Comparator JavaDoc;
29
30 /**
31  * Calculates for each vertex the longest walk. This processor assumes
32  * that the graph has no cycles.
33  *
34  * @author Franz-Josef Elmer
35  */
36 public class LongestWalkProcessor extends GraphProcessor {
37   /** Does nothing. */
38   protected void initializeProcessing(Vertex[] graph) {}
39
40   /**
41    * Resets the specified vertex.
42    * @throws IllegalArgumentException if <tt>vertex</tt> is not an instance
43    * of {@link StrongComponent}.
44    */
45   protected void processBefore(Vertex vertex) {
46     StrongComponent component = castAsStrongComponent(vertex);
47     component.setActive(true);
48     component.setLongestWalk(0);
49   }
50
51   /**
52    * Processes arc from <tt>tail</tt> to <tt>head</tt>.
53    * Calculates the longest walk of <tt>tail</tt>.
54    * @throws IllegalArgumentException if both vertices are not instances
55    * of {@link StrongComponent} or if <tt>head</tt> is visited and
56    * active which indicates a cycle in the graph.
57    */
58   protected void processArc(Vertex tail, Vertex head) {
59     StrongComponent t = castAsStrongComponent(tail);
60     StrongComponent h = castAsStrongComponent(head);
61     if (!h.isVisited()) {
62       process(h);
63     } else if (h.isActive()) {
64       // Oops! should never be happen if the graph has been created
65 // with StrongComponentProcessor
66 throw new IllegalArgumentException JavaDoc(h + " is not a strong component.");
67     }
68     t.setLongestWalk(Math.max(t.getLongestWalk(), 1 + h.getLongestWalk()));
69   }
70
71   /**
72    * Deactivate the specified vertex.
73    * @throws IllegalArgumentException if <tt>vertex</tt> is not an instance
74    * of {@link StrongComponent}.
75    */
76   protected void processAfter(Vertex vertex) {
77     castAsStrongComponent(vertex).setActive(false);
78   }
79
80   /**
81    * Finishes processing by sorting the result in accordance with the
82    * walk length.
83    */
84   protected void finishProcessing(Vertex[] graph) {
85     Arrays.sort(graph, new Comparator JavaDoc() {
86                           public int compare(Object JavaDoc obj1, Object JavaDoc obj2) {
87                             return ((StrongComponent) obj1).getLongestWalk()
88                                    - ((StrongComponent) obj2).getLongestWalk();
89                           }
90                         });
91   }
92
93   /**
94    * Casts the specified vertex as a {@link StrongComponent}.
95    * @throws IllegalArgumentException if <tt>vertex</tt> is not an instance
96    * of {@link StrongComponent}.
97    */
98   private StrongComponent castAsStrongComponent(Vertex vertex) {
99     if (vertex instanceof StrongComponent) {
100       return (StrongComponent) vertex;
101     } else {
102       throw new IllegalArgumentException JavaDoc(
103         vertex + " is not an instance of StrongComponent");
104     }
105   }
106 } //class
Popular Tags