CutGrid finds a minimal cut in an arbitrary planar grid graph, i.e., in a planar graph such that every node in an mxn grid is a vertex of the graph:
In order to compute the cut, the following steps have to be performed:
In the following sections, we explain these steps with respect to the graph sketched in the image above.
When we define the capacity of each edge, we can either do this by overwriting CutGrid::edgeCost or by calling CutGrid::setEdgeCostFunction. In this simple example we use the latter alternative:
Now, we have to compute the maximum flow. In order to do this via CutGrid, we have to initialize CutGrid with the previously defined edge function as well as a source and a sink:
Finally, we have to compute the value of the maximum flow. This is the most time consuming method of the class and is called via
For most applications, we are not only interested in the value of the minimum cut, but also in the cut itself. The classical way in describing this cut is to assign a binary labeling to each vertex of the graph. This labeling can be provided via CutGrid::getLabel or CutGrid::getLabels
The complete code can be seen here: cutgrid.cpp.