#12362: Improvement of GNP generators for graphs and digraphs
----------------------------+-----------------------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
Priority: minor | Milestone: sage-5.0
Component: graph theory | Keywords: directed graphs, generators
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
----------------------------+-----------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
Hellooooooo !!!
> Some running time. The fast algorithm is better for large sparse graphs.
Nice ! Could you advertise it in the doc ? Something like "the fast
algorithm is only faster for *LARGE* instances (try it to know whether it
is useful for you)" ?
I tried to improve it a bit because I still find weird that networkx could
beat us at this game, but found nothing yet... I'll try again later `:-p`
This being said, I was thinking of two things. The first of the two you
reported yourself some time ago : the means seem to be below what is
expected...
{{{
sage: mean([digraphs.RandomDirectedGNP(100,.1, fast = True).density()+.0
for i in range(50)])
0.0990303030303030
sage: mean([digraphs.RandomDirectedGNP(100,.1, fast = True).density()+.0
for i in range(50)])
0.0985575757575757
sage: mean([digraphs.RandomDirectedGNP(100,.1, fast = True).density()+.0
for i in range(50)])
0.0989050505050506
sage: mean([digraphs.RandomDirectedGNP(100,.1, fast = True).density()+.0
for i in range(50)])
0.0993535353535353
}}}
And there is also this "detail" `:-p`
{{{
sage: mean([digraphs.RandomDirectedGNP(100,.1, fast = False).density()+.0
for i in range(50)])
0.0498989898989899
sage: mean([digraphs.RandomDirectedGNP(100,.1, fast = True).density()+.0
for i in range(50)])
0.0987434343434344
}}}
Could you also add the file to the documentation (the files in devel/sage-
yourbranch/doc/en/reference/) and make the method available (through an
optional argument) in graphs.RandomGNP ? Even though it can not be the
default method, as networkx is faster (why the hell should it be ? `O_o`),
it would be nice to have around.
And about the matrix : it was not about C arrays but about Sage matrices,
and this is why the speedup was so huge (#12476). It is because a field
was accessed in Python as ``m[x][y]`` which translates as "build a copy of
the x^th row of m, and return its y^th element". A bit more than what was
necessary `:-P`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12362#comment:9>
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.
