commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From d..@apache.org
Subject cvs commit: jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/util Label.java PathImpl.java VertexPair.java
Date Wed, 08 May 2002 17:34:09 GMT
ddp         02/05/08 10:34:09

  Added:       graph2/src/java/org/apache/commons/graph/algorithm/path
                        AllPairsShortestPath.java AllPaths.java
                        PathIterator.java PathListener.java
               graph2/src/java/org/apache/commons/graph/algorithm/search
                        CostSearch.java DFS.java Visitor.java
               graph2/src/java/org/apache/commons/graph/algorithm/spanning
                        MinimumSpanningForest.java
               graph2/src/java/org/apache/commons/graph/algorithm/util
                        Label.java PathImpl.java VertexPair.java
  Log:
  Moving changes from local disk into CVS.
  
  Revision  Changes    Path
  1.1                  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/path/AllPairsShortestPath.java
  
  Index: AllPairsShortestPath.java
  ===================================================================
  package org.apache.commons.graph.algorithm.path;
  
  /* ====================================================================
   * 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
   *    "Commons" 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",
   *    "Commons", 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/>.
   */
  
  /**
   * AllPairs solves the All Points Shortest Path problem for a DirectedGraph. (If
   * it is weighted, it will do shortest path by weight. Otherwise shortest path
   * by jumps.) Uses Floyd's Algorithm.
   */
  
  import java.util.Set;
  import java.util.Map;
  import java.util.List;
  import java.util.HashMap;
  import java.util.Iterator;
  import java.util.ArrayList;
  import java.util.AbstractList;
  
  import org.apache.commons.graph.*;
  import org.apache.commons.graph.exception.*;
  
  /**
   * Description of the Class
   */
  public class AllPairsShortestPath
  {
      private int pred[][];
      private double cost[][];
      private Vertex vArray[];
      private DirectedGraph graph;
      private Map vertexIndex = new HashMap();// VERTEX X INTEGER
  
      /**
       * Description of the Class
       */
      public class EdgeList
           extends AbstractList
      {
          private DirectedGraph graph;
          private List vertices;
  
          /**
           * Constructor for the EdgeList object
           *
           * @param graph
           * @param vertices
           */
          public EdgeList(DirectedGraph graph,
                          List vertices)
          {
              this.graph = graph;
              this.vertices = vertices;
          }
  
          /**
           * Description of the Method
           */
          public int size()
          {
              return vertices.size() - 1;
          }
  
          /**
           * Description of the Method
           */
          public Object get(int index)
          {
              Edge RC = null;
  
              Vertex source = (Vertex) vertices.get(index);
              Vertex target = (Vertex) vertices.get(index + 1);
  
              Set outboundSet = graph.getOutbound(source);
              if (outboundSet == null)
              {
                  return null;
              }
  
              Iterator outbound = outboundSet.iterator();
              while (outbound.hasNext())
              {
                  RC = (Edge) outbound.next();
                  if (graph.getTarget(RC) == target)
                  {
                      break;
                  }
              }
  
              if (graph.getTarget(RC) != target)
              {
                  return null;
              }
  
              return RC;
          }
      }
  
      /**
       * Description of the Class
       */
      public class WPath
           implements WeightedPath
      {
          private Vertex start;
          private Vertex finish;
          private List vertexList = new ArrayList();
          private DirectedGraph graph;
          private double cost;
  
          /**
           * Constructor for the WPath object
           *
           * @param graph
           * @param vArray
           * @param pred
           * @param start
           * @param finish
           * @param cost
           * @exception GraphException
           */
          public WPath(DirectedGraph graph,
                       Vertex vArray[], int pred[][],
                       int start, int finish, double cost)
              throws GraphException
          {
              this.start = vArray[start];
              this.finish = vArray[finish];
              this.cost = cost;
              this.graph = graph;
  
              vertexList.addAll(segment(vArray, pred,
                  start, finish));
              vertexList.add(vArray[finish]);
          }
  
          /**
           * Returns a List of Vectors in order. Includes the start, but not the
           * finish.
           */
          private List segment(Vertex vArray[], int pred[][],
                               int start, int finish)
              throws GraphException
          {
              int mid = pred[start][finish];
              if (mid == -1)
              {
                  throw new NoPathException("No SubPath Available: " +
                      vArray[start] + " -> " +
                      vArray[finish]);
              }
              List RC = new ArrayList();
  
              if (start == finish)
              {
                  return RC;
              }
  
              if (start == mid)
              {
                  RC.add(vArray[start]);
  
              }
              else
              {
                  RC.addAll(segment(vArray, pred,
                      start, mid));
                  RC.add(vArray[mid]);
              }
  
              if (mid == pred[mid][finish])
              {
              }
              else
              {
                  RC.addAll(segment(vArray, pred,
                      mid, finish));
              }
              return RC;
          }
  
          /**
           * Gets the weight attribute of the WPath object
           */
          public double getWeight()
          {
              return cost;
          }
  
          /**
           * Gets the vertices attribute of the WPath object
           */
          public List getVertices()
          {
              return vertexList;
          }
  
          /**
           * Gets the edges attribute of the WPath object
           */
          public List getEdges()
          {
              return new EdgeList(graph, vertexList);
          }
  
          /**
           * Gets the start attribute of the WPath object
           */
          public Vertex getStart()
          {
              return start;
          }
  
          /**
           * Gets the end attribute of the WPath object
           */
          public Vertex getEnd()
          {
              return finish;
          }
  
  	public int size() {
  	    return vertexList.size();
  	}
      }
  
      /**
       * Constructor for the AllPairsShortestPath object
       *
       * @param graph
       * @exception NegativeCycleException
       */
      public AllPairsShortestPath(DirectedGraph graph)
          throws NegativeCycleException
      {
          update(graph);
      }
  
  
      /**
       * Description of the Method
       */
      private void initIndex(Vertex vArray[])
      {
          for (int i = 0; i < vArray.length; i++)
          {
              vertexIndex.put(vArray[i], new Integer(i));
          }
      }
  
      /**
       * Description of the Method
       */
      public void update(DirectedGraph graph)
      {
          this.graph = graph;
  
          Set vertexSet = graph.getVertices();
          vArray = (Vertex[]) vertexSet.toArray(new Vertex[vertexSet.size()]);
  
          initIndex(vArray);
  
          pred = new int[vArray.length][vArray.length];
          cost = new double[vArray.length][vArray.length];
  
          for (int i = 0; i < vArray.length; i++)
          {
              for (int j = 0; j < vArray.length; j++)
              {
                  pred[i][j] = -1;
                  cost[i][j] = Double.POSITIVE_INFINITY;
              }
  
              // First round values need to be in the matrix.
              Iterator edgeSet = graph.getOutbound(vArray[i]).iterator();
              while (edgeSet.hasNext())
              {
                  Edge e = (Edge) edgeSet.next();
                  int j = index(graph.getTarget(e));
                  pred[i][j] = i;
                  if (graph instanceof WeightedGraph)
                  {
                      cost[i][j] = ((WeightedGraph) graph).getWeight(e);
                  }
                  else
                  {
                      cost[i][j] = 1.0;
                  }
              }
  
              // Cost from any node to itself is 0.0
              cost[i][i] = 0.0;
              pred[i][i] = i;
          }
  
          compute(graph, vArray);
  
      }
  
      /**
       * Description of the Method
       */
      private int index(Vertex v)
      {
          return ((Integer) vertexIndex.get(v)).intValue();
      }
  
      /**
       * Description of the Method
       */
      private void compute(DirectedGraph graph, Vertex vArray[])
          throws NegativeCycleException
      {
          for (int k = 0; k < vArray.length; k++)
          {// Mid Point
              for (int i = 0; i < vArray.length; i++)
              {// Source
                  for (int j = 0; j < vArray.length; j++)
                  {// Target
                      if (cost[i][k] + cost[k][j] < cost[i][j])
                      {
                          if (i == j)
                          {
                              throw new NegativeCycleException();
                          }
  
                          // It is cheaper to go through K.
                          cost[i][j] = cost[i][k] + cost[k][j];
                          pred[i][j] = k;
                      }
                  }
              }
          }
      }
  
      /**
       * Gets the shortestPath attribute of the AllPairsShortestPath object
       */
      public WeightedPath getShortestPath(Vertex start, Vertex end)
          throws GraphException
      {
          return new WPath(graph, vArray, pred,
              index(start), index(end),
              cost[index(start)][index(end)]);
      }
  
      /**
       * Determines if a path exists or not.
       */
      public boolean hasPath( Vertex start, Vertex end ) 
      {
  	return cost[index(start)][index(end)] < Double.POSITIVE_INFINITY;
      }
  }
  
  
  
  1.1                  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/path/AllPaths.java
  
  Index: AllPaths.java
  ===================================================================
  package org.apache.commons.graph.algorithm.path;
  
  /* ====================================================================
   * 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 i
   *    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
   *    "Commons" 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",
   *    "Commons", 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/>.
   */
  
  /**
   * AllPaths finds for each pair of vertices, {i, j} the set of
   * all potential paths between them.  (Unrolling loops by a set
   * amount.
   */
  
  import java.util.Map;
  import java.util.Set;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.Iterator;
  
  import org.apache.commons.graph.*;
  import org.apache.commons.graph.algorithm.util.*;
  
  public class AllPaths
  {
      private Map allPaths = new HashMap(); // VERTEX PAIR X SET( PATHS )
  
      private AllPairsShortestPath apsp = null;
      private DirectedGraph graph = null;
      
      public AllPaths( DirectedGraph graph ) {
  	this.graph = graph;
  	try {
  	    apsp = new AllPairsShortestPath( graph );
  	} catch (Exception ex) {
  	    ex.printStackTrace();
  	}
      }
      
      public Iterator findPaths( final Vertex i, 
  			       final Vertex j ) {
  	final PathIterator RC = new PathIterator();
  
  	Runnable run = new Runnable() {
  		public void run() {
  		    findPaths( RC, i, j, Integer.MAX_VALUE );
  		}
  	    };
  	Thread thread = new Thread( run );
  
  	RC.setThread( thread );
  
  	thread.start();
  
  	return RC;
      }
  
      public void findPaths( PathListener listener, 
  			   Vertex i, Vertex j,
  			   int maxLength ) {
  	Set workingSet = new HashSet();
  	workingSet.add( new PathImpl( i ));
  	
  	for (int k = 0; k < maxLength; k++) {
  	    Iterator workingPaths = workingSet.iterator();
  	    if (!workingPaths.hasNext()) break;
  
  	    Set newWorkingSet = new HashSet();
  	    
  	    while (workingPaths.hasNext()) {
  		PathImpl workingPath = (PathImpl) workingPaths.next();
  
  		Iterator outbound = 
  		    graph.getOutbound(workingPath.getEnd()).iterator();
  
  		while (outbound.hasNext()) {
  		    Edge obEdge = (Edge) outbound.next();
  		    if (apsp.hasPath( graph.getTarget( obEdge ), j)) {
  			
  			PathImpl path = 
  			    workingPath.append(graph.getTarget(obEdge),
  					       obEdge );
  			
  			
  			newWorkingSet.add( path );
  			
  			if (path.getEnd() == j) {
  			    listener.notifyPath( path );
  			}
  		    }
  		}
  	    }
  
  	    workingSet = newWorkingSet;
  	}
      }
  
      /**
       * getAllPaths will return the set of all possible ways of moving
       * from i to j using the directed graph AllPaths was initialized
       * with.
       *
       * @deprecated Use findPaths instead.  Doesn't work, but code
       * may be useful in the near future.
       */
      public Set getAllPaths( Vertex i, Vertex j ) {
  	Set RC = new HashSet();
  	VertexPair key = new VertexPair( i, j );
  
  	// If we have already started this, return what we
  	// were doing. (May still be in progress.)
  	// 
  	// If we haven't started, go ahead and start. . .
  	if (allPaths.containsKey( key )) {
  	    return (Set) allPaths.get( key );
  	} else {
  	    allPaths.put( key, RC );
  	}
  
  	Iterator outbounds = graph.getOutbound(i).iterator();
  
  	while (outbounds.hasNext()) {
  	    Edge outbound = (Edge) outbounds.next();
  	    if (graph.getTarget( outbound ) == j) {
  		RC.add( new PathImpl( i, j, outbound ));
  	    }
  	}
  
  	Iterator ks = graph.getVertices().iterator();
  	while (ks.hasNext()) {
  	    Vertex k = (Vertex) ks.next();
  	    if (k != i && k != j) {
  		appendPaths( RC, 
  			     getAllPaths( i, k ), 
  			     getAllPaths( k, j ));
  	    }
  	}
  
  	allPaths.put( key, RC );
  	return RC;
      }
  
      public void appendPaths( Set RC, Set iks, Set kjs ) {
  	Iterator ikPaths = iks.iterator();
  	while (ikPaths.hasNext()) {
  	    PathImpl ik = (PathImpl) ikPaths.next();
  
  	    Iterator kjPaths = kjs.iterator();
  	    while (kjPaths.hasNext()) {
  		PathImpl kj = (PathImpl) kjPaths.next();
  		RC.add( ik.append( kj ));
  	    }
  	}
      }
  }
  
  
  
  
  
  
  1.1                  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/path/PathIterator.java
  
  Index: PathIterator.java
  ===================================================================
  package org.apache.commons.graph.algorithm.path;
  
  import java.util.List;
  import java.util.Iterator;
  import java.util.LinkedList;
  import java.util.NoSuchElementException;
  
  import org.apache.commons.graph.Path;
  
  public class PathIterator
      implements PathListener,
  	       Iterator
  {
      private List queue = new LinkedList();
      private Thread thread = null;
      private int highMark = 50;
  
      /**
       * @t is the thread which is generating the paths.
       * if this thread is terminated, we assume that
       * we have recieved everything.
       */
      public PathIterator() {
      }
      
      public void setThread( Thread thread ) {
  	this.thread = thread;
      }
  
      public void remove() {
  	throw new UnsupportedOperationException();
      }
  
      public void notifyPath( Path path ) {
  	synchronized (queue) {
  	    try {
  		if (queue.size() >= highMark) {
  		    queue.wait();
  		}
  	    } catch (InterruptedException ex) {}
  
  	    queue.add( path );
  	    queue.notifyAll();
  	}
      }
  
      public boolean hasNext() { 
  	synchronized (queue) {
  	    if (queue.size() > 0) return true;
  
  	    while ((queue.size() == 0) &&
  		   (thread.isAlive())) {
  		try { 
  		    queue.wait(100);
  		} catch (InterruptedException ex) { }
  	    }
  
  	    return queue.size() > 0;
  	}
      }
  
      public Object next() {
  	synchronized (queue) {
  	    if (hasNext()) {
  		return queue.remove( 0 );
  	    } else {
  		throw new NoSuchElementException();
  	    }
  	}
      }
  }
  
  
  
  1.1                  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/path/PathListener.java
  
  Index: PathListener.java
  ===================================================================
  package org.apache.commons.graph.algorithm.path;
  
  /* ====================================================================
   * 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 i
   *    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
   *    "Commons" 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",
   *    "Commons", 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/>.
   */
  
  /**
   * PathListener
   *
   * This interface is passed into the AllPaths algorithm, and
   * is notified of all qualifing paths.
   */
  
  import org.apache.commons.graph.Path;
  
  public interface PathListener
  {
      public void notifyPath( Path path );
  }
  
  
  
  1.1                  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/search/CostSearch.java
  
  Index: CostSearch.java
  ===================================================================
  package org.apache.commons.graph.algorithm.search;
  
  /* ====================================================================
   * 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
   *    "Commons" 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",
   *    "Commons", 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/>.
   */
  
  /**
   * This is a Cost searching algorithm. It will basically follow edges/paths with
   * minimal cost first, and then go to the later costs.
   */
  
  import java.util.Set;
  import java.util.Map;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.Iterator;
  
  import org.apache.commons.graph.*;
  
  import org.apache.commons.collections.*;
  
  /**
   * Description of the Class
   */
  public class CostSearch
  {
      /**
       * Description of the Class
       */
      public class ComparableEdge
           implements Edge, Comparable
      {
          private Edge e;
          private double cost;
  
          /**
           * Constructor for the ComparableEdge object
           *
           * @param e
           * @param cost
           */
          public ComparableEdge(Edge e, double cost)
          {
              this.e = e;
              this.cost = cost;
          }
  
          /**
           * Gets the edge attribute of the ComparableEdge object
           */
          public Edge getEdge()
          {
              return e;
          }
  
          /**
           * Gets the cost attribute of the ComparableEdge object
           */
          public double getCost()
          {
              return cost;
          }
  
          /**
           * Description of the Method
           */
          public int compareTo(Object o)
          {
              ComparableVertex cv = (ComparableVertex) o;
              if (cv.cost > cost)
              {
                  return 1;
              }
              if (cv.cost == cost)
              {
                  return 0;
              }
              if (cv.cost < cost)
              {
                  return -1;
              }
              return 0;
          }
      }
  
      /**
       * Description of the Class
       */
      public class ComparableVertex
           implements Vertex, Comparable
      {
          private Vertex v;
          private double cost;
  
          /**
           * Constructor for the ComparableVertex object
           *
           * @param v
           * @param cost
           */
          public ComparableVertex(Vertex v, double cost)
          {
              this.v = v;
              this.cost = cost;
          }
  
          /**
           * Description of the Method
           */
          public int compareTo(Object o)
          {
              ComparableVertex cv = (ComparableVertex) o;
              if (cv.cost > cost)
              {
                  return 1;
              }
              if (cv.cost == cost)
              {
                  return 0;
              }
              if (cv.cost < cost)
              {
                  return -1;
              }
              return 0;
          }
  
          /**
           * Gets the vertex attribute of the ComparableVertex object
           */
          public Vertex getVertex()
          {
              return v;
          }
      }
  
      private Map colors = new HashMap();// VERTEX X COLOR
      private PriorityQueue tasks = null;
  
      private String WHITE = "white";
      private String BLACK = "black";
      private String GRAY = "gray";
  
      /**
       * Constructor for the CostSearch object
       */
      public CostSearch()
      {
          tasks = new BinaryHeap(true);
      }
  
      /**
       * Constructor for the CostSearch object
       *
       * @param isMin
       */
      public CostSearch(boolean isMin)
      {
          tasks = new BinaryHeap(isMin);
      }
  
      /**
       * Description of the Method
       */
      public void visitVertex(WeightedGraph graph,
                              Vertex vertex,
                              double cost,
                              Visitor visitor)
      {
          colors.remove(vertex);
          colors.put(vertex, GRAY);
  
          visitor.discoverVertex(vertex);
          Iterator edges = graph.getEdges(vertex).iterator();
          while (edges.hasNext())
          {
              Edge edge = (Edge) edges.next();
  
              double edgeCost = graph.getWeight(edge);
              ComparableEdge wEdge =
                  new ComparableEdge(edge, edgeCost + cost);
              tasks.insert(wEdge);
          }
  
          visitor.finishVertex(vertex);
          colors.remove(vertex);
          colors.put(vertex, BLACK);
      }
  
      /**
       * Description of the Method
       */
      public void visitEdge(WeightedGraph graph,
                            Edge e,
                            double cost,
                            Visitor visitor)
      {
          visitor.discoverEdge(e);
  
          Iterator vertices = graph.getVertices(e).iterator();
          while (vertices.hasNext())
          {
              Vertex v = (Vertex) vertices.next();
              if (colors.get(v) == WHITE)
              {
                  visitVertex(graph, v, cost, visitor);
              }
          }
  
          visitor.finishEdge(e);
      }
  
  
      /**
       * Description of the Method
       */
      public void visit(WeightedGraph graph,
                        Vertex root,
                        Visitor visitor)
      {
          Iterator vertices = graph.getVertices().iterator();
          while (vertices.hasNext())
          {
              colors.put(vertices.next(), WHITE);
          }
  
          visitor.discoverGraph(graph);
  
          visitVertex(graph, root, 0.0, visitor);
  
          while (!tasks.isEmpty())
          {
              ComparableEdge wEdge = (ComparableEdge) tasks.pop();
              visitEdge(graph, wEdge.getEdge(), wEdge.getCost(), visitor);
          }
  
          visitor.finishGraph(graph);
      }
  }
  
  
  
  
  
  1.1                  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/search/DFS.java
  
  Index: DFS.java
  ===================================================================
  package org.apache.commons.graph.algorithm.search;
  
  /* ====================================================================
   * 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
   *    "Commons" 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",
   *    "Commons", 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/>.
   */
  
  /**
   * This class does a Depth First Search. It visits all of the children nodes
   * before moving to the siblling nodes.
   */
  
  import java.util.Set;
  import java.util.Map;
  import java.util.HashSet;
  import java.util.HashMap;
  import java.util.Iterator;
  
  import org.apache.commons.graph.*;
  
  /**
   * Description of the Class
   */
  public class DFS
  {
      private Map colors = new HashMap();// VERTEX X COLOR
      /**
       * Description of the Field
       */
      public final static String WHITE = "white";
      /**
       * Description of the Field
       */
      public final static String BLACK = "black";
      /**
       * Description of the Field
       */
      public final static String GRAY = "gray";
  
      /**
       * Constructor for the DFS object
       */
      public DFS() { }
  
      /**
       * Gets the color attribute of the DFS object
       */
      public String getColor(Vertex v)
      {
          return (String) colors.get(v);
      }
  
  
      /**
       * Description of the Method
       */
      private void visitEdge(DirectedGraph graph,
                             Edge e,
                             Visitor visitor)
      {
          visitor.discoverEdge(e);
  
          Vertex v = graph.getTarget(e);
  
          if (colors.get(v) == WHITE)
          {
              visitVertex(graph, v, visitor);
          }
  
          visitor.finishEdge(e);
      }
  
      /**
       * Description of the Method
       */
      private void visitVertex(DirectedGraph graph,
                               Vertex v,
                               Visitor visitor)
      {
          colors.remove(v);
          colors.put(v, GRAY);
  
          visitor.discoverVertex(v);
  
          Iterator edges = graph.getOutbound(v).iterator();
          while (edges.hasNext())
          {
              Edge e = (Edge) edges.next();
              visitEdge(graph, e, visitor);
          }
  
          visitor.finishVertex(v);
  
          colors.remove(v);
          colors.put(v, BLACK);
      }
  
      /**
       * visit - Visits the graph
       */
      public void visit(DirectedGraph graph,
                        Vertex root,
                        Visitor visitor)
      {
          Iterator vertices = graph.getVertices().iterator();
          while (vertices.hasNext())
          {
              colors.put(vertices.next(), WHITE);
          }
  
          visitor.discoverGraph(graph);
  
          visitVertex(graph, root, visitor);
  
          visitor.finishGraph(graph);
      }
  
  }
  
  
  
  
  1.1                  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/search/Visitor.java
  
  Index: Visitor.java
  ===================================================================
  package org.apache.commons.graph.algorithm.search;
  
  /* ====================================================================
   * 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
   *    "Commons" 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",
   *    "Commons", 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.*;
  
  /**
   * Description of the Interface
   */
  public interface Visitor
  {
      /**
       * Description of the Method
       */
      public void discoverGraph(Graph graph);
  
      /**
       * Description of the Method
       */
      public void discoverVertex(Vertex vertex);
  
      /**
       * Description of the Method
       */
      public void discoverEdge(Edge edge);
  
      /**
       * Description of the Method
       */
      public void finishEdge(Edge edge);
  
      /**
       * Description of the Method
       */
      public void finishVertex(Vertex vertex);
  
      /**
       * Description of the Method
       */
      public void finishGraph(Graph graph);
  }
  
  
  
  1.1                  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/spanning/MinimumSpanningForest.java
  
  Index: MinimumSpanningForest.java
  ===================================================================
  package org.apache.commons.graph.algorithm.spanning;
  
  import org.apache.commons.graph.*;
  import org.apache.commons.graph.exception.*;
  import org.apache.commons.graph.decorator.*;
  import org.apache.commons.graph.domain.basic.*;
  import org.apache.commons.graph.algorithm.util.*;
  
  import org.apache.commons.collections.PriorityQueue;
  import org.apache.commons.collections.BinaryHeap;
  
  import java.util.Map;
  import java.util.Set;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.Comparator;
  
  public class MinimumSpanningForest
    extends UndirectedGraphImpl
    implements UndirectedGraph,
  	     WeightedGraph
  {
    private PriorityQueue queue = null;
    private Map labels = new HashMap(); // VERTEX X LABEL
    private Set chords = new HashSet(); // Edges not in MSF.
    
    private DDirectedGraph ddg = null;
  
    public class WeightedEdgeComparator
      implements Comparator
    {
      private WeightedGraph graph = null;
      public WeightedEdgeComparator( WeightedGraph graph ) {
        this.graph = graph;
      }
  
      public int compare( Object o1, Object o2 ) {
        if ((o1 instanceof Edge) && 
  	  (o2 instanceof Edge)) {
  	double val = ( graph.getWeight( (Edge) o1 ) -
  		       graph.getWeight( (Edge) o2 ));
  	if (val > 0) return 1;
  	if (val == 0) return 0;
  	if (val < 0) return -1;
        }
  
        return -1;
      }
    }
  
    public MinimumSpanningForest( WeightedGraph graph ) {
      calculateMSF( true, graph );
    }
  
    public MinimumSpanningForest( boolean isMin, WeightedGraph graph ) {
      calculateMSF( isMin, graph );
    }
  
    protected Label findLabel( Vertex v ) {
      return (Label) labels.get( v );
    }
  
    protected boolean connectsLabels( Graph graph, 
  				    Edge e ) 
    {
      Label first = null;
      Label second = null;
  
      Iterator vertices = graph.getVertices( e ).iterator();
      if (vertices.hasNext()) {
        first = findLabel( (Vertex) vertices.next() );
      } else { return false; }
  
      if (vertices.hasNext()) {
        second = findLabel( (Vertex) vertices.next() );
      } else { return false; }
  
      if (vertices.hasNext()) {
        throw new HyperGraphException("Unable to compute MSF on Hypergraph.");
      }
  
      return !first.getRoot().equals( second.getRoot() );
    }
  
    protected void addEdge( WeightedGraph graph,
  			  Edge edge ) { 
      addEdge( edge );
      chords.remove( edge );
      Iterator vertices = graph.getVertices( edge ).iterator();
      Label prime = null;
  
      if (vertices.hasNext()) {
        Vertex p = (Vertex) vertices.next();
        prime = findLabel( p );
  
        connect( edge, p );
      }
  
      while (vertices.hasNext()) {
        Vertex v = (Vertex) vertices.next();
  
        Label l = findLabel( v );
        l.setRoot( prime );
  
        connect( edge, v );
      }
  
      setWeight( edge, graph.getWeight( edge ));
    }
  
    protected void calculateMSF( boolean isMin,
  			       WeightedGraph graph ) {
      
      PriorityQueue queue = 
        new BinaryHeap( isMin, new WeightedEdgeComparator( graph ));
      
      chords = new HashSet( graph.getEdges() );
  
      // Fill the Queue with all the edges.
      Iterator edges = graph.getEdges().iterator();
      while (edges.hasNext()) {
        queue.insert( edges.next() );
      }
  
      // Fill the graph we have with all the Vertexes.
      Iterator vertices = graph.getVertices().iterator();
      while (vertices.hasNext()) {
        Vertex v = (Vertex) vertices.next();
        labels.put( v, new Label() );
        addVertex( v );
      }
  
      // Bring the edges out in the right order.
      while (!queue.isEmpty()) {
        Edge e = (Edge) queue.pop();
  
        if ( connectsLabels( graph, e )) {
  	addEdge( graph, e );
        }
      }
    }
  
    public Set getChords() {
      return chords;
    }
  }
  
  
  
  
  
  
  
  1.1                  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/util/Label.java
  
  Index: Label.java
  ===================================================================
  package org.apache.commons.graph.algorithm.util;
  
  public class Label
  {
    private Label root = null;
  
    public Label() {
    }
  
    public Label( Label root ) {
      this.root = root.getRoot();
    }
    
    public void setRoot( Label root ) {
      if (this.root == null ) {
        this.root = root.getRoot();
      } else {
        if (root != this.root) {
  	this.root.setRoot( root.getRoot() );
  	this.root = root.getRoot();
        }
      }
    }
  
    public Label getRoot() {
      if ((root == null) ||
  	(root == this)) {
        return this;
      } else {
        root = root.getRoot();
        return root;
      }
    }
  }
  
  
  
  
  
  
  
  
  1.1                  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/util/PathImpl.java
  
  Index: PathImpl.java
  ===================================================================
  package org.apache.commons.graph.algorithm.util;
  
  import java.util.List;
  import java.util.ArrayList;
  
  import org.apache.commons.graph.*;
  
  public class PathImpl
    implements Path
  {
    protected List vertexList = new ArrayList();
    protected List edgeList = new ArrayList();
  
    public PathImpl( List vertexList,
  		   List edgeList ) {
      this.vertexList = vertexList;
      this.edgeList = edgeList;
    }
  
      public PathImpl( Vertex start ) {
  	this.vertexList.add( start );
      }
  
    public PathImpl( Vertex start,
  		   Vertex end,
  		   Edge edge ) {
      vertexList = new ArrayList();
      vertexList.add( start );
      vertexList.add( end );
  
      edgeList = new ArrayList();
      edgeList.add( edge );
    }
  
    public PathImpl append( PathImpl impl ) {
      List newVertices = new ArrayList( vertexList );
      newVertices.remove( newVertices.size() - 1 ); // Last should be duplicated
      newVertices.addAll( impl.getVertices() );
  
      List newEdges = new ArrayList( edgeList );
      newEdges.addAll( impl.getEdges() );
  
      return new PathImpl( newVertices, newEdges );
    }
  
      public PathImpl append( Vertex v, Edge e ) {
  	List newVertices = new ArrayList( vertexList );
  	newVertices.add( v );
  
  	List newEdges = new ArrayList( edgeList );
  	newEdges.add( e );
  	
  	return new PathImpl( newVertices, newEdges );
      }
  
    public Vertex getStart() {
      return (Vertex) vertexList.get( 0 );
    }
  
    public Vertex getEnd() {
      return (Vertex) vertexList.get( vertexList.size() - 1 );
    }
  
    public List getVertices() {
      return vertexList;
    }
  
    public List getEdges() {
      return edgeList;
    }
  
      public int size() {
  	return vertexList.size();
      }
  
    public String toString() {
      return vertexList.toString();
    }
  }
  
  
  
  
  
  1.1                  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/util/VertexPair.java
  
  Index: VertexPair.java
  ===================================================================
  package org.apache.commons.graph.algorithm.util;
  
  /* ====================================================================
   * 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
   *    "Commons" 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",
   *    "Commons", 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/>.
   */
  
  
  /**
   * VertexPair
   *
   * This is a tuple of two vertices which is capable
   * of storing things in a Hashtable.
   */
  
  import org.apache.commons.graph.*;
  
  public class VertexPair {
    public Vertex i = null;
    public Vertex j = null;
  
    public VertexPair( Vertex i, Vertex j ) {
      this.i = i;
      this.j = j;
    }
  
    public boolean equals( Object o ) {
      VertexPair vp = (VertexPair) o;
      return ( this.i == vp.i &&
  	     this.j == vp.j );
    }
  
    public int hashCode() {
      return (17 * i.hashCode()) + j.hashCode();
    }
  }
  
  
  
  
  
  

--
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