#17135: Compute diameter using 2sweep, 4sweep and iFUB
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_review
Type: | Milestone: sage-6.4
enhancement | Resolution:
Priority: minor | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: David | b4491296b1a0b4c0590b0678d7391f78fe503682
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
u/dcoudert/help |
Dependencies: |
-------------------------+-------------------------------------------------
Changes (by dcoudert):
* status: new => needs_review
* commit: => b4491296b1a0b4c0590b0678d7391f78fe503682
* cc: ncohen (added)
Old description:
> This patch implements:
> - 2sweep and 4sweep lower bounds on the diameter of a graph
> - iFUB, an exact and fast algorithm for computing the diameter of a graph
New description:
This patch implements:
- 2sweep and 4sweep lower bounds on the diameter of a graph
- iFUB, an exact and fast algorithm for computing the diameter of a graph
{{{
sage: G = graphs.RandomBarabasiAlbert(1000,2)
sage: %time G.diameter('standard')
CPU times: user 44 ms, sys: 0 ns, total: 44 ms
Wall time: 42.7 ms
7
sage: %time G.diameter('iFUB')
CPU times: user 24 ms, sys: 1 ms, total: 25 ms
Wall time: 23.6 ms
7
sage: G = graphs.RandomBarabasiAlbert(10000,2)
sage: %time G.diameter('standard')
CPU times: user 3.49 s, sys: 1 ms, total: 3.49 s
Wall time: 3.49 s
9
sage: %time G.diameter('iFUB')
CPU times: user 336 ms, sys: 2 ms, total: 338 ms
Wall time: 333 ms
9
}}}
The running time of the iFUB method depends on many parameters but is in
general faster than previous methods.
{{{
sage: G = graphs.Grid2dGraph(50,50)
sage: %time G.diameter('standard')
CPU times: user 138 ms, sys: 2 ms, total: 140 ms
Wall time: 139 ms
98
sage: %time G.diameter('iFUB')
CPU times: user 80 ms, sys: 2 ms, total: 82 ms
Wall time: 80.5 ms
98
sage: V = G.vertices()
sage: shuffle(V)
sage: G.relabel(inplace=True, perm=V)
sage: %time G.diameter('iFUB')
CPU times: user 35 ms, sys: 1 ms, total: 36 ms
Wall time: 33.4 ms
98
sage: shuffle(V)
sage: G.relabel(inplace=True, perm=V)
sage: %time G.diameter('iFUB')
CPU times: user 35 ms, sys: 1 ms, total: 36 ms
Wall time: 34.2 ms
98
}}}
--
Comment:
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=3dd69119192bdc8124ffe14670daa49440dcc3a0
3dd6911]||{{{add references}}}||
||[http://git.sagemath.org/sage.git/commit/?id=d0826873ce4109c726b371cca88d0e918dcb857e
d082687]||{{{add 2sweep, 4sweep, iFUB}}}||
||[http://git.sagemath.org/sage.git/commit/?id=6c788dca3b712b28e181aed66fa560ea84a37160
6c788dc]||{{{fixed bug with Infinity}}}||
||[http://git.sagemath.org/sage.git/commit/?id=fb27cf786a63620a76854e64caae3b40b0326bfc
fb27cf7]||{{{fixed bug with DiGraph}}}||
||[http://git.sagemath.org/sage.git/commit/?id=3458a0af3adb65c8cdd2f999eaac8937ce663210
3458a0a]||{{{fixed bug}}}||
||[http://git.sagemath.org/sage.git/commit/?id=b4491296b1a0b4c0590b0678d7391f78fe503682
b449129]||{{{fixed bugs}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/17135#comment:3>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
