With this post I’m starting a series about the Boost Graph Library (BGL). My objective is to present the material in small, easy-to-digest chunks, in order to build an understanding of this library and of the C++ concepts that it uses.

The code is a only a slight variation of the code presented in the quick tutorial section about the BGL. For a copy of the example revised as it appears in this post, see this gist.

### Representing the graph

First off, we know that a graph is representable in a couple of ways. One of these is the adjacency list, a data structure where we have a correspondence between each node and all its neighbors, i.e., the nodes that are 1 edge away. So for a graph like:

the adjacency list would look like:

1: 2, 4 2: 5 3: 5, 6 4: 2 5: 4 6: 6

(this graph can be found on CLRS).

To represent this list, we declare that our Graph *is* its adjacency list:

1 | typedef |

This means: use `std::vector`

for out-edges (the edges that are directed from the node outward) and for the vertex set. Other choices might have been, among the others, `listS`

and `setS`

. What we actually choose depends on the application, because some data structures optimize for space, other for times (see this brief yet complete and very useful discussion).

1 | enum { _1, _2, _3, _4, _5, _6, N }; |

Nothing special here: we decide to give identifiers to the nodes for our convenience. With this setup, we use those `enum`

values to actually create the array of the edges:

1 | typedef std::pair<int, int> Edge; |

Finally we define the graph (note that we only use the `edge_array`

, and we use it as an iterator):

1 | Graph g(edge_array, |

### Properties of a Graph object

A great feature of the BGL is the availability of fully customizable *properties*, that can be assigned to vertices and edges, according to the application we are modeling. They can be weights, for example, if we are going to use Dijkstra’s algorithm for the shortest path. A property is accessed through a `property_map`

object. Among the properties already defined, we can find the index of the vertices, that we access with a call to the `get()`

function:

1 | typedef |

Now let’s just print the vertices, using our index property:

1 | std::cout << "vertices(g) = "; |

We use `graph_traits`

to get the right iterator. The Iterator concept is crucial to the BGL library, and is an evolution of the same concept in STL, in that the graph iterator differs according to how we want to traverse the graph: by vertices, by adjacency, by visitor.

The iterator we get here is a `vertex_iterator`

, which, not surprisingly, allows us to traverse the list of vertices. The function

1 | std::pair<vertex_iterator, vertex_iterator> vertices(g) |

which is part of the `VertexListGraph`

interface, returns a range as a pair of iterators to first element and one past the last. Given the property_map object, we index it by unreferencing the iterator, getting the output:

vertices(g) = 0 1 2 3 4 5

### What’s next

We have seen how to create a graph, and how to get access to its vertex indices.

In the next installment, we are going to see how to apply some famous graph algorithm with this nice library.