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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
#ifndef CONSTRAINEDSEARCH_H
#define CONSTRAINEDSEARCH_H 1
#include "Common/ContigPath.h"
#include "Common/ContigProperties.h"
#include "Graph/ContigGraph.h"
#include "Graph/DirectedGraph.h"
#include "Graph/Properties.h"
#include <algorithm>
#include <climits> // for INT_MIN
#include <cassert>
#include <istream>
#include <utility>
#include <vector>
namespace opt {
unsigned maxCost = 100000;
/** Abort the search after visiting maxPaths solutions. */
const unsigned maxPaths = 200;
}
typedef std::pair<ContigNode, int> Constraint;
typedef std::vector<Constraint> Constraints;
typedef std::vector<ContigPath> ContigPaths;
/** Compare the distance of two constraints. */
static inline bool compareDistance(
const Constraint& a, const Constraint& b)
{
return a.second < b.second;
}
/** Compare the ID of a constraint. */
static inline bool compareID(const Constraint& constraint,
const ContigNode& key)
{
return constraint.first < key;
}
/** Find a constraint by ID. */
static inline Constraints::iterator findConstraint(
Constraints& constraints,
const ContigNode& key)
{
Constraints::iterator it = lower_bound(
constraints.begin(), constraints.end(),
key, compareID);
return it != constraints.end()
&& it->first == key ? it : constraints.end();
}
/** Find paths through the graph that satisfy the constraints.
* @return false if the search exited early
*/
template <typename Graph, typename vertex_descriptor>
bool constrainedSearch(const Graph& g,
vertex_descriptor u,
Constraints& constraints,
Constraints::const_iterator nextConstraint,
unsigned satisfied,
ContigPath& path, ContigPaths& solutions,
int distance, unsigned& visitedCount)
{
typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iterator;
assert(satisfied < constraints.size());
static const int SATISFIED = INT_MAX;
if (!path.empty()) {
vertex_descriptor v = path.back();
Constraints::iterator it = findConstraint(constraints, v);
if (it != constraints.end() && it->second != SATISFIED) {
if (distance > it->second)
return true; // This constraint cannot be met.
if (++satisfied == constraints.size()) {
// All the constraints have been satisfied.
solutions.push_back(path);
return solutions.size() <= opt::maxPaths;
}
// This constraint has been satisfied.
int constraint = it->second;
it->second = SATISFIED;
if (!constrainedSearch(g, u, constraints,
nextConstraint, satisfied, path, solutions,
distance, visitedCount))
return false;
it->second = constraint;
return true;
}
if (++visitedCount >= opt::maxCost)
return false; // Too complex.
// Check that the next constraint has not been violated.
while (distance > nextConstraint->second
&& findConstraint(constraints,
nextConstraint->first)->second == SATISFIED)
++nextConstraint; // This constraint is satisfied.
if (distance > nextConstraint->second)
return true; // This constraint cannot be met.
distance += g[v].length;
u = v;
}
path.push_back(vertex_descriptor());
std::pair<out_edge_iterator, out_edge_iterator> adj = g.out_edges(u);
for (out_edge_iterator it = adj.first; it != adj.second; ++it) {
path.back() = target(*it, g);
if (!constrainedSearch(g, u, constraints,
nextConstraint, satisfied, path, solutions,
distance + g[*it].distance, visitedCount))
return false;
}
assert(!path.empty());
path.pop_back();
return true;
}
/** Find paths through the graph that satisfy the constraints.
* @return false if the search exited early
*/
template <typename Graph, typename vertex_descriptor>
bool constrainedSearch(const Graph& g,
vertex_descriptor v,
Constraints& constraints, ContigPaths& paths,
unsigned& cost)
{
if (constraints.empty())
return false;
// Sort the constraints by ID.
sort(constraints.begin(), constraints.end());
// Sort the constraints by distance.
Constraints queue(constraints);
sort(queue.begin(), queue.end(), compareDistance);
ContigPath path;
constrainedSearch(g, v, constraints, queue.begin(), 0,
path, paths, 0, cost);
return cost >= opt::maxCost ? false : !paths.empty();
}
#endif
|
