You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by si...@apache.org on 2011/06/22 20:45:15 UTC
svn commit: r1138576 - in /commons/sandbox/graph/trunk: ./
src/main/java/org/apache/commons/graph/model/
src/main/java/org/apache/commons/graph/shortestpath/
src/main/java/org/apache/commons/graph/utils/
src/main/java/org/apache/commons/graph/visit/ sr...
Author: simonetripodi
Date: Wed Jun 22 18:45:14 2011
New Revision: 1138576
URL: http://svn.apache.org/viewvc?rev=1138576&view=rev
Log:
trying to add automagically the inverted Edge in UndirectedGraph is not successfully, switched back to a more traditional implementation where bi-directional edges have to be added explicitely
Removed:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/utils/Edges.java
Modified:
commons/sandbox/graph/trunk/ (props changed)
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/AStar.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/Visit.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledEdge.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledWeightedEdge.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/visit/VisitTestCase.java
Propchange: commons/sandbox/graph/trunk/
------------------------------------------------------------------------------
--- svn:ignore (original)
+++ svn:ignore Wed Jun 22 18:45:14 2011
@@ -5,3 +5,5 @@ velocity.log*
.classpath
.project
maven.log
+
+InvertedEdgeAdapter.patch
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=1138576&r1=1138575&r2=1138576&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 Wed Jun 22 18:45:14 2011
@@ -101,8 +101,6 @@ public abstract class BaseMutableGraph<V
getAllEdges().add( e );
getAdjacencyList().get( e.getHead() ).add( e );
- getAdjacencyList().get( e.getTail() ).add( e );
-
decorateAddEdge( e );
}
@@ -122,8 +120,6 @@ public abstract class BaseMutableGraph<V
getAllEdges().remove( e );
getAdjacencyList().get( e.getHead() ).remove( e );
- getAdjacencyList().get( e.getTail() ).remove( e );
-
decorateRemoveEdge( e );
}
@@ -143,11 +139,11 @@ public abstract class BaseMutableGraph<V
{
if ( !getAdjacencyList().containsKey( e.getHead() ) )
{
- throw new GraphException( format( "Vertex '%s' not present in the Graph", e.getHead() ) );
+ throw new GraphException( format( "Head Vertex '%s' not present in the Graph", e.getHead() ) );
}
if ( !getAdjacencyList().containsKey( e.getTail() ) )
{
- throw new GraphException( format( "Vertex '%s' not present in the Graph", e.getTail() ) );
+ throw new GraphException( format( "Tail Vertex '%s' not present in the Graph", e.getTail() ) );
}
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java?rev=1138576&r1=1138575&r2=1138576&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/AStar.java Wed Jun 22 18:45:14 2011
@@ -20,7 +20,6 @@ package org.apache.commons.graph.shortes
*/
import static java.lang.String.format;
-import static org.apache.commons.graph.utils.Edges.getConnectedVertex;
import java.util.HashSet;
import java.util.PriorityQueue;
@@ -100,7 +99,7 @@ public final class AStar
: graph.getEdges( current );
for ( WE edge : edges )
{
- V v = getConnectedVertex( current, edge );
+ V v = edge.getTail();
if ( !closedSet.contains( v ) )
{
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java?rev=1138576&r1=1138575&r2=1138576&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/Dijkstra.java Wed Jun 22 18:45:14 2011
@@ -20,7 +20,6 @@ package org.apache.commons.graph.shortes
*/
import static java.lang.String.format;
-import static org.apache.commons.graph.utils.Edges.getConnectedVertex;
import java.util.HashSet;
import java.util.PriorityQueue;
@@ -87,7 +86,7 @@ public final class Dijkstra
for ( WE edge : graph.getOutbound( vertex ) )
{
- V v = getConnectedVertex( vertex, edge );
+ V v = edge.getTail();
// skip node already settled
if ( !settledNodes.contains( v ) )
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=1138576&r1=1138575&r2=1138576&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 Wed Jun 22 18:45:14 2011
@@ -19,8 +19,6 @@ package org.apache.commons.graph.shortes
* under the License.
*/
-import static org.apache.commons.graph.utils.Edges.getConnectedVertex;
-
import java.util.HashMap;
import java.util.Map;
@@ -73,7 +71,7 @@ final class PredecessorsList<V extends V
path.addEdgeInHead( edge );
path.addVertexInHead( vertex );
- vertex = getConnectedVertex( vertex, edge );
+ vertex = edge.getHead();
}
path.addVertexInHead( source );
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/Visit.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/Visit.java?rev=1138576&r1=1138575&r2=1138576&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/Visit.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/Visit.java Wed Jun 22 18:45:14 2011
@@ -19,8 +19,6 @@ package org.apache.commons.graph.visit;
* under the License.
*/
-import static org.apache.commons.graph.utils.Edges.getConnectedVertex;
-
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
@@ -97,7 +95,7 @@ public final class Visit
: graph.getEdges( v );
for ( E e : edges )
{
- V w = getConnectedVertex( v, e );
+ V w = e.getTail();
if ( visitedVetices.add( w ) )
{
@@ -174,7 +172,7 @@ public final class Visit
: graph.getEdges( v );
for ( E e : edges )
{
- V w = getConnectedVertex( v, e );
+ V w = e.getTail();
if ( visitedVetices.add( w ) )
{
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledEdge.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledEdge.java?rev=1138576&r1=1138575&r2=1138576&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledEdge.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledEdge.java Wed Jun 22 18:45:14 2011
@@ -141,6 +141,11 @@ public class BaseLabeledEdge
return true;
}
+ public BaseLabeledEdge reverse()
+ {
+ return new BaseLabeledEdge( label, tail, head );
+ }
+
/**
* {@inheritDoc}
*/
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledWeightedEdge.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledWeightedEdge.java?rev=1138576&r1=1138575&r2=1138576&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledWeightedEdge.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/model/BaseLabeledWeightedEdge.java Wed Jun 22 18:45:14 2011
@@ -55,6 +55,12 @@ public class BaseLabeledWeightedEdge
return weight;
}
+ @Override
+ public BaseLabeledEdge reverse()
+ {
+ return new BaseLabeledWeightedEdge( getLabel(), getTail(), getHead(), weight );
+ }
+
/**
* {@inheritDoc}
*/
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=1138576&r1=1138575&r2=1138576&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 Wed Jun 22 18:45:14 2011
@@ -64,14 +64,21 @@ public final class AStarTestCase
graph.addVertex( goal );
graph.addEdge( new BaseLabeledWeightedEdge( "", start, a, 1.5D ) );
+ graph.addEdge( new BaseLabeledWeightedEdge( "", a, start, 1.5D ) );
graph.addEdge( new BaseLabeledWeightedEdge( "", start, d, 2D ) );
+ graph.addEdge( new BaseLabeledWeightedEdge( "", d, start, 2D ) );
graph.addEdge( new BaseLabeledWeightedEdge( "", a, b, 2D ) );
+ graph.addEdge( new BaseLabeledWeightedEdge( "", b, a, 2D ) );
graph.addEdge( new BaseLabeledWeightedEdge( "", b, c, 3D ) );
+ graph.addEdge( new BaseLabeledWeightedEdge( "", c, b, 3D ) );
graph.addEdge( new BaseLabeledWeightedEdge( "", c, goal, 3D ) );
+ graph.addEdge( new BaseLabeledWeightedEdge( "", goal, c, 3D ) );
graph.addEdge( new BaseLabeledWeightedEdge( "", d, e, 3D ) );
+ graph.addEdge( new BaseLabeledWeightedEdge( "", e, d, 3D ) );
graph.addEdge( new BaseLabeledWeightedEdge( "", e, goal, 2D ) );
+ graph.addEdge( new BaseLabeledWeightedEdge( "", goal, e, 2D ) );
// euristics
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java?rev=1138576&r1=1138575&r2=1138576&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java Wed Jun 22 18:45:14 2011
@@ -68,18 +68,27 @@ public final class VisitTestCase
input.addVertex( y );
input.addEdge( new BaseLabeledEdge( "", s, r ) );
+ input.addEdge( new BaseLabeledEdge( "", r, s ) );
input.addEdge( new BaseLabeledEdge( "", s, w ) );
+ input.addEdge( new BaseLabeledEdge( "", w, s ) );
input.addEdge( new BaseLabeledEdge( "", r, v ) );
+ input.addEdge( new BaseLabeledEdge( "", v, r ) );
input.addEdge( new BaseLabeledEdge( "", w, t ) );
+ input.addEdge( new BaseLabeledEdge( "", t, w ) );
input.addEdge( new BaseLabeledEdge( "", w, x ) );
+ input.addEdge( new BaseLabeledEdge( "", x, w ) );
input.addEdge( new BaseLabeledEdge( "", t, u ) );
+ input.addEdge( new BaseLabeledEdge( "", u, t ) );
input.addEdge( new BaseLabeledEdge( "", t, x ) );
+ input.addEdge( new BaseLabeledEdge( "", x, t ) );
input.addEdge( new BaseLabeledEdge( "", y, u ) );
+ input.addEdge( new BaseLabeledEdge( "", u, y ) );
input.addEdge( new BaseLabeledEdge( "", y, x ) );
+ input.addEdge( new BaseLabeledEdge( "", x, y ) );
// expected graph
@@ -97,7 +106,7 @@ public final class VisitTestCase
expected.addEdge( new BaseLabeledEdge( "", w, t ) );
expected.addEdge( new BaseLabeledEdge( "", w, x ) );
expected.addEdge( new BaseLabeledEdge( "", t, u ) );
- expected.addEdge( new BaseLabeledEdge( "", y, x ) );
+ expected.addEdge( new BaseLabeledEdge( "", x, y ) );
// actual graph
@@ -143,16 +152,24 @@ public final class VisitTestCase
input.addVertex( s );
input.addEdge( new BaseLabeledEdge( "", s, a ) );
+ input.addEdge( new BaseLabeledEdge( "", a, s ) );
input.addEdge( new BaseLabeledEdge( "", s, b ) );
+ input.addEdge( new BaseLabeledEdge( "", b, s ) );
input.addEdge( new BaseLabeledEdge( "", a, c ) );
+ input.addEdge( new BaseLabeledEdge( "", c, a ) );
input.addEdge( new BaseLabeledEdge( "", a, d ) );
+ input.addEdge( new BaseLabeledEdge( "", d, a ) );
input.addEdge( new BaseLabeledEdge( "", b, e ) );
+ input.addEdge( new BaseLabeledEdge( "", e, b ) );
input.addEdge( new BaseLabeledEdge( "", b, f ) );
+ input.addEdge( new BaseLabeledEdge( "", f, b ) );
input.addEdge( new BaseLabeledEdge( "", e, h ) );
+ input.addEdge( new BaseLabeledEdge( "", h, e ) );
input.addEdge( new BaseLabeledEdge( "", e, g ) );
+ input.addEdge( new BaseLabeledEdge( "", g, e ) );
// expected node set