PlanarGC
1.0.2
All
Data Structures
Functions
Variables
Enumerations
Enumerator
Friends
Pages
CutPlanar.h
1
/*****************************************************************************
2
* PlanarCut - software to compute MinCut / MaxFlow in a planar graph *
3
* Version 1.0 *
4
* *
5
* Copyright 2011 Eno Töppe <toeppe@in.tum.de> *
6
* Frank R. Schmidt <fschmidt@uwo.ca> *
7
******************************************************************************
8
9
If you use this software for research purposes, YOU MUST CITE the following
10
paper in any resulting publication:
11
12
[1] Efficient Planar Graph Cuts with Applications in Computer Vision.
13
F. R. Schmidt, E. Töppe, D. Cremers,
14
IEEE CVPR, Miami, Florida, June 2009
15
16
******************************************************************************
17
18
This software is released under the LGPL license. Details are explained
19
in the files 'COPYING' and 'COPYING.LESSER'.
20
21
*****************************************************************************/
22
23
#ifndef __CUTPLANAR_H__
24
#define __CUTPLANAR_H__
25
/*
26
Some EXCEPTIONS 2B DEFINED FOR
27
CyclesDetected, SourceBlocked, InvalidGraph, PreFlowNotRun
28
*/
29
#include "PlanarException.h"
30
#include "CutPlanarDefs.h"
31
#include "Planar.h"
32
#include "DynPath.h"
33
#include "CGraph.h"
34
#include <vector>
35
36
37
class
CutPlanar
52
{
53
public
:
54
static
const
int
FIRST_VERT
= 0;
55
static
const
int
LAST_VERT
= -1;
56
57
enum
ECheckFlags
68
{
70
CHECK_NONE
= 0x00,
72
CHECK_CONNECTIVITY
= 0x01,
74
CHECK_NON_NEGATIVE_COST
= 0x02,
76
CHECK_PLANARITY
= 0x04,
78
CHECK_ALL
= 0xFF,
79
};
80
81
enum
ELabel
86
{
88
LABEL_SINK
= 0,
90
LABEL_SOURCE
= 1,
91
};
92
93
//allocates memory for nodes, edges and faces
94
CutPlanar
();
95
virtual
~CutPlanar
();
96
97
//define graph
98
//class works in state, i.e., the arrays may be altered.
127
void
initialize
(
int
numVerts,
PlanarVertex
*vertexList,
128
int
numEdges,
PlanarEdge
*edgeList,
129
int
numFaces,
PlanarFace
*faceList,
130
int
idxSource =
FIRST_VERT
,
//sets which node should be source
131
int
idxSink =
LAST_VERT
,
//sets which node should be sink
132
ECheckFlags
checkInput =
CHECK_ALL
);
//enables advanced input validation
133
138
void
setSource
(
int
idxSource);
143
void
setSink
(
int
idxSink);
144
145
151
double
getMaxFlow
();
157
ELabel
getLabel
(
int
node);
// returns the label of a node
163
std::vector<int>
getLabels
(
ELabel
label);
// returns all nodes of a specific label
169
std::vector<int>
getCutBoundary
(
ELabel
label);
// returns all cut-nodes in the source or the sink set
179
std::vector<int>
getCircularPath
();
180
181
protected
:
189
virtual
void
preFlow
();
190
196
virtual
void
performChecks
(
ECheckFlags
checks);
197
198
199
200
private
:
201
// planar encoding
202
int
nVerts;
203
int
nEdges;
204
int
nFaces;
205
PlanarVertex
*verts;
206
PlanarFace
*faces;
207
PlanarEdge
*edges;
208
// source and sink
209
int
sourceID;
// previously PlanarVertex *pvSource
210
int
sinkID;
// previously PlanarVertex *pvSink
211
212
bool
computedFlow;
// stores whether the flow is already computed
213
// has to be maintained by 'maxflow' and 'initialize'
214
double
maxFlow;
215
double
capEps;
// zero capacity darts are replaced by this value
216
217
PlanarFace
*pfStartOfCut;
//if computedFlow, retains the first
218
//face of the cut loop in T*
219
220
//primal spanning tree
221
DynLeaf *primalTreeNodes;
//nodes of the primal spanning tree
222
DynLeaf *plSource;
//pointer on source in primal spanning tree
223
DynLeaf *plSink;
//pointer to sink in primal spanning tree
224
//dual spanning tree
225
PlanarFace
**dualTreeParent;
// dual tree parent relationship
226
PlanarEdge
**dualTreeEdge;
// dual tree fast edge-access
227
228
//labeling
229
bool
completelyLabeled;
230
bool
*isLabeled;
231
ELabel
*labels;
232
233
//set during constructSpanningTrees() if Source is blocked
234
bool
isSourceBlocked;
235
236
//definition of planar input graph
237
238
//auxiliary inline functions
239
int
getVertIndex(
PlanarVertex
*pv) {
return
pv - verts;}
240
int
getFaceIndex(
PlanarFace
*pf) {
return
pf - faces;}
241
int
getDynNodeIndex(DynLeaf *pl) {
return
pl - primalTreeNodes;}
242
243
//constructs the primal and dual spanning trees used by maxflow()
244
void
constructSpanningTrees();
245
};
246
247
248
#endif
© 2009 - 2013 by Eno Töppe, Frank R. Schmidt
generated by
Doxygen