commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jvan...@apache.org
Subject cvs commit: jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/visitor BFSVisitor.java DFSVisitor.java DefaultVisitor.java PrintVisitor.java SCCVisitor.java Visitor.java
Date Thu, 29 Nov 2001 14:17:34 GMT
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 apache@apache.org.
   *
   * 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 apache@apache.org.
   *
   * 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 apache@apache.org.
   *
   * 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 apache@apache.org.
   *
   * 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 apache@apache.org.
   *
   * 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 apache@apache.org.
   *
   * 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:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message