[Boost-users] [graph] Newbie question: iterator shows vertices not added, always lo .. hi

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

Hi,

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

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.

chris...

--------

[code]

#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 << 
std::endl;
         int out = boost::out_degree(v, g);
         std::cout << "Vertex " << v << " has out degree " << out << 
std::endl;
     }

     return 0;
}
[/code]