我正在尝试使用 JUNG 的 EdmondsKarpMaxFlow 对象来查找有向图中所有节点对之间的最大流量。我创建了一个简单的有向图,并在每个节点组合上运行它,没有出现错误。这是供引用的工作示例: https://pastebin.com/TLsEduxZ
但是,当我在更复杂的图上调用相同的“edkAlg.evaluate()”代码时,循环每次都会在某个边/迭代处停止。
public class SomeClass{
...
...
MyEdmondsKarpMaxFlow edk = new MyEdmondsKarpMaxFlow(dirGraph);
edk.runEdk();
}
public class MyEdmondsKarpMaxFlow {
int edgeFlowMapId = 0;
protected DirectedSparseMultigraph<GraphElements.MyVertex, GraphElements.MyEdge> dirGraph;
protected Map<GraphElements.MyEdge, Double> edgeFlowMap = new HashMap<GraphElements.MyEdge, Double>();
protected Transformer<GraphElements.MyEdge, Double> capTransformer = new Transformer<GraphElements.MyEdge, Double>() {
public Double transform(GraphElements.MyEdge edge) {
return edge.getCapacity();
}
};
// This Factory produces new edges for use by the algorithm
protected Factory<GraphElements.MyEdge> edgeFactory = new Factory<GraphElements.MyEdge>() {
public GraphElements.MyEdge create() {
return new GraphElements.MyEdge(Integer.toString(edgeFlowMapId++));
}
};
public MyEdmondsKarpMaxFlow(DirectedSparseMultigraph<GraphElements.MyVertex, GraphElements.MyEdge> dirGraph) {
this.dirGraph = dirGraph;
}
public void runEdk() {
Collection<GraphElements.MyVertex> vertexCollection = dirGraph.getVertices();
for (Iterator iterator1 = vertexCollection.iterator(); iterator1.hasNext(); ) {
GraphElements.MyVertex v1 = (GraphElements.MyVertex) iterator1.next();
Collection<GraphElements.MyVertex> vertexCollection2 = dirGraph.getVertices();
for (Iterator iterator2 = vertexCollection2.iterator(); iterator2.hasNext(); ) {
GraphElements.MyVertex v2 = (GraphElements.MyVertex) iterator2.next();
if (v1.equals(v2)) continue;
EdmondsKarpMaxFlow<GraphElements.MyVertex, GraphElements.MyEdge> edkAlg = new EdmondsKarpMaxFlow(dirGraph, v1, v2, capTransformer, edgeFlowMap, edgeFactory);
edkAlg.evaluate();
System.out.println("max edk flow between v1 and v2 is : " + edkAlg.getMaxFlow());
}
}
System.out.println("FIN");
}
}
我使用顶点和边的自定义定义,其行为符合预期,但只是比简单示例具有更多属性。代码在前 201 次迭代之前都完美地找到了 v1 和 v2 之间的最大流,但每次之后都会陷入“.evaluate()”(它每次都使用相同的对顺序,因此总是陷入 ProblemNode123 ->问题节点456)。不太确定我哪里出错了,而且网上没有太多帮助,因此不胜感激!
最佳答案
您没有提供足够的信息来确定,但问题几乎肯定与您尚未定义 hashCode()
和 equals()
有关code> 用于自定义节点和边缘对象。
关于Java JUNG EdmondsKarpMaxFlow 陷入无限循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62071983/