PlanarGC  1.0.2
 All Data Structures Functions Variables Enumerations Enumerator Friends Pages
Tutorial: CutGrid

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:

introGrid.png
Example of a Grid Graph

In order to compute the cut, the following steps have to be performed:

  1. Define the edges' capacity of the graph.
  2. Compute the maximum flow with respect to a source and a sink.
  3. Extract the minimal cut as a vertex-based representation.

In the following sections, we explain these steps with respect to the graph sketched in the image above.

Edges' Capacity

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:

CapType edgeCost3x3(int row, int col, CutGrid::EDir dir) {
if ((dir == CutGrid::DIR_SOUTH) || (dir == CutGrid::DIR_NORTH)) return 3;
if ((dir == CutGrid::DIR_EAST) && (col == 0)) return 6;
if ((dir == CutGrid::DIR_WEST) && (col == 1)) return 6;
if (row == 0) return 10;
if (row == 1) return 9;
return 4;
}

Maximum Flow

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:

CutGrid grid_cut(3,3); // defines a 3x3 grid
grid_cut.setEdgeCostFunction(edgeCost3x3); // use the previously defined edge cost function
grid_cut.setSource(1,0);
grid_cut.setSink(0,2);

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

double flow;
flow = grid_cut.getMaxFlow();

Extract the Minimal Cut

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

label = grid_cut.getLabel(1,2); // returns 'CutPlanar::LABEL_SOURCE'
label = grid_cut.getLabel(0,0); // returns 'CutPlanar::LABEL_SINK'
labels = new CutPlanar::ELabel[9];
grid_cut.getLabels(labels); // sets {T,T,T,S,S,S,S,S,S}
// with S = CutPlanar::LABEL_SOURCE
// and T = CutPlanar::LABEL_SINK

The complete code can be seen here: cutgrid.cpp.

© 2009 - 2013 by Eno Töppe, Frank R. Schmidt
generated by Doxygen