C++ Reference Material
The Boost Graph Library

The Boost Graph Library takes a little getting used to, to say the least. We discuss here, briefly, some of the concepts with which you must become familiar in order to make sense of the various code samples that are available. [See references below.] The best way to proceed, before trying to write any code of your own, is to study the source and output of any examples you can find, while reading and re-reading the descriptions of the various structures and algorithms involved. Prior experience with the C++ Standard Template Library (STL) will be very helpful when it comes to working with the Boost Graph Library.

Some assumptions about your knowledge of terminology

If you are reading this page, you should already be familiar with much of the usual graph terminology, including vertex (or node), edge (or arc), weighted and unweighted graphs, paths and cycles in graphs, neighbors (adjacent vertices), directed and undirected graphs, connected and unconnected (or disconnected or disjoint) graphs, strong and weak connectivity in directed graphs, sparse and dense graphs, as well as the degree, in-degree and/or out-degree of a vertex. Other key concepts include graph traversals, (minimal) spanning trees, and shortest paths, as well as the adjacency list and adjacency matrix methods of representing graphs. Also, the DAG (directed, acyclic (or non-cyclic) graph) is one special kind of graph of particular interest, and the notion of the transitive closure of a directed graph is a concept of interest as well.

Modeling problems with graphs

The kinds of problem structures that can be modeled with a graph are very diverse. Here are a few examples:

1. With cities as vertices, highways connecting them as edges, and edge weights being the distances between cities, how can we find the shortest route (path) between two particular cities, or between all pairs of cities?
2. With cities as vertices, highways connecting them as edges, and edge weights being the cost of building a highway between two cities, which highways should we actually build so that all cities are connected and the total cost of construction is minimized?

Some typical (small) examples

Boost graph types (graph classes) and graph setup

adjacency_list<>
adjacency_list<vecS, >
adjacency_matrix<>

Vertex descriptors and edge descriptors

Adding vertices and edges to a graph

Property maps for vertices and edges

Vertex iterators and edge iterators

Graph traversal algorithms

Other graph algorithms, and visitors

Solving problems using graph algorithms

References