Алгоритм объединения частей ориентированного графа

Рассматривается задача объединения графов с общей частью, которые были получены в результате серии моделирований сети Петри с использованием программного пакета Colored Petri Nets Tools, в котором адресное пространство процесса ограничено 2$^{32}$ байтами, начиная с различных вершин и при различных начальных условиях. Для ее решения необходимо определить общую часть графов, выполнить разрез таким образом, чтобы их общая часть осталась только в одном из начальных графов, и составить таблицу соответствия (переходов) между вершинами графов для возможности осуществления переходов между ними. Изначально предполагается, что графы представлены в виде списков смежности, но в процессе работы алгоритма они преобразовываются в хеш-таблицы для быстрого определения общей части графов, которое реализуется при помощи обхода одного из графов и проверки наличия вершин во втором. Составление таблицы переходов между графами осуществляется при помощи обхода графа по парам «родительская-дочерняя» вершины, в ходе которого проверяются условия добавления узлов в таблицу переходов. Предлагается алгоритм решения задачи объединения частей ориентированного графа и приведен пример его использования.