Tulip  6.0.0
Large graphs analysis and drawing
Dijkstra.h
1 /**
2  *
3  * This file is part of Tulip (https://tulip.labri.fr)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16  * See the GNU General Public License for more details.
17  *
18  */
19 
20 ///@cond DOXYGEN_HIDDEN
21 #ifndef DIJKSTRA_H
22 #define DIJKSTRA_H
23 
24 #include <vector>
25 #include <stack>
26 #include <list>
27 #include <tulip/tuliphash.h>
28 #include <functional>
29 #include <tulip/Graph.h>
30 #include <tulip/BooleanProperty.h>
31 #include <tulip/StaticProperty.h>
32 #include <tulip/MutableContainer.h>
33 #include <tulip/GraphTools.h>
34 
35 namespace tlp {
36 
37 class Dijkstra {
38 public:
39  //============================================================
40  Dijkstra(const Graph *const graph, node src, const EdgeStaticProperty<double> &weights,
41  NodeStaticProperty<double> &nodeDistance, EDGE_TYPE direction,
42  std::stack<node> *qN = nullptr, MutableContainer<int> *nP = nullptr);
43  //========================================================
44  bool searchPaths(node n, BooleanProperty *result);
45  //=========================================================
46  bool searchPath(node n, BooleanProperty *result);
47  //=============================================================
48  bool ancestors(tlp_hash_map<node, std::list<node>> &result);
49 
50 private:
51  void internalSearchPaths(node n, BooleanProperty *result);
52  //=========================================================
53  struct DijkstraElement {
54  DijkstraElement(const double dist = DBL_MAX, const node previous = node(),
55  const node n = node())
56  : dist(dist), previous(previous), n(n) {}
57  bool operator==(const DijkstraElement &b) const {
58  return n == b.n;
59  }
60  bool operator!=(const DijkstraElement &b) const {
61  return n != b.n;
62  }
63  double dist;
64  node previous;
65  node n;
66  std::vector<edge> usedEdge;
67  };
68 
69  struct LessDijkstraElement {
70  bool operator()(const DijkstraElement *const a, const DijkstraElement *const b) const {
71  if (fabs(a->dist - b->dist) > 1.E-9) {
72  return (a->dist < b->dist);
73  } else {
74  return (a->n.id < b->n.id);
75  }
76  }
77  };
78 
79  Graph const *graph;
80  node src;
81  MutableContainer<bool> usedEdges;
82  NodeStaticProperty<double> &nodeDistance;
83  std::stack<node> *queueNodes;
84  MutableContainer<int> *numberOfPaths;
85 };
86 } // namespace tlp
87 
88 #endif // DIJKSTRA_H
89 ///@endcond