commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject 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/
Date Mon, 06 Feb 2012 16:07:15 GMT
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



Mime
View raw message