W jaki sposób przeprowadzasz test jednostkowy przy użyciu struktur grafów?

Piszę (rekurencyjny) kod, który porusza się po wykresie zależności, szuka cykli lub sprzeczności w zależnościach. Nie jestem jednak pewien, jak podejść do testowania tego urządzenia. Problem polega na tym, że jednym z naszych głównych problemów jest to, czy kod poradzi sobie ze wszystkimi interesującymi strukturami graficznymi, które mogą powstać, i upewniając się, że wszystkie węzły będą obsługiwane odpowiednio.

Chociaż zwykle 100% zasięgu linii lub gałęzi jest wystarczające, aby mieć pewność, że jakiś kod działa, wydaje się, że nawet przy 100% pokryciu ścieżki nadal masz wątpliwości.

Jak więc wybierać struktury wykresów dla przypadków testowych, aby mieć pewność, że ich kod poradzi sobie z wszystkimi możliwymi kombinacjami, jakie można znaleźć w rzeczywistych danych.

PS - jeśli to ma znaczenie, wszystkie krawędzie na moim wykresie są oznaczone „musi mieć” xor ”nie może mieć” i nie ma żadnych trywialnych cykli, a pomiędzy dwoma dowolnymi węzłami jest tylko jedna krawędź.

PPS - To dodatkowe stwierdzenie problemu zostało pierwotnie opublikowane przez autora pytania w komentarzu poniżej:

For all vertices N in forest F, for all vertices M, in F, such that if there are any walks between N and M they all must either use only edges labelled 'conflict' or 'requires'.

Cały czas myślimy, że mamy wszystkie trudne, a potem zdajemy sobie sprawę, że pewna struktura powoduje problemy, których wcześniej nie rozważaliśmy. Testujemy każdy podstęp, jaki możemy wymyślić.

To brzmi jak dobry początek. Wydaje mi się, że próbowałeś już zastosować niektóre klasyczne techniki, takie jak analiza wartości granicznej lub podział na równoważności , jak już wspomniałeś o testowaniu opartym na zasięgu. Po zainwestowaniu dużo czasu w budowanie dobrych przypadków testowych dojdziesz do momentu, w którym Ty, Twój zespół, a także testerzy (jeśli je masz) nie mają pomysłów. I to jest punkt, w którym powinieneś opuścić ścieżkę testowania jednostkowego i rozpocząć testowanie z jak największą ilością rzeczywistych danych.

Powinno być oczywiste, że powinieneś spróbować wybrać dużą różnorodność wykresów z danych produkcyjnych. Być może musisz napisać dodatkowe narzędzia lub programy tylko dla tej części procesu. Trudność polega tu prawdopodobnie na sprawdzeniu poprawności danych wyjściowych programów, gdy umieścisz w swoim programie dziesięć tysięcy różnych wykresów świata rzeczywistego, skąd będziesz wiedzieć, czy Twój program zawsze wytwarza poprawne dane wyjściowe? Oczywiście nie można tego sprawdzić niż ręcznie. Więc jeśli masz szczęście, możesz być w stanie wykonać drugą, bardzo prostą implementację kontroli zależności, która może nie spełniać twoich oczekiwań dotyczących wydajności, ale jest łatwiejsza do zweryfikowania niż oryginalny algorytm. Powinieneś także spróbować zintegrować wiele kontroli wiarygodności bezpośrednio w swoim programie (na przykład

Na koniec naucz się akceptować fakt, że każdy test może tylko udowodnić istnienie błędów, ale nie ich brak.

1. Randomizowane generowanie testów

Napisz algorytm, który generuje wykresy, niech wygeneruje kilkaset (lub więcej) losowych wykresów i rzuci każdy na swój algorytm.

Zachowaj losowe ziarno wykresów, które powodują interesujące awarie i dodaj je jako testy jednostkowe.

2. Trudne fragmenty kodu

Niektóre struktury wykresów, o których wiesz, że są trudne, możesz od razu zakodować lub napisać kod, który je połączy i wypchnie do algorytmu.

3. Wygeneruj wyczerpującą listę

Ale jeśli chcesz mieć pewność, że „kod może obsłużyć wszystkie możliwe permutacje, które znajdziesz w danych ze świata rzeczywistego”, musisz wygenerować te dane nie z losowych nasion, ale przechodząc przez wszystkie permutacje. (Odbywa się to podczas testowania systemów sygnałów kolei metra i daje ogromną liczbę przypadków, których testowanie zajmuje całe wieki. W metrze metra system jest ograniczony, więc istnieje górna granica liczby permutacji. Nie wiem, jak twoja sprawa dotyczy)

Żadne testy nie będą w tym przypadku wystarczające, nawet tony danych z prawdziwego świata lub fuzzing. 100% pokrycia kodu, a nawet 100% pokrycia ścieżki jest niewystarczające do przetestowania funkcji rekurencyjnych.

Albo funkcja rekurencyjna wytrzymuje formalny dowód (w tym przypadku nie powinno być tak trudna), albo nie. Jeśli kod jest zbyt spleciony z kodem specyficznym dla aplikacji, aby wykluczyć skutki uboczne, to od czego zacząć.

Sam algorytm brzmi jak prosty algorytm zalewania, podobny do prostego szerokiego pierwszego wyszukiwania, z dodatkiem czarnej listy, która nie może przecinać się z listą odwiedzanych węzłów, uruchamianą ze wszystkich węzłów.

foreach nodes as node
    foreach nodes as tmp
        tmp.status = unmarked

    tovisit = []
    tovisit.push(node)
    node.status = required

    while |tovisit| > 0 do
        next = tovisit.pop()
        foreach next.requires as requirement
            if requirement.status = unmarked
                tovisit.push(requirement)
                requirement.status = required
            else if requirement.status = blacklisted
                return false
        foreach next.collides as collision
            if collision.status = unmarked
                requirement.status = blacklisted
            else if requirement.status = required
                return false
return true

Ten iteracyjny algorytm spełnia warunek, że żadna zależność nie może być wymagana i jednocześnie umieszczona na czarnej liście, dla grafów o dowolnej strukturze, zaczynając od dowolnego dowolnego artefaktu, przy czym artefakt początkowy jest zawsze wymagany.

Chociaż może, ale nie musi być tak szybki, jak twoja własna implementacja, można udowodnić, że kończy się we wszystkich przypadkach (ponieważ dla każdej iteracji zewnętrznej pętli każdy element może zostać wypchnięty tylko raz do tovisitkolejki), zalewa cały osiągalny wykres (dowód indukcyjny) i wykrywa wszystkie przypadki, w których artefakt musi być wymagany i umieszczony na czarnej liście jednocześnie, zaczynając od każdego węzła.

Jeśli możesz wykazać, że twoja implementacja ma te same cechy, możesz udowodnić poprawność bez konieczności przeprowadzania testów jednostkowych. Tylko podstawowe metody wypychania i wyskakiwania z kolejek, liczenia długości kolejek, iteracji właściwości i tym podobne muszą zostać przetestowane i wykazane, że są wolne od skutków ubocznych.

EDYCJA: Czego algorytm nie dowodzi, to że wykres jest wolny od cykli. Kierowane wykresy acykliczne są jednak dobrze zbadanym tematem, więc znalezienie gotowego algorytmu potwierdzającego tę właściwość również powinno być łatwe.

Jak widać, w ogóle nie ma potrzeby wymyślania nowego koła.

Używasz wyrażeń takich jak „wszystkie interesujące struktury grafów” i „odpowiednio obsługiwane”. O ile nie masz możliwości przetestowania kodu względem wszystkich tych struktur i ustalenia, czy kod odpowiednio obsługuje wykres, możesz używać tylko takich narzędzi, jak analiza pokrycia testowego.

Sugeruję, aby zacząć od znalezienia i przetestowania szeregu interesujących struktur graficznych i ustalenia, jaka byłaby odpowiednia obsługa, i zobaczenia, że ​​kod to robi. Następnie możesz zacząć zaburzać te wykresy na: a) uszkodzone wykresy, które naruszają reguły lub b) niezbyt interesujące wykresy, które mają problemy; sprawdź, czy Twój kod poprawnie ich nie obsługuje.

Możesz spróbować wykonać sortowanie topologiczne i sprawdzić, czy się powiedzie. Jeśli nie, masz co najmniej jeden cykl.

Jeśli chodzi o ten trudny do przetestowania algorytm, wybrałbym TDD, gdzie budujesz algorytm na podstawie testów,

W skrócie TDD,

• napisz test
• widzę, że to zawodzi
• zmodyfikuj kod
• upewnij się, że wszystkie testy przeszły pomyślnie
• refaktor

i powtórz cykl,

W tej konkretnej sytuacji

1. Pierwszym testem byłby wykres z jednym węzłem, w którym algorytm nie powinien zwracać żadnych cykli
2. Drugi to wykres z trzema węzłami bez cyklu, w którym algorytm nie powinien zwracać żadnych cykli
3. Kolejnym byłoby użycie wykresu trzech węzłów z cyklem, w którym algorytm nie powinien zwracać żadnych cykli
4. Teraz możesz przetestować go w nieco bardziej złożonym cyklu w zależności od możliwości

Jednym z ważnych aspektów tej metody jest to, że zawsze należy dodać test dla możliwego kroku (w którym możliwe jest podzielenie możliwych scenariuszy na proste testy), a po uwzględnieniu wszystkich możliwych scenariuszy zwykle algorytm ewoluuje automatycznie.

Na koniec musisz dodać jeden lub więcej skomplikowanych testów integracji, aby sprawdzić, czy występują jakieś nieprzewidziane problemy (takie jak błędy przepełnienia stosu / błędy wydajności, gdy wykres jest bardzo duży i gdy używasz rekurencji)

Moje rozumienie problemu, jak pierwotnie stwierdzono, a następnie zaktualizowano w komentarzach pod odpowiedzią Macke, obejmuje następujące elementy: 1) kierowane są oba typy krawędzi (zależności i konflikty); 2) jeżeli dwa węzły są połączone jedną krawędzią, nie mogą być połączone inną, nawet jeśli jest innego typu lub odwrotnie; 3) jeśli można zbudować ścieżkę między dwoma węzłami przez zmieszanie krawędzi różnych typów, wówczas jest to błąd, a nie okoliczność, która jest ignorowana; 4) Jeśli istnieje ścieżka między dwoma węzłami używającymi krawędzi jednego typu, wówczas może nie być innej ścieżki między nimi przy użyciu krawędzi drugiego typu; 5) cykle jednego typu krawędzi lub mieszane typy krawędzi są niedozwolone (na podstawie wniosku, nie jestem pewien, czy cykle tylko konfliktu są błędem, ale ten warunek można usunąć, jeśli nie).

Ponadto założę, że zastosowana struktura danych nie zapobiega wyrażaniu naruszeń tych wymagań (na przykład wykres 2 naruszający warunek nie mógłby zostać wyrażony na mapie od pary węzłów do (typ, kierunek), jeśli para węzłów zawsze ma najpierw najmniej numerowany węzeł.) Jeśli nie można wyrazić określonych błędów, zmniejsza liczbę przypadków do rozważenia.

W rzeczywistości można tu wziąć pod uwagę trzy wykresy: dwa wyłącznie jednego typu krawędzi i wykres mieszany utworzony przez połączenie jednego z każdego z dwóch typów. Możesz użyć tego do systematycznego generowania wszystkich wykresów do pewnej liczby węzłów. Najpierw wygeneruj wszystkie możliwe wykresy N węzłów mających nie więcej niż jedną krawędź między dowolnymi dwiema uporządkowanymi parami węzłów (uporządkowane pary, ponieważ są to wykresy ukierunkowane). Teraz weź wszystkie możliwe pary tych wykresów, jedna reprezentująca zależności, a druga reprezentująca konflikty, oraz tworzą związek każdej pary.

Jeśli twoja struktura danych nie jest w stanie wyrazić naruszenia warunku 2, możesz znacznie zmniejszyć przypadki, które należy wziąć pod uwagę, konstruując tylko wszystkie możliwe wykresy konfliktów, które mieszczą się w przestrzeniach wykresów zależności, i odwrotnie. W przeciwnym razie można wykryć naruszenia warunku 2 podczas tworzenia związku.

Podczas pierwszego przejścia połączonego wykresu z pierwszego węzła możesz zbudować zestaw wszystkich ścieżek do każdego osiągalnego węzła, a gdy to zrobisz, możesz sprawdzić naruszenia wszystkich warunków (w celu wykrycia cyklu możesz użyj algorytmu Tarjana .)

Wystarczy wziąć pod uwagę ścieżki z pierwszego węzła, nawet jeśli wykres jest odłączony, ponieważ ścieżki z dowolnego innego węzła pojawią się jako ścieżki z pierwszego węzła w innym przypadku.

Jeśli ścieżki o mieszanej krawędzi można po prostu zignorować, a nie są błędami (warunek 3), wystarczy rozważyć niezależnie wykresy zależności i konfliktów oraz sprawdzić, czy jeśli węzeł jest osiągalny w jednym, nie ma go w drugim.

Jeśli pamiętasz ścieżki znalezione podczas badania wykresów N-1 węzłów, możesz użyć ich jako punktu wyjścia do generowania i oceny wykresów N węzłów.

Nie generuje to wielu krawędzi tego samego typu między węzłami, ale można to rozszerzyć. Znacznie zwiększyłoby to jednak liczbę przypadków, więc byłoby lepiej, gdyby testowany kod uniemożliwiał przedstawienie lub, w przeciwnym razie, odfiltrowanie wszystkich takich przypadków wcześniej.

Kluczem do napisania takiej wyroczni jest utrzymanie jej tak prostym, jak to możliwe, nawet jeśli oznacza to nieefektywność, abyś mógł w nią zaufać (najlepiej poprzez argumenty za jej poprawnością, poparte testami).

Gdy będziesz już w stanie wygenerować przypadki testowe i zaufasz stworzonej wyroczni, aby dokładnie oddzielić dobro od zła, możesz użyć tego do przeprowadzenia automatycznego testowania kodu docelowego. Jeśli nie jest to wykonalne, następną najlepszą opcją jest przeczesanie wyników dla wyróżniających się przypadków. Wyrocznia może klasyfikować znalezione błędy i udzielać informacji o zaakceptowanych przypadkach, takich jak liczba i długość ścieżek każdego typu oraz czy istnieją jakieś węzły na początku obu typów ścieżek, i to może pomóc w znalezieniu przypadków, których wcześniej nie widziałeś.