You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by cs...@apache.org on 2012/03/27 22:51:48 UTC
svn commit: r1306016 - in /commons/sandbox/graph/trunk/src:
main/java/org/apache/commons/graph/flow/
main/java/org/apache/commons/graph/visit/
test/java/org/apache/commons/graph/flow/
Author: cs
Date: Tue Mar 27 20:51:48 2012
New Revision: 1306016
URL: http://svn.apache.org/viewvc?rev=1306016&view=rev
Log:
in search/visit algorithms, added support for VisitState.ABORT also when discovering edges/vertices for the first time
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/GraphVisitHandler.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java?rev=1306016&r1=1306015&r2=1306016&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java Tue Mar 27 20:51:48 2012
@@ -162,7 +162,7 @@ class FlowNetworkHandler<V, E, W>
*/
public VisitState discoverVertex( V vertex )
{
- return !vertex.equals( target ) ? CONTINUE : SKIP;
+ return finishVertex( vertex );
}
/**
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java?rev=1306016&r1=1306015&r2=1306016&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java Tue Mar 27 20:51:48 2012
@@ -32,7 +32,7 @@ import org.apache.commons.graph.VertexPa
/**
* {@link VisitAlgorithmsSelector} implementation.
- *
+ *
* @param <V> the Graph vertices type
* @param <E> the Graph edges type
* @param <G> the Graph type
@@ -48,9 +48,8 @@ final class DefaultVisitAlgorithmsSelect
private final V source;
/**
- * Create a default {@link VisitAlgorithmsSelector} for the given {@link Graph} and
- * start {@link Vertex}.
- *
+ * Create a default {@link VisitAlgorithmsSelector} for the given {@link Graph} and start {@link Vertex}.
+ *
* @param graph the {@link Graph} to be used.
* @param source the start {@link Vertex}.
*/
@@ -93,15 +92,13 @@ final class DefaultVisitAlgorithmsSelect
}
/**
- * A generalized graph search algorithm to be used to implement depth-first and
- * breadth-first searches. Depending on the used collection, the algorithm traverses
- * the graph in a different way:
- *
+ * A generalized graph search algorithm to be used to implement depth-first and breadth-first searches. Depending on
+ * the used collection, the algorithm traverses the graph in a different way:
* <ul>
- * <li>Queue (FIFO): breadth-first</li>
- * <li>Stack (LIFO): depth-first</li>
+ * <li>Queue (FIFO): breadth-first</li>
+ * <li>Stack (LIFO): depth-first</li>
* </ul>
- *
+ *
* @param handler the handler intercepts visits
* @param enqueue defines the collection behavior used to traverse the graph: true is a Queue, false is a Stack
* @return the result of {@link GraphVisitHandler#onCompleted()}
@@ -141,9 +138,14 @@ final class DefaultVisitAlgorithmsSelect
}
else
{
- if ( handler.discoverEdge( prevHead, e, v ) == VisitState.SKIP )
+ VisitState stateAfterEdgeDiscovery = handler.discoverEdge( prevHead, e, v );
+ if ( stateAfterEdgeDiscovery != VisitState.CONTINUE )
{
skipVertex = true;
+ if ( stateAfterEdgeDiscovery == VisitState.ABORT )
+ {
+ visitingGraph = false;
+ }
}
if ( handler.finishEdge( prevHead, e, v ) == VisitState.ABORT )
@@ -156,16 +158,27 @@ final class DefaultVisitAlgorithmsSelect
// only mark the current vertex as visited, if the
// edge leading to it should be expanded
+ boolean vertexWasDiscovered = false;
if ( !skipVertex )
{
visitedVertices.add( v );
+ VisitState stateAfterVertexDiscovery = handler.discoverVertex( v );
+ vertexWasDiscovered = true;
+ if ( stateAfterVertexDiscovery != VisitState.CONTINUE )
+ {
+ skipVertex = true;
+ if ( stateAfterVertexDiscovery == VisitState.ABORT )
+ {
+ visitingGraph = false;
+ }
+ }
}
- if ( !skipVertex && handler.discoverVertex( v ) == VisitState.CONTINUE )
+ if ( !skipVertex )
{
- Iterator<V> connected = ( graph instanceof DirectedGraph ) ?
- ( (DirectedGraph<V, E>) graph ).getOutbound( v ).iterator() :
- graph.getConnectedVertices( v ).iterator();
+ Iterator<V> connected =
+ ( graph instanceof DirectedGraph ) ? ( (DirectedGraph<V, E>) graph ).getOutbound( v ).iterator()
+ : graph.getConnectedVertices( v ).iterator();
while ( connected.hasNext() )
{
@@ -177,7 +190,7 @@ final class DefaultVisitAlgorithmsSelect
}
}
- if ( !skipVertex && handler.finishVertex( v ) == VisitState.ABORT )
+ if ( vertexWasDiscovered && handler.finishVertex( v ) == VisitState.ABORT )
{
visitingGraph = false;
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/GraphVisitHandler.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/GraphVisitHandler.java?rev=1306016&r1=1306015&r2=1306016&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/GraphVisitHandler.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/GraphVisitHandler.java Tue Mar 27 20:51:48 2012
@@ -34,16 +34,26 @@ public interface GraphVisitHandler<V, E,
void discoverGraph( G graph );
/**
- * Performs operations on the input {@link Vertex} and checks if it should be expanded
- * in the search algorithm.
- * @return {@link VisitState.CONTINUE} if the input {@link Vertex} should be expanded, {@link VisitState.SKIP} otherwise
+ * Performs operations on the input {@link Vertex} and determines the behavior of the visit algorithm
+ * based on the return value:
+ * <ul>
+ * <li>{@link VisitState.CONTINUE} continues the visit normally;</li>
+ * <li>{@link VisitState.SKIP} continues the visit skipping the input {@link Vertex};</li>
+ * <li>{@link VisitState.ABORT} terminates the visit.</li>
+ * </ul>
+ * @return the state of the visit after operations on the vertex
*/
VisitState discoverVertex( V vertex );
/**
- * Performs operations on the input {@link Edge} and checks if it should be expanded
- * in the search algorithm.
- * @return {@link VisitState.CONTINUE} if the input {@link Edge} should be expanded, {@link VisitState.SKIP} otherwise
+ * Performs operations on the input {@link Edge} and determines the behavior of the visit algorithm
+ * based on the return value:
+ * <ul>
+ * <li>{@link VisitState.CONTINUE} continues the visit normally;</li>
+ * <li>{@link VisitState.SKIP} continues the visit skipping the input {@link Edge};</li>
+ * <li>{@link VisitState.ABORT} terminates the visit.</li>
+ * </ul>
+ * @return the state of the visit after operations on the edge
*/
VisitState discoverEdge( V head, E edge, V tail );
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java?rev=1306016&r1=1306015&r2=1306016&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java Tue Mar 27 20:51:48 2012
@@ -155,7 +155,7 @@ public class EdmondsKarpTestCase
.to( g )
.applyingEdmondsKarp( new IntegerWeightBaseOperations() );
- assertEquals( actual, expected );
+ assertEquals( expected, actual );
}
}
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java?rev=1306016&r1=1306015&r2=1306016&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java Tue Mar 27 20:51:48 2012
@@ -184,7 +184,7 @@ public final class FordFulkersonTestCase
.to( d )
.applyingFordFulkerson( new IntegerWeightBaseOperations() );
- assertEquals( actual, expected );
+ assertEquals( expected, actual );
}
}