Opened 9 years ago

Closed 9 years ago

#8404 closed enhancement (fixed)

Computing a H-minor

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-4.4
Component: graph theory Keywords:
Cc: Merged in: sage-4.4.alpha0
Authors: Nathann Cohen Reviewers: Dmitrii Pasechnik
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

This patch is a linear program to compute a H minor of a graph... I hope you will like it ! :-)

We say that a graph G has a H-minor (or that it has a graph isomorphic to H as a minor), if for all h\in H, there exist disjoint sets S_h \subseteq V(G) such that once the vertices of each S_h have been merged to create a new graph G', this new graph contains H as a subgraph.

For more information of minor theory, see http://en.wikipedia.org/wiki/Minor_(graph_theory)

Nathann

Attachments (1)

trac_8404.patch (6.7 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (29)

comment:1 Changed 9 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by jason

This is awesome to have something like this in Sage. I noticed in the patch a misspelling: "exaclty" -> "exactly".

Do you have a reference for the translation of the minor problem into a linear programming problem? Can you put that into the docstring?

comment:3 Changed 9 years ago by ncohen

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.

Note that it can be very slow, though, even if there is no alternative that I know of.

I will fix the typo in a minute :-)

Nathann

comment:4 Changed 9 years ago by jason

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".

comment:5 follow-up: Changed 9 years ago by ncohen

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 #8405.

Actually, my recent patches of LP formulations :

  • #2203 Traveling Salesman Problem
  • #7476 Edge-disjoint spanning trees
  • #7529 Maximum average Degree
  • #8403 Steiner Tree
  • #8405 Linear arboricity / Acyclic edge coloring
  • This very patch

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

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 :-)

What would you like to find in such a document ? A list of formulations, plus explanations ?

Nathann

comment:6 in reply to: ↑ 5 Changed 9 years ago by jason

Replying to ncohen:

What would you like to find in such a document ? A list of formulations, plus explanations ?

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 :).

comment:7 follow-up: Changed 9 years ago by wdj

Nathann: Please do write up the paper Jason suggests. I would also be very interested.

comment:8 Changed 9 years ago by ncohen

  • Owner changed from rlm to ncohen

comment:9 Changed 9 years ago by ncohen

  • Owner changed from ncohen to rlm

comment:10 in reply to: ↑ 7 ; follow-up: Changed 9 years ago by dimpase

  • Status changed from needs_review to needs_work

Replying to wdj:

Nathann: Please do write up the paper Jason suggests. I would also be very interested.

Nathann, you seem to be systematically writing LP where it should be ILP, or MILP, right? Please fix this.

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)

I therefore change the status to "needs work"... (I wish we had anonymous reviewing, like in journals :-))

Dmitrii

comment:11 in reply to: ↑ 10 Changed 9 years ago by jason

Replying to dimpase:

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)

*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.

comment:12 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review

Hello !!!

Here is a new version of the patch with the examples you requested.

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.

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...

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.

Nathann

comment:13 Changed 9 years ago by ncohen

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.

( #8171 and #8172 are still waiting for review, btw :-) )

Nathann

comment:14 follow-up: Changed 9 years ago by ncohen

By the way... I just retried to solve this problem using CPLEX instead of Coin.. Result :

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]}
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]}

So it seems it is not that bad after all :-)

Nathann

comment:15 in reply to: ↑ 14 Changed 9 years ago by dimpase

Replying to ncohen:

By the way... I just retried to solve this problem using CPLEX instead of Coin.. Result :

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]}
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]}

So it seems it is not that bad after all :-)

I wonder how does it scale when the number of vertices of G grows.

Regarding CPLEX I would not be that optimistic - they did not say whether they give that free licences for unlimited time.

Nathann

comment:16 follow-up: Changed 9 years ago by ncohen

I expect it not to scale ;-)

Nathann

comment:17 in reply to: ↑ 16 ; follow-up: Changed 9 years ago by dimpase

Replying to ncohen:

I expect it not to scale ;-)

yeah - can you try some 20-25 vertex examples?

(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...)

comment:18 in reply to: ↑ 17 ; follow-up: Changed 9 years ago by ncohen

yeah - can you try some 20-25 vertex examples?

(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...)

I would be glad to review your patch if you were to write one :-D

(Sorry, but I really do not have much time available these days....)

Nathann

comment:19 in reply to: ↑ 18 Changed 9 years ago by dimpase

Replying to ncohen:

yeah - can you try some 20-25 vertex examples?

(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...)

I would be glad to review your patch if you were to write one :-D

(Sorry, but I really do not have much time available these days....)

nobody has any time :)

well, you still should change "Linear Programming" to "(Mixed) Integer Linear Programming", at least in your patch and in other docs.

Nathann

comment:20 follow-up: Changed 9 years ago by ncohen

now with *Mixed Integer* linear program

comment:21 in reply to: ↑ 20 Changed 9 years ago by dimpase

  • Status changed from needs_review to positive_review

Replying to ncohen:

now with *Mixed Integer* linear program

OK, but please also fix

ALGORITHM

Mixed Integer Linear Program

it must be "Programming", not "Program" here.

I also notice similar misuses of "Linear Program/Programming?" (instead of (M)ILP) on http://www.sagemath.org/doc/reference/sage/numerical/mip.html

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)

Please fix these too some time soon, please...

comment:22 follow-up: Changed 9 years ago by ncohen

This patch has been updated to program*ming*.

I you feel anything else in Sage needs to be fixed, please create the corresponding ticket and -- if possible -- write a patch for it.

You have set this ticket to "positive review". Have you actually tested it, docstring and documentation ?

Nathann

comment:23 in reply to: ↑ 22 Changed 9 years ago by dimpase

Replying to ncohen:

This patch has been updated to program*ming*.

I you feel anything else in Sage needs to be fixed, please create the corresponding ticket and -- if possible -- write a patch for it.

well, I do not know how to patch that writeup on linear programming --- Minh does not seem to know this, either.

You have set this ticket to "positive review". Have you actually tested it, docstring and documentation ?

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 :))

I do not know how to *test* documentation, never heard of --- is there a way?

Oh, by the way, there is still a fix needed:

you should add # optional on the line 1951 of the file, otherwise sage -t (no -optional) will complain about undefined gg.

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 :))

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?

Dima

comment:24 follow-up: Changed 9 years ago by ncohen

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.

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.

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.

Nathann

Changed 9 years ago by ncohen

comment:25 in reply to: ↑ 24 Changed 9 years ago by dimpase

Replying to ncohen:

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.

Please point me out to a place where I was rude to you. I apologize in advance, if you like, anyway.

By the way, I am considerably older than you, so please also forgive me slipping into patronizing.

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.

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.

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.

And this is exactly the point when I wondered aloud whether it would be better to have anonymous reviewers. :-)

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.

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.

Dima

Nathann

comment:27 Changed 9 years ago by ncohen

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.

Nathann

comment:28 Changed 9 years ago by jhpalmieri

  • Authors set to Nathann Cohen
  • Merged in set to sage-4.4.alpha0
  • Resolution set to fixed
  • Reviewers set to Dmitrii Pasechnik
  • Status changed from positive_review to closed

Merged "trac_8404.patch" into 4.4.alpha0.

Note: See TracTickets for help on using tickets.