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/26 00:11:38 UTC
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/
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;
}
/**