ブーストグラフライブラリで作成された2つのグラフを比較する

Question

これは初心者でも間違った質問でもよいので、許してください。 Boost Graph Library =>を使用して作成した2つのグラフをメモリに作成し、アーカイブからロードした2つのグラフを比較する方法はありますか（つまり2番目は以前にシリアル化されていましたか？

私は演算子==はBGLのドキュメントでは提供されていませんが、トラバースと比較の両方を記述する必要があるかどうかはわかりません。チュートリアル、リファレンスページやサンプルへの任意のポインタは、一般的な場合には、事前 ガネーシュ

Answer 1

：それは大規模なグラフのために時間がかかりますのでhttp://www.boost.org/doc/libs/1_39_0/libs/graph/doc/isomorphism.html

これは難しい問題です。

Answer 2

で

おかげで最も参考になる、Graph Equalityは多項式時間で扱いやすいことが知られていないという問題点です。実際には、合理的な時間内に解決することは事実上不可能かもしれないことを意味する（それはNP-completeであることは知られていないが）。しかし、頂点ラベルが同じであることに懸念がある場合は、両方のグラフですべてのエッジを繰り返し処理し、それぞれのグラフが他のグラフにも存在することを確認するだけで十分です。

編集は：頂点ラベル（各頂点に関連付けられた値）は、両方のグラフに同じであり、ユニークと同等である場合、我々は次のように、容易にO（V LG V + E LG E）に同型確認することができそう：Boost.Graphは==演算子でこれを行うことはできませんが

If |G1| != |G2|, the graphs are non-equal. Abort. 

i = 0 
For each vertex V in G1: 
    G1_M[Label(V)] = V 
    G1_I[V] = i 
    i = i + 1 

For each vertex V in G1: 
    G1_E[V] = sort(map(λDestination -> G1_I[Destination]) Edges[V]) 

For each vertex V in G2: 
    If G1_M[Label(V)] does not exist, the graphs are non-equal. Abort. 
    G2_corresp[V] = G1_M[Label(V)] 
    G2_I[V] = G1_I[G2_corresp[V]] 

For each vertex V in G2: 
    G1_E[V] = sort(map(λDestination -> G2_I[Destination]) Edges[V]) 
    Compare G1_E[G2_corresp[V]] and G2_E[V]. If non-equal, the graphs are non-equal. Abort. 

If we get here, the graphs are equal.