September 1, 2014
Hot Topics:
RSS RSS feed Download our iPhone app

Discover the Network Search Capabilities of the Boost Graph Library

  • January 11, 2006
  • By Victor Volkman
  • Send Email »
  • More Articles »

The following code is the demo application for Six Degrees of Kevin Bacon:

 1 //=====================================================
 2 // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
 3 //
 4 // Distributed under the Boost Software License, Version 1.0.
 5 (See // accompanying file LICENSE_1_0.txt or copy at
 6 // http://www.boost.org/LICENSE_1_0.txt)
 7 //=======================================================
 8 #include <boost/config.hpp>
 9 #include <iostream>
10 #include <fstream>
11 #include <string>
12 #include <boost/tuple/tuple.hpp>
13 #include <boost/graph/adjacency_list.hpp>
14 #include <boost/graph/visitors.hpp>
15 #include <boost/graph/breadth_first_search.hpp>
16 #include <map>
17 #include <boost/graph/adj_list_serialize.hpp>
18 #include <boost/archive/text_iarchive.hpp>
19
20 struct vertex_properties {
21    std::string name;
22
23    template<class Archive>
24    void serialize(Archive & ar, const unsigned int version) {
25       ar & name;
26    }
27 };
28
29 struct edge_properties {
30    std::string name;
31
32    template<class Archive>
33    void serialize(Archive & ar, const unsigned int version) {
34       ar & name;
35    }
36 };
37
38 using namespace boost;
39
40 typedef adjacency_list<vecS, vecS, undirectedS,
41                        vertex_properties,
                          edge_properties> Graph;
42 typedef graph_traits<Graph>::vertex_descriptor Vertex;
43 typedef graph_traits<Graph>::edge_descriptor Edge;
44
45 class bacon_number_recorder : public default_bfs_visitor
46 {
47 public:
48    bacon_number_recorder(int* dist) : d(dist) { }
49
50    void tree_edge(Edge e, const Graph& g) const {
51       Vertex u = source(e, g), v = target(e, g);
52       d[v] = d[u] + 1;
53   }
54 private:
55    int* d;
56 };
57
58 int main()
59 {
60    std::ifstream ifs("./kevin-bacon2.dat");
61    if (!ifs) {
62       std::cerr << "No ./kevin-bacon2.dat file" << std::endl;
63       return EXIT_FAILURE;
64    }
65    archive::text_iarchive ia(ifs);
66    Graph g;
67    ia >> g;
68
69    std::vector<int> bacon_number(num_vertices(g));
70
71    // Get the vertex for Kevin Bacon
72    Vertex src;
73    graph_traits<Graph>::vertex_iterator i, end;
74    for (tie(i, end) = vertices(g); i != end; ++i)
75       if (g[*i].name == "Kevin Bacon")
76          src = *i;
77
78    // Set Kevin's number to zero
79    bacon_number[src] = 0;
80
81    // Perform a breadth first search to compute everyone's
      // Bacon number.
82    breadth_first_search(g, src,
83       visitor(bacon_number_recorder(&bacon_number[0])));
84
85    for (tie(i, end) = vertices(g); i != end; ++i)
86       std::cout << g[*i].name << " has a Bacon number of "
87          << bacon_number[*i] << std::endl;
88
89    return 0;
90 }

In the graph, each actor is assigned a vertex (or node). From this node, the code generates one edge for each movie that the actor was in. For example, if Kevin Bacon starred with Jim Cummins in Balto, the edge connecting Kevin Bacon and Jim Cummins is labeled Balto.

First, the code reads in a data file containing a series of records formatted with an actor's name, a movie they were in together, and another actors's name (see lines 60-68 of kevin-bacon.cpp). Specifically, this data is stored in an edge-adjacency list called simply Graph (declared in line 66, templated in line 40):

typedef
adjacency_list<vecS, vecS, undirectedS,
               vertex_properties, edge_properties> Graph;

One of the coolest things you get from BGL is the vertex iterators. Lines 71-76 show how to traverse all the vertices from graph "g" that you just read in above. Note the tie() function, which is a tuple helper that allows a std::pair to be broken into two scalers:

71    // Get the vertex for Kevin Bacon
72    Vertex src;
73    graph_traits<Graph>::vertex_iterator i, end;
74    for (tie(i, end) = vertices(g); i != end; ++i)
75       if (g[*i].name == "Kevin Bacon")
76          src = *i;

The solution then can set the bacon_number of Kevin Bacon to zero, which is required to compute distances later, in line 79. Vertices all have a unique number, so a vector sized up to the count of all vertices is appropriate to store that value. Finally, the solution is ready to run the breadth_first_search() algorithm. As the code visits each vertex, it invokes the bacon_number_recorder() from lines 45-56. Basically, inside this visitor function, the solution says that the shortest distance (or bacon number) between adjacent nodes u and v is the shortest distance to v plus one (in other words, the edge you are on):

81    // Perform a breadth first search to compute everyone's
      // Bacon number.
82    breadth_first_search(g, src,
83       visitor(bacon_number_recorder(&bacon_number[0])));
84
85    for (tie(i, end) = vertices(g); i != end; ++i)
86       std::cout << g[*i].name << " has a Bacon number of "
87          << bacon_number[*i] << std::endl;

Last, the solution dumps the output of the entire tree. This time, it traverses the list of vertices again. Thus, it gives you the following output:

Tom Hanks has a Bacon number of 1
Zoya Barantsevich has a Bacon number of 5
Nikolai Panov has a Bacon number of 4
Zoia Karabanova has a Bacon number of 3
William Challee has a Bacon number of 2
P. Biryukov has a Bacon number of 5

Solutions like this one are not just for fun and games; services such as Linked In, Plaxo, and Friendster are generating a new landscape called Social Computing.

Solve Graph Searching Problems

Hopefully, I have demonstrated a relatively quick and painless way of solving some of the classic graph searching problems in computer science. I only scratched the surface of what Boost can handle. Once you've committed your data structures to a graph representation, the possibilities of sorting, searching, and connecting networks are limitless.

For Additional Reading

Certainly anyone who wants to use the Boost Graph Library ought to immediately get his or her hands on The Boost Graph Library: User Guide and Reference Manual by Siek, Lee, and Lumsdaine (2002). As you might expect from the title, the book neatly divides into two nearly equal parts: the first half covers the User Guide, and the second half covers the Reference Manual.

The User Guide starts off with a review of basic concepts of both graphs and Generic Programming. It then delves into classic graph problems such as shortest-path, minimum spanning-tree, maximum flow, knight's tour, and others. A particularly nice touch is a chapter explaining how to integrate Boost code with LEDA and Stanford GraphBase (SGB).

About the Author

Victor Volkman has been writing for C/C++ Users Journal and other programming journals since the late 1980s. He is a graduate of Michigan Tech and a faculty advisor board member for the Washtenaw Community College CIS department. Volkman is the editor of numerous books, including C/C++ Treasure Chest and is the owner of Loving Healing Press. He can help you in your quest for open source tools and libraries, just drop an e-mail to sysop@HAL9K.com.





Page 2 of 2



Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Sitemap | Contact Us

Rocket Fuel