mpadge.tngl.sh
Distances on Directed Graphs in R
1#pragma once
2
3// Modified from code by Shane Saunders
4
5#include <vector>
6#include <memory>
7#include <set>
8#include <cmath> // fabs
9#include <unordered_set> // used in bidirected search
10
11// inf_dbl used only in AStar2:
12#include <limits>
13
14#include "dgraph.h"
15
16constexpr long int INFINITE_INT = std::numeric_limits <long int>::max ();
17constexpr double INFINITE_DOUBLE = std::numeric_limits <double>::max ();
18
19class Heap;
20class HeapDesc;
21class DGraph;
22
23namespace PF{
24
25/* DijkstraEdge is used for the std::set implementation, everything else is for
26 * Shane Saunders's heap sort versions */
27struct DijkstraEdge
28{
29 DijkstraEdge (double wt, size_t i): _wt (wt), _i (i) {}
30
31 double _wt;
32 size_t _i;
33
34 size_t geti () const { return _i; }
35 double getw () const { return _wt; }
36};
37
38struct by_wt
39{
40 bool operator () (const DijkstraEdge& lhs, const DijkstraEdge& rhs) const
41 {
42 if (fabs (lhs._wt - rhs._wt) < 1.0e-12)
43 return lhs._i < rhs._i;
44 else
45 return lhs._wt < rhs._wt;
46 }
47};
48
49typedef std::set <DijkstraEdge, by_wt> EdgeSet;
50
51
52class PathFinder {
53 public:
54 PathFinder (size_t n,
55 const HeapDesc& heapD,
56 std::shared_ptr<const DGraph> g);
57 ~PathFinder();
58
59 // Disable copy/assign as will crash
60 PathFinder(const PathFinder&) = delete;
61 PathFinder& operator=(const PathFinder&) = delete;
62
63 void init (std::shared_ptr<const DGraph> g);
64 void init_arrays (
65 std::vector<double>& d,
66 std::vector<double>& w,
67 std::vector<long int>& prev,
68 bool *m_open_vec,
69 bool *m_closed_vec,
70 const size_t v,
71 const size_t n);
72 void scan_edges (
73 const DGraphEdge *edge,
74 std::vector<double>& d,
75 std::vector<double>& w,
76 std::vector<long int>& prev,
77 bool *m_open_vec,
78 const bool *m_closed_vec,
79 const size_t &v0);
80 void scan_edges_heur ( // with A* heuristic
81 const DGraphEdge *edge,
82 std::vector<double>& d,
83 std::vector<double>& w,
84 std::vector<long int>& prev,
85 bool *m_open_vec,
86 const bool *m_closed_vec,
87 const size_t &v0,
88 const std::vector<double> &heur);
89 // with A* heuristic for dists-categorical
90 void scan_edge_types_heur (
91 const DGraphEdge *edge,
92 std::vector<double>& d,
93 std::vector<double>& w,
94 std::vector<long int>& prev,
95 bool *m_open_vec,
96 const bool *m_closed_vec,
97 const size_t &v0,
98 const std::vector<double> &heur);
99 // run_sp_categorical for threshold dists
100 void scan_edge_types (
101 const DGraphEdge *edge,
102 std::vector<double>& d,
103 std::vector<double>& w,
104 std::vector<long int>& prev,
105 bool *m_open_vec,
106 const bool *m_closed_vec,
107 const size_t &v0);
108
109 void Dijkstra (
110 std::vector<double>& d,
111 std::vector<double>& w,
112 std::vector<long int>& prev,
113 const size_t v0,
114 const std::vector <size_t> &to_index);
115 void DijkstraNearest (
116 std::vector<double>& d,
117 std::vector<double>& w,
118 std::vector<long int>& prev,
119 const size_t v0,
120 const std::vector <size_t> &to_index);
121 void DijkstraLimit ( // run_sp_categorical
122 std::vector<double>& d,
123 std::vector<double>& w,
124 std::vector<long int>& prev,
125 const size_t v0,
126 const double &dlim);
127 void DijkstraLimitEdgeType (
128 std::vector<double>& d,
129 std::vector<double>& w,
130 std::vector<long int>& prev,
131 const size_t v0,
132 const double &dlim);
133 void AStar (std::vector<double>& d,
134 std::vector<double>& w,
135 std::vector<long int>& prev,
136 const std::vector<double>& heur,
137 const size_t v0,
138 const std::vector <size_t> &to_index);
139 void AStarEdgeType (std::vector<double>& d,
140 std::vector<double>& w,
141 std::vector<long int>& prev,
142 const std::vector<double>& heur,
143 const size_t v0,
144 const std::vector <size_t> &to_index);
145 void Dijkstra_set (std::vector <double>& d,
146 std::vector<double>& w,
147 std::vector<long int>& prev,
148 size_t v0);
149 void Centrality_vertex (
150 std::vector <double>& cent,
151 const size_t s,
152 const double vert_wt,
153 const double dist_threshold);
154 void Centrality_edge (
155 std::vector <double>& cent,
156 const size_t s,
157 const double vert_wt,
158 const size_t nedges,
159 const double dist_threshold);
160
161 private:
162 Heap *m_heap; // pointer: heap
163 // Convert to vector<bool>? (save memory, might be a performance hit though)
164 bool *m_open; // array: frontier set state of vertices
165 bool *m_closed; // also for bi-dir
166
167 std::shared_ptr<const DGraph> m_graph; // pointer: directed graph
168
169 EdgeSet edge_set;
170};
171
172} // end namespace PF