Alternative Boost Graph Construction based on defining edges independently

25 Dec 2012 . category: . Comments

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.

Stuart James …

Assistant Professor in Visual Computing at Durham University. Stuart's research focus is on Visual Reasoning to understand the layout of visual content from Iconography (e.g. Sketches) to 3D Scene understanding and their implications on methods of interaction. He is currently a co-I on the RePAIR EU FET, DCitizens EU Twinning, and BoSS EU Lighthouse. He was a co-I on the MEMEX RIA EU H2020 project coordinated at IIT for increasing social inclusion with Cultural Heritage. Stuart has previously held a Researcher & PostDoc positions at IIT as well as PostDocs at University College London (UCL), and the University of Surrey. Also, at the University of Surrey, Stuart was awarded his PhD on visual information retrieval for sketches. Stuart holds an External Scientist at IIT, Honorary roles UCL and UCL Digital Humanities, and an international collaborator of ITI/LARSyS. He also regularly organises Vision for Art (VISART) workshop and Humanities-orientated tutorials and was Program Chair at British Machine Conference (BMVC) 2021.