#12362: Improvement of GNP generators for graphs and digraphs
----------------------------+-----------------------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-5.0
Component: graph theory | Keywords: directed graphs, generators
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
----------------------------+-----------------------------------------------
Changes (by dcoudert):
* status: needs_work => needs_review
Comment:
I have addressed all your remarks. The "detail" was because I have
stupidly copy/paste your ``(i+1 if directed else 0)``. It should be ``(0
if directed else i+1)`` ;)
For graphs, I have decided to let the networkx method as default.
{{{
sage: %timeit networkx.gnp_random_graph(1000,0.01)
5 loops, best of 3: 1.03 s per loop
sage: %timeit graphs.RandomGNP(1000,0.01,method='sage')
5 loops, best of 3: 233 ms per loop
sage: %timeit graphs.RandomGNP(1000,0.01,method='networkx')
5 loops, best of 3: 66.5 ms per loop
sage: %timeit networkx.gnp_random_graph(100,0.05,method='sage')
25 loops, best of 3: 10.9 ms per loop
sage: %timeit graphs.RandomGNP(100,0.05,method='sage')
25 loops, best of 3: 11.4 ms per loop
sage: %timeit graphs.RandomGNP(100,0.05,method='networkx')
125 loops, best of 3: 3.45 ms per loop
}}}
Concerning the average density, it is seems correct with larger sample.
{{{
sage: mean([digraphs.RandomDirectedGNP(100,.1, loops = True).density()+.0
for i in range(500)])
0.100094400000000
sage: mean([digraphs.RandomDirectedGNP(100,.1, loops = False).density()+.0
for i in range(500)])
0.100155555555556
sage: mean([digraphs.RandomDirectedGNP(100,.1, loops = False, fast =
True).density()+.0 for i in range(500)])
0.0989579797979798
sage: mean([digraphs.RandomDirectedGNP(100,.1, loops = True, fast =
True).density()+.0 for i in range(500)])
0.0988469999999999
sage: mean([graphs.RandomGNP(100,.1, fast = False,
method='sage').density()+.0 for i in range(500)])
0.100131313131313
sage: mean([graphs.RandomGNP(100,.1, fast = False,
method='networkx').density()+.0 for i in range(500)])
0.100190707070707
sage: mean([graphs.RandomGNP(100,.1, fast = True,
method='networkx').density()+.0 for i in range(500)])
0.100002424242424
sage: mean([graphs.RandomGNP(100,.1, fast = True,
method='sage').density()+.0 for i in range(500)])
0.104045165676905
}}}
A possible improvement for RandomDirectedGNP is to return a complete
digraph (with or without loops) when p=1. However, no such function exists
and it is not relevant in this patch. I let it for another patch.
D.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12362#comment:10>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
