VTK  9.1.0
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 <map>
29#include <vector>
30
31//-----------------------------------------------------------------------------
33{
34public:
35 vtkDijkstraGraphInternals() { this->HeapSize = 0; }
36
38
39 // CumulativeWeights(v) current summed weight for path to vertex v.
40 std::vector<double> CumulativeWeights;
41
42 // Predecessors(v) predecessor of v.
43 std::vector<int> Predecessors;
44
45 // OpenVertices is the set of vertices which has not a shortest path yet but has a path.
46 // OpenVertices(v) == 1 means that vertex v is in OpenVertices.
47 // OpenVertices is a boolean (1/0) array.
48 std::vector<unsigned char> OpenVertices;
49
50 // ClosedVertices is the set of vertices with already determined shortest path
51 // ClosedVertices(v) == 1 means that vertex v is in ClosedVertices.
52 // ClosedVertices is a boolean (1/0) array.
53 std::vector<unsigned char> ClosedVertices;
54
55 // Adjacency representation.
56 std::vector<std::map<int, double>> Adjacency;
57
58 // Path repelling by assigning high costs to flagged vertices.
59 std::vector<unsigned char> BlockedVertices;
60
61 void Heapify(const int& i)
62 {
63 // left node
64 unsigned int l = i * 2;
65 // right node
66 unsigned int r = i * 2 + 1;
67 int smallest = -1;
68
69 // The value of element v is CumulativeWeights(v)
70 // the heap stores the vertex numbers
71 if (l <= this->HeapSize &&
72 (this->CumulativeWeights[this->Heap[l]] < this->CumulativeWeights[this->Heap[i]]))
73 {
74 smallest = l;
75 }
76 else
77 {
78 smallest = i;
79 }
80
81 if (r <= this->HeapSize &&
82 (this->CumulativeWeights[this->Heap[r]] < this->CumulativeWeights[this->Heap[smallest]]))
83 {
84 smallest = r;
85 }
86
87 if (smallest != i)
88 {
89 int t = this->Heap[i];
90
91 this->Heap[i] = this->Heap[smallest];
92
93 // where is Heap(i)
94 this->HeapIndices[this->Heap[i]] = i;
95
96 // Heap and HeapIndices are kinda inverses
97 this->Heap[smallest] = t;
98 this->HeapIndices[t] = smallest;
99
100 this->Heapify(smallest);
101 }
102 }
103
104 void HeapInsert(const int& v)
105 {
106 if (this->HeapSize >= (this->Heap.size() - 1))
107 {
108 return;
109 }
110
111 this->HeapSize++;
112 int i = this->HeapSize;
113
114 while (i > 1 && this->CumulativeWeights[this->Heap[i / 2]] > this->CumulativeWeights[v])
115 {
116 this->Heap[i] = this->Heap[i / 2];
117 this->HeapIndices[this->Heap[i]] = i;
118 i /= 2;
119 }
120 // Heap and HeapIndices are kinda inverses
121 this->Heap[i] = v;
122 this->HeapIndices[v] = i;
123 }
124
126 {
127 if (this->HeapSize == 0)
128 {
129 return -1;
130 }
131
132 int minv = this->Heap[1];
133 this->HeapIndices[minv] = -1;
134
135 this->Heap[1] = this->Heap[this->HeapSize];
136 this->HeapIndices[this->Heap[1]] = 1;
137
138 this->HeapSize--;
139 this->Heapify(1);
140
141 return minv;
142 }
143
144 void HeapDecreaseKey(const int& v)
145 {
146 // where in Heap is vertex v
147 int i = this->HeapIndices[v];
148 if (i < 1 || i > static_cast<int>(this->HeapSize))
149 {
150 return;
151 }
152
153 while (i > 1 && this->CumulativeWeights[this->Heap[i / 2]] > this->CumulativeWeights[v])
154 {
155 this->Heap[i] = this->Heap[i / 2];
156 this->HeapIndices[this->Heap[i]] = i;
157 i /= 2;
158 }
159
160 // Heap and HeapIndices are kinda inverses
161 this->Heap[i] = v;
162 this->HeapIndices[v] = i;
163 }
164
165 void ResetHeap() { this->HeapSize = 0; }
166
167 void InitializeHeap(const int& size)
168 {
169 this->Heap.resize(size + 1);
170 this->HeapIndices.resize(size);
171 }
172
173private:
174 unsigned int HeapSize;
175
176 // The priority queue (a binary heap) with vertex indices.
177 std::vector<int> Heap;
178
179 // HeapIndices(v) the position of v in Heap (HeapIndices and Heap are kind of inverses).
180 std::vector<int> HeapIndices;
181};
182
183#endif
184// VTK-HeaderTest-Exclude: vtkDijkstraGraphInternals.h
Helper class due to PIMPL excess.
std::vector< unsigned char > BlockedVertices
std::vector< unsigned char > OpenVertices
std::vector< unsigned char > ClosedVertices
std::vector< double > CumulativeWeights
void InitializeHeap(const int &size)
~vtkDijkstraGraphInternals()=default
std::vector< std::map< int, double > > Adjacency