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