I am trying to learn the Max-Flow algorithm on Java. When I researched, I found the Jung library for visualization and algorithms and it worked for me. I can calculate the max flow but I can't see the calculated flow for each edge. I want to write flows to edge in visualization like this example: enter image description here
Code:
import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow;
import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath;
import edu.uci.ics.jung.graph.DirectedGraph;
import edu.uci.ics.jung.graph.DirectedSparseMultigraph;
import edu.uci.ics.jung.graph.util.EdgeType;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import org.apache.commons.collections15.Factory;
import org.apache.commons.collections15.Transformer;
public class example {
static int edgeCount = 0;
DirectedGraph<MyNode, MyLink> g;
MyNode n1, n2, n3, n4, n5, n6;
public example() {
}
public void constructGraph() {
g = new DirectedSparseMultigraph<MyNode, MyLink>();
n1 = new MyNode(1);
n2 = new MyNode(2);
n3 = new MyNode(3);
n4 = new MyNode(4);
n5 = new MyNode(5);
n6 = new MyNode(6);
g.addEdge(new MyLink(10), n1, n2, EdgeType.DIRECTED);
g.addEdge(new MyLink(10), n1, n3, EdgeType.DIRECTED);
g.addEdge(new MyLink(2), n2, n3, EdgeType.DIRECTED);
g.addEdge(new MyLink(4), n2, n4, EdgeType.DIRECTED);
g.addEdge(new MyLink(8), n2, n5, EdgeType.DIRECTED);
g.addEdge(new MyLink(9), n3, n5, EdgeType.DIRECTED);
g.addEdge(new MyLink(6), n5, n4, EdgeType.DIRECTED);
g.addEdge(new MyLink(10), n4, n6, EdgeType.DIRECTED);
g.addEdge(new MyLink(10), n5, n6, EdgeType.DIRECTED);
}
public void calcMaxFlow() {
Transformer<MyLink, Double> capTransformer = new Transformer<MyLink, Double>(){
public Double transform(MyLink link) {
return link.capacity;
}
};
Map<MyLink, Double> edgeFlowMap = new HashMap<MyLink, Double>();
Factory<MyLink> edgeFactory = new Factory<MyLink>() {
public MyLink create() {
return new MyLink(1);
}
};
EdmondsKarpMaxFlow<MyNode, MyLink> alg = new EdmondsKarpMaxFlow(g, n1, n6, capTransformer, edgeFlowMap,
edgeFactory);
alg.evaluate();
System.out.println("The max flow is: " + alg.getMaxFlow());
System.out.println("The edge set is: " + alg.getMinCutEdges().toString());
}
public static void main(String[] args) {
example myApp = new example();
myApp.constructGraph();
System.out.println(myApp.g.toString());
myApp.calcMaxFlow();
}
class MyNode {
int id;
public MyNode(int id) {
this.id = id;
}
public String toString() {
return "V"+id;
}
}
class MyLink {
double capacity;
int id;
public MyLink(double capacity) {
this.id = edgeCount++;
this.capacity = capacity;
}
public String toString() {
return "E"+id;
}
}
}
I looked at document (http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/flows/EdmondsKarpMaxFlow.html). When I use getFlowGraph() I was able to get only the capacity of the edge. It doesn't show Flow. I couldn't get flow. Is there any way for this? Thanks.
(Source: http://www.grotto-networking.com/JUNG/BasicDirectedGraph.java)
Your edgeFlowMap
will be populated by the flow value for each edge once evaluate()
returns:
EdmondsKarpMaxFlow constructor
This is admittedly somewhat awkward and not super-discoverable; there's a TODO to fix this, which should be addressed in the 3.0 release.