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?
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 thedmperm
with