#14502: Improvements of hyperbolicity procedures
---------------------------------+------------------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.10
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: David Coudert | Merged in:
Dependencies: | Stopgaps:
---------------------------------+------------------------------------------
Comment (by dcoudert):
> * You probably want to sort the vertices .... in the other direction.
right. I have added a reverse=True.
> * I am not sure that the ordering of the degrees in `.degree()` is the
same as `g.vertices()`. You probably want to use `g.degree(labels =True)`.
That's of course safer. I'm now using the degree_iterator instead since
.degree(labels=True) returns a dictionary.
> * seen is a set, not a dictionary
I was wondering if it is faster to use a dict or a set in this case. I'm
now using a set.
> * Why do you need 32 bits for each vertex of a pair ? The algorithm uses
distance_all_pairs which does not work when the vertices cannot be stored
on short int.
changed
> * Why do you remove all this `h>=2` code ?
What we had before was incorrect. We were assuming that as soon as h>=2 it
was not necessary to consider some vertices anymore (hence the h>=2 code).
Since, we have proved that this is not true due to (a|b1,b2,b3) 4-tuples.
Now, the method is given a distance matrix and a set of vertices that we
should not considered during computations. We order the pairs in such a
way that pairs incident to vertices that should not be considered are
above last_pair in the arrays. Observe that these orderings are done in
linear time (in the number of pairs).
The other option was extract from the distance matrix the submatrix
containing only distances between vertices we want to consider. I don't
know which method is the fastest, but it was trivial to update the code
the way I did it.
> * Why do you replace a call to `relabel` with a call to `my_subgraph` ?
Is it because `.relabel()` is too slow ? The speed of this function has
been changed *a LOT* by #14000. You can also set `check_input=False` if
you are sure that there is no problem with the new labels.
I'm just combining the cost of taking the subgraph with the cost of
relabeling the vertices. I think it's overall faster than splitting the
calls, even if the new relabel method is fast.
I'm now also improving upper bounds since delta <= D/2.
Thanks,
David.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14502#comment:3>
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?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
