KrisLibrary  1.0.0
ApproximateShortestPaths.h
1 #ifndef GRAPH_APPROXIMATE_SHORTEST_PATHS_H
2 #define GRAPH_APPROXIMATE_SHORTEST_PATHS_H
3 
4 #include <KrisLibrary/Logger.h>
5 #include "ShortestPaths.h"
6 
7 namespace Graph {
8 
16 template <class Node,class Edge>
18 {
19  public:
20  ApproximateShortestPathProblem(const Graph<Node,Edge>& g,Real epsilon=0);
21  virtual ~ApproximateShortestPathProblem() {}
22 
23  void InitializeSource(int s);
24  void InitializeSources(const vector<int>& s);
25 
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); }
32 
33  //after all paths are found, the shortest paths can be updated with the following
34  //when an edge (u,v)'s weight is increased/decreased, call these methods
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);
41 
42  template <typename WeightFunc,typename Iterator>
43  bool HasShortestPaths(int s,WeightFunc w,Iterator it,Real epsilon=-1);
44 
45  //template specializations (directed/undirected)
46 
47  template <typename WeightFunc>
48  inline void FindPath_Directed(int t,WeightFunc w) {
49  FindPath(t,w,EdgeIterator<Edge>());
50  }
51  template <typename WeightFunc>
52  inline int FindAPath_Directed(const vector<int>& t,WeightFunc w) {
53  return FindAPath(t,w,EdgeIterator<Edge>());
54  }
55  template <typename WeightFunc>
56  inline void FindAllPaths_Directed(WeightFunc w) {
58  FindAllPaths(w,it);
59  }
60  template <typename WeightFunc>
61  inline void IncreaseUpdate_Directed(int u,int v,WeightFunc w) {
63  IncreaseUpdate(u,v,w,in,out);
64  }
65  template <typename WeightFunc>
66  inline void DecreaseUpdate_Directed(int u,int v,WeightFunc w) {
68  DecreaseUpdate(u,v,w,in,out);
69  }
70  template <typename WeightFunc>
71  inline void DeleteUpdate_Directed(int u,int v,WeightFunc w) {
73  DeleteUpdate(u,v,w,in,out);
74  }
75  template <typename WeightFunc>
76  inline bool HasShortestPaths_Directed(int s,WeightFunc w,Real epsilon=-1) {
78  return HasShortestPaths(s,w,it,epsilon);
79  }
80 
81  template <typename WeightFunc>
82  inline void FindPath_Undirected(int t,WeightFunc w) {
84  FindPath(t,w,it);
85  }
86  template <typename WeightFunc>
87  inline int FindAPath_Undirected(const vector<int>& t,WeightFunc w) {
88  return FindAPath(t,w,UndirectedEdgeIterator<Edge>());
89  }
90  template <typename WeightFunc>
91  inline void FindAllPaths_Undirected(WeightFunc w) {
92  FindAllPaths(w,UndirectedEdgeIterator<Edge>());
93  }
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);
99  }
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);
105  }
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);
111  }
112  template <typename WeightFunc>
113  inline bool HasShortestPaths_Undirected(int s,WeightFunc w,Real epsilon=-1) {
115  return HasShortestPaths(s,w,it,epsilon);
116  }
117 
122  virtual void SetDistance(int n,Real dn,int pn) { d[n]=dn; p[n]=pn; }
123 
124  const Graph<Node,Edge>& g;
125  Real epsilon;
126 
127  std::vector<int> p;
128  std::vector<Weight> d;
129 };
130 
131 
132 //definition of ApproximateShortestPaths
133 
134 template <class Node,class Edge>
136 ApproximateShortestPathProblem(const Graph<Node,Edge>& _g,Real _epsilon)
137  :g(_g),epsilon(_epsilon)
138 {}
139 
140 template <class Node,class Edge>
142 {
143  //initialize
144  int nn = g.NumNodes();
145  p.resize(nn);
146  d.resize(nn);
147  for(int i=0;i<nn;i++) {
148  p[i] = -1;
149  d[i] = inf;
150  }
151  d[s] = 0;
152 }
153 
154 template <class Node,class Edge>
156 {
157  //initialize
158  int nn = g.NumNodes();
159  p.resize(nn);
160  d.resize(nn);
161  for(int i=0;i<nn;i++) {
162  p[i] = -1;
163  d[i] = inf;
164  }
165  for(size_t i=0;i<s.size();i++)
166  d[s[i]] = 0;
167 }
168 
169 template <class Node,class Edge>
170 template <typename WeightFunc,typename Iterator>
171 void ApproximateShortestPathProblem<Node,Edge>::FindPath(int t,WeightFunc w,Iterator it)
172 {
173  int nn=g.NumNodes();
174  FixedSizeHeap<Weight> H(nn); //O(n) init, worst case log n update
175  for(int i=0;i<nn;i++) H.push(i,-d[i]);
176  Real fudgeFactor = (1.0+epsilon);
177 
178  while(!H.empty()) {
179  //pop the smallest distance element from q
180  int u = H.top(); H.pop();
181  if(u == t) return;
182 
183  for(g.Begin(u,it);!it.end();it++) {
184  int v=it.target();
185  //relax distances
186  Weight dvu = d[u] + w(*it,it.source(),it.target());
187  if(d[v] > dvu*fudgeFactor) {
188  SetDistance(v,dvu,u);
189  H.adjust(v,-d[v]);
190  }
191  }
192  }
193 }
194 
195 template <class Node,class Edge>
196 template <typename WeightFunc,typename Iterator>
197 int ApproximateShortestPathProblem<Node,Edge>::FindAPath(const vector<int>& t,WeightFunc w,Iterator it)
198 {
199  int nn=g.NumNodes();
200  FixedSizeHeap<Weight> H(nn); //O(n) init, worst case log n update
201  for(int i=0;i<nn;i++) H.push(i,-d[i]);
202 
203  set<int> targetSet;
204  for(size_t i=0;i<t.size();i++) targetSet.insert(t[i]);
205  Real fudgeFactor = (1.0+epsilon);
206 
207  while(!H.empty()) {
208  //pop the smallest distance element from q
209  int u = H.top(); H.pop();
210  if(targetSet.count(u)!=0) return u;
211 
212  for(g.Begin(u,it);!it.end();it++) {
213  int v=it.target();
214  //relax distances
215  Weight dvu = d[u] + w(*it,it.source(),it.target());
216  if(d[v] > dvu*fudgeFactor) {
217  SetDistance(v,dvu,u);
218  H.adjust(v,-d[v]);
219  }
220  }
221  }
222  return -1;
223 }
224 
225 
226 template <class Node,class Edge>
227 template <typename WeightFunc,typename InIterator,typename OutIterator>
229  InIterator in,OutIterator out)
230 {
231  //1) if not in the SP tree, return
232  if(p[v] != u) return;
233 
234  //2) look for alternative SP, if found, return
235  for(g.Begin(v,in);!in.end();in++) {
236  int t=in.target();
237  if(d[v] == d[t]+w(*in,in.source(),in.target())) {
238  p[v]=t;
239  return;
240  }
241  }
242 
243  //3) identify affected nodes
244  vector<int> Q(1,v);
245  for(size_t i=0;i<Q.size();i++) {
246  int n=Q[i];
247  SetDistance(n,inf,-1);
248  for(g.Begin(n,out);!out.end();out++) {
249  int t=out.target();
250  if(p[t]==n) {
251  //identify any alternative routes
252  for(g.Begin(t,in);!in.end();in++) {
253  int s=in.target();
254  if(d[t]==d[s]+w(*in,in.source(),in.target())) {
255  p[t]=s;
256  break;
257  }
258  }
259  if(p[t]==n) Q.push_back(t);
260  }
261  }
262  }
263  //4) update affected nodes by finding paths from outside nodes
264  Real fudgeFactor = (1.0+epsilon);
265  Heap<int,Weight> H; //O(1) init, O(n) adjust
266  for(size_t i=0;i<Q.size();i++) {
267  int n=Q[i];
268  for(g.Begin(n,in);!in.end();in++) {
269  int s=in.target();
270  double W=w(*in,in.source(),in.target());
271  if(d[n]>(d[s]+W)*fudgeFactor) {
272  SetDistance(n,d[s]+W,s);
273  }
274  }
275  if(!Math::IsInf(d[n])) H.push(n,-d[n]);
276  }
277  while(!H.empty()) {
278  int n=H.top(); H.pop();
279  for(g.Begin(n,out);!out.end();out++) {
280  int t=out.target();
281  double W=w(*out,out.source(),out.target());
282  if(d[t]>(d[n]+W)*fudgeFactor) {
283  SetDistance(t,d[n]+W,n);
284  H.adjust(t,-d[t]);
285  }
286  }
287  }
288 }
289 
290 template <class Node,class Edge>
291 template <typename WeightFunc,typename InIterator,typename OutIterator>
293  InIterator in,OutIterator out)
294 {
295  //NOTE: can't use find edge because it doesn't work for undirected graphs
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());
300  if(d[v] <= d[u]+W) {
301  return; //no change
302  }
303  SetDistance(v,d[u]+W,u);
304  break;
305  }
306  if(out.end()) {
307  FatalError("ApproximateShortestPathProblem::DecreaseUpdate(): Warning, decreasing an edge that doesn't exist in the graph!");
308  }
309  Heap<int,Weight> H; //O(1) init, O(n) adjust
310  H.push(v,-d[v]);
311  while(!H.empty()) {
312  int n=H.top(); H.pop();
313  for(g.Begin(n,out);!out.end();out++) {
314  int t=out.target();
315  double W=w(*out,out.source(),out.target());
316  if(d[t]>(d[n]+W)*fudgeFactor) {
317  SetDistance(t,d[n]+W,n);
318  H.adjust(t,-d[t]);
319  }
320  }
321  }
322 }
323 
324 template <class Node,class Edge>
325 template <typename WeightFunc,typename InIterator,typename OutIterator>
326 void ApproximateShortestPathProblem<Node,Edge>::DeleteUpdate(int u,int v,WeightFunc w,
327  InIterator in,OutIterator out)
328 {
329  Real fudgeFactor = 1.0+epsilon;
330  if(p[v] == u) {
331  SetDistance(v,inf,-1);
332  //find the best alternate parent
333  for(g.Begin(v,in);!in.end();++in) {
334  int t=in.target();
335  if(p[t] == v) continue;
336  Assert(t != u);
337  double W=w(*in,in.source(),in.target());
338  if(d[v] > (d[t]+W)*fudgeFactor) {
339  SetDistance(v,d[t]+W,t);
340  }
341  }
342  if(p[v] != -1) {
343  d[v] = inf;
344  DecreaseUpdate(p[v],v,w,in,out);
345  d[v] = 0;
346  IncreaseUpdate(p[v],v,w,in,out);
347  }
348  else {
349  for(g.Begin(v,out);!out.end();++out) {
350  int t=out.target();
351  IncreaseUpdate(v,t,w,in,out);
352  }
353  }
354  }
355 }
356 
357 template <class Node,class Edge>
358 template <typename WeightFunc,typename Iterator>
359 bool ApproximateShortestPathProblem<Node,Edge>::HasShortestPaths(int s,WeightFunc w,Iterator it,Real testEpsilon) {
360  Real fudgeFactor;
361  if(testEpsilon < 0) fudgeFactor = 1.0+epsilon;
362  else fudgeFactor = 1.0+testEpsilon;
363  int nn=g.NumNodes();
364  FixedSizeHeap<Weight> H(nn);
365  for(int i=0;i<nn;i++) H.push(i,-d[i]);
366  while(!H.empty()) {
367  int n=H.top(); H.pop();
368  if(n==s) {
369  if(d[n]!=0) {
370  LOG4CXX_INFO(KrisLibrary::logger(),"The start doesn't have distance 0\n");
371  return false;
372  }
373  }
374  for(g.Begin(n,it);!it.end();++it) {
375  int t=it.target();
376  double W=w(*it,it.source(),it.target());
377  if(p[n] == t) {
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);
381  return false;
382  }
383  }
384  }
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);
389  return false;
390  }
391  }
392  }
393  return true;
394 }
395 
396 
397 } //namespace Graph
398 
399 #endif
Definition: Edge.h:28
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
Definition: Edge.h:58
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
Definition: Edge.h:88
Approximate single-source shortest paths, whose output is at most (1+epsilon)^d times the true shorte...
Definition: ApproximateShortestPaths.h:17