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: import java.util.Arrays;
028: import java.util.Comparator;
029:
030: /**
031: * Calculates for each vertex the longest walk. This processor assumes
032: * that the graph has no cycles.
033: *
034: * @author Franz-Josef Elmer
035: */
036: public class LongestWalkProcessor extends GraphProcessor {
037: /** Does nothing. */
038: protected void initializeProcessing(Vertex[] graph) {
039: }
040:
041: /**
042: * Resets the specified vertex.
043: * @throws IllegalArgumentException if <tt>vertex</tt> is not an instance
044: * of {@link StrongComponent}.
045: */
046: protected void processBefore(Vertex vertex) {
047: StrongComponent component = castAsStrongComponent(vertex);
048: component.setActive(true);
049: component.setLongestWalk(0);
050: }
051:
052: /**
053: * Processes arc from <tt>tail</tt> to <tt>head</tt>.
054: * Calculates the longest walk of <tt>tail</tt>.
055: * @throws IllegalArgumentException if both vertices are not instances
056: * of {@link StrongComponent} or if <tt>head</tt> is visited and
057: * active which indicates a cycle in the graph.
058: */
059: protected void processArc(Vertex tail, Vertex head) {
060: StrongComponent t = castAsStrongComponent(tail);
061: StrongComponent h = castAsStrongComponent(head);
062: if (!h.isVisited()) {
063: process(h);
064: } else if (h.isActive()) {
065: // Oops! should never be happen if the graph has been created
066: // with StrongComponentProcessor
067: throw new IllegalArgumentException(h
068: + " is not a strong component.");
069: }
070: t.setLongestWalk(Math.max(t.getLongestWalk(), 1 + h
071: .getLongestWalk()));
072: }
073:
074: /**
075: * Deactivate the specified vertex.
076: * @throws IllegalArgumentException if <tt>vertex</tt> is not an instance
077: * of {@link StrongComponent}.
078: */
079: protected void processAfter(Vertex vertex) {
080: castAsStrongComponent(vertex).setActive(false);
081: }
082:
083: /**
084: * Finishes processing by sorting the result in accordance with the
085: * walk length.
086: */
087: protected void finishProcessing(Vertex[] graph) {
088: Arrays.sort(graph, new Comparator() {
089: public int compare(Object obj1, Object obj2) {
090: return ((StrongComponent) obj1).getLongestWalk()
091: - ((StrongComponent) obj2).getLongestWalk();
092: }
093: });
094: }
095:
096: /**
097: * Casts the specified vertex as a {@link StrongComponent}.
098: * @throws IllegalArgumentException if <tt>vertex</tt> is not an instance
099: * of {@link StrongComponent}.
100: */
101: private StrongComponent castAsStrongComponent(Vertex vertex) {
102: if (vertex instanceof StrongComponent) {
103: return (StrongComponent) vertex;
104: } else {
105: throw new IllegalArgumentException(vertex
106: + " is not an instance of StrongComponent");
107: }
108: }
109: } //class
|