ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 13 May 2011 12:58:08 +0200Graph minors in programminghttps://ask.sagemath.org/question/8111/graph-minors-in-programming/Hello
In a program I am writing, I need to know whether or not one graph is a minor of another, True or False. The function g.minor(h) returns the parts of g that are the minor h, if it exists, something like this:
{0: [2], 1: [1], 2: [0], 3: [3, 6], 4: [4], 5: [5]}
UPDATE: I think I can handle this but I'm sure it's not the best way, so any help is still appreciated. By doing L = g.minor(h) and then testing if len(flatten(L.values())) > 0, I will get True if h is a minor of g (or so it seems).
If no such minor exists, it throws an error. To be specific, it says "Traceback", then several lines of stuff I don't get at all, and then "ValueError: This graph has no minor isomorphic to H !". I don't know how to deal with either of these situations really. Can you help me out? Again, I just want True in the first case and False in the second case for programming purposes, as in graph theory knowing if a graph has another graph as a minor is very important in many instances.
I am using Version 4.6 (since I am a Windows user), in case that matters.
Thanks for any help!Fri, 13 May 2011 12:01:03 +0200https://ask.sagemath.org/question/8111/graph-minors-in-programming/Answer by DSM for <p>Hello</p>
<p>In a program I am writing, I need to know whether or not one graph is a minor of another, True or False. The function g.minor(h) returns the parts of g that are the minor h, if it exists, something like this:</p>
<p>{0: [2], 1: [1], 2: [0], 3: [3, 6], 4: [4], 5: [5]}</p>
<p>UPDATE: I think I can handle this but I'm sure it's not the best way, so any help is still appreciated. By doing L = g.minor(h) and then testing if len(flatten(L.values())) > 0, I will get True if h is a minor of g (or so it seems).</p>
<p>If no such minor exists, it throws an error. To be specific, it says "Traceback", then several lines of stuff I don't get at all, and then "ValueError: This graph has no minor isomorphic to H !". I don't know how to deal with either of these situations really. Can you help me out? Again, I just want True in the first case and False in the second case for programming purposes, as in graph theory knowing if a graph has another graph as a minor is very important in many instances.</p>
<p>I am using Version 4.6 (since I am a Windows user), in case that matters.</p>
<p>Thanks for any help!</p>
https://ask.sagemath.org/question/8111/graph-minors-in-programming/?answer=12346#post-id-12346The "Traceback" bits are showing you the code near where the uncaught exception was raised. Typing "Graph.minor??" will show you the whole code.
In Python, you can catch an exception by using a try/except pair. So one way to write a function that does what you want is:
def has_minor(G, H):
try:
m = G.minor(H)
return True
except ValueError:
return False
sage: has_minor(graphs.CompleteGraph(4), graphs.DurerGraph())
False
sage: has_minor(graphs.DurerGraph(), graphs.CompleteGraph(4))
True
The above calls the minor function, and tries to put that result into m. If that function succeeds, then it found a minor, and so we return True. On the other hand, if the .minor(H) call didn't succeed, then it jumps to the "except ValueError:" branch and returns False instead. The [tutorial on exceptions](http://docs.python.org/tutorial/errors.html#handling-exceptions) is pretty good in explaining how the control flow works.
This isn't necessarily the most efficient way, but it should get the job done.
Fri, 13 May 2011 12:25:07 +0200https://ask.sagemath.org/question/8111/graph-minors-in-programming/?answer=12346#post-id-12346Comment by G-Sage for <p>The "Traceback" bits are showing you the code near where the uncaught exception was raised. Typing "Graph.minor??" will show you the whole code. </p>
<p>In Python, you can catch an exception by using a try/except pair. So one way to write a function that does what you want is: </p>
<pre><code>def has_minor(G, H):
try:
m = G.minor(H)
return True
except ValueError:
return False
sage: has_minor(graphs.CompleteGraph(4), graphs.DurerGraph())
False
sage: has_minor(graphs.DurerGraph(), graphs.CompleteGraph(4))
True
</code></pre>
<p>The above calls the minor function, and tries to put that result into m. If that function succeeds, then it found a minor, and so we return True. On the other hand, if the .minor(H) call didn't succeed, then it jumps to the "except ValueError:" branch and returns False instead. The <a href="http://docs.python.org/tutorial/errors.html#handling-exceptions">tutorial on exceptions</a> is pretty good in explaining how the control flow works.</p>
<p>This isn't necessarily the most efficient way, but it should get the job done. </p>
https://ask.sagemath.org/question/8111/graph-minors-in-programming/?comment=21747#post-id-21747This worked and is very simple! This is very helpful. Thanks.Fri, 13 May 2011 12:58:08 +0200https://ask.sagemath.org/question/8111/graph-minors-in-programming/?comment=21747#post-id-21747