Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
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 <unordered_map>
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
35namespace tlp {
36
37class Dijkstra {
38public:
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(std::unordered_map<node, std::list<node>> &result);
49
50private:
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