Сравнение 2 графиков, созданных Boost Graph Library

Question

Это может быть довольно новичок или даже неправильный вопрос, поэтому, пожалуйста, простите. Есть ли способ сравнить 2 графика, созданные с помощью Boost Graph Library =>, с 1 графиком, созданным в памяти, и вторым, загруженным из архива (т.е. 2-й был сериализован ранее)?

Я не вижу оператора ==, предоставленного в документации BGL, но не уверен, означает ли это, что мне нужно написать и обход, и сравнение. Любые ссылки на учебники, справочные страницы или образцы будут наиболее полезными

Спасибо заранее Ганеш

Answer 1

Boost.Graph может сделать это, но не с оператором ==: http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/isomorphism.html

Это сложная проблема, поэтому для больших графиков это займет много времени.

Answer 2

В общем случае, Равенство графа - это проблема, о которой неизвестно, что ее можно решить за полиномиальное время; с практической точки зрения это означает, что это может быть фактически невозможно решить за разумное время (хотя неизвестно, что оно является NP -полным). Однако, если вас беспокоит, что метки вершин также равны, то достаточно перебрать все ребра в обоих графах и убедиться, что все они находятся в другом графе.

Редактировать : Если метки вершин (значения, связанные с каждой вершиной) одинаковы на обоих графиках, уникальны и сопоставимы, мы можем проверить изоморфизм в O (V lg V + E lg E) легко, вот так:

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.