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

Question

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

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

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

Answer 1

Я не уверен, что это то, что вы ищете, но алгоритм VF2 работает следующим образом.

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

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

Алгоритм:

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

Пример

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

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

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

Answer 2

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