У меня есть график в виде матрицы из 0 и 1, где 1 представляет ребро, соединяющее две вершины.Я выбрал совпадение на графике, переключив некоторые из этих единиц на -1.-1 означает, что край находится в соответствии.Очевидно, что в каждой строке / столбце есть максимум один -1, иначе это не будет совпадение.
У меня проблемы с написанием кода, который даст мне путь расширения (если он существует) из этогосуществующее соответствие.Это часть алгоритма поиска максимального соответствия.
Сначала я собрал индексы строк и столбцов всех ребер графа, которые не совпадают.Затем я хочу получить путь расширения, но я не уверен, как это сделать.Как получить путь расширения, заданный:
- Индексы существующего соответствия
- Двудольный граф, представленный в виде матрицы
- Направленный двудольный граф с -1, назначенным ребрам вграфик, который находится в сопоставлении.
Вот мой график, представленный в матричной форме:
[[1. 1. 1. 0. 0. 0. 0. 0. 0. 0.]
[0. 1. 0. 0. 0. 1. 0. 0. 0. 0.]
[1. 0. 1. 1. 1. 0. 0. 0. 0. 0.]
[1. 0. 0. 1. 1. 0. 0. 0. 0. 1.]
[0. 0. 0. 0. 0. 1. 1. 1. 0. 0.]
[0. 0. 0. 0. 0. 0. 1. 1. 0. 0.]
[0. 0. 0. 0. 0. 1. 0. 1. 0. 0.]
[0. 1. 0. 0. 0. 0. 0. 1. 0. 0.]
[0. 0. 0. 0. 0. 0. 0. 0. 1. 1.]
[0. 0. 0. 0. 0. 0. 1. 1. 0. 0.]]
Направленный граф, соответствующий сопоставлению, выглядит следующим образом:
array([[ 1., 1., -1., 0., 0., 0., 0., 0., 0., 0.],
[ 0., -1., 0., 0., 0., 1., 0., 0., 0., 0.],
[ 1., 0., 1., 1., -1., 0., 0., 0., 0., 0.],
[ 1., 0., 0., 1., 1., 0., 0., 0., 0., -1.],
[ 0., 0., 0., 0., 0., 1., 1., 1., 0., 0.],
[ 0., 0., 0., 0., 0., 0., 1., 1., 0., 0.],
[ 0., 0., 0., 0., 0., -1., 0., 1., 0., 0.],
[ 0., 1., 0., 0., 0., 0., 0., -1., 0., 0.],
[ 0., 0., 0., 0., 0., 0., 0., 0., -1., 1.],
[ 0., 0., 0., 0., 0., 0., -1., 1., 0., 0.]])