1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
/**
*
* This file is part of Tulip (https://tulip.labri.fr)
*
* Authors: David Auber and the Tulip development Team
* from LaBRI, University of Bordeaux
*
* Tulip is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License
* as published by the Free Software Foundation, either version 3
* of the License, or (at your option) any later version.
*
* Tulip is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU General Public License for more details.
*
*/
#ifndef DFS_H_
#define DFS_H_
#include <QTime>
#include <cfloat>
#include <vector>
#include <tulip/Node.h>
#include <tulip/Edge.h>
#include <tulip/StaticProperty.h>
#include "../PathAlgorithm.h"
namespace tlp {
class BooleanProperty;
class DoubleProperty;
class Graph;
class PluginProgress;
/**
* @brief An implementation of the DFS algorithm to find all the existing paths between two nodes.
*/
class DFS : public PathAlgorithm {
public:
/**
* Initiate the DFS algorithm parameters.
* @param result The boolean property where to store the results.
* @param dists A working double property where distances between nodes and the target node will
* be stored.
* @param tgt the target node.
* @param weights the edges weights.
* @param edgesOrientation The edge orientation policy.
* @param maxDist The maximal distance the algorithm can go from the source node before dropping
* the search (DBL_MAX by default)
*/
DFS(tlp::Graph *graph, tlp::BooleanProperty *result, tlp::node tgt,
const tlp::EdgeStaticProperty<double> &weights, EdgeOrientation edgesOrientation,
double maxDist = DBL_MAX);
/**
* Compute the path between the source node and the target node. Caution ! This method is
* recursive and could cause a stack overflow on big graphs.
* @param src The source node.
* @return true if a path has been found.
*/
bool searchPaths(tlp::node src);
private:
tlp::Graph *graph;
tlp::BooleanProperty *result;
tlp::node src, tgt;
const tlp::EdgeStaticProperty<double> &weights;
std::vector<tlp::edge> path;
double currentDist;
EdgeOrientation edgesOrientation;
double maxDist;
// plugin progress management
PluginProgress *progress;
unsigned int nbPaths;
QTime lastProgressTime;
bool computeSearchPaths(tlp::node src, tlp::BooleanProperty *visitable,
tlp::DoubleProperty *dists);
void updateProgressComment();
};
} // namespace tlp
#endif /* DFS_H_ */
|
