如何使用荣格的埃德蒙兹卡普获得每个边缘的流动？

Question

我正在尝试在Java上学习Max-Flow算法。当我研究时，我找到了用于可视化和算法的荣格库，它对我有用。我可以计算最大流量，但看不到每个边的计算流量。我想在可视化中将流写入边缘，如以下示例所示： 在此处输入图像描述

法典：

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.net/doc/api/edu/uci/ics/jung/algorithms/flows/EdmondsKarpMaxFlow.html(。当我使用 getFlowGraph(( 时，我只能获得边缘的容量。它不显示流。我无法获得流量。有什么办法吗？谢谢。

(来源：http://www.grotto-networking.com/JUNG/BasicDirectedGraph.java(

Answer 1

一旦返回evaluate()，您的edgeFlowMap将由每条边的流值填充：

EdmondsKarpMaxFlow 构造函数

诚然，这有点尴尬，而且不是超级可发现的;有一个TODO可以解决这个问题，这应该在3.0版本中解决。