#17227: Add new cutting rules for computing hyperbolicity
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_review
Type: | Milestone: sage-6.4
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers: Nathann Cohen
theory | Work issues:
Keywords: | Commit:
Authors: David | e44ca66fc938dbedc653fc23e88a23618d79366c
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17227 |
Dependencies: |
-------------------------+-------------------------------------------------
Changes (by dcoudert):
* status: needs_work => needs_review
Comment:
Replying to [comment:18 ncohen]:
> 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.
Corrected.
> > 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 ^^;
Method {{{__hyperbolicity__}}} takes as input the distance matrix but not
the graph itself. So the only way to check that the graph is connected
would be to check that all distances from node 0 in the distance matrix
are in the range [0,N-1].
Should I add such a test?
> > 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.
In fact all details are in a paper under submission. We can wait until the
paper get accepted to replace the reference. This can be done in the patch
removing the 'basic' method.
> 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`.
Right. I have changed to `hyp_UB = max(hyp_UB,hh_UB)`.
> - 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:
> }}}
I know that, but I don't know how it can be used to simplify the code.
Indeed, the `else` part will always be executed, even without `pass` or
`break`.
Thanks Nathann.
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=e44ca66fc938dbedc653fc23e88a23618d79366c
e44ca66]||{{{trac #17227: small corrections for comment 18}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/17227#comment:20>
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.
