So you may of seen previous posts on Boost Graph construction, here I present an easier way of constructing the graph but at a performance cost. This shouldn’t be used if can be avoided, but it may be useful if you want to adapt your edges on the fly.

1 typedef adjacency_list < listS, vecS, directedS,
2 no_property, property < edge_weight_t, float > > 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 float weights[] = { 1.5, 2.10, 1.4, 2.2, 7.6, 3.222, 1.125, 1.324, 1.983 };
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<float> d(num_vertices(g));
21 vertex_descriptor s = vertex(A, g);
22
23
24 dijkstra_shortest_paths_no_color_map(g, s, predecessor_map(&p[0]).distance_map(&d[0]));
25
26 std::vector<float> distances;
27 std::vector<float> node_index_ids;
28
29 int target = vertex(D, g);
30 do{
31 node_index_ids.push_back(target);
32 distances.push_back(d[target]);
33 std::cout << "Target " << target << " dist " << d[target] << " Source " << s << std::endl;
34 target = p[target];
35 }while(target != s);

So we start with a basic set of nodes, A->E with some connections between them. This is an example of a directed graph so “flow” can only go one direction.

An alternative way of constructing is to generate the nodes, then add in the weights as in:

1 graph_t g(num_nodes);
2 for (int i = 0 ; i < num_arcs ; ++i){
3 boost::add_edge(edge_array[i].first,edge_array[i].second,weights[i],g);
4 }

This may seem easier but comes at a performance cost. In contrast even on this simple example there is a 0.001s time increase, scale this to a real solution you may suffer badly. As stated make sure your scenario makes sense.