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 
68  {
70  CHECK_NONE = 0x00,
78  CHECK_ALL = 0xFF,
79  };
80 
81  enum ELabel
86  {
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