Improve random graph creation
(kind of a follow-up from !249 (merged), handling this in a separate MR such that the other one can be merged already)
Description
The ErdösRenyi
algorithm for creating random graphs is based on boost::generate_random_graph
. If the graph type already disallows parallel edges (i.e., setS
as edge container), the whole graph is copied unnecessarily – see this comment:
// When parallel edges are not allowed, we create a new graph which
// does not allow parallel edges, construct it and copy back.
// This is not efficient if 'g' already disallow parallel edges,
// but that's task for later.
Proposal
Check whether the edge container is setS
. If so, drop the allow_parallel
argument in the boost::generate_random_graph
call, which will then call the function overload where no such graph copy is done.
Another thing: We should improve the docstring by making the following behavior of boost::generate_random_graph
clear:
A maximum number of number_of_vertices * number_of_vertices
attempts are done for finding random edges to add (which are not already there). That implies that it is most likely not possible to create a complete graph using boost::generate_random_graph
!
How to test the implementation?
Make sure there is a test case for that.