24 #ifndef __vtkDijkstraGraphInternals_h
25 #define __vtkDijkstraGraphInternals_h
27 #include <vtkstd/vector>
61 vtkstd::vector< vtkstd::map< int,double > >
Adjacency;
70 unsigned int l = i * 2;
72 unsigned int r = i * 2 + 1;
77 if ( l <= this->HeapSize &&
88 if ( r <= this->HeapSize &&
97 int t = this->Heap[i];
99 this->Heap[ i ] = this->Heap[ smallest ];
102 this->HeapIndices[ this->Heap[i] ] = i;
105 this->Heap[ smallest ] = t;
106 this->HeapIndices[ t ] = smallest;
114 if ( this->HeapSize >= (this->Heap.size() - 1) )
120 int i = this->HeapSize;
126 this->Heap[ i ] = this->Heap[i/2];
127 this->HeapIndices[ this->Heap[i] ] = i;
132 this->HeapIndices[ v ] = i;
137 if ( this->HeapSize == 0 )
142 int minv = this->Heap[ 1 ];
143 this->HeapIndices[ minv ] = -1;
145 this->Heap[ 1 ] = this->Heap[ this->HeapSize ];
146 this->HeapIndices[ this->Heap[1] ]= 1;
157 int i = this->HeapIndices[ v ];
158 if ( i < 1 || i > static_cast<int>(this->HeapSize) )
167 this->Heap[ i ] = this->Heap[i/2];
168 this->HeapIndices[ this->Heap[i] ] = i;
174 this->HeapIndices[ v ] = i;
184 this->Heap.resize( size + 1 );
185 this->HeapIndices.resize( size );
189 unsigned int HeapSize;
192 vtkstd::vector<int> Heap;
195 vtkstd::vector<int> HeapIndices;