1 #ifndef GRAPH_SHORTEST_PATHS_H 2 #define GRAPH_SHORTEST_PATHS_H 7 #include <KrisLibrary/structs/FixedSizeHeap.h> 8 #include <KrisLibrary/structs/Heap.h> 13 const static Weight inf = Math::dInf;
38 template <
class Node,
class Edge>
45 void InitializeSource(
int s);
46 void InitializeSources(
const vector<int>& s);
48 template <
typename WeightFunc,
typename Iterator>
49 void FindPath(
int t,WeightFunc w,Iterator it);
50 template <
typename WeightFunc,
typename Iterator>
51 int FindAPath(
const vector<int>& t,WeightFunc w,Iterator it);
52 template <
typename WeightFunc,
typename Iterator>
53 inline void FindAllPaths(WeightFunc w,Iterator it) { FindPath(-1,w,it); }
57 template <
typename WeightFunc,
typename InIterator,
typename OutIterator>
58 void IncreaseUpdate(
int u,
int v,WeightFunc w,InIterator in,OutIterator out);
59 template <
typename WeightFunc,
typename InIterator,
typename OutIterator>
60 void DecreaseUpdate(
int u,
int v,WeightFunc w,InIterator in,OutIterator out);
61 template <
typename WeightFunc,
typename InIterator,
typename OutIterator>
62 void DeleteUpdate(
int u,
int v,WeightFunc w,InIterator in,OutIterator out);
64 template <
typename WeightFunc,
typename Iterator>
65 bool HasShortestPaths(
int s,WeightFunc w,Iterator it);
69 template <
typename WeightFunc>
70 inline void FindPath_Directed(
int t,WeightFunc w) {
73 template <
typename WeightFunc>
74 inline int FindAPath_Directed(
const vector<int>& t,WeightFunc w) {
77 template <
typename WeightFunc>
78 inline void FindAllPaths_Directed(WeightFunc w) {
82 template <
typename WeightFunc>
83 inline void IncreaseUpdate_Directed(
int u,
int v,WeightFunc w) {
85 IncreaseUpdate(u,v,w,in,out);
87 template <
typename WeightFunc>
88 inline void DecreaseUpdate_Directed(
int u,
int v,WeightFunc w) {
90 DecreaseUpdate(u,v,w,in,out);
92 template <
typename WeightFunc>
93 inline void DeleteUpdate_Directed(
int u,
int v,WeightFunc w) {
95 DeleteUpdate(u,v,w,in,out);
97 template <
typename WeightFunc>
98 inline bool HasShortestPaths_Directed(
int s,WeightFunc w) {
100 return HasShortestPaths(s,w,it);
103 template <
typename WeightFunc>
104 inline void FindPath_Undirected(
int t,WeightFunc w) {
108 template <
typename WeightFunc>
109 inline int FindAPath_Undirected(
const vector<int>& t,WeightFunc w) {
112 template <
typename WeightFunc>
113 inline void FindAllPaths_Undirected(WeightFunc w) {
116 template <
typename WeightFunc>
117 inline void IncreaseUpdate_Undirected(
int u,
int v,WeightFunc w) {
119 IncreaseUpdate(u,v,w,it,it);
120 IncreaseUpdate(v,u,w,it,it);
122 template <
typename WeightFunc>
123 inline void DecreaseUpdate_Undirected(
int u,
int v,WeightFunc w) {
125 DecreaseUpdate(u,v,w,it,it);
126 DecreaseUpdate(v,u,w,it,it);
128 template <
typename WeightFunc>
129 inline void DeleteUpdate_Undirected(
int u,
int v,WeightFunc w) {
131 DeleteUpdate(u,v,w,it,it);
132 DeleteUpdate(v,u,w,it,it);
134 template <
typename WeightFunc>
135 inline bool HasShortestPaths_Undirected(
int s,WeightFunc w) {
137 return HasShortestPaths(s,w,it);
144 virtual void SetDistance(
int n,Real dn,
int pn) { d[n]=dn; p[n]=pn; }
149 std::vector<Weight> d;
155 template <
class Node,
class Edge>
161 template <
class Node,
class Edge>
165 int nn = g.NumNodes();
168 for(
int i=0;i<nn;i++) {
175 template <
class Node,
class Edge>
179 int nn = g.NumNodes();
182 for(
int i=0;i<nn;i++) {
186 for(
size_t i=0;i<s.size();i++)
190 template <
class Node,
class Edge>
191 template <
typename WeightFunc,
typename Iterator>
196 for(
int i=0;i<nn;i++) H.push(i,-d[i]);
200 int u = H.top(); H.pop();
203 for(g.Begin(u,it);!it.end();it++) {
206 Weight dvu = d[u] + w(*it,it.source(),it.target());
215 template <
class Node,
class Edge>
216 template <
typename WeightFunc,
typename Iterator>
221 for(
int i=0;i<nn;i++) H.push(i,-d[i]);
224 for(
size_t i=0;i<t.size();i++) targetSet.insert(t[i]);
228 int u = H.top(); H.pop();
229 if(targetSet.count(u)!=0)
return u;
231 for(g.Begin(u,it);!it.end();it++) {
234 Weight dvu = d[u] + w(*it,it.source(),it.target());
245 template <
class Node,
class Edge>
246 template <
typename WeightFunc,
typename InIterator,
typename OutIterator>
248 InIterator in,OutIterator out)
251 if(p[v] != u)
return;
254 for(g.Begin(v,in);!in.end();in++) {
256 if(d[v] == d[t]+w(*in,in.source(),in.target())) {
264 for(
size_t i=0;i<Q.size();i++) {
267 for(g.Begin(n,out);!out.end();out++) {
271 for(g.Begin(t,in);!in.end();in++) {
273 if(d[t]==d[s]+w(*in,in.source(),in.target())) {
278 if(p[t]==n) Q.push_back(t);
284 for(
size_t i=0;i<Q.size();i++) {
286 for(g.Begin(n,in);!in.end();in++) {
288 double W=w(*in,in.source(),in.target());
296 int n=H.top(); H.pop();
297 for(g.Begin(n,out);!out.end();out++) {
299 double W=w(*out,out.source(),out.target());
308 template <
class Node,
class Edge>
309 template <
typename WeightFunc,
typename InIterator,
typename OutIterator>
311 InIterator in,OutIterator out)
314 for(g.Begin(u,out);!out.end();out++)
315 if(out.target()==v) {
316 double W=w(*out,out.source(),out.target());
324 FatalError(
"ShortestPathProblem::DecreaseUpdate(): Warning, decreasing an edge that doesn't exist in the graph!");
329 int n=H.top(); H.pop();
330 for(g.Begin(n,out);!out.end();out++) {
332 double W=w(*out,out.source(),out.target());
341 template <
class Node,
class Edge>
342 template <
typename WeightFunc,
typename InIterator,
typename OutIterator>
344 InIterator in,OutIterator out)
349 for(g.Begin(v,in);!in.end();++in) {
351 if(p[t] == v)
continue;
353 double W=w(*in,in.source(),in.target());
360 DecreaseUpdate(p[v],v,w,in,out);
362 IncreaseUpdate(p[v],v,w,in,out);
365 for(g.Begin(v,out);!out.end();++out) {
367 IncreaseUpdate(v,t,w,in,out);
373 template <
class Node,
class Edge>
374 template <
typename WeightFunc,
typename Iterator>
378 for(
int i=0;i<nn;i++) H.push(i,-d[i]);
380 int n=H.top(); H.pop();
383 LOG4CXX_INFO(KrisLibrary::logger(),
"The start doesn't have distance 0\n");
387 for(g.Begin(n,it);!it.end();++it) {
389 double W=w(*it,it.source(),it.target());
391 if(fabs(d[n]-d[t]-W) > 1e-10) {
392 LOG4CXX_INFO(KrisLibrary::logger(),
"Inconsistency in node "<< n<<
"'s weight through parent "<< t<<
", "<< d[n]<<
" vs "<<d[t]+W<<
"="<<d[t]<<
"+"<<W);
396 if(d[n]-d[t]-W > 1e-10) {
397 LOG4CXX_INFO(KrisLibrary::logger(),
"There exists a shorter path ("<<t<<
","<<n<<
") not ("<<p[n]<<
","<<n);
398 LOG4CXX_INFO(KrisLibrary::logger(),
"Weight 1 is "<< d[t]+W<<
" compared to "<< d[n]);
Common math typedefs, constants, functions.
Implements a heap that stores objects of type type, with priority keys of type ptype.
Definition: Heap.h:19
int IsInf(double x)
Returns +1 if x is +inf, -1 if x is -inf, and 0 otherwise.
Definition: infnan.cpp:40
A heap of fixed maximum size N. Each element is indexed by an integer 0...N-1. The priority key of ea...
Definition: FixedSizeHeap.h:13
Single-source shortest paths (Dijkstra's algorithm)
Definition: ShortestPaths.h:39
virtual void SetDistance(int n, Real dn, int pn)
Definition: ShortestPaths.h:144
The logging system used in KrisLibrary.
Namespace for all classes and functions in the Graph subdirectory.
Definition: ApproximateShortestPaths.h:7