PlanarGC  1.0.2
 All Data Structures Functions Variables Enumerations Enumerator Friends Pages
CutPlanar Class Reference

#include <CutPlanar.h>

Public Types

enum  ECheckFlags {
  CHECK_NONE = 0x00,
  CHECK_CONNECTIVITY = 0x01,
  CHECK_NON_NEGATIVE_COST = 0x02,
  CHECK_PLANARITY = 0x04,
  CHECK_ALL = 0xFF
}
enum  ELabel {
  LABEL_SINK = 0,
  LABEL_SOURCE = 1
}

Public Member Functions

 CutPlanar ()
virtual ~CutPlanar ()
void initialize (int numVerts, PlanarVertex *vertexList, int numEdges, PlanarEdge *edgeList, int numFaces, PlanarFace *faceList, int idxSource=FIRST_VERT, int idxSink=LAST_VERT, ECheckFlags checkInput=CHECK_ALL)
void setSource (int idxSource)
void setSink (int idxSink)
double getMaxFlow ()
ELabel getLabel (int node)
std::vector< int > getLabels (ELabel label)
std::vector< int > getCutBoundary (ELabel label)
std::vector< int > getCircularPath ()

Static Public Attributes

static const int FIRST_VERT = 0
static const int LAST_VERT = -1

Protected Member Functions

virtual void preFlow ()
virtual void performChecks (ECheckFlags checks)

Detailed Description

CutPlanar computes a graph cut of a planar graph provided as arrays of PlanarVertex, PlanarEdge and PlanarFace. These arrays also provide a natural ordering of the vertices.

The graph can be defined via CutPlanar::initialize, CutPlanar::setSource and CutPlanar::setSink.

The result of computing the graph cut can then be retrieved via CutPlanar::getMaxFlow, CutPlanar::getLabel, CutPlanar::getLabels or CutPlanar::getCutBoundary. As soon as one of these methods is called, the computation of the graph cut will be performed internally. This computation will only be repeated, if the setup via CutPlanar::initialize, CutPlanar::setSource or CutPlanar::setSink was changed. Otherwise, all these four retrieval methods can be called without recomputing the graph cut.

Examples:
cutplanar.cpp.

Member Enumeration Documentation

This type is used by CutPlanar::initialize in order to define what kind of sanity checks should be performed on the input data. If the data is expected to be correct, CHECK_NONE should be chosen. If the data may be corrupted, CHECK_ALL is recommended.

If only certain tests should be performed, the enumeration elements that correspond to specific tests can be added, e.g. CHECK_CONNECTIVITY+CHECK_PLANARITY.

Enumerator:
CHECK_NONE 

For efficiency reasons, no tests will be performed.

CHECK_CONNECTIVITY 

Test whether the graph consists of one connected component.

CHECK_NON_NEGATIVE_COST 

Test whether all edge-costs are non-negative.

CHECK_PLANARITY 

Perform some sanity checks whether the provided graph is planar.

CHECK_ALL 

For safety reasons, all mentioned tests are performed.

This type is used to specify the label associated with the source and the sink of the graph.

Enumerator:
LABEL_SINK 

Label associated with the sink.

LABEL_SOURCE 

Label associated with the source.

Constructor & Destructor Documentation

CutPlanar::CutPlanar ( )
CutPlanar::~CutPlanar ( )
virtual

Member Function Documentation

void CutPlanar::initialize ( int  numVerts,
PlanarVertex vertexList,
int  numEdges,
PlanarEdge edgeList,
int  numFaces,
PlanarFace faceList,
int  idxSource = FIRST_VERT,
int  idxSink = LAST_VERT,
ECheckFlags  checkInput = CHECK_ALL 
)

this method defines the graph on which the minimal graph will be computed.

Parameters
numVertsThe amount of vertices stored in the array vertexList.
vertexListThe array of all vertices that define the graph.
numEdgesThe amount of edges stored in the array edgeList.
edgeListThe array of all edges that define the graph.
numFacesThe amount of faces stored in the array faceList.
faceListThe array of all faces that define the graph.
idxSourceThe position of the source within the array vertexList. This parameter is optional and is set to the first vertex (FIRST_VERT=0) if it is omitted.
idxSinkThe position of the sink within the array vertexList. This parameter is optional and is set to the last vertex (LAST_VERT=-1 interpreted as numVerts-1) if it is omitted.
checkInputThis parameter encodes the sanity checks that are performed on the input data (see ECheckFlags).
Examples:
cutplanar.cpp.

References PlanarEdge::getCapacity(), PlanarEdge::getFlags(), PlanarEdge::getRevCapacity(), performChecks(), PlanarEdge::setCapacity(), PlanarEdge::setFlags(), and PlanarEdge::setRevCapacity().

Referenced by CutGrid::getMaxFlow().

void CutPlanar::setSource ( int  idxSource)

The source is redefined. If this changes the problem, the maximum flow will be recomputed.

Examples:
cutplanar.cpp.
void CutPlanar::setSink ( int  idxSink)

The sink is redefined. If this changes the problem, the maximum flow will be recomputed.

Examples:
cutplanar.cpp.
double CutPlanar::getMaxFlow ( )

This method provides the maximum flow of the described problem. If the problem has not been solved yet, this method will also take care of this computation.

Examples:
cutplanar.cpp.

References PlanarEdge::getCapacity(), PlanarEdge::getFlags(), PlanarEdge::getHead(), PlanarEdge::getHeadDual(), PlanarEdge::getRevCapacity(), PlanarEdge::getTail(), PlanarEdge::getTailDual(), LABEL_SINK, LABEL_SOURCE, preFlow(), PlanarEdge::setCapacity(), and PlanarEdge::setRevCapacity().

Referenced by getCircularPath(), getCutBoundary(), getLabel(), getLabels(), and CutGrid::getMaxFlow().

CutPlanar::ELabel CutPlanar::getLabel ( int  node)

This method provides the label (see Elabel) of a specific vertex. If the described problem has not been solved yet, this method will also take care of this computation.

Examples:
cutplanar.cpp.

References getMaxFlow(), and LABEL_SOURCE.

Referenced by getCutBoundary(), CutGrid::getLabel(), CutGrid::getLabels(), and getLabels().

std::vector< int > CutPlanar::getLabels ( ELabel  label)

This method provides all nodes of a specific label (see Elabel). If the described problem has not been solved yet, this method will also take care of this computation.

Examples:
cutplanar.cpp.

References getLabel(), getMaxFlow(), and LABEL_SOURCE.

std::vector< int > CutPlanar::getCutBoundary ( ELabel  label)

This method provides all cut nodes that are of a specific label (see Elabel). If the described problem has not been solved yet, this method will also take care of this computation.

Examples:
cutplanar.cpp.

References PlanarEdge::getHead(), getLabel(), getMaxFlow(), PlanarEdge::getTail(), LABEL_SINK, and LABEL_SOURCE.

std::vector< int > CutPlanar::getCircularPath ( )

Every cut of a planar graph forms a closed path in the dual tree.
This method provides an ordered list of faces along this circular path. The last element of the returned vector is not identical with the first element.

path = getCutBoundary(); // path is not closed
path.push_back(path[0]); // now the path is closed
Examples:
cutplanar.cpp.

References getMaxFlow().

void CutPlanar::preFlow ( )
protectedvirtual

This method applies a zero-flow to the network such that there will be no counter-clockwise circles in the network. This can be done by computing Dijkstra on the dual network.

Derived classes may want to overwrite this method.

References CGraph::addEdge(), CGraph::addNode(), CGNode::dijkWeight, PlanarEdge::getCapacity(), PlanarVertex::getEdge(), PlanarEdge::getHeadDual(), PlanarEdge::getRevCapacity(), PlanarEdge::getTail(), PlanarEdge::getTailDual(), CGraph::runDijkstra(), PlanarEdge::setCapacity(), and PlanarEdge::setRevCapacity().

Referenced by getMaxFlow().

void CutPlanar::performChecks ( ECheckFlags  checks)
protectedvirtual

Field Documentation

const int CutPlanar::FIRST_VERT = 0
static
const int CutPlanar::LAST_VERT = -1
static
© 2009 - 2013 by Eno Töppe, Frank R. Schmidt
generated by Doxygen