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