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]
https://lists.boost.org/mailman/listinfo.cgi/boost-users