blossalg

blossalg是Edmonds算法的Python实现，用于在图上构建最大匹配。有关Edmonds算法的工作原理的更多信息，请参阅维基百科页面。

安装

您可以从PyPI安装blossalg

pip install blossalg

blossalg支持Python 2.7和Python 3.8。

使用

您可以使用以下方式运行blossalg

blossalg infile.csv [outfile.txt]

输入文件infile.csv包含有关节点数量和每个节点邻居的信息。这些信息使用一系列以逗号分隔的二进制值字符串存储。节点通过不同的行和列进行标识，值为1表示节点邻居。按照惯例，节点不能与其自身成为邻居。

例如，一个包含三个节点且节点0和节点2都是节点1邻居的三节点图的输入文件如下所示

0,1,0
1,0,1
0,1,0

给定一个输入文件，blossalg将使用Edmonds blossom算法计算最大匹配。然后，将匹配的节点总数输出到屏幕。

如果提供了输出文件outfile.txt，则最大匹配中的匹配对将被保存到该文件中。输出格式如下。每个节点及其匹配节点将被存储为node_number: matched_node_number。节点号将与输入文件中的节点号相对应（例如，输入文件中的第1行将代表输出文件中的节点0）。输出文件中的每个匹配对将用换行符分隔。按照惯例，未匹配的节点不包括在输出文件中。