Постройте двудольное представление направленной сети для использования с функцией сопоставления Хопкрофта-Карпа в networkx - PullRequest
Новая
       56

Постройте двудольное представление направленной сети для использования с функцией сопоставления Хопкрофта-Карпа в networkx

0 голосов
/ 10 июля 2020

Я использую алгоритм Хопкрофта-Карпа в networkx в направленной сети, которую я преобразовал в двудольное представление. Однако двудольной сети не разрешается иметь одну и ту же вершину в левом и правом наборах узлов. В мою направленную сеть включен self l oop, поэтому в качестве обходного пути я переименовал вершины в левом наборе узлов как (X1_ +, X2 _ +, X3_ +), а в правом наборе как (X1 _-, X2_ -, Х3_-). Направленная сеть и соответствующее двудольное представление имеют следующий вид:

введите описание изображения здесь

Правильный результат для максимального соответствия, с точки зрения вывода словаря, заданного алгоритмом Хопкрофта-Карпа в networkx, должен быть

{X2-:X1+,X3-:X3+)], так что X1- будет быть единственным несогласованным узлом, поскольку он не отображается как ключ в выходном словаре.

Я следил за документацией networkx, чтобы получить соответствующую двудольную сеть, а затем использовал функцию hopcroft-karp для получения максимального соответствия. Код, который я реализовал, показан ниже вместе с результатом: 

# Add nodes w/ the node attribute bipartite
G_eg.add_nodes_from(["X1_+", "X3_+"], bipartite=1)
G_eg.add_nodes_from(["X2_-", "X3_-"], bipartite=0)
# Add edges only between nodes of opposite node sets
G_eg.add_edges_from([("X1_+", "X2_-"), ("X1_+", "X3_-"), ("X3_+", "X3_-")])

#left, right nodes based on node attribute
left_nodes = {n for n, d in G_eg.nodes(data=True) if d["bipartite"] == 1}
right_nodes = set(G_eg) - left_nodes

#apply hopcroft-karp algorithm
nx.bipartite.hopcroft_karp_matching(G_eg, left_nodes)

вывод:

{'X3_+': 'X3_-', 'X1_+': 'X2_-', 'X3_-': 'X3_+', 'X2_-': 'X1_+'}

Из моего вывода я вижу, что X1_- не указан как ключ и поэтому считается несоответствующим. Однако почему выходные данные дают результат таким образом, то есть игнорируют тот факт, что сеть направлена. Включение X1_+:X2_- в выходной словарь означает, что сопоставлено X1_+. Моя интерпретация неверна?

1 Ответ

0 голосов
/ 10 июля 2020

Действительно, любые направления, которые вы накладываете на края графа, игнорируются hopcroft_karp_matching (и другими реализациями maximum_matching). Что касается формата вывода, в документации указано, что вывод

соответствует - Соответствие возвращается как словарь matches, например это matches[v] == w, если узел v соответствует узлу w. Несовпадающие узлы не используются как ключ в matches.

В частности, совпадающие примечания - это именно ключи каталога, в вашем случае {'X3_+', 'X1_+', 'X3_-', 'X2_-'}. В частности, это означает, что вывод всегда можно разрезать пополам, при этом согласованные узлы доступны как объединение ключей и значений; Я предполагаю, что избыточная информация включена просто потому, что в некоторых случаях это может быть удобно.

...