Graph minor code (too slow in certain situations) Sage 4.6

asked 2011-05-13 16:44:00 +0200

G-Sage
411 ●19 ●32 ●48

updated 2011-10-11 09:39:02 +0200

Okay, so what I want to say here is that the code that searches for a graph minor is extremely slow in situations where it should be able to respond instantaneously. Here's a function written by DSM when responding to my last question here:

def has_minor(G, H):
    try:
        m = G.minor(H)
        return True
    except ValueError: 
        return False

I run the following code:

t=cputime()
h=graphs.CompleteGraph(7)
print h.size()
g=graphs.CompleteBipartiteGraph(4,4)
print g.size()
has_minor(g,h)
cputime(t)

This code checks if a K_{4,4} graph has as a minor a K_7 graph. The output is:

21
16
59.187697999999983

This tells us that a K_7 has 21 edges and a K_{4,4} has 16, so there's no way that a K_{4,4} has as a minor a K_7. Minors must have less than or the same number of edges as the original graph. So, it shouldn't take almost a minute to tell me that there is no such minor. It should take 0.001 seconds, approximately, because it should first check that simple thing before actually trying to find minors.

Or, am I completely off here?

edit retag flag offensive close merge delete

Comments

Oh, and by the way. CPLEX is much faster than GLPK for these computations. So if you want to go through the trouble of using it as a LP solver, your computation times should be greatly improved :-) See the bottom of http://www.sagemath.org/doc/thematic_tutorials/linear_programming.html

Nathann ( 2011-05-14 04:10:24 +0200 )edit

@Nathann As far as programming, it looks like I'd do nothing else to use this, right? I'd just get the various license and file and whatever, and then set Solver to CPLEX when using minor (or any other function that uses linear programming)?

G-Sage ( 2011-05-16 23:00:03 +0200 )edit

add a comment

3 Answers

Sort by » oldest newest most voted

answered 2011-05-13 21:37:31 +0200

DSM

5242 ●21 ●68 ●112

When you're working with Sage, it really is worth reading the code directly. It's often the case that no one optimized for a use case they didn't need. From the documentation (Graph.minor?):

   COMPLEXITY:

   Theoretically, when H is fixed, testing for the existence of a
   H-minor is polynomial. The known algorithms are highly exponential
   in H, though.

   Note: This function can be expected to be *very* slow, especially where
     the minor does not exist.

And when you look at the code (Graph.minor??) you see that it doesn't do any checking beforehand, it simply dives right in and treats it as a linear program.

In the short term, you can simply add whatever give-up-early checks you want to has_minor yourself. In the medium term, we should probably patch this; are you interested in writing one? It would be pretty simple, and I can help shepherd you through the process. Wasn't so very long ago I submitted my first patch! Warning: it can be addictive. :^)

edit flag offensive delete link

Comments

Ah, see, I didn't know how to look at the source code! Perhaps I will write up a fix for it sometime. Thanks again for your help!

G-Sage ( 2011-05-14 00:49:49 +0200 )edit

add a comment

answered 2011-05-16 20:26:31 +0200

G-Sage
411 ●19 ●32 ●48

I'm "answering" just because this will be too long to be a comment.

I don't know C/C++ any more than I know Python. I know very little of both. I took a class on C++ around 12 years ago and a class on Java around 11 years ago. I haven't used either since. I know the basics of programming. I know the Python I have used in my various experiences with Sage. In the long run, I do think I'd like to learn more.

I don't see the source code at all. When I type Graphs.minor??, it starts to show me the code and ends like this (so it gives description and examples but no actual code of the algorithm):

  sage: g = graphs.RandomGNP(20,.5)
  sage: g = g.subgraph(edges = g.min_spanning_tree())
  sage: g.is_tree()
  True
  sage: L = g.minor(graphs.CompleteGraph(3))
Traceback (click to the left of this block for traceback)
...

I can give a simple algorithm to speed it up in the cases I'm talking about. If we start with a graph G with order a and size b, then any minor of G can have at most a vertices and and b edges. So, all I'm suggesting is to start by checking if this condition holds. If it doesn't, you know there is no such graph minor and there's no reason to "search" for it.
```
if G.size() < H.size() or G.order() < H.order():
   fail, H is not a minor of G.
else:
    go through the algorithm that is programmed currently
```
I wonder if there are any other quick checks that might help, but I don't know of any others. I agree that programming it all in C is a good thing to do since the process is so slow in general. But, I won't be of much help in that, other than to suggest the quick check is included.

edit flag offensive delete link

add a comment

answered 2011-05-14 04:05:43 +0200

Nathann
1615 ●2 ●15 ●36

updated 2011-05-14 04:07:18 +0200

Wow ! Somebody is actually using this code ! Now I'am glad :-)

Well, as said before the minor function translates the code to a LP immediately. I had found a way to write this LP somehow smoothly, just to see how it can be done. I have been lookin for VERY LONG for codes to compute treedecomposition and treewidth (I know that some exists), but people never answered my emails until now. I almost began to write my own, but in any case these algorithms are REALLY exponential.

As for the graph minor test, honestly, I don't think there exists an implementation anywhere else in the world. I tried this one, and it is slow as hell, but it's more to say "it can be solved through LP" than to solve them exactly.

Of course, as you say, there are ways to improve it by actually looking at the graph (even by just counting edges... God this LP formulation is bad). There are also several equivalent conditions for several graphs (cycles, K_4), but for K_4 it is already a lot of work.

Anyway if you're willing to work on Minors in Sage, count me in. Same goes for treewidth or pathwidth, but I think we should be prepared to deal with some C/C++ code, because anything useful in this context has to be written efficiently.

Oh, that's right, you're not addited to sending patches yet. Well, if you're willing to send this patch about edge counting, we'll have plenty of time to try longer codes afterwards :-)

Nathann

edit flag offensive delete link

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Graph minor code (too slow in certain situations) Sage 4.6

Comments

3 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Graph minor code (too slow in certain situations) Sage 4.6 edit

Comments

3 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Graph minor code (too slow in certain situations) Sage 4.6