- 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

## 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.