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/25 18:12:17 UTC
svn commit: r1235827 - in /commons/sandbox/graph/trunk/src:
main/java/org/apache/commons/graph/ main/java/org/apache/commons/graph/flow/
test/java/org/apache/commons/graph/flow/
Author: simonetripodi
Date: Wed Jan 25 17:12:16 2012
New Revision: 1235827
URL: http://svn.apache.org/viewvc?rev=1235827&view=rev
Log:
moved MaxFlow algorithms APIs to fluent version
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultFromHeadBuilder.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java (with props)
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultToTailBuilder.java (with props)
Removed:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FordFulkerson.java
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/MaxFlowAlgorithmSelector.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/ToTailBuilder.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java?rev=1235827&r1=1235826&r2=1235827&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/CommonsGraph.java Wed Jan 25 17:12:16 2012
@@ -28,6 +28,7 @@ import org.apache.commons.graph.coloring
import org.apache.commons.graph.coloring.DefaultColorsBuilder;
import org.apache.commons.graph.export.DefaultToStreamBuilder;
import org.apache.commons.graph.export.ToStreamBuilder;
+import org.apache.commons.graph.flow.DefaultFromHeadBuilder;
import org.apache.commons.graph.flow.FromHeadBuilder;
import org.apache.commons.graph.model.DirectedMutableGraph;
import org.apache.commons.graph.model.DirectedMutableWeightedGraph;
@@ -71,9 +72,10 @@ public final class CommonsGraph<V extend
* @param graph the input edge-weighted graph
* @return
*/
- public static <V extends Vertex, W, WE extends WeightedEdge<W>, G extends DirectedGraph<V, WE>> FromHeadBuilder<V, W, WE, G> findMaxFlow( final G graph )
+ public static <V extends Vertex, W, WE extends WeightedEdge<W>, G extends DirectedGraph<V, WE>> FromHeadBuilder<V, W, WE, G> findMaxFlow( G graph )
{
- return null;
+ graph = checkNotNull( graph, "Max flow can not be calculated on null graph" );
+ return new DefaultFromHeadBuilder<V, W, WE, G>( graph );
}
/**
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultFromHeadBuilder.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultFromHeadBuilder.java?rev=1235827&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultFromHeadBuilder.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultFromHeadBuilder.java Wed Jan 25 17:12:16 2012
@@ -0,0 +1,53 @@
+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.apache.commons.graph.utils.Assertions.checkNotNull;
+
+import org.apache.commons.graph.DirectedGraph;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.WeightedEdge;
+
+/**
+ * {@link FromHeadBuilder} implementation.
+ *
+ * @param <V>
+ * @param <W>
+ * @param <WE>
+ * @param <G>
+ */
+public final class DefaultFromHeadBuilder<V extends Vertex, W, WE extends WeightedEdge<W>, G extends DirectedGraph<V, WE>>
+ implements FromHeadBuilder<V, W, WE, G>
+{
+
+ private final G graph;
+
+ public DefaultFromHeadBuilder( G graph )
+ {
+ this.graph = graph;
+ }
+
+ public ToTailBuilder<V, W, WE, G> from( V head )
+ {
+ head = checkNotNull( head, "head vertex has to be specifies when looking for the max flow" );
+ return new DefaultToTailBuilder<V, W, WE, G>( graph, head );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultFromHeadBuilder.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultFromHeadBuilder.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultFromHeadBuilder.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: 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=1235827&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java Wed Jan 25 17:12:16 2012
@@ -0,0 +1,125 @@
+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.apache.commons.graph.CommonsGraph.newDirectedMutableWeightedGraph;
+import static org.apache.commons.graph.CommonsGraph.visit;
+import static org.apache.commons.graph.utils.Assertions.checkNotNull;
+
+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;
+
+/**
+ * {@link MaxFlowAlgorithmSelector} implementation.
+ *
+ * @param <V>
+ * @param <W>
+ * @param <WE>
+ * @param <G>
+ */
+final class DefaultMaxFlowAlgorithmSelector<V extends Vertex, W, WE extends WeightedEdge<W>, G extends DirectedGraph<V, WE>>
+ implements MaxFlowAlgorithmSelector<V, W, WE, G>
+{
+
+ private final G graph;
+
+ private final V source;
+
+ private final V target;
+
+ public DefaultMaxFlowAlgorithmSelector( G graph, V source, V target )
+ {
+ this.graph = graph;
+ this.source = source;
+ this.target = target;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ 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" );
+
+ // 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>>()
+ {
+ @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 );
+
+ 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() ) )
+ .from( tail ).to( head );
+ }
+ }
+ }
+ } );
+
+ // create flow network handler
+ FlowNetworkHandler<V, WeightedEdge<W>, W> flowNetworkHandler =
+ new FlowNetworkHandler<V, WeightedEdge<W>, 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.getMaxFlow();
+ }
+
+ /**
+ * {@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;
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultMaxFlowAlgorithmSelector.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultToTailBuilder.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultToTailBuilder.java?rev=1235827&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultToTailBuilder.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultToTailBuilder.java Wed Jan 25 17:12:16 2012
@@ -0,0 +1,56 @@
+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.apache.commons.graph.utils.Assertions.checkNotNull;
+
+import org.apache.commons.graph.DirectedGraph;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.WeightedEdge;
+
+/**
+ * {@link DefaultToTailBuilder} implementation.
+ *
+ * @param <V>
+ * @param <W>
+ * @param <WE>
+ * @param <G>
+ */
+final class DefaultToTailBuilder<V extends Vertex, W, WE extends WeightedEdge<W>, G extends DirectedGraph<V, WE>>
+ implements ToTailBuilder<V, W, WE, G>
+{
+
+ private final G graph;
+
+ private final V head;
+
+ public DefaultToTailBuilder( G graph, V head )
+ {
+ this.graph = graph;
+ this.head = head;
+ }
+
+ public MaxFlowAlgorithmSelector<V, W, WE, G> to( V tail )
+ {
+ tail = checkNotNull( tail, "tail vertex has to be specifies when looking for the max flow" );
+ return new DefaultMaxFlowAlgorithmSelector<V, W, WE, G>( graph, head, tail );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultToTailBuilder.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultToTailBuilder.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/DefaultToTailBuilder.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/MaxFlowAlgorithmSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/MaxFlowAlgorithmSelector.java?rev=1235827&r1=1235826&r2=1235827&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/MaxFlowAlgorithmSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/MaxFlowAlgorithmSelector.java Wed Jan 25 17:12:16 2012
@@ -33,7 +33,7 @@ public interface MaxFlowAlgorithmSelecto
* @param orderedMonoid
* @return
*/
- W applyingFordFulkerson( OrderedMonoid<W> orderedMonoid );
+ <OM extends OrderedMonoid<W>> W applyingFordFulkerson( OM orderedMonoid );
/**
*
@@ -41,6 +41,6 @@ public interface MaxFlowAlgorithmSelecto
* @param orderedMonoid
* @return
*/
- W applyingEdmondsKarp( OrderedMonoid<W> orderedMonoid );
+ <OM extends OrderedMonoid<W>> W applyingEdmondsKarp( OM orderedMonoid );
}
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/ToTailBuilder.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/ToTailBuilder.java?rev=1235827&r1=1235826&r2=1235827&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/ToTailBuilder.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/ToTailBuilder.java Wed Jan 25 17:12:16 2012
@@ -29,9 +29,9 @@ public interface ToTailBuilder<V extends
/**
*
*
- * @param head
+ * @param tail
* @return
*/
- MaxFlowAlgorithmSelector<V, W, WE, G> to( V head );
+ MaxFlowAlgorithmSelector<V, W, WE, G> to( V tail );
}
Modified: 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=1235827&r1=1235826&r2=1235827&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/flow/FordFulkersonTestCase.java Wed Jan 25 17:12:16 2012
@@ -19,6 +19,7 @@ package org.apache.commons.graph.flow;
* under the License.
*/
+import static org.apache.commons.graph.CommonsGraph.findMaxFlow;
import static org.apache.commons.graph.CommonsGraph.newDirectedMutableWeightedGraph;
import static org.junit.Assert.assertEquals;
@@ -26,6 +27,7 @@ import org.apache.commons.graph.builder.
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;
/**
@@ -67,7 +69,7 @@ public final class FordFulkersonTestCase
final Integer expected = 2000;
// actual max flow
- Integer actual = FordFulkerson.findMaxFlow( graph, a, d );
+ Integer actual = findMaxFlow( graph ).from( a ).to( d ).applyingFordFulkerson( new IntegerWeight() );
assertEquals( actual, expected );
}