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