Сопоставление иерархических неточных графов

Пожалуйста, обратитесь к изображению ниже

Иерархические графики

Я хочу сравнить 2 графика, чтобы определить, какие изменения произошли на определенном графике. Например, если я считаю, что график слева является графиком модели, а один или правый - модифицированным графиком, мне нужно иметь возможность определить следующее.

  1. самый левый оранжевый узел удален
  2. Зеленый узел был добавлен как дочерний к самому правому оранжевому узлу.
  3. 3-й зеленый узел слева имеет новый синий дочерний узел

и так далее. Я могу сравнивать только узлы похожего цвета. т. е. Все оранжевые узлы можно сравнивать между двумя графами, все зеленые узлы можно сравнивать между двумя графами и т. д. Каждый узел будет иметь некоторый атрибут, который можно использовать для идентификации соответствующего уникального узла в другом графе.

Пожалуйста, дайте мне знать, какой алгоритм сопоставления графов подходит для этой цели. Или вообще требуется использовать алгоритм сопоставления графов, поскольку узлы одного цвета могут быть сопоставлены с использованием цвета и уникального атрибута узла.


graph matching algorithm hierarchical
person balajir712    schedule 20.10.2015    source источник
comment
Всегда ли графы являются деревьями, как в вашем примере? Если это так, то решение вашей проблемы подразумевает решение проблемы изоморфизма графов (кратко: эквивалентны ли 2 заданных графа?), которая, как известно, не является NP-трудной, но для которой в настоящее время не известны эффективные алгоритмы (хотя инструмент Наути очень хорошо работает на практике).   -  person j_random_hacker    schedule 20.10.2015
comment
Могут быть и циклы. Я не могу утверждать, что это будет дерево. Разве изоморфизм графов не требует, чтобы количество узлов и ребер совпадало в графе 2. то есть они должны быть одного размера?   -  person balajir712    schedule 20.10.2015
comment
В ПОРЯДКЕ. В этом случае алгоритмы с полиномиальным временем неизвестны. Возможно, вы сможете использовать дополнительные параметры nauty, чтобы обеспечить ограничения цвета — я не использовал его широко.   -  person j_random_hacker    schedule 20.10.2015
comment
Можно ли это рассматривать как проблему изоморфизма максимального общего ребра? Помогут ли в этом случае какие-то алгоритмы MCES?   -  person balajir712    schedule 22.10.2015
comment
Я не знаю, что это за проблема, извините.   -  person j_random_hacker    schedule 22.10.2015

Ответы (1)


arrow_upward
0
arrow_downward

Возможно, сначала попробуйте самое простое решение. Поиск в ширину по графу (+ набор посещенных узлов для разбиения циклов). Поместите узлы одинакового цвета в массивы в порядке их появления. Затем сравните массивы либо как линейную последовательность, либо используйте самую длинную общую последовательность. Обратите внимание, что у узла может быть другой родитель, но та же позиция в массиве, поэтому сравните также родителя узла.

person One Man Monkey Squad    schedule 04.02.2016