我正试图在Java上学习Max-Flow算法。当我研究时,我发现了用于可视化和算法的Jung库,它为我工作。我可以计算出最大流量,但我不能看到每个边缘的计算流量。我想在可视化中像这个例子一样把流量写到边缘。在这里输入图像描述
代码。
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;
}
}
}
我看了一下文件http:/jung.sourceforge.netdocapieduuciicsjungalgorithmsflowsEdmondsKarpMaxFlow.html。). 当我使用getFlowGraph()时,我只能得到边缘的容量。它不显示Flow。我无法得到流量。有什么方法可以解决这个问题吗?有什么办法吗?
(来源 http:/www.grotto-networking.comJUNGBasicDirectedGraph.java)
你的 edgeFlowMap
将会被每个边缘的流量值填充,一旦 evaluate()
返回。
这一点诚然有些尴尬,也不是超级大发现,而是有 a 待办事项 来解决这个问题,这个问题应该在3.0版本中解决。