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:32:59 UTC
svn commit: r1235249 -
/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FordFulkerson.java
Author: simonetripodi
Date: Tue Jan 24 13:32:58 2012
New Revision: 1235249
URL: http://svn.apache.org/viewvc?rev=1235249&view=rev
Log:
no needs to allocate a wrapper method to build the graph
Modified:
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/flow/FordFulkerson.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/flow/FordFulkerson.java?rev=1235249&r1=1235248&r2=1235249&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:32:58 2012
@@ -55,13 +55,34 @@ public final class FordFulkerson
* @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,
+ public static <V extends Vertex, W, WE extends WeightedEdge<W>, G extends DirectedGraph<V, WE>> W findMaxFlow( final G graph,
V source,
V target,
- OrderedMonoid<W> orderedMonoid )
+ final OrderedMonoid<W> orderedMonoid )
{
// create flow network
- DirectedGraph<V, WE> flowNetwork = createFlowNetwork( graph, 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() ) );
+ }
+ }
+ } );
// create flow network handler
FlowNetworkHandler<V, WE, W> flowNetworkHandler =
@@ -96,34 +117,4 @@ public final class FordFulkerson
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;
- }
-
}