Revision history [back]

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?

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} 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?