commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1142404 - 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/ test/java/org/apache/commons/graph/shortestpath/
Date Sun, 03 Jul 2011 08:47:21 GMT
Author: simonetripodi
Date: Sun Jul  3 08:47:20 2011
New Revision: 1142404

URL: http://svn.apache.org/viewvc?rev=1142404&view=rev
Log:
Path implemented as a Graph - it can be rendered by the Exporters

Modified:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Path.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryPath.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Path.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Path.java?rev=1142404&r1=1142403&r2=1142404&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Path.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/Path.java Sun Jul 
3 08:47:20 2011
@@ -27,6 +27,7 @@ package org.apache.commons.graph;
  * @param <E> the Graph edges type
  */
 public interface Path<V extends Vertex, E extends Edge>
+    extends Graph<V, E>
 {
 
     /**
@@ -43,37 +44,4 @@ public interface Path<V extends Vertex, 
      */
     V getTarget();
 
-    /**
-     * Returns a list of Vertices, in order as they go from Start to End.
-     *
-     * This includes the Start and End vertex, and will have one
-     * more entry than the Edges list.
-     *
-     * @return a list of Vertices, in order as they go from Start to End.
-     */
-    Iterable<V> getVertices();
-
-    /**
-     * Returns the <i>order</i> of a Graph (the number of Vertices);
-     *
-     * @return the <i>order</i> of a Graph (the number of Vertices);
-     */
-    int getOrder();
-
-    /**
-     * Returns a list of Edges which comprise the path.
-     *
-     * It will have one less than the list of Vertices.
-     *
-     * @return a list of Edges which comprise the path.
-     */
-    Iterable<E> getEdges();
-
-    /**
-     * Returns the <i>size</i> of a Graph (the number of Edges)
-     *
-     * @return the <i>size</i> of a Graph (the number of Edges)
-     */
-    int getSize();
-
 }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryPath.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryPath.java?rev=1142404&r1=1142403&r2=1142404&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryPath.java
(original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryPath.java
Sun Jul  3 08:47:20 2011
@@ -19,14 +19,19 @@ package org.apache.commons.graph.model;
  * under the License.
  */
 
+import static java.util.Arrays.asList;
 import static java.lang.String.format;
 import static java.util.Collections.unmodifiableList;
 
+import java.util.HashMap;
 import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
 
 import org.apache.commons.graph.Edge;
 import org.apache.commons.graph.Path;
 import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.VertexPair;
 
 /**
  * Support {@link Path} implementation, optimized for algorithms (such Dijkstra's) that need
to rebuild the path
@@ -47,6 +52,12 @@ public class InMemoryPath<V extends Vert
 
     private final LinkedList<E> edges = new LinkedList<E>();
 
+    private final Map<V, V> successors = new HashMap<V, V>();
+
+    private final Map<VertexPair<V>, E> indexedEdges = new HashMap<VertexPair<V>,
E>();
+
+    private final Map<E, VertexPair<V>> indexedVertices = new HashMap<E, VertexPair<V>>();
+
     public InMemoryPath( V start, V target )
     {
         if ( start == null )
@@ -78,16 +89,6 @@ public class InMemoryPath<V extends Vert
         return target;
     }
 
-    public void addVertexInHead( V vertex )
-    {
-        vertices.addFirst( vertex );
-    }
-
-    public void addVertexInTail( V vertex )
-    {
-        vertices.addLast( vertex );
-    }
-
     /**
      * {@inheritDoc}
      */
@@ -104,14 +105,27 @@ public class InMemoryPath<V extends Vert
         return vertices.size();
     }
 
-    public void addEdgeInHead( E edge )
+    public void addConnectionInHead( V head, E edge, V tail )
     {
+        vertices.addFirst( head );
         edges.addFirst( edge );
+        addConnection( head, edge, tail );
     }
 
-    public void addEdgeInTail( E edge )
+    public void addConnectionInTail( V head, E edge, V tail )
     {
+        vertices.addLast( head );
         edges.addLast( edge );
+        addConnection( head, edge, tail );
+    }
+
+    private void addConnection( V head, E edge, V tail )
+    {
+        successors.put( head, tail );
+
+        VertexPair<V> vertexPair = new VertexPair<V>( head, tail );
+        indexedEdges.put( vertexPair, edge );
+        indexedVertices.put( edge, vertexPair );
     }
 
     /**
@@ -133,6 +147,70 @@ public class InMemoryPath<V extends Vert
     /**
      * {@inheritDoc}
      */
+    public int getDegree( V v )
+    {
+        if ( v == null )
+        {
+            throw new IllegalArgumentException( "Impossible to get the degree of a null vertex"
);
+        }
+
+        if ( !successors.containsKey( v ) )
+        {
+            throw new IllegalArgumentException( "Impossible to get the degree of vertex not
contained in this path" );
+        }
+
+        if ( source.equals( v ) || target.equals( v ) )
+        {
+            return 1;
+        }
+
+        return 2;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public Iterable<V> getConnectedVertices( V v )
+    {
+        if ( v == null )
+        {
+            throw new IllegalArgumentException( "Impossible to get the successor of a null
vertex" );
+        }
+
+        if ( target.equals( v ) )
+        {
+            return null;
+        }
+
+        if ( !successors.containsKey( v ) )
+        {
+            throw new IllegalArgumentException( "Impossible to get the successor of vertex
not contained in this path" );
+        }
+
+        @SuppressWarnings( "unchecked" ) // type driven by input type
+        List<V> connected = asList( successors.get( v ) );
+        return connected;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public E getEdge( V source, V target )
+    {
+        return indexedEdges.get( new VertexPair<V>( source, target ) );
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    public VertexPair<V> getVertices( E e )
+    {
+        return indexedVertices.get( e );
+    }
+
+    /**
+     * {@inheritDoc}
+     */
     @Override
     public int hashCode()
     {

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java?rev=1142404&r1=1142403&r2=1142404&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java
(original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/model/InMemoryWeightedPath.java
Sun Jul  3 08:47:20 2011
@@ -48,9 +48,9 @@ public final class InMemoryWeightedPath<
      * {@inheritDoc}
      */
     @Override
-    public void addEdgeInHead( WE edge )
+    public void addConnectionInHead( V head, WE edge, V tail )
     {
-        super.addEdgeInHead( edge );
+        super.addConnectionInHead( head, edge, tail );
         increaseWeight( edge );
     }
 
@@ -58,9 +58,9 @@ public final class InMemoryWeightedPath<
      * {@inheritDoc}
      */
     @Override
-    public void addEdgeInTail( WE edge )
+    public void addConnectionInTail( V head, WE edge, V tail )
     {
-        super.addEdgeInTail( edge );
+        super.addConnectionInTail( head, edge, tail );
         increaseWeight( edge );
     }
 

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java?rev=1142404&r1=1142403&r2=1142404&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
(original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
Sun Jul  3 08:47:20 2011
@@ -77,14 +77,11 @@ final class PredecessorsList<V extends V
             V predecessor = predecessors.get( vertex );
             WE edge = graph.getEdge( predecessor, vertex );
 
-            path.addEdgeInHead( edge );
-            path.addVertexInHead( vertex );
+            path.addConnectionInHead( predecessor, edge, vertex );
 
             vertex = predecessor;
         }
 
-        path.addVertexInHead( source );
-
         return path;
     }
 

Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java?rev=1142404&r1=1142403&r2=1142404&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java
(original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/AStarTestCase.java
Sun Jul  3 08:47:20 2011
@@ -98,16 +98,10 @@ public final class AStarTestCase
         InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
             new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( start,
goal );
 
-        expected.addVertexInTail( start );
-        expected.addVertexInTail( a );
-        expected.addVertexInTail( b );
-        expected.addVertexInTail( c );
-        expected.addVertexInTail( goal );
-
-        expected.addEdgeInTail( new BaseLabeledWeightedEdge( "start <-> a", 1.5D )
);
-        expected.addEdgeInTail( new BaseLabeledWeightedEdge( "a <-> b", 2D ) );
-        expected.addEdgeInTail( new BaseLabeledWeightedEdge( "b <-> c", 3D ) );
-        expected.addEdgeInTail( new BaseLabeledWeightedEdge( "c <-> goal", 3D ) );
+        expected.addConnectionInTail( start, new BaseLabeledWeightedEdge( "start <->
a", 1.5D ), a );
+        expected.addConnectionInTail( a, new BaseLabeledWeightedEdge( "a <-> b", 2D
), b );
+        expected.addConnectionInTail( b, new BaseLabeledWeightedEdge( "b <-> c", 3D
), c );
+        expected.addConnectionInTail( c, new BaseLabeledWeightedEdge( "c <-> goal",
3D ), goal );
 
         // actual path
 

Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java?rev=1142404&r1=1142403&r2=1142404&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java
(original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/BellmannFordTestCase.java
Sun Jul  3 08:47:20 2011
@@ -73,12 +73,8 @@ public final class BellmannFordTestCase
         // the expected weighted path
         InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
             new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( one,
three );
-        expected.addVertexInTail( one );
-        expected.addVertexInTail( four );
-        expected.addVertexInTail( three );
-
-        expected.addEdgeInTail( new BaseLabeledWeightedEdge( "1 -> 4", 7D ) );
-        expected.addEdgeInTail( new BaseLabeledWeightedEdge( "4 -> 3", -3D ) );
+        expected.addConnectionInTail( one, new BaseLabeledWeightedEdge( "1 -> 4", 7D ),
four );
+        expected.addConnectionInTail( four, new BaseLabeledWeightedEdge( "4 -> 3", -3D
), three );
 
         // the actual weighted path
         AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge> allVertexPairsShortestPath
=

Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java?rev=1142404&r1=1142403&r2=1142404&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java
(original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/DijkstraTestCase.java
Sun Jul  3 08:47:20 2011
@@ -76,14 +76,9 @@ public final class DijkstraTestCase
         InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected =
             new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>( one,
five );
 
-        expected.addVertexInTail( one );
-        expected.addVertexInTail( three );
-        expected.addVertexInTail( six );
-        expected.addVertexInTail( five );
-
-        expected.addEdgeInTail( new BaseLabeledWeightedEdge( "1 -> 3", 9D ) );
-        expected.addEdgeInTail( new BaseLabeledWeightedEdge( "3 -> 6", 2D ) );
-        expected.addEdgeInTail( new BaseLabeledWeightedEdge( "6 -> 5", 9D ) );
+        expected.addConnectionInTail( one, new BaseLabeledWeightedEdge( "1 -> 3", 9D ),
three );
+        expected.addConnectionInTail( three, new BaseLabeledWeightedEdge( "3 -> 6", 2D
), six );
+        expected.addConnectionInTail( six, new BaseLabeledWeightedEdge( "6 -> 5", 9D ),
five );
 
         // actual path
 

Modified: 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=1142404&r1=1142403&r2=1142404&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
(original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/shortestpath/FloydWarshallTestCase.java
Sun Jul  3 08:47:20 2011
@@ -110,12 +110,8 @@ public class FloydWarshallTestCase
             // Expected
             InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected
=
                 new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>(
one, six );
-            expected.addVertexInTail( one );
-            expected.addVertexInTail( three );
-            expected.addVertexInTail( six );
-
-            expected.addEdgeInTail( new BaseLabeledWeightedEdge( "1 -> 3", 9D ) );
-            expected.addEdgeInTail( new BaseLabeledWeightedEdge( "3 -> 6", 2D ) );
+            expected.addConnectionInTail( one, new BaseLabeledWeightedEdge( "1 -> 3",
9D ), three );
+            expected.addConnectionInTail( three, new BaseLabeledWeightedEdge( "3 -> 6",
2D ), six );
 
             // Actual
             assertEquals( expected, wp );
@@ -142,12 +138,8 @@ public class FloydWarshallTestCase
 
             InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge> expected
=
                 new InMemoryWeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge>(
one, six );
-            expected.addVertexInTail( one );
-            expected.addVertexInTail( three );
-            expected.addVertexInTail( six );
-
-            expected.addEdgeInTail( new BaseLabeledWeightedEdge( "1 -> 3", 9D ) );
-            expected.addEdgeInTail( new BaseLabeledWeightedEdge( "3 -> 6", 2D ) );
+            expected.addConnectionInTail( one, new BaseLabeledWeightedEdge( "1 -> 3",
9D ), three );
+            expected.addConnectionInTail( three, new BaseLabeledWeightedEdge( "3 -> 6",
2D ), six );
 
             // Actual
             wp = p.findShortestPath( one, six );



Mime
View raw message