1 #ifndef GRAPH_APPROXIMATE_SHORTEST_PATHS_H 2 #define GRAPH_APPROXIMATE_SHORTEST_PATHS_H 5 #include "ShortestPaths.h" 16 template <
class Node,
class Edge>
23 void InitializeSource(
int s);
24 void InitializeSources(
const vector<int>& s);
26 template <
typename WeightFunc,
typename Iterator>
27 void FindPath(
int t,WeightFunc w,Iterator it);
28 template <
typename WeightFunc,
typename Iterator>
29 int FindAPath(
const vector<int>& t,WeightFunc w,Iterator it);
30 template <
typename WeightFunc,
typename Iterator>
31 inline void FindAllPaths(WeightFunc w,Iterator it) { FindPath(-1,w,it); }
35 template <
typename WeightFunc,
typename InIterator,
typename OutIterator>
36 void IncreaseUpdate(
int u,
int v,WeightFunc w,InIterator in,OutIterator out);
37 template <
typename WeightFunc,
typename InIterator,
typename OutIterator>
38 void DecreaseUpdate(
int u,
int v,WeightFunc w,InIterator in,OutIterator out);
39 template <
typename WeightFunc,
typename InIterator,
typename OutIterator>
40 void DeleteUpdate(
int u,
int v,WeightFunc w,InIterator in,OutIterator out);
42 template <
typename WeightFunc,
typename Iterator>
43 bool HasShortestPaths(
int s,WeightFunc w,Iterator it,Real epsilon=-1);
47 template <
typename WeightFunc>
48 inline void FindPath_Directed(
int t,WeightFunc w) {
51 template <
typename WeightFunc>
52 inline int FindAPath_Directed(
const vector<int>& t,WeightFunc w) {
55 template <
typename WeightFunc>
56 inline void FindAllPaths_Directed(WeightFunc w) {
60 template <
typename WeightFunc>
61 inline void IncreaseUpdate_Directed(
int u,
int v,WeightFunc w) {
63 IncreaseUpdate(u,v,w,in,out);
65 template <
typename WeightFunc>
66 inline void DecreaseUpdate_Directed(
int u,
int v,WeightFunc w) {
68 DecreaseUpdate(u,v,w,in,out);
70 template <
typename WeightFunc>
71 inline void DeleteUpdate_Directed(
int u,
int v,WeightFunc w) {
73 DeleteUpdate(u,v,w,in,out);
75 template <
typename WeightFunc>
76 inline bool HasShortestPaths_Directed(
int s,WeightFunc w,Real epsilon=-1) {
78 return HasShortestPaths(s,w,it,epsilon);
81 template <
typename WeightFunc>
82 inline void FindPath_Undirected(
int t,WeightFunc w) {
86 template <
typename WeightFunc>
87 inline int FindAPath_Undirected(
const vector<int>& t,WeightFunc w) {
90 template <
typename WeightFunc>
91 inline void FindAllPaths_Undirected(WeightFunc w) {
94 template <
typename WeightFunc>
95 inline void IncreaseUpdate_Undirected(
int u,
int v,WeightFunc w) {
97 IncreaseUpdate(u,v,w,it,it);
98 IncreaseUpdate(v,u,w,it,it);
100 template <
typename WeightFunc>
101 inline void DecreaseUpdate_Undirected(
int u,
int v,WeightFunc w) {
103 DecreaseUpdate(u,v,w,it,it);
104 DecreaseUpdate(v,u,w,it,it);
106 template <
typename WeightFunc>
107 inline void DeleteUpdate_Undirected(
int u,
int v,WeightFunc w) {
109 DeleteUpdate(u,v,w,it,it);
110 DeleteUpdate(v,u,w,it,it);
112 template <
typename WeightFunc>
113 inline bool HasShortestPaths_Undirected(
int s,WeightFunc w,Real epsilon=-1) {
115 return HasShortestPaths(s,w,it,epsilon);
122 virtual void SetDistance(
int n,Real dn,
int pn) { d[n]=dn; p[n]=pn; }
128 std::vector<Weight> d;
134 template <
class Node,
class Edge>
137 :g(_g),epsilon(_epsilon)
140 template <
class Node,
class Edge>
144 int nn = g.NumNodes();
147 for(
int i=0;i<nn;i++) {
154 template <
class Node,
class Edge>
158 int nn = g.NumNodes();
161 for(
int i=0;i<nn;i++) {
165 for(
size_t i=0;i<s.size();i++)
169 template <
class Node,
class Edge>
170 template <
typename WeightFunc,
typename Iterator>
175 for(
int i=0;i<nn;i++) H.push(i,-d[i]);
176 Real fudgeFactor = (1.0+epsilon);
180 int u = H.top(); H.pop();
183 for(g.Begin(u,it);!it.end();it++) {
186 Weight dvu = d[u] + w(*it,it.source(),it.target());
187 if(d[v] > dvu*fudgeFactor) {
195 template <
class Node,
class Edge>
196 template <
typename WeightFunc,
typename Iterator>
201 for(
int i=0;i<nn;i++) H.push(i,-d[i]);
204 for(
size_t i=0;i<t.size();i++) targetSet.insert(t[i]);
205 Real fudgeFactor = (1.0+epsilon);
209 int u = H.top(); H.pop();
210 if(targetSet.count(u)!=0)
return u;
212 for(g.Begin(u,it);!it.end();it++) {
215 Weight dvu = d[u] + w(*it,it.source(),it.target());
216 if(d[v] > dvu*fudgeFactor) {
226 template <
class Node,
class Edge>
227 template <
typename WeightFunc,
typename InIterator,
typename OutIterator>
229 InIterator in,OutIterator out)
232 if(p[v] != u)
return;
235 for(g.Begin(v,in);!in.end();in++) {
237 if(d[v] == d[t]+w(*in,in.source(),in.target())) {
245 for(
size_t i=0;i<Q.size();i++) {
248 for(g.Begin(n,out);!out.end();out++) {
252 for(g.Begin(t,in);!in.end();in++) {
254 if(d[t]==d[s]+w(*in,in.source(),in.target())) {
259 if(p[t]==n) Q.push_back(t);
264 Real fudgeFactor = (1.0+epsilon);
266 for(
size_t i=0;i<Q.size();i++) {
268 for(g.Begin(n,in);!in.end();in++) {
270 double W=w(*in,in.source(),in.target());
271 if(d[n]>(d[s]+W)*fudgeFactor) {
278 int n=H.top(); H.pop();
279 for(g.Begin(n,out);!out.end();out++) {
281 double W=w(*out,out.source(),out.target());
282 if(d[t]>(d[n]+W)*fudgeFactor) {
290 template <
class Node,
class Edge>
291 template <
typename WeightFunc,
typename InIterator,
typename OutIterator>
293 InIterator in,OutIterator out)
296 Real fudgeFactor = (1.0+epsilon);
297 for(g.Begin(u,out);!out.end();out++)
298 if(out.target()==v) {
299 double W=w(*out,out.source(),out.target());
307 FatalError(
"ApproximateShortestPathProblem::DecreaseUpdate(): Warning, decreasing an edge that doesn't exist in the graph!");
312 int n=H.top(); H.pop();
313 for(g.Begin(n,out);!out.end();out++) {
315 double W=w(*out,out.source(),out.target());
316 if(d[t]>(d[n]+W)*fudgeFactor) {
324 template <
class Node,
class Edge>
325 template <
typename WeightFunc,
typename InIterator,
typename OutIterator>
327 InIterator in,OutIterator out)
329 Real fudgeFactor = 1.0+epsilon;
333 for(g.Begin(v,in);!in.end();++in) {
335 if(p[t] == v)
continue;
337 double W=w(*in,in.source(),in.target());
338 if(d[v] > (d[t]+W)*fudgeFactor) {
344 DecreaseUpdate(p[v],v,w,in,out);
346 IncreaseUpdate(p[v],v,w,in,out);
349 for(g.Begin(v,out);!out.end();++out) {
351 IncreaseUpdate(v,t,w,in,out);
357 template <
class Node,
class Edge>
358 template <
typename WeightFunc,
typename Iterator>
361 if(testEpsilon < 0) fudgeFactor = 1.0+epsilon;
362 else fudgeFactor = 1.0+testEpsilon;
365 for(
int i=0;i<nn;i++) H.push(i,-d[i]);
367 int n=H.top(); H.pop();
370 LOG4CXX_INFO(KrisLibrary::logger(),
"The start doesn't have distance 0\n");
374 for(g.Begin(n,it);!it.end();++it) {
376 double W=w(*it,it.source(),it.target());
378 if(fudgeFactor == 1.0) {
379 if(fabs(d[n]-d[t]-W) > 1e-10) {
380 LOG4CXX_INFO(KrisLibrary::logger(),
"Inconsistency in node "<< n<<
"'s weight through parent "<< t<<
", "<< d[n]<<
" vs "<<d[t]+W<<
"="<<d[t]<<
"+"<<W);
385 if(d[n]-(d[t]+W)*fudgeFactor > 1e-10) {
386 LOG4CXX_INFO(KrisLibrary::logger(),
"There exists a shorter path ("<<t<<
","<<n<<
") not ("<<p[n]<<
","<<n);
387 LOG4CXX_INFO(KrisLibrary::logger(),
"Weight 1 is "<< d[t]+W<<
" compared to "<< d[n]);
388 LOG4CXX_INFO(KrisLibrary::logger(),
"Fudge factor "<< fudgeFactor<<
", comparison value "<< d[n]-(d[t]-W)*fudgeFactor);
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
virtual void SetDistance(int n, Real dn, int pn)
Definition: ApproximateShortestPaths.h:122
The logging system used in KrisLibrary.
Namespace for all classes and functions in the Graph subdirectory.
Definition: ApproximateShortestPaths.h:7
Approximate single-source shortest paths, whose output is at most (1+epsilon)^d times the true shorte...
Definition: ApproximateShortestPaths.h:17