Get all perfect matchings of Hybercubes In Python

Question

I am working on hyper-cubes. I am currently using networX in python. I read that networkX is a very good library for working on graphs. My problem is that

1) I want to construct the all perfect matchings of hypercube Q4 and Q5.

2) Then i want to verify that all perfect matchings always extends to Hamiltonian cycle of Hypercube?

P.S : its already proven all perfect matchings in hyper-cubes always extends to Hamiltonian Cycle in hyper-cubes.

I want to verify both these task by a computer program.

I am new to python. I write a code for constructing hyper-cube.

import networkx as nx

graphSize = 4
hypercube = nx.hypercube_graph(graphSize)
print("Nodes in Q_" + str(graphSize) + " : " + str(nx.Graph.number_of_nodes(hypercube)))
print("Edges in Q_" + str(graphSize) + " : " + str(nx.Graph.number_of_edges(hypercube)))

OUTPUT

Nodes in Q_4 : 16

Edges in Q_4 : 32

This runs perfectly fine. But i can't find any library or functions in networkX to get the list of all perfect matchings. Can someone tell me if there is any function available in any python library for getting all perfect matching in graphs Or someone have the code who construct all the perfect matchings for only Q4 and Q5. Thanks in Advance.

Answer 1

1) I want to construct the all perfect matchings of hypercube Q4 and Q5.

I don't know of any library for finding all perfect matchings of a graph directly. However, this github repository "contains functions to enumerate all perfect and maximum matchings in bipartited graph." Since all perfect matchings are maximum matchings, you can use this to get all maximum matchings and throw out those that are not perfect. Below is some code to do this in python 2.7.

import networkx as nx

graph_size = 4
hypercube = nx.hypercube_graph(graph_size)

# Set the 'bipartite' attribute of the nodes, as required by bipartitematching.py
bottom_nodes, top_nodes = nx.bipartite.sets(hypercube)
bipartite_attributes = {node: 0 for node in bottom_nodes}
bipartite_attributes.update({node: 1 for node in top_nodes})
nx.set_node_attributes(hypercube, bipartite_attributes, "bipartite")

# Now find all of the maximum bipartite matchings
from bipartitematching import enumMaximumMatching
matchings = enumMaximumMatching(hypercube)

# Finally, find those maximum matchings that are perfect
perfect_matchings = []
for matching in matchings:
    if len(matching) == nx.number_of_nodes(hypercube)/2:
        perfect_matchings.append(matching)

# How many were there?
print(len(perfect_matchings))

I have verified that this code produces 272 for the 4d hypercube, but I was not patient enough to let it finish for the 5d hypercube. According to OEIS, the 5d hypercube should have 589185 perfect matchings, so it could be quite slow to find them all using this code.