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
|
/**
*
* This file is part of Tulip (www.tulip-software.org)
*
* 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 <float.h>
#include <vector>
#include <tulip/Node.h>
#include <tulip/Edge.h>
#include <tulip/MutableContainer.h>
#include "../PathAlgorithm.h"
namespace tlp {
class BooleanProperty;
class DoubleProperty;
class Graph;
/**
* @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::DoubleProperty *dists, tlp::node tgt, tlp::MutableContainer<double> &weights, EdgeOrientation edgesOrientation, double maxDist=DBL_MAX);
~DFS();
/**
* 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::DoubleProperty *dists;
tlp::BooleanProperty *visitable;
tlp::node tgt;
tlp::MutableContainer<double> *weights;
std::vector<tlp::edge> path;
double currentDist;
EdgeOrientation edgesOrientation;
double maxDist;
};
}
#endif /* DFS_H_ */
|
