[Boost-users] Bug in Boost Graph Library?

From: Heiko Bauke (Heiko.Bauke_at_[hidden])
Date: 2004-03-17 03:54:53

Dear all,

today I was engaged in searching for a bug in my program. After a 
while I figured out that boost::num_egdes behaves not as I expected. 
If G is an undirected adjacency matrix graph boost::num_egdes(G) 
returns the number of edges in the graph G plus the number of edges 
in G that are no self edges. That means almost all edges are counted 
twice in undirected adjacency matrix graphs.

In my oppinion this behaviour is a bug. At least it makes the 
BGL-user's live unnecessary difficult. Let's considder the following 
program:

#include <cstdlib>
#include <iostream>
#include <boost/tuple/tuple.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>

template <typename Graph>
void add_edges(const char * const c) {
  std::cout << c;
  Graph G(6);
  boost::graph_traits<Graph>::vertex_iterator v, vbegin, vend;
  boost::tie(vbegin, vend)=boost::vertices(G);
  for (v=vbegin; v!=vend; ++v) {
    boost::add_edge(*vbegin, *v, G);
    std::cout << ' ' << boost::num_edges(G);
  }
  std::cout << std::endl;
}

int main() {
  typedef boost::adjacency_list<boost::vecS, boost::vecS,
    boost::undirectedS> adjacency_list;
  typedef boost::adjacency_matrix<boost::undirectedS>
    adjacency_matrix;
  add_edges<adjacency_list>("adjacency list graph   :");
  add_edges<adjacency_matrix>("adjacency matrix graph :");
  return EXIT_SUCCESS;
}

It prints to stdout:

adjacency list graph   : 1 2 3 4 5 6
adjacency matrix graph : 1 3 5 7 9 11

So the result of the template function add_edges in the program above
depends of the graph container that the function add_edges is applied 
to. I think this is verry unintuitive and boost::num_edges should be 
changed, so that alls edges in undirected adjacency matrix graphs are
counted only once.

Or is there a special reason that boost::num_edges is implemented in
this way?

         with regards,

         Heiko

-- 
-- Gute Sitten haben für die Gesellschaft mehr Wert als alle 
-- Berechnungen Newtons. (Friedrich II., der Große, 1712-1786)
-- Supercomputing in Magdeburg @ http://tina.nat.uni-magdeburg.de
--                 Heiko Bauke @ http://www.uni-magdeburg.de/bauke