Tulip  5.3.0
Large graphs analysis and drawing
Dikjstra.h
1 /**
2  *
3  * This file is part of Tulip (http://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 DIKJSTRA_TOOL_H
22 #define DIKJSTRA_TOOL_H
23 #include <vector>
24 #include <set>
25 #include <climits>
26 #include <functional>
27 #include <tulip/Graph.h>
28 #include <tulip/Vector.h>
29 #include <tulip/LayoutProperty.h>
30 #include <tulip/DoubleProperty.h>
31 #include <tulip/StaticProperty.h>
32 #include <tulip/MutableContainer.h>
33 
34 namespace tlp {
35 
36 class Dikjstra {
37 public:
38  //============================================================
39  Dikjstra(const Graph *const graph, node src, const EdgeStaticProperty<double> &weights,
40  NodeStaticProperty<double> &nodeDistance,
41  std::function<Iterator<edge> *(node)> &getFunc);
42  //========================================================
43  bool searchPaths(node n, BooleanProperty *result);
44  //=========================================================
45  bool searchPath(node n, BooleanProperty *result);
46  //=============================================================
47 private:
48  void internalSearchPaths(node n, BooleanProperty *result);
49  //=========================================================
50  struct DikjstraElement {
51  DikjstraElement(const double dist = DBL_MAX, const node previous = node(),
52  const node n = node())
53  : dist(dist), previous(previous), n(n) {}
54  bool operator==(const DikjstraElement &b) const {
55  return n == b.n;
56  }
57  bool operator!=(const DikjstraElement &b) const {
58  return n != b.n;
59  }
60  double dist;
61  node previous;
62  node n;
63  std::vector<edge> usedEdge;
64  };
65 
66  struct LessDikjstraElement {
67  bool operator()(const DikjstraElement *const a, const DikjstraElement *const b) const {
68  if (fabs(a->dist - b->dist) > 1.E-9) {
69  return (a->dist < b->dist);
70  } else {
71  return (a->n.id < b->n.id);
72  }
73  }
74  };
75 
76  Graph const *graph;
77  node src;
78  MutableContainer<bool> usedEdges;
79  NodeStaticProperty<double> &nodeDistance;
80 };
81 } // namespace tlp
82 #endif // DIKJSTRA_H
83 ///@endcond