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

i like this post (click again to cancel)
1
i dont like this post (click again to cancel)

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?

asked May 13 '11

G-Sage gravatar image G-Sage
301 2 17 30

updated Oct 11 '11

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.htmlNathann (May 14 '11)
@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 (May 16 '11)

3 Answers:

i like this answer (click again to cancel)
2
i dont like this answer (click again to cancel) G-Sage has selected this answer as correct

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

link

posted May 13 '11

DSM gravatar image DSM flag of Canada
4892 12 65 105
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 (May 13 '11)
i like this answer (click again to cancel)
1
i dont like this answer (click again to cancel)

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

link

posted May 14 '11

Nathann gravatar image Nathann
690 6 18

updated May 14 '11

i like this answer (click again to cancel)
1
i dont like this answer (click again to cancel)

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

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

  2. 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)
    ...
    
  3. 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
    
  4. 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.

link

posted May 16 '11

G-Sage gravatar image G-Sage
301 2 17 30

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!
Login/Signup to Post

Question tools

1 follower

Tags:

Stats:

Asked: May 13 '11

Seen: 291 times

Last updated: May 16 '11

powered by ASKBOT version 0.7.22
Copyright Sage, 2010. Some rights reserved under creative commons license.