graph - Graphviz ファイルとグラフ同形性

Question

問題は次のとおりです。.dot ファイルで表される 2 つの二部有向グラフが与えられた場合、2 つのグラフが同形かどうかを確認できるツールはありますか?

Answer 1

Graphvizはレイアウトアプリケーションです。ただし、少なくともPythonには、「Networkx」と呼ばれるGraphvizと緊密に統合されたグラフ分析ライブラリがあります。

一般に、Networkxを使用するか、別のグラフ分析ライブラリを使用するかは、おそらく個人的な選択の問題です。ただし、この場合、Networkxには、他のグラフ分析ライブラリに比べて1つの大きな利点があります。それは、ドットファイルを直接読み取ることができることです（正確にはネイティブサポートではありませんが、ネイティブグラフオブジェクトに変換します）。

Networkxのインストールは簡単で（主要なOSのバイナリ）、 Pythonで「EasyInstall」をインストールした場合はさらに簡単です。

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

2 つのグラフが同型かどうかをチェックするツールがあります。1 つの可能性は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

もう 1 つの選択肢は、Python パッケージでもあるNetworkXです。DOT ファイルをネイティブに読み取ることができますが、純粋な Python で実装されているため、ほとんどが C で実装されているigraphよりも遅くなる傾向があります。後者のケースは通常、2 つのグラフの次数分布をチェックするときに早期に判明するため、同形である可能性が低い場合。(それらが同型の場合、次数分布は等しくなければなりません)。2 つのグラフが大きく、同形であることが予想される場合は、おそらくigraphを使用したほうがよいでしょう。