commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
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 GMT
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 <V> the vertex type
  * @param <W> the weight type
  */
-class FlowNetworkHandler<V, W>
-    extends BaseGraphVisitHandler<V, WeightedEdge<W>, DirectedGraph<V, WeightedEdge<W>>,
W>
+class FlowNetworkHandler<V, E, W>
+    extends BaseGraphVisitHandler<V, E, DirectedGraph<V, E>, W>
 {
 
-    private final DirectedGraph<V, WeightedEdge<W>> flowNetwork;
+    private final DirectedGraph<V, E> flowNetwork;
 
     private final V source;
 
@@ -48,27 +49,30 @@ class FlowNetworkHandler<V, W>
 
     private final OrderedMonoid<W> weightOperations;
 
+    private final Mapper<E, W> weightedEdges;
+
     private W maxFlow;
 
-    private final Map<WeightedEdge<W>, W> residualEdgeCapacities = new HashMap<WeightedEdge<W>,
W>();
+    private final Map<E, W> residualEdgeCapacities = new HashMap<E, W>();
 
     // these are new for each new visit of the graph
-    private PredecessorsList<V, WeightedEdge<W>, W> predecessors;
+    private PredecessorsList<V, E, W> predecessors;
 
     private boolean foundAugmentingPath;
 
-    FlowNetworkHandler( DirectedGraph<V, WeightedEdge<W>> flowNetwork, V source,
V target, OrderedMonoid<W> weightOperations )
+    FlowNetworkHandler( DirectedGraph<V, E> flowNetwork, V source, V target, OrderedMonoid<W>
weightOperations, Mapper<E, W> weightedEdges )
     {
         this.flowNetwork = flowNetwork;
         this.source = source;
         this.target = target;
         this.weightOperations = weightOperations;
+        this.weightedEdges = weightedEdges;
 
         maxFlow = weightOperations.zero();
 
-        for ( WeightedEdge<W> 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<V, W>
     void updateResidualNetworkWithCurrentAugmentingPath()
     {
         // build actual augmenting path
-        WeightedPath<V, WeightedEdge<W>, W> augmentingPath = predecessors.buildPath(
source, target );
-        
+        WeightedPath<V, E, W> augmentingPath = predecessors.buildPath( source, target
);
+
         // find flow increment
         W flowIncrement = null;
-        for ( WeightedEdge<W> edge : augmentingPath.getEdges() )
+        for ( E edge : augmentingPath.getEdges() )
         {
             W edgeCapacity = residualEdgeCapacities.get( edge );
             if ( flowIncrement == null
@@ -107,7 +111,7 @@ class FlowNetworkHandler<V, W>
 
         // update max flow and capacities accordingly
         maxFlow = weightOperations.append( maxFlow, flowIncrement );
-        for ( WeightedEdge<W> edge : augmentingPath.getEdges() )
+        for ( E edge : augmentingPath.getEdges() )
         {
             // decrease capacity for direct edge
             W directCapacity = residualEdgeCapacities.get( edge );
@@ -115,7 +119,7 @@ class FlowNetworkHandler<V, W>
 
             // increase capacity for inverse edge
             VertexPair<V> vertexPair = flowNetwork.getVertices( edge );
-            WeightedEdge<W> 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<V, W>
      * {@inheritDoc}
      */
     @Override
-    public void discoverGraph( DirectedGraph<V, WeightedEdge<W>> graph )
+    public void discoverGraph( DirectedGraph<V, E> graph )
     {
         // reset ausiliary structures for a new graph visit
-        predecessors = new PredecessorsList<V, WeightedEdge<W>, W>( graph, weightOperations
);
+        predecessors = new PredecessorsList<V, E, W>( graph, weightOperations, weightedEdges
);
         foundAugmentingPath = false;
     }
 
@@ -136,7 +140,7 @@ class FlowNetworkHandler<V, W>
      * {@inheritDoc}
      */
     @Override
-    public boolean discoverEdge( V head, WeightedEdge<W> 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



Mime
View raw message