jvanzyl 01/11/29 06:17:34
Modified: graph/src/java/org/apache/commons/graph BFS.java DFS.java
Edge.java Graph.java GraphVisualizer.java
Sequential.java TraversalOrder.java VStack.java
Vertex.java
Added: graph/src/java/org/apache/commons/graph/visitor
BFSVisitor.java DFSVisitor.java DefaultVisitor.java
PrintVisitor.java SCCVisitor.java Visitor.java
Removed: graph/src/java/org/apache/commons/graph BFSVisitor.java
DFSVisitor.java DefaultVisitor.java
PrintVisitor.java SCCVisitor.java Visitor.java
Log:
- creating a separate visitor package to organize the code a little
better.
Revision Changes Path
1.2 +2 -1
jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/BFS.java
Index: BFS.java
===================================================================
RCS file:
/home/cvs/jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/BFS.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- BFS.java 2001/11/12 16:05:17 1.1
+++ BFS.java 2001/11/29 14:17:33 1.2
@@ -55,6 +55,7 @@
*/
import java.util.Vector;
+import org.apache.commons.graph.visitor.Visitor;
/**
* Visit graph with breadth first search and compute the predecessor
@@ -62,7 +63,7 @@
* so that it performs Dijkstra's shortest-path algorithm, for
* instance, if you extend the VQueue class to a Priority Queue.
*
- * @version $Id: BFS.java,v 1.1 2001/11/12 16:05:17 jvanzyl Exp $
+ * @version $Id: BFS.java,v 1.2 2001/11/29 14:17:33 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm";>M. Dahm</A>
*/
public class BFS extends TraversalOrder {
1.2 +3 -1
jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/DFS.java
Index: DFS.java
===================================================================
RCS file:
/home/cvs/jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/DFS.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- DFS.java 2001/11/12 16:05:18 1.1
+++ DFS.java 2001/11/29 14:17:33 1.2
@@ -54,11 +54,13 @@
* <http://www.apache.org/>.
*/
+import org.apache.commons.graph.visitor.Visitor;
+
/**
* Visit graph with depth first search and mark discovery and finishing time in all
* vertices.
*
- * @version $Id: DFS.java,v 1.1 2001/11/12 16:05:18 jvanzyl Exp $
+ * @version $Id: DFS.java,v 1.2 2001/11/29 14:17:33 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm";>M. Dahm</A>
*/
public class DFS extends TraversalOrder {
1.2 +3 -1
jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/Edge.java
Index: Edge.java
===================================================================
RCS file:
/home/cvs/jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/Edge.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- Edge.java 2001/11/12 16:05:18 1.1
+++ Edge.java 2001/11/29 14:17:33 1.2
@@ -54,11 +54,13 @@
* <http://www.apache.org/>.
*/
+import org.apache.commons.graph.visitor.Visitor;
+
/**
* Describes an edge between two vertices of a graph, i.e. a relation between
* two arbitrary vertices.
*
- * @version $Id: Edge.java,v 1.1 2001/11/12 16:05:18 jvanzyl Exp $
+ * @version $Id: Edge.java,v 1.2 2001/11/29 14:17:33 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm";>M. Dahm</A>
*/
public class Edge implements Cloneable, Constants, java.io.Serializable {
1.2 +5 -1
jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/Graph.java
Index: Graph.java
===================================================================
RCS file:
/home/cvs/jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/Graph.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- Graph.java 2001/11/12 16:05:19 1.1
+++ Graph.java 2001/11/29 14:17:33 1.2
@@ -58,10 +58,14 @@
import java.util.zip.*;
import java.io.*;
+import org.apache.commons.graph.visitor.Visitor;
+import org.apache.commons.graph.visitor.DefaultVisitor;
+import org.apache.commons.graph.visitor.PrintVisitor;
+
/**
* Describes a generic graph G = (V, E), i.e. a set of vertices and edges.
*
- * @version $Id: Graph.java,v 1.1 2001/11/12 16:05:19 jvanzyl Exp $
+ * @version $Id: Graph.java,v 1.2 2001/11/29 14:17:33 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm";>M. Dahm</A>
*/
public class Graph implements Cloneable, Constants, Serializable {
1.2 +3 -1
jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/GraphVisualizer.java
Index: GraphVisualizer.java
===================================================================
RCS file:
/home/cvs/jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/GraphVisualizer.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- GraphVisualizer.java 2001/11/12 16:05:19 1.1
+++ GraphVisualizer.java 2001/11/29 14:17:33 1.2
@@ -56,6 +56,8 @@
import java.io.*;
import java.util.StringTokenizer;
+import org.apache.commons.graph.visitor.Visitor;
+
/**
* Abstract super class for drivers that visualize graphs
* in different graph formats such as
@@ -67,7 +69,7 @@
* By default graphs are dumped in the native Java format, i.e. by using the
* Serialization feature.
*
- * @version $Id: GraphVisualizer.java,v 1.1 2001/11/12 16:05:19 jvanzyl Exp $
+ * @version $Id: GraphVisualizer.java,v 1.2 2001/11/29 14:17:33 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm";>M. Dahm</A>
* @see DaVinciVisualizer
* @see GMLVisualizer
1.2 +3 -1
jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/Sequential.java
Index: Sequential.java
===================================================================
RCS file:
/home/cvs/jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/Sequential.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- Sequential.java 2001/11/12 16:05:20 1.1
+++ Sequential.java 2001/11/29 14:17:33 1.2
@@ -54,10 +54,12 @@
* <http://www.apache.org/>.
*/
+import org.apache.commons.graph.visitor.Visitor;
+
/**
* Visit graph in sequential order, i.e. in the order returned by
Graph.getVertices().
*
- * @version $Id: Sequential.java,v 1.1 2001/11/12 16:05:20 jvanzyl Exp $
+ * @version $Id: Sequential.java,v 1.2 2001/11/29 14:17:33 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm";>M. Dahm</A>
*/
public final class Sequential extends TraversalOrder {
1.2 +3 -1
jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/TraversalOrder.java
Index: TraversalOrder.java
===================================================================
RCS file:
/home/cvs/jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/TraversalOrder.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- TraversalOrder.java 2001/11/12 16:05:20 1.1
+++ TraversalOrder.java 2001/11/29 14:17:33 1.2
@@ -54,6 +54,8 @@
* <http://www.apache.org/>.
*/
+import org.apache.commons.graph.visitor.Visitor;
+
/**
* Class takes a visitor "piggy-backed" and applies it to all nodes
* and edges. The traversal order implemented by children of this
@@ -61,7 +63,7 @@
*
* This relates to the "Strategy" design pattern.
*
- * @version $Id: TraversalOrder.java,v 1.1 2001/11/12 16:05:20 jvanzyl Exp $
+ * @version $Id: TraversalOrder.java,v 1.2 2001/11/29 14:17:33 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm";>M. Dahm</A>
* @see DFS
* @see BFS
1.2 +7 -7
jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/VStack.java
Index: VStack.java
===================================================================
RCS file:
/home/cvs/jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/VStack.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- VStack.java 2001/11/12 16:05:20 1.1
+++ VStack.java 2001/11/29 14:17:33 1.2
@@ -57,19 +57,19 @@
/**
* Implements a simple first-in, last-out stack of vertices of fixed size.
*
- * @version $Id: VStack.java,v 1.1 2001/11/12 16:05:20 jvanzyl Exp $
+ * @version $Id: VStack.java,v 1.2 2001/11/29 14:17:33 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm";>M. Dahm</A>
*/
-final class VStack {
+public final class VStack {
private Vertex[] vertices;
private int top;
- VStack(int s) {
+ public VStack(int s) {
vertices = new Vertex[s];
}
- final void push(Vertex v) { vertices[top++] = v; }
- final Vertex pop() { return vertices[--top]; }
- final Vertex top() { return vertices[top - 1]; }
- final boolean empty() { return top <= 0; }
+ public final void push(Vertex v) { vertices[top++] = v; }
+ public final Vertex pop() { return vertices[--top]; }
+ public final Vertex top() { return vertices[top - 1]; }
+ public final boolean empty() { return top <= 0; }
}
1.2 +3 -1
jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/Vertex.java
Index: Vertex.java
===================================================================
RCS file:
/home/cvs/jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/Vertex.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- Vertex.java 2001/11/12 16:05:20 1.1
+++ Vertex.java 2001/11/29 14:17:33 1.2
@@ -54,10 +54,12 @@
* <http://www.apache.org/>.
*/
+import org.apache.commons.graph.visitor.Visitor;
+
/**
* Describes a vertex of a graph.
*
- * @version $Id: Vertex.java,v 1.1 2001/11/12 16:05:20 jvanzyl Exp $
+ * @version $Id: Vertex.java,v 1.2 2001/11/29 14:17:33 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm";>M. Dahm</A>
*/
public class Vertex implements Cloneable, Constants, java.io.Serializable {
1.1
jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/visitor/BFSVisitor.java
Index: BFSVisitor.java
===================================================================
package org.apache.commons.graph.visitor;
/* ====================================================================
* The Apache Software License, Version 1.1
*
* Copyright (c) 2001 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Apache" and "Apache Software Foundation" and
* "Apache BCEL" must not be used to endorse or promote products
* derived from this software without prior written permission. For
* written permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache",
* "Apache BCEL", nor may "Apache" appear in their name, without
* prior written permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
import org.apache.commons.graph.BFS;
import org.apache.commons.graph.Constants;
import org.apache.commons.graph.Edge;
import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.VStack;
/**
* Visit graph with BFS and compute predecessors during traversal as
* well as the "distance" to the source node (number of edges in between).
*
* @version $Id: BFSVisitor.java,v 1.1 2001/11/29 14:17:34 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm";>M. Dahm</A>
* @see BFS
*/
public class BFSVisitor extends DefaultVisitor implements Constants {
private VStack stack; // Stack to remember predecessors
public BFSVisitor() {}
public void discoverGraph(Graph g) {
int size = g.getNoVertices();
Vertex[] vertices = g.getVertexArray();
for(int i=0; i < size; i++) {
vertices[i].setDistance(INFINITE);
vertices[i].setPredecessor(null);
}
stack = new VStack(size);
}
public void discoverVertex(Vertex v) {
if(stack.empty()) { // At start vertex, v == start
v.setPredecessor(null);
v.setDistance(0);
}
else {
Vertex pred = stack.top();
v.setPredecessor(pred);
v.setDistance(pred.getDistance() + 1);
}
stack.push(v);
}
public void finishVertex(Vertex v) {
stack.pop();
}
public void visit(Graph g, Vertex start) {
new BFS(this).start(g, start);
}
}
1.1
jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/visitor/DFSVisitor.java
Index: DFSVisitor.java
===================================================================
package org.apache.commons.graph.visitor;
/* ====================================================================
* The Apache Software License, Version 1.1
*
* Copyright (c) 2001 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Apache" and "Apache Software Foundation" and
* "Apache BCEL" must not be used to endorse or promote products
* derived from this software without prior written permission. For
* written permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache",
* "Apache BCEL", nor may "Apache" appear in their name, without
* prior written permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
import org.apache.commons.graph.Edge;
import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.VStack;
/**
* Visit graph with DFS and compute predecessors during traversal as
* well as discovery and finishing time of all vertices. Instances of
* this class (and of course its descendants) may be passed to a DFS
* object.
*
* @version $Id: DFSVisitor.java,v 1.1 2001/11/29 14:17:34 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm";>M. Dahm</A>
* @see DFS
*/
public class DFSVisitor extends DefaultVisitor {
private int time; // Global time
private VStack stack; // Stack to remember predecessors
public DFSVisitor() {}
public void discoverGraph(Graph g) {
int size = g.getNoVertices();
Vertex[] vertices = g.getVertexArray();
for(int i=0; i < size; i++)
vertices[i].setPredecessor(null);
time = 0; // Reset timer
stack = new VStack(size);
}
public void discoverVertex(Vertex v) {
if(stack.empty()) // First node
v.setPredecessor(null);
else
v.setPredecessor(stack.top());
stack.push(v);
v.setDiscoveryTime(time++);
}
public void finishVertex(Vertex v) {
v.setFinishingTime(time++);
stack.pop();
}
}
1.1
jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/visitor/DefaultVisitor.java
Index: DefaultVisitor.java
===================================================================
package org.apache.commons.graph.visitor;
/* ====================================================================
* The Apache Software License, Version 1.1
*
* Copyright (c) 2001 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Apache" and "Apache Software Foundation" and
* "Apache BCEL" must not be used to endorse or promote products
* derived from this software without prior written permission. For
* written permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache",
* "Apache BCEL", nor may "Apache" appear in their name, without
* prior written permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
import org.apache.commons.graph.DFS;
import org.apache.commons.graph.Edge;
import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;
/**
* Empty Visitor, i.e. all visit methods do nothing.
*
* @version $Id: DefaultVisitor.java,v 1.1 2001/11/29 14:17:34 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm";>M. Dahm</A>
*/
public class DefaultVisitor implements Visitor {
protected DFS dfs;
public DefaultVisitor() {}
public void discoverGraph(Graph g) {}
public void finishGraph(Graph g) {}
public void discoverVertex(Vertex v) {}
public void finishVertex(Vertex v) { }
public void discoverEdge(Edge e) {}
public void finishEdge(Edge e) {}
public void visit(Graph g, Vertex start) {
dfs = new DFS(this);
dfs.start(g, start);
}
}
1.1
jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/visitor/PrintVisitor.java
Index: PrintVisitor.java
===================================================================
package org.apache.commons.graph.visitor;
/* ====================================================================
* The Apache Software License, Version 1.1
*
* Copyright (c) 2001 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Apache" and "Apache Software Foundation" and
* "Apache BCEL" must not be used to endorse or promote products
* derived from this software without prior written permission. For
* written permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache",
* "Apache BCEL", nor may "Apache" appear in their name, without
* prior written permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
import java.io.PrintWriter;
import org.apache.commons.graph.DFS;
import org.apache.commons.graph.Edge;
import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;
/**
* Visit graph with depth first search and simply prints the current
* vertices and edges as they are discovered. May be used with DFS, BFS,
* Sequential or any other visitor. Uses DFS by default.
*
* @version $Id: PrintVisitor.java,v 1.1 2001/11/29 14:17:34 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm";>M. Dahm</A>
*/
public class PrintVisitor implements Visitor {
private PrintWriter out;
private int verbose;
/**
* Simply print vertex and edge contents, when visiting them.
*
* @param o stream to print to
* @param v toggle verbosity of output
* @see Constants
*/
public PrintVisitor(PrintWriter o, int v) {
out = o;
verbose = v;
}
public void discoverGraph(Graph g) {}
public void finishGraph(Graph g) {}
public void finishVertex(Vertex v) {}
public void finishEdge(Edge e) {}
public void discoverVertex(Vertex v) { out.println(v.toString(verbose)); }
public void discoverEdge(Edge e) { out.println(e.toString(verbose)); }
public void visit(Graph g, Vertex start) {
new DFS(this).start(g, start);
}
}
1.1
jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/visitor/SCCVisitor.java
Index: SCCVisitor.java
===================================================================
package org.apache.commons.graph.visitor;
/* ====================================================================
* The Apache Software License, Version 1.1
*
* Copyright (c) 2001 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Apache" and "Apache Software Foundation" and
* "Apache BCEL" must not be used to endorse or promote products
* derived from this software without prior written permission. For
* written permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache",
* "Apache BCEL", nor may "Apache" appear in their name, without
* prior written permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
import java.util.Vector;
import org.apache.commons.graph.DFS;
import org.apache.commons.graph.Edge;
import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;
import org.apache.commons.graph.VStack;
/**
* Visit graph computing its "Strongly Connected Components" (SCC).
*
* @version $Id: SCCVisitor.java,v 1.1 2001/11/29 14:17:34 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm";>M. Dahm</A>
* @see DFS
*/
public class SCCVisitor implements Visitor {
private int time; // Global time
private VStack stack; // Stack to remember members of a SCC
private Vector sccs; // Forest of SCCs
private Graph graph;
private Graph[] graphs;
private int size;
public SCCVisitor() {}
public void discoverGraph(Graph g) {
graph = g;
size = g.getNoVertices();
Vertex[] vertices = g.getVertexArray();
for(int i=0; i < size; i++) {
vertices[i].setDiscoveryTime(0);
/* Should rather be setMyMinTime(), "abused" to remember local minimum
*/
vertices[i].setFinishingTime(size * 2); // Invalidate
}
time = 0; // Reset timer
stack = new VStack(size);
sccs = new Vector();
}
public void discoverVertex(Vertex v) {
int min = time++; // Clock tick
v.setDiscoveryTime(min); // Remember time of discovery
v.setFinishingTime(min); // Remember local minimum
stack.push(v); // Push current node on stack
}
public void discoverEdge(Edge e) {}
public void finishEdge(Edge e) {
Vertex src = graph.getSource(e);
Vertex target = graph.getTarget(e);
int m = target.getFinishingTime();
/* After recursion, test if the (white) vertex just visited has now a smaller
* minium than the local one, i.e. if target.min < src.min && !target.isBlack().
*/
if((m < src.getFinishingTime()) && (target.getDiscoveryTime() < size + 1))
src.setFinishingTime(m);
}
public void finishVertex(Vertex v) {
/* If the local minimum hasn't changed, i.e. if no vertices with smaller minimums
* have been reached, this must be the root vertex of a SCC.
*/
if(v.getFinishingTime() == v.getDiscoveryTime()) { // Root of SCC?
Graph scc = new Graph(); // Gather nodes in subgraph
Vertex p;
do { // Pop all nodes belonging to this SCC subgraph
p = stack.pop();
scc.addVertex(p); // May have no edges, so put it first in there
p.setDiscoveryTime(size * 2); // Invalidate, i.e. mark vertex as black
} while(p != v);
Vertex[] vertices = scc.getVertexArray();
for(int j=0; j < vertices.length; j++) {
p = vertices[j];
Edge[] edges = graph.getEdgeArray(p);
for(int i=0; i < edges.length; i++) { // Build up subgraph
Edge e = edges[i];
Vertex src = graph.getSource(e);
Vertex target = graph.getTarget(e);
// Add only edges that are within the subgraph
if(scc.contains(src) && scc.contains(target))
scc.addEdge(src, target, e);
}
}
sccs.addElement(scc); // Add subgraph vectorto forest of subgraphs
}
}
public void finishGraph(Graph g) {
graphs = new Graph[sccs.size()];
sccs.copyInto(graphs);
}
/**
* @return all strongly connected components found during traversal
*/
public final Graph[] getSCCs() { return graphs; }
/**
* Visit graph with DFS and find all its strongly connected components
* which may be obtained with getSCCs().
*
* @param g graph to traverse
* @param start where to start traversal
*/
public void visit(Graph g, Vertex start) {
new DFS(this).start(g, start);
}
}
1.1
jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/visitor/Visitor.java
Index: Visitor.java
===================================================================
package org.apache.commons.graph.visitor;
/* ====================================================================
* The Apache Software License, Version 1.1
*
* Copyright (c) 2001 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. The end-user documentation included with the redistribution,
* if any, must include the following acknowledgment:
* "This product includes software developed by the
* Apache Software Foundation (http://www.apache.org/)."
* Alternately, this acknowledgment may appear in the software itself,
* if and wherever such third-party acknowledgments normally appear.
*
* 4. The names "Apache" and "Apache Software Foundation" and
* "Apache BCEL" must not be used to endorse or promote products
* derived from this software without prior written permission. For
* written permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called "Apache",
* "Apache BCEL", nor may "Apache" appear in their name, without
* prior written permission of the Apache Software Foundation.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
* ====================================================================
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* <http://www.apache.org/>.
*/
import org.apache.commons.graph.Edge;
import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;
/**
* Interface for visitor patterns.
*
* @version $Id: Visitor.java,v 1.1 2001/11/29 14:17:34 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm";>M. Dahm</A>
*/
public interface Visitor {
public void discoverGraph(Graph g); // may be also used as "visitGraph"
public void finishGraph(Graph g);
public void discoverVertex(Vertex v); // same as above
public void finishVertex(Vertex v);
public void discoverEdge(Edge e); // same as above
public void finishEdge(Edge e);
public void visit(Graph g, Vertex v); // Start visiting graph g beginning at start
}
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
