Алгоритм VF2 — реализация

У меня проблема с реализацией алгоритма VF2. Кажется, во многих случаях все работает отлично, однако есть проблема, которую я не могу решить.

Алгоритм не работает на примере ниже. В этом примере мы сравниваем два идентичных графика (см. изображение ниже). Начальная вершина равна 0. Множество P, вычисляемое внутри s0, хранит мощность всех пар вершин.

график

Ниже приведен псевдокод, включенный в публикации о VF2, на которых я основывал свою реализацию.

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=B51AD0DAEDF60D6C8AB589A39A570257?doi=10.1.1.101.5342&rep=rep1&type=pdf

http://www.icst.pku.edu.cn/intro/leizou/teaching/2012-autumn/papers/part2/VF2%20A%20%28sub%29Graph%20Isomorphism%20Algorithm%20For%20Matching%20Large%20Graphs.pdf

Комментарии справа от /* описывают, как я понимаю код:

Я не уверен, что создание набора P() допустимо, как описано ниже. Наборы мощности пар повторяются в лексикографическом порядке по первому, а затем по второму значению пары.

PROCEDURE Match(s)
  INPUT: an intermediate state s; the initial state s0 has M(s0)=empty
  OUTPUT: the mappings between the two graphs
  IF M(s) covers all the nodes of G2 THEN
    OUTPUT M(s)
  ELSE
    Compute the set P(s) of the pairs candidate for inclusion in M(s)
    /*by powerset of all succesors from already matched M(s) if not empty or
    /*predestors to already matched M(s) if not empty
    /*or all possible not included vertices in M(s)
    FOREACH (n, m)∈ P(s)
      IF F(s, n, m) THEN
    Compute the state s ́ obtained by adding (n, m) to M(s)
    /*add n to M1(s), exclude from T1(s)
    /*add m to M2(s), exclude from T2(s)
    /*M1(s) is now M1(s'), other structures belong to s' too
    CALL Match(s′)
      END IF
    END FOREACH
    Restore data structures
    /*Return all structures as from before foreach
  END IF
END PROCEDURE

Когда алгоритм переходит к s4, при возврате из функции он теряет информацию о хорошем совпадении вершин. Это приводит к поиску изоморфизма подграфов ({(0,0),(1,1),(2,2),(5,3),(6,4)}) - даже если графы изоморфны.

Что я здесь делаю неправильно?


graph algorithm subgraph isomorphism
person ThunderSS    schedule 09.11.2013    source источник
comment
Уже больше полугода. Вы уже нашли ответ на свой вопрос? Или просто оставить это и двигаться дальше?   -  person Jim Raynor    schedule 25.06.2014

Ответы (1)


arrow_upward
2
arrow_downward

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

У меня не было времени копаться в деталях, но я также работаю с графиками, поэтому я попробовал networkx (пакет Python) и библиотеку Boost 1.55.0 (очень обширная библиотека C++ для графиков). Ваш пример и еще один пример графа с 1000 узлов, 1500 ребер возвращают правильное сопоставление (тривиальный случай сопоставления графа с самим собой).

import networkx as nx
G1 = nx.Graph()
G2 = nx.Graph()

G1.clear()
G2.clear()

G1.add_nodes_from(range(0,7))
G2.add_nodes_from(range(0,7))
G1.add_edges_from([(0,1), (1,2), (2,3), (3,4), (2,5), (5,6)])
G2.add_edges_from([(0,1), (1,2), (2,3), (3,4), (2,5), (5,6)])

from networkx.algorithms import isomorphism
GM = isomorphism.GraphMatcher(G2,G1)
print GM.is_isomorphic()
GM.mapping

Истинный

Исход[39]: {0:0, 1:1, 2:2, 3:3, 4:4, 5:5, 6:6}

person Jim Raynor    schedule 25.06.2014