rustworkx.max_weight_matching#

max_weight_matching(graph, /, max_cardinality=False, weight_fn=None, default_weight=1, verify_optimum=False)#

计算 PyGraph 的最大权重匹配

匹配是边的一个子集，其中任一节点最多出现一次。 匹配的权重是其所有边的权重之和。 极大匹配无法再添加更多边同时仍保持匹配性质。 匹配的基数是指已匹配边的数量。

此函数需要的时间为 \(O(n^3)\)，其中 n 表示图中节点的数量。

此方法基于Jack Edmonds发明的两种方法：一是用于寻找增强路径的“开花”方法，二是用于寻求最大权重匹配的“原始-对偶”方法 [1]。

Parameters:

  • graph (PyGraph) – 用于计算最大权重匹配的无向图。期望没有平行边（多图当前未经测试）。

  • max_cardinality (bool) - 如果为True，则从所有最大基数匹配中计算具有最大权重的最大基数匹配。默认为False。

  • weight_fn (可调用对象) – 一个可选的可调用对象，该对象将接收图中每条边的边对象作为单一参数。预期它会为该边返回一个int类型的权重值。例如，如果权重值都是整数，则可以使用：lambda x: x。若未指定，则会使用default_weight的值作为所有边的权重。

  • default_weight (int) – 当未指定weight_fn时，用于图中所有边权重的int值。默认为1。

  • verify_optimum (bool) – 一个布尔标志，用于运行检查以确保找到的解决方案为最优解。若设置为true，则当找到的解决方案非最优时会抛出异常。这主要用于测试。

Returns:

匹配的元组集合，注意输出中只会列出单一方向，例如： {(0, 1),}。

Return type:

设置