#17227: Add new cutting rules for computing hyperbolicity
-------------------------------------+-------------------------------------
Reporter: dcoudert | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: David Coudert | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/dcoudert/add_new_cutting_rules_for_computing_hyperbolicity|
ee216e2669de1aff1cc91e6a7b0c47c46a3159a9
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by dcoudert):
* status: new => needs_review
* commit: => ee216e2669de1aff1cc91e6a7b0c47c46a3159a9
Old description:
New description:
This patch adds two cutting rules, one for the `'basic'` algorithm and one
for the `'cuts'` algorithm.
* the new `'basic+'` algorithm uses the new cutting rule and is always
faster than the `'basic'` one.
* the `'cuts+'` algorithm is now an exact algorithm using the notion of
far-apart pairs to reduce the size of the search space. It is sometimes
faster than the `'cuts'` algorithm although it has a longer pre-processing
time. It is faster for instance on rectangular grids, petersen, and on
graphs such that the hyperbolicity is small compared to the diameter/2.
--
Comment:
Some examples
{{{
sage: from sage.graphs.hyperbolicity import hyperbolicity
sage: G = graphs.PetersenGraph()
sage: %time hyperbolicity(G, algorithm='basic')
CPU times: user 2 ms, sys: 0 ns, total: 2 ms
Wall time: 1.16 ms
(1/2, [0, 1, 2, 3], 1/2)
sage: %time hyperbolicity(G, algorithm='basic+')
CPU times: user 1 ms, sys: 0 ns, total: 1 ms
Wall time: 1.13 ms
(1/2, [0, 1, 2, 3], 1/2)
sage: %time hyperbolicity(G, algorithm='cuts')
CPU times: user 2 ms, sys: 0 ns, total: 2 ms
Wall time: 1.19 ms
(1/2, [0, 1, 2, 3], 1/2)
sage: %time hyperbolicity(G, algorithm='cuts+')
CPU times: user 1e+03 µs, sys: 0 ns, total: 1e+03 µs
Wall time: 776 µs
(1/2, [0, 1, 2, 3], 1/2)
}}}
{{{
sage: G = graphs.Grid2dGraph(20,10)
sage: %time hyperbolicity(G, algorithm='basic')
CPU times: user 681 ms, sys: 3 ms, total: 684 ms
Wall time: 682 ms
(9, [(0, 0), (0, 9), (9, 0), (9, 9)], 9)
sage: %time hyperbolicity(G, algorithm='basic+')
CPU times: user 52 ms, sys: 0 ns, total: 52 ms
Wall time: 49 ms
(9, [(0, 0), (0, 9), (9, 0), (9, 9)], 9)
sage: %time hyperbolicity(G, algorithm='cuts')
CPU times: user 22 ms, sys: 1 ms, total: 23 ms
Wall time: 21.5 ms
(9, [(0, 0), (0, 9), (19, 0), (19, 9)], 9)
sage: %time hyperbolicity(G, algorithm='cuts+')
CPU times: user 17 ms, sys: 2 ms, total: 19 ms
Wall time: 16.2 ms
(9, [(0, 0), (0, 9), (19, 0), (19, 9)], 9)
}}}
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=ee216e2669de1aff1cc91e6a7b0c47c46a3159a9
ee216e2]||{{{#17227: adds far apart pairs and cleanup the code}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/17227#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.
