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