vtkDijkstraGraphInternals.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
// SPDX-License-Identifier: BSD-3-Clause
#ifndef vtkDijkstraGraphInternals_h
#define vtkDijkstraGraphInternals_h
 
#include <map>
#include <vector>
 
//-----------------------------------------------------------------------------
VTK_ABI_NAMESPACE_BEGIN
class vtkDijkstraGraphInternals
{
public:
  vtkDijkstraGraphInternals() { this->HeapSize = 0; }
 
  ~vtkDijkstraGraphInternals() = default;
 
  // CumulativeWeights(v) current summed weight for path to vertex v.
  std::vector<double> CumulativeWeights;
 
  // Predecessors(v) predecessor of v.
  std::vector<int> Predecessors;
 
  // OpenVertices is the set of vertices which has not a shortest path yet but has a path.
  // OpenVertices(v) == 1 means that vertex v is in OpenVertices.
  // OpenVertices is a boolean (1/0) array.
  std::vector<unsigned char> OpenVertices;
 
  // ClosedVertices is the set of vertices with already determined shortest path
  // ClosedVertices(v) == 1 means that vertex v is in ClosedVertices.
  // ClosedVertices is a boolean (1/0) array.
  std::vector<unsigned char> ClosedVertices;
 
  // Adjacency representation.
  std::vector<std::map<int, double>> Adjacency;
 
  // Path repelling by assigning high costs to flagged vertices.
  std::vector<unsigned char> BlockedVertices;
 
  void Heapify(const int& i)
  {
    // left node
    unsigned int l = i * 2;
    // right node
    unsigned int r = i * 2 + 1;
    int smallest = -1;
 
    // The value of element v is CumulativeWeights(v)
    // the heap stores the vertex numbers
    if (l <= this->HeapSize &&
      (this->CumulativeWeights[this->Heap[l]] < this->CumulativeWeights[this->Heap[i]]))
    {
      smallest = l;
    }
    else
    {
      smallest = i;
    }
 
    if (r <= this->HeapSize &&
      (this->CumulativeWeights[this->Heap[r]] < this->CumulativeWeights[this->Heap[smallest]]))
    {
      smallest = r;
    }
 
    if (smallest != i)
    {
      int t = this->Heap[i];
 
      this->Heap[i] = this->Heap[smallest];
 
      // where is Heap(i)
      this->HeapIndices[this->Heap[i]] = i;
 
      // Heap and HeapIndices are kinda inverses
      this->Heap[smallest] = t;
      this->HeapIndices[t] = smallest;
 
      this->Heapify(smallest);
    }
  }
 
  void HeapInsert(const int& v)
  {
    if (this->HeapSize >= (this->Heap.size() - 1))
    {
      return;
    }
 
    this->HeapSize++;
    int i = this->HeapSize;
 
    while (i > 1 && this->CumulativeWeights[this->Heap[i / 2]] > this->CumulativeWeights[v])
    {
      this->Heap[i] = this->Heap[i / 2];
      this->HeapIndices[this->Heap[i]] = i;
      i /= 2;
    }
    // Heap and HeapIndices are kinda inverses
    this->Heap[i] = v;
    this->HeapIndices[v] = i;
  }
 
  int HeapExtractMin()
  {
    if (this->HeapSize == 0)
    {
      return -1;
    }
 
    int minv = this->Heap[1];
    this->HeapIndices[minv] = -1;
 
    this->Heap[1] = this->Heap[this->HeapSize];
    this->HeapIndices[this->Heap[1]] = 1;
 
    this->HeapSize--;
    this->Heapify(1);
 
    return minv;
  }
 
  void HeapDecreaseKey(const int& v)
  {
    // where in Heap is vertex v
    int i = this->HeapIndices[v];
    if (i < 1 || i > static_cast<int>(this->HeapSize))
    {
      return;
    }
 
    while (i > 1 && this->CumulativeWeights[this->Heap[i / 2]] > this->CumulativeWeights[v])
    {
      this->Heap[i] = this->Heap[i / 2];
      this->HeapIndices[this->Heap[i]] = i;
      i /= 2;
    }
 
    // Heap and HeapIndices are kinda inverses
    this->Heap[i] = v;
    this->HeapIndices[v] = i;
  }
 
  void ResetHeap() { this->HeapSize = 0; }
 
  void InitializeHeap(const int& size)
  {
    this->Heap.resize(size + 1);
    this->HeapIndices.resize(size);
  }
 
private:
  unsigned int HeapSize;
 
  // The priority queue (a binary heap) with vertex indices.
  std::vector<int> Heap;
 
  // HeapIndices(v) the position of v in Heap (HeapIndices and Heap are kind of inverses).
  std::vector<int> HeapIndices;
};
 
VTK_ABI_NAMESPACE_END
#endif
// VTK-HeaderTest-Exclude: vtkDijkstraGraphInternals.h