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
