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/24 14:09:46 UTC
svn commit: r1235238 - in /commons/sandbox/graph/trunk/src: changes/
main/java/org/apache/commons/graph/flow/
main/java/org/apache/commons/graph/shortestpath/
test/java/org/apache/commons/graph/flow/
Author: simonetripodi
Date: Tue Jan 24 13:09:45 2012
New Revision: 1235238
URL: http://svn.apache.org/viewvc?rev=1235238&view=rev
Log:
[SANDBOX-355] Provide Flow algorithms - patch provided by Claudio Squarcella
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java (with props)
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java (with props)
Modified:
commons/sandbox/graph/trunk/src/changes/changes.xml
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FordFulkerson.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.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=1235238&r1=1235237&r2=1235238&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/changes/changes.xml (original)
+++ commons/sandbox/graph/trunk/src/changes/changes.xml Tue Jan 24 13:09:45 2012
@@ -35,6 +35,9 @@
<action dev="simonetripodi" type="update" issue="SANDBOX-361">
Add fluent APIs to build mutable Graphes
</action>
+ <action dev="simonetripodi" type="update" issue="SANDBOX-355" due-to="Claudio Squarcella">
+ Provide Flow algorithms
+ </action>
<action dev="simonetripodi" type="update" issue="SANDBOX-358" due-to="Claudio Squarcella">
Early return/termination for graph visit.
</action>
Added: 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=1235238&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java Tue Jan 24 13:09:45 2012
@@ -0,0 +1,179 @@
+package org.apache.commons.graph.flow;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+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;
+import org.apache.commons.graph.WeightedPath;
+import org.apache.commons.graph.shortestpath.PredecessorsList;
+import org.apache.commons.graph.visit.BaseGraphVisitHandler;
+import org.apache.commons.graph.weight.OrderedMonoid;
+
+/**
+ * Provides standard operations for max-flow algorithms,
+ * like Ford-Fulkerson or Edmonds-Karp.
+ *
+ * @param <V> the vertex type
+ * @param <WE> the weighted edge type
+ * @param <W> the weight type
+ */
+class FlowNetworkHandler<V extends Vertex, WE extends WeightedEdge<W>, W>
+ extends BaseGraphVisitHandler<V, WE>
+{
+
+ private final DirectedGraph<V, WE> flowNetwork;
+
+ private final V source;
+
+ private final V target;
+
+ private final OrderedMonoid<W> orderedMonoid;
+
+ private W maxFlow;
+
+ private final Map<WE, W> residualEdgeCapacities = new HashMap<WE, W>();
+
+ // these are new for each new visit of the graph
+ private PredecessorsList<V, WE, W> predecessors;
+
+ private boolean foundAugmentingPath;
+
+ FlowNetworkHandler( DirectedGraph<V, WE> flowNetwork, V source, V target, OrderedMonoid<W> orderedMonoid )
+ {
+ this.flowNetwork = flowNetwork;
+ this.source = source;
+ this.target = target;
+ this.orderedMonoid = orderedMonoid;
+
+ maxFlow = orderedMonoid.zero();
+
+ for ( WE edge : flowNetwork.getEdges() )
+ {
+ residualEdgeCapacities.put( edge, edge.getWeight() );
+ }
+
+ predecessors = null;
+ }
+
+ /**
+ * Checks whether there is an augmenting path in the flow network,
+ * given the current residual capacities.
+ * @return true if there is an augmenting path, false otherwise
+ */
+ boolean hasAugmentingPath()
+ {
+ return foundAugmentingPath;
+ }
+
+ /**
+ * Updates the residual capacities in the flow network,
+ * based on the most recent augmenting path.
+ */
+ void updateResidualNetworkWithCurrentAugmentingPath()
+ {
+ // build actual augmenting path
+ WeightedPath<V, WE, W> augmentingPath = predecessors.buildPath( source, target );
+
+ // find flow increment
+ W flowIncrement = null;
+ for ( WE edge : augmentingPath.getEdges() )
+ {
+ W edgeCapacity = residualEdgeCapacities.get( edge );
+ if ( flowIncrement == null
+ || orderedMonoid.compare( edgeCapacity, flowIncrement ) < 0 )
+ {
+ flowIncrement = edgeCapacity;
+ }
+ }
+
+ // update max flow and capacities accordingly
+ maxFlow = orderedMonoid.append( maxFlow, flowIncrement );
+ for ( WE edge : augmentingPath.getEdges() )
+ {
+ // decrease capacity for direct edge
+ W directCapacity = residualEdgeCapacities.get( edge );
+ residualEdgeCapacities.put( edge, orderedMonoid.append( directCapacity, orderedMonoid.inverse( flowIncrement ) ) );
+
+ // increase capacity for inverse edge
+ VertexPair<V> vertexPair = flowNetwork.getVertices( edge );
+ WE 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<V, WE> graph )
+ {
+ // reset ausiliary structures for a new graph visit
+ predecessors = new PredecessorsList<V, WE, W>( graph, orderedMonoid );
+ foundAugmentingPath = false;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean discoverEdge( V head, WE edge, V tail )
+ {
+ W residualEdgeCapacity = residualEdgeCapacities.get( edge );
+ // avoid expanding the edge when it has no residual capacity
+ if ( orderedMonoid.compare( residualEdgeCapacity, orderedMonoid.zero() ) <= 0 )
+ {
+ return false;
+ }
+ predecessors.addPredecessor( tail, head );
+ return true;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean finishEdge( V head, WE edge, V tail )
+ {
+ if ( tail.equals( target ) )
+ {
+ // search ends when target vertex is reached
+ foundAugmentingPath = true;
+ return true;
+ }
+ return false;
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FlowNetworkHandler.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FordFulkerson.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FordFulkerson.java?rev=1235238&r1=1235237&r2=1235238&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FordFulkerson.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FordFulkerson.java Tue Jan 24 13:09:45 2012
@@ -19,9 +19,111 @@ package org.apache.commons.graph.flow;
* under the License.
*/
+import static org.apache.commons.graph.CommonsGraph.newDirectedMutableWeightedGraph;
+import static org.apache.commons.graph.CommonsGraph.visit;
+
+import org.apache.commons.graph.DirectedGraph;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.VertexPair;
+import org.apache.commons.graph.WeightedEdge;
+import org.apache.commons.graph.builder.AbstractGraphConnection;
+import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
+import org.apache.commons.graph.weight.OrderedMonoid;
+import org.apache.commons.graph.weight.primitive.IntegerWeight;
+
+/**
+ * Contains the implementation of the algorithm of Ford and Fulkerson
+ * to calculate the maximum allowed flow in a graph.
+ */
public final class FordFulkerson
{
- // TODO
+ /**
+ * This class can not be instantiated directly
+ */
+ private FordFulkerson()
+ {
+ // do nothing
+ }
+
+ /**
+ * Applies the algorithm of Ford and Fulkerson to find the maximum flow on the input {@link Graph},
+ * given a source and a target {@link Vertex}.
+ * @param graph the input edge-weighted graph
+ * @param source the source vertex
+ * @param target the target vertex
+ * @param orderedMonoid the ordered monoid needed for operations on edge weights
+ * @return the maximum flow between source and target
+ */
+ public static <V extends Vertex, W, WE extends WeightedEdge<W>, G extends DirectedGraph<V, WE>> W findMaxFlow( G graph,
+ V source,
+ V target,
+ OrderedMonoid<W> orderedMonoid )
+ {
+ // create flow network
+ DirectedGraph<V, WE> flowNetwork = createFlowNetwork( graph, orderedMonoid );
+
+ // create flow network handler
+ FlowNetworkHandler<V, WE, W> flowNetworkHandler =
+ new FlowNetworkHandler<V, WE, W>( flowNetwork, source, target, orderedMonoid );
+
+ // perform depth first search
+ visit( flowNetwork ).from( source ).applyingDepthFirstSearch( flowNetworkHandler );
+
+ while ( flowNetworkHandler.hasAugmentingPath() )
+ {
+ // update flow network
+ flowNetworkHandler.updateResidualNetworkWithCurrentAugmentingPath();
+ // look for another augmenting path
+ visit( flowNetwork ).from( source ).applyingDepthFirstSearch( flowNetworkHandler );
+ }
+
+ return flowNetworkHandler.getMaxFlow();
+ }
+
+ /**
+ * Applies the algorithm of Ford and Fulkerson to find the maximum flow on the input {@link Graph}
+ * whose edges have weights of type Integer, given a source and a target {@link Vertex}.
+ * @param graph the input edge-weighted graph
+ * @param source the source vertex
+ * @param target the target vertex
+ * @return the maximum flow between source and target
+ */
+ public static <V extends Vertex, WE extends WeightedEdge<Integer>, G extends DirectedGraph<V, WE>> Integer findMaxFlow( G graph,
+ V source,
+ V target )
+ {
+ return findMaxFlow( graph, source, target, new IntegerWeight() );
+ }
+
+ private static <V extends Vertex, WE extends WeightedEdge<W>, W, G extends DirectedGraph<V, WE>> DirectedGraph<V, WE> createFlowNetwork( final G graph,
+ final OrderedMonoid<W> orderedMonoid )
+ {
+ DirectedGraph<V, WE> flowNetwork =
+ newDirectedMutableWeightedGraph( new AbstractGraphConnection<V, WE>()
+ {
+ @SuppressWarnings( "unchecked" )
+ @Override
+ public void connect()
+ {
+ // vertices
+ for ( V vertex : graph.getVertices() )
+ {
+ addVertex( vertex );
+ }
+ // edges
+ for ( WE edge : graph.getEdges() )
+ {
+ VertexPair<V> edgeVertices = graph.getVertices( edge );
+ V head = edgeVertices.getHead();
+ V tail = edgeVertices.getTail();
+ addEdge( edge ).from( head ).to( tail );
+ addEdge( (WE) new BaseLabeledWeightedEdge<W>( "Inverse edge for " + edge.toString(), orderedMonoid.zero() ) );
+ }
+ }
+ } );
+
+ return flowNetwork;
+ }
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java?rev=1235238&r1=1235237&r2=1235238&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/shortestpath/PredecessorsList.java Tue Jan 24 13:09:45 2012
@@ -37,11 +37,11 @@ import org.apache.commons.graph.weight.M
* @param <WE> the Graph weighted edges type
* @param <W> the weight type
*/
-final class PredecessorsList<V extends Vertex, WE extends WeightedEdge<W>, W>
+public final class PredecessorsList<V extends Vertex, WE extends WeightedEdge<W>, W>
{
private final Graph<V, WE> graph;
-
+
private final Monoid<W> monoid;
private final Map<V, V> predecessors = new HashMap<V, V>();
Added: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java?rev=1235238&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java (added)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java Tue Jan 24 13:09:45 2012
@@ -0,0 +1,70 @@
+package org.apache.commons.graph.flow;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import static org.junit.Assert.assertEquals;
+
+import org.apache.commons.graph.model.BaseLabeledVertex;
+import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
+import org.apache.commons.graph.model.DirectedMutableWeightedGraph;
+import org.junit.Test;
+
+/**
+ * Test for Ford-Fulkerson algorithm implementation.
+ * The test graph is available on
+ * <a href="http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm#Integral_example">Wikipedia</a>.
+ */
+public final class FordFulkersonTestCase
+{
+
+ @Test
+ public void findMaxFlowAndVerify()
+ {
+ DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>, Integer> graph =
+ new DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>, Integer>();
+
+ // building Graph
+ BaseLabeledVertex a = new BaseLabeledVertex("A");
+ BaseLabeledVertex b = new BaseLabeledVertex("B");
+ BaseLabeledVertex c = new BaseLabeledVertex("C");
+ BaseLabeledVertex d = new BaseLabeledVertex("D");
+
+ graph.addVertex( a );
+ graph.addVertex( b );
+ graph.addVertex( c );
+ graph.addVertex( d );
+
+ graph.addEdge( a, new BaseLabeledWeightedEdge<Integer>( "A -> B", 1000 ), b );
+ graph.addEdge( a, new BaseLabeledWeightedEdge<Integer>( "A -> C", 1000 ), c );
+ graph.addEdge( b, new BaseLabeledWeightedEdge<Integer>( "B -> C", 1 ), c );
+ graph.addEdge( b, new BaseLabeledWeightedEdge<Integer>( "B -> D", 1000 ), d );
+ graph.addEdge( c, new BaseLabeledWeightedEdge<Integer>( "C -> D", 1000 ), d );
+
+
+ // expected max flow
+ Integer expected = 2000;
+
+ // actual max flow
+ Integer actual = FordFulkerson.findMaxFlow( graph, a, d );
+
+ assertEquals( actual, expected );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java
------------------------------------------------------------------------------
svn:mime-type = text/plain