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.Sun, 14 Feb 2016 23:50:12 +0100Compute perfect matchings in a graphhttps://ask.sagemath.org/question/32555/compute-perfect-matchings-in-a-graph/I am trying to calculate all the perfect matchings of a graph G (i. e., the subgraphs of G such that every two points are connected)
def matchings(G):
"""Returns a list of the perfect matchings of G.
It uses a recursive algorithm. Get a vertex x in G.
Since all the perfect matchings contain exactly one edge for every vertex,
we have that matchings(G) = {<x,y> U matchings(G\{x,y}) for y adjacent to x}.
"""
Ms=[] #List of mathchings
x = G.random_vertex()
for e in G.edges_incident(x):
H=G.copy()
H.delete_vertices([e[0],e[1]]
for M in matchings(H):
Ms.append(M.add_edge(e))
return Ms
But this gives me
line 14 for M in matchings(H):
SyntaxError: invalid syntax
I don't understand the error (the loop seems fine to me). What's wrong?
Sat, 13 Feb 2016 00:42:52 +0100https://ask.sagemath.org/question/32555/compute-perfect-matchings-in-a-graph/Answer by tmonteil for <p>I am trying to calculate all the perfect matchings of a graph G (i. e., the subgraphs of G such that every two points are connected)</p>
<pre><code>def matchings(G):
"""Returns a list of the perfect matchings of G.
It uses a recursive algorithm. Get a vertex x in G.
Since all the perfect matchings contain exactly one edge for every vertex,
we have that matchings(G) = {<x,y> U matchings(G\{x,y}) for y adjacent to x}.
"""
Ms=[] #List of mathchings
x = G.random_vertex()
for e in G.edges_incident(x):
H=G.copy()
H.delete_vertices([e[0],e[1]]
for M in matchings(H):
Ms.append(M.add_edge(e))
return Ms
</code></pre>
<p>But this gives me </p>
<pre><code>line 14 for M in matchings(H):
SyntaxError: invalid syntax
</code></pre>
<p>I don't understand the error (the loop seems fine to me). What's wrong?</p>
https://ask.sagemath.org/question/32555/compute-perfect-matchings-in-a-graph/?answer=32558#post-id-32558I did not check the whole correctedness of your algorithm, but i can see a syntax error at the line
H.delete_vertices([e[0],e[1]]
At the end of the line, a closing parenthesis is missing.
Sat, 13 Feb 2016 12:53:16 +0100https://ask.sagemath.org/question/32555/compute-perfect-matchings-in-a-graph/?answer=32558#post-id-32558Comment by MLainz for <p>I did not check the whole correctedness of your algorithm, but i can see a syntax error at the line</p>
<pre><code>H.delete_vertices([e[0],e[1]]
</code></pre>
<p>At the end of the line, a closing parenthesis is missing.</p>
https://ask.sagemath.org/question/32555/compute-perfect-matchings-in-a-graph/?comment=32562#post-id-32562Thank you. Now I use the Jupyter notebook. It's much easier noticing that mistakes with syntax colouring.Sun, 14 Feb 2016 23:50:12 +0100https://ask.sagemath.org/question/32555/compute-perfect-matchings-in-a-graph/?comment=32562#post-id-32562