Bug in generate - will tend to fail for very big graphs

[GoogleCodeExporter]

At line 85:

{{{
for i in range(num_edges):
        each = edges[i]
        random_graph.add_edge((each[0], each[1]), wt = randint(min_wt, max_wt))
}}}

It's indexing over range(num_edges), however since edges will always
contain fewer items than num_edges this will produce an index out of range.
Suggest that it should be changed to:

{{{
for i in range(len(edges)):
}}}

I cannot change this right now as I'm working on a different branch. 

Original issue reported on code.google.com by salimfadhley@gmail.com on 18 Nov 2009 at 1:15

[GoogleCodeExporter]

Original comment by salimfadhley@gmail.com on 18 Nov 2009 at 1:16

• Added labels: Milestone-1.7.0
• Removed labels: Milestone-1.6.3

[GoogleCodeExporter]

This isn't the right fix.

  Looking at the code, this seems to generate a non multigraph (same edge can't
appear twice) without loops. What's happening in you bug (I would guess) is 
that the
number of edges is more than the complete graph. This can be checked with a 
simple
assertion:

assert num_edges <= len(edges)

  Or we can just do a check, print a warning, and reset the num_edges:

if num_edges > len(edges):
    print "Warning: More edges than possible. Creating complete graph."
    num_edges = len(edges)

  Essentially the list of edges is /every/ possible edge. Note: this should be
raising flags in your minds for performance issues ;).

Original comment by christian.muise on 18 Nov 2009 at 3:11

[GoogleCodeExporter]

"this should be raising flags in your minds for performance issues ;)."

Yes, I can confirm that - it takes many seconds to generate a 1000 node, 10000 
edge
graph. In the world of modern graph theory that's not a particularly big graph. 
I
think this is inefficient for most undergraduate purposes. 

Original comment by salimfadhley@gmail.com on 18 Nov 2009 at 3:44

[GoogleCodeExporter]

@christian: 
 I am sorry if i am missing something, but are we assuming we can generate atmost
complete graphs without cycles??
Because if we are not this check should be in the salim's code right??

Original comment by anand.ib...@gmail.com on 18 Nov 2009 at 11:20

[GoogleCodeExporter]

Currently we can generate a complete graph with all the cycles you want. 
There's no
notion of DAG's in any of the code at the moment. What we /don't/ generate is
multigraphs -- ie. no edge can appear more than once.

Original comment by christian.muise on 19 Nov 2009 at 12:14

[GoogleCodeExporter]

Hmm.... thanks.. had no idea those were called multigraphs... Sorry, should 
have 
looked up first... 
anyway... here is the diff file.. 

Original comment by anand.jeyahar on 19 Nov 2009 at 12:55

Attachments:

• generators.py.diff

[GoogleCodeExporter]

Thanks. We'll get er in after the current release is packaged up.

  Cheers

Original comment by christian.muise on 19 Nov 2009 at 1:53

[GoogleCodeExporter]

Oops.... looks like my overconfidence shows.... uploaded the diff file too 
early..... 
discovered some errors.. will investigate and update.. fix .. 

Original comment by anand.jeyahar on 19 Nov 2009 at 2:25

[GoogleCodeExporter]

It turns out i was testing on an old version.. Sorry for the mess....guys.....  
I 
still need to set up development environment right.. 

Original comment by anand.jeyahar on 19 Nov 2009 at 3:58

[GoogleCodeExporter]

Original comment by pmatiello on 20 Mar 2010 at 10:23

• Removed labels: Milestone-1.7.0

[GoogleCodeExporter]

Does this bug still exist? Is there a test case that produces the error?

Original comment by pmatiello on 4 Oct 2010 at 4:05

[GoogleCodeExporter]

Taking ownership of this issue.

Original comment by pmatiello on 23 Dec 2010 at 1:50

• Changed state: Started

[GoogleCodeExporter]

Can't reproduce. I generated complete graphs of many different sizes and they 
all worked. It's still way too slow. I'll try to improve this today.

Original comment by pmatiello on 23 Dec 2010 at 2:29

• Changed state: CantReproduce