如何使用 Jung 的 Edmonds Karp 获得每条边的流动？

Question

我正在尝试学习 Java 上的 Max-Flow 算法。当我研究时，我发现了用于可视化和算法的 Jung 库，它对我很有用。我可以计算最大流量，但看不到每条边的计算流量。我想像这个例子一样在可视化中将流写到边缘： enter image description here

代码：

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

您的 edgeFlowMap 将由每条边的流量值填充一次 evaluate() returns:

EdmondsKarpMaxFlow constructor

诚然，这有点尴尬，而且不太容易被发现； a TODO 可以解决这个问题，应该在 3.0 版本中解决。

如何使用 Jung 的 Edmonds Karp 获得每条边的流动？

How to get flow for every edge using Jung's Edmonds Karp?

java

graph

jung

max-flow

edmonds-karp