commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From c.@apache.org
Subject svn commit: r1305162 - in /commons/sandbox/graph/trunk/src: main/java/org/apache/commons/graph/connectivity/ main/java/org/apache/commons/graph/flow/ main/java/org/apache/commons/graph/visit/ test/java/org/apache/commons/graph/visit/
Date Sun, 25 Mar 2012 22:11:38 GMT
Author: cs
Date: Sun Mar 25 22:11:38 2012
New Revision: 1305162

URL: http://svn.apache.org/viewvc?rev=1305162&view=rev
Log:
[SANDBOX-416] used states in graph visits, replacing ambiguous boolean values to determine
when to abort prematurely and/or skip edges/vertices.

Modified:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java
    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/BaseGraphVisitHandler.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/main/java/org/apache/commons/graph/visit/VisitGraphBuilder.java
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java?rev=1305162&r1=1305161&r2=1305162&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java
(original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectivity/ConnectedComponentHandler.java
Sun Mar 25 22:11:38 2012
@@ -24,6 +24,7 @@ import java.util.List;
 
 import org.apache.commons.graph.Graph;
 import org.apache.commons.graph.visit.BaseGraphVisitHandler;
+import org.apache.commons.graph.visit.VisitState;
 
 final class ConnectedComponentHandler<V, E>
     extends BaseGraphVisitHandler<V, E, Graph<V, E>, List<V>>
@@ -42,11 +43,11 @@ final class ConnectedComponentHandler<V,
      * {@inheritDoc}
      */
     @Override
-    public boolean finishVertex( V vertex )
+    public VisitState finishVertex( V vertex )
     {
         untouchedVertices.remove( vertex );
         touchedVertices.add( vertex );
-        return false;
+        return VisitState.CONTINUE;
     }
 
     /**

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=1305162&r1=1305161&r2=1305162&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
Sun Mar 25 22:11:38 2012
@@ -28,6 +28,7 @@ import org.apache.commons.graph.VertexPa
 import org.apache.commons.graph.WeightedPath;
 import org.apache.commons.graph.shortestpath.PredecessorsList;
 import org.apache.commons.graph.visit.BaseGraphVisitHandler;
+import org.apache.commons.graph.visit.VisitState;
 import org.apache.commons.graph.weight.OrderedMonoid;
 
 /**
@@ -140,38 +141,38 @@ class FlowNetworkHandler<V, E, W>
      * {@inheritDoc}
      */
     @Override
-    public boolean discoverEdge( V head, E edge, V tail )
+    public VisitState discoverEdge( V head, E edge, V tail )
     {
         W residualEdgeCapacity = residualEdgeCapacities.get( edge );
         // avoid expanding the edge when it has no residual capacity
         if ( weightOperations.compare( residualEdgeCapacity, weightOperations.identity()
) <= 0 )
         {
-            return false;
+            return VisitState.SKIP;
         }
         predecessors.addPredecessor( tail, head );
-        return true;
+        return VisitState.CONTINUE;
     }
 
     /**
      * {@inheritDoc}
      */
-    public boolean discoverVertex( V vertex )
+    public VisitState discoverVertex( V vertex )
     {
-        return !vertex.equals( target );
+        return !vertex.equals( target ) ? VisitState.CONTINUE : VisitState.SKIP;
     }
 
     /**
      * {@inheritDoc}
      */
-    public boolean finishVertex( V vertex )
+    public VisitState finishVertex( V vertex )
     {
         if ( vertex.equals( target ) )
         {
             // search ends when target vertex is reached
             foundAugmentingPath = true;
-            return true;
+            return VisitState.ABORT;
         }
-        return false;
+        return VisitState.CONTINUE;
     }
 
     @Override

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/BaseGraphVisitHandler.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/BaseGraphVisitHandler.java?rev=1305162&r1=1305161&r2=1305162&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/BaseGraphVisitHandler.java
(original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/BaseGraphVisitHandler.java
Sun Mar 25 22:11:38 2012
@@ -42,37 +42,37 @@ public class BaseGraphVisitHandler<V, E,
     /**
      * {@inheritDoc}
      */
-    public boolean discoverVertex( V vertex )
+    public VisitState discoverVertex( V vertex )
     {
         // do nothing
-        return true;
+        return VisitState.CONTINUE;
     }
 
     /**
      * {@inheritDoc}
      */
-    public boolean discoverEdge( V head, E edge, V tail )
+    public VisitState discoverEdge( V head, E edge, V tail )
     {
         // do nothing
-        return true;
+        return VisitState.CONTINUE;
     }
 
     /**
      * {@inheritDoc}
      */
-    public boolean finishEdge( V head, E edge, V tail )
+    public VisitState finishEdge( V head, E edge, V tail )
     {
         // do nothing
-        return false;
+        return VisitState.CONTINUE;
     }
 
     /**
      * {@inheritDoc}
      */
-    public boolean finishVertex( V vertex )
+    public VisitState finishVertex( V vertex )
     {
         // do nothing
-        return false;
+        return VisitState.CONTINUE;
     }
 
     /**

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=1305162&r1=1305161&r2=1305162&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
Sun Mar 25 22:11:38 2012
@@ -141,12 +141,12 @@ final class DefaultVisitAlgorithmsSelect
                 }
                 else
                 {
-                    if ( !handler.discoverEdge( prevHead, e, v ) )
+                    if ( handler.discoverEdge( prevHead, e, v ) == VisitState.SKIP )
                     {
                         skipVertex = true;
                     }
 
-                    if ( handler.finishEdge( prevHead, e, v ) )
+                    if ( handler.finishEdge( prevHead, e, v ) == VisitState.ABORT )
                     {
                         skipVertex = true;
                         visitingGraph = false;
@@ -161,7 +161,7 @@ final class DefaultVisitAlgorithmsSelect
                 visitedVertices.add( v );
             }
 
-            if ( !skipVertex && handler.discoverVertex( v ) )
+            if ( !skipVertex && handler.discoverVertex( v ) == VisitState.CONTINUE
)
             {
                 Iterator<V> connected = ( graph instanceof DirectedGraph ) ?
                         ( (DirectedGraph<V, E>) graph ).getOutbound( v ).iterator()
:
@@ -177,7 +177,7 @@ final class DefaultVisitAlgorithmsSelect
                 }
             }
 
-            if ( !skipVertex && handler.finishVertex( v ) )
+            if ( !skipVertex && 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=1305162&r1=1305161&r2=1305162&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
Sun Mar 25 22:11:38 2012
@@ -36,30 +36,30 @@ public interface GraphVisitHandler<V, E,
     /**
      * Performs operations on the input {@link Vertex} and checks if it should be expanded
      * in the search algorithm.
-     * @return true if the input {@link Vertex} should be expanded, false otherwise
+     * @return {@link VisitState.CONTINUE} if the input {@link Vertex} should be expanded,
{@link VisitState.SKIP} otherwise
      */
-    boolean discoverVertex( V vertex );
+    VisitState discoverVertex( V vertex );
 
     /**
      * Performs operations on the input {@link Edge} and checks if it should be expanded
      * in the search algorithm.
-     * @return true if the input {@link Edge} should be expanded, false otherwise
+     * @return {@link VisitState.CONTINUE} if the input {@link Edge} should be expanded,
{@link VisitState.SKIP} otherwise
      */
-    boolean discoverEdge( V head, E edge, V tail );
+    VisitState discoverEdge( V head, E edge, V tail );
 
     /**
      * Checks if the search algorithm should be terminated. Called after the search algorithm
has finished
      * visiting the input {@link Edge}.
-     * @return true if the search algorithm should be terminated after visiting the input
{@link Edge}, false otherwise
+     * @return {@link VisitState.ABORT} if the search algorithm should be terminated after
visiting the input {@link Edge}, {@link VisitState.CONTINUE} otherwise
      */
-    boolean finishEdge( V head, E edge, V tail );
+    VisitState finishEdge( V head, E edge, V tail );
 
     /**
      * Checks if the search algorithm should be terminated. Called after the search algorithm
has finished
      * visiting the input {@link Vertex}.
-     * @return true if the search algorithm should be terminated after visiting the input
{@link Vertex}, false otherwise
+     * @return {@link VisitState.ABORT} if the search algorithm should be terminated after
visiting the input {@link Vertex}, {@link VisitState.CONTINUE} otherwise
      */
-    boolean finishVertex( V vertex );
+    VisitState finishVertex( V vertex );
 
     /**
      * Called upon termination of the search algorithm.

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/VisitGraphBuilder.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/VisitGraphBuilder.java?rev=1305162&r1=1305161&r2=1305162&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/VisitGraphBuilder.java
(original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/VisitGraphBuilder.java
Sun Mar 25 22:11:38 2012
@@ -62,10 +62,10 @@ final class VisitGraphBuilder<V, E, G ex
      * {@inheritDoc}
      */
     @Override
-    public boolean discoverEdge( V head, E edge, V tail )
+    public VisitState discoverEdge( V head, E edge, V tail )
     {
         visitGraph.addEdge( head, edge, tail );
-        return true;
+        return VisitState.CONTINUE;
     }
 
     /**

Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java?rev=1305162&r1=1305161&r2=1305162&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java
(original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/NodeSequenceVisitor.java
Sun Mar 25 22:11:38 2012
@@ -38,10 +38,10 @@ public final class NodeSequenceVisitor
      * {@inheritDoc}
      */
     @Override
-    public boolean discoverVertex( BaseLabeledVertex vertex )
+    public VisitState discoverVertex( BaseLabeledVertex vertex )
     {
         vertices.add( vertex );
-        return true;
+        return VisitState.CONTINUE;
     }
 
     /**



Mime
View raw message