Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

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