#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:
----------------------------------------+-----------------------------------
Comment (by ncohen):
Hellooooooooooooooooooo !!
A better day begins, with music. Music solves everything `:-P`
> 1. Yes we can define a structure to store extremities of paths, but I'm
not so sure it is totally free. I agree it could be easier to read.
Oh. C struct ? Yeah, they are free. Especially when their size is
2*sizeof(int) `:-P`
> 1. I agree with proposed improvement of documentation
> 1. Concerning the uint64_t. I did some tests with very large graphs, so
it was useful at least for me (I also used that type to count number of
visited 4-tuples although it is not part of this patch).
What ? `O_o`
Do you mean that in some situation regular int were not enough ? I really
wonder where `O_O;;;`
Furthermore, I'm not so sure we can use int instead, and clearly unsigned
int or unsigned long int would be harder to read that uint64_t.
Well, it seems to me that you can easily use regular 32 bits int without
any proble, so that coding this with int should work. You count vertices
(less than `2^16=65536`, and even less than `2^15=32768`. Anyway the
distance_all_pairs code is meant to work with unished short, if I make no
mistake, so it would not work if you have more than `2^16-1` vertices.
Then, you count pair of vertices, and this is not larger than `(2^16)^2 =
2^32`, so what's the problem ? At some point in your code there is a weird
"if" with a comment reading "we work on unisnged int", and I did not
understand it so I cannot tell right now that this would not be a problem
either if 64-bits int are replaced by 32bits int.
> 1. Number of paths: you are right. The proposed modification clarifies
the doc.
> 1. elimination_bucket: The patch is ready to host any heuristic/algo
able to identify vertices that could be eliminated as soon as the lower
bound is 2 or 3 or more. However, as discussed by mail, I don't have
efficient ways to identify such vertices yet. Since the extra cost is
negligeable, I suggest to let it as it (including comments).
Well, the extra computing time is negligible, but it makes it much harder
to understand when you try to read the code. And. Well, it does nothing
`^^;` Could you keep a copy of this method instead, to be used when you
will have heuristics to plug there, and in the meantime keep Sage's code
optimal with what is implemented and not what we plan to implement
eventually ? `:-P`
> 1. sage_calloc: was not aware of it. is it safe? stable? can we safely
use it if we use structures instead of arrays of numbers?
Oh. Well, calloc is a C function, so I guess that it is just wrapped by
sage, the same way malloc and free are wrapped.
http://linux.die.net/man/3/calloc
> 1. extra tmp variable: since the function _invert_cells is inlined, it
means each execution would have to instantiate a new variable. I'm not
sure it is better/faster than current implementation.
Here is how the function is writted right now :
{{{
cdef inline _invert_cells(uint64_t * tab, uint64_t idxa, uint64_t idxb,
uint64_t tmp):
tmp = tab[idxa]
tab[idxa] = tab[idxb]
tab[idxb] = tmp
}}}
Let us assume for a start that the function is *NOT* inlined. In this
case, the value of "tmp" that the function received as input is totally
useless : the function creates a new local variable named tmp, and assigns
to it the value of tmp given as input.
Well, that is useless for a new local variable is created.
And if the function is inlined, a variable will be created, well then
there is no problem for a variable will be created inside of the function
that call it to do exactly what you are doing.
But. Well, how much do you want to bet that it is totally impossible to
detect the difference between the two codes, even if _invert_cells called
malloc(sizeof(int)) manually each time this function is called ? `:-P`
> 1. the a.patch is OK.
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13808#comment:10>
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.
