commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From c.@apache.org
Subject 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/
Date Tue, 27 Mar 2012 20:51:48 GMT
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 );
     }
 
 }



Mime
View raw message