[BGL] Possible bug in minimum_degree_ordering

From: Jeppe N. Madsen (yg-boost-users_at_[hidden])
Date: 2002-12-22 08:23:27

Hi,

I'm fairly new to BGL so this may not be a bug after all......but I
get a fair number of warnings about possible loss of data due to
conversions (mainly between signed/unsigned types) with MSVC7 trying
to compile the example below. Some may be ignored but at least line
188 of minimum_degree_ordering.hpp seems wrong:

       data[id[i]] = - (id[j] + offset);

id[j] is unsigned, making (id[j] + offset) unsigned thus making the unary
minus rather spurious.

Also, compile time checks for correctly using signed types for the
permutations would be nice :-)

rgds
Jeppe

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include "boost/graph/minimum_degree_ordering.hpp"
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include "boost/graph/minimum_degree_ordering.hpp"
using namespace std;
using namespace boost;
int main(int, char **)
  {
  typedef adjacency_list <vecS, vecS, directedS> Graph;
  Graph G;

  add_edge(0, 1, G); add_edge(1, 0, G);
  add_edge(0, 2, G); add_edge(2, 0, G);
  add_edge(0, 5, G); add_edge(5, 0, G);
  add_edge(1, 2, G); add_edge(2, 1, G);
  add_edge(1, 3, G); add_edge(3, 1, G);
  add_edge(1, 6, G); add_edge(6, 1, G);
  add_edge(2, 4, G); add_edge(4, 2, G);
  add_edge(3, 4, G); add_edge(4, 3, G);
  add_edge(4, 5, G); add_edge(5, 4, G);

  std::vector<size_t> degree(num_vertices(G), 0);
  std::vector<int> inverse_perm(num_vertices(G), 0), perm(num_vertices(G), 0);
  std::vector<size_t> supernode_sizes(num_vertices(G), 1);
  property_map<Graph, vertex_index_t>::type id = get(vertex_index, G);

  minimum_degree_ordering
    (G,
     make_iterator_property_map(&degree[0], id, degree[0]),
     &inverse_perm[0],
     &perm[0],
     make_iterator_property_map(&supernode_sizes[0], id, supernode_sizes[0]), 
     0, id);

  for(size_t i = 0; i < num_vertices(G); ++i)
    std::cout << inverse_perm[i] << "\n";
  return 0;
}