[BGL] minimum cut separating two given vertices on undirected graph

From: Ziye Tang (ziyet_at_[hidden])
Date: 2019-10-18 02:52:56

Hi all,

This is my first time posting, and I've read the posting guideline. I might
still make some mistakes in the posting style. In particular, I am not sure
how to insert code snippet into email. Please let me know when I do make
such mistakes.

I need to find a min-cut separating a given pair of vertices on an
undirected graph. Conceptually this is how I would solve it: first I
bidirect the graph, treat one vertex as the source and the other as the
sink. Then run any max flow algorithm from source to sink. When the
algorithm finishes, in the residual graph, identify connected component
which contains a given vertex. This gives the min-cut.

In order to implement it, I use push_relabel_max_flow. According to the doc
I need to augment each edge with a reverse edge. Since I bi-directed the
graph already, this would give rise to a multi-graph where each edge, say
(i,j) has two copies, with the first copy treated as the `true' edge and
the second copy as the reverse edge of arc (j,i). Then I set capacity and
residual capacity map accordingly. But now I am getting a segmentation
error when calling push_relabel_max_flow. Could you help me understand what
is going on? I've attached my code snippet below. Here g is my graph, n is
the number of vertices, xval is a 2 by 2 positive matrix where each
corresponding entry is the capacity of the edge.

for (int i=0; i<n; i++)
    for (int j=i+1; j<n; j++) {
        graph_traits<Graph>::out_edge_iterator e_start, e_end,
            e_start2, e_end2;;
        boost::tie(e_start, e_end) = boost::edge_range(i,j,g);
        // check if an edge exists
        if (e_start == e_end) continue;
        boost::tie(e_start2, e_end2) = boost::edge_range(j,i,g);
        // set reverse edge, set its capacity to be zero
        g[*e_start].rev = *(--e_end2);
        g[*e_start2].rev = *(--e_end);
        g[*e_start].capacity = xval[i][j];
        g[*e_start].res_capacity = xval[i][j];
        g[*e_start2].capacity = xval[i][j];
        g[*e_start2].res_capacity = xval[i][j];
        // now end points to the second parallel edge
        g[*e_end].capacity = 0;
        g[*e_end].res_capacity = 0;
        g[*e_end2].capacity = 0;
        g[*e_end2].res_capacity = 0;
            //g[e].rev = boost::edge(j,i,g).first;
            std::cout << "(" << i << ", " << j <<
                "): " << g[*e_start].capacity << ", " <<
g[*e_start2].capacity << endl;
        }

Thanks in advance!