VTK
vtkDijkstraGraphInternals.h
Go to the documentation of this file.
1/*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkDijkstraGraphInternals.h
5
6 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7 All rights reserved.
8 See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
9
10 This software is distributed WITHOUT ANY WARRANTY; without even
11 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12 PURPOSE. See the above copyright notice for more information.
13
14=========================================================================*/
25#ifndef vtkDijkstraGraphInternals_h
26#define vtkDijkstraGraphInternals_h
27
28#include <vector>
29#include <map>
30
31//-----------------------------------------------------------------------------
33{
34public:
35
37 {
38 this->HeapSize = 0;
39 }
40
42 {
43 }
44
45 // CumulativeWeights(v) current summed weight for path to vertex v.
46 std::vector<double> CumulativeWeights;
47
48 // Predecessors(v) predecessor of v.
49 std::vector<int> Predecessors;
50
51 // OpenVertices is the set of vertices which has not a shortest path yet but has a path.
52 // OpenVertices(v) == 1 means that vertex v is in OpenVertices.
53 // OpenVertices is a boolean (1/0) array.
54 std::vector<unsigned char> OpenVertices;
55
56 // ClosedVertices is the set of vertices with already determined shortest path
57 // ClosedVertices(v) == 1 means that vertex v is in ClosedVertices.
58 // ClosedVertices is a boolean (1/0) array.
59 std::vector<unsigned char> ClosedVertices;
60
61 // Adjacency representation.
62 std::vector< std::map< int,double > > Adjacency;
63
64 // Path repelling by assigning high costs to flagged vertices.
65 std::vector<unsigned char> BlockedVertices;
66
67
68 void Heapify(const int& i)
69 {
70 // left node
71 unsigned int l = i * 2;
72 // right node
73 unsigned int r = i * 2 + 1;
74 int smallest = -1;
75
76 // The value of element v is CumulativeWeights(v)
77 // the heap stores the vertex numbers
78 if ( l <= this->HeapSize &&
79 ( this->CumulativeWeights[ this->Heap[l] ] <
80 this->CumulativeWeights[ this->Heap[i] ] ) )
81 {
82 smallest = l;
83 }
84 else
85 {
86 smallest = i;
87 }
88
89 if ( r <= this->HeapSize &&
90 ( this->CumulativeWeights[ this->Heap[ r ] ] <
91 this->CumulativeWeights[ this->Heap[ smallest ] ] ) )
92 {
93 smallest = r;
94 }
95
96 if ( smallest != i )
97 {
98 int t = this->Heap[i];
99
100 this->Heap[ i ] = this->Heap[ smallest ];
101
102 // where is Heap(i)
103 this->HeapIndices[ this->Heap[i] ] = i;
104
105 // Heap and HeapIndices are kinda inverses
106 this->Heap[ smallest ] = t;
107 this->HeapIndices[ t ] = smallest;
108
109 this->Heapify( smallest );
110 }
111 }
112
113 void HeapInsert(const int& v)
114 {
115 if ( this->HeapSize >= (this->Heap.size() - 1) )
116 {
117 return;
118 }
119
120 this->HeapSize++;
121 int i = this->HeapSize;
122
123 while ( i > 1 &&
124 this->CumulativeWeights[ this->Heap[i/2] ] >
125 this->CumulativeWeights[v] )
126 {
127 this->Heap[ i ] = this->Heap[i/2];
128 this->HeapIndices[ this->Heap[i] ] = i;
129 i /= 2;
130 }
131 // Heap and HeapIndices are kinda inverses
132 this->Heap[ i ] = v;
133 this->HeapIndices[ v ] = i;
134 }
135
137 {
138 if ( this->HeapSize == 0 )
139 {
140 return -1;
141 }
142
143 int minv = this->Heap[ 1 ];
144 this->HeapIndices[ minv ] = -1;
145
146 this->Heap[ 1 ] = this->Heap[ this->HeapSize ];
147 this->HeapIndices[ this->Heap[1] ]= 1;
148
149 this->HeapSize--;
150 this->Heapify( 1 );
151
152 return minv;
153 }
154
155 void HeapDecreaseKey(const int& v)
156 {
157 // where in Heap is vertex v
158 int i = this->HeapIndices[ v ];
159 if ( i < 1 || i > static_cast<int>(this->HeapSize) )
160 {
161 return;
162 }
163
164 while ( i > 1 &&
165 this->CumulativeWeights[ this->Heap[ i/2 ] ] >
166 this->CumulativeWeights[ v ] )
167 {
168 this->Heap[ i ] = this->Heap[i/2];
169 this->HeapIndices[ this->Heap[i] ] = i;
170 i /= 2;
171 }
172
173 // Heap and HeapIndices are kinda inverses
174 this->Heap[ i ] = v;
175 this->HeapIndices[ v ] = i;
176 }
177
179 {
180 this->HeapSize = 0;
181 }
182
183 void InitializeHeap(const int& size)
184 {
185 this->Heap.resize( size + 1 );
186 this->HeapIndices.resize( size );
187 }
188
189private:
190 unsigned int HeapSize;
191
192 // The priority que (a binary heap) with vertex indices.
193 std::vector<int> Heap;
194
195 // HeapIndices(v) the position of v in Heap (HeapIndices and Heap are kind of inverses).
196 std::vector<int> HeapIndices;
197
198};
199
200#endif
201// VTK-HeaderTest-Exclude: vtkDijkstraGraphInternals.h
Helper class due to PIMPL excess.
std::vector< std::map< int, double > > Adjacency
std::vector< unsigned char > BlockedVertices
std::vector< unsigned char > OpenVertices
std::vector< unsigned char > ClosedVertices
std::vector< double > CumulativeWeights
void InitializeHeap(const int &size)
@ size
Definition: vtkX3D.h:253