25 #ifndef vtkDijkstraGraphInternals_h
26 #define vtkDijkstraGraphInternals_h
71 unsigned int l = i * 2;
73 unsigned int r = i * 2 + 1;
78 if ( l <= this->HeapSize &&
89 if ( r <= this->HeapSize &&
98 int t = this->Heap[i];
100 this->Heap[ i ] = this->Heap[ smallest ];
103 this->HeapIndices[ this->Heap[i] ] = i;
106 this->Heap[ smallest ] = t;
107 this->HeapIndices[ t ] = smallest;
115 if ( this->HeapSize >= (this->Heap.size() - 1) )
121 int i = this->HeapSize;
127 this->Heap[ i ] = this->Heap[i/2];
128 this->HeapIndices[ this->Heap[i] ] = i;
133 this->HeapIndices[ v ] = i;
138 if ( this->HeapSize == 0 )
143 int minv = this->Heap[ 1 ];
144 this->HeapIndices[ minv ] = -1;
146 this->Heap[ 1 ] = this->Heap[ this->HeapSize ];
147 this->HeapIndices[ this->Heap[1] ]= 1;
158 int i = this->HeapIndices[ v ];
159 if ( i < 1 || i > static_cast<int>(this->HeapSize) )
168 this->Heap[ i ] = this->Heap[i/2];
169 this->HeapIndices[ this->Heap[i] ] = i;
175 this->HeapIndices[ v ] = i;
185 this->Heap.resize( size + 1 );
186 this->HeapIndices.resize( size );
190 unsigned int HeapSize;
193 std::vector<int> Heap;
196 std::vector<int> HeapIndices;
void HeapInsert(const int &v)
std::vector< unsigned char > BlockedVertices
~vtkDijkstraGraphInternals()
std::vector< unsigned char > ClosedVertices
std::vector< double > CumulativeWeights
vtkDijkstraGraphInternals()
Helper class due to PIMPL excess.
void Heapify(const int &i)
std::vector< std::map< int, double > > Adjacency
void HeapDecreaseKey(const int &v)
void InitializeHeap(const int &size)
std::vector< int > Predecessors
std::vector< unsigned char > OpenVertices