UNIVERZA V LJUBLJANI PEDAGOˇ SKA FAKULTETA
Luka Taras Koroˇ sec
ANALIZA IN NADGRADNJA APLIKACIJE ZA DELO Z GRAFI
DIPLOMSKO DELO
LJUBLJANA, 2016
UNIVERZA V LJUBLJANI PEDAGOˇ SKA FAKULTETA
UNIVERZITETNI ˇ STUDIJSKI PROGRAM 1. STOPNJE DVOPREDMETNI U ˇ CITELJ
Luka Taras Koroˇ sec
Mentor: doc. dr. Primoˇ z ˇ Sparl Somentor: as. Matej Zapuˇ sek
ANALIZA IN NADGRADNJA APLIKACIJE ZA DELO Z GRAFI
DIPLOMSKO DELO
LJUBLJANA, 2016
Povzetek
Ob svojem ˇstudiju na Pedagoˇski fakulteti Univerze v Ljubljani sem se ob obiskovanju predme- tov Teorija grafov, Diskretna matematika in Raˇcunalniˇska matematika spoznal s spletno ap- likacijo z0diak za delo z grafi. Aplikacijo, ki vsebuje zajeten nabor funkcij, je v okviru svojega diplomskega dela leta 2013 razvil Luka Jurkovi´c. Z njo lahko ustvarimo vizualno reprezentacijo enostavnih neusmerjenih grafov in nato na prikazanem grafu uporabljamo razliˇcna orodja.
Tekom veˇcletne uporabe aplikacije sem spoznal, da ima le-ta doloˇcene pomanjkljivosti in da bi bile dobrodoˇsle kakˇsne dodatne funkcije, zato sem se odloˇcil, da v okviru svojega diplomskega dela analiziram aplikacijo in njeno uporabnost ter jo nadgradim z novimi funkcijami in funkcionalnos- tmi. Analizo uporabnosti aplikacije sem opravil s pomoˇcjo anketnega vpraˇsalnika in sicer med ˇstudenti, ki so aplikacijo redno uporabljali pri svojem ˇstudiju. Glede na rezultate analize odgov- orov ter tehniˇcno in algoritemsko zahtevnost implementacije, sem izluˇsˇcil tiste funkcionalnosti, ki sem jih lahko dodal v aplikacijo. Le-ta sedaj med drugim poleg obstojeˇcih funkcionalnosti pod- pira tudi izraˇcun in prikaz oˇzine ter premera grafa, prikaz zaporedja stopenj grafa in funkcije, s katerimi si lahko pomagamo pri iskanju Hamiltonovega cikla. V diplomskem delu je razloˇzeno njihovo delovanje, na konkretnih primerih pa je prikazan tudi primer uporabe funkcij.
Kljuˇcne besede: graf, aplikacija z0diak, manipulacija grafa, premer, oˇzina, Hamiltonov cikel MSC klasifikacija (2010): 05C85, 05C62
Abstract
During my studies at the Faculty of Education, University of Ljubljana, I familiarized myself with a web application for graph manipulation called z0diak while I was attending courses on Graph Theory, Discrete Mathematics and Computer Mathematics. This application, which has a substantial set of functionalities, was developed by Luka Jurkovi´c for his diploma thesis in 2013. With it we can create visual representations of simple undirected graphs and then use a multitude of tools on the displayed graph.
In my years of using this application I realized that it has a few shortcomings and that I would appreciate new additional features. That is why I decided to analyze the application and its usability and upgrade it with new features and functionalities for my diploma thesis.
Using a questionnaire and with the help of students who used the application regularly in their studies, the analysis of usefulness of the application has been carried out. According to the results of the analysis of student responses as well as technical and algorithmic complexities of the implementation, I discerned those features that could be added to the application with a reasonable amount of effort and added them. Apart from the existing functionalities the application now also supports the calculation and display of the girth and diameter of the graph, calculation of the graph degree sequence and functions which can help in determining whether a graph contains a Hamiltonian cycle or not. The thesis explains how these functions were implemented and also presents a demonstration of their usage on specific examples.
Key words: graph, application z0diak, graph manipulation, girth, diameter, Hamiltonian cycle MSC clasification (2010): 05C85, 05C62
Kazalo
Uvod 1
1 Opis aplikacije z0diak 3
1.1 Izgled . . . 3
1.1.1 Platno . . . 4
1.1.2 Meni in gumbi . . . 4
1.1.3 Okno za izpisovanje navodil in povratnih informacij . . . 6
2 Zbiranje in analiza podatkov 8 2.1 Priprava raziskave . . . 8
2.2 Zbiranje in analiza podatkov . . . 9
2.2.1 Zbiranje podatkov . . . 9
2.2.2 Analiza podatkov . . . 9
2.3 Izbira novih funkcionalnosti . . . 13
2.3.1 Razveljavitev zadnje akcije . . . 13
2.3.2 Izraˇcun in prikaz oˇzine ter premera grafa . . . 14
2.3.3 Izpis zaporedja stopenj . . . 15
2.3.4 Preverjanje zadostnih pogojev za obstoj Hamiltonovega cikla . . . 16
2.3.5 Izvoz slike grafa v slikovni obliki . . . 17
3 Razvoj novih funkcionalnosti 19 3.1 Podatkovna struktura aplikacije in dodajanje novih elementov na platno . . . 19
3.1.1 Dodajanje novega vozliˇsˇca . . . 19
3.1.2 Dodajanje nove povezave . . . 20
3.2 Izpis zaporedja stopenj . . . 21
3.2.1 Algoritem za izraˇcun zaporedja stopenj . . . 21
3.2.2 Implementacija . . . 21
3.3 Izraˇcun in prikaz oˇzine grafa . . . 22
3.3.1 Algoritem za izraˇcun oˇzine grafa . . . 22
3.3.2 Implementacija algoritma za izraˇcun oˇzine grafa . . . 22
3.4 Izraˇcun in prikaz premera grafa . . . 23
3.4.1 Algoritem za izraˇcun premera grafa . . . 23
3.4.2 Implementacija algoritma za izraˇcun in prikaz premera grafa . . . 23
3.5 Preverjanje zadostnih pogojev za obstoj Hamiltonovega cikla . . . 25
3.5.1 Algoritem za preverjanje pogojev izreka P´osa . . . 25
3.5.2 Algoritem za preverjanje pogojev Diracovega izreka . . . 26
3.5.3 Algoritem za preverjanje pogojev Orejevega izreka . . . 26
3.6 Izvoz grafa v slikovni obliki . . . 27
3.7 Ilustracija uporabe novih funkcionalnosti . . . 27
3.7.1 Iskanje grafa ki vsebuje Hamiltonov cikel, vendar ne zadoˇsˇca pogojem izreka Diraca . . . 27
3.7.2 Iskanje kletk s podano oˇzino in stopnjo grafa . . . 28
3.7.3 Iskanje najveˇcjega grafa s podano stopnjo in premerom . . . 30
Zakljuˇcek 31
Slike
1.1 Logotip aplikacije z0diak. . . 3
1.2 Aplikacija z0diak, kot izgleda takoj po zagonu. . . 4
1.3 Poln graf na petih vozliˇsˇcih na platnu znotraj aplikacije z0diak. . . 4
1.4 Meni in gumbi, ki se nahajajo ob levi strani platna. . . 5
2.1 Primeri ˇstirih manjˇsih kletk. Od leve proti desni: Petersenov graf, Heawoodov graf, McGeejev graf in Tutte-Coxeterjev graf. . . 14
2.2 Dva neizomorfna grafa z istim zaporedjem stopenj (3,2,2,2,2,1,1,1). . . 16
2.3 Graf, ki ne zadoˇsˇca pogojem Diracovega in Orejevega izreka, izpolnjuje pa pogoje izreka P´osa ([13], str. 52). . . 17
3.1 Slika grafa, ki je bila izvoˇzena s pomoˇcjo funkcije za izvoz grafa v slikovni obliki. 28 3.2 Graf, ki zadoˇsˇca pogojem izrekov P´osa in Oreja, ne pa tudi pogojem izreka Diraca. 28 3.3 Graf po tem ko smo 5-ciklu dodali dve vozliˇsˇci in ju povezali z dvema obstojeˇcima vozliˇsˇcema. . . 29
3.4 Graf po tem ko smo vsakem izmed vozliˇsˇc 2, 3 in 4 dodali ˇse po dva soseda. Z rdeˇco je predstavljena ena izmed razdalj dolˇzine 4, ki predstavlja premer grafa. . 30
Uvod
Stevilo spletnih aplikacij je v zadnjih letih moˇˇ cno naraslo. Ob vsakdanji rabi raˇcunalnika ˇ
cedalje pogosteje uporabljamo spletne brskalnike in ob njihovi uporabi preˇzivimo veliko ˇcasa, pa naj bo to zaradi dela ali zabave. Odliˇcen primer je Microsoftov urejevalnik besedila Word, ki so ga najprej razvili kot program za operacijski sistem Windows, sedaj pa je ˇze na voljo na spletu kot spletna aplikacija. Zato razumem odloˇcitev avtorja Luka Jurkovi´ca, da je v okviru svojega diplomskega dela [4] razvil spletno aplikacijo z0diak. Ob pisanju diplomskega dela je pridobil novo znanje na tem podroˇcju, kar je bil eden izmed njegovih glavnih namenov razvoja aplikacije.
Zelel si je namreˇˇ c pridobiti izkuˇsnje z oznaˇcevalnim jezikom HTML5 in pri tem ustvariti nekaj uporabnega za njegove naslednike na Pedagoˇski fakulteti. Aplikacija z0diak je namreˇc namenjena delu z grafi in je za uporabo brezplaˇcna. Vsak ˇstudent Pedagoˇske fakultete si jo lahko prenese na svoj raˇcunalnik in jo nato uporablja brez internetne povezave. Prav tako aplikacije ni potrebno namestiti na osebni raˇcunalnik. Vse kar je potrebno storiti je, da jo shranimo na trdi disk, odpremo glavno stran in ˇze smo pripravljeni na delo z grafi.
Sam sem aplikacijo z0diak spoznal pri predmetu Teorija grafov, kjer smo jo uporabljali za interaktivno vizualizacijo obravnavanih grafov. Med predavanji jo je profesor pogosto uporabljal, da nam je hitro prikazal kakˇsen primer uporabe trenutno obravnavanih rezultatov na konkretnih primerih grafov. Aplikacija z0diak je mnogim ˇstudentom pomagala pri uˇcenju in reˇsevanju domaˇcih nalog, saj podpira ˇstevilna orodja za delo z grafi, kot so izris pripadnikov podprtih druˇzin grafov, razdaljne particije grafa in pomoˇc pri iskanju Hamiltonove poti oziroma cikla, ˇce naˇstejem samo nekaj funkcij.
Glavni cilj tega diplomskega dela je analiza obstojeˇcih orodij in funkcionalnosti aplikacije z0diak in zasnova ter izdelava veˇc novih funkcionalnosti. Za njegovo razumevanje je potrebno osnovno znanje raˇcunalniˇstva in teorije grafov. Bralcu, ki bi ˇzelel ponoviti osnovne pojme s teh dveh podroˇcij, v branje predlagam diplomsko delo Luka Jurkovi´ca [4], v katerem je postavil temelje aplikacije, ki jo sedaj mi analiziramo in nadgrajujemo. Vsebuje tako osnove teorije grafov, kot tudi osnove HTML5 in knjiˇznice Paper.js. V nadaljevanju se bomo drˇzali terminologije, vpeljane v [4].
V 1. poglavju tega diplomskega dela na kratko opiˇsemo delovanje aplikacije in njene glavne funkcionalnosti. Tu se osredotoˇcimo predvsem na plat aplikacije, ki je vidna konˇcnemu uporab- niku. Namen poglavja je seznanitev z aplikacijo in njenimi funkcijami.
V 2. poglavju predstavimo naˇcin zbiranja podatkov o mnenju ˇstudentov glede aplikacije z0diak, predstavimo odgovore ˇstudentov in jih statistiˇcno analiziramo. Glede na izsledke raziskave sem izbral par najbolj zaˇzelenih funkcionalnosti s strani uporabnikov, t.j. ˇstudentov, in nekaj tistih funkcij, za katere menim, da bi dobro dopolnjevale ostale dele programa. Vseh zaˇzelenih funkcionalnosti se seveda v ˇcasu, ki je na voljo za izvedbo diplomskega dela ne da razviti, zato se
osredotoˇcimo le na nekatere izmed njih. Opisali bomo teoretiˇcno podlago za vsako obravnavano funkcijo, naredili analizo moˇznosti implementacije v aplikacijo in jih nato, ˇce bo implementacija izvedljiva, dodali v obstojeˇco reˇsitev.
3. poglavje je namenjeno sami implementaciji izbranih novih funkcionalnosti. Tu predstavimo algoritme, ki so potrebni za implementacijo doloˇcene funkcionalnsti. Nekateri algoritmi so seveda bolj zahtevni kot drugi, zato nekaterim funkcijam posvetimo veˇc pozornosti kot drugim. Opiˇsemo tudi teˇzave, s katerimi sem se sooˇcal, in prikaˇzemo reˇsitve za podane ali nastale probleme. Na koncu tega poglavja si bomo ogledali veˇc primerov uporabe razvitih funkcionalnosti na konkretnih problemih.
Poglavje 1
Opis aplikacije z0diak
Pri vsakem produktu ali spletni strani nam obiˇcajno najprej padeta v oko ime in logotip. Ime spletne aplikacije, ki jo bom analiziral, je z0diak. Avtor aplikacije v svojem diplomskem delu navaja, da si je to ime izbral zato, ker zodiakalna znamenja na nek naˇcin izgledajo kot grafi [4].
Zvezde predstavljajo vozliˇsˇca v grafu, medtem ko povezave med zvezdami predstavljajo povezave med vozliˇsˇci v grafu. Kot lahko vidite na sliki 1.1, sta tako ime, kot tudi logotip odliˇcno izbrana glede na namen uporabe aplikacije in kaˇzeta na izvirnost pri izdelavi aplikacije.
Slika 1.1: Logotip aplikacije z0diak.
1.1 Izgled
Na sliki 1.2 je prikazan izgled aplikacije takoj po zagonu. Vizualno in funkcijsko je razdeljena na tri dele.
• Platno za izrisovanje grafov (siv pravokotnik, ki zavzema veˇcino prostora na ekranu).
• Meni in gumbi, z naborom funkcij za delo z grafi (zavzemajo levi del ekrana).
• Okno za izpisovanje navodil in povratnih informacij (vidno na spodnjem delu ekrana pod platnom).
Slika 1.2: Aplikacija z0diak, kot izgleda takoj po zagonu.
Slika 1.3: Poln graf na petih vozliˇsˇcih na platnu znotraj aplikacije z0diak.
1.1.1 Platno
Na sliki 1.3 se nahaja avtomatsko izrisan graf, kot je prikazan v aplikaciji. Opazimo lahko, da so vozliˇsˇca oˇstevilˇcena s ˇstevili od 1 do 5 in da so obarvana z enotno barvo. Vozliˇsˇcem lahko dodajamo povezave, a na polnem grafu tega ne moremo storiti, saj aplikacija ne podpira veˇckratnih povezav med dvema vozliˇsˇcema. Aplikacija prav tako ne podpira zank, to so povezave vozliˇsˇca samega s seboj. Podprti so torej tako imenovani enostavni grafi. Lahko pa obstojeˇco povezavo odstranimo s tiˇsˇcanjem tipke dvigalke (angl. shift) in klikom na povezavo, ki jo ˇzelimo odstraniti (na enak naˇcin lahko odstranimo tudi vozliˇsˇca).
1.1.2 Meni in gumbi
Meni je del aplikacije, ki vsebuje gumbe, s katerimi lahko dostopamo do velike veˇcine funkcij aplikacije. Poudariti je treba, da zgornje ˇstiri moˇznosti v meniju vsebujejo tudi podmenije. Na sliki 1.4 je prikazan izgled menija.
Slika 1.4: Meni in gumbi, ki se nahajajo ob levi strani platna.
Vse funkcije, ki se nahajajo v meniju, skupaj z njihovimi kratkimi opisi delovanja, naˇstete od zgoraj navzdol glede na sliko 1.4, so:
• Naloˇzi/shrani graf
• Shrani graf: Trenutno prikazani graf na platnu shrani v tekstovno datoteko za kas- nejˇso rabo.
• Naloˇzi graf: Iz podane tekstovne datoteke prebere podatke za izris shranjenega grafa na platno.
• Osnovne druˇzine grafov
• Izriˇsi cikel: Izriˇse cikel dolˇzine, ki jo poda uporabnik.
• Izriˇsi cirkulant: Izriˇse cirkulant s parametri, ki jih poda uporabnik.
• Izriˇsi poln graf: Izriˇse poln graf na podanem ˇstevilu vozliˇsˇc.
• Izriˇsi pot: Izriˇse pot podane dolˇzine.
• Izriˇsi GPG: Izriˇse posploˇseni Petersenov graf glede na podane parametre.
• Ostala orodja
• Dvodelnost: Orodje, ki nam pove, ali je trenutno izrisani graf dvodelen ali ne.
• Oznake (on/off): Kot je razvidno ˇze iz imena funkcije, skrije ali ponovno prikaˇze oznake na vozliˇsˇcih.
• Premeˇsaj: Nakljuˇcno razporedi vozliˇsˇca po platnu (povezave med vozliˇsˇci ostanejo nespremenjene).
• Pribliˇzaj/odmakni pogled
• Pribliˇzaj: Pribliˇza pogled na platno.
• Odmakni: Odmakne pogled od platna.
• Nova vozliˇsˇca: Orodje, s katerim dodajamo na platno nova vozliˇsˇca.
• Nove povezave: Orodje, s katerim dodajamo na platno nove povezave med vozliˇsˇci.
• Razdaljna particija: Izpiˇse kardinalnosti tako imenovanih i-tih soseˇsˇcin grafa glede na izbrano vozliˇsˇce in jih tudi vizualno razporedi in prikaˇze na platnu.
• Avtomorfizem: S pomoˇcjo tega orodja lahko ugotavljamo ali je doloˇcena vneˇsena preslikava avtomorfizem tega grafa.
• Hamiltonova pot/cikel: Orodje, ki nam pove, ali tvorijo izbrane povezave Hamiltonovo pot ali cikel.
• Barvanje grafa: S tem orodjem lahko enostavno barvamo vozliˇsˇca grafa. Orodje nam tudi pove, ˇce smo naˇsli dobro barvanje vozliˇsˇc grafa.
• Izpisovanje (on/off): Vkljuˇci ali izkljuˇci dodatno izpisovanje pri uporabi naprednejˇsih funkcij.
• Preimenuj vozliˇsˇca: Ob izbiri lahko vozliˇsˇce s klikom nanj preimenujemo.
• Pomoˇc: Odpre PDF dokument, v katerem je bolj podrobno opisano delovanje aplikacije in njenih funkcij.
Ob kliku na katero izmed funkcij nam aplikacija v tekstovnem polju pod platnom izpiˇse navodila za uporabo te funkcije in pa tudi doloˇcene povratne informacije, ki so vezane na samo funkcijo. Bolj podroben opis tega okna sledi v naslednjem podrazdelku.
1.1.3 Okno za izpisovanje navodil in povratnih informacij
Okno za izpisovanje navodil in povratnih informacij je glavni naˇcin, s katerim aplikacija komu- nicira z uporabnikom. Seveda komunicira tudi na ostale naˇcine, kot je recimo obarvanje gumba funkcije, ki je trenutno v uporabi, z rdeˇco barvo, ali pa obarvanje in oznaˇcitev vozliˇsˇca grafa, nad katerim je miˇska. Tudi pri funkciji barvanja grafa se vozliˇsˇce, nad katerim je kazalec miˇske, ˇ
ze v naprej obarva z izbrano barvo. Kljub temu pa je potrebno uporabniku povedati veliko veˇc, kot mu lahko povemo z enostavnim barvanjem ali drugimi metodami. Zato se je avtor odloˇcil, da bo implementiral tudi tekstovno polje, v katerem program izpisuje navodila in sporoˇcila za uporabnika ter rezultate izvedenih algoritmov.
Eden bolj ilustrativnih primerov sporoˇcila uporabniku se prikaˇze ob kliku na gumb za barvanje grafa. Sporoˇcilo je sledeˇce:
Vkljuˇcili ste barvanje grafa. S pomoˇcjo barvne palete lahko sedaj barvate vozliˇsˇca.
Kliknite za ˇzeljeno barvo in lahko priˇcnete z barvanjem vozliˇsˇc!
Graf ni lih cikel ali poln graf. Po Brooksovem izreku je torej kromatiˇcno ˇstevilo grafa manjˇse ali enako 3.
Kot vidimo, vsebuje sporoˇcilo par kljuˇcnih delov. Najprej nam aplikacija sporoˇci, da smo uspeˇsno vkljuˇcili funkcijo barvanje grafa. To je povratna informacija na klik na gumb za barvanje grafa. V raˇcunalniˇstvu je koncept povratne informacije zelo pomemben [7]. ˇCe ne dobimo vsaj kakˇsne povratne informacije, potem kot konˇcni uporabniki aplikacije ne moremo vedeti, kdaj je aplikacija sprejela naˇs vnos in ga obravnava ter kdaj se je zgodilo nekaj nepriˇcakovanega in aplikacija vnosa enostavno ne more interpretirati. Brez povratne informacije bi se lahko zgodilo, da bi mi ˇcakali na raˇcunalnik, raˇcunalnik pa bi ˇcakal na nas.
Naslednji del sporoˇcila uporabniku so navodila za uporabo funkcije barvanja. Navodilo je kratko, jedrnato in dovolj natanˇcno, da si uporabnik osveˇzi spomin in zaˇcne z delom. ˇCe uporab- nik navodila ne razume in ne ve kako nadaljevati z delom, lahko v meniju na levi strani kadarkoli klikne na gumb Pomoˇc in si prebere bolj natanˇcna navodila za uporabo neke doloˇcene funkcije, s katero ima teˇzave. Navodila se odprejo v novem zavihku, tako da ni bojazni, da bi zaradi tega izgubili delo, ki smo ga do tedaj ˇze naredili.
Zadnji del sporoˇcila se pokaˇze le, ko je to relevantno, torej v tem primeru samo takrat, ko graf zadovolji pogojem Brooksovega izreka. Tu pa ne gre ne za povratno informacijo, ne za navodilo, ampak za pogojno sporoˇcilo, ki uporabniku (ˇce ne pozna Brooksovega izreka, ali pa je nanj le pozabil) olajˇsa delo. Uporabnik tako spozna zgornjo mejo kromatiˇcnega ˇstevila grafa in se lahko omeji na doloˇceno ˇstevilo barv.
Aplikacija ob ustreznem barvanju grafa uporabniku to tudi sporoˇci s sporoˇcilom: ,,Barvanje grafa je ustrezno!”. Sporoˇcilo se izpiˇse le, ˇce smo ustrezno pobarvali vsa vozliˇsˇca, medtem ko na vmesnih korakih uporabnik o njegovem napredku oziroma pravilnosti njegovega barvanja ni obveˇsˇcen. To moˇznost lahko vklopimo s klikom na gumb Izpisovanje (on/off). Takrat ob vsakem na novo pobarvanem vozliˇsˇcu dobimo sporoˇcilo: ,,Barvanje ni ustrezno!”, ˇce barvanje (ˇse) ni ustrezno.
S tem zakljuˇcujemo kratek opis aplikacije. Za bolj natanˇcno seznanitev z uporabo aplikacije si lahko bralec prebere diplomsko delo ,,Aplikacija za delo z grafi” [4], hkrati pa aplikacijo tudi sam preizkusi.
Poglavje 2
Zbiranje in analiza podatkov
V tem poglavju bomo spoznali metodologijo zbiranja podatkov o uporabi programa med ˇstudenti Pedagoˇske fakultete Univerze v Ljubljani, ki so uporabljali aplikacijo z0diak. Podatke bomo analizirali in interpretirali.
2.1 Priprava raziskave
Z raziskavo ˇzelimo ugotoviti, katere funkcionalnosti so ˇstudenti najveˇc uporabljali in katere funkcionalnosti po njihovem mnenju aplikaciji manjkajo in bi si jih ˇzeleli v novi razliˇcici. Z mentorjevo pomoˇcjo sem priˇsel tudi do naˇcina realizacije raziskave. Predlagal mi je, naj sestavim kratko anketo in jo dam izpolniti ˇstudentom po enem izmed njegovih predavanj. Na ta naˇcin so anketo izpolnili ˇstudenti, ki so aplikacijo z0diak zagotovo uporabljali vsaj dve ˇstudijski leti.
Omeniti velja tudi dejstvo, da so lahko ob izpolnjevanju vpraˇsalnika za dodatna pojasnila vpraˇsali mene osebno.
V naslednjem koraku sem pripravil anketo. V ta namen sem se moral najprej temeljito seznaniti z aplikacijo, spoznati katere funkcije vsebuje, kako se uporablja in katere funkcije se meni osebno zdijo nedodelane ali manjkajoˇce. Zapiski iz predmeta Teorija grafov [13] so mi bili v veliko pomoˇc, saj sem za vse grafovske primere in naloge poiskuˇsal uporabiti z0diak in funkcionalnosti, ki jih vsebuje. Ob tem sem si zapisoval, katere funkcije bi bile koristne in uporabne, a jih aplikacija ne vsebuje. Na ta naˇcin sem dodobra spoznal delovanje aplikacije in si izdelal seznam manjkajoˇcih, a po mojem mnenju uporabnih funkcionalnosti.
Na koncu je bilo potrebno le ˇse sestaviti anketo. Glede na namen raziskave sem se odloˇcil za vpraˇsanja o uporabnosti in pogostosti uporabe funkcij. ˇStudente sem povpraˇsal po njihovi oceni uporabnosti in frekvenci uporabe funkcij, ki jih aplikacija trenutno ˇze vsebuje. Namen teh dveh vpraˇsanj je dobiti vpogled v naˇcin dela z aplikacijo s strani ˇstudentov.
Tretje vpraˇsanje na anketi spraˇsuje po oceni zaˇzelenosti implementacije funkcij, ki jih z0diak trenutno ˇse ne vsebuje. Tu sem naˇstel funkcije, ki sem jih ob podrobnem branju zapiskov v aplikaciji pogreˇsal, ali pa se mi je zdela moja zamiˇsljena funkcionalnost ˇse posebej uporabna.
Seznam predlaganih funkcionalnosti so lahko ˇstudentje po ˇzelji dopolnili z njihovimi idejami, ki jih niso naˇsli med ˇze naˇstetimi, saj sem jim dal moˇznost prostega vnosa njihovih idej.
Pri ˇcetrtem vpraˇsanju sem si pomagal s Perlmanovim vpraˇsalnikom [11]. Nekatera vpraˇsanja iz njegovega originalnega vpraˇsalnika sem izpustil ali poenostavil. V tem zadnjem vpraˇsanju sem ˇstudente spraˇseval po uporabnosti, enostavnosti uporabe in uˇcenja uporabe ter o zadovoljstvu pri uporabi aplikacije. Gre za oceno celotne aplikacije in ne samo posameznih delov ali funkcij.
Na koncu vpraˇsalnika so imeli ˇstudentje moˇznost, da v obliki prostega teksta sporoˇcijo ˇse karkoli drugega, kar se jim je zdelo pomembno pri mojem delu.
Konˇcna razliˇcica anketnega vpraˇsalnika je na voljo kot priloga k temu diplomskemu delu.
2.2 Zbiranje in analiza podatkov
2.2.1 Zbiranje podatkov
Anketo sem izvedel 21.1.2016 po koncu predavanj pri predmetuRaziskovalni pristop k algebri in diskretni matematiki profesorja doc. dr. Primoˇza ˇSparla. ˇStudentje, ki obiskujejo ta pred- met na drugostopenjskem ˇstudijskem programu Pouˇcevanje, so v prejˇsnjih letih obiskovali veˇc predmetov, pri katerih so aplikacijo redno uporabljali, zato jo poznajo in jo znajo uporabljati.
ˇStudente sem najprej nagovoril in jim povedal kakˇsen je namen moje raziskave, ter jih prosil, ˇce lahko tisti, ki so aplikacijo uporabljali, izpolnijo kratko anketo. Izpolnilo jo je 26 ˇstudentov, a sem eno anketo takoj odstranil iz nabora za analizo, ko mi je ˇstudentka ob oddaji priznala, da aplikacije z0diak ni nikoli uporabljala. Analiziral sem torej 25 izpolnjenih anket.
2.2.2 Analiza podatkov
Zbrane ankete sem za laˇzjo analizo vnesel v razpredelnico na raˇcunalniku, kjer sem potem izvajal vso potrebno analizo. Za potrebe te raziskave nisem potreboval veˇc kot le povpreˇcje podanih odgovorov in pa standardni odklon, za vpogled v medsebojna odstopanja mnenj.
Vpraˇsanji uporabnosti in pogostosti uporabe funkcij v aplikaciji z0diak
Prvi dve vpraˇsanji se nanaˇsata na isto mnoˇzico funkcij, ki so jih morali ˇstudentje oceniti, tako da bomo ti dve vpraˇsanji obravnavali skupaj. Prvo vpraˇsanje se glasi:
,,Kako ocenjujete uporabnost spodaj naˇstetih funkcij?”,
drugo pa:
,,Katere funkcije aplikacije ste najbolj uporabljali?”.
ˇStudentje so morali vsako naˇsteto funkcionalnost oceniti z oceno od 1 do 5, pri ˇcemer 1 oznaˇcuje najmanj, 5 pa najbolj uporabno ali uporabljano funkcijo. V tabeli 2.1 se nahajajo povpreˇcja in standardni odkloni ocen funkcij za obe vpraˇsanji.
Zaporedna 1. vpraˇsanje (uporabnost) 2. vpraˇsanje (uporaba) ˇst. funkcije Povpreˇcje Std. odklon Povpreˇcje Std. odklon
1 3,83 1,01 2,92 1,32
2 4,76 0,44 3,84 1,18
3 4,48 0,82 3,60 1,12
4 3,32 1,15 2,44 1,26
5 3,60 1,29 2,60 1,53
6 3,24 1,13 2,56 1,36
7 4,76 0,60 3,76 1,01
8 4,12 1,30 3,28 1,31
9 4,12 1,36 3,40 1,42
10 3,92 1,26 3,44 0,53
11 3,68 1,11 2,44 1,33
12 4,28 1,14 3,88 1,05
Tabela 2.1: Povpreˇcja in standardni odkloni ocen funkcij iz prvega in drugega vpraˇsanja v anketi.
Glede na povpreˇcja ocen iz vpraˇsanja o uporabnosti funkcij lahko razberemo, da sta ˇstudentom najbolj uporabni funkciji za izrisovanje pripadnikov podprtih druˇzin grafov in za izris razdaljne particije grafa. Imeli sta namreˇc najviˇsjo povpreˇcno vrednost (4,76) izmed vseh funkcij. Pri teh dveh je bil tudi standardni odklon najniˇzji (0,44 in 0,60), kar pomeni, da so imeli ˇstudentje zelo enotno mnenje o teh dveh funkcionalnostih. Sledi jima funkcija, ki ugotavlja dvodelnost grafa in sicer ima povpreˇcno vrednost 4,48 in relativno nizek standardni odklon 0,82.
Studentje so kot najmanj uporabno funkcijo ocenili pribliˇˇ zevanje in oddaljevanje pogleda (povpreˇcje 3,24 in standardni odklon 1,13). Tudi sam nisem veliko uporabljal te funkcionalnosti, tako da me to ne ˇcudi. Redko smo morali namreˇc delati s tako velikimi grafi, da jih ne bi mogli liˇcno prikazati na zaslonu brez oddaljevanja pogleda. Hkrati pa je privzeta velikost vozliˇsˇc in povezav dovolj velika, da pri delu ne potrebujemo pribliˇzevanja pogleda, ˇce delamo z grafi, ki nimajo velikega ˇstevila vozliˇsˇc.
Pri drugem vpraˇsanju je bila priˇcakovano najbolje ocenjena funkcija za premikanje vozliˇsˇc grafa (povpreˇcje 3,88 in standardni odklon 1,05), sledi pa ji funkcija izrisovanja pripadnikov podprtih druˇzin grafov (povpreˇcje 3,84 in standardni odklon 1,18). Na tretjem mestu po uporabi sledi izris razdaljne particije (povpreˇcje 3,76 in standardni odklon 1,01). Kot lahko vidimo, so se tu mnenja ˇstudentov bolj razlikovala kot pri prejˇsnjem vpraˇsanju, razlika med najbolje ocenjenima funkcijama pa je zanemarljiva.
Med najmanj uporabljanimi funkcijami sta funkciji, ki sta vezani na oznake vozliˇsˇc. Prva je moˇznost vklopa/izklopa oznak vozliˇsˇc (povpreˇcje 2,44 in standardni odklon 1,26), druga pa je preimenovanje vozliˇsˇc (povpreˇcje 2,44 in standardni odklon 1,33). Sklepam, da ˇstudentje enostavno niso preimenovali oznak vozliˇsˇc, saj jim je bilo privzeto in avtomatsko poimenovanje oznak z naraˇsˇcajoˇcimi celimi ˇstevili sprejemljivo dobro. Vklop in izklop oznak vozliˇsˇc kot kaˇze prav tako nimata neke velike uporabne vrednosti, saj lahko oznake brez teˇzav ignoriramo in nadaljujemo z delom. Dve izmed situacij, v katerih bi ta funkcija priˇsla prav, sta situacija ko ˇ
zelimo narediti sliko grafa za izvoz in pa situacija ko bi delali s tako velikim grafom, da bi oznake zavzemale prepotreben prostor na platnu.
Vpraˇsanje zaˇzelenosti implementacije manjkajoˇcih funkcionalnosti
Tretje vpraˇsanje v anketi je bilo namenjeno ugotavljanju zaˇzelenosti implementacije doloˇcenih manjkajoˇcih funkcionalnosti. ˇStudentje so morali naˇstete funkcije oceniti s ˇstevilom od 1 do 5, pri ˇcemer 1 oznaˇcuje najmanj, 5 pa najbolj zaˇzeleno funkcijo. Imeli so tudi moˇznost dopisati svojo funkcionalnost, ˇce le-ta ni bila vsebovana v seznamu. Samo en/a ˇstudent/ka je dodatno zapisal/a, da si ˇzeli moˇznost shranjevanja grafov v obliki slike, kar je zelo dober predlog in se nanj ob zasnovi ankete sam nisem spomnil. Rezultati ankete so zbrani v tabeli 2.2.
Zap. ˇst. funkcije Povpreˇcje Std. odklon
1 4,44 0,92
2 4,68 0,56
3 4,12 1,09
4 3,84 1,03
5 4,36 0,81
6 4,84 0,47
7 4,36 0,64
8 3,88 0,78
9 4,32 0,99
10 4,40 0,96
11 4,12 0,97
12 4,00 1,04
13 3,20 1,15
14 3,58 1,21
15 3,21 1,35
Tabela 2.2: Povpreˇcja in standardni odkloni ocen zaˇzelenosti implementacije novih funkcij pri tretjem vpraˇsanju v anketi.
Rezultati analize so pokazali, da je najbolj zaˇzelena funkcija v applikaciji z0diak razveljavitev (angl. undo) s povpreˇcno oceno 4,84 in standardnim odklonom 0,47. Sam sem med delom z aplikacijo veˇckrat instinktivno pritisnil kombinacijo tipkCtrl + Z, ki v veˇcini aplikacij predstavlja bliˇznjico za razveljavitev zadnje akcije, a se z0diak ni odzval, saj razveljavitve ne podpira. Tudi ostali ˇstudentje so, glede na visoko povpreˇcje ocen, naleteli na to teˇzavo in si zato sedaj ˇzelijo implementacije te funkcionalnosti.
Naslednja funkcija, ki po povpreˇcni vrednosti ocen sledi razveljavitvi, je izraˇcun in prikaz oˇzine in premera grafa (povpreˇcna vrednost 4,68 in standardni odklon 0,56). Tudi tu so imeli ˇstudentje med seboj glede na standardni odklon kar podobno mnenje. Tretja najviˇsje uvrˇsˇcena funkcional- nost je izpis zaporedja stopenj (povpreˇcna vrednost 4,44 in standardni odklon 0,92). Zdi se kar malce nenavadno, da avtor aplikacije z0diak izpisa zaporedja stopenj grafa ni implementiral ˇze sam, saj algoritem za izraˇcun res ni zahteven.
Vpraˇsanje uporabniˇske izkuˇsnje
Zadnje (ˇcetrto) vpraˇsanje se nanaˇsa na uporabniˇsko izkuˇsnjo. Studentje so morali ocen-ˇ iti uporabnost aplikacije, enostavnost uporabe, enostavnost uˇcenja uporabe in zadovoljstvo pri uporabi aplikacije. Vsako izmed teh podroˇcij vsebuje nekaj trditev kot so ,,Je koristna”, ,,Lahko jo uporabljam brez pisnih navodil” ali ,,Dela tako, kot si ˇzelim, da deluje”. S ˇstevilko od vkljuˇcno 1 do 5 so morali ˇstudentje oceniti, v kolikˇsni meri se strinjajo s trditvami, pri ˇcimer 1 oznaˇcuje popolno nestrinjanje, 5 pa popolno strinjanje.
Zap. ˇst. trditve Povpreˇcna vrednost Std. odklon Uporabnost aplikacije
1 3.88 0.88
2 3.80 1.04
3 4.64 0.49
4 3.52 0.96
5 4.16 1.03
6 3.36 1.19
Enostavnost uporabe
1 4.16 1.11
2 3.56 1.19
3 3.96 1.10
4 3.56 0.96
5 2.92 1.35
Enostavnost uˇcenja uporabe
1 4.28 1.06
2 4.04 1.02
3 4.24 0.97
Zadovoljstvo
1 4.08 0.81
2 4.00 0.87
3 3.28 1.02
4 2.64 1.25
Tabela 2.3: Povpreˇcja in standardni odkloni ocen trditev iz zadnjega vpraˇsanja v anketi.
Poglejmo si najprej rezultate analize o uporabnosti aplikacije. ˇStudentje se v najveˇcji meri strinjajo, da je aplikacija koristna (povpreˇcna vrednost 4,64 in standardni odklon 0,49). Kljub koristnostni aplikacije vseeno menijo, da aplikacija ne izpolnjuje nujno vseh njihovih potreb, saj ima ta trditev najniˇzjo povpreˇcno vrednost 3,36 in najviˇsji standardni odklon 1,19, kar nakazuje doloˇceno mero razprˇsenosti mnenja ˇstudentov.
V razdelku Enostavnost uporabe imamo najniˇzjo povpreˇcno vrednost 2,92 in najviˇsji stan- dardni odklon 1,35 pri trditvi ,, ˇCe naredim napako, jo lahko hitro odpravim”, kar nakazuje na to, da je v aplikaciji res nujno potrebna funkcionalnost razveljavitve zadnje akcije. To je konsis- tentno z odgovori pri tretjem vpraˇsanju, kjer je bila najbolj zaˇzelena funkcija ravno razveljavitev zadnje akcije. Glede na povpreˇcno vrednost prve trditve (povpreˇcna vrednost 4,16 in standardni odklon 1,11) ˇstudentje menijo, da je aplikacija enostavna za uporabo in zanjo ne potrebujejo pisnih navodil (povpreˇcna vrednost 3,96 in standardni odklon 1,10).
Studenti so dobro ocenili enostavnost uˇˇ cenja uporabe, saj imajo vse tri trditve povpreˇcno oceno nad 4, standardni odklon pa vse okoli 1. Kljub temu pa so se ˇstudentje hitreje nauˇcili uporabljati aplikacijo, kot postali z njo spretni.
V zadnjem razdelku, ki se nanaˇsa na zadovoljstvo, so ˇstudentje ocenili, da so z aplikacijo zadovoljni in da je prijetna za uporabo (povpreˇcni oceni 4,08 in 4,00, ter standardna odklona 0,81 in 0,87). Kljub temu pa menijo, da aplikacija za njihov ˇstudij ni kljuˇcnega pomena (povpreˇcna vrednost 2,64 in standardni odklon 1,25).
2.3 Izbira novih funkcionalnosti
V prejˇsnjem razdelku smo videli, katerih novih funkcionalnosti si ˇzelijo ˇstudentje, ki so ap- likacijo uporabljali dalj ˇcasa. Naˇs cilj je bil, da v aplikacijo, glede na izsledke ankete, dodamo tri najbolj zaˇzelene funkcije. V tem razdelku analiziramo moˇznost implementacije teh funkcij in komentiramo moˇznost implementacije ˇse kakˇsne dodatne funkcije, ki ni priˇsla v sam vrh ˇzelja.
2.3.1 Razveljavitev zadnje akcije
Najbolj zaˇzelena funkcionalnost je bila razveljavitev zadnje akcije. Dandanes skoraj vsaka ap- likacija vsebuje nek sistem razveljavitve sprememb (poudariti je treba, da skoraj vse aplikacije, ki omogoˇcajo razveljavitev sprememb, omogoˇcaju tudi preklic razveljavitve spremembe in povr- nitev v stanje pred razveljavitvijo spremembe), ki jih delamo tekom dela z aplikacijo, pa naj bo to razveljavitev brisanja besede ali pa razveljavitev potega ˇcopiˇca v risarskih programih. Tako se zdi ta funkcionalnost ˇze skoraj samoumevna in zato je razumljivo, da si jo ˇstudentje ˇzelijo uporabljati tudi v tej aplikaciji. Strinjam se, da bi ta funkcionalnost moˇcno poenostavila uporabo aplikacije, saj moramo sedaj ob napaki v najslabˇsem primeru z delom zaˇceti od zaˇcetka, v najboljˇsem pa vsaj ponoviti par zadnjih akcij, ki smo jih izvedli.
Razvoja razveljavitve zadnje akcije bi se lahko lotili na dva naˇcina. Prvi je naˇceloma sila preprost. Ustvarili bi povezan seznam, katerega elementi so stanja grafa na platnu. Vsako vozliˇsˇce seznama ima kazalec na svojega predhodnika in naslednika. Ob vsaki spremembi na platnu bi se na konec seznama dodalo nov element, ki bi vseboval trenutno vsebino platna (to so vozliˇsˇca, povezave ter njihove lokacije, oznaˇcbe vozliˇsˇc, barve, itd.). Ob razveljavitvi zadnje akcije bi izbrisali vsebino platna, se pomaknili v povezanem seznamu na predhodnika trenutnega elementa in izrisali graf. Ce bi si ˇˇ zeleli preklicati naˇso razveljavitev zadnje akcije, bi morali postopek ponoviti v obratni smeri. S tem bi implementirali osnovno (ˇcetudi relativno prostorsko zahtevno) funkcionalnost razveljavitve zadnje akcije.
Drug naˇcin, ki je veliko bolj eleganten, pa je v programerskem svetu poznan kot ukazni vzorec (angl. command pattern), ki je del zasnovnih vzorcev (angl. design patterns) v objektnem programiranju ([3] in [12]). Vsako akcijo z vsemi potrebnimi informacijami, ki jo lahko sproˇzi uporabnik, se nekako zapiˇse v nek objekt in se ga poˇslje mehanizmu, ki skrbi za njihovo izvedbo.
Nabor moˇznih akcij je vnaprej doloˇcen (razliˇcne podprte funkcije), spreminjajo se samo podatki, s katerimi doloˇcena akcija operira. Za implementacijo razveljavitve zadnje akcije potrebuje vsaka funkcija metodo, s katero povrne stanje na stanje pred izvedbo akcije. Vse kar potem preostane je to, da si zapomnimo izvedene akcije. V primeru, ko ˇzeli uporabnik razveljaviti zadnjo akcijo, pogledamo zadnjo izvedeno akcijo in pokliˇcemo njeno metodo za povrnitev prvotnega stanja, kazalec trenutno izvedene akcije pa v povezanem seznamu prestavimo za en ˇclen nazaj. S tem bi implementirali funkcionalnost razveljavitve zadnje akcije na eleganten in prostorsko manj zahteven naˇcin.
Po pregledu programske kode, ki sestavlja aplikacijo, sem spoznal, da implementacija prve ali druge moˇznosti ne pride v poˇstev (oziroma bi bilo kaj takega zelo nepraktiˇcno in v nasprotju z uveljavljenimi standardi v raˇcunalniˇstvu), predvsem zato, ker avtor originalne aplikacije te funkcionalnosti ob razvoju aplikacije ni predvidel. Posledica takega razvoja je koda, ki ne sledi spremembam na platnu na naˇcin, smiselen za implementacijo razveljavitve zadnje akcije. Stanje na platnu se hrani v veˇc spremenljivkah, ki so med seboj na prvi pogled neodvisne. Podrobnejˇsa analiza je pokazala, da veliko ˇstevilo globalnih spremenljivk v najslabˇsem primeru onemogoˇca,
v najboljˇsem primeru pa zelo oteˇzuje sledenje spremembam v delovanju programa. ˇCe bi ˇzeleli implementirati prvi algoritem za razveljavitev zadnjih akcij, bi zato morali ob vsaki spremembi shraniti spremenljivke, ki so se spremenile. To bi pomenilo zelo natanˇcno poglabljanje v samo drobovje aplikacije in bi vzelo ogromno ˇcasa, saj iz kode na prvi pogled ni razvidno, katere spre- menljivke so uporabljene samo v nekem delu programa in katere povsod. Drugi algoritem bi priˇsel v poˇstev v primeru, da bi avtor vgradil akcije v samostojne objekte ˇze od samega zaˇcetka razvoja aplikacije. Predelava programa bi v tem primeru pomenila popoln prepis aplikacije z upoˇstevanjem ukaznega vzorca pri razvoju aplikacije. Implementacija funkcionalnosti razveljav- itve zadnje akcije zaradi nesorazmernosti potrebnega truda in rezultatom le-tega zato ne pride v poˇstev v okviru tega diplomskega dela. Vsekakor pa je to eden izmed pomembnejˇsih korakov ob morebitni obˇsirnejˇsi predelavi aplikacije v prihodnosti.
2.3.2 Izraˇ cun in prikaz oˇ zine ter premera grafa
Druga najbolj zaˇzelena funkcionalnost je bila izraˇcun in prikaz oˇzine ter premera grafa. Tu gre pravzaprav za dve razliˇcni funkcionalnosti, zato ju bomo kot taki tudi obravnavali. Zaˇcnimo z oˇzino grafa.
Oˇzina grafa
Najprej definirajmo oˇzino enostavnega neusmerjenega grafa.
Definicija: Imejmo graf Γ = (V, E). Oˇzina grafa je tedaj definirana kot dolˇzina najkrajˇsega cikla v Γ oziroma je definirana kot∞, ˇce Γ ne vsebuje nobenega cikla.
Kot cikel tu smatramo sklenjen sprehod, ki se torej zaˇcne in konˇca v istem vozliˇsˇcu, sicer pa ne obiˇsˇce nobenega vozliˇsˇca dvakrat.
Pri oˇzini grafa se velikokrat omenja tudikletke, ˇse posebej kubiˇcne. To so najmanjˇsi moˇzni kubiˇcni grafi (vsa vozliˇsˇca imajo stopnje 3) z dano oˇzinog. Takim grafom se reˇce tudig-kletke.
Najbrˇz je najbolj znan Petersenov graf, ki je edinstvena 5-kletka (torej najmanjˇsi kubiˇcni graf z oˇzino 5). Heawood-ov graf je 6-kletka, McGee-jev graf 7-kletka in Tutte-Coxeter-jev graf 8-kletka [10]. Predstavljeni so na sliki 2.1.
Slika 2.1: Primeri ˇstirih manjˇsih kletk. Od leve proti desni: Petersenov graf, Heawoodov graf, McGeejev graf in Tutte-Coxeterjev graf.
Za izraˇcun oˇzine grafa potrebujemo seznam vozliˇsˇc in povezav grafa. Le-te imamo v aplikaciji
z0diak na voljo v objektuGraph. Pri implemetaciji te funkcionalnosti nas torej niˇc ne omejuje. V svoji raziskavi sem naˇsel tudi dva algoritma za izraˇcun oˇzine grafa, ki pa sta bolj podrobno opisana v podrazdelku 3.3.1, kjer je tudi opisano, kako smo to funkcionalnost dejansko implementirali v aplikacijo.
Premer grafa
Najprej definirajmo premer grafa. Ponovno se bomo omejili samo na enostavne neusmerjene grafe.
Definicija: Premer enostavnega neusmerjenega grafa Γ = (V, E) je najdaljˇsa razdalja med katerimkoli parom vozliˇsˇcv, u∈V.
Razdalja med dvema vozliˇsˇcema grafa je ˇstevilo povezav v najkrajˇsi poti, ki povezuje ti dve vozliˇsˇci. ˇCe ne obstaja nobena pot, ki bi povezovala dani dve vozliˇsˇci grafa, potem je razdalja med tema dvema vozliˇsˇcema enaka∞.
Tudi za izraˇcun premera grafa zadoˇsˇca seznam vozliˇsˇc in povezav. Prav tako potrebujemo algoritem, s katerim bomo izmerili najkrajˇse poti med poljubnimi pari vozliˇsˇc grafa. Tak algo- ritem poznamo pod imenom Dijkstrov algoritem [5], poglavje 4.4. Opis njegove uporabe za to funkcionalnost je podan v podrazdelku 3.4.1.
2.3.3 Izpis zaporedja stopenj
Tretja najbolj zaˇzelena funkcionalnost je izpis zaporedja stopenj. Gre za enostavno funkcijo, ki pa nam lahko ob pogostem delu z aplikacijo olajˇsa delo. Tudi tu najprej podajmo definicijo zaporedja stopenj.
Definicija: Zaporedje stopenj neusmerjenega grafa Γ = (V, E) je padajoˇce zaporedje stopenj vozliˇsˇc grafa Γ, pri ˇcemer je dolˇzina zaporedja enaka|V|.
Zaporedje stopenj je seveda neodvisno od izbrane reprezentacije grafa, zato imajo izomorfni grafi isto zaporedje stopenj. Moramo pa biti pozorni, saj isto zaporedje stopenj ˇse ne pomeni nujno, da sta dva grafa izomorfna. Zaporedja stopenj grafa torej ne moremo uporabiti za iden- tifikacijo toˇcno doloˇcenega grafa.
Kot zanimivost omenimo ˇse tako imenovani problem zaporedja stopenj grafa. To je problem, kjer ˇzelimo za podano padajoˇce zaporedje naravnih ˇstevil poiskati vsaj enega ali kar vse grafe, ki imajo zaporedje stopenj enako podanemu zaporedju ˇstevil. Podano zaporedje, za katerega lahko najdemo vsaj en graf, ki ima tako zaporedje stopenj, imenujemo grafiˇcno. Nobeno padajoˇce zaporedje naravnih ˇstevil z liho vsoto, zaradi sodosti vsote stopenj vseh vozliˇsˇc v poljubnem grafu (kar nam zagotavlja Lema o rokovanju [6]), ne ustreza nobenemu grafu in zato ni grafiˇcno [16].
Seveda pa niti vsako padajoˇce zaporedje naravnih ˇstevil s sodo vsoto stopenj vozliˇsˇc ni grafiˇcno.
Tu omenimo, da obstaja preprost algoritem za ugotavljanje grafiˇcnosti zaporedja stopenj. ˇCe je le-to grafiˇcno, lahko s preprostim algoritmom vsaj en tak graf tudi konstruiramo. Ta dva algoritma bi bilo tako moˇzno implementirati v aplikacijo v morebitni nadaljnji posodobitvi.
Primer istega zaporedja stopenj za dva neizmorfna grafa je podan na sliki 2.2. Neizomorfnost
lahko dokaˇzemo na enostaven naˇcin. Pogledati moramo le sosede vozliˇsˇca stopnje 3. Hitro opazimo, da ima vozliˇsˇce stopnje tri na zgornjem grafu dva soseda stopnje dva in le enega soseda stopnje ena, medtem ko ima vozliˇsˇce stopnje tri na spodnjem grafu dva soseda stopnje ena in enega soseda stopnje dva. Ker v vsakem grafu obstaja le eno vozliˇsˇce stopnje 3 in imata ti dve vozliˇsˇci med sabo razliˇcne prej naˇstete lastnosti, sta grafa medseboj neizomorfna, saj se ne ujemata v vseh njunih lastnostih.
Slika 2.2: Dva neizomorfna grafa z istim zaporedjem stopenj (3,2,2,2,2,1,1,1).
Ceprav bi morali ˇˇ studentje brez teˇzav znati zapisati zaporedje stopenj poljubnega danega grafa, so si vseeno zaˇzeleli, da bi aplikacija z0diak vsebovala tudi to funkcionalnost. Najbrˇz zato, ker je za veˇcje grafe zapis zaporedja stopenj dolgoˇcasno delo, ki zahteva nekaj natanˇcnosti, vseeno pa je ujemanje zaporedja stopenj dveh grafov prvi potreben pogoj za njuno izomorfnost. Funkcijo bomo zato implementirali v aplikacijo predvsem zaradi priroˇcnosti. Za izpis zaporedja stopenj grafa ne potrebujemo zahtevnih algoritmov, le sprehod ˇcez vsa vozliˇsˇca in urejanje dobljenega seznama. Podroben opis algoritma se nahaja v podrazdelku 3.2.1.
2.3.4 Preverjanje zadostnih pogojev za obstoj Hamiltonovega cikla
Ta funkcija sicer ni bila v samem vrhu po zaˇzelenosti, vendar pa se zdi, da bi lahko njena implementacija v doloˇcenih primerih precej pripomogla pri preverjanu hamiltonskosti danega grafa. Aplikacija namreˇc ˇze vsebuje funkcionalnost, s katero lahko uporabnik sam iˇsˇce tak cikel.
Zato se zdi smiselno, da dodamo v aplikacijo tudi preverjanje pogojev izrekov P´osa, Oreja in Diraca, ki podajajo zadostne pogoje za obstoj Hamiltonovega cikla. Na ta naˇcin bi pomagali ˇstudentom pri ugotavljanju, ali graf vsebuje tak cikel ali ne. Izmed vseh treh je najmoˇcnejˇsi izrek P´osa in ˇze samo z njegovo implementacijo bi dobili najboljˇsi moˇzen odgovor na vpraˇsanje hamiltonskosti grafa [13]. Kljub temu sem se odloˇcil tudi za implementacijo funkcionalnosti preverjanja pogojev izreka Oreja in Diraca, saj bodo lahko na ta naˇcin ˇstudentje na razliˇcnih primerih ugotovili kako se izreki med seboj primerjajo po moˇci. Prav tako ju bodo lahko uporabili za uˇcenje in vadbo. Zaˇcnimo s izrekom P´osa.
Izrek P´osa: Naj bo Γ graf redan≥3, za katerega velja naslednje. Za vsak 1≤k <(n−1)/2 obstaja manj kotkvozliˇsˇc stopnje najveˇckv Γ, ˇce pa jenliho ˇstevilo, dodatno velja ˇse, da v Γ obstaja najveˇc (n−1)/2 vozliˇsˇc stopnje najveˇc (n−1)/2. Tedaj Γ premore Hamiltonov cikel.
Iz samega izreka ˇze lahko razberemo, da bomo problem lahko reˇsili s sprehodom ˇcez vsek in hkrati tudi ˇcez zaporedje stopenj grafa, kjer bomo ˇsteli ˇstevilo vozliˇsˇc doloˇcene stopnje. ˇCasovna kompleksnost algoritma tako ne bo previsoka za implementacijo, saj bo najveˇcO(|V|log(|V|)), kjer je V mnoˇzica vozliˇsˇc grafa. Veˇcina kompleksnosti izhaja iz funkcije za izraˇcun zaporedja stopenj saj vsebuje sortiranje. Taka kompleksnost nas za grafe, ki jih ˇstudentje vnaˇsajo v pro- gram, ne skrbi. Teˇzave ne bi nastopile niti v primeru, ˇce bi v aplikacijo vnesli graf, ki vsebuje npr. 1000 vozliˇsˇc.
Diracov izrek: Naj bo Γ graf reda n ≥ 3, v katerem je poljubno vozliˇsˇce stopnje vsaj n/2.
Tedaj Γ premore Hamiltonov cikel.
Tudi pri Diracovem izreku vidimo, da ni algoritmiˇcno zahteven in da ga bomo lahko imple- mentirali kar z lastnim znanjem. Kompleksnost algoritma bo podobno kot prejO(|V|log(|V|)), saj potrebujemo za pregled samo en sprehod ˇcez zaporedje stopenj grafa.
Orejev izrek: Naj bo Γ graf redan≥3, v katerem je vsota stopenj poljubnega para nesosednjih vozliˇsˇc vsajn. Tedaj Γ premore Hamiltonov cikel.
Izmed vseh treh izrekov, se zdi Orejev izrek ˇse najteˇzji za implementacijo, saj bomo morali pre- gledati vsak par nesosednjih vozliˇsˇc in preveriti vsoto njunih stopenj. Vseeno bil sem prepriˇcan, da ne bo predstavljal veˇcjih teˇzav, zato sem se odloˇcil tudi za njegovo implementacijo v aplikacijo.
Izrek P´osa je izmed vseh treh izrekov najmoˇcnejˇsi, kar je dokazano v zapiskih [13], str. 53.
Diracov in Orejev izrek namreˇc sledita iz izreka P´osa. Graf na sliki 2.3 izpolnjuje le pogoje izreka P´osa, ne zadoˇsˇca pa pogojem Diracovega in Orejevega izreka, kar nakazuje na dejstvo, da je P´osev izrek res najmoˇcnejˇsi.
Slika 2.3: Graf, ki ne zadoˇsˇca pogojem Diracovega in Orejevega izreka, izpolnjuje pa pogoje izreka P´osa ([13], str. 52).
2.3.5 Izvoz slike grafa v slikovni obliki
Ob pregledovanju podatkov, pridobljenih z anketo, sem med dodatnimi predlogi za funkcional- nosti zasledil tudi predlog za izvoz grafa v slikovni obliki. Ob sestavljanju ankete na to funkcional- nost nisem pomislil, zato sem bil nad predlogom prijetno preseneˇcen.
Kar nekaj ˇstudentov uporablja aplikacijo z0diak za izdelavo slik grafov, ki jih potem uporabijo v raznih seminarskih nalogah in diplomskih delih. Doslej je bil postopek shranjevanja slike sledeˇc. Najprej moramo v aplikaciji izdelati graf. Tu lahko uporabimo ˇze vgrajene grafe ali pa ga ustvarimo roˇcno z dodajanjem vozliˇsˇc in povezav. Nato ustvarimo zaslonsko sliko celotnega zaslona in jo shranimo. Taka zaslonska slika vsebuje tudi orodno vrsto, odprte zavihke in ostale
elemente, ki jih seveda ne ˇzelimo imeti v konˇcni sliki, zato moramo sliko obrezati, da nam na njej ostane samo ˇse graf. ˇSele nato lahko sliko shranimo in jo vstavimo v dokument. Slika, izdelana na tak naˇcin, ima sivo ozadje (platno) in tako stilsko ne sodi v nekatere dokumente, ki imajo po veˇcini belo podlago.
Proces je po nepotrebnem preveˇc zahteven in ˇce ne drugega za veˇcino ˇstudentov vsaj nadleˇzen.
Funkcija za izvoz bi bistveno olajˇsala zgoraj opisan proces, zato sem se odloˇcil, da implementiram tudi to funkcionalnost.
Po kratkem raziskovanju na spletu sem spoznal, da je izvoz platna v slikovni obliki enostaven in zanj ne potrebujemo kakega zahtevnega algoritma.
Poglavje 3
Razvoj novih funkcionalnosti
Preden predstavimo algoritme, s katerimi bomo v aplikacijo z0diak implementirali izbrane nove funkcionalnosti, si najprej poglejmo osnovno podatkovno strukturo v kateri je zapisan graf in vse njene lastnosti.
3.1 Podatkovna struktura aplikacije in dodajanje novih el- ementov na platno
Aplikacija z0diak hrani graf v globalni spremenljivki Graph, ki je tipaGraph data structure.
Graph torej vsebuje tako tabelo vozliˇsˇcnodes in tabelo povezavlines.
1 f u n c t i o n G r a p h _ d a t a _ s t r u c t u r e () { // s t r u k t u r a g r a f a 2 t h i s. n o d e s = new A r r a y () ;
3 t h i s. l i n e s = new A r r a y () ; 4 }
5
6 f u n c t i o n n o d e () { // s t r u k t u r a v o z l i s c a 7 t h i s. c o n s t r u c t = new P a t h . C i r c l e () ; 8 }
Delˇcek kode 3.1: Osnovna podatkovna struktura grafa v aplikaciji.
3.1.1 Dodajanje novega vozliˇ sˇ ca
Ce ˇˇ zeli uporabnik grafu dodati novo vozliˇsˇce, z miˇsko klikne na gumbNova vozliˇsˇca in nato klikne na poljubno mesto na platnu, kamor ˇzeli postaviti vozliˇsˇce. Ob kliku na platno, se sproˇzi dogodek (angl. event), ki v sebi nosi podatke kot so lokacija klika in podobno. Lokacijo do- godka potem uporabimo v drugem koraku dodajanja vozliˇsˇca, saj ustvarimo nov krog z lokacijo (event.point) in polmerom 12 enot (4. vrstica v delˇcku kode 3.2).
1 // I n i c i a l i z i r a m o e l e m e n t
2 G r a p h . n o d e s [ G r a p h . n o d e s . l e n g t h ] = new n o d e () ; 3 // D e f i n i r a m o l o k a c i j o in v e l i k o s t v o z l i s c a
4 G r a p h . n o d e s [ G r a p h . n o d e s . l e n g t h - 1]. c o n s t r u c t = new P a t h . C i r c l e ( e v e n t . point , 12) ; 5 // V o z l i s c u n a s t a v i m o b a r v o na m o d r o
6 G r a p h . n o d e s [ G r a p h . n o d e s . l e n g t h - 1]. c o n s t r u c t . f i l l C o l o r = " #00 F ";
7 // V o z l i s c u n a s t a v i m o m e s a n j e b a r v
8 G r a p h . n o d e s [ G r a p h . n o d e s . l e n g t h - 1]. c o n s t r u c t . b l e n d M o d e = ’ e x c l u s i o n ’;
9 // V o z l i s c u d o d a m o f u n k c i o n a l n o s t b a r v a n j a na r d e c o ob p r e m i k u m i s k e nad v o z l i s c e 10 G r a p h . n o d e s [ G r a p h . n o d e s . l e n g t h - 1]. c o n s t r u c t . a t t a c h (’ m o u s e e n t e r ’, f u n c t i o n () { 11 t h i s. f i l l C o l o r = ’ red ’;
12 }) ;
13 // V o z l i s c u d o d a m o f u n k c i o n a l n o s t b a r v a n j a na m o d r o ob p r e m i k u m i s k e z v o z l i s c a 14 G r a p h . n o d e s [ G r a p h . n o d e s . l e n g t h - 1]. c o n s t r u c t . a t t a c h (’ m o u s e l e a v e ’, f u n c t i o n () { 15 if ( a d d i n g E d g e == f a l s e || E d g e C o n s t r u c t i o n == f a l s e)
16 t h i s. f i l l C o l o r = ’ b l u e ’;
17 e l s e if ( s e t A c t i v e )
18 t h i s. f i l l C o l o r = ’ b l u e ’; 19 }) ;
20 // I n i c i a l i z i r a m o n a p i s na v o z l i s c u
21 G r a p h . n o d e s [ G r a p h . n o d e s . l e n g t h - 1]. c o n s t r u c t . v e r t e x = new P o i n t T e x t ; 22 // N a s t a v i m o b a r v o n a p i s a na b e l o
23 G r a p h . n o d e s [ G r a p h . n o d e s . l e n g t h - 1]. c o n s t r u c t . v e r t e x . f i l l C o l o r = ’ w h i t e ’;
24 // N a s t a v i m o o z n a k o v o z l i s c a
25 G r a p h . n o d e s [ G r a p h . n o d e s . l e n g t h - 1]. c o n s t r u c t . v e r t e x . c o n t e n t = c o n t e n t _ i n p u t ; 26 // N a s t a v i m o p o l o z a j n a p i s a nad l o k a c i j o v o z l i s c a
27 G r a p h . n o d e s [ G r a p h . n o d e s . l e n g t h - 1]. c o n s t r u c t . v e r t e x . p o s i t i o n = G r a p h . n o d e s [ G r a p h . n o d e s . l e n g t h - 1]. c o n s t r u c t . p o s i t i o n ;
28 // U s t v a r i m o p r a z n o t a b e l o sosedov , saj je b i l o v o z l i s c e r a v n o k a r u s t v a r j e n o in se n i m a s o s e d o v
29 G r a p h . n o d e s [ G r a p h . n o d e s . l e n g t h - 1]. c o n s t r u c t . n e i g h b o u r s = new A r r a y () ;
Delˇcek kode 3.2: Delˇcek kode, ki doda v graf novo vozliˇsˇce na mesto miˇskinega klika na platnu.
Ob premikanju vozliˇsˇca s klikom nanj in vleˇcenjem, se v strukturi posodobi lokacija tega vozliˇsˇca na platnu. Prav tako se morajo ob vleˇcenju posodobiti tudi vse povezave, ki imajo to vozliˇsˇce za svoje krajiˇsˇce.
3.1.2 Dodajanje nove povezave
Novo povezavo dodamo na platno tako, da najprej z miˇsko kliknemo na levi strani na gumb Nove povezave, nato pa kliknemo na prvo vozliˇsˇce, ter nato ˇse na drugo vozliˇsˇce med katerima ˇ
zelimo ustvariti povezavo. Prvo vozliˇsˇce se shrani v spremenljivko startingPoint, drugo pa v spremenljivkoendPoint.
1 // I n i c i a l i z i r a m o n o v o p o v e z a v o z z a c e t n o in k o n c n o l o k a c i j o
2 G r a p h . l i n e s [ G r a p h . l i n e s . l e n g t h ] = new P a t h . L i n e ( s t a r t i n g P o i n t . p o s i t i o n , e n d P o i n t . p o s i t i o n ) ;
3 // S h r a n i m o si z a c e t n o v o z l i s c e p o v e z a v e
4 G r a p h . l i n e s [ G r a p h . l i n e s . l e n g t h - 1]. e d g e S t a r t = s t a r t i n g P o i n t ; 5 // S h r a n i m o si k o n c n o v o z l i s c e p o v e z a v e
6 G r a p h . l i n e s [ G r a p h . l i n e s . l e n g t h - 1]. e d g e E n d = e n d P o i n t ; 7 // N a s t a v i m o b a r v o p o v e z a v e na c r n o
8 G r a p h . l i n e s [ G r a p h . l i n e s . l e n g t h - 1]. s t r o k e C o l o r = ’ b l a c k ’;
9 // N a s t a v i m o s i r i n o p o v e z a v e na 4
10 G r a p h . l i n e s [ G r a p h . l i n e s . l e n g t h - 1]. s t r o k e W i d t h = 4;
11 }) ;
Delˇcek kode 3.3: Delˇcek kode, ki doda v graf novo povezavo med izbranima vozliˇsˇcema.
Vsako vozliˇsˇce zase v tabeli Graph.nodes[i].construct.neighbours, kjer je i zaporedno ˇstevilo nekega vozliˇsˇca, hrani svoje sosede. Ob dodajanju nove povezave se doda v tabelo sosedov prvega vozliˇsˇca nov sosed z ukazom Graph.nodes[i].construct.neighbours.push(endPoint). Postopek je treba ponoviti tudi za drugo vozliˇsˇce, le da tu dodamo elementstartingPoint.
V naslednjih petih razdelkih se bomo lotili implementacije izbranih novih funkcionalnosti.
Opisali bomo tako algoritme, s katerimi bomo reˇsili probleme, kot tudi kodo v programskem jeziku JavaScript, ki je osnova aplikacije z0diak.
3.2 Izpis zaporedja stopenj
Za implementacijo je izmed zaˇzelenih funkcionalnosti najlaˇzji izpis zaporedja stopenj, zato se ji posvetimo najprej.
3.2.1 Algoritem za izraˇ cun zaporedja stopenj
Algoritem za izraˇcun zaporedja stopenj je relativno enostaven. Najprej se moramo sprehoditi ˇ
cez vsa vozliˇsˇca grafa in si zapomniti njihovo ˇstevilo sosedov. Nato ta seznam uredimo v padajoˇce zaporedje, ga loˇcimo z vejicami in na vsaki strani obdamo z oklepaji. Tako dobimo zaporedje stopenj grafa.
3.2.2 Implementacija
Implementacija zgornjega algoritma v programskem jezikuJavaScript, ki je potrebna za izpis zaporedja stopenj, je precej preprosta, zato jo navajamo v celoti.
1 // F u n k c i j a za i z r a c u n in p r i k a z z a p o r e d j a s t o p e n j g r a f a 2 Z a p o r e d j e S t o p e n j = f u n c t i o n ( s i l e n t ) {
3 if ( G r a p h _ l o a d e d ) {
4 // I n i c i a l i z i r a m o tabelo , ki bo v s a b o v a s t o p n j e v o z l i s c 5 var z a p o S t o p e n j = new A r r a y () ;
6 // S h r a n i m o si s t e v i l o s o s e d o v p o s a m e z n e g a v o z l i s c a 7 for (var i = 0; i < G r a p h . n o d e s . l e n g t h ; i ++) {
8 z a p o S t o p e n j . p u s h ( G r a p h . n o d e s [ i ]. c o n s t r u c t . n e i g h b o u r s . l e n g t h ) ;
9 }
10 // S o r t i r a m o s e z n a m od n a j v e c j e g a do n a j m a n j s e g a e l e m e n t a
11 z a p o S t o p e n j = z a p o S t o p e n j . s o r t (f u n c t i o n ( a , b ) { r e t u r n b - a ; }) ; 12 // I n i c i a l i z i r a m o niz za p r i k a z u p o r a b n i k u
13 var z a p o r e d j e T e x t = new S t r i n g (" ") ;
14 // V niz n a n i z a m o z a p o r e d j e stopenj , l o c e n a z v e j i c a m i 15 for (var i = 0; i < G r a p h . n o d e s . l e n g t h ; i ++) {
16 if ( z a p o r e d j e T e x t != " ") { 17 z a p o r e d j e T e x t += " , ";
18 }
19 z a p o r e d j e T e x t += z a p o S t o p e n j [ i ];
20 }
21 // P r i k a z e m o z a p o r e d j e s t o p e n j u p o r a b n i k u g l e d e na p a r a m e t e r s i l e n t
22 if ( s i l e n t === t r u e) {
23 r e t u r n z a p o S t o p e n j
24 }
25 e l s e {
26 d o c u m e n t . g e t E l e m e n t B y I d (’ a r e a ’) . v a l u e = " Z a p o r e d j e s t o p e n j : ( " + z a p o r e d j e T e x t + " ) . ";
27 }
28 }
29 }
Delˇcek kode 3.4: Implementacija algoritma za prikaz zaporedja stopenj grafa.
3.3 Izraˇ cun in prikaz oˇ zine grafa
Ena izmed funkcionalnosti, ki so jo ˇstudentje ocenili kot zelo zaˇzeleno, je tudi izraˇcun in prikaz oˇzine grafa. Ta problem ni tako enostaven kot izraˇcun in prikaz zaporedja stopenj grafa, kljub temu pa ga z nekaj dela lahko uˇzenemo.
3.3.1 Algoritem za izraˇ cun oˇ zine grafa
Naˇsel sem dva razliˇcna algoritma za iskanje najkrajˇsega cikla v grafu.
Prvi algoritem temelji na iskanju v ˇsirino (angl. breadth-first search ali okrajˇsano BFS).
To iskanje je implementirano z vrsto. Zaˇcnemo v nekem vozliˇsˇcu grafa Γ, dodamo njegove sosede na konec v vrsto, vzamemo prvega iz vrste in postopek ponavljamo, dokler ne najdemo iskanega vozliˇsˇca ali pa ne obiˇsˇcemo vseh vozliˇsˇc grafa. ˇCasovna zahtevnost takega algoritma je O(|V|+|E|), kjer je Γ = (V, E).
Pri uporabi iskanja v ˇsirino pravzaprav iˇsˇcemo vozliˇsˇce, do katerega smo od korena grafa (tj.
vozliˇsˇca, v katerem smo zaˇceli iskanje) priˇsli po dveh razliˇcnih poteh. ˇCe tako vozliˇsˇce obstaja, potem smo naˇsli cikel. Dolˇzino cikla izraˇcunamo tako, da seˇstejemo dolˇzini teh dveh poti, ki povezujeta koren in najdeno vozliˇsˇce. ˇCe je dolˇzina najdenega cikla krajˇsa od do sedaj najdenih ciklov, si jo zapomnimo in iskanje nadaljujemo, dokler nismo obiskali vseh vozliˇsˇc v grafu. ˇCe iskanje ponovimo iz vseh vozliˇsˇc grafa Γ, smo si zagotovili, da smo naˇsli najkrajˇsi cikel in s tem tudi oˇzino grafa. ˇCasovna zahtevnost je tedaj enaka O(|V| · |E|) [9].
Drugi algoritem pa temelji na Dijkstrovem algoritmu iskanja najkrajˇse poti. Za vsako povezavo e∈E, kjer Γ = (V, E), ustvarimo graf Γ0, ki je skorajda identiˇcen grafu Γ, le da mu odvzamemo povezavoe. Torej Γ0 = (V, E\ {e}). Nato s pomoˇcjo Dijkstrovega algoritma poiˇsˇcemo najkrajˇso pot med vozliˇsˇci, ki ju je povezovala povezavae. ˇCe je ta pot krajˇsa od do sedaj najdene najkrajˇse poti, potem si jo zapomnimo in nadaljujemo z iskanjem, dokler nismo priˇsli ˇcez vse povezave v Γ. Na koncu dolˇzini najkrajˇse najdene poti priˇstejemo 1 za dolˇzino povezave, ki smo jo odstranili in tako dobimo oˇzino grafa.
3.3.2 Implementacija algoritma za izraˇ cun oˇ zine grafa
Za implementacijo sem si izbral prvi algoritem, ki iˇsˇce s pomoˇcjo iskanja v ˇsirino. Pseudo- koda, povzeta po [9], se nahaja spodaj.
functionOzinaGrafa(Γ) ozina← ∞
for allv∈V(Γ)do S← ∅
R← {v}
P redhodnik(v)←null Oddaljenost(v)←0 whileR6=∅ do
choose x∈R S←S∪ {x}
R←R\ {x}
for ally∈Sosedi(x)\ {P redhodnik(x)} do if y /∈S then
P redhodnik(y)←x
Oddaljenost(y)←Oddaljenost(x) + 1 R←R∪ {y}
else
ozina←min{ozina, Oddaljenost(x) +Oddaljenost(y) + 1}
end if end for end while end for returnozina end function
Zgornji algoritem nam vrne ˇstevilo, ki predstavlja oˇzino grafa. Velikokrat pa uporabnika zanima tudi, kako najti vsaj en najkrajˇsi cikel v grafu. Zato bomo zgornjemu algoritmu dodali ˇse eno malenkost. Ko najdemo neko manjˇso oˇzino grafa, si v posebno strukturo (v tem primeru kar tabelo), zapiˇsemo katera so tista vozliˇsˇca, ki so nam dala trenutno najkrajˇsi cikel. Po tem, ko se algoritem izvede do konca, imamo v posebni tabeli shranjena vozliˇsˇca najkrajˇsega cikla, zato lahko usrezne povezave obarvamo z drugo barvo in tako uporabniku na vizualen naˇcin podamo povratno informacijo o najkrajˇsem najdenem ciklu.
Kode zaradi njene obseˇznosti v samem diplomskem delu ne bom prikazal.
3.4 Izraˇ cun in prikaz premera grafa
3.4.1 Algoritem za izraˇ cun premera grafa
Algoritem za izraˇcun premera grafa je sledeˇc.
Za vsako vozliˇsˇce v grafu izvedemo Dijkstrov algoritem, ki nam izraˇcuna razdalje od izhodiˇsˇcnega vozliˇsˇca do vseh ostalih vozliˇsˇc. Pregledamo razdalje in si zapomnimo najveˇcjo. Na koncu nam da najdaljˇsa razdalja premer grafa. Vse kar ˇse potrebujemo, je to, da obarvamo pripadajoˇco pot in jo s tem prikaˇzemo uporabniku.
Ceprav se zdi algoritem na prvi pogled enostaven, je implementacija vseeno netrivialna.ˇ
3.4.2 Implementacija algoritma za izraˇ cun in prikaz premera grafa
V aplikaciji z0diak je graf shranjen v posebni strukturi, ki vsebuje seznama vozliˇsˇca in povezav, kot tudi njihove oznaˇcbe, barve za prikaz, itd. Za izvedbo Dijkstrovega algoritma [15] pa potrebu- jemo sosednostno matriko. Najprej moramo torej grafovsko strukturo preoblikovati v sosednostno matriko danega grafa. Spodnji delˇcek kode 3.5 nam naredi ravno to.
1 // S t e v i l o v o z l i s c
2 var Vno = G r a p h . n o d e s . l e n g t h ;
3 // I n i c i a l i z i r a m o s o s e d n o s t n o m a t r i k o tako , da v v s a k i c e l i c i v s e b u j e v r e d n o s t n e s k o n c n o
4 var a d j M a t r i x = new A r r a y ( Vno ) ;
5 for (var i = 0; i < Vno ; i ++) {
6 a d j M a t r i x [ i ] = new A r r a y ( Vno ) ; 7 }
8 for (var i = 0; i < Vno ; i ++) {
9 for (var j = 0; j < Vno ; j ++) {
10 a d j M a t r i x [ i ][ j ] = I n f i n i t y ;
11 }
12 } 13
14 // Tu p r e s l i k a m o g r a f o v s k o s t r u k t u r o v s o s e d n o s t n o m a t r i k o
15 for (var i = 0; i < G r a p h . n o d e s . l e n g t h ; i ++) { // S p r e h o d i m o se cez vsa v o z l i s c a 16 var n o d e = G r a p h . n o d e s [ i ]. c o n s t r u c t . v e r t e x . c o n t e n t ;
17 for (var ne = 0; ne < G r a p h . n o d e s [ i ]. c o n s t r u c t . n e i g h b o u r s . l e n g t h ; ne ++) { //
S p r e h o d i m o se cez vse s o s e d e t e g a v o z l i s c a
18 var n e i g h b o u r = G r a p h . n o d e s [ i ]. c o n s t r u c t . n e i g h b o u r s [ ne ]. v e r t e x . c o n t e n t ; 19 for (var j = 0; j < G r a p h . n o d e s . l e n g t h ; j ++) { // S p r e h o d i m o se cez vsa
v o z l i s c a , da p o i s c e m o n j e g o v i n d e k s v n a s i g r a f o v s k i s t r u k t u r i 20 var n e w N o d e = G r a p h . n o d e s [ j ]. c o n s t r u c t . v e r t e x . c o n t e n t ;
21 if ( n e w N o d e == n e i g h b o u r ) {
22 // Ker je g r a f n e u s m e r j e n , bo m a t r i k a s o s e d n o s t i s i m e t r i c n a
23 a d j M a t r i x [ i ][ j ] = 1;
24 a d j M a t r i x [ j ][ i ] = 1;
25 b r e a k;
26 }
27 }
28 }
29 }
Delˇcek kode 3.5: Preoblikovanje strukture grafa v sosednostno matriko.
Sedaj, ko imamo sosednostno matriko, jo lahko brez teˇzav podajamo Dijkstrovemu algoritmu.
Za prikaz najdaljˇse razdalje uporabniku potrebujemo tudi objekt, v katerega bomo shranjevali do sedaj najdeno najdaljˇso pot. V delˇcku kode 3.6 ustvarimo tak objekt in se nato sprehodimo ˇ
cez vsa vozliˇsˇca grafa, iz katerih potem s pomoˇcjo Dijkstrovega algoritma poiˇsˇcemo najkrajˇse poti do vseh ostalih vozliˇsˇc grafa.
Ko dobimo najkrajˇse poti, se sprehodimo ˇcez tabelo teh poti in poiˇsˇcemo najdaljˇso, ter si zapomnimo, kje se pot zaˇcne in konˇca, kolikˇsna je njena dolˇzina in kateri so vmesni ˇcleni poti.
Vse te informacije bomo na koncu podali uporabniku.
1 // Objekt , ki bo v s e b o v a l p o d a t k e o n a j d a l j s i n a j k r a j s i p o t i 2 var l o n g e s t S h o r t e s t P a t h = {
3 l e n g t h : 0 ,
4 s t a r t : 0 ,
5 end : 0 ,
6 p a t h s : n u l l 7 };
8 // S p r e h o d i m o se cez v o z l i s c a g r a f a
9 for (var i = 0; i < G r a p h . n o d e s . l e n g t h ; i ++) {
10 // U p o r a b i m o D i j s k t r o v a l g o r i t e m , za i s k a n j e n a j k r a j s i h p o t i do o s t a l i h v o z l i s c v g r a f u
11 var s h o r t e s t P a t h s = s h o r t e s t P a t h ( a d j M a t r i x , G r a p h . n o d e s . length , i ) ; 12 // S p r e h o d i m o se cez vse n a j k r a j s t e p o t i in i s c e m o n a j d a l j s o
13 for (var j = 0; j < s h o r t e s t P a t h s . p a t h L e n g t h s . l e n g t h ; j ++) {
14 if ( s h o r t e s t P a t h s . p a t h L e n g t h s [ j ] > l o n g e s t S h o r t e s t P a t h . l e n g t h ) {
15 // S h r a n i m o si vse podatke , da b o m o l a h k o pot k a s n e j e r e k o n s t r u i r a l i 16 l o n g e s t S h o r t e s t P a t h . l e n g t h = s h o r t e s t P a t h s . p a t h L e n g t h s [ j ];
17 l o n g e s t S h o r t e s t P a t h . s t a r t = s h o r t e s t P a t h s . s t a r t V e r t e x ; 18 l o n g e s t S h o r t e s t P a t h . end = j ;
