Alternative Boost Graph Construction based on defining edges independently

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.

So we start with the normal code:

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.

The benefit of this is you define the construct of the graph and create the graph_t, object g.

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.

Tuesday, December 25, 2012 10:40:00 PM Categories: API C++ HowTo Programming
Stuart James