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

CutPlanar finds a minimal cut in an arbitrary planar graph, i.e., in a graph that can be embedded into the plane. Instead of an explicit embedding of vertices and edges, an algebraic embedding is used.
This embedding is given by a counter-clockwise order of all edges that are adjacent to a given vertex:

introGraph.png
Example of a Planar Graph

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

  1. Define the planar embedding.
  2. Compute the maximum flow with respect to a source and a sink.
  3. Extract the minimal cut as a vertex-based or an edge-based representation.

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

Planar Embedding

First, we have to define the algebraic embedding of the planar graph. To do this, we construct an array of 9 vertices, an array of 13 edges and an array of 6 faces (Face A, ..., Face F):

PlanarVertex vertex[ 9];
PlanarEdge edge[13];
PlanarFace face[ 6];

Next, we define the edges by providing a start and a target vertex as well as a left and a right face. In this example, we assume an undirected edge with unit capacity, i.e., the capacity in both directions is 1.

edge[ 0].setEdge(vertex+0, vertex+1, face+5, face+0, 1, 1);
edge[ 1].setEdge(vertex+0, vertex+2, face+0, face+1, 1, 1);
edge[ 2].setEdge(vertex+0, vertex+3, face+1, face+5, 1, 1);
edge[ 3].setEdge(vertex+1, vertex+2, face+2, face+0, 1, 1);
edge[ 4].setEdge(vertex+2, vertex+3, face+3, face+1, 1, 1);
edge[ 5].setEdge(vertex+1, vertex+6, face+5, face+2, 1, 1);
edge[ 6].setEdge(vertex+2, vertex+4, face+2, face+3, 1, 1);
edge[ 7].setEdge(vertex+3, vertex+5, face+3, face+5, 1, 1);
edge[ 8].setEdge(vertex+4, vertex+5, face+4, face+3, 1, 1);
edge[ 9].setEdge(vertex+4, vertex+7, face+2, face+4, 1, 1);
edge[10].setEdge(vertex+5, vertex+8, face+4, face+5, 1, 1);
edge[11].setEdge(vertex+6, vertex+7, face+5, face+2, 1, 1);
edge[12].setEdge(vertex+7, vertex+8, face+5, face+4, 1, 1);

Finally, to every vertex a list of adjacent edges has to be provided. The edges in every list are ordered in a counter-clockwise sense.

PlanarEdge *edges_CCW[4]; // every vertex has at most four adjacent edges
edges_CCW[0] = edge+ 0; edges_CCW[1] = edge+ 2; edges_CCW[2] = edge+ 1;
vertex[0].setEdgesCCW(edges_CCW, 3);
edges_CCW[0] = edge+ 0; edges_CCW[1] = edge+ 3; edges_CCW[2] = edge+ 5;
vertex[1].setEdgesCCW(edges_CCW, 3);
edges_CCW[0] = edge+ 1; edges_CCW[1] = edge+ 4; edges_CCW[2] = edge+ 6; edges_CCW[3] = edge+ 3;
vertex[2].setEdgesCCW(edges_CCW, 4);
edges_CCW[0] = edge+ 2; edges_CCW[1] = edge+ 7; edges_CCW[2] = edge+ 4;
vertex[3].setEdgesCCW(edges_CCW, 3);
edges_CCW[0] = edge+ 6; edges_CCW[1] = edge+ 8; edges_CCW[2] = edge+ 9;
vertex[4].setEdgesCCW(edges_CCW, 3);
edges_CCW[0] = edge+ 7; edges_CCW[1] = edge+10; edges_CCW[2] = edge+ 8;
vertex[5].setEdgesCCW(edges_CCW, 3);
edges_CCW[0] = edge+ 5; edges_CCW[1] = edge+11;
vertex[6].setEdgesCCW(edges_CCW, 2);
edges_CCW[0] = edge+ 9; edges_CCW[1] = edge+12; edges_CCW[2] = edge+11;
vertex[7].setEdgesCCW(edges_CCW, 3);
edges_CCW[0] = edge+10; edges_CCW[1] = edge+12;
vertex[8].setEdgesCCW(edges_CCW, 2);

Maximum Flow

Now, we have to compute the maximum flow. In order to do this via CutPlanar, we have to initialize CutPlanar with the planar graph as well as a source and a sink.

CutPlanar planar_cut;
planar_cut.initialize(9,vertex, 13,edge, 6,face);
planar_cut.setSource(2);
planar_cut.setSink (6);

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 = planar_cut.getMaxFlow();

Extract 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 CutPlanar::getLabel or CutPlanar::getLabels

vector<int> labels;
label = planar_cut.getLabel(5); // returns 'CutPlanar::LABEL_SOURCE'
label = planar_cut.getLabel(6); // returns 'CutPlanar::LABEL_SINK'
labels = planar_cut.getLabels(CutPlanar::LABEL_SOURCE); // returns {0,1,2,3,4,5,7,8}
labels = planar_cut.getLabels(CutPlanar::LABEL_SINK); // returns {6}

It is known that the edges of a planar cut define a closed path in the dual graph. To extract either this path or the vertices at the boundary of this path, the methods CutPlanar::getCircularPath and CutPlanar::getCutBoundary are provided

vector<int> dual_path;
vector<int> boundary;
dual_path = planar_cut.getCircularPath(); // returns face IDs {5,2}
boundary = planar_cut.getCutBoundary(CutPlanar::LABEL_SOURCE); // returns vertex IDs {7,1}
boundary = planar_cut.getCutBoundary(CutPlanar::LABEL_SINK); // returns vertex IDs {6,6}

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

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