Boost Graph Algorithm - Adding Constraint

Question

Problem

I have a set of vertices distributed evenly (grid). The distance between adjacent vertices is 1 (normal grid unit) when moving vertically or horizontally. Basically a normal grid:

Here are the limitations that I still have in my code:

• Visit every peak
• Move only vertically or horizontally (not diagonally)

I just need to add one more restriction. I need to minimize the number of turns. That is, to minimize the number of times when the "seller" will need to change directions (examples below). How can i achieve this?

<strong> Examples

In these two images, although all the peaks are visited, the number of turns required to obtain is different. I want to minimize these turns.

How can i achieve this?

My code

I simplified my code below (it's just a 4x4 grid for simplicity).

#include <boost/config.hpp> #include <iostream> #include <fstream> #include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> using namespace boost; int main(int, char *[]) { typedef adjacency_list < listS, vecS, directedS, no_property, property < edge_weight_t, int > > graph_t; typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor; typedef graph_traits < graph_t >::edge_descriptor edge_descriptor; typedef std::pair<int, int> Edge; // This just creates a 4x4 vertex grid like in the examples above const int num_nodes = 16; enum nodes { A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P }; char name[] = "ABCDEFGHIJKLMNOP"; Edge edge_array[] = { Edge(A, B), Edge(B, C), Edge(C, D), Edge(A, E), Edge(B, F), Edge(C, G), Edge(D, H), Edge(E, F), Edge(F, G), Edge(G, H), Edge(E, I), Edge(F, J), Edge(G, K), Edge(K, L), Edge(I, J), Edge(J, K), Edge(K, L), Edge(I, M), Edge(J, N), Edge(K, O), Edge(L, P), Edge(M, N), Edge(N, O), Edge(O, P), }; int weights[num_nodes]; std::fill_n(weights, num_nodes, 1); // set all edge weights to 1 int num_arcs = sizeof(edge_array) / sizeof(Edge); graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes); property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g); std::vector<vertex_descriptor> p(num_vertices(g)); std::vector<int> d(num_vertices(g)); vertex_descriptor s = vertex(A, g); dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d[0])); return EXIT_SUCCESS; } 

Answer 1

You need to add a penalty to the estimated cost when you change direction (which you need to calculate on the fly). You can perform dynamic cost calculations in bgl using:

 boost::function_property_map<MyDynamicWeightFunctor, edge_t, float> weight_map(weight_functor); dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d[0]).weight_map(weight_map)); struct MyDynamicWeightFunctor : public std::unary_function<edge_t, float> { MyDynamicWeightFunctor(const GRAPH_TYPE &g) : mGraph(g) { } float operator()(edge_t e) const { // You will need to do something more complicated here // You will need to look up where you came from. You can accomplish this // by passing some structure in the constructor of this functor that keeps // track of you previous location(s) return mGraph[e].weight * 2; } const GRAPH_TYPE &mGraph; }; 

It has been a while since I used this to see how to use the property maps http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/using_property_maps.html and in particular the function property maps http://www.boost.org/doc/libs/1_54_0/libs/property_map/doc/function_property_map.html