如何使用 Edmonds Karp Impl 定义割集？

Question

我正在使用 JGraphT，我正在使用 EdmondsKarpMFImpl。

问题是：如何定义整个边集 'participate' in min-cut.

我尝试使用 getCutEdges 方法，但它只有 returns 1 边。

我有下图：

(所有的边都有权重值(1)和剩余容量值(10))

public SimpleDirectedWeightedGraph generateAbilene(){

        Supplier<Integer> vSupplier3 = new Supplier<Integer>() {

            private int id = 1;

            @Override
            public Integer get() {
                return id++;
            }
        };

        SimpleDirectedWeightedGraph exGraph3 =
                new SimpleDirectedWeightedGraph<Integer, MyDefaultWeightedEdge>(vSupplier3, MyUtil.createDefaultWeightedEdgeSupplier());


        exGraph3.addVertex(1);
        exGraph3.addVertex(2);
        exGraph3.addVertex(3);
        exGraph3.addVertex(4);
        exGraph3.addVertex(5);
        exGraph3.addVertex(6);
        exGraph3.addVertex(7);
        exGraph3.addVertex(8);
        exGraph3.addVertex(9);
        exGraph3.addVertex(10);
        exGraph3.addVertex(11);


        exGraph3.addEdge(1,2);
        exGraph3.addEdge(1,7);
        exGraph3.addEdge(2,3);
        exGraph3.addEdge(3,4);
        exGraph3.addEdge(4,5);
        exGraph3.addEdge(6,7);
        exGraph3.addEdge(10,7);
        exGraph3.addEdge(7,8);
        exGraph3.addEdge(8,5);
        exGraph3.addEdge(8,9);
        exGraph3.addEdge(8,11);
    return exGraph3; 
}

并且使用该方法我仅获得源节点 (1) 和汇节点 (5) 之间的前 2 条边（1-2 和 1-7）

我想检索最小切割中的所有边。例如在上面的例子中它应该 return： 1-2, 1-7, 2-3, 7-8, 3-4, 8-5, 4-5 （关于边缘的顺序我不关心）

图形如下所示：

Answer 1

我认为您误解了最小割的定义。（加权）最小切割是两个不相交子集（比如 S 和 T）中的顶点的分区，使得边的权重之和 crossing 分区最小。在您的情况下，您特别要求最小 s-t 切割，这是最小切割的特定情况：在最小 s-t 切割中，您要求源顶点 (s) 是 S 的成员，并且汇点 t是 T 的成员。观察到在图中找到最小割的更一般的问题可能会产生一个解决方案，其中顶点 s 和 t 都在 same 分区中。

查看您的图表，s=1 和 t=5 的最小 s-t 切割为：S={1,2,6,7,10} 和 T={3,4,5,8 ,9,11}。穿过这些分区的边 ((2,3),(7,8)) 的总权重为 2，因此此切割的值为 2。类似地，您可以识别此图中具有相同值的其他 s-t 切割。

现在maximum flow min cut theorem告诉我们cut和flow之间的关系。如果我们要计算图中的最大 s-t 流量，其中 s=1 且 t=5，则最大流量最小割定理告诉我们，我们不能从 s 发送超过 2 个单位的流量到 t。此图中最大流量的示例：我们在路径 1-7-8-5 上发送 1 个流量单位，在路径 1-2-3-4-5 上发送 1 个流量单位，导致总流量为 2。

所以你似乎在寻找的不是最小切割问题的解决方案，而是最大流量问题的解决方案。特别是，您想要计算最大流问题中的哪些边具有正流值。当然，您可以使用 JGraphT 来获得这些结果。这是您的示例的清理版本：

public static void maxFlowMinCutExample(){
    Graph<Integer, DefaultWeightedEdge> graph =
            new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
    Graphs.addAllVertices(graph, Arrays.asList(1,2,3,4,5,6,7,8,9,10,11));

    //NOTE: by default, edges in jgrapht have a weight of 1.0. You would invoke graph.setEdgeWeight(.)
    //to change the edges' weight.
    graph.addEdge(1,2);
    graph.addEdge(1,7);
    graph.addEdge(2,3);
    graph.addEdge(3,4);
    graph.addEdge(4,5);
    graph.addEdge(6,7);
    graph.addEdge(10,7);
    graph.addEdge(7,8);
    graph.addEdge(8,5);
    graph.addEdge(8,9);
    graph.addEdge(8,11);

    //Calculate a Minimum Cut:
    minCut(graph, 1, 5);
    //Calculate a max flow:
    maxFlow(graph, 1, 5);
}

public static void minCut(Graph<Integer, DefaultWeightedEdge> graph, Integer source, Integer sink){
    MinimumSTCutAlgorithm<Integer, DefaultWeightedEdge> mc = new EdmondsKarpMFImpl<>(graph);
    System.out.println("Minimum s-t cut weight: "+mc.calculateMinCut(source, sink));
    System.out.println("Source partition S: "+mc.getSourcePartition());
    System.out.println("Sink partition T: "+mc.getSinkPartition());
    System.out.println("Cut edges (edges with their tail in S and their head in T): "+mc.getCutEdges());
}

public static void maxFlow(Graph<Integer, DefaultWeightedEdge> graph, Integer source, Integer sink){
    MaximumFlowAlgorithm<Integer, DefaultWeightedEdge> mf = new EdmondsKarpMFImpl<>(graph);
    MaximumFlowAlgorithm.MaximumFlow<DefaultWeightedEdge> flow = mf.getMaximumFlow(source, sink);
    System.out.println("Max flow value: "+flow.getValue());
    System.out.println("Edges with positive flow:");
    for(DefaultWeightedEdge edge : graph.edgeSet())
        if(flow.getFlow(edge) > 0)
            System.out.println("Edge: "+edge+" value: "+flow.getFlow(edge));
}

以上代码的输出：

Minimum s-t cut weight: 2.0
Source partition S: [1]
Sink partition T: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Cut edges (edges with their tail in S and their head in T): [(1 : 2), (1 : 7)]
Max flow value: 2.0
Edges with positive flow:
Edge: (1 : 2) value: 1.0
Edge: (1 : 7) value: 1.0
Edge: (2 : 3) value: 1.0
Edge: (3 : 4) value: 1.0
Edge: (4 : 5) value: 1.0
Edge: (7 : 8) value: 1.0
Edge: (8 : 5) value: 1.0

如何使用 Edmonds Karp Impl 定义割集？

How to define cut set with Edmonds Karp Impl?

jgrapht

edmonds-karp