scipy.sparse.csgraph.

maximum_bipartite_matching#

scipy.sparse.csgraph.maximum_bipartite_matching(граф, perm_type='строка')#

Возвращает паросочетание двудольного графа, мощность которого не меньше мощности любого заданного паросочетания графа.

Параметры:

графразреженный массив или матрица: Входная разреженная матрица в формате CSR, строки которой представляют одну часть графа, а столбцы — другую. Ребро между двумя вершинами указывается наличием соответствующего элемента в матрице в её разреженном представлении.
perm_typestr, {'row', 'column'}: Какую разбивку вернуть в терминах соответствия: Если 'row', функция производит массив, длина которого равна количеству столбцов во входных данных, и чей \(j\)i-й элемент соответствует строке, сопоставленной с \(j\)-й столбец. И наоборот, если perm_type является 'column', это возвращает столбцы, соответствующие каждой строке.

Возвращает:

permndarray: Сопоставление вершин в одном из двух разделов. Несопоставленные вершины представлены -1 в результате.

Примечания

Эта функция реализует алгоритм Хопкрофта–Карпа [1]. Его временная сложность составляет \(O(\lvert E \rvert \sqrt{\lvert V \rvert})\), и его пространственная сложность линейна по числу строк. На практике эта асимметрия между строками и столбцами означает, что может быть эффективнее транспонировать входные данные, если они содержат больше столбцов, чем строк.

По теореме Кёнига, мощность паросочетания также равна количеству вершин, входящих в минимальное вершинное покрытие графа.

Обратите внимание, что если разреженное представление содержит явные нули, они всё ещё считаются рёбрами.

Реализация была изменена в SciPy 1.4.0 для поддержки сопоставления общих двудольных графов, тогда как предыдущие версии предполагали существование идеального сопоставления. Таким образом, код, написанный для версии 1.4.0, не обязательно будет работать в более старых версиях.

Если возможны несколько допустимых решений, вывод может варьироваться в зависимости от версии SciPy и Python.

Ссылки

[1]

Джон Э. Хопкрофт и Ричард М. Карп. «Алгоритм n^{5 / 2} для максимальных паросочетаний в двудольных графах». В: SIAM Journal of Computing 2.4 (1973), стр. 225–231. DOI:10.1137/0202019

Примеры

>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import maximum_bipartite_matching

В качестве простого примера рассмотрим двудольный граф, в котором доли содержат 2 и 3 элемента соответственно. Предположим, что одна доля содержит вершины с метками 0 и 1, а другая доля содержит вершины с метками A, B и C. Предположим, что есть ребра, соединяющие 0 и C, 1 и A, и 1 и B. Этот граф будет представлен следующим разреженным массивом:

>>> graph = csr_array([[0, 0, 1], [1, 1, 0]])

Здесь единицы могут быть любыми, пока они хранятся как элементы в разреженном массиве. Теперь мы можем вычислить максимальные соответствия следующим образом:

>>> print(maximum_bipartite_matching(graph, perm_type='column'))
[2 0]
>>> print(maximum_bipartite_matching(graph, perm_type='row'))
[ 1 -1  0]

Первый вывод сообщает, что 1 и 2 сопоставлены с C и A соответственно, а второй вывод сообщает, что A, B и C сопоставлены с 1, ничем и 0 соответственно.

Обратите внимание, что явные нули всё равно преобразуются в рёбра. Это означает, что другой способ представления вышеуказанного графа — использование структуры CSR напрямую следующим образом:

>>> data = [0, 0, 0]
>>> indices = [2, 0, 1]
>>> indptr = [0, 1, 3]
>>> graph = csr_array((data, indices, indptr))
>>> print(maximum_bipartite_matching(graph, perm_type='column'))
[2 0]
>>> print(maximum_bipartite_matching(graph, perm_type='row'))
[ 1 -1  0]

Когда одна или обе разделы пусты, сопоставление также пусто:

>>> graph = csr_array((2, 0))
>>> print(maximum_bipartite_matching(graph, perm_type='column'))
[-1 -1]
>>> print(maximum_bipartite_matching(graph, perm_type='row'))
[]

Когда входной массив квадратный, и известно, что граф допускает совершенное паросочетание, т.е. паросочетание со свойством, что каждая вершина графа принадлежит некоторому ребру в паросочетании, то результат можно рассматривать как перестановку строк (или столбцов), превращающую входной массив в такой, что все диагональные элементы непустые:

>>> a = [[0, 1, 2, 0], [1, 0, 0, 1], [2, 0, 0, 3], [0, 1, 3, 0]]
>>> graph = csr_array(a)
>>> perm = maximum_bipartite_matching(graph, perm_type='row')
>>> print(graph[perm].toarray())
[[1 0 0 1]
 [0 1 2 0]
 [0 1 3 0]
 [2 0 0 3]]