Univerza v Ljubljani
Fakulteta za raˇ cunalniˇ stvo in informatiko
Luka Kalezi´c
Orodje za doloˇ canje testnih poti z uporabo strukturnega grafa programa
DIPLOMSKO DELO
VISOKOˇSOLSKI STROKOVNI ˇSTUDIJSKI PROGRAM PRVE STOPNJE
RA ˇCUNALNIˇSTVO IN INFORMATIKA
Mentor : viˇs. pred. dr. Igor Roˇ zanc
Ljubljana, 2022
To delo je ponujeno pod licenco Creative Commons Priznanje avtorstva-Deljenje pod enakimi pogoji 2.5 Slovenija (ali novejˇso razliˇcico). To pomeni, da se tako besedilo, slike, grafi in druge sestavine dela kot tudi rezultati diplomskega dela lahko prosto distribuirajo, reproducirajo, uporabljajo, priobˇcujejo javnosti in pre- delujejo, pod pogojem, da se jasno in vidno navede avtorja in naslov tega dela in da se v primeru spremembe, preoblikovanja ali uporabe tega dela v svojem delu, lahko distribuira predelava le pod licenco, ki je enaka tej. Podrobnosti licence so dostopne na spletni strani creativecommons.si ali na Inˇstitutu za intelektualno lastnino, Streliˇska 1, 1000 Ljubljana.
Izvorna koda diplomskega dela, njeni rezultati in v ta namen razvita program- ska oprema je ponujena pod licenco GNU General Public License, razliˇcica 3 (ali novejˇsa). To pomeni, da se lahko prosto distribuira in/ali predeluje pod njenimi pogoji. Podrobnosti licence so dostopne na spletni strani http://www.gnu.org/
licenses/.
Besedilo je oblikovano z urejevalnikom besedil LATEX.
Kandidat: Luka Kalezi´c
Naslov: Orodje za doloˇcanje testnih poti z uporabo strukturnega grafa pro- grama
Vrsta naloge: Diplomska naloga na visokoˇsolskem programu prve stopnje Raˇcunalniˇstvo in informatika
Mentor: viˇs. pred. dr. Igor Roˇzanc
Opis:
Snovanje uˇcinkovitih testov programske kode je zahtevna aktivnost, ki zah- teva poglobljeno razumevanje zapisane kode in veliko izkuˇsenj. Modelira- nje programske kode s strukturnim grafom omogoˇca, da doloˇcanje testov poveˇzemo z doloˇcanjem ustreznih (testnih) poti od zaˇcetnega do konˇcnih vo- zliˇsˇc. V ta namen je definiranih veˇc vrst pokritij grafa, ki odraˇzajo razliˇcne stopnje zahtevnosti testiranja. Tak pristop lahko zelo olajˇsa delo snovalcu testov, vendar je v praksi slabo podprt z orodji.
V diplomskem delu kratko predstavite podroˇcje testiranja programske kode z uporabo strukturnih grafov. Pri tem izpostavite ˇstiri osrednja pokritja grafov strukture (pokritje vozliˇsˇc – NC, pokritje povezav – EC, pokritje pa- rov povezav – EPC in pokritje primitivnih poti – PPC) ter algoritme zanje.
Zasnujte in izdelajte programsko orodje, ki omogoˇca uˇcinkovit vnos struktur- nega grafa, preverjanje njegove pravilnosti ter doloˇcanje nabora testnih poti za vsa ˇstiri pokritja. Orodje preverite na veˇc razliˇcno zahtevnih primerih.
Iskreno se zahvaljujem viˇs. pred. dr. Igorju Roˇzancu za pomoˇc pri usmerja- nju do konca naloge in odliˇcno sodelovanje. Hvala vam za vse, kar ste storili zame.
Svojoj dragoj porodici.
Kazalo
Povzetek Abstract
1 Uvod 1
1.1 Orodja . . . 2
1.2 Napoved vsebine . . . 3
2 Pokritje grafa kode 5 2.1 Osnovni pojmi . . . 5
2.2 Pokritje vozliˇsˇc . . . 10
2.3 Pokritje povezav . . . 12
2.4 Pokritje parov povezav . . . 13
2.5 Pokritje primitivnih poti . . . 14
3 Zahteve in reˇsitev 17 3.1 Zahteve . . . 17
3.2 Naˇcrt programa . . . 18
3.3 Vmesnik . . . 18
3.4 Ozadje . . . 22
4 Analiza 29 4.1 Urejanje z navadnim izbiranjem . . . 29
4.2 Iterativno urejanje z zlivanjem . . . 35
4.3 Iterativno hitro urejanje . . . 39
5 Zakljuˇcek 45
Literatura 47
Seznam uporabljenih kratic
kratica angleˇsko slovensko
CFG Control Flow Graph graf programskega toka
NC Node Coverage pokritje vozliˇsˇc
EC Edge Coverage pokritje povezav
EPC Edge Pair Coverage pokritje parov povezav PPC Prime Path Coverage pokritje primitivnih poti
SS Selection Sort urejanje z izbiranjem
MS Merge Sort urejanje z zlivanjem
QS Quick Sort hitro urejanje
IDE IntelliJ IDEA IntelliJ IDEA
Povzetek
Naslov: Orodje za doloˇcanje testnih poti z uporabo strukturnega grafa pro- grama
Avtor: Luka Kalezi´c
V diplomski nalogi predstavljamo razvoj in programiranje orodja, ki doloˇca testne poti iz strukturnih grafov programske kode, da jih lahko uporabimo pri pisanju testov. Za programsko kodo doloˇcimo model, v naˇsem primeru strukturni graf, in na podlagi tega izberemo testne zahteve. Testne zahteve doloˇcamo z uporabo izbranega kriterija pokritja grafa. Osnovna pokritja so pokritje vozliˇsˇc – NC, pokritje povezav – EC, pokritje parov povezav – EPC in pokritje primitivnih poti – PPC. V naˇse orodje na zaˇcetku vnesemo graf s povezovanjem ˇze narisanih vozliˇsˇc. ˇCe imamo testne poti ˇze znane, lahko z naˇsim orodjem preverimo, ˇce ustrezajo izbranemu pokritju. V nasprotnem primeru orodje izpiˇse vse ugotovitve testne poti za kriterij pokritja. Testne poti izpiˇse na zaslon in shrani v datoteko. Orodje je intuitivno in preprosto za uporabo. Uspeˇsno smo ga preverili na veˇc algoritmih za urejanje. Analiza je pokazala, da orodje prihrani veliko ˇcasa v primerjavi z roˇcnim doloˇcanjem testov.
Kljuˇcne besede: testiranje programa, strukturni graf programa, pokritje grafa, pokritje voliˇsˇc – NC, pokritje povezav – EC, pokritje parov povezav – EPC, pokritje primitivnih poti – PPC.
Abstract
Title: Tool for determining test paths using a control-flow graph of a pro- gram
Author: Luka Kalezi´c
In the diploma thesis we present the development of java tool that determines the test paths from the control-flow graphs of the program code in order to use them for writing tests. We define a model for the program code, in our case a control-flow graph, and on this basis we select test requirements.
Test requirements are determined using the selected graph coverage criteria.
The basic graph coverage criterias are node coverage – NC, edge coverage – EC, edge pair coverage – EPC and primitive path coverage – PPC. At the beginning, the graph is inserted into our tool by connecting already drawn nodes. If we already have the test paths and want to check them, our tool checks them to see if they cover the selected coverage criteria. Otherwise, the tool can also provide correct test path for the coverage criteria. The correct test paths are printed and saved into a file. The tool is intuitive and easy to use. It has been successfully tested on several sorting algorithms.
The analysis showed that the tool saves a lot of time compared to manual determination of test paths.
Keywords: program testing, program structural graph, graph coverage, node coverage – NC, edge coverage – EC, edge pair coverage – EPC, primitive path coverage – PPC.
Poglavje 1 Uvod
Vsak, ki se ukvarja s programiranjem, ve, kako teˇzko je testirati program, da bi naˇsli skrito napako. Za uˇcinkovito testiranje moramo zato poskrbeti, da so testi ˇcim bolj kakovostni. Z izrazom kakovostni testi mislimo na teste, ki doseˇzejo vse dele kode in testirajo vse vrste prehodov v algoritmu.
Ko testiramo preprost program, nam je relativno jasno, kaj in kako testirati, ko pa je program veˇcji, je zelo teˇzko zagotoviti zanesljivost testov, zato je dobrodoˇsel znanstveni pristop, kjer obstajajo definirani kriteriji, ki oprede- ljujejo ustreznost testov. Ideja je zagotoviti kakovostno testiranje ne glede na vrsto programa.
Osnovni namen diplomske naloge je izdelati pripomoˇcek, ki bo pomagal pa- metneje pisati teste. Pomagal bo tako, da nas bo usmerjal do pravilne reˇsitve ali pa preprosto sam izpisal testne poti. Izhodiˇsˇce je programska koda, ki jo ˇzelimo testirati. Za programsko kodo nariˇsemo ustrezen strukturni graf in skuˇsamo po razliˇcnih kriterijih pokritja doloˇciti testne poti, ki doloˇcajo te- stne primere.
Izhodiˇsˇce za delo je knjiga ”Introduction to Software Testing” [1] avtorjev Paula Ammanna in Jeffa Offutta, v kateri so kriteriji pokritja lepo razloˇzeni.
Seveda smo najprej preverili, ˇce obstajajo orodja, ki podpirajo uporabo teh kriterijev. Reˇsitev za Python [12] doloˇca primitivne poti, naˇs cilj pa je po- kriti veˇc vrst kriterijev za Javo. Glavni cilj je implementirati popolnoma
1
2 Luka Kalezi´c delujoˇc program, ki vzame model kode (graf) kot vhod in poda testne pri- mere kot izhod ali ˇse boljˇse, vhodne parametre za klicanje funkcij. Idejna reˇsitev popolnega pristopa vkljuˇcuje naslednje korake:
1. vneseno kodo programa se prevede v strukturni graf;
2. izberemo kriterij pokritja;
3. program izdela testne poti;
4. iz testnih poti se tvorijo testni primeri ter
5. iz testnih primerov program doloˇci ustrezne vhodne parametre.
V tej nalogi smo se osredotoˇcili na implementiranje zahtev 3, 4, 5, ker sta preostala koraka preveˇc zahtevna. Kot zamenjavo za pretvorbo kode v graf smo omogoˇcili vnos in preverjanje strukturnega grafa, kjer lahko nariˇsemo graf za svoj program. Sistem doloˇcanja parametrov iz testnih primerov pred- stavljamo v poglavju 4 za tri konkretne primere.
1.1 Orodja
Program je bil izdelan v programskem jeziku Java, kot razvojno okolje smo uporabili IntelliJ IDEA.
Java [2] je preprost, uˇcinkovit in sploˇsen jezik, ki je objektno naravno in- terpretiran jezik. Java je izjemno prenosljiva. Ista Java aplikacija se bo na vseh raˇcunalnikih izvajala enako, ne glede na strojno in programsko struk- turo. Poleg prenosljivosti je druga kljuˇcna prednost Jave njen nabor varno- stnih funkcij, ki ˇsˇcitijo raˇcunalnik, in to ne le pred teˇzavami, ki jih povzroˇca napaˇcna koda, ampak tudi pred zlonamernimi programi (recimo virusi). Javo lahko ˇstejemo za prevedeni in interpretirani jezik, ker je njena izvorna koda najprej prevedena v binarno kodo. Za Javo smo se odloˇcili predvsem zato, ker imamo s programiranjem z njo najveˇc izkuˇsenj.
Diplomska naloga 3
IntelliJ IDEA [13] je integrirano razvojno okolje (IDE), ki je v veliki meri namenjeno Javi. To okolje se uporablja predvsem za razvoj programov. Raz- vilo ga je podjetje z imenom JetBrains, ki se je uradno imenovalo IntelliJ.
Na voljo je v dveh izdajah: izdaja za skupnost Community, ki jo licencira Apache 2.0, in komercialna izdaja, znana kot Ultimate Edition.
IntelliJ IDEA se razlikuje od konkurence po enostavnosti uporabe, prilago- dljivosti in obliki. Velja za eno od boljˇsih programskih orodij, ki temeljijo na Javi, tudi zaradi pomoˇci, ki olajˇsa uporabo. Ima tudi napredne funkcije preverjanja napak, ki omogoˇcajo hitrejˇse in laˇzje preverjanje napak. Intel- liJ je najbolj pomagal pri uˇcinkovitem pisanju programov, hitrem pisanju razredov, pa tudi pri enostavnem naˇcinu odpravljanja napak v kodi.
1.2 Napoved vsebine
V uvodu pojasnimo razloge in motive za izbrano temo. V drugem poglavju predstavljamo osnovne pojme in teorijo grafa, nato pa koncept pokritja v obsegu, ki je primeren za naˇs problem. Za vsak kriterij pokaˇzemo defini- cijo, kodo in razloˇzimo primer. V tretjem poglavju doloˇcimo funkcionalne in nefunkcionalne zahteve za naˇs program. Predstavljamo naˇcrt pisanja in po- stopoma opiˇsemo svojo reˇsitev. V ˇcetrtem poglavju analiziramo predlagano reˇsitev in ocenimo kakovost naˇsih rezultatov na zgledu veˇc algoritmov ure- janja. V zakljuˇcku pojasnimo ugotovitve in predstavimo ideje za nadaljnje delo.
4 Luka Kalezi´c
Poglavje 2
Pokritje grafa kode
V tem poglavju so opisani osnovni koncepti modeliranja programske kode z grafi, pokritji in algoritmi. Kljuˇcni del poglavja je opis vseh vrst pokritij na primerih.
2.1 Osnovni pojmi
2.1.1 Graf Definicija
Graf [5], je nabor vozliˇsˇc (angl. node, vertex), ki so povezana s povezavami ali robovi (angl. edge).
Opis
Veˇcina grafov je opredeljena s pomoˇcjo naslednjih pravil.
• Graf (G) je sestavljen iz dveh mnoˇzic – mnoˇzice vozliˇsˇc V in mnoˇzice povezav E.
• V je lahko konˇcna ali neskonˇcna.
5
6 Luka Kalezi´c
• Vsak element E je par, sestavljen iz dveh elementov iz V.
• G so pogosto prikazani vizualno; najprej nariˇsemo elemente V, ki so predstavljeni kot vozliˇsˇca, nato elemente E kot povezave med vozliˇsˇci.
Med v1 in v2 je povezava, ˇce je (v1, v2) element E.
Primer
:
Slika 2.1: Neusmerjen graf.
Graf na sliki 2.1 je definiran kot G (V, E), kjer je:
• V ={1, 2, 3, 4, 5, 6}
• E = {(6, 4), (4, 5), (4, 3), (3, 2), (5, 2), (2, 1), (5, 1)}
Tipi grafov
Ce so povezave v grafu usmerjene (angl. directed), torej kaˇˇ zejo samo v eno smer, se graf imenuje usmerjen graf. ˇCe so vse povezave neusmerjene (angl.
undirected), je graf neusmerjen. Primera obeh grafov sta prikazana na sliki 2.2. Pri usmerjenem grafu je tako vidna razlika v povezavah, saj so povezave narisane kot puˇsˇcice, ki oznaˇcujejo smer.
Diplomska naloga 7
Slika 2.2: Primera grafov.
2.1.2 Graf programskega toka Definicija
Strukturni graf programskega toka (angl. Control Flow Graphs – CFG) je grafiˇcni prikaz krmilnega toka ali izraˇcuna med izvaja- njem programa ali aplikacije [11].
Opis
Doloˇcimo ˇse mnoˇzico zaˇcetnih in konˇcnih vozliˇsˇc, tako da CFG definiramo kot:
• mnoˇzico vozliˇsˇc V;
• mnoˇzico zaˇcetnih vozliˇsˇc V0, kjer V0 ⊆ V in V0 == {1};
• mnoˇzico konˇcnih vozliˇsˇc Vf, kjer Vf ⊆ V in velikost Vf≥ 1;
• mnoˇzico povezav E, kjer je E podmnoˇzica V × V.
Ce CFG nima povezav, je smiseln le v primeru, ko obstaja natanˇˇ cno eno vozliˇsˇce. V primeru veˇc nepovezanih vozliˇsˇc pravimo, da CFG ni logiˇcen.
CFG bo obiˇcajno imel samo eno zaˇcetno vozliˇsˇce, medtem ko je konˇcnih vozliˇsˇc veˇc. Njegove znaˇcilnosti so:
• CFG je usmerjen graf;
8 Luka Kalezi´c
• CFG prikazuje vse poti, ki jih je mogoˇce prehoditi med izvajanjem programa;
• povezave v CFG prikazujejo poti krmilnega toka, vozliˇsˇca v CFG pa osnovne bloke (angl. basic block).
Osnovni blok je sosledje veˇc stavkov, ki se vedno izvedejo v istem zaporedju.
V CFG sta dva posebej oznaˇcena bloka: vstopni in izhodni blok. Vstopni blok se izvede prvi, izvajanje pa se zakljuˇci z izhodnim blokom. Vstopni blok v grafu vedno oznaˇcimo z enko. Izhodnih blokov je lahko veˇc in so poljubno oznaˇceni.
Primer
Preprosti algoritem:
y = args[0]
for (x = 0; x < y; x++){
y = f(x,y);
}
Slika 2.3: CFG za podan algoritem.
Zaˇcetno vozliˇsˇce (angl. start node) najprej nariˇsemo za vsak CFG. Zaˇcetno vozliˇsˇce oznaˇcuje vhod v graf. Na sliki 2.3 je vozliˇsˇce oznaˇceno z 1.
Vozliˇsˇce definicije (angl. definiton node) obiˇcajno sledi zaˇcetnemu. Vozliˇsˇce
Diplomska naloga 9 predstavlja definicije spremenljivk, ki se obiˇcajno zgodijo na zaˇcetku. Na sliki 2.3 je vozliˇsˇce oznaˇceno z 2.
Akcijska vozliˇsˇca (angl. action node) doloˇcajo tok programa, odloˇcitve algo- ritma in vrsto obnaˇsanja (recimo rekurziven ali iterativen algoritem). Stavki v kodi, kot so if, for, while, definirajo videz grafa. Na sliki 2.3 je vozliˇsˇce oznaˇceno s 3 in opisuje pogoj x <y.
Konˇcno vozliˇsˇce (angl. final node) oznaˇcuje konec programa. Konˇcnih vo- zliˇsˇc je lahko veˇc, v naˇsem primeru pa je samo eno. Na sliki 2.3 je vozliˇsˇce oznaˇceno s 5.
2.1.3 Poti
Pot (angl. path – P) je konˇcno (ali neskonˇcno) zaporedje povezav, ki pove- zuje zaporedje vozliˇsˇc v grafu [4].
Usmerjena pot (angl. directed path – DP) je pot v usmerjenem grafu, kjer so vse povezave usmerjene v smeri [4].
Preprosta pot (angl. simple path – SP) je usmerjena pot, kjer se nobeno vozliˇsˇce na poti od zaˇcetnega do konˇcnega ne ponovi. To je pot brez cikla.
Primitivna pot (angl. prime path – PP) Pot je preprosta pot, ki ni pod- pot katere koli druge primitivne poti [1].
2.1.4 Testne poti
Testna pot (angl. Test Path – TP) je pot, ki se zaˇcne v zaˇcetnem vozliˇsˇcu (N0) in se konˇca v konˇcnem vozliˇsˇcu (v Nf).
TP predstavlja izvedbo testnega primera, lahko pa ena TP ustreza tudi veˇcjemu ˇstevilu testnih primerov v programski opremi. Ce je TP neizve-ˇ
10 Luka Kalezi´c dljiva, TP ne ustreza nobenemu testnemu primeru [1].
Za graf 3.2 bi bile veljavne TP:
T P :={[1,2,3,5],[1,2,3,4,3,5],[1,2,3,4,3,4,3,5], ...}
2.1.5 Testne zahteve
Testna zahteva (angl. test requirement – tr) zahteva obisk vo- zliˇsˇca, povezave ali poti. Mnoˇzica tr je oznaˇcena z TR. V grafu je izpolnjena z vsaj eno testno potjo p v TP, izhaja iz izbranega kriterija.
Za graf 3.2 bi bile veljavne TR:
T R:={[1],[2],[3],[4],[5],[1,2],[2,3],[3,4], ...}
2.1.6 Pokritje grafa
Pokritje grafa (angl. Graph Coverage – GC): Glede na mnoˇzico TR za kriterij grafa testna pot izpolnjuje pokritje v grafu G, ˇce za vsako testno zahtevo tr v TR obstaja vsaj ena testna pot p v TP, tako da p izpolnjuje tr.
Poznamo veˇc vrst GC, ki jih bomo spoznali v nadaljevanju.
2.2 Pokritje vozliˇ sˇ c
Definicija
Pokritje vozliˇsˇc (angl. Node Coverage – NC) TR vsebujejo vsa dosegljiva vozliˇsˇca v G.
Diplomska naloga 11
Opis in primer
Najenostavnejˇse pokritje je NC, ker zahteva, da se obiˇsˇce vsako vozliˇsˇce v grafu [1]. NC bi uporabili v primerih, ko ˇzelimo preveriti, ali so vsi deli modela dosegljivi. Tu je najmanj testnih poti. Najprej doloˇcimo TR.
N C :T R={1,2,3,4,5}
Ker ˇzelimo pokriti vsa vozliˇsˇca, morajo testne zahteve vsebovati vsa vozliˇsˇca grafa. Ker je graf preprost, lahko vse testne zahteve pokrijemo z eno testno potjo.
N C :T P ={[1,2,3,4,3,5]}
Testna pot ustreza vsem testnim zahtevam. Glede na znaˇcilnosti algoritma lahko doloˇcimo parameter y, ki ustreza takˇsni testni poti. Ob pogoju y > 0 je vrednost args[0] = 1.
Psevdokoda algoritma
Za NC kriterij:
I n p u t : G1 = (V1, E1) , with {s, t} ∈ V1
O u t p u t : Set of NC Criteria , P = {p1, p2, ... ,pn} i n i t i a l i z e P = {};
for i = (|V1|) to 1 do add vi into P ; end
o u t p u t P ;
Kot vhod podamo mnoˇzici vozliˇsˇc in povezav. Algoritem je sestavljen iz ene zanke, ki obiˇsˇce vsa vozliˇsˇca iz mnoˇzice in jih doda v prazno mnoˇzico. Kot izhod dobimo mnoˇzico poti za NC pokritje (poti dolˇzine 0, z vsemi vozliˇsˇc).
12 Luka Kalezi´c
2.3 Pokritje povezav
Definicija
Pokritje povezav (angl. Edge Coverage – EC): TR vsebuje vse dosegljive poti dolˇzine niˇc (tudi vozliˇsˇca) ali ena, ki so vkljuˇcene v G.
Opis in primer
Pokritje povezav je nekoliko zahtevnejˇse od pokritja vozliˇsˇc, saj preverja if stavke. Naˇceloma, ˇce koda teh ne vsebuje, se testne poti EC ne razlikujejo od testnih poti NC. Za EC so testne zahteve vse povezave (in vozliˇsˇca).
EC :T R ={(1,2),(2,3),(3,4),(3,5),(4,3)}
EC :T P ={[1,2,3,4,3,5]}
V naˇsem primeru je TP za EC enak kot za NC, zato je edina moˇzna reˇsitev args[0] = 1.
Slika 2.4: Vozliˇsˇce 1 predstavljaif stavek.
Drugaˇcna zgodba je na sliki 2.4, kjer se kriterija NC in EC razlikujeta.
NC : TR ={ 1, 2, 3 } NC : TP ={ [1, 2, 3]}
Diplomska naloga 13 EC : TR = {(1, 2), (1,3), (2,3) }
EC : TP = { [1, 2, 3], [1, 3] }
Testne poti za NC in EC se pri tem modelu razlikujejo. EC za drugi model ima drugaˇcne testne poti od NC, ker je med vozliˇsˇcema 1 in 3 veˇc podpoti.
Psevdokoda algoritma
Za EC kriterij:
I n p u t : G1 = (V1, E1) , with {s, t} ∈ V1
O u t p u t : Set of EC Criteria , P = {p1, p2, ... , pn} i n i t i a l i z e P = {};
for i = (|E1|) to 1 do add pi into P ; end
o u t p u t P ;
Kot vhod podamo mnoˇzico vozliˇsˇc in mnoˇzico povezav. Algoritem je sesta- vljen iz ene zanke, ki obiˇsˇce vse poti (ki vsebujejo povezave) iz mnoˇzice in jih doda v prazno mnoˇzico. Kot izhod dobimo mnoˇzico poti za EC pokritje (vsa vozliˇsˇca in povezave).
2.4 Pokritje parov povezav
Definicija
Pokritje parov povezav (angl. Edge Pair Coverage – EPC): TR vsebuje vse dosegljive poti dolˇzine do dva, ki so vkljuˇcene v G.
14 Luka Kalezi´c
Opis in primer
Pokritje parov povezav je podobno EC, vendar z dodatkom, da je dolˇzina poti do dve. Pri EPC dejansko preverjamo zanke (razen vgnezdenih). Za graf na sliki 2.3 velja naslednje:
EP C :T R={(1,2,3),(2,3,4),(2,3,5),(3,4,3),(4,3,5),(4,3,4)}
EP C :T P ={[1,2,3,5],[1,2,3,4,3,4,3,5]}
Imamo dve testni poti. Prva se takoj konˇca, druga pa gre v zanko dvakrat.
To zahteva dve vrednosti args[0]. V prvem primeru je ta enaka 0, v drugem pa 2. ˇCim veˇc zahtev imamo v TR, zahtevnejˇse so testne poti.
Psevdokoda algoritma
Za EPC kriterij:
I n p u t : G1 = (V1, E1) , w i t h {s, t} ∈ V1
Output : S e t o f EC C r i t e r i a , P = {p1, p2, . . . ,pn}
i n i t i a l i z e P0 = {p1, p2, . . . ,pn} = {e1,e2, . . . , en}, ∀ei ∈ E1; for i = (|P0|) to 1 do
if pi c a n be e x t e n d e d by e d g e e∈E1 then pi += e ;
add pi i n t o P ; end
end o u t p u t P ;
Kot vhod podamo mnoˇzico vozliˇsˇc in mnoˇzico povezav. Algoritem je sesta- vljen iz ene zanke, ki obiˇsˇce vse povezave v mnoˇzici in najprej preveri, ali je ta povezava razˇsirljiva s sosednjo povezavo. ˇCe je, jo razˇsiri in doda v prazno mnoˇzico. Kot izhod dobimo mnoˇzico poti za EPC pokritje (vse pare povezav).
2.5 Pokritje primitivnih poti
Definicija
Pokritje primitivnih poti (angl. Prime Path Coverage – PPC):
TR vsebuje vsako primitivno pot v G.
Diplomska naloga 15
Opis in primer
Pokritje primitivnih poti je preprosto in elegantno merilo, ki ustrezno obrav- nava vgnezdene zanke. Pri tem zahteva, da se vsaka zanka izvede niˇckrat, enkrat ali dvakrat.
Izraˇcunajmo testne zahteve po algoritmu, ki smo ga napisali. Prve tri korake ˇze imamo (NC, EC in EPC); tu doloˇcimo poti dolˇzine 0, 1 in 2. Nadaljujemo ˇse z ostalimi poti.
N C :T R={1,2,3,4,5}
EC :T R={(1,2),(2,3),(3,4),(3,5),(4,3)}
EP C :T R={(1,2,3),(2,3,4),(2,3,5),(3,4,3),(4,3,5),(4,3,4)}
Poti dolˇzine 3 :T R={(1,2,3,4),(1,2,3,5)}
Dobili smo vse preproste poti, zdaj pa izpostavimo tiste, ki so primitivne.
Zaˇcnemo od daljˇsih in preverjamo proti krajˇsim. Izloˇcimo vse, ki se pona- vljajo v prejˇsnjih poteh.
P P C :T R={(3,4,3),(4,3,5),(4,3,4),(1,2,3,4),(1,2,3,5)}
Na koncu moramo le ˇse dopolniti poti do testnih poti (dodati pot do zaˇcetnega in konˇcnega vozliˇsˇca), ki bodo pokrivale TR.
P P C :T P ={[1,2,3,5],[1,2,3,4,3,4,3,5]}
Ker je naˇs graf preprost in vsebuje le eno zanko, so testne poti enake kot v EPC, torej ima args[0] enaki vrednosti kot tam.
2.5.1 Psevdokoda algoritma
Poglejmo zdaj psevdokodo algoritma za ustvarjanje testnih zahtev v ppc [6].
16 Luka Kalezi´c
I n p u t : G1 = (V1, E1) , w i t h {s, t} ∈ V1
Output : S e t o f Prime Paths , P = {p1, p2, . . . ,pn}
i n i t i a l i z e P0 = {p1, p2, . . . ,pn} = {e1,e2, . . . , en}, ∀ei ∈ E1; while pi ∈ P0 ∀i i s n o t e x p l o r e d do
if pi i s n o t a c y c l e then
if pi c a n be e x t e n d e d by e d g e e∈E1 then if e d o e s n o t v i s i t a v e r t e x i n pi then
pi += e ; end
end end end
s o r t P0 i n a s c e n d i n g o r d e r o f s i z e ; for i = (|P0|) to 1 do
if pi i s n o t a sub−p a t h o f any o t h e r p a t h i n P then add pi i n t o P ;
end end o u t p u t P ;
Kot vhod podamo mnoˇzico vozliˇsˇc in mnoˇzico povezav. Najprej definiramo tabelo primitivnih poti, ki vsebujejo samo povezave. Algoritem je sestavljen iz ene zanke, ki obiˇsˇce vse primitivne poti in jih ˇcim bolj razˇsiri. Za vsako primitivno pot najprej preveri, ˇce je cikliˇcna. Ce ni, potem gre ˇˇ cez vse povezave in preveri, ali je moˇzno razˇsiriti PP z novo povezavo. ˇCe najde tako povezavo, preveri, ali ima ta nova povezava sosednje povezave, ki so ˇze vsebovane (tako prepreˇcujemo cikle). ˇCe so vsi pogoji izpolnjeni, razˇsirimo primitivno pot z novo povezavo. Na koncu moramo izloˇciti primitivne iz preprostih poti in jih dodati novi mnoˇzici. Kot izhod dobimo mnoˇzico poti za PPC pokritje.
Poglavje 3
Zahteve in reˇ sitev
V tem poglavju bomo prestavili reˇsitev, ki smo jo sistematiˇcno razvili. Naj- prej smo definirali zahteve in naredili naˇcrt. Ko je bil ta konˇcan, smo zaˇceli razvijati in sproti testirati.
Naredili smo vmesnik za risanje grafa, pisanje testnih poti, izbiro tipa pokri- tja, ˇstevila vozliˇsˇc in drugo. Po predstavitvi uporabe vmesnika sledi imple- mentacija algoritmov v ozadju. Kot konˇcni izdelek tega poglavja ˇzelimo imeti uporabniku prijetno, odzivno in enostavno aplikacijo. Zadevo smo razdelili na veˇc delov (nalog) in za vsak del definirali, kaj priˇcakujemo in kako smo do tega priˇsli.
3.1 Zahteve
Sploˇsne zahteve so izdelati orodje, ki:
• omogoˇca vnos grafa strukture;
• preveri pravilnost grafa;
• z izbiro kriterija pokritje (NC, EC, EPC, PPC) bodisi:
– preverja ustreznost podanih testnih poti, – izpiˇse vse testne poti;
17
18 Luka Kalezi´c
• izpiˇse rezultate (na zaslon in v datoteko).
Programirana reˇsitev naj bo preprosta za uporabo, uporabniku prijazna in zanesljiva. Natanˇcnejˇse zahteve za posamezne dele bodo opisane ob naˇcrtovanju.
3.2 Naˇ crt programa
Po naˇcrtu sta glavna razreda programa dva: Vmesnik inOzadje (slika 3.1).
Program se zaˇzene v razredu Vmesnik, ki prikazuje naˇse okvirje. Najprej nam omogoˇca, da vnesemo ˇzeleno ˇstevilo vozliˇsˇc in vrsto kriterija pokritja.
Po tem nariˇsemo graf. To izvede razred Narisi, ki najprej nariˇse vozliˇsˇca glede na vneseno velikost z uporabo razreda Node. Ko povezujemo vozliˇsˇca, se kliˇce razredPovezava, s pomoˇcjo katerega riˇsemo puˇsˇcice. Po risanju pre- verimo pravilnost grafa. ˇCe je pravilen, vnesemo testne poti.
Nato preklopimo v razred Ozadje. Preverjanje testnih poti smo prepustili razredu Ozadje, ker v istem delu okvirja komentiramo testne poti; od pra- vilnosti samih TP do tega, koliko pokrivajo kriterije pokritja.
Ce so pravilne, naˇs program doloˇˇ ci testne zahteve. Na koncu dobimo ocene naˇsih testnih poti (kaj jim manjka za izpolnjevanje ˇzelenih kriterijev pokri- tja), ˇce pa ˇzelimo, nam tudi izpiˇse pravilne testne poti.
3.3 Vmesnik
Zahteve
Program mora kot vhod prejeti graf, ki ga bo interpretiral kot svoj model za analizo. Uporabniku mora omogoˇciti, da izbere vrsto kriterija pokritja in ˇstevilo vozliˇsˇc v grafu. Vrste pokritja smo predstavili v poglavju 2. Po izbiri kriterija in ˇstevila vozliˇsˇc moramo uporabniku omogoˇciti, da nariˇse graf za svoj program. Na koncu napiˇse testne poti in zaˇzene program. Kot izhod lahko uporabnik dobi potrditev, ˇce testne poti ustrezajo kriteriju ali obratno
Diplomska naloga 19
Slika 3.1: Naˇcrt programa.
– kaj jim manjka. Z uporabo izbranega kriterija pokritja tako lahko tudi ocenjujemo testne poti.
Reˇ sitev
Vmesnik smo implementirali vJFame. Sestavljen je iz treh okvirjev, ki se od- pirajo po vrstnem redu. ˇSirina in viˇsina okvirja za risanje sta fiksni. Velikosti so fiksne zaradi laˇzjega izraˇcuna formul za velikost vozliˇsˇc in risanja puˇsˇcic.
Prvi okvir (slika 3.2) je sestavljen iz gumba, polja za vnos ˇstevila vozliˇsˇc in seznama za kriterij pokritja. Tu vnesemo ˇstevilo vozliˇsˇc, ki jih ˇzelimo, in kriterij pokritja. Naslednji se odpre okvir za risanje.
20 Luka Kalezi´c
Slika 3.2: Prvi okvir.
3.3.1 Vozliˇ sˇ ca Zahteve
Zelimo, da vmesnik prikaˇˇ ze vsa vozliˇsˇca brez pomikanja okvirja. Ne ˇzelimo premajhnih vozliˇsˇc, ker bi jih bilo teˇzko razlikovati med seboj ali povezati.
Da bi olajˇsali risanje, program obarva vozliˇsˇce, ki ga ˇzelimo povezati.
Reˇ sitev
Na drugem okvirju (slika 3.3) vidimo ˇstevilo vozliˇsˇc, ki smo jih predhodno izbrali. Premer vsakega vozliˇsˇca in razdalja med njimi sta odvisni od ˇstevila vnesenih vozliˇsˇc. Premer vozliˇsˇca izraˇcunamo po formuli:
premer = ˇsirinaOkvirja / (ˇsteviloVozliˇsˇc * 2)
Na ta naˇcin na risbi upoˇstevamo razdaljo med sosednjim vozliˇsˇci. Razdalja med vozliˇsˇci je enaka premeru vozliˇsˇca. Ko kliknemo na vozliˇsˇce, se pobarva v zeleno – s tem vemo, katero vozliˇsˇce ˇzelimo povezati. Ko ga poveˇzemo, se zopet spremeni v belo barvo.
3.3.2 Risanje puˇ sˇ cic Zahteve
Vozliˇsˇca je treba povezati s puˇsˇcicami, ki se ne smejo veliko prekrivati, saj je tako teˇzje risati graf. Puˇsˇcice naj tudi ne preˇckajo mej okvirja. Konica
Diplomska naloga 21
Slika 3.3: Drugi okvir.
puˇsˇcice ne sme biti prevelika ali premajhna – odvisna je od velikosti vozliˇsˇca.
Reˇ sitev
Ko povezujemo razliˇcna vozliˇsˇca, se v ozadju odvija program. ˇCe je povezava dodana, se pokliˇce funkcijo risanja puˇsˇcice. Velikost puˇsˇcice je odvisna od ˇstevila vozliˇsˇc. ˇCe imamo veliko vozliˇsˇc, je majhna, sicer je velika. Viˇsina se izraˇcuna po formuli. Na sliki 3.4 se vozliˇsˇci 2 in 4 povezujeta preko vozliˇsˇca 3.
Slika 3.4: Povezan graf.
Veˇcja kot je razdalja med vozliˇsˇci, veˇcja je viˇsina. Vrednost k je razlika med indeksoma vozliˇsˇca, katerima doloˇcamo viˇsino puˇsˇcic. Za ˇstevilo k velja:
22 Luka Kalezi´c k = abs(index(source) - index(dest))
visina = verticalY(source) + k * m
ˇStevilo m je odvisno od tega, koliko visoko puˇsˇcico ˇzelimo imeti. To formulo uporabljamo zaradi tega, da ena povezava ne prekriva druge. Puˇsˇcica gre nad ali pod drugimi vozliˇsˇci, ki so vmes. To je odvisno od paritete prvega vozliˇsˇca. Za drugo polje je znaˇcilen gumb za oznaˇcevanje konˇcnih vozliˇsˇc.
Ce bi oznaˇˇ cili kot konˇcno vozliˇsˇce tisto, ki ima izhodno povezavo, bi to pov- zroˇcilo napako. Oznaˇcevanje konˇcnega vozliˇsˇca je pomembno, saj bo tako laˇzje preveriti pravilnost in logiko grafa.
3.3.3 Testne poti Zahteve
Prostor za pisanje testnih poti mora biti jasen in ˇcitljiv (izbira ustrezne pisave in barve ozadja). V primeru ˇstevilnih testnih poti je mogoˇce tudi pomikanje.
Velikost pisave je fiksna.
Reˇ sitev
Tretji okvir (slika 3.5) je za vnos testnih poti. Ima veliko besedilno obmoˇcje za vnos testnih poti in dva gumba: prvi je za preverjanje testnih poti upo- rabnika, drugi pa za shranjevanje pravilnih testnih poti v loˇceno datoteko.
Zapiˇsemo veˇc vrstic testnih poti. Vsako vozliˇsˇce loˇcimo z vejico, vsako testno pot pa loˇcimo z novo vrstico. Ko pritisnemo gumbe, zaˇzenemo algoritem.
3.4 Ozadje
Zahteve
Zelimo imeti hiter in zanesljiv program, ki pravilno izvede testne poti. Hi-ˇ trost bomo zagotovili s ˇcim bolj preprostim algoritmom, zanesljivost pa z
Diplomska naloga 23
Slika 3.5: Tretji okvir.
njegovim testiranjem. Rezultati morajo biti jasni in razumljivi. Uporab- nik mora razumeti, kako prebrati reˇsitev v primeru veˇcjega ˇstevila testnih poti. Program mora biti preprost in enostaven za uporabo, upoˇstevati pa moramo tudi izkuˇsnje uporabnika. V primeru preverjanja njegovih testnih poti prikaˇzemo ustrezne rezultate. ˇCe ˇzeli dobiti pravilne testne poti, te tudi shranimo v datoteko.
Reˇ sitev
Predstavili smo delovanje vmesnika, ki ga vidimo med uporabo programa, vendar se v ozadju odvija bolj zapletena zgodba. Po vnosu testnih poti se sproˇzi veˇcfazni postopek.
3.4.1 Preverjanje logiˇ cnosti grafa Zahteve
Preden zaˇcnemo pisati testne poti, mora program preveriti smiselnost grafa.
Algoritem ne sme biti zapleten, ker je rekurziven – biti mora hiter.
24 Luka Kalezi´c
Reˇ sitev
Naˇcela preverjanja logike grafa:
• Ali so konˇcna vozliˇsˇca oznaˇcena? ˇCe niso, program ne more preveriti pravilnosti grafa.
• Ali so vsa vozliˇsˇca povezana? Vsa vozliˇsˇca morajo imeti neko vrsto povezave (vhodne ali izhodne).
• Ali so vsa vozliˇsˇca logiˇcno povezana? Za to uporabimo rekurzivni al- goritem, ki od zaˇcetnega obiˇsˇce vsa vozliˇsˇca.
• Ali so konˇcna vozliˇsˇca brez izhodnih povezav? Konˇcno vozliˇsˇce ne sme imeti izhodnih povezav.
• Ali so zaˇcetna vozliˇsˇca brez vhodnih povezav? Zaˇcetno vozliˇsˇce ne sme imeti vhodnih povezav.
Za preverjanje logike grafa uporabljamo rekurzivni algoritem.
b o o l e a n [ ] r e k u r z i v n o O b i s c i ( b o o l e a n [ ] o b i s k a n a , i n t i ){ i f ( o b i s k a n a [ i ] == t r u e ){
r e t u r n o b i s k a n a ; }
o b i s k a n a [ i ] = t r u e ; f o r k ∈ Ei {
i f ( k n i k o n c n o ){
r e k u r z i v n o O b i s c i ( o b i s k a n a , k ) ; }
}
r e t u r n o b i s k a n a ; }
Algoritem mora obiskati vsa vozliˇsˇca, zato mora biti vsak element tabele obiskana TRUE. ˇCe ni tako, pravimo, da graf ni logiˇcen.
3.4.2 Preverjanje pravilnosti testnih poti Zahteve
Preverimo pravilnost testnih poti. Da bi ocenili kakovost napisanih testnih poti glede na kriterij pokritja, moramo vedeti, ali so te pravilne.
Diplomska naloga 25
Slika 3.6: Primer veljavnega grafa (zeleno je zaˇcetno, modra pa konˇcna vo- zliˇsˇca)
Reˇ sitev
Testna pot je pravilna, ˇce:
• se zaˇcne v zaˇcetnemu vozliˇsˇcu (vedno 1);
• so vsa vozliˇsˇca med seboj pravilno povezana in
• se konˇca v konˇcnem vozliˇsˇcu.
Ce tega ne bi upoˇstevali, bi se program takoj ustavil. Na zaˇˇ cetku zato pre- verimo pravilnost testnih poti in ˇce katera od testni poti ni pravilna, dobimo obvestilo, katera pot ni dobra in zakaj.
Za sliko 3.6 so primeri veljavnih in neveljavnih testnih poti naslednji:
Veljavne TP = {[1, 2, 3, 4, 7], [1, 2, 3 ,5, 6], [1, 3, 5, 6]... } Neveljavne TP ={ [2, 3, 4, 7], [1, 2 ,5, 6], [1, 3, 5, 6, 5]... }
3.4.3 Doloˇ canje testnih zahtev Zahteve
V skladu s predstavljenimi pokritji (NC/EC/EPC/PPC) doloˇcimo testne zahteve.
26 Luka Kalezi´c
Reˇ sitev
V poglavju 2 so predlagani algoritmi za kriterije pokritosti – NC, EC, EPC, PPC. Naˇs program se konˇca, ko preveri, ali vnesene testne poti vsebujejo vse testne zahteve izbranega kriterija. ˇCe ˇzelimo, da program shrani testno pot v loˇceno datoteko, testnim zahtevam dodamo vozliˇsˇca, da dobimo logiˇcne testne poti.
3.4.4 Prevajanje testnih zahtev v poti Zahteve
Dopolni testne zahteve do pravilnih testnih poti. Pravilna testna pot poteka od zaˇcetnega do konˇcnega vozliˇsˇca.
Reˇ sitev
Prevajanje testnih zahtev v logiˇcne testne poti poteka v dveh fazah. ˇCe prvo vozliˇsˇce testne zahteve ni zaˇcetno vozliˇsˇce, dodajamo vozliˇsˇca od zaˇcetnega, dokler ga ne poveˇzemo s prvim v testni zahtevi. Algoritem poteka rekurzivno, optimizacija je upoˇstevana. Za vsako prvo vozliˇsˇce testne zahteve shranimo najkrajˇso pot (najdemo jo z rekurzijo) od zaˇcetnega do njega. Na ta naˇcin se izognemo iskanju najkrajˇse poti za ista prva vozliˇsˇca.
Princip je popolnoma enak za drugo fazo, ko doloˇcimo pot od zadnjega vo- zliˇsˇca testne zahteve do konˇcnega v grafu. Na koncu dobimo najkrajˇse moˇzne testne poti, ki pokrivajo vse testne zahteve, in jih shranimo v datoteko.
3.4.5 Shranjevanje testnih poti v datoteko Zahteve
Izraˇcunane poti shranimo tako, da jih lahko podamo kot parametre za prever- janje poti v naˇsem programu. Vsebina datoteke mora biti primerna kot vhod
Diplomska naloga 27 za naˇs program, ker lahko pravilnost shranjenih poti preverimo z naˇsim pro- gramom. Med seboj moramo loˇcevati vsako pot in tudi vozliˇsˇca. Shranimo jo v primeren format za nadaljnjo uporabo.
Reˇ sitev
Glede na to, da morajo biti shranjene testne poti sprejemljive za naˇs pro- gram, jih moramo ohraniti na enak naˇcin. Vsako pot loˇcimo s presledkom, vsako vozliˇsˇce na poti z vejico in presledkom. Za to uporabljamo formati- ranje nizov s knjiˇznico PrintWriter. Reˇsitev shranimo kot navadno .txt datoteko, ker je ta format najbolj sploˇsno uporabljen.
Ustvarili smo lep interaktiven vmesnik, ki omogoˇca uˇcinkovito izvedbo zah- tevanih pogojev. Kar naredi to orodje ˇse boljˇse, je to, da ga je zaradi siste- matiˇcnega naˇcina programiranja zelo enostavno razˇsiriti. ˇCe ˇzelimo reˇsitev avtomatizirati, lahko preprosto dodamo funkcijo, kjer namesto risanja grafa le-tega preberemo iz datoteke na vhodu.
28 Luka Kalezi´c
Poglavje 4 Analiza
Za prikaz delovanja in analizo uporabljamo nekoliko bolj zapletene primere iz podroˇcja urejanja. Analiziramo iterativne algoritme, ker nam ti dajo veˇcje in zanimivejˇse modele. Cilj je pokazati, da naˇsa reˇsitev deluje pravilno in da nam njena uporaba prihrani veliko ˇcasa.
4.1 Urejanje z navadnim izbiranjem
Definicija in opis
Urejanje z navadnim izbiranjem (angl. Selection Sort – SS) raz- vrsti zaporedje tako, da vedno znova najde minimalni element (glede na naraˇsˇcajoˇci vrstni red) iz neurejenega dela in ga po- stavi na zaˇcetek [10].
Algoritem vzdrˇzuje dve podzaporedji:
• podzaporedje, ki je ˇze urejeno;
• preostalo podzaporedje, ki ni urejeno.
Pri vsaki iteraciji urejanja je izbran minimalni element (glede na naraˇsˇcajoˇci vrstni red) iz neurejenega dela tabele in premaknjen v urejen del.
29
30 Luka Kalezi´c
Psevdokoda SS
Java koda za SS:
v o i d s o r t ( i n t a r r [ ] ) {
i n t n = a r r . l e n g t h ;
f o r ( i n t i = 0 ; i < n−1; i ++) {
i n t m i n i d x = i ;
f o r ( i n t j = i +1; j <n ; j ++) i f ( a r r [ j ] < a r r [ m i n i d x ] )
m i n i d x = j ; i n t temp = a r r [ m i n i d x ] ; a r r [ m i n i d x ] = a r r [ i ] ; a r r [ i ] = temp ;
} }
Kot parameter metode podajamo tabelo za urejanje. Algoritem je sestavljen iz dveh vgnezdenih zank. Glavna zanka gre po vrstnem redu od zaˇcetka in nastavlja ustrezne ˇstevilke, ki jih najde vgnezdena zanka. Vgnezdena zanka najde najmanjˇse ˇstevilke iz neurejenega dela zaporedja. Zaˇcne se s ˇstevilko na indeksu, ki ga doloˇca glavna zanka (v prvi iteraciji je vedno 0), ob predpostavki, da je najmanjˇsa, in jo primerjamo z vsemi ostalimi. ˇCe najdemo manjˇse ˇstevilo od tega, ga shranimo kot novo najmanjˇse ˇstevilo. Na koncu vgnezdene zanke zamenjamo pozicije najmanjˇsega ˇstevila in ˇstevilke, na katero kaˇze indeks glavne zanke. Iz kode nariˇsemo graf na sliki 4.1.
Primer
Po predstavljenem naˇcelu poiˇsˇcemo testne zahteve za SS (od NC do PPC).
NC : TR = { [1], [2], [3], [4], [5], [6], [7], [8], [9]}
EC : TR = {[1, 2], [2, 3], [2, 4], [3, 5], [5, 6], [5, 7], [6, 2], [7, 8], [7, 9], [8, 9], [9, 5] }
EPC : TR = { [1, 2, 3], [1, 2, 4], [2, 3, 5], [3, 5, 6], [3, 5, 7], [5, 6, 2], [5, 7, 8], [5, 7, 9], [6, 2, 3], [6, 2, 4], [7, 8, 9], [7, 9, 5], [8, 9, 5], [9, 5, 6], [9, 5, 7] } Poti dolˇzine 4 : TR ={ [1, 2, 3, 5], [2, 3, 5, 6], [2, 3, 5, 7], [3, 5, 6, 2], [3, 5, 7, 8], [3, 5, 7, 9], [5, 6, 2, 3], [5, 6, 2, 4], [5, 7, 8, 9], [5, 7, 9, 5], [6, 2, 3, 5], [7, 8, 9, 5], [7, 9, 5, 6], [7, 9, 5, 7], [8, 9, 5, 6], [8, 9, 5, 7], [9, 5, 6, 2], [9, 5, 7, 8],
[9, 5, 7, 9] }
Diplomska naloga 31
Slika 4.1: CFG za Selection Sort.
Poti dolˇzine 5 : TR = {[1, 2, 3, 5, 6], [1, 2, 3, 5, 7], [2, 3, 5, 6, 2], [2, 3, 5, 7, 8], [2, 3, 5, 7, 9], [3, 5, 6, 2, 3], [3, 5, 6, 2, 4], [3, 5, 7, 8, 9], [3, 5, 7, 9, 5], [5, 6, 2, 3, 5], [5, 7, 8, 9, 5], [6, 2, 3, 5, 6], [6, 2, 3, 5, 7], [7, 8, 9, 5, 6], [7, 8, 9, 5, 7], [7, 9, 5, 6, 2], [8, 9, 5, 6, 2], [8, 9, 5, 7, 8], [8, 9, 5, 7, 9], [9, 5, 6, 2,
3], [9, 5, 6, 2, 4], [9, 5, 7, 8, 9] }
Poti dolˇzine 6 : TR = { [1, 2, 3, 5, 6, 2], [1, 2, 3, 5, 7, 8], [1, 2, 3, 5, 7, 9], [2, 3, 5, 7, 8, 9], [2, 3, 5, 7, 9, 5], [3, 5, 7, 8, 9, 5], [6, 2, 3, 5, 7, 8], [6, 2, 3, 5, 7, 9], [7, 8, 9, 5, 6, 2], [7, 9, 5, 6, 2, 3], [7, 9, 5, 6, 2, 4], [8, 9, 5, 6, 2, 3], [8, 9,
5, 6, 2, 4], [9, 5, 6, 2, 3, 5] }
Poti dolˇzine 7 : TR ={[1, 2, 3, 5, 7, 8, 9], [1, 2, 3, 5, 7, 9, 5], [2, 3, 5, 7, 8, 9, 5], [6, 2, 3, 5, 7, 8, 9], [6, 2, 3, 5, 7, 9, 5], [7, 8, 9, 5, 6, 2, 3], [7, 8, 9, 5, 6,
2, 4], [7, 9, 5, 6, 2, 3, 5], [8, 9, 5, 6, 2, 3, 5]}
Poti dolˇzine 8 : TR ={[1, 2, 3, 5, 7, 8, 9, 5], [6, 2, 3, 5, 7, 8, 9, 5], [7, 8, 9,
32 Luka Kalezi´c 5, 6, 2, 3, 5] }
PPC : TR = { [1, 2, 4], [5, 7, 9, 5], [7, 9, 5, 7], [9, 5, 7, 9], [1, 2, 3, 5, 6], [2, 3, 5, 6, 2], [3, 5, 6, 2, 3], [3, 5, 6, 2, 4], [5, 6, 2, 3, 5], [5, 7, 8, 9, 5], [6, 2, 3, 5,
6], [7, 8, 9, 5, 7], [8, 9, 5, 7, 8], [9, 5, 7, 8, 9], [1, 2, 3, 5, 7, 9], [6, 2, 3, 5, 7, 9], [7, 9, 5, 6, 2, 3], [7, 9, 5, 6, 2, 4], [1, 2, 3, 5, 7, 8, 9], [6, 2, 3, 5, 7, 8, 9], [7,
8, 9, 5, 6, 2, 3], [7, 8, 9, 5, 6, 2, 4] }
Dopolnili bomo testne zahteve, da dobimo testne poti, in jih bomo dali v naˇs program preverjanja.
PPC : TP = {[1, 2, 4], [1, 2, 3, 5, 7, 9, 5, 6, 2, 4], [1, 2, 3, 5, 7, 9, 5, 7, 9, 5, 6, 2, 4], [1, 2, 3, 5, 7, 9, 5, 7, 9, 5, 6, 2, 4], [1, 2, 3, 5, 6, 2, 4], [1, 2, 3, 5, 6, 2, 4], [1, 2, 3, 5, 6, 2, 3, 5, 6, 2, 4], [1, 2, 3, 5, 6, 2, 4], [1, 2, 3, 5, 6, 2, 3, 5, 6, 2, 4], [1, 2, 3, 5, 7, 8, 9, 5, 6, 2, 4], [1, 2, 3, 5, 6, 2, 3, 5, 6, 2, 4], [1, 2, 3, 5, 7, 8, 9, 5, 7, 9, 5, 6, 2, 4], [1, 2, 3, 5, 7, 8, 9, 5, 7, 8, 9, 5, 6, 2, 4], [1, 2, 3, 5, 7, 9, 5, 7, 8, 9, 5, 6, 2, 4], [1, 2, 3, 5, 7, 9, 5, 6, 2, 4], [1, 2, 3, 5, 6, 2, 3, 5, 7, 9, 5, 6, 2, 4], [1, 2, 3, 5, 7, 9, 5, 6, 2, 3, 5, 6, 2, 4], [1, 2, 3, 5, 7, 9, 5, 6, 2, 4], [1, 2, 3, 5, 7, 8, 9, 5, 6, 2, 4], [1, 2, 3, 5, 6, 2, 3, 5, 7, 8, 9, 5, 6, 2, 4], [1, 2, 3, 5, 7,
8, 9, 5, 6, 2, 3, 5, 6, 2, 4], [1, 2, 3, 5, 7, 8, 9, 5, 6, 2, 4] }
Slika 4.2: Naˇs program.
Naˇs program doloˇci pravilne testne poti (slika 4.2), kar nam pove, da pro- gram natanˇcno oceni preskusne poti.
Diplomska naloga 33
Slika 4.3: Testne poti programa.
ˇStevili roˇcno in programsko doloˇcenih testnih poti se razlikujeta. To je zato, ker za dve testni zahtevi ([7, 9, 5, 7] in [9, 5, 7, 9]) obstaja ena testna pot, ki vsebuje oboje ([1, 2, 3, 5, 7, 9, 5, 7, 9, 5, 6, 2, 4]). Program izpusti vse podvojene testne poti. Program je napisal pravilne testne poti (slika 4.3).
Testni primer
Imamo testne poti in ˇzelimo vedeti, kako nam pomagajo pri pisanju testov.
Za zaˇcetek bomo napisali testne primere za najkrajˇso PPC ([1, 2, 4] in naj- daljˇso testno pot ([1, 2, 3, 5, 7, 8, 9, 5, 7, 8, 9, 5, 6, 2, 4]).
Za najkrajˇso TP ˇzelimo, da se program takoj ustavi. Ko pogledamo psevdo- kodo algoritma, vidimo, da program sploh ne vstopi v zanko, ˇce je velikost tabele za urejanje manjˇsa ali enaka 1. Zato velja:
int [] arr = new int [ ] { 1 } ; sort ( arr );
Za najdaljˇso TP vidimo, da enkrat vstopi v glavno zanko in dvakrat v vgnez- deno zanko, torej stavek if obiˇsˇce obakrat. To nam pove, da mora biti ve- likost tabele enaka 3. ˇCe pa je velikost tabele 3, glavne zanke ni mogoˇce
34 Luka Kalezi´c obiskati samo enkrat – glavna zanka mora imeti 2 ponovitvi. Poleg tega je stavek if obiskan obakrat v vgnezdenih zankah, kar pomeni, da je prvo ˇstevilo najveˇcje v zaporedju in tudi zaradi tega ni pravilno, da se glavna zanka izvede samo enkrat. Pri tem vidimo teˇzavo neizvedljivih testnih poti.
PPC zahteva, da se vsaka zanka izvede niˇckrat, enkrat ali dvakrat, a za dan algoritem vˇcasih to ni mogoˇce. Zato za nekatere poti ne najdemo pravih testnih primerov. Reˇsitev za to se imenuje Best Effort Testing. ˇCe najdemo neizvedljivo pot, je cilj to pot spremeniti, da se bo lahko izvedla. Spremeniti pomeni nekaj dodati, da je originalna pot ˇcim bolj podobna spremenjeni, ki pa je izvedljiva. Najlaˇzje je zato dodati eno ponovitev glavne zanke.
[1, 2, 3, 5, 7, 8, 9, 5, 7, 8, 9, 5, 6, 2, 4]→[1, 2, 3, 5, 7, 8, 9, 5, 7, 8, 9, 5, 6, 2, 3, 5, 7, 8, 9, 5, 6, 2, 4]
Od 13 poti je veˇcina neizvedljivih, zato postopek ponovimo za vse ostale. V naˇsem primeru postopka ne bomo ponavljali, ampak bomo naˇso posodobljeno pot zgolj dodali med izvedljive, za te pa bomo podali testne primere.
TP = { [1, 2, 4], [1, 2, 3, 5, 7, 8, 9, 5, 6, 2, 4], [1, 2, 3, 5, 7, 9, 5, 6, 2, 4], [1, 2, 3, 5, 7, 8, 9, 5, 7, 8, 9, 5, 6, 2, 3, 5, 7, 8, 9, 5, 6, 2, 4] }
Za prvo pot smo ˇze doloˇcili primer, treba je ˇse za ostale 3 poti. V prvem primeru se stavek if izvede, ˇce je drugo ˇstevilo v zaporedju manjˇse od pr- vega. V drugem primeru je ravno nasprotno. V tretjem primeru se v prvi ponovitvi glavni zanki obakrat izvede if stavek, kar pomeni, da je tabela urejena padajoˇce.
Za prvi primer sledi:
int [] arr = new int []{2 , 1};
sort ( arr );
Za drugi primer sledi:
int [] arr = new int []{1 , 2};
sort ( arr );
Za tretji primer sledi:
Diplomska naloga 35 int [] arr = new int []{3 , 2 , 1};
sort ( arr );
4.2 Iterativno urejanje z zlivanjem
Definicija in opis
Urejanje z zlivanjem (angl. Merge Sort – MS) je algoritem po naˇcelu ”Deli in Vladaj”. Vhodni niz razdeli na dve polovici, sam sebe pokliˇce za obe polovici in nato urejeno zdruˇzi obe (urejeni) polovici [8].
Psevdokoda MS
Iz podane kode [7] nariˇsemo graf (slika 4.4).
s t a t i c v o i d m e r g e S o r t ( i n t a r r [ ] , i n t n ) {
i n t c u r r s i z e ; i n t l e f t s t a r t ;
f o r ( c u r r s i z e = 1 ; c u r r s i z e <= n−1;
c u r r s i z e = 2∗c u r r s i z e ) {
f o r ( l e f t s t a r t = 0 ; l e f t s t a r t < n−1;
l e f t s t a r t += 2∗c u r r s i z e ) {
i n t mid = Math . min ( l e f t s t a r t + c u r r s i z e − 1 , n−1 ) ; i n t r i g h t e n d = Math . min ( l e f t s t a r t
+ 2∗c u r r s i z e − 1 , n−1 ) ; merge ( a r r , l e f t s t a r t , mid , r i g h t e n d ) ; }
} }
s t a t i c v o i d merge ( i n t a r r [ ] , i n t l , i n t m, i n t r ) {
i n t i , j , k ; i n t n1 = m− l + 1 ; i n t n2 = r −m;
i n t L [ ] = new i n t [ n1 ] ; i n t R [ ] = new i n t [ n2 ] ; f o r ( i = 0 ; i < n1 ; i ++)
L [ i ] = a r r [ l + i ] ; f o r ( j = 0 ; j < n2 ; j ++)
R [ j ] = a r r [m + 1+ j ] ; i = 0 ;
j = 0 ; k = l ;
w h i l e ( i < n1 && j < n2 ) {
i f ( L [ i ] <= R [ j ] )
36 Luka Kalezi´c
{
a r r [ k ] = L [ i ] ; i ++;
} e l s e {
a r r [ k ] = R [ j ] ; j ++;
} k++;
}
w h i l e ( i < n1 ) {
a r r [ k ] = L [ i ] ; i ++;
k++;
}
w h i l e ( j < n2 ) {
a r r [ k ] = R [ j ] ; j ++;
k++;
} }
Kot parameter metode podajamo tabelo za urejanje in velikost tabele. Al- goritem se izvaja postopoma po delih. Najprej uredimo pare ˇstevilk, ki so sosednje. Tabelo razdelimo v majhne dele, ki so sestavljeni iz dveh tabel.
Prva vsebuje ˇstevilke levo od sredine, druga pa ˇstevilke desno od sredine. Ta- bele zdruˇzimo po sistemu primerjave vsakega ˇstevila po indeksu. Zaˇcnemo z indeksoma na zaˇcetku in primerjamo prvi dve ˇstevilki. ˇCe je ˇstevilka iz prve tabele manjˇsa, jo dodamo v zdruˇzeno tabelo in poveˇcamo indeks za prvo tabelo. Ko zlijemo vse tabele majhnih kosov, poveˇcamo kapaciteto tabele (kosa) za dvakrat in tako naprej.
Primer
Graf je zelo zapleten, zato PPC doloˇcimo programsko. Kot primer preverja- nja pravilnosti programa bomo uporabili NC.
NC : TR = { [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20] }
NC : TP = { [1, 2, 3, 4, 6, 7, 8, 7, 9, 10, 9, 11, 13, 15, 18, 11, 13, 16, 18, 11, 12, 14, 12, 17, 19, 17, 20, 4, 3, 5]}
Celotno testno zahtevo pokrivamo z eno veliko testno potjo. Zaenkrat se
Diplomska naloga 37
Slika 4.4: CFG za iterativni Merge Sort.
nam zdi, da je pot pravilna in izvedljiva. V nadaljevanju bomo videli, ali lahko iz nje dobimo testni primer. Naˇsa reˇsitev je uspeˇsna (slika 4.5). Ko program zapisuje reˇsitve (testne poti), za vsako vozliˇsˇce zapiˇse loˇceno pot.
To ni slaba reˇsitev, saj je cilj programa jasnost in enostavnost za uporabo.
Uporabnik ˇzeli razumeti, kaj pomeni vsaka pot posebej.
ˇStevilo testnih PPC zahtev je kar 73, ˇstevilo testnih poti pa 49. Za pre- verjanje naˇsih rezultatov priporoˇcamo program [12]. Izvedba je zdaj trajala pribliˇzno pol sekunde, kar je sicer veˇc kot v prejˇsnjih primerih, vendar je ˇcas glede na zahtevnost grafa razumljiv. ˇCeprav je model ogromen, risba na uporabniˇskem vmesniku uporabnika ne moti.
38 Luka Kalezi´c
Slika 4.5: NC rezultat.
Testni primer
Poskusimo zdaj najti testni primer za naˇso pot. Oˇcitno gre skozi vse zanke enkrat, razen zanke, kjer primerjamo ˇstevilke in jih dodajamo v zdruˇzeno ta- belo, ki jo obiˇsˇcemo dvakrat (vozliˇsˇce 13). Najprej opazimo, da je nemogoˇce vstopiti v obe zanki na vozliˇsˇcu 12 in 17 v isti glavni iteraciji. Ti zanki se izvedeta, ˇce katera od obeh tabel (kosa) ostane s ˇstevilkami, ki niso vkljuˇcene v zdruˇzeno tabelo. Te ˇstevilke na koncu dodamo. Zato je nemogoˇce, da bi za obe tabeli ostali ˇstevilki, ki nista bili primerjani. Primerjava se izvaja, dokler ena tabela ne ostane brez ˇstevilk, nato pa vse ˇstevilke iz druge tabele dodamo na koncu.
Vendar naˇs program pravi, da testna pot pokriva vse NC poti, kar pa poˇcne zato, ker naˇs program doloˇca testne zahteve in preverja, ali so vsebovane v testni poti, ne pa logiko te poti. Pri tem bi tester zaˇcetnik teˇzko razumel, v ˇcem je teˇzava. Zelo pomembno je, kako bo uporabnik graf narisal; namreˇc bolj kot smo izkuˇseni, manj teˇzav bomo imeli z nelogiˇcnostjo. V naˇsem pri- meru teˇzava ni v risbi, ampak v sami kodi. ˇCe pogledamo pobliˇze, algoritem ob izvedbi prve zanke tudi preveri, ali je moˇzno izvesti drugo zanko. ˇCe se izvede prva zanka, se druga ne more izvesti, vendar vseeno preverja; v tem primeru bi bila bolj smiseln pogoj if-else. Torej moramo biti ob zaˇcetku pisanja testne poti zelo pozorni.
Diplomska naloga 39 Napiˇsimo zdaj bolj logiˇcno testno pot, ki bo obiskala vse NC poti.
NC : TP = { [1, 2, 3, 4, 6, 7, 8, 7, 9, 10, 9, 11, 13, 15, 18, 11, 12, 17, 19, 17, 20, 4, 6, 7, 8, 7, 9, 10, 9, 11, 13, 16, 18, 11, 12, 14, 12, 17, 20, 4, 3, 5] } Ta TP je za naslednji testni primer:
int [] arr = new int []{1 , 2 , 4 , 3};
m e r g e S o r t ( arr , 4);
Zdaj se program izvaja v dveh glavnih iteracijah in tako lahko obiˇsˇcemo oba whilestavka na dnu kode. ˇCeprav se zdi NC preprosto, v primeru gotovo ni.
Cilj ni samo zajeti vseh delov kode, cilj je tudi to, da je vse, kar poˇcnemo, smiselno.
4.3 Iterativno hitro urejanje
Definicija in opis
Hitro urejanje (angl. QuickSort – QS) je tudi algoritem ”Deli in Vladaj”. Izbere pivotni element in razdeli podano zaporedje glede na njega v levi del, kjer so vsi elementi manjˇsi (ali enaki), in desni, kjer so veˇcji [9].
Obstaja veliko razliˇcnih razliˇcic Quick Sort-a, ki izberejo pivota na razliˇcne naˇcine.
• izberejo prvi element;
• izberejo zadnji element (v naˇsem primeru);
• izberejo nakljuˇcni element ali
• izberejo mediano.
40 Luka Kalezi´c
Psevdokoda QS
Java koda za algoritem:
s t a t i c v o i d q u i c k S o r t I t e r a t i v e ( i n t a r r [ ] , i n t low , i n t h i g h ) {
i n t [ ] s t a c k = new i n t [ h i g h − l o w + 1 ] ; i n t t o p = −1;
s t a c k [++ t o p ] = l o w ; s t a c k [++ t o p ] = h i g h ; w h i l e ( t o p >= 0 ) {
h i g h = s t a c k [ top−−];
l o w = s t a c k [ top−−];
i n t p i v o t = a r r [ h i g h ] ; i n t i = ( l o w − 1 ) ; i n t temp ;
f o r ( i n t j = l o w ; j <= h i g h − 1 ; j ++) { i f ( a r r [ j ] <= p i v o t ) {
i ++;
temp = a r r [ i ] ; a r r [ i ] = a r r [ j ] ; a r r [ j ] = temp ; }
}
temp = a r r [ i + 1 ] ; a r r [ i + 1 ] = a r r [ h i g h ] ; a r r [ h i g h ] = temp ; p i v o t = i + 1 ;
i f ( p i v o t − 1 > l o w ) { s t a c k [++ t o p ] = l o w ; s t a c k [++ t o p ] = p i v o t − 1 ; }
i f ( p i v o t + 1 < h i g h ) { s t a c k [++ t o p ] = p i v o t + 1 ; s t a c k [++ t o p ] = h i g h ; }
} }
Kot parameter metode podajamo tabelo za urejanje, indeks prvega (0) in zadnjega (n-1) elementa. Na zaˇcetku inicializiramo novo indeksno tabelo, kamor bo algoritem shranil indekse neurejenih elementov. Algoritem deluje tako, da najprej pogleda indeksno tabelo, prvi in zadnji indeks neurejenega dela tabele in na podlagi njih doloˇci pivota (pri nas je to zadnji element).
Nato privzeto primerja elemente in spreminja njihova mesta, dokler ne po- stavi pivota na pravo mesto. Na koncu pa shrani indekse neurejenih delov in ponovi desne, dokler dela nista dolˇzine 1.
Primer
Nariˇsemo graf na sliki 4.6:
Diplomska naloga 41
Slika 4.6: CFG za iterativni Quick Sort.
Model je nekoliko preprostejˇsi od prejˇsnjega. Analizirajmo rezultate naˇsega programa. Tokrat bomo preverili pokritje EC.
NC : TR = {[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15] }
EC : TR = {[1, 2], [2, 3], [3, 4], [3, 5], [4, 6], [4, 9], [6, 7], [6, 8], [7, 8], [8, 4], [9, 10], [10, 11], [10, 12], [11, 12], [12, 13], [13, 14], [13, 15], [14, 15], [15, 3] } EC : TP = {[1, 2, 3, 4, 6, 7, 8, 4, 6, 8, 4, 9, 10, 11, 12, 13, 14, 15, 3, 4, 9,
10, 12, 13, 15, 3, 5] } Doloˇcili smo testno pot, ki jo predlagamo programu.
Testna pot obiˇsˇce vse EC zahteve (slika 4.7).
42 Luka Kalezi´c
Slika 4.7: EC pokritje – rezultat.
ˇStevilo PPC testnih zahtev je 62, ˇstevilo testnih poti pa 35. Program za QS deluje enako hitro kot SS.
Testni primer
Na podlagi testne poti za EC doloˇcimo primeren testen primer za program.
Ker gre spet v vgnezdeno zanko (4), samo enkrat vidimo, da je velikost tabele 2. ˇCe je velikost tabele 2, je mogoˇce iti v glavno zanko samo enkrat.
Spremenljivkatopse ne bo poveˇcala, ker je velikost tabele premajhna. ˇCe je velikost tabele premajhna, se if stavki na koncu kode ne bodo izvedli, zato ni mogoˇce vsega izvesti le z eno glavno zanko. Pot, ki obiˇsˇce vse:
EC : TP = { [1, 2, 3, 4, 6, 8, 4, 6, 8, 4, 6, 8, 4, 9, 10, 12, 13, 14, 15, 3, 4, 6, 7, 8, 4, 6, 7, 8, 4, 9, 10, 11, 12, 13, 15, 3, 4, 6, 8, 4, 9, 10, 12, 13, 15, 3, 5] } Za njo velja:
int [] arr = new int []{5 , 4 , 3 , 2};
q u i c k S o r t I t e r a t i v e ( arr , 0 , 3);
Izvedene so bile tri ponovitve glavne zanke. V prvi iteraciji je pivot 2. Ker je najmanjˇse ˇstevilo v zaporedju, if stavek v vgnezdeni zanki ni obiskan (vo- zliˇsˇce 7). Ker ni priˇslo do zamenjave, smo pivot takoj prenesli na prvo mesto v zaporedju. Poslediˇcno se prvi if stavek na dnu kode ne izvede, izvede se
Diplomska naloga 43 zgolj drugi. V drugi ponovitvi je pivot najveˇcje ˇstevilo 5. Zato se stavek if v vgnezdeni zanki izvede obakrat. Ker smo kot zadnjo ˇstevilko v zaporedju dobili 5, je zdaj situacija obratna. Samo drugi stavek if se izvede na dnu kode. Po drugi iteraciji imamo tako obiskane vse dele kode.
Na koncu analize ˇse komentirajmo, kaj smo s programom dosegli. Krite- riji pokritja imajo svoje prednosti in slabosti. Oˇcitne prednosti so, da z njihovo uporabo doloˇcimo testne poti (in teste), ki v praksi pomenijo dobro testiranje zahtev. Predstavili smo tudi slabosti kriterijev pokritja grafov in kako jih reˇsiti oziroma se jim izogniti. ˇCe imamo neizvedljive poti, upora- bimo naˇcelo Best Effort Testing.
Naˇsa reˇsitev seveda ne ve, kaj je v narisanih vozliˇsˇcih. Za doloˇcanje testnih zahtev na podlagi narisanega grafa uporablja svoje algoritme, zato je po- membno, da graf nariˇsemo na sistematiˇcen naˇcin. Ne glede na zapletenost primera ga s tem poenostavimo.
Ena od pomanjkljivosti roˇcnega pristopa doloˇcanja pokritosti je poˇcasnost.
V primeru urejanja z zlivanjem bi roˇcno doloˇcanje primitivnih poti trajalo pribliˇzno eno uro, ˇce bi skrbno preverili vse poti. Program nam da reˇsitev v manj kot pol sekunde. ˇCe bi merili celotni ˇcas, bi lahko ocenili, da traja pribliˇzno minuto za vnos zapletenega grafa, ˇse minuto pa za vnos doloˇcenih testnih poti, torej traja pribliˇzno 2 minuti za celotno izvedbo. To je oˇcitna ˇcasovna izboljˇsava, pri ˇcemur je treba omeniti tudi to, da so vsi vneseni deli (graf, testne poti) tudi preverjeni.
44 Luka Kalezi´c
Poglavje 5 Zakljuˇ cek
V diplomski nalogi smo govorili o naprednejˇsem naˇcinu testiranja, ki temelji na upoˇstevanju kriterijev pokritja. Bralca najprej uvedemo v temo z osnovno predstavitvijo pojmov z zgledi, nato pa predstavimo, na kakˇsen naˇcin smo to uporabili v naˇsi temi.
V nadaljevanju govorimo o implementaciji programa. Uporabljamo vmesnik, ki je enostaven za uporabo in razumljiv ne glede na uporabniˇske izkuˇsnje uporabnika. Program nam omogoˇca preverjanje vnesenih ali doloˇcanje pra- vih testih poti.
Analiza ustrezno zahtevnih algoritmov pokaˇze, da orodje zagotavlja pravilno delovanje, je uˇcinkovito in omogoˇca velike ˇcasovne prihranke v primerjavi z roˇcno izvedbo.
Ker se priˇcakuje, da bodo uporabniki znali pretvoriti kodo v graf, zaenkrat program uporabljajo predvsem izkuˇseni uporabniki. ˇZelja je omogoˇciti vsem razvijalcem, da testirajo svoje programe ne glede na njihovo znanje testira- nja. Z dodajanjem funkcionalnosti pretvarjanja kode v graf in izbiro pravih vhodnih parametrov za pridobljene testne poti, bomo naredili orodje ˇse bolj uspeˇsno. Za avtomatizirano uporabo bi recimo lahko omogoˇcili vnos grafov iz datotek.
Pri pretvorbi kode v graf govorimo o zelo zapletenem problemu, saj obsta- jajo zelo razliˇcne vrste programov. Obstajajo znani poskusi reˇsitve tega
45
46 Luka Kalezi´c vpraˇsanja [3], vendar problem kot tak presega obseg naˇsega diplomskega dela.
Podobno je z doloˇcanjem parametrov iz testnih primerov. Lahko bi uporabili enostaven algoritem za proste modele, vendar je to v primeru zahtevnejˇsih grafov teˇzko izvedljivo.
Laˇzje bi se lotili nekaterih drugih nadgradenj naˇsega orodja. Kriteriji pokri- tja, ki jih uporabljamo, niso edini mogoˇci. Orodje lahko razˇsirimo s ˇse veˇc obstojeˇcimi kriteriji pokritja za grafe. ˇCe ˇzelimo definirati za nas specifiˇcne testne zahteve, uporabljamo Specified Path Coverage – SPC. ˇCe bi strukturni graf nadgradili v graf podatkovnega toka (z opisom spremenljivk in njihovih mest doloˇcanja in uporabe), bi lahko implementirali ADC, AUC in ADUPC kriterije pokritja.
Konˇcni izdelek diplomske naloge je orodje, ki uporabnikom omogoˇca veliko laˇzje, zanesljivejˇse in uˇcinkovitejˇse testiranje. ˇCeprav bo orodje koristilo upo- rabnikom, morajo biti ti pri njegovi uporabi pozorni, orodje namreˇc lahko najde reˇsitev, ki morda ni povezana s smislom njihovega programa, zato so uporabniki sami odgovorni za njegovo pravilno implementacijo.
Najveˇcja prednost aplikacije je, da prihrani veliko ˇcasa pri pisanju dobrih te- stov. Med naˇso raziskavo na spletu nismo naˇsli podobnega orodja, ki omogoˇca tako preprost vnos grafov, njihovo preverjanje in doloˇcanje testnih poti. Go- tovo pa obstajajo uspeˇsne implementacije veˇc opisanih kriterijev.
Literatura
[1] Paul Ammann in Jeff Offutt. Introduction to software testing. Cam- bridge University Press, 2016.
[2] Howard Austerlitz. “CHAPTER 13 - Computer Programming Langua- ges”. V:Data Acquisition Techniques Using PCs (Second Edition). Ur.
Howard Austerlitz. Second Edition. San Diego: Academic Press, 2003, str. 326–360. isbn: 978-0-12-068377-2. doi: https : / / doi . org / 10 . 1016/B978-012068377-2/50013-9.url:https://www.sciencedirect.
com/science/article/pii/B9780120683772500139.
[3] Andrea Corradini in sod. “Translating Java Code to Graph Transfor- mation Systems”. V: sep. 2004, str. 383–398.isbn: 978-3-540-23207-0.
doi:10.1007/978-3-540-30203-2_27.
[4] D. D’Souza, A. Lal in K.G. Larsen. Verification, Model Checking, and Abstract Interpretation: 16th International Conference, VMCAI 2015, Mumbai, India, January 12-14, 2015, Proceedings. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2014.isbn: 9783662460818.
url:https://books.google.me/books?id=CifUBQAAQBAJ.
[5] Duane Q. Nykamp.Graph definition, From Math Insight.url:https:
//mathinsight.org/definition/graph(pridobljeno 29. 10. 2021).
[6] Anurag Dwarakanath in Aruna Jankiti. “Minimum Number of Test Paths for Prime Path and Other Structural Coverage Criteria”. V:
6th IFIP International Conference on Testing Software and Systems
47
