Sage: Ticket #15181: Treewidth (lazy implementation)
https://trac.sagemath.org/ticket/15181
<p>
This code is a veeeery lazy implementation of a very lazy algorithm to compute the treewidth of a graph. It can be greatly improved in at least two places.
</p>
<p>
If it is to be improved later, this implementation will probably remain useful anyway, as we try to always keep many of them alive, just to check whether they all return sound results. Hence it's not so bad if it is a bit wasteful <code>:-P</code>
</p>
<p>
And well. It's great to have this, too <code>:-P</code>
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/15181
Trac 1.1.6ncohenMon, 09 Sep 2013 12:09:12 GMTstatus, component changed; branch set
https://trac.sagemath.org/ticket/15181#comment:1
https://trac.sagemath.org/ticket/15181#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>component</strong>
changed from <em>PLEASE CHANGE</em> to <em>graph theory</em>
</li>
<li><strong>branch</strong>
set to <em>u/ncohen/15181</em>
</li>
</ul>
TicketdcoudertMon, 09 Sep 2013 13:10:57 GMT
https://trac.sagemath.org/ticket/15181#comment:2
https://trac.sagemath.org/ticket/15181#comment:2
<p>
Hello,
</p>
<p>
Since I have not yet started to use git (yes, I'm lazy too), it will take some time before I will be able to review this patch.
</p>
<p>
However, I have a first remark: you should not add the function to graph.py, but to some treewidth.py or treewidth.pyx file into the <code>graph_decompositions</code> directory. This is just to gather methods.
</p>
<p>
David.
</p>
TicketncohenMon, 09 Sep 2013 18:55:53 GMT
https://trac.sagemath.org/ticket/15181#comment:3
https://trac.sagemath.org/ticket/15181#comment:3
<p>
I can't really, for I define a function inside of the main function -- you can't do that in Cython -- and it would behave differently with respect to caching if I moved the function outside.
</p>
<p>
Plus we're not there yet... If there was a lot of doc to write it would be worth creating a module for only one function, but it isn't deserved here <code>;-)</code>
</p>
<p>
Nathann
</p>
TicketgitTue, 10 Sep 2013 09:24:43 GMTcommit set
https://trac.sagemath.org/ticket/15181#comment:4
https://trac.sagemath.org/ticket/15181#comment:4
<ul>
<li><strong>commit</strong>
set to <em>fad9254d311c815f25b80ce6103d1f7c916683da</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td>[changeset:fad9254]</td><td>Adds Graph.treewidth()
</td></tr></table>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/15181#comment:5
https://trac.sagemath.org/ticket/15181#comment:5
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/15181#comment:6
https://trac.sagemath.org/ticket/15181#comment:6
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
TicketdcoudertSat, 02 Aug 2014 10:04:58 GMT
https://trac.sagemath.org/ticket/15181#comment:7
https://trac.sagemath.org/ticket/15181#comment:7
<p>
Hello,
</p>
<p>
After a really long time, I finally have some time to review patchs.
</p>
<p>
I have successfully rebased this patch with current develop version (6.3.beta8), compiled and executed the code. I have not yet tried to build the documentation.
</p>
<p>
I have a few remarks:
</p>
<ol><li>The description of outputs is incomplete. A call to <code>G.treewidth()</code> returns the treewidth.
</li><li>You should add examples/tests such as:
<pre class="wiki">sage: graphs.PetersenGraph().treewidth(k=2)
False
sage: graphs.PetersenGraph().treewidth(k=6)
True
sage: graphs.Grid2DGraph(2,5).treewidth()
2
sage: graphs.Grid2DGraph(3,5).treewidth()
3
sage: graphs.PetersenGraph().treewidth(certificate=True).is_tree()
True
sage: graphs.PetersenGraph().treewidth(k=3,certificate=True)
False
sage: graphs.PetersenGraph().treewidth(k=4,certificate=True)
Graph on 7 vertices
</pre></li></ol><ol start="3"><li>It could be useful to add simple tests such as <code>if G.is_tree(): return 1</code> or <code>if G.is_clique(): return G.order()-1</code>.
</li></ol><ol start="4"><li>How can I double check the results?? The results are correct for all the graphs I have tried and for which I know the treewidth. This could of course be done later, e.g., when a tree_decomposition module will be created with alternative methods.
</li></ol><ol start="5"><li>Typos:
</li></ol><ul><li>tree-decompostion itself -> tree-decomposition itself
</li></ul>
TicketncohenSat, 02 Aug 2014 10:21:17 GMT
https://trac.sagemath.org/ticket/15181#comment:8
https://trac.sagemath.org/ticket/15181#comment:8
<p>
Yooooooooooo !!
</p>
<blockquote class="citation">
<p>
After a really long time, I finally have some time to review patchs.
</p>
</blockquote>
<p>
Wow ! I am glad to see something happen on this ticket. I even forgot it was in <code>needs_review</code>... <code>:-P</code>
</p>
<blockquote class="citation">
<p>
I have a few remarks:
</p>
<ol><li>The description of outputs is incomplete. A call to <code>G.treewidth()</code> returns the treewidth.
</li></ol></blockquote>
<p>
Right. Fixed.
</p>
<blockquote class="citation">
<ol start="2"><li>You should add examples/tests such as:
</li></ol></blockquote>
<p>
Done.
</p>
<blockquote class="citation">
<ol start="3"><li>It could be useful to add simple tests such as <code>if G.is_tree(): return 1</code> or <code>if G.is_clique(): return G.order()-1</code>.
</li></ol></blockquote>
<p>
This I did not do for two reasons:
</p>
<p>
1) In order to deal with a specific kind of input graph you do not only need to know the treewidth but also to input a decomposition directly in the code, in case the user asks for the treedecomposition itself. It is not complicated to do in those cases indeed, but it means adding a lot of lines for easy cases. I don't mind particularly, but it makes it less appealing, and there is also 2)
</p>
<p>
2) Somehow those two cases are partially handled already, as when <code>k=None</code> the implementation uses the max clique as a lower bound on the treewidth. So its first guess on the treewidth of these two instances is already right, and it will not waste so much time on this input.
</p>
<p>
Tell me what you think !
</p>
<blockquote class="citation">
<ol start="4"><li>How can I double check the results?? The results are correct for all the graphs I have tried and for which I know the treewidth. This could of course be done later, e.g., when a tree_decomposition module will be created with alternative methods.
</li></ol></blockquote>
<p>
Ahahahah. Well, yes, I guess that the only way to check the output for harder instances is to read the code 1000 times, and to try to add more implementations. There is so much litterature about treewidth problem that we must have several algorithms to compute it !
</p>
<blockquote class="citation">
<ul><li>tree-decompostion itself -> tree-decomposition itself
</li></ul></blockquote>
<p>
Done.
</p>
<p>
Thanks for your work on that !
</p>
<p>
Nathann
</p>
TicketgitSat, 02 Aug 2014 10:21:37 GMTcommit changed
https://trac.sagemath.org/ticket/15181#comment:9
https://trac.sagemath.org/ticket/15181#comment:9
<ul>
<li><strong>commit</strong>
changed from <em>fad9254d311c815f25b80ce6103d1f7c916683da</em> to <em>06277e4d185a8f1c8de0e62d3f785eb6e15aca3a</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=02def56b8c55c82ad54fb6e47dbfd92b31e45328"><span class="icon"></span>02def56</a></td><td><code>trac #15181: Merged with 6.3.beta8</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=06277e4d185a8f1c8de0e62d3f785eb6e15aca3a"><span class="icon"></span>06277e4</a></td><td><code>trac #15181: Reviewer's remarks</code>
</td></tr></table>
TicketdcoudertSat, 02 Aug 2014 11:07:37 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/15181#comment:10
https://trac.sagemath.org/ticket/15181#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>David Coudert</em>
</li>
</ul>
<p>
I agree that the code is cleaner that way. Adding special tricks could be done later. This implementation will serve as a reference for future additions.
</p>
<p>
I don't have additional comments. The patch is working correctly, the documentation is OK, we have several tests, etc. So I give positive review ;-)
</p>
TicketncohenSat, 02 Aug 2014 11:08:10 GMT
https://trac.sagemath.org/ticket/15181#comment:11
https://trac.sagemath.org/ticket/15181#comment:11
<p>
Thaaaaaaaaaaaaaanks !
</p>
<p>
Nathann
</p>
TicketvbraunMon, 04 Aug 2014 13:46:33 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/15181#comment:12
https://trac.sagemath.org/ticket/15181#comment:12
<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>branch</strong>
changed from <em>u/ncohen/15181</em> to <em>06277e4d185a8f1c8de0e62d3f785eb6e15aca3a</em>
</li>
</ul>
Ticket