图论包

介绍了图数据结构和算法的 Python 实现。最小图形接口与几个实现该接口的类一起定义。图节点可以是任何可散列的 Python 对象。有向边是 Edge 类的实例。图是 Graph 类的实例（有几个版本）。Multigraph 是 MultiGraph 类的实例。许多算法都是使用统一的方法实现的。有专门用于不同算法的单独的类和模块。

问题和算法

• 连通性：连通分量、强连通分量、割节点、割边（桥）
• 循环检测、拓扑排序（DFS、Kahn）、传递闭包（矩阵乘法、Floyd-Warshall、BFS、DFS）
• 二部性：二部图检测（BFS，DFS），最大基数匹配（Hopcroft-Karp，Ford-Fulkerson）
• 匹配：启发式（贪心最大基数匹配，贪心最小权重匹配）
• 顶点着色：顺序（US、RS、CS）、布鲁克斯定理（Delta 颜色）、m-coloring（回溯、精确）、计数器方法（精确）、LF、SLF、RLF、SL、GIS
• 边缘着色：使用折线图（使用顶点着色）、顺序（US、RS、CS）、NTL（使用 Delta 或 Delta+1 颜色）、完整图（精确）、二分图（精确）
• 独立集：回溯（精确）、US、RS、LL、SF
• 主导集：回溯（精确）、混合（精确）、US、RS、LF
• 顶点覆盖（启发式）：贪婪，2-近似，LF
• 最小生成树（加权无向图）：Boruvka、Prim、Kruskal
• 单源最短路径（无负循环的加权有向图）：Dijkstra（非负权重）、DAG（使用拓扑排序）、Bellman-Ford
• 全对最短路径（没有负循环的加权有向图）：Floyd-Warshall，Johnson，矩阵乘法
• 欧拉图：DFS、Fleury、Hierholzer
• 哈密​​顿图：DFS、锦标赛、TSP（DFS，带 MST、NN、RNN、排序边）
• 森林（精确算法）：iset、dset、顶点覆盖、匹配、树中心、绘图
• 串并图（精确算法）：识别、生成器、iset、dset、顶点覆盖、匹配、弦完成（PEO）、顶点着色
• Halin 图（精确算法）：识别、生成器、顶点着色、弦完成 (PEO)、树分解、绘图
• 弦图（精确算法）：识别、生成器、寻找 PEO（MCS）、寻找最大团（PEO、MDO）、寻找所有最大团（PEO）、寻找树分解
• 外平面图（精确算法）：识别、弦完成（PEO）、顶点着色
• 排列图：进行中...
• 聚类：克鲁斯卡尔。

安装

见 doc/quickstart.txt

参考

[1] A.卡帕诺夫斯基和Ł。Gałuszka，使用 Python 的加权图算法。 http://arxiv.org/abs/1504.07828 [草案]

A.卡帕诺夫斯基和Ł。Gałuszka，使用 Python 的加权图算法。Python 论文 11、3（2016 年）。 http://ojs.pythonpapers.org/index.php/tpp/article/view/270 [最终版]

[2] A. Kapanowski 和 A. Krawczyk，Halin 图是 3-vertex-colorable，除了偶数轮。 https://arxiv.org/abs/1903.02904

贡献者

Andrzej Kapanowski（项目负责人）

Łukasz Gałuszka（MST，最短路径，流）

Łukasz Malinowski（匹配、欧拉图、图着色、二分图）

Paweł Motyl（多重图、图着色、独立集）

Piotr Szestało（哈密顿图、TSP、锦标赛）

Kacper Dziubek（平面度测试）

Sandra Pażyniowska（绘图）

Wojciech Sarka（统治系列）

Igor Samson（图形着色）

Dariusz Zdybski（派系）

Aleksander Krawczyk（哈林图，轮图）

Małgorzata Olak（弦图）

Krzysztof Niedzielski（匹配）

Konrad Gałuszka（串并图）

Maciej Niezabitowski（树分解）

Piotr Wlazło（边缘着色）

Magdalena Stępień (平面图)

Sandra Rudnicka（外平面图）

Albert Surmacz（排列图）

EOF