dulmage_mendelsohn

(函数来自 pyomo.contrib.incidence_analysis.dulmage_mendelsohn)

pyomo.contrib.incidence_analysis.dulmage_mendelsohn.dulmage_mendelsohn(matrix_or_graph, top_nodes=None, matching=None)[source]

根据Dulmage-Mendelsohn特征对二分图或关联矩阵进行分区

Dulmage-Mendelsohn 分区告诉我们，在最大基数匹配之后，两个二分集合中的哪些节点可能无法匹配。应用于关联矩阵时，可以将其解释为将行和列划分为欠约束、过约束和良好约束的子系统。

由于显式检查未匹配的行和列通常很有用， dulmage_mendelsohn 将行划分为以下子集：

  • 欠约束 - 行与可能未匹配的列匹配（未匹配和欠约束的列）

  • square - 良好约束的行，与良好约束的列相匹配

  • overconstrained - 在某些最大基数匹配中可能无法匹配的匹配行

  • unmatched - 在特定最大基数匹配中未匹配的行

并将列分区为子集：

  • unmatched - 在特定最大基数匹配中未匹配的列

  • underconstrained - 在某些最大基数匹配中可能不匹配的列

  • square - 与良好约束的行相匹配的列

  • overconstrained - 列与可能未匹配的行（未匹配和过度约束的行）匹配

虽然Dulmage-Mendelsohn分解没有指定这些子集内的顺序，但此函数返回的顺序保留了用于计算分解的最大匹配。也就是说，将“对应”的行和列子集压缩在一起会生成此最大匹配中的对。例如：

>>> row_dmpartition, col_dmpartition = dulmage_mendelsohn(matrix)
>>> rdmp = row_dmpartition
>>> cdmp = col_dmpartition
>>> matching = list(zip(
...     rdmp.underconstrained + rdmp.square + rdmp.overconstrained,
...     cdmp.underconstrained + cdmp.square + cdmp.overconstrained,
... ))
>>> # matching is a valid maximum matching of rows and columns of the matrix!
Parameters:

  • matrix_or_graph (scipy.sparse.coo_matrix 或 networkx.Graph) – 要分割的关联矩阵或二分图

  • top_nodes (list) – 图中一个二分集合的节点列表。如果提供了图，则必须提供此列表。

  • 匹配 (dict) – 一个最大基数匹配，以字典形式映射从“顶部节点”到它们的匹配节点以及从匹配节点返回到“顶部节点”。

Returns:

  • row_dmp (RowPartition) – 行的Dulmage-Mendelsohn分区

  • col_dmp (ColPartition) – 列的Dulmage-Mendelsohn分区