KrisLibrary  1.0.0
APSP.h
1 #ifndef GRAPH_ALL_PAIRS_SHORTEST_PATHS_H
2 #define GRAPH_ALL_PAIRS_SHORTEST_PATHS_H
3 
4 #include "ShortestPaths.h"
5 #include "Path.h"
6 #include "Operations.h"
7 
8 namespace Graph {
9 
10 const static Weight inf = Math::dInf;
11 
12 template <class Node,Edge>
13 class SetUpdatingShortestPathProblem<Node,Edge>;
14 
36 template <class Node,class Edge>
37 class APSP
38 {
39  public:
40  APSP(const Graph<Node,Edge>& g);
41  virtual ~APSP() {}
42  void SolveFloydWarshall_Directed(WeightFunc w);
43  void SolveFloydWarshall_Undirected(WeightFunc w);
44  void SolveDijkstras_Directed(WeightFunc w);
45  void SolveDijkstras_Undirected(WeightFunc w);
46  Real GetDistance(int i,int j) const;
47  bool GetPath(int i,int j,std::vector<int>& path) const;
48 
49  void InitDynamicUpdates_Directed();
50  void InitDynamicUpdates_Undirected();
51  void IncreaseUpdate_Directed(int u,int v,WeightFunc w);
52  void DecreaseUpdate_Directed(int u,int v,WeightFunc w);
53  void IncreaseUpdate_Undirected(int u,int v,WeightFunc w);
54  void DecreaseUpdate_Undirected(int u,int v,WeightFunc w);
55 
56  const Graph<Node,Edge>& g;
57 
58  //Floyd Warshall
59  std::vector<std::vector<Weight> > d;
60  std::vector<std::vector<int> > next;
61 
62  //Dijkstra
63  std::vector<std::shared_ptr<SetUpdatingShortestPathProblem<Node,Edge> > > spps;
64  Graph<int,std::set<int> > edgeSets;
65 };
66 
67 template <class Node,Edge>
68 class SetUpdatingShortestPathProblem<Node,Edge> : public ShortestPathProblem<Node,Edge>
69 {
70  public:
71  virtual void SetDistance(int n,Real dn,int pn)
72  {
73  if(!edgeSets) {
75  return;
76  }
77  Real dold = d[n];
78  int pold = p[n];
80  std::set<int>* s = *edgeSets->FindEdge(pold,n);
81  s->remove(index);
82  s = *edgeSets->FindEdge(pn,n);
83  s->insert(index);
84  }
85 
86  int index;
87  Graph<int,std::set<int> >* edgeSets;
88 };
89 
90 template <class Node,Edge>
91 APSP<Node,Edge>::APSP(const Graph<Node,Edge>& _g)
92  :g(_g)
93  {}
94 
95 template <class Node,Edge>
96 void APSP<Node,Edge>::SolveFloydWarshall_Directed(WeightFunc w)
97 {
98  EdgeIterator<Edge> e;
99  int n=ng.NumNodes();
100  d.resize();
101  next.resize(n);
102  for(int i=0;i<n;i++) {
103  d[i].resize(n);
104  next[i].resize(n);
105  fill(d[i].begin(),d[i].end(),inf);
106  fill(next[i].begin(),next[i].end(),-1);
107  for(g.Begin(i,e);!e.end();e++) {
108  d[i][e.target()] = w(*e,i,e.target());
109  }
110  d[i][i] = 0.0;
111  }
112  for(int k=0;k<n;k++)
113  for(int i=0;i<n;i++)
114  for(int j=0;j<n;j++) {
115  if(d[i][k]+d[k][j] < d[i][j]) {
116  d[i][j] = d[i][k]+d[k][j];
117  next[i][j] = k;
118  }
119  }
120 }
121 
122 
123 template <class Node,Edge>
124 void APSP<Node,Edge>::SolveFloydWarshall_Undirected(WeightFunc w)
125 {
126  UndirectedEdgeIterator<Edge> e;
127  int n=ng.NumNodes();
128  d.resize();
129  next.resize(n);
130  for(int i=0;i<n;i++) {
131  d[i].resize(n);
132  next[i].resize(n);
133  fill(d[i].begin(),d[i].end(),inf);
134  fill(next[i].begin(),next[i].end(),-1);
135  for(g.Begin(i,e);!e.end();e++) {
136  d[i][e.target()] = w(*e,i,e.target());
137  }
138  d[i][i] = 0.0;
139  }
140  for(int k=0;k<n;k++)
141  for(int i=0;i<n;i++)
142  for(int j=0;j<n;j++) {
143  if(d[i][k]+d[k][j] < d[i][j]) {
144  d[i][j] = d[i][k]+d[k][j];
145  next[i][j] = k;
146  }
147 }
148 
149 template <class Node,Edge>
150 void APSP<Node,Edge>::SolveDijkstras_Directed(WeightFunc w)
151 {
152  spp.resize(g.nodes.size());
153  for(size_t i=0;i<g.nodes.size();i++) {
154  spp[i] = new SetUpdatingShortestPathsProblem<Node,Edge>(g);
155  spp[i]->index = i;
156  spp[i]->edgeSets = NULL;
157  spp[i]->InitializeSource(i);
158  spp[i]->FindAllPaths_Directed(w);
159  }
160 }
161 
162 template <class Node,Edge>
163 void APSP<Node,Edge>::SolveDijkstras_Undirected(WeightFunc w)
164 {
165  spp.resize(g.nodes.size());
166  for(size_t i=0;i<g.nodes.size();i++) {
167  spp[i] = new SetUpdatingShortestPathsProblem<Node,Edge>(g);
168  spp[i]->index = i;
169  spp[i]->edgeSets = NULL;
170  spp[i]->InitializeSource(i);
171  spp[i]->FindAllPaths_Undirected(w);
172  }
173 }
174 
175 template <class Node,Edge>
176 Real APSP<Node,Edge>::GetDistance(int i,int j) const
177 {
178  if(!d.empty()) return d[i][j];
179  else {
180  Assert(!spp.empty());
181  return spp[i].d[j];
182  }
183 }
184 
185 template <class Node,Edge>
186 bool APSP<Node,Edge>::GetPath(int i,int j,std::vector<int>& path) const
187 {
188  if(!d.empty()) {
189  path.resize(0);
190  if(next[i][j] < 0) return false;
191  if(i == j) {
192  path.push_back(i);
193  return true;
194  }
195  std::vector<int> p1,p2;
196  GetPath(i,next[i][j],p1);
197  GetPath(next[i][j],j,p2);
198  path = p1;
199  path.insert(path.end(),++p2.begin(),p2.end());
200  return true;
201  }
202  else {
203  Assert(!spp.empty());
204  return GetAncestorPath(spp[i]->p,j,-1,path);
205  }
206 }
207 
208 template <class Node,Edge>
209 void APSP<Node,Edge>::InitDynamicUpdates_Directed()
210 {
211  Assert(!spp.empty());
212  //initialize edgeSets structure
213  CopyStructure(g,edgeSets);
214  //mark which edges are in which SPP problems
215  for(size_t i=0;i<spp.size();i++) {
216  spp[i]->edgeSets = &edgeSets;
217  for(size_t j=0;j<spp[i]->p.size();j++)
218  if(spp[i]->p[j] >= 0)
219  edgeSets.FindEdge(j,spp[i]->p[j])->insert(i);
220  }
221 }
222 
223 template <class Node,Edge>
224 void APSP<Node,Edge>::InitDynamicUpdates_Undirected()
225 {
226  Assert(!spp.empty());
227  //add forward and reverse edges
228  edgeSets.Cleanup();
229  edgeSets.Resize(g.nodes.size());
230  for(size_t i=0;i<g.nodes.size();i++) {
231  EdgeIterator<E1> e;
232  for(g.Begin(i,e);!e.end();e++) {
233  edgeSets.AddEdge(i,e.target());
234  edgeSets.AddEdge(e.target(),i);
235  }
236  }
237  //mark which edges are in which SPP problems
238  for(size_t i=0;i<spp.size();i++) {
239  spp[i]->edgeSets = &edgeSets;
240  for(size_t j=0;j<spp[i]->p.size();j++)
241  if(spp[i]->p[j] >= 0)
242  edgeSets.FindEdge(j,spp[i]->p[j])->insert(i);
243  }
244 }
245 
246 
247 template <class Node,Edge>
248 void APSP<Node,Edge>::IncreaseUpdate_Directed(int u,int v,WeightFunc w)
249 {
250  EdgeIterator<std::set<int> >* e=edgeSets.FindEdge(u,v);
251  Assert(e!=NULL);
252  for(std::set<int>::iterator i=(*e)->begin();i!=(*e)->end();i++) {
253  spp[*i]->IncreaseUpdate_Directed(u,v,w);
254  }
255 }
256 
257 template <class Node,Edge>
258 void APSP<Node,Edge>::DecreaseUpdate_Directed(int u,int v,WeightFunc w)
259 {
260  EdgeIterator<std::set<int> >* e=edgeSets.FindEdge(u,v);
261  Assert(e!=NULL);
262  for(std::set<int>::iterator i=(*e)->begin();i!=(*e)->end();i++) {
263  spp[*i]->DecreaseUpdate_Directed(u,v,w);
264  }
265 }
266 
267 template <class Node,Edge>
268 void APSP<Node,Edge>::IncreaseUpdate_Undirected(int u,int v,WeightFunc w)
269 {
270  EdgeIterator<std::set<int> >* e=edgeSets.FindEdge(u,v);
271  Assert(e!=NULL);
272  for(std::set<int>::iterator i=(*e)->begin();i!=(*e)->end();i++) {
273  spp[*i]->IncreaseUpdate_Undirected(u,v,w);
274  }
275  e=edgeSets.FindEdge(v,u);
276  Assert(e!=NULL);
277  for(std::set<int>::iterator i=(*e)->begin();i!=(*e)->end();i++) {
278  spp[*i]->IncreaseUpdate_Undirected(v,u,w);
279  }
280 }
281 
282 template <class Node,Edge>
283 void APSP<Node,Edge>::DecreaseUpdate_Undirected(int u,int v,WeightFunc w)
284 {
285  EdgeIterator<std::set<int> >* e=edgeSets.FindEdge(u,v);
286  Assert(e!=NULL);
287  for(std::set<int>::iterator i=(*e)->begin();i!=(*e)->end();i++) {
288  spp[*i]->IncreaseUpdate_Undirected(u,v,w);
289  }
290  e=edgeSets.FindEdge(v,u);
291  Assert(e!=NULL);
292  for(std::set<int>::iterator i=(*e)->begin();i!=(*e)->end();i++) {
293  spp[*i]->IncreaseUpdate_Undirected(v,u,w);
294  }
295 }
296 
297 
298 } //namespace Graph
299 
300 #endif
void CopyStructure(const Graph< N1, E1 > &G1, Graph< N2, E2 > &G2)
Copies the edge structure of G1 to G2 without setting its data.
Definition: Operations.h:14
bool GetAncestorPath(const std::vector< int > &p, int n, int lastAncestor, std::list< int > &path)
Calculates a path of nodes from a list of parents.
Definition: graph/Path.h:25
Abstract base class for an edge planner / edge checker (i.e., local planner).
Definition: EdgePlanner.h:49
bool fill(AnyCollection &universe, bool checkSuperset=false)
Definition: AnyCollection.cpp:1336
A tree graph structure, represented directly at the node level.
Definition: Tree.h:25
virtual void SetDistance(int n, Real dn, int pn)
Definition: ShortestPaths.h:144
Namespace for all classes and functions in the Graph subdirectory.
Definition: ApproximateShortestPaths.h:7