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 2012/01/20 21:20:55 UTC
svn commit: r1234109 - in /commons/sandbox/graph/trunk/src: changes/
main/java/org/apache/commons/graph/scc/
main/java/org/apache/commons/graph/visit/
test/java/org/apache/commons/graph/visit/
Author: simonetripodi
Date: Fri Jan 20 20:20:54 2012
New Revision: 1234109
URL: http://svn.apache.org/viewvc?rev=1234109&view=rev
Log:
[SANDBOX-358] Early return/termination for graph visit - patch submitted by Claudio Squarcella
Modified:
commons/sandbox/graph/trunk/src/changes/changes.xml
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowVisitHandler.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/KosarajuSharirVisitHandler.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/GraphVisitHandler.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/Visit.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/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/changes/changes.xml?rev=1234109&r1=1234108&r2=1234109&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/changes/changes.xml (original)
+++ commons/sandbox/graph/trunk/src/changes/changes.xml Fri Jan 20 20:20:54 2012
@@ -26,6 +26,9 @@
<action dev="simonetripodi" type="update" issue="SANDBOX-361">
Add fluent APIs to build mutable Graphes
</action>
+ <action dev="simonetripodi" type="update" issue="SANDBOX-358" due-to="Claudio Squarcella">
+ Early return/termination for graph visit.
+ </action>
<action dev="simonetripodi" type="update" issue="SANDBOX-356" due-to="Claudio Squarcella">
Generic weight types and algorithms implementations based on wighted graphes.
</action>
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowVisitHandler.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowVisitHandler.java?rev=1234109&r1=1234108&r2=1234109&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowVisitHandler.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowVisitHandler.java Fri Jan 20 20:20:54 2012
@@ -68,18 +68,19 @@ final class CheriyanMehlhornGabowVisitHa
* {@inheritDoc}
*/
@Override
- public void discoverVertex( V vertex )
+ public boolean discoverVertex( V vertex )
{
marked.add( vertex );
preorder.put( vertex, preorderCounter++ );
s.push( vertex );
p.push( vertex );
+ return true;
}
/**
* {@inheritDoc}
*/
- public void discoverEdge( V head, E edge, V tail )
+ public boolean discoverEdge( V head, E edge, V tail )
{
if ( !marked.contains( tail ) )
{
@@ -106,6 +107,8 @@ final class CheriyanMehlhornGabowVisitHa
while ( !head.equals( w ) );
sscCounter++;
}
+
+ return true;
}
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/KosarajuSharirVisitHandler.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/KosarajuSharirVisitHandler.java?rev=1234109&r1=1234108&r2=1234109&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/KosarajuSharirVisitHandler.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/KosarajuSharirVisitHandler.java Fri Jan 20 20:20:54 2012
@@ -49,12 +49,13 @@ final class KosarajuSharirVisitHandler<V
/**
* {@inheritDoc}
*/
- public void finishVertex( V vertex )
+ public boolean finishVertex( V vertex )
{
if ( !startVisit.equals( vertex ) )
{
vertices.add( vertex );
}
+ return false;
}
@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=1234109&r1=1234108&r2=1234109&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 Fri Jan 20 20:20:54 2012
@@ -44,33 +44,37 @@ public class BaseGraphVisitHandler<V ext
/**
* {@inheritDoc}
*/
- public void discoverVertex( V vertex )
+ public boolean discoverVertex( V vertex )
{
// do nothing
+ return true;
}
/**
* {@inheritDoc}
*/
- public void discoverEdge( V head, E edge, V tail )
+ public boolean discoverEdge( V head, E edge, V tail )
{
// do nothing
+ return true;
}
/**
* {@inheritDoc}
*/
- public void finishEdge( V head, E edge, V tail )
+ public boolean finishEdge( V head, E edge, V tail )
{
// do nothing
+ return false;
}
/**
* {@inheritDoc}
*/
- public void finishVertex( V vertex )
+ public boolean finishVertex( V vertex )
{
// do nothing
+ return 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=1234109&r1=1234108&r2=1234109&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 Fri Jan 20 20:20:54 2012
@@ -24,38 +24,47 @@ import org.apache.commons.graph.Graph;
import org.apache.commons.graph.Vertex;
/**
- * Description of the Interface
+ * A {@link GraphVisitHandler} controls the execution of breadth-first and depth-first search
+ * algorithms in {@link Visit}.
*/
public interface GraphVisitHandler<V extends Vertex, E extends Edge>
{
/**
- * Description of the Method
+ * Called at the beginning of breadth-first and depth-first search.
*/
void discoverGraph( Graph<V, E> graph );
/**
- * Description of the Method
+ * 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
*/
- void discoverVertex( V vertex );
+ boolean discoverVertex( V vertex );
/**
- * Description of the Method
+ * 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
*/
- void discoverEdge( V head, E edge, V tail );
+ boolean discoverEdge( V head, E edge, V tail );
/**
- * Description of the Method
+ * 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
*/
- void finishEdge( V head, E edge, V tail );
+ boolean finishEdge( V head, E edge, V tail );
/**
- * Description of the Method
+ * 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
*/
- void finishVertex( V vertex );
+ boolean finishVertex( V vertex );
/**
- * Description of the Method
+ * Called upon termination of the search algorithm.
*/
void finishGraph( Graph<V, E> graph );
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=1234109&r1=1234108&r2=1234109&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 Fri Jan 20 20:20:54 2012
@@ -20,6 +20,7 @@ package org.apache.commons.graph.visit;
*/
import java.util.HashSet;
+import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
@@ -82,32 +83,45 @@ public final class Visit
Queue<V> vertexQueue = new LinkedList<V>();
vertexQueue.add( source );
- Set<V> visitedVetices = new HashSet<V>();
- visitedVetices.add( source );
+ Set<V> visitedVertices = new HashSet<V>();
+ visitedVertices.add( source );
- while ( !vertexQueue.isEmpty() )
+ boolean visitingGraph = true;
+
+ while ( visitingGraph && !vertexQueue.isEmpty() )
{
V v = vertexQueue.remove();
- handler.discoverVertex( v );
-
- Iterable<V> connected = ( graph instanceof DirectedGraph ) ? ( (DirectedGraph<V, E>) graph ).getOutbound( v )
- : graph.getConnectedVertices( v );
- for ( V w : connected )
- {
- if ( visitedVetices.add( w ) )
+ if ( handler.discoverVertex( v ) ) {
+
+ Iterator<V> connected = ( graph instanceof DirectedGraph ) ? ( (DirectedGraph<V, E>) graph ).getOutbound( v ).iterator()
+ : graph.getConnectedVertices( v ).iterator();
+
+ while ( connected.hasNext() )
{
- E e = graph.getEdge( v, w );
-
- handler.discoverEdge( v, e, w );
-
- vertexQueue.offer( w );
-
- handler.finishEdge( v, e, w );
+ V w = connected.next();
+ if ( visitedVertices.add( w ) )
+ {
+ E e = graph.getEdge( v, w );
+
+ if ( handler.discoverEdge( v, e, w ) )
+ {
+ vertexQueue.offer( w );
+ }
+
+ if ( handler.finishEdge( v, e, w ) )
+ {
+ visitingGraph = false;
+ }
+ }
}
+
}
- handler.finishVertex( v );
+ if ( handler.finishVertex( v ) )
+ {
+ visitingGraph = false;
+ }
}
handler.finishGraph( graph );
@@ -159,32 +173,43 @@ public final class Visit
Stack<V> vertexStack = new Stack<V>();
vertexStack.push( source );
- Set<V> visitedVetices = new HashSet<V>();
- visitedVetices.add( source );
+ Set<V> visitedVertices = new HashSet<V>();
+ visitedVertices.add( source );
- while ( !vertexStack.isEmpty() )
+ boolean visitingGraph = true;
+
+ while ( visitingGraph && !vertexStack.isEmpty() )
{
V v = vertexStack.pop();
- handler.discoverVertex( v );
-
- Iterable<V> connected = ( graph instanceof DirectedGraph ) ? ( (DirectedGraph<V, E>) graph ).getOutbound( v )
- : graph.getConnectedVertices( v );
- for ( V w : connected )
+ if ( handler.discoverVertex( v ) )
{
- if ( visitedVetices.add( w ) )
+ Iterator<V> connected = ( graph instanceof DirectedGraph ) ? ( (DirectedGraph<V, E>) graph ).getOutbound( v ).iterator()
+ : graph.getConnectedVertices( v ).iterator();
+
+ while ( connected.hasNext() )
{
- E e = graph.getEdge( v, w );
-
- handler.discoverEdge( v, e, w );
-
- vertexStack.push( w );
-
- handler.finishEdge( v, e, w );
+ V w = connected.next();
+ if ( visitedVertices.add( w ) )
+ {
+ E e = graph.getEdge( v, w );
+
+ if ( handler.discoverEdge( v, e, w ) )
+ {
+ vertexStack.push( w );
+ }
+
+ if ( handler.finishEdge( v, e, w ) ) {
+ visitingGraph = false;
+ }
+ }
}
}
- handler.finishVertex( v );
+ if ( handler.finishVertex( v ) )
+ {
+ visitingGraph = false;
+ }
}
handler.finishGraph( graph );
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=1234109&r1=1234108&r2=1234109&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 Fri Jan 20 20:20:54 2012
@@ -64,9 +64,10 @@ final class VisitGraphBuilder<V extends
* {@inheritDoc}
*/
@Override
- public void discoverEdge( V head, E edge, V tail )
+ public boolean discoverEdge( V head, E edge, V tail )
{
visitGraph.addEdge( head, edge, tail );
+ return true;
}
/**
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=1234109&r1=1234108&r2=1234109&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 Fri Jan 20 20:20:54 2012
@@ -37,9 +37,10 @@ public final class NodeSequenceVisitor<V
* {@inheritDoc}
*/
@Override
- public void discoverVertex( V vertex )
+ public boolean discoverVertex( V vertex )
{
vertices.add( vertex );
+ return true;
}
/**