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