/*
* Copyright (c) 2003, The JUNG Authors
*
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* https://github.com/jrtom/jung/blob/master/LICENSE for a description.
*/
package edu.uci.ics.jung.algorithms.flows;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import junit.framework.Assert;
import junit.framework.Test;
import junit.framework.TestCase;
import junit.framework.TestSuite;
import com.google.common.base.Functions;
import com.google.common.base.Supplier;
import edu.uci.ics.jung.graph.DirectedGraph;
import edu.uci.ics.jung.graph.DirectedSparseMultigraph;
import edu.uci.ics.jung.graph.util.EdgeType;
/**
* @author Scott White, Joshua O'Madadhain, Tom Nelson
*/
public class TestEdmondsKarpMaxFlow extends TestCase {
public static Test suite() {
return new TestSuite(TestEdmondsKarpMaxFlow.class);
}
@Override
protected void setUp() {
}
public void testSanityChecks()
{
DirectedGraph g = new DirectedSparseMultigraph();
Number source = new Integer(1);
Number sink = new Integer(2);
g.addVertex(source);
g.addVertex(sink);
Number v = new Integer(3);
DirectedGraph h = new DirectedSparseMultigraph();
Number w = new Integer(4);
g.addVertex(w);
try
{
new EdmondsKarpMaxFlow(g, source, source, null, null, null);
fail("source and sink vertices not distinct");
}
catch (IllegalArgumentException iae) {}
try
{
new EdmondsKarpMaxFlow(h, source, w, null, null, null);
fail("source and sink vertices not both part of specified graph");
}
catch (IllegalArgumentException iae) {}
try
{
new EdmondsKarpMaxFlow(g, source, v, null, null, null);
fail("source and sink vertices not both part of specified graph");
}
catch (IllegalArgumentException iae) {}
}
public void testSimpleFlow() {
DirectedGraph graph = new DirectedSparseMultigraph();
Supplier edgeFactory = new Supplier() {
int count = 0;
public Number get() {
return count++;
}
};
Map edgeCapacityMap = new HashMap();
for(int i=0; i<6; i++) {
graph.addVertex(i);
}
Map edgeFlowMap = new HashMap();
graph.addEdge(edgeFactory.get(),0,1,EdgeType.DIRECTED);
edgeCapacityMap.put(0, 16);
graph.addEdge(edgeFactory.get(),0,2,EdgeType.DIRECTED);
edgeCapacityMap.put(1,13);
graph.addEdge(edgeFactory.get(),1,2,EdgeType.DIRECTED);
edgeCapacityMap.put(2, 6);
graph.addEdge(edgeFactory.get(),1,3,EdgeType.DIRECTED);
edgeCapacityMap.put(3, 12);
graph.addEdge(edgeFactory.get(),2,4,EdgeType.DIRECTED);
edgeCapacityMap.put(4, 14);
graph.addEdge(edgeFactory.get(),3,2,EdgeType.DIRECTED);
edgeCapacityMap.put(5, 9);
graph.addEdge(edgeFactory.get(),3,5,EdgeType.DIRECTED);
edgeCapacityMap.put(6, 20);
graph.addEdge(edgeFactory.get(),4,3,EdgeType.DIRECTED);
edgeCapacityMap.put(7, 7);
graph.addEdge(edgeFactory.get(),4,5,EdgeType.DIRECTED);
edgeCapacityMap.put(8, 4);
EdmondsKarpMaxFlow ek =
new EdmondsKarpMaxFlow(
graph,
0,
5,
Functions.forMap(edgeCapacityMap, null),
edgeFlowMap,
edgeFactory);
ek.evaluate();
assertTrue(ek.getMaxFlow() == 23);
Set nodesInS = ek.getNodesInSourcePartition();
assertEquals(4,nodesInS.size());
for (Number v : nodesInS) {
Assert.assertTrue(v.intValue() != 3 && v.intValue() != 5);
}
Set nodesInT = ek.getNodesInSinkPartition();
assertEquals(2,nodesInT.size());
for (Number v : nodesInT) {
Assert.assertTrue(v.intValue() == 3 || v.intValue() == 5);
}
Set minCutEdges = ek.getMinCutEdges();
int maxFlow = 0;
for (Number e : minCutEdges) {
Number flow = edgeFlowMap.get(e);
maxFlow += flow.intValue();
}
Assert.assertEquals(23,maxFlow);
Assert.assertEquals(3,minCutEdges.size());
}
public void testAnotherSimpleFlow() {
DirectedGraph graph = new DirectedSparseMultigraph();
Supplier edgeFactory = new Supplier() {
int count=0;
public Number get() {
return count++;
}
};
Map edgeCapacityMap = new HashMap();
for(int i=0; i<6; i++) {
graph.addVertex(i);
}
Map edgeFlowMap = new HashMap();
graph.addEdge(edgeFactory.get(),0,1,EdgeType.DIRECTED);
edgeCapacityMap.put(0,5);
graph.addEdge(edgeFactory.get(),0,2,EdgeType.DIRECTED);
edgeCapacityMap.put(1,3);
graph.addEdge(edgeFactory.get(),1,5,EdgeType.DIRECTED);
edgeCapacityMap.put(2,2);
graph.addEdge(edgeFactory.get(),1,2,EdgeType.DIRECTED);
edgeCapacityMap.put(3,8);
graph.addEdge(edgeFactory.get(),2,3,EdgeType.DIRECTED);
edgeCapacityMap.put(4,4);
graph.addEdge(edgeFactory.get(),2,4,EdgeType.DIRECTED);
edgeCapacityMap.put(5,2);
graph.addEdge(edgeFactory.get(),3,4,EdgeType.DIRECTED);
edgeCapacityMap.put(6,3);
graph.addEdge(edgeFactory.get(),3,5,EdgeType.DIRECTED);
edgeCapacityMap.put(7,6);
graph.addEdge(edgeFactory.get(),4,5,EdgeType.DIRECTED);
edgeCapacityMap.put(8,1);
EdmondsKarpMaxFlow ek =
new EdmondsKarpMaxFlow(
graph,
0,
5,
Functions.forMap(edgeCapacityMap, null),
edgeFlowMap,
edgeFactory);
ek.evaluate();
assertTrue(ek.getMaxFlow() == 7);
}
}
Ads help maintain this website.