Сравнение 2 графиков создается Библиотекой Графика Повышения
Еще одна точка: я нашел, что это лучше связываться с клиентами по электронной почте, если это возможно. Это - намного более эффективный способ передать информацию (предполагающий, что все вовлеченные могут записать), и это оставляет постоянную запись того, что клиент сказал Вам делать.
2 ответа
Boost.Graph может сделать это, но не с оператором ==: http: //www.boost.org/doc/libs/1_39_0/libs/graph/doc/isomorphism.html
Это сложная проблема, поэтому для больших графиков потребуется много времени.
В общем случае Равенство графов - это проблема, которая, как известно, не решается за полиномиальное время; с практической точки зрения это означает, что решить эту проблему в разумные сроки может быть невозможно (хотя известно, что она не является 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.