Zastosowanie teorii grafów Hamiltona w projektowaniu oraz testowaniu aplikacji [aktualizacja]

Niech Goznacza graf, V(G) zbiór jego wierzchołków, E(G) zbiór krawędzi, |A| moc zbioru, u_ipojedynczy (w tym przypadku i-ty) wierzchołek grafu a deg(v) stopień wierzchołka (liczbę kończących się w nim krawędzi). Tradycyjnie oznacza się V(G) = n oraz E(G) = m, zapis {v,u} będący zbiorem dwuelementowym wierzchołków, używa się do oznaczenia krawędzi między viu.

Twierdzenie 1 (Ore). Jeżeli w grafie prostym G o n wierzchołkach, n > 2, zachodzi następująca nierówność:

deg(v) + deg(u)  ≥ n – 1,

dla każdej pary niepołączonych bezpośrednio krawędzią wierzchołków u i v, to graf G posiada cykl Hamiltona.

Twierdzenie 2 (Diraca). Jeśli graf G nie ma pętli, ani krawędzi wielokrotnych (jest grafem prostym) i 

|V(G)| ≥ 3 oraz jeśli  deg(v)≥ (|V(G)|)/2 dla każdego wierzchołka w G, to jest on hamiltonowski.

Aby graf mógł posiadać cykl Hamiltona, musi być spójny – jest to oczywiste. W grafie niespójnym istnieją wierzchołki, pomiędzy którymi brak ścieżki, zatem nie można ich odwiedzić. Można podać prosty algorytm rekurencyjny znajdowania wszystkich cykli i ścieżek Hamiltona, jednakże posiada on złożoność O(n!), co czyni go zupełnie niepraktycznym dla większych grafów (zawierających powyżej 30 wierzchołków). Zasada działania naszego algorytmu jest następująca:

za pomocą odpowiednio zmodyfikowanej procedury przeglądamy graf począwszy od wierzchołka nr 0 (wybór wierzchołka nie ma znaczenia, ponieważ możliwa ścieżka lub cykl Hamiltona musi przechodzić przez wszystkie wierzchołki grafu). Przetwarzany wierzchołek umieszczamy na stosie. Następnie sprawdzamy, czy stos zawiera n wierzchołków. Jeśli tak, to otrzymaliśmy ścieżkę Hamiltona. W takim przypadku sprawdzamy, czy ostatni wierzchołek ścieżki jest połączony krawędzią z wierzchołkiem nr 0. Jeśli tak, to ścieżka tworzy cykl Hamiltona - wyprowadzamy jej zawartość ze stosu (dla cyklu dodatkowo dodajemy na końcu wierzchołek 0), usuwamy ostatni wierzchołek ze stosu i wycofujemy się na wyższy poziom rekurencji, gdzie będą rozważone inne ścieżki lub cykle Hamiltona.

Jeśli stos nie zawiera n wierzchołków, to rekurencyjnie wywołujemy procedurę szukającą ścieżki dla wszystkich nieodwiedzonych sąsiadów. Wierzchołek usuwamy ze stosu i kasujemy informację o jego odwiedzeniu, po czym wycofujemy się na wyższy poziom rekurencji.

Algorytm  wyszukiwania ścieżki Hamiltona

Przykładowy algorytm znajdujący ścieżkę Hamiltona w grafie może mieć następującą postać:

1) Funkcja rekurencyjna Hamilton (n, graf, v, visited, S)

2) Wejście:

S – stos wierzchołków,

3) Wyjście: Wszystkie cykle i ścieżki Hamiltona w grafie,

4) Elementy pomocnicze:

u – wierzchołek grafu.

Liczba kroków w algorytmie:

1. założenie budowy oraz przetarg wygrany można potraktować jako jeden węzeł, ponieważ dokumenty związane już z samą budową są zupełnie innymi dokumentami niż projekt przetargu i nie są już statusem przetargu. W momencie założenia budowy, tworzymy  nowy pusty dokument, który należy wypełnić i zapisać. Przy takim podejściu graf redukuje się do siedmiu wierzchołków,
2. pomijamy przetarg zamknięty, ponieważ jest to przetarg, z którego firma zrezygnuje. Pozostaje on jedynie w bazie danych i nic się już z nim nie dzieje(dane z takiego przetargu nie są już przenoszone po zamknięciu). 

Myśląc w ten sposób, możemy zredukować graf do sześciu wierzchołków. Graf przepływu danych przyjmie następującą postać:

Dodana została możliwość odrzucania projektu w przygotowaniu. Ścieżka Hamiltona dla tego grafu wygląda następująco:

Przegrany -> W przygotowaniu -> Odrzucony -> Złożony -> Wygrany -> Unieważniony

 

Jeśli chcemy przetestować zakładanie budowy oraz zamykanie przetargu, to wymagane będzie napisanie przypadków testowych innych, niż nasz cykl Hamiltona. Sprawę zamykania przetargu można rozwiązać w ten sposób, że dokładamy krawędź od przetargu Unieważnionego do Zamkniętego i graf będzie wtedy hamiltonowski w siedmioma wierzchołkami. Podejście takie może niekiedy poważnie wspomóc testy, ale zawsze musimy zastanowić się czy jest to opłacalne – ponieważ dodanie ścieżki to nowa funkcjonalność.

 

Ważone grafy hamiltonowskie

Zastanówmy się, co byłoby w przypadku sytuacji, gdy w stanach w systemie lub pomiędzy przepływem danych istnieje więcej niż jeden graf Hamiltona. W praktyce, zawsze istnieje w aplikacji ścieżka, którą klient wykonuje częściej, niż inne czynności. 

Problem wyboru ścieżki możemy rozwiązać za pomocą wprowadzenia wag dla krawędzi. Kwestia czy suma wag ma być największa, czy najmniejsza, zależy od kontekstu. Przedstawia to poniższy przykład:

 

 

 

a) Jeżeli chcemy najmniejszą sumę wag, to wybierzemy ścieżkę:

1 -> 2 -> 4 -> 0 -> 3,

gdzie suma wag wynosi 7,

b) Jeśli chcemy największą sumę wag, to wybierzemy ścieżkę:

0 -> 1 -> 3 -> 4  -> 2,

gdzie suma wag jest równa 13.

 

Algorytm, który sprawdza sumy wag może być analogiczny do algorytmu, który przedstawiony jest w rozdziale 3, z tą różnicą, że musi mieć dodatkowy warunek, który sprawdza sumę ścieżek po znalezieniu ścieżki Hamiltona.

 

Zadaniem testera (zgodnie z ideologią ISTQB) jest powiedzenie, że "to działa" a nie pesymistyczne podchodzenie do aplikacji, w sposób, że nic nie działa dobrze. Więc, projektowanie testów oraz aplikacji pod kątem istnienia w niej cyklu Hamiltona pozwoli zaoszczędzić czas (którego często brakuje) podczas testowania przenaszalności danych między stanami w aplikacji. Jeśli wynik testu okaże się pozytywny, to znaczy, że dane przenoszą się poprawnie i nie ma luki ani defektu pomiędzy funkcjami przejścia przez stany.

Istnienie cyklu Hamiltona (tak jak w schemacie przetargów) pozwoli również zaprojektować test automatyczny tak, że raz wprowadzamy dane i na końcu tworzymy warunki sprawdzające.