commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1139232 - in /commons/sandbox/graph/trunk/src: main/java/org/apache/commons/graph/ main/java/org/apache/commons/graph/model/ main/java/org/apache/commons/graph/shortestpath/ main/java/org/apache/commons/graph/utils/ test/java/org/apache/co...
Date Fri, 24 Jun 2011 10:31:13 GMT
Author: simonetripodi
Date: Fri Jun 24 10:31:12 2011
New Revision: 1139232

URL: http://svn.apache.org/viewvc?rev=1139232&view=rev
Log:
[SANDBOX-332] add FloydWarshall algorithm implementation - patch submitted by Marco Speranza

Added:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java
  (with props)
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/utils/VertexPair.java
  (with props)
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
  (with props)
Modified:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Graph.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseGraph.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseMutableGraph.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Graph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Graph.java?rev=1139232&r1=1139231&r2=1139232&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Graph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Graph.java Fri Jun
24 10:31:12 2011
@@ -22,10 +22,10 @@ package org.apache.commons.graph;
 import java.util.Set;
 
 /**
- * A Graph data structure consists of a finite (and possibly mutable) set of ordered pairs,
- * called {@link Edge}s or arcs, of certain entities called {@link Vertex} or node.
- * As in mathematics, an {@link Edge} {@code (x,y)} is said to point or go from {@code x}
to {@code y}.
- *
+ * A Graph data structure consists of a finite (and possibly mutable) set of ordered pairs,
called {@link Edge}s or
+ * arcs, of certain entities called {@link Vertex} or node. As in mathematics, an {@link
Edge} {@code (x,y)} is said to
+ * point or go from {@code x} to {@code y}.
+ * 
  * @param <V> the Graph vertices type
  * @param <E> the Graph edges type
  */
@@ -34,28 +34,37 @@ public interface Graph<V extends Vertex,
 
     /**
      * Returns the total set of Vertices in the graph.
-     *
+     * 
      * @return the total set of Vertices in the graph.
      */
     Set<V> getVertices();
 
     /**
      * Returns the total set of Edges in the graph.
-     *
+     * 
      * @return the total set of Edges in the graph.
      */
     Set<E> getEdges();
 
     /**
      * Returns all edges which touch this vertex, where the input vertex is in the edge head.
-     *
+     * 
      * @return all edges which touch this vertex, where the input vertex is in the edge head.
      */
     Set<E> getEdges( V v );
 
     /**
+     * Returns the edge with vertex source and target.
+     * 
+     * @param source the source vertex
+     * @param target the target vertex
+     * @return the edge with vertex source and target.
+     */
+    E getEdge( V source, V target );
+
+    /**
      * Return the set of {@link Vertex} on the input {@link Edge} (2 for normal edges, >
2 for HyperEdges)
-     *
+     * 
      * @return the set of {@link Vertex} on this Edge.
      */
     Set<V> getVertices( E e );

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseGraph.java?rev=1139232&r1=1139231&r2=1139232&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseGraph.java
(original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseGraph.java
Fri Jun 24 10:31:12 2011
@@ -30,13 +30,12 @@ import java.util.Set;
 import org.apache.commons.graph.Edge;
 import org.apache.commons.graph.Graph;
 import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.utils.VertexPair;
 
 /**
- * Basic abstract in-memory based of a simple read-only {@link Graph} implementation.
- *
- * Subclasses may load adjacency list/edges set in the constructor,
- * or expose {@link org.apache.commons.graph.MutableGraph} APIs.
- *
+ * Basic abstract in-memory based of a simple read-only {@link Graph} implementation. Subclasses
may load adjacency
+ * list/edges set in the constructor, or expose {@link org.apache.commons.graph.MutableGraph}
APIs.
+ * 
  * @param <V> the Graph vertices type
  * @param <E> the Graph edges type
  */
@@ -46,7 +45,7 @@ public abstract class BaseGraph<V extend
 
     private final Map<V, Set<E>> adjacencyList = new HashMap<V, Set<E>>();
 
-    private final Set<E> allEdges = new HashSet<E>();
+    private final Map<VertexPair<V>, E> indexedEdges = new HashMap<VertexPair<V>,
E>();
 
     /**
      * {@inheritDoc}
@@ -61,7 +60,7 @@ public abstract class BaseGraph<V extend
      */
     public final Set<E> getEdges()
     {
-        return unmodifiableSet( allEdges );
+        return unmodifiableSet( new HashSet<E>( indexedEdges.values() ) );
     }
 
     /**
@@ -75,6 +74,14 @@ public abstract class BaseGraph<V extend
     /**
      * {@inheritDoc}
      */
+    public final E getEdge( V source, V target )
+    {
+        return indexedEdges.get( new VertexPair<Vertex>( source, target ) );
+    }
+
+    /**
+     * {@inheritDoc}
+     */
     public final Set<V> getVertices( E e )
     {
         Set<V> vertices = new LinkedHashSet<V>();
@@ -87,7 +94,7 @@ public abstract class BaseGraph<V extend
 
     /**
      * Returns the adjacency list where stored vertex/edges.
-     *
+     * 
      * @return the adjacency list where stored vertex/edges.
      */
     protected final Map<V, Set<E>> getAdjacencyList()
@@ -97,14 +104,17 @@ public abstract class BaseGraph<V extend
 
     /**
      * Returns the set with all Graph edges.
-     *
+     * 
      * @return the set with all Graph edges.
      */
-    protected final Set<E> getAllEdges()
+    private final Set<E> getAllEdges()
     {
-        return allEdges;
+        return unmodifiableSet( new HashSet<E>( indexedEdges.values() ) );
     }
 
+    /**
+     * {@inheritDoc}
+     */
     @Override
     public boolean equals( Object obj )
     {
@@ -123,13 +133,14 @@ public abstract class BaseGraph<V extend
             return false;
         }
 
-        @SuppressWarnings( "unchecked" ) // test against any Graph typed instance
+        @SuppressWarnings( "unchecked" )
+        // test against any Graph typed instance
         BaseGraph<Vertex, Edge<Vertex>> other = (BaseGraph<Vertex, Edge<Vertex>>)
obj;
         if ( !adjacencyList.equals( other.getAdjacencyList() ) )
         {
             return false;
         }
-        if ( !allEdges.equals( other.getAllEdges() ) )
+        if ( !getAllEdges().equals( other.getAllEdges() ) )
         {
             return false;
         }
@@ -142,7 +153,15 @@ public abstract class BaseGraph<V extend
     @Override
     public String toString()
     {
-        return String.valueOf( getAdjacencyList() );
+        return String.valueOf( adjacencyList );
+    }
+
+    /**
+     * @return the indexedEdges
+     */
+    protected Map<VertexPair<V>, E> getIndexedEdges()
+    {
+        return indexedEdges;
     }
 
 }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseMutableGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseMutableGraph.java?rev=1139232&r1=1139231&r2=1139232&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseMutableGraph.java
(original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/BaseMutableGraph.java
Fri Jun 24 10:31:12 2011
@@ -28,6 +28,7 @@ import org.apache.commons.graph.Graph;
 import org.apache.commons.graph.GraphException;
 import org.apache.commons.graph.MutableGraph;
 import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.utils.VertexPair;
 
 /**
  * Basic abstract in-memory based of a simple mutable {@link Graph} implementation.
@@ -50,7 +51,8 @@ public abstract class BaseMutableGraph<V
             throw new GraphException( "Impossible to add a null Vertex to the Graph" );
         }
 
-        if ( getAdjacencyList().containsKey( v ) ){
+        if ( getAdjacencyList().containsKey( v ) )
+        {
             throw new GraphException( format( "Vertex '%s' already present in the Graph",
v ) );
         }
 
@@ -60,8 +62,6 @@ public abstract class BaseMutableGraph<V
     }
 
     /**
-     * 
-     *
      * @param v
      */
     protected abstract void decorateAddVertex( V v );
@@ -99,8 +99,9 @@ public abstract class BaseMutableGraph<V
     {
         checkEdge( e );
 
-        getAllEdges().add( e );
         getAdjacencyList().get( e.getHead() ).add( e );
+        getIndexedEdges().put( new VertexPair<V>( e.getHead(), e.getTail() ), e );
+
         decorateAddEdge( e );
     }
 
@@ -118,8 +119,9 @@ public abstract class BaseMutableGraph<V
     {
         checkEdge( e );
 
-        getAllEdges().remove( e );
         getAdjacencyList().get( e.getHead() ).remove( e );
+        getIndexedEdges().remove( new VertexPair<V>( e.getHead(), e.getTail() ) );
+
         decorateRemoveEdge( e );
     }
 

Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java?rev=1139232&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java
(added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java
Fri Jun 24 10:31:12 2011
@@ -0,0 +1,154 @@
+package org.apache.commons.graph.shortestpath;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import java.util.HashMap;
+import java.util.Map;
+
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.WeightedEdge;
+import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.utils.VertexPair;
+
+/**
+ * Represents all shortest paths between all vertex pairs calculated by {@link FloydWarshall}
algorithm.
+ * 
+ * @param <V> the Graph vertices type
+ * @param <E> the Graph edges type
+ */
+public final class AllVertexPairsShortestPath<V extends Vertex, WE extends WeightedEdge<V>>
+{
+
+    private final Map<VertexPair<V>, WeightedPath<V, WE>> paths = new HashMap<VertexPair<V>,
WeightedPath<V, WE>>();
+
+    private final Map<VertexPair<V>, Double> shortestDistances = new HashMap<VertexPair<V>,
Double>();
+
+    /**
+     * Constructor visible only inside the package
+     */
+    AllVertexPairsShortestPath()
+    {
+        // do nothing
+    }
+
+    /**
+     * @param source
+     * @param target
+     * @param weightedPath
+     */
+    void addShortestPath( V source, V target, WeightedPath<V, WE> weightedPath )
+    {
+        if ( source == null )
+        {
+            throw new IllegalArgumentException( "Impossible to add a shortest path from a
null source" );
+        }
+        if ( target == null )
+        {
+            throw new IllegalArgumentException( "Impossible to add a shortest path to a null
target" );
+        }
+        if ( weightedPath == null )
+        {
+            throw new IllegalArgumentException( "Impossible to add a null weightedPath path
to a null target" );
+        }
+
+        paths.put( new VertexPair<V>( source, target ), weightedPath );
+    }
+
+    /**
+     * Returns the shortest path between source and target
+     * 
+     * @param source The source Vertex
+     * @param target The target Vertex
+     * @return Returns the shortest path between source and target
+     */
+    public WeightedPath<V, WE> findShortestPath( V source, V target )
+    {
+        if ( source == null )
+        {
+            throw new IllegalArgumentException( "Impossible to find the shortest path from
a null source" );
+        }
+        if ( target == null )
+        {
+            throw new IllegalArgumentException( "Impossible to find the shortest path to
a null target" );
+        }
+
+        VertexPair<V> vertexPair = new VertexPair<V>( source, target );
+        WeightedPath<V, WE> path = paths.get( vertexPair );
+
+        return path;
+    }
+
+    /**
+     * @param source
+     * @param target
+     * @param distance
+     */
+    void addShortestDistance( V source, V target, Double distance )
+    {
+        if ( source == null )
+        {
+            throw new IllegalArgumentException( "Impossible to add a shortest distance with
a null source" );
+        }
+        if ( target == null )
+        {
+            throw new IllegalArgumentException( "Impossible to add a shortest distance with
a null target" );
+        }
+        if ( distance == null )
+        {
+            throw new IllegalArgumentException( "Impossible to add a shortest distance with
a null distance" );
+        }
+
+        shortestDistances.put( new VertexPair<V>( source, target ), distance );
+    }
+
+    /**
+     * Returns the shortest distance between source and target.
+     * 
+     * @param source The source Vertex
+     * @param target The target Vertex
+     * @return Returns the shortest distance between source and target.
+     */
+    public Double getShortestDistance( V source, V target )
+    {
+        if ( source == null )
+        {
+            throw new IllegalArgumentException( "Impossible to get the shortest distance
from a null source" );
+        }
+        if ( target == null )
+        {
+            throw new IllegalArgumentException( "Impossible to get the shortest distance
to a null target" );
+        }
+
+        if ( source.equals( target ) )
+        {
+            return 0D;
+        }
+
+        Double distance = shortestDistances.get( new VertexPair<V>( source, target
) );
+
+        if ( distance == null )
+        {
+            return Double.POSITIVE_INFINITY;
+        }
+
+        return distance;
+    }
+
+}

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AllVertexPairsShortestPath.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java?rev=1139232&r1=1139231&r2=1139232&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java
(original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/FloydWarshall.java
Fri Jun 24 10:31:12 2011
@@ -19,40 +19,116 @@ package org.apache.commons.graph.shortes
  * under the License.
  */
 
+import java.util.HashMap;
+import java.util.Map;
+
 import org.apache.commons.graph.Vertex;
 import org.apache.commons.graph.WeightedEdge;
 import org.apache.commons.graph.WeightedGraph;
 import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.utils.VertexPair;
 
 /**
- * Contains the FloydÐWarshall's shortest path algorithm implementation.
+ * Contains the Floyd�Warshall's shortest paths algorithm implementation.
  */
 public final class FloydWarshall
 {
 
     /**
-     * This class can not be instantiated directly
+     * This class can't be explicitly instantiated.
      */
     private FloydWarshall()
     {
-        // do nothing
+        // do nothgin
     }
 
     /**
-     * Applies the classical FloydÐWarshall's algorithm to find the shortest path from the
source to the target, if exists.
-     *
+     * Applies the classical Floyd�Warshall's algorithm to find all vertex shortest
path
+     * 
      * @param <V> the Graph vertices type.
      * @param <WE> the Graph weighted edges type
-     * @param graph the Graph which shortest path from {@code source} to {@code target} has
to be found
-     * @param source the shortest path source Vertex
-     * @param target the shortest path target Vertex
-     * @return a path which describes the shortest path, if any, otherwise a {@link PathNotFoundException}
will be thrown
+     * @return a data structure which contains all vertex pairs shortest path.
      */
-    public static <V extends Vertex, WE extends WeightedEdge<V>> WeightedPath<V,
WE> findShortestPath( WeightedGraph<V, WE> graph,
-                                                                                        
              V source,
-                                                                                        
              V target )
+    public static <V extends Vertex, WE extends WeightedEdge<V>> AllVertexPairsShortestPath<V,
WE> findAllVertexPairsShortestPath( WeightedGraph<V, WE> graph )
+    {
+        AllVertexPairsShortestPath<V, WE> shortesPaths = new AllVertexPairsShortestPath<V,
WE>();
+        Map<VertexPair<V>, V> next = new HashMap<VertexPair<V>, V>();
+
+        // init
+        for ( WE we : graph.getEdges() )
+        {
+            shortesPaths.addShortestDistance( we.getHead(), we.getTail(), we.getWeight()
);
+        }
+
+        // run the Floyd-Warshall algorithm.
+
+        for ( V k : graph.getVertices() )
+        {
+            for ( V i : graph.getVertices() )
+            {
+                for ( V j : graph.getVertices() )
+                {
+                    Double newDistance =
+                        shortesPaths.getShortestDistance( i, k ) + shortesPaths.getShortestDistance(
k, j );
+                    if ( newDistance < shortesPaths.getShortestDistance( i, j ) )
+                    {
+                        shortesPaths.addShortestDistance( i, j, newDistance );
+
+                        // store the intermediate vertex
+                        next.put( new VertexPair<V>( i, j ), k );
+                    }
+                }
+            }
+
+        }
+
+        // fills all WeightedPaths
+        for ( V source : graph.getVertices() )
+        {
+            for ( V target : graph.getVertices() )
+            {
+                if ( !source.equals( target ) )
+                {
+                    PredecessorsList<V, WE> predecessorsList = new PredecessorsList<V,
WE>();
+
+                    pathReconstruction( predecessorsList, source, target, next, graph );
+                    if ( !predecessorsList.predecessors.isEmpty() )
+                    {
+                        WeightedPath<V, WE> weightedPath = predecessorsList.buildPath(
source, target );
+                        if ( weightedPath.size() > 0 )
+                        {
+                            shortesPaths.addShortestPath( source, target, weightedPath );
+                        }
+                    }
+
+                }
+            }
+        }
+
+        return shortesPaths;
+    }
+
+    private static <V extends Vertex, WE extends WeightedEdge<V>> void pathReconstruction(
PredecessorsList<V, WE> path,
+                                                                                        
  V source, V target,
+                                                                                        
  Map<VertexPair<V>, V> next,
+                                                                                        
  WeightedGraph<V, WE> graph )
     {
-        return null;
+        V k = next.get( new VertexPair<Vertex>( source, target ) );
+        if ( k == null )
+        {
+            // there is a direct path between a and b
+            WE edge = graph.getEdge( source, target );
+            if ( edge != null )
+            {
+                path.addPredecessor( target, edge );
+            }
+        }
+        else
+        {
+            pathReconstruction( path, source, k, next, graph );
+            pathReconstruction( path, k, target, next, graph );
+        }
+
     }
 
 }

Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/utils/VertexPair.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/utils/VertexPair.java?rev=1139232&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/utils/VertexPair.java
(added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/utils/VertexPair.java
Fri Jun 24 10:31:12 2011
@@ -0,0 +1,121 @@
+package org.apache.commons.graph.utils;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import org.apache.commons.graph.Vertex;
+
+/**
+ * Indicates a {@link Vertex} pair.
+ *
+ * @param <V> the Graph vertices type
+ */
+public final class VertexPair<V extends Vertex>
+{
+
+    private final V head;
+
+    private final V tail;
+
+    /**
+     * Initializes a new {@link Vertex} pair.
+     *
+     * @param head the head Vertex
+     * @param tail the tail Vertex
+     */
+    public VertexPair( V head, V tail )
+    {
+        if ( head == null )
+        {
+            throw new IllegalArgumentException( "Impossible to construct a Vertex with a
null head" );
+        }
+        if ( tail == null )
+        {
+            throw new IllegalArgumentException( "Impossible to construct a Vertex with a
null tail" );
+        }
+        this.head = head;
+        this.tail = tail;
+    }
+
+    /**
+     * @return the source
+     */
+    public V getHead()
+    {
+        return head;
+    }
+
+    /**
+     * @return the target
+     */
+    public V getTail()
+    {
+        return tail;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public int hashCode()
+    {
+        final int prime = 31;
+        int result = 1;
+        result = prime * result + ( ( head == null ) ? 0 : head.hashCode() );
+        result = prime * result + ( ( tail == null ) ? 0 : tail.hashCode() );
+        return result;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public boolean equals( Object obj )
+    {
+        if ( this == obj )
+        {
+            return true;
+        }
+
+        if ( obj == null )
+        {
+            return false;
+        }
+
+        if ( getClass() != obj.getClass() )
+        {
+            return false;
+        }
+
+        @SuppressWarnings( "unchecked" ) // equals() invoked against only same VertexPair
type
+        VertexPair<V> other = (VertexPair<V>) obj;
+        if ( !head.equals( other.getHead() ) )
+        {
+            return false;
+        }
+
+        if ( !tail.equals( other.getTail() ) )
+        {
+            return false;
+        }
+
+        return true;
+    }
+
+}

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/utils/VertexPair.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/utils/VertexPair.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/utils/VertexPair.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Added: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java?rev=1139232&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
(added)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
Fri Jun 24 10:31:12 2011
@@ -0,0 +1,167 @@
+package org.apache.commons.graph.shortestpath;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import static org.apache.commons.graph.shortestpath.FloydWarshall.findAllVertexPairsShortestPath;
+import static junit.framework.Assert.assertEquals;
+
+import org.apache.commons.graph.MutableGraph;
+import org.apache.commons.graph.UndirectedGraph;
+import org.apache.commons.graph.WeightedGraph;
+import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.model.BaseLabeledVertex;
+import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
+import org.apache.commons.graph.model.DirectedMutableWeightedGraph;
+import org.apache.commons.graph.model.InMemoryWeightedPath;
+import org.apache.commons.graph.model.UndirectedMutableWeightedGraph;
+import org.junit.Test;
+
+/**
+ */
+public class FloydWarshallTestCase
+{
+
+    @Test
+    public void undirectedShortestPath()
+    {
+        findShortestPathAndVerify( new UndirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge>() );
+    }
+
+    @Test
+    public void directedShortestPath()
+    {
+        findShortestPathAndVerify( new DirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge>() );
+    }
+
+    @SuppressWarnings( "unchecked" )
+    private void findShortestPathAndVerify( WeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge>
weighted )
+    {
+        // mutable by definition, generic types driven by input graph
+        MutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge> mutable =
+            (MutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge>) weighted;
+
+        // building Graph
+
+        BaseLabeledVertex one = new BaseLabeledVertex( "1" );
+        BaseLabeledVertex two = new BaseLabeledVertex( "2" );
+        BaseLabeledVertex three = new BaseLabeledVertex( "3" );
+        BaseLabeledVertex four = new BaseLabeledVertex( "4" );
+        BaseLabeledVertex five = new BaseLabeledVertex( "5" );
+        BaseLabeledVertex six = new BaseLabeledVertex( "6" );
+
+        mutable.addVertex( one );
+        mutable.addVertex( two );
+        mutable.addVertex( three );
+        mutable.addVertex( four );
+        mutable.addVertex( five );
+        mutable.addVertex( six );
+
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", one, six, 14D ) );
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", one, three, 9D ) );
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", one, two, 7D ) );
+
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", two, three, 10D ) );
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", two, four, 15D ) );
+
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", three, six, 2D ) );
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", three, four, 11D ) );
+
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", four, five, 6D ) );
+        mutable.addEdge( new BaseLabeledWeightedEdge( "", six, five, 9D ) );
+
+        // reverse all edges
+        if ( weighted instanceof UndirectedGraph )
+        {
+            mutable.addEdge( new BaseLabeledWeightedEdge( "", six, one, 14D ) );
+            mutable.addEdge( new BaseLabeledWeightedEdge( "", three, one, 9D ) );
+            mutable.addEdge( new BaseLabeledWeightedEdge( "", two, one, 7D ) );
+
+            mutable.addEdge( new BaseLabeledWeightedEdge( "", three, two, 10D ) );
+            mutable.addEdge( new BaseLabeledWeightedEdge( "", four, two, 15D ) );
+
+            mutable.addEdge( new BaseLabeledWeightedEdge( "", six, three, 2D ) );
+            mutable.addEdge( new BaseLabeledWeightedEdge( "", four, three, 11D ) );
+
+            mutable.addEdge( new BaseLabeledWeightedEdge( "", five, four, 6D ) );
+            mutable.addEdge( new BaseLabeledWeightedEdge( "", five, six, 9D ) );
+        }
+
+        AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge> p =
+            findAllVertexPairsShortestPath( weighted );
+
+        if ( weighted instanceof UndirectedGraph )
+        {
+            // Verify shortestDistance
+            assertEquals( 11D, p.getShortestDistance( one, six ) );
+
+            assertEquals( 11D, p.getShortestDistance( six, one ) );
+
+            assertEquals( 6D, p.getShortestDistance( four, five ) );
+            assertEquals( 6D, p.getShortestDistance( five, four ) );
+
+            assertEquals( 20D, p.getShortestDistance( one, five ) );
+            assertEquals( 20D, p.getShortestDistance( five, one ) );
+
+            // Verify shortest paths
+
+            WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> wp = p.findShortestPath(
one, six );
+
+            // Expected
+            InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected
=
+                new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>(
one, six );
+            expected.addVertexInTail( one );
+            expected.addVertexInTail( three );
+            expected.addVertexInTail( six );
+
+            expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", one, three, 9D ) );
+            expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", three, six, 2D ) );
+
+            // Actual
+            assertEquals( expected, wp );
+        }
+        else
+        {
+            assertEquals( 11D, p.getShortestDistance( one, six ) );
+
+            assertEquals( 6D, p.getShortestDistance( four, five ) );
+
+            assertEquals( 20D, p.getShortestDistance( one, five ) );
+            assertEquals( Double.POSITIVE_INFINITY, p.getShortestDistance( five, one ) );
+
+            // Verify shortest paths
+            WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> wp = p.findShortestPath(
five, one );
+            assertEquals( null, wp );
+
+            InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected
=
+                new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>(
one, six );
+            expected.addVertexInTail( one );
+            expected.addVertexInTail( three );
+            expected.addVertexInTail( six );
+
+            expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", one, three, 9D ) );
+            expected.addEdgeInTail( new BaseLabeledWeightedEdge( "", three, six, 2D ) );
+
+            // Actual
+            wp = p.findShortestPath( one, six );
+            assertEquals( expected, wp );
+        }
+    }
+
+}

Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain



Mime
View raw message