- Grasping Graph Theory
- Old and Famous Problems
- Graphs, Computers, and Popular Culture
- Constructing a Simple Graph with Boost
- Adding Values to Vertices and Edges
- Manipulating Property Values
- Adding Vertices and Edges
- Iterating Through the Edges and Vertices
- Solving Problems with Graphs and Boost
- Conclusion
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Solving Problems with Graphs and Boost
Although the Six Degrees of Kevin Bacon game is for fun, the technique used to solve it, called the "Shortest Path" problem, has some practical uses beyond ruminating over movie stars. For example, if you use one of the popular shipping companies to ship a product from Bakersfield, California to Lake Mary, Florida, the shipper needs to find the shortest (that is, the least expensive) path to get the package to the destination. Most likely the package will travel through at least a few cities that the shipper considers hubs. Each city, then, is a vertex on the graph, and cities are connected by edges. The graph is weighted, since the distances between cities vary, as do the time and method to move a package from one city to the next. This is where the problem differs from the Six Degrees problem, since the Six Degrees problem doesn’t have weights to the edges.
Mathematicians and computer scientists have developed various algorithms to solve graph theory problems, including the Shortest Path problem. Entire books have been written on the subject of solving problems with graph theory. Certainly, many of the big problems such as those dealing with product shipping involve large numbers of vertices and edges. (Think of the number of cities in the United States, pretty much all served by the United States Post Office.) Thus, these problems are best suited for computers.
The Boost library includes several well-known graph theory algorithms so you don’t have to code them yourself. It includes several different Shortest Path algorithms, for example. The thing about the fun Kevin Bacon problem is that it’s actually not all that interesting from a graph theory perspective, because all the edge weights are 1; by that I mean that when two actors are connected by having been in a movie together, there isn’t a physical distance associated with the connection.
When the edge weight is 1, as with the Kevin Bacon problem, the algorithm becomes identical to an algorithm called "Breadth First Search" (BFS). BFS is used for iterating over vertices, starting at a beginning vertex called the root. The idea is that you start at the root vertex, and spread out to each vertex touching the root, marking each as visited. Then you continue for each of these vertices, visiting each unvisited vertex until you’ve covered the graph. Or you can stop when you find a particular vertex you want, in which case you’ve found the shortest path to the vertex you wanted.
The documentation for the Boost library includes a good demonstration of the Kevin Bacon game. Rather than write up similar code here, I suggest just checking out the documentation.
Of more interest to a lot of programmers than the Kevin Bacon game is another interesting problem of file dependencies. Programs such as make and ant as well as spreadsheets need this algorithm. For example, if you’re writing spreadsheet software, and the spreadsheet contains cells with formulas referencing other cells, you need to figure out the order in which to evaluate the formulas. If cell A1 has a formula that makes use of cell A2, and A2 has a formula, then you have to evaluate the formula in A2 before you can evaluate the one in A1. That’s a dependency algorithm. The same applies to compilation order in programs such as make and ant. If file 1 depends on file 2, then you have to know to compile file 2 before file 1. The documentation for the Boost Graph library includes a sample that solves the file dependency problem.