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/02/06 17:07:15 UTC
svn commit: r1241056 - in /commons/sandbox/graph/trunk/src: changes/
main/java/org/apache/commons/graph/flow/
main/java/org/apache/commons/graph/visit/
test/java/org/apache/commons/graph/flow/
Author: simonetripodi
Date: Mon Feb 6 16:07:15 2012
New Revision: 1241056
URL: http://svn.apache.org/viewvc?rev=1241056&view=rev
Log:
[SANDBOX-385] Provide Edmonds-Karp algorithm - Patch provided by Claudio Squarcella
Added:
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java (with props)
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/visit/DefaultVisitAlgorithmsSelector.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=1241056&r1=1241055&r2=1241056&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/changes/changes.xml (original)
+++ commons/sandbox/graph/trunk/src/changes/changes.xml Mon Feb 6 16:07:15 2012
@@ -23,6 +23,9 @@
</properties>
<body>
<release version="0.1" date="201?-??-??" description="First release.">
+ <action dev="simonetripodi" type="update" issue="SANDBOX-385" due-to="Claudio Squarcella">
+ Provide Edmonds-Karp algorithm
+ </action>
<action dev="simonetripodi" type="fix" issue="SANDBOX-384">
Make Graph components Serializable
</action>
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=1241056&r1=1241055&r2=1241056&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 Feb 6 16:07:15 2012
@@ -61,11 +61,58 @@ final class DefaultMaxFlowAlgorithmSelec
*/
public <OM extends OrderedMonoid<W>> W applyingFordFulkerson( OM orderedMonoid )
{
- final OrderedMonoid<W> monoid = checkNotNull( orderedMonoid, "Wight monoid can not be null to find the max flow in the graph" );
+ final OM checkedOrderedMonoid = checkNotNull( orderedMonoid, "Weight monoid can not be null to find the max flow in the graph" );
// create flow network
- // note: use edges of more generic type WeightedEdge<W> to allow for newly created edges
- DirectedGraph<V, WeightedEdge<W>> flowNetwork = newDirectedMutableWeightedGraph( new AbstractGraphConnection<V, WeightedEdge<W>>()
+ final DirectedGraph<V, WeightedEdge<W>> flowNetwork = newFlowNetwok( graph, checkedOrderedMonoid );
+
+ // create flow network handler
+ final FlowNetworkHandler<V, W> flowNetworkHandler = new FlowNetworkHandler<V, W>( flowNetwork, source, target, checkedOrderedMonoid );
+
+ // perform depth first search
+ visit( flowNetwork ).from( source ).applyingDepthFirstSearch( flowNetworkHandler );
+
+ while ( flowNetworkHandler.hasAugmentingPath() )
+ {
+ // update flow network
+ flowNetworkHandler.updateResidualNetworkWithCurrentAugmentingPath();
+ // look for another augmenting path with depth first search
+ visit( flowNetwork ).from( source ).applyingDepthFirstSearch( flowNetworkHandler );
+ }
+
+ return flowNetworkHandler.onCompleted();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public <OM extends OrderedMonoid<W>> W applyingEdmondsKarp( OM orderedMonoid )
+ {
+ final OM checkedOrderedMonoid = checkNotNull( orderedMonoid, "Weight monoid can not be null to find the max flow in the graph" );
+
+ // create flow network
+ final DirectedGraph<V, WeightedEdge<W>> flowNetwork = newFlowNetwok( graph, checkedOrderedMonoid );
+
+ // create flow network handler
+ final FlowNetworkHandler<V, W> flowNetworkHandler = new FlowNetworkHandler<V, W>( flowNetwork, source, target, checkedOrderedMonoid );
+
+ // perform breadth first search
+ visit( flowNetwork ).from( source ).applyingBreadthFirstSearch( flowNetworkHandler );
+
+ while ( flowNetworkHandler.hasAugmentingPath() )
+ {
+ // update flow network
+ flowNetworkHandler.updateResidualNetworkWithCurrentAugmentingPath();
+ // look for another augmenting path with breadth first search
+ visit( flowNetwork ).from( source ).applyingBreadthFirstSearch( flowNetworkHandler );
+ }
+
+ return flowNetworkHandler.onCompleted();
+ }
+
+ private <OM extends OrderedMonoid<W>> DirectedGraph<V, WeightedEdge<W>> newFlowNetwok( final G graph, final OM orderedMonoid )
+ {
+ return newDirectedMutableWeightedGraph( new AbstractGraphConnection<V, WeightedEdge<W>>()
{
@Override
public void connect()
@@ -87,38 +134,12 @@ final class DefaultMaxFlowAlgorithmSelec
if ( graph.getEdge( tail, head ) == null )
{
// complete the flow network with a zero-capacity inverse edge
- addEdge( new BaseLabeledWeightedEdge<W>( "Inverse edge for " + edge, monoid.zero() ) )
+ addEdge( new BaseLabeledWeightedEdge<W>( "Inverse edge for " + edge, orderedMonoid.zero() ) )
.from( tail ).to( head );
}
}
}
} );
-
- // create flow network handler
- FlowNetworkHandler<V, W> flowNetworkHandler = new FlowNetworkHandler<V, W>( flowNetwork, source, target, monoid );
-
- // 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.onCompleted();
- }
-
- /**
- * {@inheritDoc}
- */
- public <OM extends OrderedMonoid<W>> W applyingEdmondsKarp( OM orderedMonoid )
- {
- orderedMonoid = checkNotNull( orderedMonoid, "Wight monoid can not be null to find the max flow in the graph" );
- // TODO add missing implementation!
- return null;
}
}
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=1241056&r1=1241055&r2=1241056&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 Feb 6 16:07:15 2012
@@ -36,7 +36,6 @@ import org.apache.commons.graph.weight.O
* 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, W>
@@ -95,7 +94,7 @@ class FlowNetworkHandler<V extends Verte
{
// build actual augmenting path
WeightedPath<V, WeightedEdge<W>, W> augmentingPath = predecessors.buildPath( source, target );
-
+
// find flow increment
W flowIncrement = null;
for ( WeightedEdge<W> edge : augmentingPath.getEdges() )
@@ -154,10 +153,17 @@ class FlowNetworkHandler<V extends Verte
/**
* {@inheritDoc}
*/
- @Override
- public boolean finishEdge( V head, WeightedEdge<W> edge, V tail )
+ public boolean discoverVertex( V vertex )
+ {
+ return !vertex.equals( target );
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean finishVertex( V vertex )
{
- if ( tail.equals( target ) )
+ if ( vertex.equals( target ) )
{
// search ends when target vertex is reached
foundAugmentingPath = true;
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=1241056&r1=1241055&r2=1241056&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 Feb 6 16:07:15 2012
@@ -99,13 +99,14 @@ final class DefaultVisitAlgorithmsSelect
while ( connected.hasNext() )
{
V w = connected.next();
- if ( visitedVertices.add( w ) )
+ if ( !visitedVertices.contains( w ) )
{
E e = graph.getEdge( v, w );
if ( handler.discoverEdge( v, e, w ) )
{
vertexQueue.offer( w );
+ visitedVertices.add( w );
}
if ( handler.finishEdge( v, e, w ) )
@@ -116,7 +117,6 @@ final class DefaultVisitAlgorithmsSelect
}
}
-
if ( handler.finishVertex( v ) )
{
visitingGraph = false;
@@ -157,13 +157,14 @@ final class DefaultVisitAlgorithmsSelect
while ( connected.hasNext() )
{
V w = connected.next();
- if ( visitedVertices.add( w ) )
+ if ( !visitedVertices.contains( w ) )
{
E e = graph.getEdge( v, w );
if ( handler.discoverEdge( v, e, w ) )
{
vertexStack.push( w );
+ visitedVertices.add( w );
}
if ( handler.finishEdge( v, e, w ) ) {
Added: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java?rev=1241056&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java (added)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java Mon Feb 6 16:07:15 2012
@@ -0,0 +1,86 @@
+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 org.apache.commons.graph.builder.AbstractGraphConnection;
+import org.apache.commons.graph.model.BaseLabeledVertex;
+import org.apache.commons.graph.model.BaseLabeledWeightedEdge;
+import org.apache.commons.graph.model.DirectedMutableWeightedGraph;
+import org.apache.commons.graph.weight.primitive.IntegerWeight;
+import org.junit.Test;
+
+import static org.apache.commons.graph.CommonsGraph.findMaxFlow;
+import static org.apache.commons.graph.CommonsGraph.newDirectedMutableWeightedGraph;
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Test for Edmonds-Karp algorithm implementation.
+ * The test graph is available on
+ * <a href="http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm#Example">Wikipedia</a>.
+ */
+public class EdmondsKarpTestCase
+{
+
+ @Test
+ public void findMaxFlowAndVerify()
+ {
+ final BaseLabeledVertex a = new BaseLabeledVertex( "A" );
+ final BaseLabeledVertex g = new BaseLabeledVertex( "G" );
+
+ DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>, Integer> graph =
+ newDirectedMutableWeightedGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>>()
+ {
+
+ @Override
+ public void connect()
+ {
+ addVertex( a );
+ BaseLabeledVertex b = addVertex( new BaseLabeledVertex( "B" ) );
+ BaseLabeledVertex c = addVertex( new BaseLabeledVertex( "C" ) );
+ BaseLabeledVertex d = addVertex( new BaseLabeledVertex( "D" ) );
+ BaseLabeledVertex e = addVertex( new BaseLabeledVertex( "E" ) );
+ BaseLabeledVertex f = addVertex( new BaseLabeledVertex( "F" ) );
+ addVertex( g );
+
+ addEdge( new BaseLabeledWeightedEdge<Integer>( "A -> B", 3 ) ).from( a ).to( b );
+ addEdge( new BaseLabeledWeightedEdge<Integer>( "A -> D", 3 ) ).from( a ).to( d );
+ addEdge( new BaseLabeledWeightedEdge<Integer>( "B -> C", 4 ) ).from( b ).to( c );
+ addEdge( new BaseLabeledWeightedEdge<Integer>( "C -> A", 3 ) ).from( c ).to( a );
+ addEdge( new BaseLabeledWeightedEdge<Integer>( "C -> D", 1 ) ).from( c ).to( d );
+ addEdge( new BaseLabeledWeightedEdge<Integer>( "C -> E", 2 ) ).from( c ).to( e );
+ addEdge( new BaseLabeledWeightedEdge<Integer>( "D -> E", 2 ) ).from( d ).to( e );
+ addEdge( new BaseLabeledWeightedEdge<Integer>( "D -> F", 6 ) ).from( d ).to( f );
+ addEdge( new BaseLabeledWeightedEdge<Integer>( "E -> B", 1 ) ).from( e ).to( b );
+ addEdge( new BaseLabeledWeightedEdge<Integer>( "E -> G", 1 ) ).from( e ).to( g );
+ addEdge( new BaseLabeledWeightedEdge<Integer>( "F -> G", 9 ) ).from( f ).to( g );
+ }
+
+ } );
+
+ // expected max flow
+ final Integer expected = 5;
+
+ // actual max flow
+ Integer actual = findMaxFlow( graph ).from( a ).to( g ).applyingEdmondsKarp( new IntegerWeight() );
+
+ assertEquals( actual, expected );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/EdmondsKarpTestCase.java
------------------------------------------------------------------------------
svn:mime-type = text/plain