#12362: Improvement of GNP generators for graphs and digraphs
-----------------------------------------------+----------------------------
Reporter: dcoudert | Owner: jason, ncohen,
rlm
Type: enhancement | Status: closed
Priority: minor | Milestone: sage-5.0
Component: graph theory | Resolution: fixed
Keywords: directed graphs, generators | Work issues:
Report Upstream: N/A | Reviewers: Nathann Cohen
Authors: David Coudert | Merged in: sage-5.0.beta9
Dependencies: | Stopgaps:
-----------------------------------------------+----------------------------
Comment (by dcoudert):
Hello,
the default method is networkx (as before this patch) and so when used
with default parameters this patch has no impact on the running time.
When I wrote this patch, we decided to let networkx as default algorithm
because the running time was faster with new method only for large graphs.
Something has changed with networkx. It is now surprisingly slow...
{{{
sage: %timeit networkx.gnp_random_graph(2000,0.01)
5 loops, best of 3: 4.31 s per loop
sage: %timeit graphs.RandomGNP(2000, .01, method='networkx')
5 loops, best of 3: 4.47 s per loop
sage: %timeit Graph(networkx.gnp_random_graph(2000,0.01))
5 loops, best of 3: 4.49 s per loop
sage: %timeit graphs.RandomGNP(2000, .01, method='Sage')
5 loops, best of 3: 173 ms per loop
sage:
sage: %timeit graphs.RandomGNP(100, .01, method='networkx')
25 loops, best of 3: 11.2 ms per loop
sage: %timeit graphs.RandomGNP(100, .01, method='Sage')
625 loops, best of 3: 659 µs per loop
}}}
If we are unable to find why networkx is now slow, we can open a ticket to
put Sage as default algorithm.
For directed graphs, our implementation was always faster than networkx,
and so we removed the networkx one.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12362#comment:40>
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.
