#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 | e44ca66fc938dbedc653fc23e88a23618d79366c
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17227 |
Dependencies: |
-------------------------+-------------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
Helloooooo !
> 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?
Yes, please. It will only be a l-dimension loop, so it will really be
cheap.
> 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.
Okay, +1.
> > 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)`.
Okay. My question had a second part, however: is it possible that even
though `hh < hyp` we have `hh_UB > hyp_UB` ? In this situation the upper
bound would need to be updated, even though `hyp` would stay the same.
> 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`.
Sorry sorry, I just meant this as a general remark. While it could be used
in this code, it is already sufficiently complicated to not use Python-
specific instructions unless there is a good reason (that I do not see
here).
I set the ticket to `needs_work`, because of the connectivity test and the
question related to the upper bound. We will be done soon.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17227#comment:21>
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.
