graph - Graphviz 文件和图同构

Question

问题如下：给定 .dot 文件中表示的两个二部有向图，是否有工具可以检查这两个图是否同构？

Answer 1

Graphviz 是一个布局应用程序；但是，至少在 python 中，有一个与 Graphviz 紧密集成的图形分析库，称为“ Networkx ”。

一般来说，是否应该使用Networkx或其他图形分析库可能只是个人选择的问题；然而，在这种情况下，Networkx 与其他图形分析库相比有一个显着优势，那就是它可以直接读取点文件（不完全是原生支持，但它会将它们转换为原生图形对象）。

Networkx 易于安装（主要操作系统的二进制文件），如果您使用 python安装了“ Easy Install ”，则更容易：

easy_install networkx

import networkx as NX

# convert dot files to the graph analysis package's native graph object:
G1 = NX.read_dot("/maindir/mydir/my_bipartite_graph1.dot")
G2 = NX.read_dot("/maindir/mydir/my_bipartite_graph1.dot")

# returns 'True'/'False'
NX.DiGraphMatcher.is_isomorphic(G1 G2)

Answer 2

有一些工具可以检查两个图是否同构。一种可能是名为igraph的库，它具有 R 和 Python 的更高级别接口。不幸的是， igraph目前无法读取 DOT 文件，因此您必须将图形转换为其他格式（例如，标准边列表格式即可）。转换后，您可以在 Python 中执行以下操作：

>>> from igraph import load
>>> g = load("my_graph.txt", format="edgelist")
>>> g2 = load("my_other_graph.txt", format="edgelist")
>>> g.isomorphic(g2)
False

另一个选择是NetworkX，它也是一个 Python 包。它可以原生读取 DOT 文件，但它是用纯 Python 实现的，因此它往往比igraph慢，而 igraph 主要用 C 实现。所以，一般来说，如果你的图形相对较小或使用NetworkX可能会更好如果它们不太可能是同构的，因为在检查两个图的度分布时，后一种情况通常会很早就出现。（如果它们是同构的，则度分布必须相等）。如果这两个图很大并且预计它们是同构的，那么使用igraph可能会更好，因为在这种情况下证明同构的计算量更大。