（Python）计算加权完美匹配的代码？

Question

如果这个问题更适合mathoverflow或其他姐妹网站，请原谅我。在

我对计算（不一定是二部）平面图中完美匹配的加权和感兴趣。这是一个标准问题；通常使用FKT algorithm来解决它。我想找一些Python代码来解决这个问题（我不想自己写，因为算法有点复杂）。在

否则，是否有其他（相对主流）语言的代码可用？在

下面的用户sabbahillel建议我列出一些我发现不起作用的软件，以避免重复工作。为此目的：

• fkt似乎只适用于未加权的图，并且在Gforth中。在
• OBDD作者：Knuth（！）仅适用于未加权二部图，且在CWEB中。在
• vaxmaple需要Maple，vaxmacs是Emacs模式（？！？！）不支持加权图或非二部图。在

Answer 1

谷歌是你的朋友。我发现了一个在FORTH中实现此功能的sourceforge项目

FKT Alpha Count perfect matchings in planar graphs.

Description: This project provides an implementation of the FKT algorithm to count the number of perfect matchings in a planar graph. The source code is written in the Forth language, requiring Gforth to run. Computations can be perfored via a command line tool as well as via a library usable with Gforth.

Source Code

Answer 2

我是sourceforge上FKT项目的作者。FKT支持加权图。FKT安装一个命令行程序，该程序将图形的ASCII描述作为输入，并在stdout上输出计算出的匹配数。此接口允许与其他编程语言（如Python）轻松集成。当然，您需要在您的系统上安装Gforth，但这应该不是问题，所有主流Linux发行版的存储库中都有Gforth包。在

FKT在有限域上用整数运算进行所有计算（将所选整数N模化）。整数N的宽度限制为31或63位，具体取决于您的操作系统。如果需要更长的结果，您可以使用不同的（co）素数N劏1..N_k多次调用FKT，然后使用Chinese Remainder Theorem来确定图模N_1*.*N_k匹配的实际加权计数

注意，FKT算法不确定匹配和的实际符号。它只保证所有匹配都用同一个符号求和。所以FKT输出-m或m（mod N），在应用中国剩余定理后，输出要么是-m，要么是m（mod N_1*…*N_k）。通常你对你的图有足够的了解，知道什么符号可以作为例子。在