java - 如何使用 JUNG 的 Edmonds Karp 获得每个可能的源/汇节点对的最大流量?
问题描述
我有一些简单的 Java/JUNG 代码,可以创建有向图,添加一些带有权重和容量值的边,并运行从源节点到汇节点的最大流量分析。
如果您有:A --- (容量 2) -----> B ---- (容量 5)----> C 并且想从 A->C 中找到最大流量,它将是 2。
import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow;
import edu.uci.ics.jung.graph.DirectedSparseMultigraph;
import edu.uci.ics.jung.graph.util.EdgeType;
import org.apache.commons.collections15.Factory;
import org.apache.commons.collections15.Transformer;
import java.util.HashMap;
import java.util.Map;
public class stack {
static int edgeCount = 0;
static class MyNode {
int id;
public MyNode(int id) {
this.id = id;
}
public String toString() {
return "V"+id;
}
}
static class MyLink {
double capacity;
double weight;
int id;
public MyLink(double weight, double capacity) {
this.id = edgeCount++;
this.weight = weight;
this.capacity = capacity;
}
public String toString() {
return "E"+id;
}
}
public static void main(String[] args){
DirectedSparseMultigraph<MyNode, MyLink> g = new DirectedSparseMultigraph<MyNode, MyLink>();
Transformer<MyLink, Double> capTransformer = new Transformer<MyLink, Double>(){
public Double transform(MyLink link) {
return link.capacity;
}
};
Map<MyLink, Double> edgeFlowMap = new HashMap<MyLink, Double>();
// This Factory produces new edges for use by the algorithm
Factory<MyLink> edgeFactory = new Factory<MyLink>() {
public MyLink create() {
return new MyLink(1.0, 1.0);
}
};
// Create some MyNode objects to use as vertices
MyNode n1 = new MyNode(1);
MyNode n2 = new MyNode(2);
MyNode n3 = new MyNode(3);
MyNode n4 = new MyNode(4);
MyNode n5 = new MyNode(5);
MyNode n6 = new MyNode(6);
MyNode n7 = new MyNode(7);
// Add some directed edges along with the vertices to the graph
g.addEdge(new MyLink(2.0, 48),n1, n2, EdgeType.DIRECTED);
g.addEdge(new MyLink(2.0, 58),n2, n3, EdgeType.DIRECTED);
g.addEdge(new MyLink(3.0, 192), n3, n5, EdgeType.DIRECTED);
g.addEdge(new MyLink(2.0, 48), n5, n4, EdgeType.DIRECTED);
g.addEdge(new MyLink(2.0, 20), n6, n1, EdgeType.DIRECTED);
g.addEdge(new MyLink(8, 24), n7, n4, EdgeType.DIRECTED);
System.out.println("RUNNING EDMONDS KARP MAX FLOW FOR SOURCE " + n1.toString() + " TO SINK " + n2.toString());
EdmondsKarpMaxFlow<MyNode, MyLink> edk = new EdmondsKarpMaxFlow(g, n1, n2, capTransformer, edgeFlowMap, edgeFactory);
edk.evaluate();
System.out.println("The max flow is: " + edk.getMaxFlow());
}
}
运行它将输出:
RUNNING EDMONDS KARP MAX FLOW FOR SOURCE V1 TO SINK V2 最大流量为:48
如何编写算法以使其在每对可能的源和接收器上运行,以便我可以看到图中所有路径的最大流量?对这些东西完全陌生,所以任何东西都有帮助!
解决方案
只需为每对节点运行算法。没有已知算法对有向图更有效:All pair Maximum Flow
推荐阅读
- wpf - 如何在 WPF xaml 中单击 datepicker 时仅显示月份
- continuous-integration - Knative:更新 CI 自动部署管道中的服务映像
- javascript - javascript中的微任务和宏任务有什么区别?
- sparql - 在 SPARQL 中按 ObjectProperty 显示
- android - 无法在android中选择微调器项目
- pdf - 编辑 Oracle APEX 后将 iFrame 中加载的 pdf 文件保存到数据库
- r - 如何在 R 中创建三分位数
- javascript - 为什么括号在这个创建 JavaScript 对象的 .reduce() 语法中的作用?
- jquery - 添加由 jquery append 方法生成的事件
- javascript - dict 不为空时的 ng-show