How to define cut set with Edmonds Karp Impl?

Question

I'm using JGraphT, and I'm using EdmondsKarpMFImpl.

The question is: How to define the whole set of edges what is 'participate' in min-cut.

I tried to use the getCutEdges method, but it only returns 1 edge.

I have the following graph:

(all the edges has a weight value(1) and a residual capacity value(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; 
}

And with that method I only get the first 2 edge(1-2 & 1-7) between the Source node (1) and the Sink node (5)

I want to retrieve all the edges in the min cut. For example in the case above it should return: 1-2, 1-7, 2-3, 7-8, 3-4, 8-5, 4-5 (about the order of the edges I do not care)

The Graph looks like this:

Answer 1

I think you are misinterpreting the definition of a minimum cut. A (weighted) min cut is a partitioning of the vertices in two disjoint subsets (say S and T) such that the sum of the weights of edges crossing the partition is minimum. In your case, you are specifically asking for a minimum s-t cut, which is a specific case of a minimum cut: in the minimum s-t cut, you require that the source vertex (s) is a member of S, and the sink vertex t is a member of T. Observe that the more general problem of finding a minimum cut in the graph could yield a solution where both vertices s and t are in the same partition.

Looking at your graph, a minimum s-t cut with s=1 and t=5, would be: S={1,2,6,7,10} and T={3,4,5,8,9,11}. The total weight of the edges ((2,3),(7,8)) crossing these partitions is 2, so this cut has value 2. Similarly, you can identify other s-t cuts in this graph with the same value.

Now the maximum flow min cut theorem tells us the relation between a cut and a flow. If we were to compute a max s-t flow in your graph, with s=1 and t=5, the max flow min cut theorem tells us that we cannot send more than 2 units of flow from s to t. An example of a max flow in this graph: we send 1 unit of flow on the path 1-7-8-5 and 1 unit on the path 1-2-3-4-5 resulting in a total flow of 2.

So what you seem to be looking for, is not a solution to the min cut problem, but a solution to the max flow problem. In particular, you want to compute which edges in the max flow problem have a positive flow value. Naturally, you can use JGraphT to get these results. Here's a cleaned-up version of your example:

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));
}

The output of the above code:

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