Tomasz Czekala

Kamil Ślesiński

Izomorfizm grafów acyklicznych skierowanych z kolorowymi wierzchołkami

I. Przedstawienie problemu i opis jego rozwiÄ…zania

Problem polega na stworzeniu efektywnego algorytmu stwierdzającego czy dwa grafy acykliczne skierowane z kolorowymi wierzchołkami są izomorficzne.

Problem rozstrzygania izomorficzności dwóch grafów należy do klasy NP, ale prawdopodobnie nie jest problemem NP-zupełnym. Z drugiej strony, nie są znane wielomianowe algorytmy deterministyczne, probabilistyczne, ani kwantowe rozwiązujęce ten problem. Niemniej jednak, dla wielu specjalnych klas grafów izomorfizm może zostać rozstrzygnięty w czasie wielomianowym. Dla naszej klasy problemów staraliśmy się skonstruować algorytm działający jak najszybciej, składający się z dwóch części: jednej działającej w czasie wielomianowym, a drugiej w czasie wykładniczym. Staraliśmy się tak zoptymalizować część wielomianową, aby część działająca w czasie wykładniczym miała jak najmniej danych do przetworzenia.

Algorytm wygląda następująco:

1) Wczytujemy dwa grafy do sprawdzenia. „W” - wejÅ›ciowy i „R”- referencyjny.

2) Dokonujemy wstępnego, szybkiego, liniowego sprawdzenia czy grafy mogą być izomorficzne. Sprawdzamy liczność wierzchołków, krawędzi i kolorów.

3) Z grafów W i R tworzymy grafy o przeciwnie skierowanych krawędziach, odpowiednio OW - odwrócony wejściowy i OR - odwrócony referencyjny.

4) Dzielimy wszystkie grafy na warstwy w następujący sposób:

a) W warstwie pierwszej znajduję się wierzchołki do których nie wchodzą krawędzie.

b) W warstwie n-tej znajdują się wierzchołki, które nie znajdują się w poprzednich warstwach, do których dochodzą krawędzie z warstwy n-1.

5) Dokonujemy porównania warstw oryginalnych i odwróconych. W implementacji nie tworzymy oddzielnych grafów, tylko każdy wierzchołek ma numer warstwy oryginalnego i odwróconego grafu, ale dla jasności w dalszej części dokumentacji będziemy nazywać to graf oryginalny W i odwrócony OW. Sprawdzamy takie rzeczy jak ilość, kolory i stopnie wierzchołków w odpowiednich warstwach grafów oryginalnych; jednocześnie dla każdego wierzchołka z grafów W i OW tworzymy listę wierzchołków z grafów R i OR, które mogą im odpowiadać; na tym etapie algorytmu istnieje duże prawdopodobieństwo odrzucenia izomorfizmu grafów lub znalezienia jednoznacznie określonych wierzchołków.

Przykład, gdzie podział na warstwy (i odwrócenie krawędzi!) jest przydatne został przedstawiony na poprzednim diagramie w punkcie 4.b. Widać, iż na grafach odwróconych pojawiła się warstwa z tylko jednym wierzchołkiem.

6) Dla każdego wierzchołka z W i OW bierzemy część wspólną list możliwych, odpowiadających im wierzchołków z R i OR (dzięki nie tworzeniu w programie grafu odwróconego, ten iloczyn jest wykonywany automatycznie przy porównywaniu wierzchołków). Dzięki temu, prawdopodobnie bardzo, zawężamy ilość kombinacji do sprawdzenia. Istnieje również szansa, że na tym etapie dostaniemy kolejne, jednoznacznie zidentyfikowane, odpowiadające sobie wierzchołki z W i R.

7) Na tym etapie, każdy wierzchołek z grafów W i OW ma przypisaną listę możliwych wierzchołków z R i OR. Istnieje również szansa, że niektóre wierzchołki będą zidentyfikowane jednoznacznie. Na podstawie jednoznacznie wyznaczonych wierzchołków staramy się wyznaczyć jednoznacznie kolejne wierzchołki. Jest to proces iteracyjny. Gdy nie jesteśmy w stanie wyznaczyć więcej wierzchołków to przechodzimy do kolejnego etapu.

8) Na zbiorze wierzchołków które nie zostały wyznaczone jednoznacznie (poprzednie kroki algorytmu starały się zmniejszyć liczność tego zbioru) wykonujemy proste sprawdzanie wszystkich możliwych kombinacji. Krok ten ma złożoność wykładniczą.
Na tym etapie algorytmu, wszystkie niejednoznaczne wierzchołki są podzielone na zbiory. W każdym zbiorze znajdują się wierzchołki z grafu W i R które mogą być ze sobą izomorficzne. Wierzchołki z różnych zbiorów na pewno nie są ze sobą izomorficzne. Dla tych zbiorów generujemy iteracyjnie wszystkie możliwe przypisania niejednoznacznych wierzchołków grafu W do niejednoznacznych wierzchołków grafu R. Samo podzielenie wierzchołków na takie zbiory daje bardzo wymierną korzyść. Przykładowo: dla grafu o 12 wierzchołkach bez podziału na takie zbiory istnieje 12! kombinacji - 479001600. Gdyby udało się podzielić wierzchołki chociaż na 3 zbiory po 4 elementy to mamy tylko (4!)^3 = 13824 kombinacji do sprawdzenia.

9) Jeśli nie udało się wyznaczyć jednoznacznie wszystkich wierzchołków, lub nie istnieje kombinacja wierzchołków która spełnia założenia izomorficzności W i R to grafy nie są izomorficzne.

II. Analiza poprawności i złożoności algorytmu

Cały proces składa się z kilku niezależnych kroków, więc trzeba je po kolei opisać.

1. Wczytanie - algorytm oczywisty, złożoność O(n + m)

2. Wstępne sprawdzenie podstawowych danych statystycznych (ilość wierzchołków danego koloru, itp.) - wymaga jedynie zliczenia odpowiednich parametrów, złożoność O(n + m)

3. Tworzenie grafu odwrotnego - kopia wierzchołków i krawędzi, tylko odwracamy krawędzie. Złożoność O(n + m). My jednak tego nie robimy.

4. Dzielenie na warstwy - Przeszukiwanie wszerz mając na początku kolejki wszystkie wierzchołki, do których nie wchodzą krawędzie. Złożoność O(n + m).

5. Porównanie warstw - Sprawdzamy każdy z każdym. Złożoność O(k^2), gdzie k jest ilością wierzchołków w warstwie. Budujemy zbiory wierzchołków niejednoznacznych.

6. Porównanie grafu wejściowego i odwróconego. Dzięki odpowiednio dobranej strukturze nie robi się to automatycznie.

7. Szukanie jednoznacznych wierzchołków na podstawie jednoznacznych. Ze względu na to, jakie grafy będziemy dostawać w programie użytkowym, zdecydowaliśmy się zrobić tylko sprawdzanie, czy wierzchołek niejednoznaczny na jednoznacznego rodzica/dziecko, który ma tylko 1 dziecko/rodzica danego stopnia. W praktyce w grafach które będziemy sprawdzać dochodząc do tego etapu będzie bardzo mało wierzchołków niejednoznacznych i zapewne będą one mogły być wyeliminowane w podany sposób, chociażby dlatego, że kolory rzadko się będą powtarzać.

8. Sprawdzanie wszystkich pozostałych możliwości. Złożoność O(k! ^ (n / k)).

III. Opis programu

Algorytm został zaimplementowany z myślą o integracji z większą aplikacją, a zatem jest w formie kodu źródłowego. Podstawowa funkcjonalność to funkcja assessIsomorphismBetweenGraphs klasy GraphUtilities, która sprawdza czy dane grafy są izomorficzne. Dodatkowo, nasza biblioteka udostępnia funkcję hasError która może służyć do sprawdzania czy graf zawiera cykl, krawędzie wielokrotne oraz czy jego krawędzie są poprawnie zdefiniowane.

Ze względu na swoją charakterystykę nasza biblioteka nie posiada UI. Jej działanie można obejrzeć i przetestować za pomocą dołączonych (bądź własnych) testów jednostkowych. Załączone testy zostały opisane w rozdziale V.

IV. Opis techniczny programu

Wszelkie złożone operacje zostały opatrzone stosownymi komentarzami w kodzie.

V. Opis testów

Testowanie swojego algorytmu oparliśmy głównie na testach jednostkowych (JUnit). Testowane były zarówno algorytmy pomocnicze (np. iteracyjne generowanie permutacji) jak i algorytmy które same stworzyliśmy. W miarę możliwości tworzone były testy automatyczne, np. automatyczne permutowanie grafu i sprawdzanie czy funkcja sprawdzająca izomorficzność zwraca poprawny wynik, niemniej jednak, niektóre testy były preparowane ręcznie w celu sprawdzenia konkretnych właściwości algorytmu. Stworzone były również testy wydajnościowe.

Poniżej zamieszczona została lista klas wraz z opisami testów które zawierają.

1. PermutationsTest

a) test() - testuje klasę PossibilitySet oraz funkcję służącą do generowania permutacji zbioru 8-elementowego; wynik działania wypisywany na konsolę

2. GraphNodePermutationsTest

a) graphNodePermutations() - testuje funkcję PermuteGraphNodes klasy PermutationsGenerator; wynik działania wypisywane na konsolę

3. SimpleTest

a) allPermutations() - testujemy algorytm na grafach, które wymagają sprawdzania wszystkich kombinacji

b) cycleTest1() - sprawdzamy czy dane grafy mają cykle; jest to test funkcji dodatkowej, nie sprawdza izomorficzności

c) efficiencyTest1() - 100'000 razy sprawdzamy izomorficzność takich grafów, jak w punkcie g); zajmuje to około jednej sekundy

d) efficiencyTest2() - budujemy 2 długie grafy (podwójne listy mające łącznie 100 wierzchołków) i 10'000 razy sprawdzamy izomorfizm; wykonuje się kilka sekund

e) emptyGraphsTest() - testujemy przypadki skrajne, np. obsługę grafu pustego

f) findClearFromClear() - budujemy graf, który składa się z dwóch rozłącznych ciągów wierzchołków, przy czym 1 wierzchołek jest innego koloru. Na jego podstawie można wyznaczyć wszystkie pozostałe wierzchołki jako jednoznaczne. Sprawdzamy, czy tak się dzieje

g) isomorphismTest1() - tworzymy 2 grafy 10 elementowe, sprawdzamy ich izomorficzność z samym sobą, po czym ze sobą nawzajem. Grafy wyglądają następująco:

tylko mają inną numerację wierzchołków. Są też robione zmiany niektórych krawędzi w jednym z nich i jest sprawdzane, czy grafy nie są izomorficzne.

h) test1() - sprawdzamy, czy konstruktor naszego grafu rzuci wyjątek IllegalArgumentException jeśli dostanie niepoprawne wejście

i) test2() - sprawdzamy, czy jeśli w danej warstwie (jest tylko jedna) mamy inną ilość wierzchołków danego typu (pomiędzy grafem W i R), to czy grafy zostaną uznane za nie izomorficzne

4. AdvancedTests

a) bigGraph() - testuje graf automatycznie tworząc jego permutacje, nacisk położony na znajdowanie wierzchołków na podstawie warstw oraz na znajdowanie jednoznacznych wierzchołków na podstawie już znalezionych jednoznacznych wierzchołków

b) longGraph() - testuje permutacje grafu
, nacisk położony na porównywanie warstw

c) test1() - testuje grafy, nacisk położony na sprawdzanie wszystkich możliwych kombinacji

OW

W

R

OR

---