Dulmage-Mendelsohn matrix decomposition in Python

Question

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?

Answer 1

"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