PlanarGC  1.0.2
 All Data Structures Functions Variables Enumerations Enumerator Friends Pages
CGraph.h
1 /*****************************************************************************
2 * PlanarCut - software to compute MinCut / MaxFlow in a planar graph *
3 * Version 1.0.1 *
4 * *
5 * Copyright 2011 - 2012 Eno Töppe <toeppe@in.tum.de> *
6 * Frank R. Schmidt <info@frank-r-schmidt.de> *
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 __CGRAPH_H__
24 #define __CGRAPH_H__
25 
26 #include "CutPlanarDefs.h"
27 #include "BlockAllocator.h"
28 #include <iostream>
29 
30 #define NODE_BLOCK_SIZE 512
31 #define ARC_BLOCK_SIZE 512
32 
33 //values for CGNode::type
34 #define TYPE_STARTNODE 1
35 #define TYPE_ENDNODE 2
36 
37 
38 struct CGNode;
39 
40 class CDijkNode {
41 
42  public:
43  CapType dijkWeight;
45  int heapId; //index into the heap array
46  int heapNr; //number of heap
47 
48 };
49 
50 typedef CDijkNode* HeapId;
51 
52 struct CGEdge; //forward declaration
53 
54 /* node structure */
55 struct CGNode
56 {
57 
58  CGEdge *first; //first outcoming edge
59  int tag; //just a tag
60  uchar type; //type of node (start- or end-node)
61  HeapId heapId; //corresponding entity in heap
62  CapType dijkWeight; //used by runDijkstra() to compute shortest path
63  CGNode *dijkPrev; //points to previous node on the shortest path
64 
65 };
66 
67 
68 
69 /* arc structure */
70 struct CGEdge
71 {
72 
73  CGNode *head; //node the arc points to
74  CGEdge *next; //next arc with the same originating node
75  CGEdge *sister; //reverse arc
76  CapType weight; //capacity
77 
78 };
79 
80 
81 
82 /********************************************************************
83  DijkHeap
84 ********************************************************************/
85 
86 class DijkHeap {
87 
88  CDijkNode **heap;
89  BlockAllocator<CDijkNode> dijkNodes;
90 
91  int maxIdx;
92  int maxHeapSize;
93 
94  void ascend(int heapId);
95  void descend(int heapId);
96 
97  public:
98 
99  DijkHeap(uint maxHeapSize);
100  ~DijkHeap();
101 
102  HeapId insert(CDijkNode &node);
103  void decrease(HeapId node, CapType amount);
104  bool deleteMin(CDijkNode &node);
105  bool getMin(CDijkNode &node);
106  double getMin();
107  bool isempty();
108 
109  //Methoden zum Einfuegen und Loeschen bereits allozierter Elemente
110  HeapId deleteLast(); //Loescht das letzte Element im Heap ohne es zu zerstoeren
111  void insert(HeapId node); //fuegt ein bereits alloziertes Element ein
112 };
113 
114 
115 
116 
117 
118 
119 
120 /********************************************************************
121  CGraph
122 ********************************************************************/
123 class CGraph {
124 
125  BlockAllocatorStatic<CGNode, NODE_BLOCK_SIZE> *nodeBlock;
126  BlockAllocatorStatic<CGEdge, NODE_BLOCK_SIZE> *edgeBlock;
127 
128  uint numMaxNodes;
129 
130  public:
131  CGraph(uint numMaxNodes);
132  ~CGraph();
133 
134  //remove all nodes and edges
135  void clear();
136 
137  //adds a node to the graph
138  CGNode *addNode();
139  CGNode *addNode(int tag); //like addNode() but sets the tag flag
140 
141  void addEdge(CGNode *from, CGNode *to, CapType weight);
142  /* void addbiEdge(CGNode *from, CGNode *to, CapType weight); */
143 
144  // returns whether the edge was found
145  bool setEdgeWeight(CGNode *from, CGNode *to, CapType cap);
146 
147  void runDijkstra(CGNode *start);
148  CGNode *runDijkstraMulti(CGNode **start, int numStart, CGNode **end, int numEnd);
149  //returns null-terminated list of shortest path nodes
150  CGNode **getShortestPath(CGNode *dest, int *length = NULL);
151  void printShortestPath(CGNode *dest);
152 
153 };
154 
155 
156 
157 
158 
159 
160 
161 #endif //#ifndef __CGRAPH_H__
162 
© 2009 - 2013 by Eno Töppe, Frank R. Schmidt
generated by Doxygen