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
