eppstein_matching

eppstein_matching(G, top_nodes=None)

返回二部图的最大基数匹配 G .

参数

G网络X图表

无向二部图

top_nodes集装箱

所有节点都在一个二分节点集中的容器。如果未提供，则将进行计算。但如果存在多个解决方案，则会引发异常。

返回

matches词典

将匹配作为词典返回， matching ，以便 matching[v] == w IF节点 v 与节点匹配 w 。不匹配的节点不会在中作为键出现 matching 。

加薪

AmbiguousSolution

如果输入二部图是断开连接的，并且没有提供包含一个二部集中所有节点的容器时引发。当确定每个二部集合中的节点时，如果输入图断开连接，则可能有多个有效解。

参见

hopcroft_karp_matching

笔记

这个函数是用david eppstein版本的hopcroft--karp算法实现的（参见 hopcroft_karp_matching() ，最初出现在 Python Algorithms and Data Structures library (PADS) .

见 bipartite documentation 有关如何在NetworkX中处理二部图的详细信息。