On Mar 18, 2005, at 8:10 AM, Matthias Linkenheil wrote:
tie(e1, in1) = add_edge(vertex(node_nr, g), vertex(right, g), g); tie(e2, in2) = add_edge(vertex(right, g), vertex(node_nr, g), g); if (in1 && in2){ cap[e1] = cap_ptr->cap; cap[e2] = cap_ptr->inv_cap; rev_edge[e1] = e2; rev_edge[e2] = e1; }
*cap_ptr=myintensity.get_cap_below(node_nr, below);
tie(e1, in1) = add_edge(vertex(node_nr, g), vertex(below, g), g); tie(e2, in2) = add_edge(vertex(below, g), vertex(node_nr, g), g); if (in1 && in2){ cap[e1] = cap_ptr->cap; cap[e2] = cap_ptr->inv_cap; rev_edge[e1] = e2; rev_edge[e2] = e1; } ++matrix_counter; } ++matrix_counter; } matrix_counter = ((x_size*y_size)-x_size); for (int spalten_counter = 0; spalten_counter <= (x_size-2); ++spalten_counter){ node_nr = matrix_counter; right = matrix_counter + 1;
*cap_ptr=myintensity.get_cap_right(node_nr, right);
tie(e1, in1) = add_edge(vertex(node_nr, g), vertex(right, g), g); tie(e2, in2) = add_edge(vertex(right, g), vertex(node_nr, g), g); if (in1 && in2){ cap[e1] = cap_ptr->cap; cap[e2] = cap_ptr->inv_cap; rev_edge[e1] = e2; rev_edge[e2] = e1; }
I'm not sure if the initialization of the graph is correct for the max-flow algorithms. For each edge (u, v) the graph needs an edge (v, u) such that the rev_edge map maps back and forth (okay so far) and the capacity of (v, u) is zero (I'm just quoting from the push_relabel_max_flow docs). However, it looks like the capacity of the reverse edge (called "e2" in the above snippets) is always set to cap_ptr->inv_cap, which is not necessarily zero. If I change the capacity of these reverse edges to 0, the example completes and gives a max_flow of 0 (with both max-flow algorithms). However, I don't have enough of an understanding of max-flow problems to know whether that is a reasonably answer or not :( Doug