#19049: New Hyperbolicity Algorithm
-------------------------------------+-------------------------------------
Reporter: borassi | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.9
Component: graph theory | Resolution:
Keywords: Hyperbolicity | Merged in:
Authors: Michele Borassi | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/borassi/new_hyperbolicity_algorithm|
e2fe1c11dee8d5424927eb2a002c92687536b68e
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by borassi):
Hello!
Replying to [comment:4 dcoudert]:
> It's working very well. I have very few and minor comments
> - reduce the number of iterations of the test `for i in range(100): #
long time`. 10 is enough.
Done!
> - replace reference [CCL12] with [CCL15]: N. Cohen, D. Coudert, A.
Lancin. On computing the Gromov hyperbolicity. ACM Journal of Experimental
Algorithmics, 20(1.6):1-18, 2015. [`<http://dx.doi.org/10.1145/2780652>`_]
or [`<https://hal.inria.fr/hal-01182890>`_]
Done! I used the first link.
> - I think it is better to write `for b in range(D-1,-1,-1):` than `for b
from D > b >= 0:` although the later is easier to read. see
http://docs.cython.org/src/userguide/language_basics.html#integer-for-
loops
Done!
> - Instead of `c = a`, `a = b` and `b = c` you can write directly `a,b =
b,a`
Done!
> - When you `# We reset acc_bool`, it might be easier to use `memset`.
This part has negligeable impact on the computation time anyway.
Not done! In my opinion, it has impact on the computation time. Indeed,
when we fix a pair (a,b), the algorithm does the following:
{{{
for c in decreasing order of ecc(c)-d(a,c):
if ecc(c)-d(a,c) >= 3*(h+1)-2*d(a,b):
... other tests to check if v is acceptable and/or valuable
else:
break # All other vertices c are not acceptable and not valuable
for c in valuable:
for (c,d) pair before (a,b), with d acceptable:
h = max(h, delta(a,b,c,d))
for c in acceptable:
acc_bool[c] = 0
}}}
Here, the first for loop is performed as many times as the number of
vertices satisfying `ecc(c)-d(a,c) >= 3*(h+1)-2*d(a,b)` (let's say, 100,
if the graph has with 10000 vertices). The second for loop needs time
O(acceptable * valuable), where acceptable is, let's say, 10, and valuable
is 5. The total time is 50.
The last loop takes time 10, as it is, while it takes time 10000 if we use
memset (I know memset is very fast, but here we are talking about two
orders of magnitude).
Did I convince you?
--
Ticket URL: <http://trac.sagemath.org/ticket/19049#comment:5>
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.
