[boost] random graphs

From: Heiko Bauke (heiko.bauke_at_[hidden])
Date: 2006-10-15 07:48:19

Dear all,

during the last few days I was examining the boost facilities for random graphs
and found there is a lot of room for improvements. I do not want to blame BGL,
I just want to point out some things that could be improved in future versions of BGL.

random_vertex
=============

This function returns a random vertex. For Graphs with more than one vertex
this is done by iterating over a random number of vertices starting from the
first vertex.  

      uniform_int<> distrib(0, num_vertices(g)-1);
      variate_generator<RandomNumGen&, uniform_int<> > rand_gen(gen, distrib);
      std::size_t n = rand_gen();
      typename graph_traits<Graph>::vertex_iterator
        i = vertices(g).first;
      while (n-- > 0) ++i; // std::advance not VC++ portable
      return *i;

If graph_traits<Graph>::vertex_iterator is a random access iterator this
implementation is unnecessary slow and causes a significant performance loss
if random_vertex lies in the innermost loop of a computation. So I wonder, do
recent versions of the Microsoft-Compiler still suffer form this problem, and
if so is there a work-around? 

In my opinion an implementation by std::advance would improve the quality of 
the function random_vertex significantly.

random_edge
===========

Here the same criticism applies as for random_vertex.

generate_random_graph
=====================

The documentation describes this function as follows:

  template <typename MutableGraph, class RandNumGen>
  void generate_random_graph
    (MutableGraph& g, 
     typename graph_traits<MutableGraph>::vertices_size_type V,
     typename graph_traits<MutableGraph>::vertices_size_type E,
     RandNumGen& gen,
     bool allow_parallel = true,
     bool self_edges = false);

  Effects: Adds V vertices and E edges, to g. Source and target vertices of each
  edge are randomly chosen. If self_edges is false, then no edge will have the
  same source and targets. 

  Precondition: num_vertices(g) == 0

  Compleixity: O(V*E)

This description is a little bit misleading. If this function is called with
an empty graph and allow_parallel = false, the resulting graph will have at
most E edges but not exactly E edges as one could expect. Some edges may be
inserted more than one time, but they will effectively appear just once
because of allow_parallel = false. As a consequence it is not possible to
generate graphs from the classical Erdös-Renyi-ensemble by
generate_random_graph. Erdös-Renyi-ensemble G_{V,E} is usually defined as the
ensemble of random undirected graphs with V nodes and E edges but no parallel
edges or self edge.

Furthermore shouldn't the signature of generate_random_graph read

  template <typename MutableGraph, class RandNumGen>
  void generate_random_graph
    (MutableGraph& g, 
     typename graph_traits<MutableGraph>::vertices_size_type V,
     typename graph_traits<MutableGraph>::edges_size_type E,
     RandNumGen& gen,
     bool allow_parallel = true,
     bool self_edges = false);

class erdos_renyi_iterator
==========================

This class template does not implement a generator for Erdös-Renyi graphs as
claimed. It's just a crude approximation to Erdös-Renyi graphs. 

The first point to criticise is that in erdos_renyi_iterator the parameter of
the Erdös-Renyi-ensemble G_{V,E} are given in unusual units. Instead of
specifying the number of edges in the graph E a "probability" p is given, with

  E = p * V * V            if the graph is directed, and

  E = p * floor(V*V/2)     if the graph is undirected.

Note, for fixed V and p the current implementation of erdos_renyi_iterator
will generate graphs with the same number of edges, no matter if the the graph
allows self loops or not. But if p should be interpreted as a probability a
graph without self loops has to have fewer edges than a graph with self
loops. If erdos_renyi_iterator is used for initialising a graph structure with
iterator-based initialisation that does not provide parallel edges, the
resulting graph will have E or less edges.

Therefore I would suggest an erdos_renyi_iterator class that will never
generate parallel edges and that has the following signature:

template<typename RandomGenerator, typename Graph>
class erdos_renyi_iterator
{
public:
  typedef std::input_iterator_tag iterator_category;
  typedef std::pair<vertices_size_type, vertices_size_type> value_type;
  typedef const value_type& reference;
  typedef const value_type* pointer;
  typedef void difference_type;

  erdos_renyi_iterator();
  erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
                       edges_size_type m, bool allow_self_loops = false);
  // Iterator operations
  reference operator*() const;
  pointer operator->() const;
  erdos_renyi_iterator& operator++();
  erdos_renyi_iterator operator++(int);
  bool operator==(const erdos_renyi_iterator& other) const;
  bool operator!=(const erdos_renyi_iterator& other) const;
}; 

Pre-condition:

  0 <= m <= n(n-1)/2    if  allow_self_loops == false  and graph undirected
  0 <= m <= n(n+1)/2    if  allow_self_loops == true   and graph undirected
  
  0 <= m <= n(n-1)      if  allow_self_loops == false  and graph directed
  0 <= m <= n*n         if  allow_self_loops == true   and graph directed
  

Class erdos_renyi_iterator is suitable for initialising an adjacency_list or
other graph structure with iterator-based initialisation. Class
adjacency_matrix is such a graph structure, at least according to the 
documentation. But in fact the implementation of adjacency_matrix is lacking
the constructors 

template <typename EdgeIterator>
adjacency_matrix(EdgeIterator first,
                 EdgeIterator last,
                 vertices_size_type n,
                 const GraphProperty& p = GraphProperty())

and

template <typename EdgeIterator, typename EdgePropertyIterator>
adjacency_matrix(EdgeIterator first, EdgeIterator last,
                 EdgePropertyIterator ep_iter,
                 vertices_size_type n,
                 const GraphProperty& p = GraphProperty())

Both constructors are described by the BLG documentation but actually not
implemented. One should either change the documentation of adjacency_matrix or
its implementation. Here a possible implementation of one missing constructor:

    // Constructor required by IteratorConstructibleGraph
    template <typename EdgeIterator>
    adjacency_matrix(EdgeIterator first,
                     EdgeIterator last,
                     vertices_size_type n_vertices,
                     const GraphProperty& p = GraphProperty()) : 
      m_matrix(Directed::is_directed ? 
               (n_vertices * n_vertices)
               : (n_vertices * (n_vertices + 1) / 2)),
      m_vertex_set(0, n_vertices),
      m_vertex_properties(n_vertices),
      m_num_edges(0) { 
      if (first != last) {  // do nothing if list of edges is empty
        // if number of vertices unknown determine number of vertices 
        // by the largest node number in edge range
        if (n_vertices==0) {
          for (EdgeIterator i(first); i!=last; ++i) {
            if (i->first>n_vertices)
              n_vertices=i->first;
            if (i->second>n_vertices)
              n_vertices=i->second;
          }
          ++n_vertices;
          // resize storrage objects
          m_matrix.resize(Directed::is_directed ?
                          (n_vertices * n_vertices)
                          : (n_vertices * (n_vertices + 1) / 2));
          m_vertex_set=VertexList(0, n_vertices);
          m_vertex_properties.resize(n_vertices);
        }
        // add edges
        for (EdgeIterator i(first); i!=last; ++i)
          add_edge(i->first, i->second, *this);
      }
    } 

    with regards

    Heiko

-- 
-- Die Moral ist immer die letzte Zuflucht der Leute, welche die
-- Schönheit nicht begreifen. 
-- (Oscar Wilde, engl. Schriftsteller, 1854-1900)
-- Heiko Bauke @ http://www.uni-magdeburg.de/bauke