Boost logo

Boost Users :

Subject: [Boost-users] [graph] Newbie question: iterator shows vertices not added, always lo .. hi
From: Chris Lott (mail08_at_[hidden])
Date: 2008-10-21 09:09:04


I am new to the Boost graph library and trying to learn from examples in
the documentation. I would like to ask about the simple vertex
iterator's behavior. Below is sample code. In a nutshell, the program
adds some edges to a Boost graph, then prints the vertices. The vertex
numbers added are not contiguous: the loop basically adds edges between
vertices 0, 1, 2, 6, and 7; no edges are added for vertices 3, 4, 5.
Then I use a vertex iterator to show tine in- and out-degree of each

My expectation was that the iterator would only show me the vertices for
which I added edges, but instead it shows vertices from 0..7,
essentially from the low value to the high value. This seems to be a
feature, but I don't know where to look to find an explanation. Perhaps
this behavior is dictated by my choices of data structures vecS?

So far I have been relying on the online documentation, which I find to
be quite difficult to use. For example, the web site doesn't seem to
have a comprehensive index to Boost generic types and functions, just
that alone would be an enormous help.

Is the Boost book is (substantially?) better than using the online docs,
or is it just the same content on paper?

Please advise, thanks for your help.




#include <iostream> // for std::cout
#include <utility> // for std::pair
#include <algorithm> // for std::for_each
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>

int /* GraphExample_ */ main(int,char*[])
     // create a typedef for the Graph type
     typedef boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS> Graph;

     // Make convenient labels for the vertices
     enum { A, B, C, X, Y, Z, D, E, N };
     const int num_vertices = N;

     typedef std::pair<int, int> Edge;
     Edge edge_array[] =
     { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
             Edge(C,E), Edge(B,D), Edge(D,E) };
     const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);

     // Declare a graph object with the specified number of vertices.
     Graph g(num_vertices);

     // add the edges to the graph object
     // Each vertex is an integer.
     for (int i = 0; i < num_edges; ++i)
         boost::add_edge(edge_array[i].first, edge_array[i].second, g);

     // Iterate through the vertices and print them out.
     // This iterator seems to be simply 0.. (largest vertex number).
     // Some vertices were never added as part of any edge, yet the
     // loop below shows them anyhow.
     typedef boost::graph_traits<Graph>::vertex_iterator vertex_iter;
     std::pair<vertex_iter, vertex_iter> vp;
     for (vp = vertices(g); vp.first != vp.second; ++vp.first) {
         vertex_iter iter = vp.first;
         boost::graph_traits<Graph>::vertex_descriptor v = *iter;
         int in = boost::in_degree(v, g);
         std::cout << "Vertex " << v << " has in degree " << in <<
         int out = boost::out_degree(v, g);
         std::cout << "Vertex " << v << " has out degree " << out <<

     return 0;

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at