Dulmage-Mendelsohn matrix decomposition in Python

816 views Asked by At

Matlab has a function called dmperm that computes the so-called Dulmage–Mendelsohn decomposition of a n x n matrix.

From wikipedia, the Dulmage–Mendelsohn is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph.

Looking both on scipy and numpy, I could not find this function, nor some similar version. Is it possible to implement it using basic linear algebra operations? Any idea if this is implemented in some Python package?

1

There are 1 answers

0
Nicky Mattsson On

"Any idea if this is implemented in some Python package?"

Well as MATLAB have a Python API, this is definitely a yes. The package is called matlab.engine, and you can see here for installation. Note that you will probably have to install it with sudo rights.

For example usage let A be some matrix, then you can find the dmperm with

import matlab.engine
eng = matlab.engine.start_matlab()
#Define A
B = eng.dmperm(eng.double(A)) #Apply MATLABs dmperm