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

9567
wyświetleń
Zastosowanie teorii grafów Hamiltona w projektowaniu oraz testowaniu aplikacji [aktualizacja]
Jest wiele teorii oraz artykułów na temat testowania. Ludzie starają się szukać jak najlepszych sposobów zaprojektowania systemów komputerowych pod kątem ich późniejszych testów użyteczności oraz testów funkcjonalnych. Artykuł przedstawia nieco matematyczne podejście dotyczące testowania z wykorzystaniem teorii grafów oraz cykli Hamiltona.
 
Wstęp

Testowanie aplikacji  nie jest oczywistą i prostą pracą. W praktyce bardzo często brakuje czasu na to, aby „optymalnie” przetestować aplikację, zanim trafi ona do klienta.  Z tym problemem spotyka się sporo firm informatycznych oraz programistycznych. Ostatnimi czasy testowanie oprogramowania stało się bardzo gorącym tematem. Jest to problem, który próbują rozwiązać potężne umysły. Oczywisty jest fakt, że nikt nie może przetestować całej aplikacji od początku do końca, ponieważ czas testów wielokrotnie przekraczałby długość życia oprogramowania lub byłoby to nieopłacalne. Nawet testy automatyczne nie są w stanie zapewnić pełnego pokrycia wszystkich możliwych kombinacji funkcjonalności oraz danych w programie. Pojawia się pytanie: Jak zaprojektować testy i jak napisać przypadki testowe, aby najbardziej optymalnie sprawdzić, czy wszystkie funkcje w aplikacji działają prawidłowo? Jak najbardziej optymalnie sprawdzić przenaszalność danych pomiędzy stanami?

Można zoptymalizować testowanie, gdy ograniczymy się do takiego zaprojektowania systemu oraz napisania przypadków testowych, w którym wykorzystujemy cykl Hamiltona w grafie przepływu danych, w grafie stanów lub w grafie przenaszalności danych pomiędzy stanami zdefiniowanymi oraz zaprojektowanymi w danym systemie informatycznym.

Przedstawione podejście można stosować na każdym poziomie testów oraz na każdym poziomie projektowania systemu, np. poprzez wykorzystanie modelu V(fazy testów są powiązane z fazami projektowania oraz wytwarzania oprogramowania).

 

Grafy Hamiltona ich własności

Zaprezentujmy niezbędne wiadomości, które należy poznać w celu zrozumienia  najważniejszego problemu opisywanego w następnym rozdziale, a mianowicie zastosowania teorii grafów Hamiltona podczas projektowania systemów informatycznych oraz przypadków testowych. Zaczniemy od cykli Hamiltona: 

Definicja 1. Cykl Hamiltona to taki cykl w grafie, w którym każdy wierzchołek grafu przechodzony jest tylko jeden raz (oprócz pierwszego wierzchołka). Ścieżka Hamiltona (ang. Hamiltonian path) jest taką ścieżką w grafie, która odwiedza każdy jego wierzchołek dokładnie jeden raz.

Znalezienie cyklu Hamiltona o minimalnej sumie wag krawędzi jest równoważne rozwiązaniu problemu komiwojażera. Grafy zawierające cykl Hamiltona nazywamy hamiltonowskimi. Graf hamiltonowski to graf rozważany w teorii grafów zawierający ścieżkę (drogę) przechodzącą przez każdy wierzchołek dokładnie jeden raz zwaną ścieżką Hamiltona. W szczególności grafem hamiltonowskim jest graf zawierający cykl Hamiltona, tj. zamkniętą ścieżkę Hamiltona.
 

Definicja 2. Grafem spójnym nazywamy graf spełniający warunek, że dla każdej pary wierzchołków istnieje ścieżka, która je łączy.

 

Przykład 1. 

 
 
 
Graf ten jest spójny, więc zgodnie z definicją ma jedną spójną składową. Po usunięciu krawędzi 2-3 i 4-5 graf ten nie jest już spójny.
 

W celu łatwiejszego zrozumienia kolejnych rozdziałów należy znać dwie poniżej przedstawione definicje:

Definicja 3. Spójną składową grafu nieskierowanego G jest spójny podgraf grafu G nie zawarty w większym podgrafie spójnym grafu G. Innymi słowy spójna składowa grafu jest to taki podgraf, który można "wydzielić" z całego grafu bez usuwania krawędzi. Graf spójny ma jedną spójna składową. 

Definicja 4. Grafem prostym nazywamy graf bez pętli własnych i krawędzi wielokrotnych. Często określenie graf (bez przymiotników) oznacza graf prosty.

 
Przykład 2. 
 
 
 
Graf skierowany posiadający ścieżkę Hamiltona. Niebieskie kropki to wierzchołki grafu, strzałki to krawędzie grafu, a ścieżkę Hamiltona oznaczono kolorem czerwonym.
 
 
Przykład 3. 
 
 
Przykładowy cykl Hamiltona w grafie dwunastościanu foremnego.
 
 

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.

Istnieją twierdzenia pozwalające na podstawie cech grafu, dostępnych w czasie liniowym, stwierdzić jednoznacznie, że dany graf jest hamiltonowski. Należy pamiętać, że jest to implikacja jednostronna - istnieje nieskończenie wiele grafów hamiltonowskich, które nie mają poniższych cech. Twierdzenia te są matematycznym obrazem dość naturalnej obserwacji dotyczącej własności grafów - jest logiczne, że im więcej jest krawędzi w grafie, tym "większe są szanse" na znalezienie wśród nich drogi Hamiltona. W skrócie (i nieformalnie), poniższe twierdzenia mówią, że graf jest hamiltonowski, jeżeli tylko ma on odpowiednio dużo krawędzi w stosunku do ilości wierzchołków. Najbardziej znane twierdzenia z tego zakresu to: 
 

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.

Powyższy algorytm produkuje ścieżki i cykle Hamiltona w kierunku odwrotnym do ich przebywania. Dla grafu nieskierowanego nie ma to znaczenia. W grafie skierowanym należy tę kolejność odwrócić. Stos można w prosty sposób zrealizować w dynamicznej tablicyn elementowej. Wtedy bez problemu da się odczytywać wierzchołki cyklu w kolejności ich przebywania.

 

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:

n liczba wierzchołków w grafie, 
graf zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
v bieżący wierzchołek grafu, 
visited n elementowa tablica odwiedzin,

S stos wierzchołków,

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

4) Elementy pomocnicze:

test zmienna logiczna do testowania cyklu lub ścieżki Hamiltona,

u wierzchołek grafu.

 

Liczba kroków w algorytmie:

K01:

S.push(v)

; umieszczamy v na stosie

K02:

JeśliSzawiera mniej niż n wierzchołków, to idź do K10

; mamy ścieżkę Hamiltona?

K03:

test← false

; zakładamy brak cyklu Hamiltona

K04:

Dlakażdego sąsiada u wierzchołka v, wykonuj K05

; przeglądamy sąsiadów v

K05:

    Jeśliu = 0, totest ← true i idź do K06

 

K06:

Jeślitest= true, to pisz "Cykl Hamiltona:"
inaczej                  pisz "Hamiltonian Path : "

 

K07:

Piszzawartość S bez usuwania danych z S

 

K08:

Jeślitest= true, to pisz 0

; dla cyklu dopisujemy wierzchołek startowy

K09:

Idź doK14

 

K10:

visited[v] ← true

; oznaczamy wierzchołek jako odwiedzony

K11:

Dlakażdego sąsiada u wierzchołka v, wykonuj K12

; przeglądamy sąsiadów wierzchołka v

K12:

    Jeślivisited[u] = false, toHamilton(n,graf,u,visited,S)

; dla sąsiadów nieodwiedzonych wykonujemy wywołanie rekurencyjne

K13:

visited[v] ← false

; wycofujemy się z wierzchołka v

K14:

S.pop()

; wierzchołek v usuwamy ze stosu

K15:

Zakończ

 

 

 

Zastosowanie teorii w praktyce

 

Wykorzystanie twierdzenia Ore oraz ścieżki Hamiltona w projektowaniu testów

 
Załóżmy że mamy zaprojektowany pewnąfunkcję, którą możemy przedstawić za pomocą następującego grafu:
 
 
Graf ten nie jest grafem hamiltonowskim. Liczba wierzchołków tego grafu jest równa 4. Można skorzystać z twierdzenia Orei dopisać krawędzie tak, aby spełnione było założenie twierdzenia. Wystarczy  dodać jedną krawędź i graf stanie się hamiltonowski. Krawędź możemy dodać tak, jak przedstawia poniższy graf:
 
 
Takie postępowanie jest możliwe, jeśli dodanie nowej ścieżki nie zakłóci pracy projektowanego systemu lub nie jest sprzeczne z logiką danego systemu. Algorytm, który wyznacza cykl Hamiltona, wskaże następującą ścieżkę:
 
 
Rozpatrzmy teraz następujący problem związany z przenoszeniem danych. Niżej przedstawiony graf pokazuje, jak mogą zmieniać się statusy projektów przetargów w firmach budowlanych.
 
 

Graf ten nie jest grafem Hamiltona. Statusy grafów możemy potraktować jak wierzchołki grafu. Aby przetestować przenaszalność danych pomiędzy poszczególnymi statusami, trzeba wielokrotnie przechodzić przez niektóre węzły. Możemy jednak zastanowić się, czy nie warto dodać jeszcze jednej ścieżki, tak aby nie było to niezgodne z logiką firm budowlanych. Możemy zaproponować takie podejście:

  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ć:

 
Teraz wystarczy dodać krawędź tak, jak poniżej na obrazku i graf już jest hamiltonowski:
 
 

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.

 
 
 

O autorze

Marek Żukowicz jest absolwentem matematyki na Uniwersytecie Rzeszowskim. Obecnie pracuje jako tester. Jego zainteresowania skupiają się wokół testowania, matematyki, zastosowania algorytmów ewolucyjnych oraz zastosowania matematyki w procesie testowania. Interesuje się również muzyką, grą na akordeonach oraz na perkusji.

 

Od redakcji

Jeśli chcesz podzielić się swoją wiedzą z innymi testerami, czekamy na Twój artykuł, film, komentarz, pracę dyplomową czy inną formę treści, jaką chcesz opublikować na naszych łamach.
 
 
 
 
 
 
 





 
9567
wyświetleń
Marek Żukowicz

Autor

Marek Żukowicz jest absolwentem matematyki na Uniwersytecie Rzeszowskim. Jest testerem oprogramowania w firmie Ailleron.

To powinno Cię zainteresować

Dołącz do dyskusji