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
;
44
CGNode
*
node
;
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