4

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.

Khalid Shah
  • 3,132
  • 3
  • 20
  • 39
  • 1
    Networkx has an algorithm that will check if a collection of edges is a perfect matching. But I'm not aware of any algorithm in networkx or other python software that will construct all of them. – Joel Jul 22 '19 at 04:46
  • @Joel if you know any library in any other language which will generate all perfect matchings of the graph ? Any help would be appreciated :) – Khalid Shah Jul 22 '19 at 05:31
  • sorry, can't help you there. The closest I found while looking up this problem is the "blossom algorithm", but it's not clear to me how to be sure you've found all of them. – Joel Jul 22 '19 at 05:51

1 Answers1

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.

Moormanly
  • 1,258
  • 1
  • 9
  • 20