W przypadku grafów nieznakowanych problemem izomorfizmu grafów można zająć się szeregiem algorytmów, które działają bardzo dobrze w praktyce. Oznacza to, że chociaż najgorszy przypadek czasu działania jest wykładniczy, zwykle ma on czas działania wielomianowego.
Miałem nadzieję, że sytuacja jest podobna w przypadku wykresów oznaczonych. Jednak naprawdę ciężko mi znaleźć jakiekolwiek odniesienie, które proponuje „praktycznie wydajny” algorytm.
Uwaga: W tym przypadku wymagamy, aby izomorfizm zachował etykiety. Oznacza to, że izomorfizm między dwoma skończonymi terminami automat / algebra procesów oznaczałby, że automaty / terminy są w zasadzie „równe aż do zmiany nazwy węzłów”.
Jedyne odniesienie, które znalazłem, to ten z Wikipedii, który stwierdza, że problem izomorfizmu wykresów znakowanych można wielomianowo zredukować do problemu zwykłych wykresów. Podstawowy artykuł dotyczy jednak bardziej teorii złożoności niż praktycznych algorytmów.
Coś mi brakuje, czy też tak naprawdę nie ma wydajnych algorytmów „heurystycznych” decydujących o tym, czy dwa oznaczone wykresy są izomorficzne?
Każda podpowiedź lub odniesienie byłoby świetne.
Odpowiedzi:
Ten artykuł może Cię zainteresować:
Aidan Hogan: Skolemizacja pustych węzłów przy jednoczesnym zachowaniu izomorfizmu. WWW 2015: 430–440
Ma algorytm (oparty na Nauty) do testowania izomorfizmu grafów RDF, które są zasadniczo ukierunkowanymi grafami oznaczonymi, które mogą zawierać stałe etykiety. Algorytm uwzględnia etykiety w celu zawężenia przestrzeni wyszukiwania.
Jeśli możesz przedstawić swój wykres wejściowy jako wykres RDF, możesz spróbować użyć powiązanego pakietu oprogramowania „
blabel
” do przetestowania izomorfizmu.źródło
Dowiedziałem się, że algorytm należy do kategorii algorytmów Weisfeiler-Lehman w wymiarze k-wymiaru i zawodzi przy zwykłych grafach. Aby uzyskać więcej tutaj:
http://dabacon.org/pontiff/?p=4148
Oryginalny post:
Wiele lat temu stworzyłem prosty i elastyczny algorytm dla dokładnie tego problemu (izomorfizm wykresu z etykietami).
Nazwałem go „Powerhash”, a aby stworzyć algorytm, potrzebowałem dwóch informacji. Pierwszym z nich jest algorytm wykresu iteracji mocy, również używany w PageRank. Druga to możliwość zastąpienia funkcji wewnętrznego kroku iteracji mocy wszystkim, co chcemy. Zastąpiłem go funkcją, która wykonuje następujące czynności dla każdej iteracji i dla każdego węzła:
W pierwszym kroku na skrót węzła wpływają jego bezpośredni sąsiedzi. W drugim kroku na skrót węzła wpływ ma sąsiedztwo oddalone od niego o 2 przeskoki. Na piątym kroku na skrót węzła będą miały wpływ otaczające go skoki sąsiedztwa. Musisz więc tylko kontynuować Powerhash dla kroków N = graph_radius. Ostatecznie cały skrót ma wpływ na wartość skrótu węzła centrum wykresu.
Aby utworzyć końcowy skrót, posortuj skróty węzłów ostatniego kroku i połącz je razem. Następnie możesz porównać końcowe wartości skrótu, aby sprawdzić, czy dwa wykresy są izomorficzne. Jeśli masz etykiety, dodaj je (podczas pierwszej iteracji) do skrótów wewnętrznych obliczanych dla każdego węzła.
Więcej informacji na ten temat można znaleźć tutaj:
https://plus.google.com/114866592715069940152/posts/fmBFhjhQcZF
Powyższy algorytm został zaimplementowany w funkcjonalnej relacyjnej bazie danych „madIS”. Kod źródłowy algorytmu można znaleźć tutaj:
https://github.com/madgik/madis/blob/master/src/functions/aggregate/graph.py
źródło