1 #ifndef GRAPH_ALL_PAIRS_SHORTEST_PATHS_H 2 #define GRAPH_ALL_PAIRS_SHORTEST_PATHS_H 4 #include "ShortestPaths.h" 6 #include "Operations.h" 10 const static Weight inf = Math::dInf;
12 template <
class Node,Edge>
13 class SetUpdatingShortestPathProblem<
Node,
Edge>;
36 template <
class Node,
class Edge>
40 APSP(
const Graph<Node,Edge>& g);
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;
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);
56 const Graph<Node,Edge>& g;
59 std::vector<std::vector<Weight> > d;
60 std::vector<std::vector<int> > next;
63 std::vector<std::shared_ptr<SetUpdatingShortestPathProblem<Node,Edge> > > spps;
64 Graph<int,std::set<int> > edgeSets;
67 template <
class Node,Edge>
68 class SetUpdatingShortestPathProblem<
Node,
Edge> :
public ShortestPathProblem<Node,Edge>
71 virtual void SetDistance(
int n,Real dn,
int pn)
80 std::set<int>* s = *edgeSets->FindEdge(pold,n);
82 s = *edgeSets->FindEdge(pn,n);
87 Graph<int,std::set<int> >* edgeSets;
90 template <
class Node,Edge>
91 APSP<Node,Edge>::APSP(
const Graph<Node,Edge>& _g)
95 template <
class Node,Edge>
96 void APSP<Node,Edge>::SolveFloydWarshall_Directed(WeightFunc w)
102 for(
int i=0;i<n;i++) {
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());
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];
123 template <
class Node,Edge>
124 void APSP<Node,Edge>::SolveFloydWarshall_Undirected(WeightFunc w)
126 UndirectedEdgeIterator<Edge> e;
130 for(
int i=0;i<n;i++) {
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());
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];
149 template <
class Node,Edge>
150 void APSP<Node,Edge>::SolveDijkstras_Directed(WeightFunc w)
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);
156 spp[i]->edgeSets = NULL;
157 spp[i]->InitializeSource(i);
158 spp[i]->FindAllPaths_Directed(w);
162 template <
class Node,Edge>
163 void APSP<Node,Edge>::SolveDijkstras_Undirected(WeightFunc w)
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);
169 spp[i]->edgeSets = NULL;
170 spp[i]->InitializeSource(i);
171 spp[i]->FindAllPaths_Undirected(w);
175 template <
class Node,Edge>
176 Real APSP<Node,Edge>::GetDistance(
int i,
int j)
const 178 if(!d.empty())
return d[i][j];
180 Assert(!spp.empty());
185 template <
class Node,Edge>
186 bool APSP<Node,Edge>::GetPath(
int i,
int j,std::vector<int>& path)
const 190 if(next[i][j] < 0)
return false;
195 std::vector<int> p1,p2;
196 GetPath(i,next[i][j],p1);
197 GetPath(next[i][j],j,p2);
199 path.insert(path.end(),++p2.begin(),p2.end());
203 Assert(!spp.empty());
208 template <
class Node,Edge>
209 void APSP<Node,Edge>::InitDynamicUpdates_Directed()
211 Assert(!spp.empty());
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);
223 template <
class Node,Edge>
224 void APSP<Node,Edge>::InitDynamicUpdates_Undirected()
226 Assert(!spp.empty());
229 edgeSets.Resize(g.nodes.size());
230 for(
size_t i=0;i<g.nodes.size();i++) {
232 for(g.Begin(i,e);!e.end();e++) {
233 edgeSets.AddEdge(i,e.target());
234 edgeSets.AddEdge(e.target(),i);
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);
247 template <
class Node,Edge>
248 void APSP<Node,Edge>::IncreaseUpdate_Directed(
int u,
int v,WeightFunc w)
250 EdgeIterator<std::set<int> >* e=edgeSets.FindEdge(u,v);
252 for(std::set<int>::iterator i=(*e)->begin();i!=(*e)->end();i++) {
253 spp[*i]->IncreaseUpdate_Directed(u,v,w);
257 template <
class Node,Edge>
258 void APSP<Node,Edge>::DecreaseUpdate_Directed(
int u,
int v,WeightFunc w)
260 EdgeIterator<std::set<int> >* e=edgeSets.FindEdge(u,v);
262 for(std::set<int>::iterator i=(*e)->begin();i!=(*e)->end();i++) {
263 spp[*i]->DecreaseUpdate_Directed(u,v,w);
267 template <
class Node,Edge>
268 void APSP<Node,Edge>::IncreaseUpdate_Undirected(
int u,
int v,WeightFunc w)
270 EdgeIterator<std::set<int> >* e=edgeSets.FindEdge(u,v);
272 for(std::set<int>::iterator i=(*e)->begin();i!=(*e)->end();i++) {
273 spp[*i]->IncreaseUpdate_Undirected(u,v,w);
275 e=edgeSets.FindEdge(v,u);
277 for(std::set<int>::iterator i=(*e)->begin();i!=(*e)->end();i++) {
278 spp[*i]->IncreaseUpdate_Undirected(v,u,w);
282 template <
class Node,Edge>
283 void APSP<Node,Edge>::DecreaseUpdate_Undirected(
int u,
int v,WeightFunc w)
285 EdgeIterator<std::set<int> >* e=edgeSets.FindEdge(u,v);
287 for(std::set<int>::iterator i=(*e)->begin();i!=(*e)->end();i++) {
288 spp[*i]->IncreaseUpdate_Undirected(u,v,w);
290 e=edgeSets.FindEdge(v,u);
292 for(std::set<int>::iterator i=(*e)->begin();i!=(*e)->end();i++) {
293 spp[*i]->IncreaseUpdate_Undirected(v,u,w);
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:1344
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