Sage: Ticket #13808: Gromov hyperbolicity of graphs
https://trac.sagemath.org/ticket/13808
<p>
This patch implements algorithms for computing the Gromov hyperbolicity of a graph. Although the worst case time complexity is in <code>O(n^4)</code>, the proposed implementation performs quite well in practice. It has been used on graphs with more than 10.000 vertices.
</p>
<p>
APPLY:
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/13808/trac_13808-v3.patch" title="Attachment 'trac_13808-v3.patch' in Ticket #13808">trac_13808-v3.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/13808/trac_13808-v3.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/13808/trac_13808-revb.patch" title="Attachment 'trac_13808-revb.patch' in Ticket #13808">trac_13808-revb.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/13808/trac_13808-revb.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/13808/trac_13808-rev2.patch" title="Attachment 'trac_13808-rev2.patch' in Ticket #13808">trac_13808-rev2.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/13808/trac_13808-rev2.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/13808/trac_13808-combinations.patch" title="Attachment 'trac_13808-combinations.patch' in Ticket #13808">trac_13808-combinations.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/13808/trac_13808-combinations.patch" title="Download"></a>
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/13808
Trac 1.1.6dcoudertSat, 08 Dec 2012 12:06:56 GMTstatus changed; cc, keywords set
https://trac.sagemath.org/ticket/13808#comment:1
https://trac.sagemath.org/ticket/13808#comment:1
<ul>
<li><strong>cc</strong>
<em>ncohen</em> added
</li>
<li><strong>keywords</strong>
<em>graph</em> <em>hyperbolicity</em> added
</li>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
<p>
I did my best to put comments inside the patch and sufficient documentation. I hope one will be able to review this patch ;-)
</p>
<p>
Thanks.
</p>
TicketncohenSun, 09 Dec 2012 19:37:31 GMTstatus changed
https://trac.sagemath.org/ticket/13808#comment:2
https://trac.sagemath.org/ticket/13808#comment:2
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Here is my current patch, and two comments :
</p>
<ul><li>It would be nice if <code></code>sage -coverage hyperbolicity.pyx<code></code> returned "100% coverage". I hate to say it, because it often means adding useless tests just to fit to the metrics <code>-_-</code>
</li><li>What is the use of _reduce_biconnected_graph compared to goodcores ? The docstring says that this function, by removing degree 2 vertices whose neighborhood is an edge, would reduce a complete bipartite graph to an edge... But no vertex of a complete bipartite graph is adjacent to two adjacent vertices (a triangle). I do not see how (as the docstring says) this function does anything different from the good core decomposition method above.
</li></ul><p>
It would also be better to set this ticket to <code>need_work</code> until your have found out where the bug you found comes from.
</p>
<p>
Tell me what you think of the changes I made ! They should make the html doc nicer !
</p>
<p>
Nathann
</p>
TicketdcoudertSun, 09 Dec 2012 19:56:18 GMT
https://trac.sagemath.org/ticket/13808#comment:3
https://trac.sagemath.org/ticket/13808#comment:3
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13808#comment:2" title="Comment 2">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Here is my current patch, and two comments :
</p>
<ul><li>It would be nice if <code></code>sage -coverage hyperbolicity.pyx<code></code> returned "100% coverage". I hate to say it, because it often means adding useless tests just to fit to the metrics <code>-_-</code>
</li></ul></blockquote>
<p>
OK, I will work on this.
</p>
<blockquote class="citation">
<ul><li>What is the use of _reduce_biconnected_graph compared to goodcores ?
</li></ul></blockquote>
<p>
Useless, but since it is very fast (linear) it can be used for all methods, while goodcores is only for cuts+.
</p>
<blockquote class="citation">
<p>
The docstring says that this function, by removing degree 2 vertices whose neighborhood is an edge, would reduce a complete bipartite graph to an edge... But no vertex of a complete bipartite graph is adjacent to two adjacent vertices (a triangle). I do not see how (as the docstring says) this function does anything different from the good core decomposition method above.
</p>
</blockquote>
<p>
Oups. We must add an edge to get many triangles.
</p>
<blockquote class="citation">
<p>
It would also be better to set this ticket to <code>need_work</code> until your have found out where the bug you found comes from.
</p>
</blockquote>
<p>
Sure.
</p>
<blockquote class="citation">
<p>
Tell me what you think of the changes I made ! They should make the html doc nicer !
</p>
</blockquote>
<p>
That's perfect. Thanks.
</p>
<blockquote class="citation">
<p>
Nathann
</p>
</blockquote>
TicketncohenSun, 09 Dec 2012 20:06:20 GMT
https://trac.sagemath.org/ticket/13808#comment:4
https://trac.sagemath.org/ticket/13808#comment:4
<blockquote class="citation">
<p>
Useless, but since it is very fast (linear) it can be used for all methods, while goodcores is only for cuts+.
</p>
</blockquote>
<p>
Oh. But what is the difference between this function and the other one, what is it that <code>_reduce_biconnected_graph</code> can do and that the core decomposition can't ? Is their running time very different for the same purposes ? Why do you need two functions ?
</p>
<p>
Nathann
</p>
TicketdcoudertSat, 15 Dec 2012 15:06:57 GMTstatus, description changed
https://trac.sagemath.org/ticket/13808#comment:5
https://trac.sagemath.org/ticket/13808#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/13808?action=diff&version=5">diff</a>)
</li>
</ul>
<p>
Hello,
</p>
<p>
I have fully revised the patch. I have merged both patches into a new one to simplify the process. I have removed the <code>_reduce_biconnected_graph</code> and <code>good_core_decomposition</code> methods and added a new one: <code>elimination_buckets</code>, where a bucket is understood as a set of vertices that can be eliminated as soon as the lower equals the index of the bucket. So far, this new function only identifies vertices that can be eliminated as soon as we know that the lower bound is 1. The code contains all the machinery to handle larger values, but I don't have good heuristic/algorithm ready to identify vertices that can be eliminated for 2 (only slow and not efficient methods). I propose to let this part for a future patch. This one is already huge...
</p>
<p>
The doc coverage is now 100%.
</p>
<p>
Should be better now.
</p>
TicketncohenSun, 16 Dec 2012 15:49:22 GMT
https://trac.sagemath.org/ticket/13808#comment:6
https://trac.sagemath.org/ticket/13808#comment:6
<p>
Apply trac_13808-v2.patch
</p>
TicketncohenMon, 17 Dec 2012 17:33:13 GMTstatus changed
https://trac.sagemath.org/ticket/13808#comment:7
https://trac.sagemath.org/ticket/13808#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Helloooooooo David !!
</p>
<p>
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...
</p>
<p>
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 <code>:-P</code>)
</p>
<pre class="wiki"># Defining a pair of vertices as a C struct
ctypedef struct pair:
int i
int j
</pre><p>
This way, you do not have wird <code>+2</code> increments anymore, and you can call the <code>invert_cells</code> function only once (to exchange pair structs, not integers).
</p>
<p>
I wanted to add the following documentation
</p>
<pre class="wiki"> # 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.
#
</pre><p>
to replace your
</p>
<pre class="wiki"># We organize the path by length in an array using 2 cells per path.
</pre><p>
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.
</p>
<p>
Other comments :
</p>
<ul><li>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 <code>:-P</code> The integers you need are -- in the worst case -- of order <code>n^2</code>, 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 <code>O_o</code> Plus the code would be muuuuuuuuch easier to read without that <code>:-P</code>
</li><li>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 <code>n!</code> 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.
</li><li>elimination_bucket : hmmm... Well, this method is written so that it is able to deal with code that.... it does not contain :-P
<pre class="wiki"> - 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.
</pre>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 <code>max_diameter</code> is completely useless, ...
</li><li>Oh, and you can use <code>sage_calloc</code> to allocate and set to zero at the same time.
</li></ul><p>
I attach a small patch that deals with unimportant things.
</p>
<p>
Nathann
</p>
TicketncohenMon, 17 Dec 2012 17:34:46 GMT
https://trac.sagemath.org/ticket/13808#comment:8
https://trac.sagemath.org/ticket/13808#comment:8
<p>
Oh, and I forgot something ! You define in your graph a tmp variable which is totally useless. You can remove it, and define it only inside of <code>_invert_cells</code> !
</p>
<p>
Nathann
</p>
TicketdcoudertMon, 17 Dec 2012 19:54:06 GMT
https://trac.sagemath.org/ticket/13808#comment:9
https://trac.sagemath.org/ticket/13808#comment:9
<p>
Hello,
</p>
<ol><li>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.
</li><li>I agree with proposed improvement of documentation
</li><li>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). 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.
</li><li>Number of paths: you are right. The proposed modification clarifies the doc.
</li><li>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).
</li><li>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?
</li><li>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.
</li><li>the a.patch is OK.
</li></ol><p>
D.
</p>
TicketncohenTue, 18 Dec 2012 09:55:04 GMT
https://trac.sagemath.org/ticket/13808#comment:10
https://trac.sagemath.org/ticket/13808#comment:10
<p>
Hellooooooooooooooooooo !!
</p>
<p>
A better day begins, with music. Music solves everything <code>:-P</code>
</p>
<blockquote class="citation">
<ol><li>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.
</li></ol></blockquote>
<p>
Oh. C struct ? Yeah, they are free. Especially when their size is 2*sizeof(int) <code>:-P</code>
</p>
<blockquote class="citation">
<ol><li>I agree with proposed improvement of documentation
</li><li>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).
</li></ol></blockquote>
<p>
What ? <code>O_o</code>
Do you mean that in some situation regular int were not enough ? I really wonder where <code>O_O;;;</code>
</p>
<p>
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.
</p>
<p>
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 <code>2^16=65536</code>, and even less than <code>2^15=32768</code>. 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 <code>2^16-1</code> vertices. Then, you count pair of vertices, and this is not larger than <code>(2^16)^2 = 2^32</code>, 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.
</p>
<blockquote class="citation">
<ol><li>Number of paths: you are right. The proposed modification clarifies the doc.
</li><li>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).
</li></ol></blockquote>
<p>
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 <code>^^;</code> 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 ? <code>:-P</code>
</p>
<blockquote class="citation">
<ol><li>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?
</li></ol></blockquote>
<p>
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.
<a class="ext-link" href="http://linux.die.net/man/3/calloc"><span class="icon"></span>http://linux.die.net/man/3/calloc</a>
</p>
<blockquote class="citation">
<ol><li>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.
</li></ol></blockquote>
<p>
Here is how the function is writted right now :
</p>
<pre class="wiki">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
</pre><p>
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.
</p>
<p>
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.
</p>
<p>
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 ? <code>:-P</code>
</p>
<blockquote class="citation">
<ol><li>the a.patch is OK.
</li></ol></blockquote>
<p>
Nathann
</p>
TicketdcoudertTue, 18 Dec 2012 11:00:27 GMT
https://trac.sagemath.org/ticket/13808#comment:11
https://trac.sagemath.org/ticket/13808#comment:11
<blockquote class="citation">
<blockquote class="citation">
<ol><li>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).
</li></ol></blockquote>
<p>
What ? <code>O_o</code>
Do you mean that in some situation regular int were not enough ? I really wonder where <code>O_O;;;</code>
</p>
</blockquote>
<p>
On some computers, unsigned long int are on 32 bits. When you count the number of visited 4-tuples, you can exceed <code>2^32-1</code>. It happens when working on biconnected graphs with more than 20000 vertices (kind of graphs I'm currently considering).
</p>
<p>
For the rest of the code, I will (try to) simplify it asap.
</p>
<p>
D.
</p>
TicketncohenTue, 18 Dec 2012 11:01:56 GMT
https://trac.sagemath.org/ticket/13808#comment:12
https://trac.sagemath.org/ticket/13808#comment:12
<blockquote class="citation">
<p>
On some computers, unsigned long int are on 32 bits. When you count the number of visited 4-tuples, you can exceed <code>2^32-1</code>. It happens when working on biconnected graphs with more than 20000 vertices (kind of graphs I'm currently considering).
</p>
</blockquote>
<p>
Oh, right. <code>n^4</code> can go far beyond 32bits integers indeed !
</p>
<p>
Nathann
</p>
TicketdcoudertFri, 21 Dec 2012 00:12:48 GMTstatus, description changed; reviewer set
https://trac.sagemath.org/ticket/13808#comment:13
https://trac.sagemath.org/ticket/13808#comment:13
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Nathann Cohen</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/13808?action=diff&version=13">diff</a>)
</li>
</ul>
<p>
I have implemented all proposed changes:
</p>
<ul><li>use of a struct for pairs
</li><li>use of sage_calloc when appropriate
</li><li>use uint32_t instead of uint64_t when appropriate. These types are shorter to write/read. Also uint64_t is needed for distributions since number could potentially be huge (more theoretical than practical due to huge computation time)
</li><li>improve ordering for visiting pairs
</li><li>simplify pre-processing and corresponding data structure. It now only considers simplicial vertices.
</li></ul><p>
I have merged the <a class="missing attachment">a.patch</a> into the new version of the patch: <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/13808/trac_13808-v3.patch" title="Attachment 'trac_13808-v3.patch' in Ticket #13808">trac_13808-v3.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/13808/trac_13808-v3.patch" title="Download"></a>. The patch is much better now, the doc is nicer, and it is a bit faster.
</p>
TicketdcoudertFri, 21 Dec 2012 09:12:13 GMT
https://trac.sagemath.org/ticket/13808#comment:14
https://trac.sagemath.org/ticket/13808#comment:14
<p>
don't know why the patchbot applies v2+a.patch+v3. How to change this ?
</p>
TicketncohenFri, 21 Dec 2012 15:22:48 GMT
https://trac.sagemath.org/ticket/13808#comment:15
https://trac.sagemath.org/ticket/13808#comment:15
<p>
Apply trac_13808-v3.patch
</p>
TicketncohenFri, 21 Dec 2012 16:02:19 GMT
https://trac.sagemath.org/ticket/13808#comment:16
https://trac.sagemath.org/ticket/13808#comment:16
<p>
Helloooooo again !!
</p>
<p>
It took quiiiiiiiiite a while, but I think it's done ! Here is a small patch to attach on top of yours if you agree with it. One mistake (1->2), some comments, and memory checks Btw, if you find a way to make memory checks more compact, I'd be glad to learn it. Thought about it for a while, didn't find anything.
</p>
<p>
You can set this patch to positive review if everything is fine for you !
</p>
<p>
Nathann
</p>
TicketncohenFri, 21 Dec 2012 16:02:53 GMTattachment set
https://trac.sagemath.org/ticket/13808
https://trac.sagemath.org/ticket/13808
<ul>
<li><strong>attachment</strong>
set to <em>trac_13808-rev.patch</em>
</li>
</ul>
TicketdcoudertFri, 21 Dec 2012 20:14:39 GMTdescription changed
https://trac.sagemath.org/ticket/13808#comment:17
https://trac.sagemath.org/ticket/13808#comment:17
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13808?action=diff&version=17">diff</a>)
</li>
</ul>
<p>
Thanks for the revision patch. I did some more improvements in the rev2 patch to prevent others bugs. In particular, I found that the <code>c_distances_all_pairs</code> function returns NULL when the memory space is too small. I have added dedicated test, but may be we should patch the distance all pairs function.
</p>
<p>
Q: should we add a message to <a class="missing wiki">MemoryError?</a> like "Not enough memory to execute the function.". We cannot doctest this because this is machine dependent.
</p>
<p>
Let me know.
</p>
<p>
</p>
TicketncohenMon, 24 Dec 2012 13:27:36 GMTstatus changed
https://trac.sagemath.org/ticket/13808#comment:18
https://trac.sagemath.org/ticket/13808#comment:18
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
Helloooooooooo !!
</p>
<p>
Why isn't your <code>hyp==2</code> a <code>hyp >= 2</code> ? Once this is clear, you can set the ticket to <code>positive_review</code>. I hope that your next patches will be a tad smaller though <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketncohenMon, 24 Dec 2012 13:28:51 GMT
https://trac.sagemath.org/ticket/13808#comment:19
https://trac.sagemath.org/ticket/13808#comment:19
<p>
About <code>c_distances_all_pairs</code> : well, it's up to you actually. Exceptions could be nice too, as I do not expect this to cost much time where <code>c_distances_all_pairs</code> is called. But in another patch ! <code>;-)</code>
</p>
<p>
Nathann
</p>
TicketdcoudertFri, 28 Dec 2012 11:04:18 GMTattachment set
https://trac.sagemath.org/ticket/13808
https://trac.sagemath.org/ticket/13808
<ul>
<li><strong>attachment</strong>
set to <em>trac_13808-rev2.patch</em>
</li>
</ul>
TicketdcoudertFri, 28 Dec 2012 11:07:47 GMTstatus changed
https://trac.sagemath.org/ticket/13808#comment:20
https://trac.sagemath.org/ticket/13808#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
Hello Nathann,
</p>
<p>
I have replaced the hyp==2 with hyp>=2 and clarified the text.
</p>
<p>
Thanks for the review. The patch has been greatly improved.
</p>
<p>
David.
</p>
TicketdcoudertFri, 28 Dec 2012 11:13:17 GMTstatus changed
https://trac.sagemath.org/ticket/13808#comment:21
https://trac.sagemath.org/ticket/13808#comment:21
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
I set the patch to positive_review as you have suggested.
</p>
<p>
Thanks.
</p>
TicketjdemeyerTue, 01 Jan 2013 16:58:28 GMTstatus changed; dependencies set
https://trac.sagemath.org/ticket/13808#comment:22
https://trac.sagemath.org/ticket/13808#comment:22
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
<li><strong>dependencies</strong>
set to <em>#13821</em>
</li>
</ul>
<p>
This needs to be fixed w.r.t. <a class="closed ticket" href="https://trac.sagemath.org/ticket/13821" title="enhancement: Change sage.combinat.combinat.combinations() to use Combinations (closed: fixed)">#13821</a>:
</p>
<pre class="wiki">sage -t -force_lib devel/sage/sage/graphs/hyperbolicity.pyx
**********************************************************************
File "/release/merger/sage-5.6.beta3/devel/sage-main/sage/graphs/hyperbolicity.pyx", line 351:
sage: elimination_ordering_of_simplicial_vertices(G)
Expected:
[2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 11]
Got:
doctest:1: DeprecationWarning: Use Combinations(mset,k) instead.
See http://trac.sagemath.org/13821 for details.
[2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 11]
**********************************************************************
File "/release/merger/sage-5.6.beta3/devel/sage-main/sage/graphs/hyperbolicity.pyx", line 806:
sage: for i in xrange(10): # long test
G = graphs.RandomBarabasiAlbert(Integer(100),Integer(2))
d1,_,_ = hyperbolicity(G,algorithm='basic')
d2,_,_ = hyperbolicity(G,algorithm='cuts')
d3,_,_ = hyperbolicity(G,algorithm='cuts+')
l3,_,u3 = hyperbolicity(G,approximation_factor=Integer(2))
if d1!=d2 or d1!=d3 or l3>d1 or u3<d1:
print "That's not good!"
Expected nothing
Got:
doctest:5: DeprecationWarning: Use Combinations(mset,k) instead.
See http://trac.sagemath.org/13821 for details.
**********************************************************************
</pre>
TicketjdemeyerWed, 02 Jan 2013 10:54:21 GMT
https://trac.sagemath.org/ticket/13808#comment:23
https://trac.sagemath.org/ticket/13808#comment:23
<p>
Also,
</p>
<pre class="wiki"># long test
</pre><p>
should be
</p>
<pre class="wiki"># long time
</pre>
TicketdcoudertWed, 02 Jan 2013 23:22:00 GMTattachment set
https://trac.sagemath.org/ticket/13808
https://trac.sagemath.org/ticket/13808
<ul>
<li><strong>attachment</strong>
set to <em>trac_13808-combinations.patch</em>
</li>
</ul>
TicketdcoudertWed, 02 Jan 2013 23:24:47 GMTstatus, description changed
https://trac.sagemath.org/ticket/13808#comment:24
https://trac.sagemath.org/ticket/13808#comment:24
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/13808?action=diff&version=24">diff</a>)
</li>
</ul>
<p>
I was not aware of this patch.
</p>
<p>
The dependency is fixed, as well as the #long time. I hope it is OK now.
</p>
<hr />
<p>
patchbot apply trac_13808-v3.patch trac_13808-rev.patch trac_13808-rev2.patch trac_13808-combinations.patch
</p>
TicketdcoudertThu, 03 Jan 2013 10:45:34 GMTattachment set
https://trac.sagemath.org/ticket/13808
https://trac.sagemath.org/ticket/13808
<ul>
<li><strong>attachment</strong>
set to <em>trac_13808-v3.patch</em>
</li>
</ul>
<p>
new combined version
</p>
TicketdcoudertThu, 03 Jan 2013 10:48:00 GMTattachment set
https://trac.sagemath.org/ticket/13808
https://trac.sagemath.org/ticket/13808
<ul>
<li><strong>attachment</strong>
set to <em>trac_13808-revb.patch</em>
</li>
</ul>
TicketdcoudertThu, 03 Jan 2013 10:49:41 GMTdescription changed
https://trac.sagemath.org/ticket/13808#comment:25
https://trac.sagemath.org/ticket/13808#comment:25
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13808?action=diff&version=25">diff</a>)
</li>
</ul>
<p>
Minor edit to get rid of trailing white space. Should be better for the patchbot.
</p>
<hr />
<p>
patchbot apply trac_13808-v3.patch trac_13808-revb.patch trac_13808-rev2.patch trac_13808-combinations.patch
</p>
TicketncohenFri, 04 Jan 2013 09:59:58 GMTstatus changed
https://trac.sagemath.org/ticket/13808#comment:26
https://trac.sagemath.org/ticket/13808#comment:26
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Passed all long tests modulo the doctest problem in beta2. Good to go again !
</p>
<p>
Nathann
</p>
TicketdcoudertFri, 04 Jan 2013 10:14:59 GMT
https://trac.sagemath.org/ticket/13808#comment:27
https://trac.sagemath.org/ticket/13808#comment:27
<p>
Thanks (again) !
</p>
TicketjdemeyerSat, 12 Jan 2013 08:52:16 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/13808#comment:28
https://trac.sagemath.org/ticket/13808#comment:28
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.6.rc0</em>
</li>
</ul>
Ticket