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

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

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

Boost - Users mailing list
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!

Boost-users mailing list
[hidden email]