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
114
115
116
117
118
119
120
121
122
123
124
125
|
/**
*
* 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 "PathAlgorithm.h"
#include <tulip/BooleanProperty.h>
#include <tulip/DoubleProperty.h>
#include <tulip/MutableContainer.h>
#include <tulip/ForEach.h>
#include <tulip/Graph.h>
#include "Dikjstra/Dikjstra.h"
#include "DFS/DFS.h"
#define SMALLEST_WEIGHT 1.E-6
using namespace tlp;
using namespace std;
double computePathLength(BooleanProperty *result, MutableContainer<double> &weights) {
double retVal(0);
Graph *graph(result->getGraph());
edge e;
forEach(e, graph->getEdges()) {
if (result->getEdgeValue(e))
retVal += weights.get(e.id);
}
return retVal;
}
bool PathAlgorithm::computePath(Graph *graph, PathType pathType, EdgeOrientation edgesOrientation, node src, node tgt, BooleanProperty *result, DoubleProperty *weights, double tolerance) {
#ifndef NDEBUG
assert(graph);
assert(result);
if (weights)
assert(result->getGraph() == weights->getGraph());
assert(graph->isElement(src));
assert(graph->isElement(tgt));
assert(src != tgt);
#endif /* NDEBUG */
// We always compute Dikjstra as it is used in the all path computation too
MutableContainer<double> weightsContainer;
if (!weights) {
edge e;
forEach(e, graph->getEdges())
weightsContainer.set(e.id, SMALLEST_WEIGHT);
}
else {
edge e;
forEach(e, graph->getEdges()) {
double val(weights->getEdgeValue(e));
if (val == 0)
weightsContainer.set(e.id, SMALLEST_WEIGHT);
else
weightsContainer.set(e.id, val);
}
}
set<node> focus;
vector<node> vNodes;
DoubleProperty *depth = new DoubleProperty(graph);
Dikjstra dikjstra;
dikjstra.initDikjstra(graph, 0, src, edgesOrientation, weightsContainer, 0, focus);
bool retVal = false;
switch (pathType) {
case AllShortest:
retVal = dikjstra.searchPaths(tgt, result, depth);
break;
case OneShortest:
retVal = dikjstra.searchPath(tgt, result, vNodes, depth);
break;
case AllPaths:
retVal = dikjstra.searchPath(tgt, result, vNodes, depth);
if (retVal) {
double pathLength;
if (tolerance == DBL_MAX)
pathLength=DBL_MAX;
else {
pathLength = computePathLength(result, weightsContainer);
pathLength *= tolerance;
}
if (tolerance > 1) { // We only compute the other paths if the tolerance is greater than 1. Meaning that the user doesn't want only the shortest path.
result->setAllNodeValue(false);
result->setAllEdgeValue(false);
DoubleProperty *dists = new DoubleProperty(result->getGraph());
DFS d(graph, result, dists, tgt, weightsContainer, edgesOrientation, pathLength);
retVal = d.searchPaths(src);
delete dists;
}
}
break;
}
delete depth;
return retVal;
}
|
