Ask Your Question
0

Compute perfect matchings in a graph

asked 2016-02-13 00:42:52 +0100

MLainz gravatar image

updated 2016-02-13 07:04:43 +0100

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?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2016-02-13 12:53:16 +0100

tmonteil gravatar image

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

edit flag offensive delete link more

Comments

Thank you. Now I use the Jupyter notebook. It's much easier noticing that mistakes with syntax colouring.

MLainz gravatar imageMLainz ( 2016-02-14 23:50:12 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-02-13 00:42:52 +0100

Seen: 7,577 times

Last updated: Feb 13 '16