Sage: Ticket #8404: Computing a H-minor
https://trac.sagemath.org/ticket/8404
<p>
This patch is a linear program to compute a H minor of a graph... I hope you will like it ! :-)
</p>
<p>
We say that a graph <code>G</code> has a <code>H</code>-minor (or that it has a graph isomorphic to <code>H</code> as a minor), if for all <code>h\in H</code>, there exist disjoint sets <code>S_h \subseteq V(G)</code> such that once the vertices of each <code>S_h</code> have been merged to create a new graph <code>G'</code>, this new graph contains <code>H</code> as a subgraph.
</p>
<p>
For more information of minor theory, see <a class="ext-link" href="http://en.wikipedia.org/wiki/Minor_(graph_theory"><span class="icon"></span>http://en.wikipedia.org/wiki/Minor_(graph_theory</a>)
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/8404
Trac 1.1.6ncohenSun, 28 Feb 2010 18:46:46 GMTstatus changed
https://trac.sagemath.org/ticket/8404#comment:1
https://trac.sagemath.org/ticket/8404#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketjasonMon, 01 Mar 2010 12:19:13 GMT
https://trac.sagemath.org/ticket/8404#comment:2
https://trac.sagemath.org/ticket/8404#comment:2
<p>
This is awesome to have something like this in Sage. I noticed in the patch a misspelling: "exaclty" -> "exactly".
</p>
<p>
Do you have a reference for the translation of the minor problem into a linear programming problem? Can you put that into the docstring?
</p>
TicketncohenMon, 01 Mar 2010 15:32:26 GMT
https://trac.sagemath.org/ticket/8404#comment:3
https://trac.sagemath.org/ticket/8404#comment:3
<p>
No, that's mine. Or at least I did not read it anywhere, as I can not claim no one thought about it before. I recently talked with someone who should have known it if it existed, and who did not.
</p>
<p>
Note that it can be very slow, though, even if there is no alternative that I know of.
</p>
<p>
I will fix the typo in a minute :-)
</p>
<p>
Nathann
</p>
TicketjasonMon, 01 Mar 2010 16:08:29 GMT
https://trac.sagemath.org/ticket/8404#comment:4
https://trac.sagemath.org/ticket/8404#comment:4
<p>
Well, congratulations! I think it would be interesting to see a short writeup of it, maybe posted on arxiv.org? Are there any other linear program graph functions that aren't in the literature that you've already incorporated into Sage? It would make an interesting "Survey of using linear programming to solve graph problems".
</p>
TicketncohenMon, 01 Mar 2010 16:18:44 GMT
https://trac.sagemath.org/ticket/8404#comment:5
https://trac.sagemath.org/ticket/8404#comment:5
<p>
Not really... The only way for me to use LP is through Sage, so most of what I write ends up as a patch. I recently sent a patch for two variations of graph coloring that interest me <a class="closed ticket" href="https://trac.sagemath.org/ticket/8405" title="enhancement: Linear Arboricity, Acyclic edge coloring (closed: fixed)">#8405</a>.
</p>
<p>
Actually, my recent patches of LP formulations :
</p>
<ul><li><a class="closed ticket" href="https://trac.sagemath.org/ticket/2203" title="enhancement: Add a traveling salesman problem solver (closed: fixed)">#2203</a> Traveling Salesman Problem
</li><li><a class="closed ticket" href="https://trac.sagemath.org/ticket/7476" title="enhancement: Edge-disjoint spanning trees (closed: fixed)">#7476</a> Edge-disjoint spanning trees
</li><li><a class="closed ticket" href="https://trac.sagemath.org/ticket/7529" title="enhancement: Maximum Average Degree of a graph (closed: fixed)">#7529</a> Maximum average Degree
</li><li><a class="closed ticket" href="https://trac.sagemath.org/ticket/8403" title="enhancement: Steiner Tree (closed: fixed)">#8403</a> Steiner Tree
</li><li><a class="closed ticket" href="https://trac.sagemath.org/ticket/8405" title="enhancement: Linear Arboricity, Acyclic edge coloring (closed: fixed)">#8405</a> Linear arboricity / Acyclic edge coloring
</li><li>This very patch
</li></ul><p>
All have the same thing in common : there is an easy way that I ignored until very recently to write "acyclicity" without using column generation. It may be a bit slower, but I do not have to write column generation to define them, at least :p
</p>
<p>
Knowing how to say "acyclicity" enables one to say "connectedness". And once you know how to say "connectedness", you can say Minor, Steiner Tree, TSP, etc :-)
</p>
<p>
What would you like to find in such a document ? A list of formulations, plus explanations ?
</p>
<p>
Nathann
</p>
TicketjasonMon, 01 Mar 2010 16:40:58 GMT
https://trac.sagemath.org/ticket/8404#comment:6
https://trac.sagemath.org/ticket/8404#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8404#comment:5" title="Comment 5">ncohen</a>:
</p>
<blockquote class="citation">
<p>
What would you like to find in such a document ? A list of formulations, plus explanations ?
</p>
</blockquote>
<p>
Yes, I think that would be great. It's also a way for your Sage work to get more traditional credit in academics, especially if you are formulating things that aren't in a standard reference and might be less than straightforward. And thirdly, it's a way for people like me, who have a minimal understanding of linear programming, to check your code :).
</p>
TicketwdjMon, 01 Mar 2010 21:39:17 GMT
https://trac.sagemath.org/ticket/8404#comment:7
https://trac.sagemath.org/ticket/8404#comment:7
<p>
Nathann: Please do write up the paper Jason suggests. I would also be very interested.
</p>
TicketncohenThu, 04 Mar 2010 14:31:27 GMTowner changed
https://trac.sagemath.org/ticket/8404#comment:8
https://trac.sagemath.org/ticket/8404#comment:8
<ul>
<li><strong>owner</strong>
changed from <em>rlm</em> to <em>ncohen</em>
</li>
</ul>
<p>
Here it is !
</p>
<p>
<a class="ext-link" href="http://www-sop.inria.fr/members/Nathann.Cohen/LP_formulations.pdf"><span class="icon"></span>http://www-sop.inria.fr/members/Nathann.Cohen/LP_formulations.pdf</a>
</p>
<p>
Nathann
</p>
TicketncohenThu, 04 Mar 2010 14:31:44 GMTowner changed
https://trac.sagemath.org/ticket/8404#comment:9
https://trac.sagemath.org/ticket/8404#comment:9
<ul>
<li><strong>owner</strong>
changed from <em>ncohen</em> to <em>rlm</em>
</li>
</ul>
TicketdimpaseFri, 05 Mar 2010 04:16:44 GMTstatus changed
https://trac.sagemath.org/ticket/8404#comment:10
https://trac.sagemath.org/ticket/8404#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8404#comment:7" title="Comment 7">wdj</a>:
</p>
<blockquote class="citation">
<p>
Nathann: Please do write up the paper Jason suggests. I would also be very interested.
</p>
</blockquote>
<p>
Nathann, you seem to be systematically writing LP where it should be ILP, or MILP, right?
Please fix this.
</p>
<p>
As well, you need to include meaningful examples: e.g. showing how to use your code to show that some well-known graph (say, Petersen) is not planar by finding a Kuratowski minor. It's not obvious that your code can handle this in reasonable time (I have had my share of using ILP for seemingly small problems, with very limited success).
And, apart from planarity (planarity is easy algorithmically, so it has only theoretical interest here), few other real problems involving graph minors.
And if the code cannot do anything useful, it should not be included in Sage (not in the standard or optional part, anyway)
</p>
<p>
I therefore change the status to "needs work"... (I wish we had anonymous reviewing, like in journals :-))
</p>
<p>
Dmitrii
</p>
TicketjasonFri, 05 Mar 2010 11:26:09 GMT
https://trac.sagemath.org/ticket/8404#comment:11
https://trac.sagemath.org/ticket/8404#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8404#comment:10" title="Comment 10">dimpase</a>:
</p>
<blockquote class="citation">
<p>
And, apart from planarity (planarity is easy algorithmically, so it has only theoretical interest here), few other real problems involving graph minors.
And if the code cannot do anything useful, it should not be included in Sage (not in the standard or optional part, anyway)
</p>
</blockquote>
<p>
*I'm* interested in it. In some of my research in graph parameters (minimum rank of graphs), there are some nice bounds written in terms of the minors of a graph. Even if it only works for graphs up to 20 vertices, it would be interesting to me and others working in this area (minimum rank of graphs) so that we could quickly compute small examples.
</p>
TicketncohenFri, 05 Mar 2010 11:58:59 GMTstatus changed
https://trac.sagemath.org/ticket/8404#comment:12
https://trac.sagemath.org/ticket/8404#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Hello !!!
</p>
<p>
Here is a new version of the patch with the examples you requested.
</p>
<p>
I mever tried to make a mystery that this method is slow. It was one on my first comments about this patch. The thing is that there is no alternative that I know of. Minor theory is not what I should work on, but it is an interesting thing and I tried to find practical algorithms to solve it, and failed most of the time. I sent messages to people who claimed to have one and received no answer... And as for every LP algorithm written in Sage, I consider this one as a quick and lazy way to have some feature available, and the function as bound to be rewritten as soon as someone will want to spend time on it.
</p>
<p>
I would like very much to send a patch soon to be able to compute the treewidth of a graph, and even heuristics for it.. I would have to ask this code from a researcher who may be kind enough to share it, but those would still remain very slow algorithms. I can not stand the very idea of a heuristic as a mathematician, but sometimes you just have no other alternative...
</p>
<p>
As for anonymous reviewing, research has still to learn from Free Software that we are working together, not competing, and most of the time just doing the best we can.
</p>
<p>
Nathann
</p>
TicketncohenFri, 05 Mar 2010 12:03:22 GMT
https://trac.sagemath.org/ticket/8404#comment:13
https://trac.sagemath.org/ticket/8404#comment:13
<p>
Oh, and I set the test of K5 and K33 minors in Petersen Graph as both optional and long... It takes on my computer something like 4 seconds for K5 and 2 for K33 with Cbc.. With a bit of luck it will be faster soon enough : the next package for Cbc can handle multithreading and Cplex seems ti be giving free licenses to researchers and students.
</p>
<p>
( <a class="closed ticket" href="https://trac.sagemath.org/ticket/8171" title="enhancement: New Cbc spkg with Cplex support (closed: fixed)">#8171</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/8172" title="enhancement: Support for CPLEX (closed: fixed)">#8172</a> are still waiting for review, btw :-) )
</p>
<p>
Nathann
</p>
TicketncohenSat, 06 Mar 2010 10:01:57 GMT
https://trac.sagemath.org/ticket/8404#comment:14
https://trac.sagemath.org/ticket/8404#comment:14
<p>
By the way... I just retried to solve this problem using CPLEX instead of Coin.. Result :
</p>
<pre class="wiki">sage: time graphs.PetersenGraph().minor(graphs.CompleteGraph(5))
Wall time: 0.22 s
{0: [3, 8], 1: [5, 7], 2: [1, 2], 3: [0, 4], 4: [6, 9]}
</pre><pre class="wiki">sage: time graphs.PetersenGraph().minor(graphs.CompleteBipartiteGraph(3,3))
Wall time: 0.18 s
{0: [4, 9], 1: [5], 2: [1, 2], 3: [3, 8], 4: [0], 5: [7]}
</pre><p>
So it seems it is not that bad after all :-)
</p>
<p>
Nathann
</p>
TicketdimpaseSat, 06 Mar 2010 11:34:02 GMT
https://trac.sagemath.org/ticket/8404#comment:15
https://trac.sagemath.org/ticket/8404#comment:15
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8404#comment:14" title="Comment 14">ncohen</a>:
</p>
<blockquote class="citation">
<p>
By the way... I just retried to solve this problem using CPLEX instead of Coin.. Result :
</p>
<pre class="wiki">sage: time graphs.PetersenGraph().minor(graphs.CompleteGraph(5))
Wall time: 0.22 s
{0: [3, 8], 1: [5, 7], 2: [1, 2], 3: [0, 4], 4: [6, 9]}
</pre><pre class="wiki">sage: time graphs.PetersenGraph().minor(graphs.CompleteBipartiteGraph(3,3))
Wall time: 0.18 s
{0: [4, 9], 1: [5], 2: [1, 2], 3: [3, 8], 4: [0], 5: [7]}
</pre><p>
So it seems it is not that bad after all :-)
</p>
</blockquote>
<p>
I wonder how does it scale when the number of vertices of G grows.
</p>
<p>
Regarding CPLEX I would not be that optimistic - they did not say whether
they give that free licences for unlimited time.
</p>
<blockquote class="citation">
<p>
Nathann
</p>
</blockquote>
TicketncohenSat, 06 Mar 2010 11:43:46 GMT
https://trac.sagemath.org/ticket/8404#comment:16
https://trac.sagemath.org/ticket/8404#comment:16
<p>
I expect it not to scale ;-)
</p>
<p>
Nathann
</p>
TicketdimpaseSat, 06 Mar 2010 11:50:24 GMT
https://trac.sagemath.org/ticket/8404#comment:17
https://trac.sagemath.org/ticket/8404#comment:17
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8404#comment:16" title="Comment 16">ncohen</a>:
</p>
<blockquote class="citation">
<p>
I expect it not to scale ;-)
</p>
</blockquote>
<p>
yeah - can you try some 20-25 vertex examples?
</p>
<p>
(by the way, "no K_4-minor" is equivalent to "treewidth at most 2", so you can write
another short function to test fro just this...)
</p>
TicketncohenSat, 06 Mar 2010 12:17:47 GMT
https://trac.sagemath.org/ticket/8404#comment:18
https://trac.sagemath.org/ticket/8404#comment:18
<blockquote class="citation">
<p>
yeah - can you try some 20-25 vertex examples?
</p>
<p>
(by the way, "no K_4-minor" is equivalent to "treewidth at most 2", so you can write
another short function to test fro just this...)
</p>
</blockquote>
<p>
I would be glad to review your patch if you were to write one :-D
</p>
<p>
(Sorry, but I really do not have much time available these days....)
</p>
<p>
Nathann
</p>
TicketdimpaseSat, 06 Mar 2010 12:24:33 GMT
https://trac.sagemath.org/ticket/8404#comment:19
https://trac.sagemath.org/ticket/8404#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8404#comment:18" title="Comment 18">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
yeah - can you try some 20-25 vertex examples?
</p>
<p>
(by the way, "no K_4-minor" is equivalent to "treewidth at most 2", so you can write
another short function to test fro just this...)
</p>
</blockquote>
<p>
I would be glad to review your patch if you were to write one :-D
</p>
<p>
(Sorry, but I really do not have much time available these days....)
</p>
</blockquote>
<p>
nobody has any time :)
</p>
<p>
well, you still should change "Linear Programming" to "(Mixed) Integer Linear Programming", at least
in your patch and in other docs.
</p>
<blockquote class="citation">
<p>
Nathann
</p>
</blockquote>
TicketncohenMon, 08 Mar 2010 18:00:55 GMT
https://trac.sagemath.org/ticket/8404#comment:20
https://trac.sagemath.org/ticket/8404#comment:20
<p>
now with *Mixed Integer* linear program
</p>
TicketdimpaseTue, 09 Mar 2010 02:52:24 GMTstatus changed
https://trac.sagemath.org/ticket/8404#comment:21
https://trac.sagemath.org/ticket/8404#comment:21
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8404#comment:20" title="Comment 20">ncohen</a>:
</p>
<blockquote class="citation">
<p>
now with *Mixed Integer* linear program
</p>
</blockquote>
<p>
OK, but please also fix
</p>
<pre class="wiki">ALGORITHM
Mixed Integer Linear Program
</pre><p>
it must be "Programming", not "Program" here.
</p>
<p>
I also notice similar misuses of "Linear <a class="missing wiki">Program/Programming?</a>" (instead of (M)ILP) on
<a href="http://www.sagemath.org/doc/reference/sage/numerical/mip.html">http://www.sagemath.org/doc/reference/sage/numerical/mip.html</a>
</p>
<p>
and another tutorial-like thing you wrote
(in the latter you also forget to mention that max. matching problem in a graph
can be solved in polynomial time, using LP (or otherwise), so that the MILP formulation is far from the best possible)
</p>
<p>
Please fix these too some time soon, please...
</p>
TicketncohenTue, 09 Mar 2010 10:04:14 GMT
https://trac.sagemath.org/ticket/8404#comment:22
https://trac.sagemath.org/ticket/8404#comment:22
<p>
This patch has been updated to program*ming*.
</p>
<p>
I you feel anything else in Sage needs to be fixed, please create the corresponding ticket and -- if possible -- write a patch for it.
</p>
<p>
You have set this ticket to "positive review". Have you actually tested it, docstring and documentation ?
</p>
<p>
Nathann
</p>
TicketdimpaseTue, 09 Mar 2010 11:14:48 GMT
https://trac.sagemath.org/ticket/8404#comment:23
https://trac.sagemath.org/ticket/8404#comment:23
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8404#comment:22" title="Comment 22">ncohen</a>:
</p>
<blockquote class="citation">
<p>
This patch has been updated to program*ming*.
</p>
<p>
I you feel anything else in Sage needs to be fixed, please create the corresponding ticket and -- if possible -- write a patch for it.
</p>
</blockquote>
<p>
well, I do not know how to patch that writeup on linear programming --- Minh
does not seem to know this, either.
</p>
<blockquote class="citation">
<p>
You have set this ticket to "positive review". Have you actually tested it, docstring and documentation ?
</p>
</blockquote>
<p>
I applied the patch, to sage-4.3.3 on boxen (so this is a 64-bit intel linux)
and did sage -t -optional on graphs/graph.py
and it all passed (I also did some minor computations at sage prompt, just to make sure there is no screwup anywhere :))
</p>
<p>
I do not know how to *test* documentation, never heard of --- is there a way?
</p>
<p>
Oh, by the way, there is still a fix needed:
</p>
<p>
you should add # optional on the line 1951 of the file, otherwise
sage -t (no -optional) will complain about undefined gg.
</p>
<p>
Please fix this, otherwise I'll have to revert to "needs work" :)
(I wish I had such an efficient means to make my students work hard :))
</p>
<p>
PS. I do not seem to be able to find out which MILP solver I am actually using --- is there a way to find this out without uninstalling several optional packages?
</p>
<p>
Dima
</p>
TicketncohenTue, 09 Mar 2010 11:43:37 GMT
https://trac.sagemath.org/ticket/8404#comment:24
https://trac.sagemath.org/ticket/8404#comment:24
<p>
The difference being that I am not your student, nor do I have any intention of standing your rudeness and the way you give me orders for very long.
</p>
<p>
I write these patches, even though they require *a lot* of time, because I think people may be interested in them. If you are not (you had the kindness to mention earlier that it should be thrown away as useless), I do not need you here.
</p>
<p>
This is the last time I edit the patch, I can not afford to update it each time you change your mind about what needs to be done.
</p>
<p>
Nathann
</p>
TicketncohenTue, 09 Mar 2010 11:44:59 GMTattachment set
https://trac.sagemath.org/ticket/8404
https://trac.sagemath.org/ticket/8404
<ul>
<li><strong>attachment</strong>
set to <em>trac_8404.patch</em>
</li>
</ul>
TicketdimpaseTue, 09 Mar 2010 12:03:52 GMT
https://trac.sagemath.org/ticket/8404#comment:25
https://trac.sagemath.org/ticket/8404#comment:25
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8404#comment:24" title="Comment 24">ncohen</a>:
</p>
<blockquote class="citation">
<p>
The difference being that I am not your student, nor do I have any intention of standing your rudeness and the way you give me orders for very long.
</p>
</blockquote>
<p>
Please point me out to a place where I was rude to you.
I apologize in advance, if you like, anyway.
</p>
<p>
By the way, I am considerably older than you, so please also forgive me slipping
into patronizing.
</p>
<blockquote class="citation">
<p>
I write these patches, even though they require *a lot* of time, because I think people may be interested in them. If you are not (you had the kindness to mention earlier that it should be thrown away as useless), I do not need you here.
</p>
</blockquote>
<p>
I just want your, and others, patches to be useful to people, this is all.
I never said that your work should be thrown away, regardless. I said it should be thrown away if it does not work as advertised, and I asked you to provide few more examples to demonstrate the usefulness of them. This is downright normal reviewing process, believe me.
</p>
<p>
In fact, I am very patient with you. Many would have said "meshugene genz, meshugene grivn", and stopped dealing with you and your patches all together.
</p>
<p>
And this is exactly the point when I wondered aloud whether it would be better
to have anonymous reviewers. :-)
</p>
<blockquote class="citation">
<p>
This is the last time I edit the patch, I can not afford to update it each time you change your mind about what needs to be done.
</p>
</blockquote>
<p>
It's not that I change my mind, that is I see a way to improve it. It's normal process of work. I am only human after all.
</p>
<p>
Dima
</p>
<blockquote class="citation">
<p>
Nathann
</p>
</blockquote>
TicketncohenSat, 13 Mar 2010 08:06:44 GMT
https://trac.sagemath.org/ticket/8404#comment:26
https://trac.sagemath.org/ticket/8404#comment:26
<p>
Where the conversation moved :
</p>
<p>
<a class="ext-link" href="http://groups.google.com/group/sage-devel/browse_thread/thread/cd4e971043773fd3"><span class="icon"></span>http://groups.google.com/group/sage-devel/browse_thread/thread/cd4e971043773fd3</a>
</p>
<p>
Nathann
</p>
TicketncohenTue, 16 Mar 2010 02:06:33 GMT
https://trac.sagemath.org/ticket/8404#comment:27
https://trac.sagemath.org/ticket/8404#comment:27
<p>
With the new (and free) cplex, it takes 120 seconds to prove there is no K5 in a 4x4 grid. Finding a K4 is instantaneous.
</p>
<p>
Nathann
</p>
TicketjhpalmieriThu, 15 Apr 2010 23:45:51 GMTstatus changed; reviewer, resolution, merged, author set
https://trac.sagemath.org/ticket/8404#comment:28
https://trac.sagemath.org/ticket/8404#comment:28
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>reviewer</strong>
set to <em>Dmitrii Pasechnik</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.4.alpha0</em>
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
Merged "trac_8404.patch" into 4.4.alpha0.
</p>
Ticket