Chapter 31. Boost.Graph

Boost.Graph provides tools to work with graphs. Graphs are two-dimensional point clouds with any number of lines between points. A subway map is a good example of a graph. Subway stations are points, which are connected by subway lines.

The graph theory is the field of mathematics that researches graphs. Graph theory tries to answer questions such as how to determine the shortest path between two points. Auto navigation systems have to solve that problem to guide drivers to their desired location using the shortest path. Graphs are very important in practice because many problems can be modelled with them.

Boost.Graph provides containers to define graphs. However, even more important are the algorithms Boost.Graph offers to operate on graphs, for example, to find the shortest path. This chapter introduces you to the containers and algorithms in Boost.Graph.