#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:
----------------------------+-----------------------------------------------
Comment(by ncohen):
Hellooooooo David !
Well, I don't think not being able to define the seed *as a parameter* of
the function is so bad. As it works fine when you set it globally for the
doctests anyway....
Now, here is a small patch with some modifications. It adds a few tests,
check that the given method is "networkx" or "Sage" but nothing else
(that's how we do it usually). I also added a "(Cython)" to the title of
the new file you create. It makes more sense this way when you look at the
documentation. Otherwise, you would have:
* Digraph generators
* Graph Generators
* Digraph and Graph generators
Now there is a "Cython" at the end of the third one, and there's some
logic to it `:-)`
This being said, I added one test which does *not* pass... Here it is :
{{{
sage: from sage.graphs.graph_generators_pyx import RandomGNP
sage: abs(mean([RandomGNP(150,.2, fast = True).density() for i in
range(30)])-.2) < .001
False
}}}
It looks like there is some deviation with the "fast" algorithm, which
does not occur with the usual one :
{{{
sage: sage: abs(mean([RandomGNP(200,.2).density() for i in range(30)])-.2)
0.000443886097152429
sage: sage: abs(mean([RandomGNP(200,.2, fast = True).density() for i in
range(30)])-.2)
0.0163283739008691
}}}
Well, that's already 1% of edges too much. I don't think the deviation
with the first algorithm is very bad (though for some reason it is always
positive on my tests, and I do not like that), but I'm no big fan of the
deviation for the second implementation
The "fast" algorithm is also.... *MUCH SLOWER* on most cases... Is it
better than the other one in some interesting situations ?
Oh, and I also noticed that the graphs returned did not necessarily have n
vertices when p was too low. I fixed that in the patch too `:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12362#comment:12>
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.
