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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
/**
*
* 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.
*
*/
#include "DFS.h"
#include <stack>
#include <tulip/BooleanProperty.h>
#include <tulip/DoubleProperty.h>
#include <tulip/ForEach.h>
using namespace tlp;
using namespace std;
DFS::DFS(Graph *graph, BooleanProperty *result, DoubleProperty *dists, node tgt, MutableContainer<double> &weights, EdgeOrientation edgesOrientation, double maxDist) :
graph(graph), result(result), dists(dists), tgt(tgt), currentDist(0), edgesOrientation(edgesOrientation), maxDist(maxDist) {
#ifndef NDEBUG
assert(graph->getRoot() == result->getGraph()->getRoot());
#endif /* NDEBUG */
dists->setAllNodeValue(DBL_MAX);
visitable = new BooleanProperty(graph);
visitable->setAllNodeValue(true);
visitable->setAllEdgeValue(true);
this->weights = &weights;
}
DFS::~DFS() {
delete visitable;
}
bool DFS::searchPaths(node src) {
if (!visitable->getNodeValue(src))
return false;
if (dists->getNodeValue(src) != DBL_MAX && currentDist + dists->getNodeValue(src) > maxDist)
return false;
if (currentDist > maxDist)
return false;
else if (src == tgt || result->getNodeValue(src)) {
double distLeft(0);
if (result->getNodeValue(src))
distLeft = dists->getNodeValue(src);
node nd(src);
for (vector<edge>::reverse_iterator it = path.rbegin(); it != path.rend(); ++it) {
edge e(*it);
node opposite(graph->opposite(e, nd));
result->setEdgeValue(e, true);
result->setNodeValue(opposite, true);
result->setNodeValue(nd, true);
dists->setNodeValue(nd, min<double> (distLeft, dists->getNodeValue(nd)));
distLeft += weights->get(e.id);
nd = opposite;
}
dists->setNodeValue(nd, min<double> (distLeft, dists->getNodeValue(nd)));
return true;
}
bool result = false;
visitable->setNodeValue(src, false);
edge e;
Iterator<edge> *edgeIt=0;
switch (edgesOrientation) {
case NonOriented:
edgeIt = graph->getInOutEdges(src);
break;
case Oriented:
edgeIt = graph->getOutEdges(src);
break;
case Reversed:
edgeIt = graph->getInEdges(src);
break;
}
while (edgeIt->hasNext()) {
edge e=edgeIt->next();
currentDist += weights->get(e.id);
path.push_back(e);
result |= searchPaths(graph->opposite(e, src));
path.pop_back();
currentDist -= weights->get(e.id);
}
delete edgeIt;
visitable->setNodeValue(src, true);
return result;
}
|
