#13808: Gromov hyperbolicity of graphs
----------------------------------------+-----------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.6
Component: graph theory | Resolution:
Keywords: graph, hyperbolicity | Work issues:
Report Upstream: N/A | Reviewers:
Authors: David Coudert | Merged in:
Dependencies: | Stopgaps:
----------------------------------------+-----------------------------------
Changes (by ncohen):
* status: needs_review => needs_work
Comment:
Helloooooooo David !!
Well, I have been working of this patch for the last hour (at least), and
I was not able to produce a patch for some of the changes I think would be
good for I still do not understand the code well enough, and I only end up
producing segfaults...
I think that it would be nice to define the following C struct, for we are
in the wonderful world of C where creating structs is totally free (unlike
Java `:-P`)
{{{
# Defining a pair of vertices as a C struct
ctypedef struct pair:
int i
int j
}}}
This way, you do not have wird `+2` increments anymore, and you can call
the `invert_cells` function only once (to exchange pair structs, not
integers).
I wanted to add the following documentation
{{{
# We organize the pairs of vertices by length in an array of pair
structs
#
# - path_of_length[i] point to the list of nb_path_of_length[i] pairs
of
# vertices at distance i
#
# - cpt_path[i] counts the number of pairs have already been added to
# path_of_length[i]
#
# - all_pairs is a memory block of binomial(n,2) pairs of
# vertices. path_of_length[i] points toward a memory area contained
in -
# all_pairs.
#
}}}
to replace your
{{{
# We organize the path by length in an array using 2 cells per path.
}}}
though it only makes sense in my segfaulting version of hyperbolicity.pyx.
If you agree with this change from integers toward pairs, then this doc
could be useful.
Other comments :
* I do not see the point of using uint64_t instead of integers. I mean, if
we all agree that the code is not supposed to run on 16-bits machines
`:-P` The integers you need are -- in the worst case -- of order `n^2`,
which may reach the 32bits limit only if the graph has size around 40k
vertices. The rest of the time, requiring the integers to be 64bits just
means moving around blocks of 0, and will be slower than int on 32 bits
machines. Except if I missed something somewhere `O_o` Plus the code would
be muuuuuuuuch easier to read without that `:-P`
* You say several times that you compute the number of paths of each
length. This scared me for you did this with only +1 increments, and the
number of paths of each length is possibly... HUGE (of order `n!` in a
complete graph). What you compute is actually the number of pairs of
distance l for each l. Some names of variables need to be updated.
* elimination_bucket : hmmm... Well, this method is written so that it is
able to deal with code that.... it does not contain :-P
{{{
- Then, we take a vertex ``u``. The diameter in ``G`` of the subgraph
of its
neighbors is at most two. To ensure a valid tree-decomposition, we
select
``u`` if and only if the bag formed by its neighbors is either
included in
another bag, or includes another bag. We repeat until no more vertex
can be
selected. This step is heuristic and the result depends on the order
in
which vertices are considered. NOT IMPLEMENTED YET.
}}}
And it returns a list of things, in which only the first element will
have any use (the one corresponding to vertices whose neighborhood is a
clique) for the other ones will be empty. And the `max_diameter` is
completely useless, ...
* Oh, and you can use `sage_calloc` to allocate and set to zero at the
same time.
I attach a small patch that deals with unimportant things.
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13808#comment:7>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
