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 9ACCD91D4 for ; Wed, 7 Mar 2012 23:42:37 +0000 (UTC) Received: (qmail 7042 invoked by uid 500); 7 Mar 2012 23:42:37 -0000 Delivered-To: apmail-commons-commits-archive@commons.apache.org Received: (qmail 6970 invoked by uid 500); 7 Mar 2012 23:42:37 -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 6963 invoked by uid 99); 7 Mar 2012 23:42:37 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Wed, 07 Mar 2012 23:42:37 +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; Wed, 07 Mar 2012 23:42:34 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id 3D3162388980 for ; Wed, 7 Mar 2012 23:42:13 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1298224 - /commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java Date: Wed, 07 Mar 2012 23:42:13 -0000 To: commits@commons.apache.org From: simonetripodi@apache.org X-Mailer: svnmailer-1.0.8-patched Message-Id: <20120307234213.3D3162388980@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org Author: simonetripodi Date: Wed Mar 7 23:42:12 2012 New Revision: 1298224 URL: http://svn.apache.org/viewvc?rev=1298224&view=rev Log: the visit handler has to use now the Mapper to get edge weight Modified: commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java Modified: commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java?rev=1298224&r1=1298223&r2=1298224&view=diff ============================================================================== --- commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java (original) +++ commons/sandbox/graph/branches/drop-marker-interfaces-feature/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java Wed Mar 7 23:42:12 2012 @@ -23,6 +23,7 @@ import java.util.HashMap; import java.util.Map; import org.apache.commons.graph.DirectedGraph; +import org.apache.commons.graph.Mapper; import org.apache.commons.graph.VertexPair; import org.apache.commons.graph.WeightedPath; import org.apache.commons.graph.shortestpath.PredecessorsList; @@ -36,11 +37,11 @@ import org.apache.commons.graph.weight.O * @param the vertex type * @param the weight type */ -class FlowNetworkHandler - extends BaseGraphVisitHandler, DirectedGraph>, W> +class FlowNetworkHandler + extends BaseGraphVisitHandler, W> { - private final DirectedGraph> flowNetwork; + private final DirectedGraph flowNetwork; private final V source; @@ -48,27 +49,30 @@ class FlowNetworkHandler private final OrderedMonoid weightOperations; + private final Mapper weightedEdges; + private W maxFlow; - private final Map, W> residualEdgeCapacities = new HashMap, W>(); + private final Map residualEdgeCapacities = new HashMap(); // these are new for each new visit of the graph - private PredecessorsList, W> predecessors; + private PredecessorsList predecessors; private boolean foundAugmentingPath; - FlowNetworkHandler( DirectedGraph> flowNetwork, V source, V target, OrderedMonoid weightOperations ) + FlowNetworkHandler( DirectedGraph flowNetwork, V source, V target, OrderedMonoid weightOperations, Mapper weightedEdges ) { this.flowNetwork = flowNetwork; this.source = source; this.target = target; this.weightOperations = weightOperations; + this.weightedEdges = weightedEdges; maxFlow = weightOperations.zero(); - for ( WeightedEdge edge : flowNetwork.getEdges() ) + for ( E edge : flowNetwork.getEdges() ) { - residualEdgeCapacities.put( edge, edge.getWeight() ); + residualEdgeCapacities.put( edge, weightedEdges.map( edge ) ); } predecessors = null; @@ -91,11 +95,11 @@ class FlowNetworkHandler void updateResidualNetworkWithCurrentAugmentingPath() { // build actual augmenting path - WeightedPath, W> augmentingPath = predecessors.buildPath( source, target ); - + WeightedPath augmentingPath = predecessors.buildPath( source, target ); + // find flow increment W flowIncrement = null; - for ( WeightedEdge edge : augmentingPath.getEdges() ) + for ( E edge : augmentingPath.getEdges() ) { W edgeCapacity = residualEdgeCapacities.get( edge ); if ( flowIncrement == null @@ -107,7 +111,7 @@ class FlowNetworkHandler // update max flow and capacities accordingly maxFlow = weightOperations.append( maxFlow, flowIncrement ); - for ( WeightedEdge edge : augmentingPath.getEdges() ) + for ( E edge : augmentingPath.getEdges() ) { // decrease capacity for direct edge W directCapacity = residualEdgeCapacities.get( edge ); @@ -115,7 +119,7 @@ class FlowNetworkHandler // increase capacity for inverse edge VertexPair vertexPair = flowNetwork.getVertices( edge ); - WeightedEdge inverseEdge = flowNetwork.getEdge( vertexPair.getTail(), vertexPair.getHead() ); + E inverseEdge = flowNetwork.getEdge( vertexPair.getTail(), vertexPair.getHead() ); W inverseCapacity = residualEdgeCapacities.get( inverseEdge ); residualEdgeCapacities.put( inverseEdge, weightOperations.append( inverseCapacity, flowIncrement ) ); } @@ -125,10 +129,10 @@ class FlowNetworkHandler * {@inheritDoc} */ @Override - public void discoverGraph( DirectedGraph> graph ) + public void discoverGraph( DirectedGraph graph ) { // reset ausiliary structures for a new graph visit - predecessors = new PredecessorsList, W>( graph, weightOperations ); + predecessors = new PredecessorsList( graph, weightOperations, weightedEdges ); foundAugmentingPath = false; } @@ -136,7 +140,7 @@ class FlowNetworkHandler * {@inheritDoc} */ @Override - public boolean discoverEdge( V head, WeightedEdge edge, V tail ) + public boolean discoverEdge( V head, E edge, V tail ) { W residualEdgeCapacity = residualEdgeCapacities.get( edge ); // avoid expanding the edge when it has no residual capacity