Разложение матрицы Дульмага-Мендельсона в Python

Question

Matlab имеет функцию с именем dmperm, которая вычисляет так называемый Dulmage – Mendelsohn разложение матрицы n x n.

Из википедии Dulmage – Mendelsohn - это разбиение вершин двудольного графа на подмножества со свойством, что две смежные вершины принадлежат одному и тому же подмножеству тогда и только тогда, когда они спарены с каждым другой в идеальном соответствии графа.

Глядя как на scipy, так и на numpy, я не смог найти ни эту функцию, ни какую-то похожую версию. Можно ли реализовать это с помощью базовых операций линейной алгебры? Любая идея, если это реализовано в некотором пакете Python?

Answer 1

"Есть ли идеи, если это реализовано в каком-то пакете Python?"

Ну, поскольку у MATLAB есть Python API, это определенно да. Пакет называется matlab.engine, и вы можете увидеть здесь для установки. Обратите внимание, что вам, вероятно, придется установить его с правами sudo.

Например, использование пусть A будет некоторой матрицей, тогда вы можете найти dmperm с

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