I am playing with boost A* algorithm, started with the example found at: http://www.boost.org/doc/libs/1_37_0/libs/graph/example/astar-cities.cpp
I see that you can override its heuristics and its visitor to have some sort of custom tweaks, just that I don't quite get the concept yet for such a thing like the following, as a learning example, I'd like the algorithm to NOT pick a edge city - city, if travel time (edge weight) is greater than X, for example 100 minutes. (only if possible, if no other path is found, then that city should be chosed instead of not path found)
I tried a custom heuristic class which returns a greater time than reality, to "trick" it not to chose that city, however the problem is that with this trick, the penaltied city gets discarded, even for further interactions. (The following example explains it: B->D is discarded as a better path is found, but city D is not discarded (you see it's picked in a following iteration)
So I simplified the problem furter:
enum nodes {
A, B, C, D, E, N
};
const char *name[] = {
"A", "B", "C", "D", "E", "F"
};
edge edge_array[] = {
edge(A,B), edge(B,C),
edge(C,D), edge(D,E),
edge(B,D) // B to D is the problem here, it should be excluded
};
cost weights[] = { // estimated travel time (mins)
// 107, 174, 283, 71, 436
35, 58, 94, 23, 145
};
With this example (taking the code from original as base), I get a route:
Start vertex: A
Goal vertex: E
Shortest path from A to E: A -> B -> D -> E
Total travel time: 204.5
The problem is the B -> D path, which is such a long distance (supposing a threshold of 100, for example, that would be preferable a path like: A -> B -> C -> D -> E, this way, the distance between 2 cities is not superior to 100 (of course only if possible, if no other path, any have to be chosen)
I solved it in a suboptimal way: A custom function once adding the edge, that, (or setting manually weight) return travelTime > 100 ? travelTime * 2 : travelTime, which can be achieved for testing with:
cost weights[] = { // estimated travel time (mins)
// 107, 174, 283, 71, 436
(35 > 100) ? 35*2 : 35, (58 > 100) ? 58*2 : 58, (94>100) ? 94*2 : 94, 23, (145 > 100) ? 145*2 : 145
}; // The comparisons are not needed, just there to better explain what the custom add_edge function will do.
With this method, I get the desired A -> B -> C -> D -> E, but this way, is just a hack/workaround the problem and modifies input data internally, which I think it is not the best solution.
Is there any better way to achieve this without having to manually change distances/travel time?
I think you just wanted shortest paths here (dijkstra would be alright).
The key is to realize that you can use a custom edge_weight property map. This could be e.g. boost::property_map::transform_value_property_map<> like so:
auto my_custom_weight_map =
boost::make_transform_value_property_map(
[](float w) { return w>100? 10*w : w; },
boost::get(boost::edge_weight, g));
You see that any edge weight above 100 will be increased tenfold.
Then, you're basically already done:
astar_search_tree(g, start,
distance_heuristic<mygraph_t, cost>(goal),
boost::weight_map(my_custom_weight_map) // THIS LINE ADDED
.predecessor_map(make_iterator_property_map(p.begin(), get(boost::vertex_index, g)))
.distance_map(make_iterator_property_map(d.begin(), get(boost::vertex_index, g)))
.visitor(astar_goal_visitor<vertex>(goal))
);
And the result is:
Start vertex: A
Goal vertex: E
Shortest path from A to E: A -> B -> C -> D -> E
Total travel time: 210
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/astar_search.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <iostream>
#include <list>
// auxiliary types
struct location {
float y, x; // lat, long
};
typedef float cost;
// euclidean distance heuristic
template <class Graph, class CostType>
class distance_heuristic : public boost::astar_heuristic<Graph, CostType> {
public:
typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
distance_heuristic(Vertex goal) : m_goal(goal) {}
CostType operator()(Vertex /*u*/) {
return 0; // Not really needed here
}
private:
Vertex m_goal;
};
struct found_goal {}; // exception for termination
// visitor that terminates when we find the goal
template <class Vertex> class astar_goal_visitor : public boost::default_astar_visitor {
public:
astar_goal_visitor(Vertex goal) : m_goal(goal) {}
template <class Graph> void examine_vertex(Vertex u, Graph &/*g*/) {
if (u == m_goal)
throw found_goal();
}
private:
Vertex m_goal;
};
int main() {
// specify some types
typedef boost::adjacency_list<boost::listS, boost::vecS,
boost::undirectedS, boost::no_property,
boost::property<boost::edge_weight_t, cost>
> mygraph_t;
typedef boost::property_map<mygraph_t, boost::edge_weight_t>::type WeightMap;
typedef mygraph_t::vertex_descriptor vertex;
typedef mygraph_t::edge_descriptor edge_descriptor;
typedef std::pair<int, int> edge;
enum nodes { A, B, C, D, E, N };
const char *name[] = { "A", "B", "C", "D", "E", "F" };
edge edge_array[] = {
edge(A, B), edge(B, C), edge(C, D), edge(D, E), edge(B, D) // B to D is the problem here, it should be excluded
};
cost weights[] = { // estimated travel time (mins)
// 107, 174, 283, 71, 436
35, 58, 94, 23, 145
};
unsigned int num_edges = sizeof(edge_array) / sizeof(edge);
// create graph
mygraph_t g(N);
WeightMap weightmap = get(boost::edge_weight, g);
for (std::size_t j = 0; j < num_edges; ++j) {
edge_descriptor e;
bool inserted;
boost::tie(e, inserted) = add_edge(edge_array[j].first, edge_array[j].second, g);
weightmap[e] = weights[j];
}
// pick start/goal
vertex start = A;
vertex goal = E;
std::cout << "Start vertex: " << name[start] << std::endl;
std::cout << "Goal vertex: " << name[goal] << std::endl;
std::vector<mygraph_t::vertex_descriptor> p(num_vertices(g));
using boost::get;
// do a real edit
std::vector<cost> d(num_vertices(g));
auto my_custom_weight_map =
boost::make_transform_value_property_map(
[](float w) { return w>100? 10*w : w; },
boost::get(boost::edge_weight, g));
try {
// call astar named parameter interface
astar_search_tree(g, start,
distance_heuristic<mygraph_t, cost>(goal),
boost::weight_map(my_custom_weight_map)
.predecessor_map(make_iterator_property_map(p.begin(), get(boost::vertex_index, g)))
.distance_map(make_iterator_property_map(d.begin(), get(boost::vertex_index, g)))
.visitor(astar_goal_visitor<vertex>(goal))
);
} catch (found_goal fg) { // found a path to the goal
std::list<vertex> shortest_path;
for (vertex v = goal;; v = p[v]) {
shortest_path.push_front(v);
if (p[v] == v)
break;
}
std::cout << "Shortest path from " << name[start] << " to " << name[goal] << ": ";
std::list<vertex>::iterator spi = shortest_path.begin();
std::cout << name[start];
for (++spi; spi != shortest_path.end(); ++spi)
std::cout << " -> " << name[*spi];
std::cout << std::endl << "Total travel time: " << d[goal] << std::endl;
return 0;
}
std::cout << "Didn't find a path from " << name[start] << "to" << name[goal] << "!" << std::endl;
return 0;
}