3 classes (0, 1, 4) on the Boost graph

Question

I get strange results when I use the BGL function boykov_kolmogorov_max_flow (). Although I would see 2 classes (0-1 or something else, but only 2!), But I often see three classes: 0, 1 and 4.

For example, using the image below with

• source: middle pixel on the left border
• sink: middle pixel on the right border
• horizontal edge cost = 10 * e ^ (rightPixel / 50)
• vertical edge code = 0.1.

I get the following results:

444444444444400000000000000000 444444444444440000000000000000 444444444444440000000000000000 444444444444440000000000000000 444444444444444000000000000000 444444444444444000000000000000 444444444444444000000000000000 444444444444444000000000000000 444444444444444000000000000000 444444444444444000000000000000 444444444444444411000000000000 444444444444444444000000000000 444444444444444444000000000000 444444444444444444000000000000 444444444441111111000000000000 444444444440000000000000000000 444444444440000000000000000000 444444444440000000000000000000 444444444440000000000000000000 444444444444000000000000000000 444444444444000000000000000000 444444444444100000000000000000 444444444444110000000000000000 444444444444110000000000000000 444444444444411000000000000000 444444444444444400000000000000 444444444444444400000000000000 444444444444444400000000000000 444444444444444400000000000000 444444444444444400000000000000 

Can someone explain the real meaning of these classes? I'm sure 4 is the source class and 0 is the shell class, but what about 1? I did not find anything in the documentation. I think this means an “unsure” horizontal zone, but why does this mean that?!?

Second question. Are they reliable? Can I use them to find a smoother border, as in the image below? The goal would be to select one of the green pixels instead of the red, which is too far to the right. I mean, I know that I could use 1 in this case to do this, but can I trust them to be there when I need them? :)

Thank you for your time.

Answer 1

In your example:

 boykov_kolmogorov_max_flow(graph, make_iterator_property_map(&capacity[0], get(boost::edge_index, graph)), make_iterator_property_map(&residual_capacity[0], get(boost::edge_index, graph)), make_iterator_property_map(&reverse_edges[0], get(boost::edge_index, graph)), //CHANGED make_iterator_property_map(&groups[0], get(boost::vertex_index, graph)), get(boost::vertex_index, graph), s, t ); 

They call the following constructor from here :

 boykov_kolmogorov_max_flow(Graph& g, CapacityEdgeMap cap, ResidualCapacityEdgeMap res_cap, ReverseEdgeMap rev, ColorMap color, IndexMap idx, typename graph_traits<Graph>::vertex_descriptor src, typename graph_traits<Graph>::vertex_descriptor sink) 

This means that what you consider classes are really colors. According to the documentation ,

If the color of the vertex after the algorithm is run is black, the vertex belongs to the source tree, otherwise it belongs to the sink tree (used for minimal cuts).

Now, if you look at the default color map here , the colors are an enumeration going from 0 to 4, where 4 is black.

With all this, you can conclude that 4 is indeed the source, but everything else (including 1's) belongs to the sink!

The different color probably depends on the implementation itself, but I don’t think you can make any assumptions about it without knowing what the implementation is ...