{ Stuart James }

18 Aug 2012 . .
Boost Dijkstra Shortest Path Example utilising backtracking from target Comments

Often API documentation can be difficult to follow and your memory might fail for algorithms you learnt in school, so a simple example often explains how to use a function. Well unless you are very familiar with the way Boost Graph library works then you may find the Dijkstra shortest path documentation confusing.

So this is what you get from boost…

 1 typedef adjacency_list < listS, vecS, directedS,
 2   no_property, property < edge_weight_t, int > > graph_t;
 3 typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
 4 typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
 5 typedef std::pair<int, int> Edge;
 6 
 7 const int num_nodes = 5;
 8 enum nodes { A, B, C, D, E };
 9 char name[] = "ABCDE";
10 Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
11   Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B)
12 };
13 int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
14 int num_arcs = sizeof(edge_array) / sizeof(Edge);
15 
16 graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
17 property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
18 
19 std::vector<vertex_descriptor> p(num_vertices(g));
20 std::vector<int> d(num_vertices(g));
21 vertex_descriptor s = vertex(A, g);
22 
23 dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d[0]));

Taken from http://www.boost.org/doc/libs/1_49_0/libs/graph/example/dijkstra-example.cpp

From this example you are able to get the predecessor map and the distances travelled from a root node to all other nodes. But this doesn’t answer the question of how you get the shortest path from point A to point B. The way to do this is called backtracking and is very easy but not necessarily obvious when you don't know the data structures.

1 // Backtrack from end node, storing distances
2 int target = vertex(B, g);
3 std::vector<int> nodes;
4 std::vector<float> distance;
5 do{
6     nodes.push_back(target);
7     distances.push_back(d[target]);
8     target = p[target];
9 }while(target != s);

The vector nodes then contains a list of nodes passed through, that can be reversed easily using std lib functions to find the route from A to B.

Stuart James …

16 Aug 2012 . .
Game Night: Carcassonne, this is not a good map! Comments

Played my first game of Carcassonne tonight, was interesting didn’t really construct into anything nice though that I am disappointed by! Would of been nice to have a good map of castles and paths. May have more luck next time.

Stuart James …

13 Aug 2012 . .
Pixel Tracking! (Dog Tracking) Comments

Ever wonder what your dog gets up to at home? Well I do a lot, this weekend I decided to setup a temporary solution to see what my dog does. Here are some day 1 results, only the masks to protect my dogs(Pixel) and my privacy!

Pixel Relaxing on sofa

Pixel leaping off the sofa

Exploring?

This was achieved writing no code (sad I know) but was more of an exploration to see what Linux tools are around for doing this type of thing. i used the motion project(http://www.lavrsen.dk/foswiki/bin/view/Motion/WebHome) with some parameter playing, pretty simple out of the box. What I found was the tools are ok, not very out of the box and didn’t really work that great. So this is spawning a project for me.

With the computer vision knowledge I have I think I should be able to mock up a good tracker with all sorts of bells and whistles, to allow me track my dog moving around during the day learn where he likes to sleep dig into what motions he performs possibly even guess when the mail man comes each day and if there are cats around to annoy him.

The one useful piece of information I have learnt from looking back through the days activity, is that my dog really is as lazy as originally expected. Spends most of his day asleep on sofa explaining why he has so much energy when I get home. Most motion over the day was him moving into a new position!

Stuart James …

13 Aug 2012 . .
Cycling to work the killer first day! Comments

It has been a long time since I tried to cycle to the office, well so long when I was sorting out my bike on the weekend rust leaked out. But none the less checked inner tubes for punctures(none) pumped up the tires cycled round the block and I was ready for today(brave). I realise that it was probably a better idea to go get a bike check up, but didn’t fancy that. Well the day went quite well, got in without issue, only small catch was trying to miss the rain on way home, I failed. I would strongly recommend people take up cycling to work especially if you live in area with terrible bus service like that in Guildford!

Stuart James …