python networkx 获得独特的匹配组合

Question

我有一个节点图，这些节点可能是项目的重复项，我正试图找到所有可能的匹配项组合。如果两个节点相连，这意味着它们可能是相同的项目，但没有节点可以匹配超过一次。

例如，如果我采用以下简单图表：

T = nx.Graph()

T.add_edge('A','B')
T.add_edge('A','C')
T.add_edge('B','D')
T.add_edge('D','A')

在此示例中，我的输出可能是：

[{A:B},{A:C,B:D},{A:D}]

我怎样才能制定独特组合的列表？一些图表有大约 20 个节点，因此无法通过所有组合进行暴力破解。

Answer 1

看来您要查找的是 G 的匹配项，即没有两条边共享公共顶点的边集。
特别是，您正在寻找 最大匹配 的 G.

Networkx 提供功能maximal_matching。您可以扩展此功能以获得所有最大匹配。
一种方法可能如下所示。您从部分匹配的列表开始，每个匹配由一条边组成。然后扩展每个部分匹配，直到它成为最大匹配，即，直到它不能扩展到更大基数的匹配。

如果部分匹配 m 可以使用边 (u,v) 扩展为更大的匹配，则 m'=m ∪ {(u,v)} 被添加到部分匹配列表中。否则，将 m 添加到最大匹配列表中。

可以改进以下代码以在许多方面提高效率。一种方法是在添加到部分匹配列表之前进行检查。事实上，该列表将包含代表相同的部分匹配（即 [{i,j},{u,v}] 和 [{u,v},{i,j}] ）。

import networkx as nx
import itertools

def all_maximal_matchings(T):

    maximal_matchings = []
    partial_matchings = [{(u,v)} for (u,v) in T.edges()]

    while partial_matchings:
        # get current partial matching
        m = partial_matchings.pop()
        nodes_m = set(itertools.chain(*m))

        extended = False
        for (u,v) in T.edges():
            if u not in nodes_m and v not in nodes_m:
                extended = True
                # copy m, extend it and add it to the list of partial matchings
                m_extended = set(m)
                m_extended.add((u,v))
                partial_matchings.append(m_extended)

        if not extended and m not in maximal_matchings:
            maximal_matchings.append(m)

    return maximal_matchings

T = nx.Graph()

T.add_edge('A','B')
T.add_edge('A','C')
T.add_edge('B','D')
T.add_edge('D','A')

print(all_maximal_matchings(T))

python networkx 获得独特的匹配组合

python networkx get unique matching combinations

python

graph

matching

networkx