Return-Path: X-Original-To: apmail-commons-commits-archive@minotaur.apache.org Delivered-To: apmail-commons-commits-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 0069298C1 for ; Mon, 30 Jan 2012 13:04:01 +0000 (UTC) Received: (qmail 15495 invoked by uid 500); 30 Jan 2012 13:04:00 -0000 Delivered-To: apmail-commons-commits-archive@commons.apache.org Received: (qmail 15431 invoked by uid 500); 30 Jan 2012 13:03:59 -0000 Mailing-List: contact commits-help@commons.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@commons.apache.org Delivered-To: mailing list commits@commons.apache.org Received: (qmail 15422 invoked by uid 99); 30 Jan 2012 13:03:59 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 30 Jan 2012 13:03:59 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 30 Jan 2012 13:03:54 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id 196EC23888E7 for ; Mon, 30 Jan 2012 13:03:33 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1237632 - in /commons/sandbox/graph/trunk/src: changes/ main/java/org/apache/commons/graph/flow/ main/java/org/apache/commons/graph/scc/ main/java/org/apache/commons/graph/visit/ test/java/org/apache/commons/graph/visit/ Date: Mon, 30 Jan 2012 13:03:32 -0000 To: commits@commons.apache.org From: simonetripodi@apache.org X-Mailer: svnmailer-1.0.8-patched Message-Id: <20120130130333.196EC23888E7@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org Author: simonetripodi Date: Mon Jan 30 13:03:31 2012 New Revision: 1237632 URL: http://svn.apache.org/viewvc?rev=1237632&view=rev Log: [SANDBOX-372] Make the org.apache.commons.graph.visit.GraphVisitHandler able to return objects Modified: commons/sandbox/graph/trunk/src/changes/changes.xml commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.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/scc/CheriyanMehlhornGabowVisitHandler.java commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.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/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/VisitAlgorithmsSelector.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 commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/VisitTestCase.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=1237632&r1=1237631&r2=1237632&view=diff ============================================================================== --- commons/sandbox/graph/trunk/src/changes/changes.xml (original) +++ commons/sandbox/graph/trunk/src/changes/changes.xml Mon Jan 30 13:03:31 2012 @@ -23,6 +23,9 @@ + + Make the org.apache.commons.graph.visit.GraphVisitHandler able to return objects + GraphML format exporter Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java?rev=1237632&r1=1237631&r2=1237632&view=diff ============================================================================== --- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java (original) +++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java Mon Jan 30 13:03:31 2012 @@ -95,8 +95,7 @@ final class DefaultMaxFlowAlgorithmSelec } ); // create flow network handler - FlowNetworkHandler, W> flowNetworkHandler = - new FlowNetworkHandler, W>( flowNetwork, source, target, monoid ); + FlowNetworkHandler flowNetworkHandler = new FlowNetworkHandler( flowNetwork, source, target, monoid ); // perform depth first search visit( flowNetwork ).from( source ).applyingDepthFirstSearch( flowNetworkHandler ); @@ -109,7 +108,7 @@ final class DefaultMaxFlowAlgorithmSelec visit( flowNetwork ).from( source ).applyingDepthFirstSearch( flowNetworkHandler ); } - return flowNetworkHandler.getMaxFlow(); + return flowNetworkHandler.onCompleted(); } /** 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=1237632&r1=1237631&r2=1237632&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 Mon Jan 30 13:03:31 2012 @@ -23,7 +23,6 @@ import java.util.HashMap; import java.util.Map; import org.apache.commons.graph.DirectedGraph; -import org.apache.commons.graph.Graph; import org.apache.commons.graph.Vertex; import org.apache.commons.graph.VertexPair; import org.apache.commons.graph.WeightedEdge; @@ -40,11 +39,11 @@ import org.apache.commons.graph.weight.O * @param the weighted edge type * @param the weight type */ -class FlowNetworkHandler, W> - extends BaseGraphVisitHandler +class FlowNetworkHandler + extends BaseGraphVisitHandler, DirectedGraph>, W> { - private final DirectedGraph flowNetwork; + private final DirectedGraph> flowNetwork; private final V source; @@ -54,14 +53,14 @@ class FlowNetworkHandler residualEdgeCapacities = new HashMap(); + private final Map, W> residualEdgeCapacities = new HashMap, W>(); // these are new for each new visit of the graph - private PredecessorsList predecessors; + private PredecessorsList, W> predecessors; private boolean foundAugmentingPath; - FlowNetworkHandler( DirectedGraph flowNetwork, V source, V target, OrderedMonoid orderedMonoid ) + FlowNetworkHandler( DirectedGraph> flowNetwork, V source, V target, OrderedMonoid orderedMonoid ) { this.flowNetwork = flowNetwork; this.source = source; @@ -70,7 +69,7 @@ class FlowNetworkHandler edge : flowNetwork.getEdges() ) { residualEdgeCapacities.put( edge, edge.getWeight() ); } @@ -95,11 +94,11 @@ class FlowNetworkHandler augmentingPath = predecessors.buildPath( source, target ); + WeightedPath, W> augmentingPath = predecessors.buildPath( source, target ); // find flow increment W flowIncrement = null; - for ( WE edge : augmentingPath.getEdges() ) + for ( WeightedEdge edge : augmentingPath.getEdges() ) { W edgeCapacity = residualEdgeCapacities.get( edge ); if ( flowIncrement == null @@ -111,7 +110,7 @@ class FlowNetworkHandler edge : augmentingPath.getEdges() ) { // decrease capacity for direct edge W directCapacity = residualEdgeCapacities.get( edge ); @@ -119,29 +118,20 @@ class FlowNetworkHandler vertexPair = flowNetwork.getVertices( edge ); - WE inverseEdge = flowNetwork.getEdge( vertexPair.getTail(), vertexPair.getHead() ); + WeightedEdge inverseEdge = flowNetwork.getEdge( vertexPair.getTail(), vertexPair.getHead() ); W inverseCapacity = residualEdgeCapacities.get( inverseEdge ); residualEdgeCapacities.put( inverseEdge, orderedMonoid.append( inverseCapacity, flowIncrement ) ); } } /** - * Returns the maximum flow through the input graph. - * @return the maximum flow through the input graph - */ - W getMaxFlow() - { - return maxFlow; - } - - /** * {@inheritDoc} */ @Override - public void discoverGraph( Graph graph ) + public void discoverGraph( DirectedGraph> graph ) { // reset ausiliary structures for a new graph visit - predecessors = new PredecessorsList( graph, orderedMonoid ); + predecessors = new PredecessorsList, W>( graph, orderedMonoid ); foundAugmentingPath = false; } @@ -149,7 +139,7 @@ class FlowNetworkHandler edge, V tail ) { W residualEdgeCapacity = residualEdgeCapacities.get( edge ); // avoid expanding the edge when it has no residual capacity @@ -165,7 +155,7 @@ class FlowNetworkHandler edge, V tail ) { if ( tail.equals( target ) ) { @@ -176,4 +166,10 @@ class FlowNetworkHandler the Graph vertices type. * @param the Graph edges type. */ -final class CheriyanMehlhornGabowVisitHandler - extends BaseGraphVisitHandler +final class CheriyanMehlhornGabowVisitHandler> + extends BaseGraphVisitHandler { - private final DirectedGraph graph; + private final G graph; private final Map preorder = new HashMap(); @@ -58,7 +58,7 @@ final class CheriyanMehlhornGabowVisitHa private int sscCounter = 0; - public CheriyanMehlhornGabowVisitHandler( DirectedGraph graph, Set marked ) + public CheriyanMehlhornGabowVisitHandler( G graph, Set marked ) { this.graph = graph; this.marked = marked; Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java?rev=1237632&r1=1237631&r2=1237632&view=diff ============================================================================== --- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java (original) +++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java Mon Jan 30 13:03:31 2012 @@ -61,7 +61,7 @@ public final class DefaultSccAlgorithmSe { source = checkNotNull( source, "KosarajuSharir algorithm requires a non-null source vertex" ); - visit( graph ).from( source ).applyingDepthFirstSearch( new KosarajuSharirVisitHandler( source ) ); + visit( graph ).from( source ).applyingDepthFirstSearch( new KosarajuSharirVisitHandler( source ) ); DirectedGraph reverted = new RevertedGraph( graph ); @@ -77,7 +77,7 @@ public final class DefaultSccAlgorithmSe { final Set marked = new HashSet(); - final GraphVisitHandler visitHandler = new CheriyanMehlhornGabowVisitHandler( graph, marked ); + final GraphVisitHandler visitHandler = new CheriyanMehlhornGabowVisitHandler( graph, marked ); for ( V vertex : graph.getVertices() ) { 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=1237632&r1=1237631&r2=1237632&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 Mon Jan 30 13:03:31 2012 @@ -21,8 +21,8 @@ package org.apache.commons.graph.scc; import java.util.LinkedList; +import org.apache.commons.graph.DirectedGraph; import org.apache.commons.graph.Edge; -import org.apache.commons.graph.Graph; import org.apache.commons.graph.Vertex; import org.apache.commons.graph.visit.BaseGraphVisitHandler; @@ -33,8 +33,8 @@ import org.apache.commons.graph.visit.Ba * @param the Graph vertices type. * @param the Graph edges type. */ -final class KosarajuSharirVisitHandler - extends BaseGraphVisitHandler +final class KosarajuSharirVisitHandler> + extends BaseGraphVisitHandler { final V startVisit; @@ -59,7 +59,7 @@ final class KosarajuSharirVisitHandler graph ) + public void finishGraph( G graph ) { vertices.add( startVisit ); 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=1237632&r1=1237631&r2=1237632&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 Mon Jan 30 13:03:31 2012 @@ -29,14 +29,14 @@ import org.apache.commons.graph.Vertex; * @param the Graph vertices type * @param the Graph edges type */ -public class BaseGraphVisitHandler - implements GraphVisitHandler +public class BaseGraphVisitHandler, O> + implements GraphVisitHandler { /** * {@inheritDoc} */ - public void discoverGraph( Graph graph ) + public void discoverGraph( G graph ) { // do nothing } @@ -80,9 +80,17 @@ public class BaseGraphVisitHandler graph ) + public void finishGraph( G graph ) { // do nothing } + /** + * {@inheritDoc} + */ + public O onCompleted() + { + return null; + } + } 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=1237632&r1=1237631&r2=1237632&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 Mon Jan 30 13:03:31 2012 @@ -59,9 +59,7 @@ final class DefaultVisitAlgorithmsSelect */ public Graph applyingBreadthFirstSearch() { - VisitGraphBuilder visitGraphBuilder = new VisitGraphBuilder(); - applyingBreadthFirstSearch( visitGraphBuilder ); - return visitGraphBuilder.getVisitGraph(); + return applyingBreadthFirstSearch( new VisitGraphBuilder() ); } /** @@ -69,15 +67,13 @@ final class DefaultVisitAlgorithmsSelect */ public Graph applyingDepthFirstSearch() { - VisitGraphBuilder visitGraphBuilder = new VisitGraphBuilder(); - applyingDepthFirstSearch( visitGraphBuilder ); - return visitGraphBuilder.getVisitGraph(); + return applyingDepthFirstSearch( new VisitGraphBuilder() ); } /** * {@inheritDoc} */ - public void applyingBreadthFirstSearch( GraphVisitHandler handler ) + public O applyingBreadthFirstSearch( GraphVisitHandler handler ) { handler = checkNotNull( handler, "Graph visitor handler can not be null." ); @@ -128,12 +124,14 @@ final class DefaultVisitAlgorithmsSelect } handler.finishGraph( graph ); + + return handler.onCompleted(); } /** * {@inheritDoc} */ - public void applyingDepthFirstSearch( GraphVisitHandler handler ) + public O applyingDepthFirstSearch( GraphVisitHandler handler ) { handler = checkNotNull( handler, "Graph visitor handler can not be null." ); @@ -182,6 +180,8 @@ final class DefaultVisitAlgorithmsSelect } handler.finishGraph( graph ); + + return handler.onCompleted(); } } 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=1237632&r1=1237631&r2=1237632&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 Mon Jan 30 13:03:31 2012 @@ -27,13 +27,13 @@ import org.apache.commons.graph.Vertex; * A {@link GraphVisitHandler} controls the execution of breadth-first and depth-first search * algorithms in {@link Visit}. */ -public interface GraphVisitHandler +public interface GraphVisitHandler, O> { /** * Called at the beginning of breadth-first and depth-first search. */ - void discoverGraph( Graph graph ); + void discoverGraph( G graph ); /** * Performs operations on the input {@link Vertex} and checks if it should be expanded @@ -66,6 +66,13 @@ public interface GraphVisitHandler graph ); + void finishGraph( G graph ); + + /** + * Invoked once the visit is finished. + * + * @return Value that will be returned by the visit + */ + O onCompleted(); } Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/VisitAlgorithmsSelector.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/VisitAlgorithmsSelector.java?rev=1237632&r1=1237631&r2=1237632&view=diff ============================================================================== --- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/VisitAlgorithmsSelector.java (original) +++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/VisitAlgorithmsSelector.java Mon Jan 30 13:03:31 2012 @@ -52,13 +52,13 @@ public interface VisitAlgorithmsSelector * * @param handler the handler intercepts visit actions */ - void applyingBreadthFirstSearch( GraphVisitHandler handler ); + O applyingBreadthFirstSearch( GraphVisitHandler handler ); /** * Depth-first search algorithm implementation. * * @param handler the handler intercepts visit actions */ - void applyingDepthFirstSearch( GraphVisitHandler handler ); + O applyingDepthFirstSearch( GraphVisitHandler handler ); } 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=1237632&r1=1237631&r2=1237632&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 Mon Jan 30 13:03:31 2012 @@ -33,8 +33,8 @@ import org.apache.commons.graph.model.Un * @param the Graph vertices type. * @param the Graph edges type. */ -final class VisitGraphBuilder - extends BaseGraphVisitHandler +final class VisitGraphBuilder> + extends BaseGraphVisitHandler> { private BaseMutableGraph visitGraph; @@ -43,7 +43,7 @@ final class VisitGraphBuilder graph ) + public void discoverGraph( G graph ) { if ( graph instanceof DirectedGraph ) { @@ -71,11 +71,10 @@ final class VisitGraphBuilder getVisitGraph() + @Override + public Graph onCompleted() { return visitGraph; } 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=1237632&r1=1237631&r2=1237632&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 Mon Jan 30 13:03:31 2012 @@ -24,31 +24,31 @@ import static java.util.Collections.unmo import java.util.ArrayList; import java.util.List; -import org.apache.commons.graph.Edge; -import org.apache.commons.graph.Vertex; +import org.apache.commons.graph.model.BaseLabeledEdge; +import org.apache.commons.graph.model.BaseLabeledVertex; +import org.apache.commons.graph.model.UndirectedMutableGraph; -public final class NodeSequenceVisitor - extends BaseGraphVisitHandler +public final class NodeSequenceVisitor + extends BaseGraphVisitHandler, List> { - private final List vertices = new ArrayList(); + private final List vertices = new ArrayList(); /** * {@inheritDoc} */ @Override - public boolean discoverVertex( V vertex ) + public boolean discoverVertex( BaseLabeledVertex vertex ) { vertices.add( vertex ); return true; } /** - * - * - * @return + * {@inheritDoc} */ - public List getVertices() + @Override + public List onCompleted() { return unmodifiableList( vertices ); } Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java?rev=1237632&r1=1237631&r2=1237632&view=diff ============================================================================== --- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java (original) +++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/visit/VisitTestCase.java Mon Jan 30 13:03:31 2012 @@ -177,12 +177,8 @@ public final class VisitTestCase // actual node set - NodeSequenceVisitor visitor = - new NodeSequenceVisitor(); - - visit( input ).from( new BaseLabeledVertex( "S" ) ).applyingDepthFirstSearch( visitor ); - - final List actual = visitor.getVertices(); + final List actual = + visit( input ).from( new BaseLabeledVertex( "S" ) ).applyingDepthFirstSearch( new NodeSequenceVisitor() ); // assertion