Return-Path: Delivered-To: apmail-jakarta-commons-dev-archive@apache.org Received: (qmail 40777 invoked from network); 8 May 2002 17:37:19 -0000 Received: from unknown (HELO nagoya.betaversion.org) (192.18.49.131) by daedalus.apache.org with SMTP; 8 May 2002 17:37:19 -0000 Received: (qmail 25488 invoked by uid 97); 8 May 2002 17:37:03 -0000 Delivered-To: qmlist-jakarta-archive-commons-dev@jakarta.apache.org Received: (qmail 25331 invoked by uid 97); 8 May 2002 17:37:02 -0000 Mailing-List: contact commons-dev-help@jakarta.apache.org; run by ezmlm Precedence: bulk List-Unsubscribe: List-Subscribe: List-Help: List-Post: List-Id: "Jakarta Commons Developers List" Reply-To: "Jakarta Commons Developers List" Delivered-To: mailing list commons-dev@jakarta.apache.org Received: (qmail 18755 invoked by uid 97); 8 May 2002 17:34:16 -0000 X-Antivirus: nagoya (v4198 created Apr 24 2002) Date: 8 May 2002 17:34:09 -0000 Message-ID: <20020508173409.4072.qmail@icarus.apache.org> From: ddp@apache.org To: jakarta-commons-sandbox-cvs@apache.org Subject: cvs commit: jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/util Label.java PathImpl.java VertexPair.java X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N 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 * . */ /** * 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 * . */ /** * 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 * . */ /** * 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 * . */ /** * 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 * . */ /** * 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 * . */ 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 * . */ /** * 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: For additional commands, e-mail: