- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我有一些简单的 Java/JUNG 代码,可以创建有向图,添加一些带有权重和容量值的边,并运行从源节点到汇节点的最大流量分析。
如果你有:A --- (capacity 2) -----> B ---- (capacity 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 The max flow is: 48
如何编写一个算法,使其在每对可能的源和接收器上运行,以便我可以看到图中所有路径的最大流量?对这个东西完全陌生,所以任何东西都有帮助!
最佳答案
只需为每对节点运行算法即可。没有已知的算法对于有向图更有效:All pair Maximum Flow
关于java - 如何使用 JUNG 的 Edmonds Karp 获得每个可能的源/汇节点对的最大流量?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61330222/
我正在尝试更详细地了解 Edmonds-Karp 算法,并且很想知道它使用什么算法计算每次迭代中从 s 到 t 的最短路径(最少边数) 最佳答案 广度优先搜索。您可能想阅读 Wikipedia ent
我在整个互联网上进行了搜索,试图找到 PHP 示例代码,但我无法找到。我想做的是将类(class)与房间匹配,类(class)有一组与之兼容的房间。 示例:类(class) A 可以在 X、Y 和 Z
我会实现 Edmond Karp algorithm ,但它似乎不正确,我没有得到正确的流程,请考虑下图和从 4 到 8 的流程: 算法运行如下: 首先找到4→1→8,然后找到4→5→8之后4→1→6
我使用在 Edmonds–Karp 算法维基页面中找到的伪代码实现了 Edmonds–Karp 算法:http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp
我正在为一个有向图实现这个算法。但有趣的是,这个图节点也有自己的流量。我认为,必须以特殊的方式处理原始问题的这种细微变化。因为,在最初的最大流问题中,可以找到从头到尾的任何路径(实际上,在 Edmon
我正在尝试实现 Edmonds-Karp在 C++ 中以获得最大流量,我写的略有不同: 我没有遍历残差图中的所有边,而是使用邻接表仅遍历了原始图中存在的边。 在用最小流量更新残差图时,我没有更新任何后
我想在加权有向图上找到最小生成树 (MST)。我一直在尝试使用 Chu-Liu/Edmond's algorithm ,我已经用 Python 实现了(下面的代码)。可以找到对该算法的简单、清晰的描述
我喜欢在有向图中(有时可能有环)找到最小生成树(甚至森林)。一个解释here有一些错误。这个算法在 Python 中是否有任何实际有效的包/代码? 最佳答案 虽然我没用过,here是来自 GitHub
在深入探讨这个问题之前,先了解一下我已有的一些背景信息: -我首先创建了一个基于美国各城市的无向邻接矩阵图,边权重为计算的距离(通过距离公式实现)。 -我还使用 prim 算法实现了最小生成树。 现在
我有一些简单的 Java/JUNG 代码,可以创建有向图,添加一些带有权重和容量值的边,并运行从源节点到汇节点的最大流量分析。 如果你有:A --- (capacity 2) -----> B ---
我是一名优秀的程序员,十分优秀!