1

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

问题是：如何定义整个边集什么是最小切割中的“参与”。

我尝试使用该 getCutEdges方法，但它只返回 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; 
}

使用这种方法，我只能在 Source 节点 (1) 和 Sink 节点 (5) 之间获得前 2 条边 (1-2 & 1-7)

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

图表如下所示：

最小干扰路由示例图

4

1 回答 1

1

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

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

现在最大流最小割定理告诉我们割和流之间的关系。如果我们要在您的图中计算最大 st 流，其中 s=1 和 t=5，最大流最小割定理告诉我们，我们不能将超过 2 个单位的流从 s 发送到 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
于 2021-10-04T18:37:46.017 回答