#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) |
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.
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.
enum CutPlanar::ELabel |
CutPlanar::CutPlanar | ( | ) |
|
virtual |
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.
numVerts | The amount of vertices stored in the array vertexList. |
vertexList | The array of all vertices that define the graph. |
numEdges | The amount of edges stored in the array edgeList. |
edgeList | The array of all edges that define the graph. |
numFaces | The amount of faces stored in the array faceList. |
faceList | The array of all faces that define the graph. |
idxSource | The 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. |
idxSink | The 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. |
checkInput | This parameter encodes the sanity checks that are performed on the input data (see ECheckFlags). |
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.
void CutPlanar::setSink | ( | int | idxSink | ) |
The sink is redefined. If this changes the problem, the maximum flow will be recomputed.
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.
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.
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.
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.
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.
References getMaxFlow().
|
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().
|
protectedvirtual |
This method provides all the tests described in CutPlanar::ECheckFlags.
Derived classes may want to overwrite this method.
References CHECK_CONNECTIVITY, CHECK_NON_NEGATIVE_COST, CHECK_PLANARITY, PlanarVertex::getEdge(), PlanarEdge::getHead(), PlanarEdge::getHeadDual(), PlanarVertex::getNumEdges(), PlanarEdge::getTail(), and PlanarEdge::getTailDual().
Referenced by initialize().
|
static |
|
static |