Любой рабочий пример алгоритма VF2?

Question

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

Из базового Google, кажется, это считается одним из де-факто алгоритмов для определения того, являются ли два графика изоморфными, но по какой-то причине я не могу найти объяснение, достаточно простое для понимания на высоком уровне. Или этот алгоритм известен под другим именем?

В любом случае, кто-нибудь знает какие-нибудь примеры работы этого алгоритма?

Answer 1

Я не уверен, что это то, что вы ищете, но алгоритм VF2 работает, как показано ниже.

Допустим, у вас есть 2 графика: V и V ', и вы хотите сопоставить V с V'

Алгоритм спускается по дереву, на каждом шаге вы пытаетесь сопоставить следующий элемент V с одним из V 'и останавливаетесь, когда проходили все узлы в V' (когда вы находите лист).

Алгоритм:

• Первый шаг: сопоставить пустой V с пустым графом V '.
• Второй шаг: попробуйте объединить один узел в V с одним узлом в V '
• ...
• N-й шаг: попробуйте сопоставить один узел в V с одним новым узлом в V ', если вы не можете вернуться на один шаг назад в дереве и попробовать новое совпадение на предыдущем шаге... и если вы не можете вернуться снова и т. Д....
• ...
• КОНЕЦ: когда вы найдете лист, то есть когда вы прошли все узлы в V 'или когда вы прошли все дерево, не найдя лист.

пример

Вот пример, алгоритм продолжить слева направо от дерева.

"A <-> B" означает сопоставить узел A из V с узлом B из V '

Надеюсь, я ясен, и это то, что вы ищете.

Answer 2

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