25#ifndef vtkDijkstraGraphInternals_h
26#define vtkDijkstraGraphInternals_h
64 unsigned int l = i * 2;
66 unsigned int r = i * 2 + 1;
71 if (l <= this->HeapSize &&
72 (this->CumulativeWeights[this->Heap[l]] < this->CumulativeWeights[this->Heap[i]]))
81 if (r <= this->HeapSize &&
82 (this->CumulativeWeights[this->Heap[r]] < this->CumulativeWeights[this->Heap[smallest]]))
89 int t = this->Heap[i];
91 this->Heap[i] = this->Heap[smallest];
94 this->HeapIndices[this->Heap[i]] = i;
97 this->Heap[smallest] = t;
98 this->HeapIndices[t] = smallest;
106 if (this->HeapSize >= (this->Heap.size() - 1))
112 int i = this->HeapSize;
114 while (i > 1 && this->CumulativeWeights[this->Heap[i / 2]] > this->CumulativeWeights[v])
116 this->Heap[i] = this->Heap[i / 2];
117 this->HeapIndices[this->Heap[i]] = i;
122 this->HeapIndices[v] = i;
127 if (this->HeapSize == 0)
132 int minv = this->Heap[1];
133 this->HeapIndices[minv] = -1;
135 this->Heap[1] = this->Heap[this->HeapSize];
136 this->HeapIndices[this->Heap[1]] = 1;
147 int i = this->HeapIndices[v];
148 if (i < 1 || i >
static_cast<int>(this->HeapSize))
153 while (i > 1 && this->CumulativeWeights[this->Heap[i / 2]] > this->CumulativeWeights[v])
155 this->Heap[i] = this->Heap[i / 2];
156 this->HeapIndices[this->Heap[i]] = i;
162 this->HeapIndices[v] = i;
169 this->Heap.resize(size + 1);
170 this->HeapIndices.resize(size);
174 unsigned int HeapSize;
177 std::vector<int> Heap;
180 std::vector<int> HeapIndices;
Helper class due to PIMPL excess.
std::vector< unsigned char > BlockedVertices
std::vector< unsigned char > OpenVertices
void HeapDecreaseKey(const int &v)
std::vector< unsigned char > ClosedVertices
std::vector< int > Predecessors
void Heapify(const int &i)
std::vector< double > CumulativeWeights
void HeapInsert(const int &v)
void InitializeHeap(const int &size)
vtkDijkstraGraphInternals()
~vtkDijkstraGraphInternals()=default
std::vector< std::map< int, double > > Adjacency