Unexpected results applying maxflow algorithm

[Rowandish]

I'm trying to get the max flow/min cut of the following graph:

The function g.get_grid_segments(nodeid) gives me the following output:

[[False False True True True True]
 [False False False True True True]
 [False False False True True True]
 [False False False False True True]
 [False False False False False True]]

That corresponds to the following cut (the blue one): It corresponds to a total capacity of 6 but I think that the correct cut is the green one, that corresponds to a total capacity of 4.

Did I miss something?

Thank you very much for your help!

[pmneila]

Hi,

The blue cut has a capacity 18 (5 + 4 + 3 + 3 + 2 + 1) while the green cut has a capacity 32 (9 + 8 + 5 + 4 + 3 + 2 + 1), so the blue cut is better (lower) than the green cut.

What do you mean with "a total capacity of 6" for the blue cut? I don't understand that.

[Rowandish]

With "total capacity" I mean the result of the function g.maxflow(): sorry but I noticed that the image is almost unreadable: the vertical edges has a negative weights (if you zoom the image you should see them). I obtain the following output:

• Blue one: 5 - 4 + 3 + 3 - 2 + 1 = 6
• Green one: 9 - 8 + 5 - 4 + 3 - 2 + 1 = 4 Thanks!

[pmneila]

Oh, sorry. I did not see the - symbol.

Maximum flow problems are defined only for positive capacities, and the maxflow algorithm assumes that. In fact, I'm not very sure what a negative capacity means.

The methods add_tedge and add_grid_tedges do allow negative capacities for the terminal edges, but that is because setting a negative capacity in a s-->i edge is equivalent to setting a positive capacity of same magnitude to the i-->t edge.

Is this a test graph or do you need negative weights in a real world application?

[Rowandish]

I need negative weights in my problem, is there workaround to map negative weights in positive ones and get the same result? I can not find the right solution for this problem...

Thank you!

[pmneila]

If you can give me more details about where your weights come from I might be able to think if an alternative is possible.

Unfortunately, if you really need negative weights there is no easy workaround.

Negative weights mean that your energy is not submodular. Basically, "submodular" means that you are encouraging at least two nodes to be separated by the minimum cut, i.e., separating two nodes has a lower cost than not separating them.

It is well known that graph-cuts can only minimize submodular energies, i.e., they cannot deal with negative weights. There are approaches to extend them to non-submodular energies, but the results are not very good in general. Approximate methods, such as belief propagation, are more suitable than graph-cuts for that kind of problems.

[Rowandish]

As you have seen I'm not so expert in graph cut, thank you for your useful information.

I have a collaboration with @ProGM to implement an algorithm for image processing, our graph represents a sequence of pixels that starts from the bottom of the image and must be connected according to the following rule: We have three energy functions that represent the cost of crossing from one pixel to one of the three possible directions upwards for each step. The structure of the graph shown in the previous posts is inspired by a known structure and it is used to get the monotonicity and the connectivity of the cuts. The horizontal arc weight represents the up direction energy (from 0 to 2) while the two vertical edges weights represents the two diagonal energy (from 0 to 1 and from 0 to 3). The problem is that when the cut is completely vertical energies are weighed properly while when we have a diagonal cut the horizontal arc weight is added to the vertical arc weight and so the result is wrong. We solved the problem substracting the upper weight to the vertical weight but the result is often a negative number and so the maxflow doesn't work. Now we are working to solve this problem and obtain an equivalent graph without using negative weights. We understand that it is difficult to explain and understand but if you have any idea it would be really really appreciated!

[pmneila]

I understand. In the work you cite the cost of moving up-left (or up-right) is equal to the cost of going up plus the cost of going left (or right), so the capacities of the vertical edges are the costs of going left and right (see here in Section 5.1 the definitions for C_L, C_U and C_R and note that C_L and C_R are equal to the cost of going up C_U plus the cost of going left or right). Therefore, in their case, for the cut in your example, the cost would be up2 + up1 + left, and that is correct.

How do you define your weights for your problem? Couldn't you force the cost of going up-left and up-right to be always higher than the cost of going up?

[Rowandish]

You understand exactly my problem. I think the only solution if forcing the cost of going up-left and up-right to be always higher than the cost of going up, as you said in your previous answer. Thank you for your help, it was really really useful!

[pmneila]

You are welcome. Don't hesitate to ask more questions!