#17227: Add new cutting rules for computing hyperbolicity
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_work
Type: | Milestone: sage-6.4
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers: Nathann Cohen
theory | Work issues:
Keywords: | Commit:
Authors: David | 6f5df4ae85820ac3235c21134f79c07b27710184
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17227 |
Dependencies: |
-------------------------+-------------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
Hello David !
> Well, since we have 'basic+', we don't need 'basic' anymore.
+1
> I have corrected the documentation. Soto proved that `hyp(a,b,c,d) <=
2*dist(a,b)`
It seems that you only fixed the text and not the math formula that
follows.
> I'm clearly consuming much more memory than necessary.
> If the extra cost is not too high, I may propose the modification in
another patch.
Okay. Perhaps the removal of 'basic' will make things slightly clearer
already.
> I have updated the documentation of the method to precise that it
assumes that
> the input graph is connected.
Would you be willing to add a check right at the beginning of the
function, just
in case the graph is not connected ? The complexity of the algorithm will
not be
hurt by one more BFS ^^;
> I have changed the comment to `Compute the hyperbolicity using a the
algorithm of [CCL12]_`
Sorry, my remark was not very clear: what I meant is that the function
that
follows does not only implement the algorithm from CCL12. It also deals
with
far-apart pairs, and unless I make a mistake there was no mention of them
in
that paper. The second line of the function's doc say the same.
Other comments:
- In this block of code:
{{{
if hh > hyp or (hh==hyp and not certificate):
hyp = hh
hyp_UB = hh_UB
certificate = certif
}}}
Shouldn't we have `hyp_UB = max(hyp_UB,hh_UB)` instead ? Or is it always
correct for some other reason ? Also, if the 'min' is necessary, could
there
be a situation in which `hh < hyp` but `hh_UB > hyp_UB` ? In that case
the
upper bound would need to be updated, but not `hyp`.
- About {{{return (h, certificate, h_UB if GOTO_RETURN else h)}}}: note
that in
Python you can have a for/else:
{{{
sage: for i in range(40):
....: pass
....: else:
....: print "Hey"
....:
Hey
sage: for i in range(40):
....: break
....: else:
....: print "Hey"
....:
sage:
}}}
By the way, thank you for adressing all those remarks methodically and
answering
on each point. While the branch is heavy it makes this review less painful
than
others in which the authors "forget" some questions `:-P`
Cheers,
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17227#comment:18>
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.
