#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: |
-------------------------+-------------------------------------------------
Comment (by dcoudert):
Replying to [comment:21 ncohen]:
> 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.
I have added a test at the beginning of method `__hyperbolicity__`. I have
also forced initialization of distances to largest possible value in
method `distances_and_far_apart_pairs`, although it is clearly written
that this method ensures a connected graph. Now we should be on the safe
side.
> 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.
You are right, such situation may happen. Suppose for instance that the
graph has 2 biconnected components, a (k+1)*(k+1)-grid and a k-hyperbolic
graph with large diameter and plenty of far-apart pairs with various
distances. The upper bound for the grid will be k, but for the other
component the upper bound could be large (c*k or k+c).
I have moved the update of the upper bound (`hyp_UB = max(hyp_UB, hh_UB)`)
outside of the `if...` to address such case.
> 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
I hope it's better now.
--
Ticket URL: <http://trac.sagemath.org/ticket/17227#comment:22>
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.
