Univerza v Ljubljani
Fakulteta za raˇ cunalniˇ stvo in informatiko
Sergej Munda
Spletna aplikacija za samodejno izdelavo sedeˇ znih redov
DIPLOMSKO DELO
UNIVERZITETNI ˇSTUDIJSKI PROGRAM PRVE STOPNJE
RA ˇCUNALNIˇSTVO IN INFORMATIKA
Mentor : doc. dr. Jurij Miheliˇ c Somentor : izr. prof. dr. Miha Moˇskon
Ljubljana, 2021
koriˇsˇcenje rezultatov diplomske naloge je potrebno pisno privoljenje avtorja, Fakultete za raˇcunalniˇstvo in informatiko ter mentorja.
Besedilo je oblikovano z urejevalnikom besedil LATEX.
Fakulteta za raˇcunalniˇstvo in informatiko izdaja naslednjo nalogo:
Spletna aplikacija za samodejno izdelavo sedeˇznih redov Tematika naloge:
Kandidat naj se v delu osredotoˇci na problem izdelave sedeˇznega reda, kjer gre za razmestitev udeleˇzencev na sedeˇzna mesta. Problem naj natanˇcno opredeli in raziˇsˇce teˇzkost njegovega reˇsevanja. Pregleda naj obstojeˇce sple- tne aplikacije za reˇsevanje problema razmestitve v praktiˇcni uporabi pri razmeˇsˇcanju udeleˇzencev glede na vnaprej definirana sedeˇzna mesta in ome- jitve. Kandidat naj predlaga in razvije lastno spletno aplikacijo, ki bo od- pravljala omejitve obstojeˇcih reˇsitev in ki bo temeljila na reˇsevanju problema razmestitve z reˇsevanjem problema podgrafnega izomorfizma.
Zahvaljujem se mentorju doc. dr. Juriju Miheliˇcu in somentorju izr. prof.
dr. Mihu Moˇskonu za vse nasvete in napotke pri izdelavi diplomskega dela.
Prav tako se zahvaljujem svoji druˇzini, punci, prijateljem in vsem drugim, ki so me podpirali v ˇcasu ˇstudija.
Kazalo
Povzetek Abstract
1 Uvod 1
2 Problem razmestitve 3
2.1 Opis problema . . . 3
2.2 Definicija problema . . . 4
2.3 Teˇzkost problema . . . 5
2.4 Problem podgrafnega izomorfizma . . . 6
2.5 Reˇsevanje problema razmestitve . . . 7
2.6 Reˇsevanje podgrafnega izomorfizma . . . 9
3 Analiza obstojeˇcih reˇsitev 11 3.1 Aplikacija Mega Seating Plan . . . 12
3.2 Aplikacija ClickSchool Seating Planner . . . 15
3.3 Povzetek analize obstojeˇcih reˇsitev . . . 20
4 Razvoj spletne aplikacije 21 4.1 Podatkovni model in funkcionalnosti . . . 21
4.2 Uporabljene tehnologije . . . 27
4.3 Arhitektura spletne aplikacije . . . 30
5 Predstavitev spletne aplikacije 43
Literatura 51
Seznam uporabljenih kratic
Kratica Angleˇsko Slovensko
E-R Entity–relationship Entitetno-odnosni
JSON JavaScript Object Notation Objektna notacija za Java- Script
URL Uniform Resource Locator Enoliˇcni krajevnik vira
JWT JSON Web Token Spletni ˇzeton JSON
SPA Single-page Application Aplikacija na eni strani
DB Database Podatkovna baza
SQL Structured Query Language Strukturirani povpraˇsevalni je- zik
API Application programming in- terface
Vmesnik uporabniˇskega pro- grama
REST Representational state transfer Prenos predstavitvenega sta- nja
HTTP Hypertext Transfer Protocol Protokol za prenos hiperteksta YAML Yet Another Markup Langu-
age
ˇSe en oznaˇcevalni jezik
Povzetek
Naslov: Spletna aplikacija za samodejno izdelavo sedeˇznih redov Avtor: Sergej Munda
Pri posedanju uˇcencev v ˇsolske klopi, organizaciji tekmovanj iz znanja, or- ganizaciji poroke in pri drugih podobnih dogodkih se sreˇcamo s problemom razmestitve. Gre za enega od tistih problemov, ki so na zaˇcetku videti tri- vialni, saj so pravila posedanja po navadi preprosta in razumljiva. Zaradi tega se organizatorji zgoraj navedenih dogodkov velikokrat odloˇcijo za iz- delavo sedeˇznega reda na roke, kar hitro postane eno najbolj zamudnih del organizatorja. V okviru diplomske naloge je bil problem razmestitve na- tanˇcno opredeljen, dokazano je bilo, da je problem NP-poln in izdelana je bila spletna aplikacija za samodejno izdelavo sedeˇznih redov. Poleg samo- dejne izdelave sedeˇznega reda aplikacija ponuja tudi uporabniˇske vmesnike za vnos podatkov o osebah, izdelavo topologije sedeˇznih mest in prikaz konˇcne razmestitve.
Kljuˇcne besede: spletna aplikacija, problem razmestitve, sedeˇzni red, pod- grafni izomorfizem.
Abstract
Title: Web application for automated creation of seating plans Author: Sergej Munda
We encounter the arrangement problem while making classroom seating plans, organizing knowledge competitions, organizing weddings and other similar events. This is one of those problems that seem trivial at first, because the rules of creating a seating plan are usually simple and understandable.
As a result, the organizers of the above-mentioned events often decide to cre- ate a seating plan by hand, which becomes one of the most time-consuming tasks of the organizers. In this thesis, we defined the arrangement problem and proved it to be NP-complete. Furthermore, we created a web application that allows its users an automatic creation of seating plans. In addition to the automatic creation of seating plans, the application also includes user inter- faces for entering the data of the seated persons, for creating seat topologies and for displaying the final seating plan.
Keywords: web application, arrangement problem, seating plan, subgraph isomorphism.
Poglavje 1 Uvod
Uˇcitelji, profesorji in predavatelji pogosto naletijo na problem razmestitve svojih uˇcencev, dijakov ali ˇstudentov na sedeˇzna mesta bodisi za namen oce- njevanja znanja ali zgolj zaradi miru v uˇcilnici med poukom. Z enakim pro- blem se redno sreˇcujejo organizatorji veˇcjih dogodkov, kot so tekmovanja iz znanja ali poroke. Na takih dogodkih je pogosto veliko oseb, med katerimi ve- ljajo omejitve glede sedenja, zato postane takˇsno razmeˇsˇcanje zelo zahtevno.
V tej diplomski nalogi se bomo osredotoˇcili na samodejno izdelavo sedeˇznih mest z omejitvami sedenja, kar bomo poimenovali problem razmestitve.
V drugem poglavju bomo problem razmestitve formalno definirali, doka- zali, da je problem NP-poln in predstavili reˇsitev problema.
Tretje poglavje bo zajemalo analizo obstojeˇcih reˇsitev. Predstavili bomo spletne aplikacije za izdelavo sedeˇznih redov, ki trenutno ˇze obstajajo.
V ˇcetrtem poglavju bomo navedli in opisali funkcionalne zahteve, ki jih bo naˇsa spletna aplikacija implementirala. Na kratko bomo predstavili upo- rabljene tehnologije in arhitekturo izdelane aplikacije.
V petem poglavju bomo predstavili delovanje spletne aplikacije. Izvedli bomo celoten postopek izdelave sedeˇznega reda. Najprej bomo vnesli podatke o osebah in sedeˇznih mestih, nato pa bomo izvedli samodejno razmestitev oseb na sedeˇzna mesta.
V zakljuˇcku bomo podali sklepne ugotovitve ter predstavili moˇznosti za 1
izboljˇsave in nadaljnji razvoj.
Poglavje 2
Problem razmestitve
To poglavje je namenjeno predstavitvi problema razmestitve. Problem bomo najprej opisali, nato pa ga formalno definirali. Ko bo problem definiran, bomo dokazali, da spada v razred NP-polnih problemov. Za tem bomo opisali znan problem podgrafnega izomorfizma in pokazali, kako lahko problem raz- mestitve prevedemo na problem podgrafnega izomorfizma. Na koncu bomo predstavili, na kakˇsen naˇcin bomo reˇsevali problem podgrafnega izomorfizma.
2.1 Opis problema
V tej diplomski nalogi reˇsujemo problem izdelave sedeˇznega reda z doloˇcenimi omejitvami, kar v nadaljevanju poimenujemo problem razmestitve. Naˇs cilj je, da poljubno ˇstevilo oseb razmestimo na poljubno ˇstevilo sedeˇznih mest.
Pri tem za vsako osebo poznamo nabor omejitev, ki nam pove, kdo zraven te osebe ne sme sedeti, za vsako sedeˇzno mesto pa poznamo sosednja sedeˇzna mesta.
Osebe in sedeˇzna mesta predstavljajo vhodne podatke naˇsega problema.
Izhodni podatek predstavlja odgovor na vpraˇsanje: ”Ali obstaja takˇsna raz- mestitev oseb po sedeˇznih mestih, ki bo upoˇstevala vse omejitve med ose- bami?”. V primeru, da je odgovor pritrdilen, nas zanima tudi, kako takˇsna razmestitev izgleda.
3
2.2 Definicija problema
Problem razmestitve lahko formalno definiramo z mnoˇzicama oseb P in sedeˇzev S ter s preslikavami, ki jih izvajamo nad elementi teh mnoˇzic. V nadaljevanju bomo definirali posamezne mnoˇzice in preslikave:
1. Mnoˇzica P vsebuje n oseb, oznaˇcenih z indeksi od 1 do n. Velikost mnoˇzice P oznaˇcimo s |P| in velja, da je n =|P|.
2. Mnoˇzica S vsebujem sedeˇzev, oznaˇcenih z indeksi od 1 dom. Velikost mnoˇzice S oznaˇcimo s |S|in velja, da je m=|S|.
3. Preslikava α :P →2P vsaki osebi p iz mnoˇzice P priredi podmnoˇzico oseb iz potenˇcne mnoˇzice 2P. Podmnoˇzica predstavlja vse osebe, ki z osebop niso kompatibilne oziroma ne smejo sedeti skupaj z osebo p.
4. Preslikava β : S → 2S vsakemu sedeˇznemu mestu s iz mnoˇzice S pri- redi podmnoˇzico sedeˇznih mest iz potenˇcne mnoˇzice 2S. Podmnoˇzica predstavlja vsa sedeˇzna mesta, ki so sosednja mestu s.
Za velikosti |P| in |S| predpostavimo, da velja |P| ≤ |S|, torej ˇstevilo oseb je manjˇse ali enako kot ˇstevilo sedeˇznih mest. Prav tako predposta- vimo, da omejitve med osebami veljajo v obe smeri oziroma so simetriˇcne.
Torej, ˇce reˇcemo, da oseba pi ne sme sedeti zraven osebe pj, velja tudi, da oseba pj ne sme sedeti zraven osebe pi. To lahko tudi formalno zapiˇsemo:
pi ∈ α(pj) ⇔ pj ∈ α(pi). Zgoraj navedeno simetriˇcnost bomo upoˇstevali v nadaljnjih izrazih in enaˇcbah. Enako velja za sosednosti med sedeˇznimi mesti in za preslikavo β, torej si ∈β(sj)⇔sj ∈β(si).
Reˇsitev problema predstavlja mnoˇzica R, ki vsebuje |P| elementov r = (s, p), kjer nam vsak element r pove, da na sedeˇznem mestu s sedi oseba p.
Reˇsitev R je veljavna, ˇce za vse pare elementov ri = (si, pi) in rj = (sj, pj) velja:
pi ∈α(pj)⇒si ∈/ β(sj). (2.1)
Diplomska naloga 5 Torej, ˇce osebipi inpj nista kompatibilni, moratapiinpj sedeti na sedeˇzih si insj, ki nista sosednja.
2.3 Teˇ zkost problema
Predpostavimo, da je problem razmestitve NP-poln. ˇCe ˇzelimo dokazati NP- polnost problema, moramo pokazati, da problem pripada razredu NP in da nanj lahko prevedemo poljuben NP-poln problem.
2.3.1 Pripadnost razredu NP
Pripadnost problema razredu NP pokaˇzemo s certifikatom reˇsitve, ki bo v naˇsem primeru mnoˇzicaR. Velja, da problem pripada razredu NP, ˇce lahko v polinomskem ˇcasu preverimo, ali je poljubna mnoˇzicaRtudi veljavna reˇsitev problema. Mnoˇzica R je veljavna, ˇce za vse pare elementov mnoˇzice R ve- lja izraz 2.1. Casovna zahtevnost preverjanja veljavnosti jeˇ O(|R|·(|R|−1)
2 ),
oziroma O(|R|2), kar predstavlja polinomski ˇcas.
2.3.2 Prevedba
Za prevedbo bomo najprej opisali odloˇcitveni problem razmestitve. Pri odloˇcitvenem problemu razmestitve nas zanima, ali za podani mnoˇzici P inS ter preslikavi αin β obstaja razmestitev R, ki ustreza pogojem 2.1. Na odloˇcitveni problem razmestitve bomo v polinomskem ˇcasu prevedli odloˇci- tveni problem neodvisne mnoˇzice, ki spada med NP-polne probleme [11].
Problem neodvisne mnoˇzice odgovarja na vpraˇsanje: “Ali v grafu G = (V, E) obstaja mnoˇzica vozliˇsˇcC ⊆V velikosti|C| ≥k, za katero velja, da so vsa vozliˇsˇca paroma nepovezana?”. Primerek problema neodvisne mnoˇzice pretvorimo v primerek problema razmestitve. Iz grafa G= (V, E) izdelamo mnoˇzico S = V in preslikavo β(u) = {v ∈ V|(u, v) ∈ E}. Nato izdelamo mnoˇzicoP velikosti|P|=k in preslikavoα, pri kateri za vsak element p∈P velja α(p) = P \ {p}. Reˇsitev takega problema bo mnoˇzica R elementov
r= (s, p), iz katere pridobimo reˇsitev problema neodvisne mnoˇziceC ={s∈ S|(s, p)∈R}.
Sedaj dokaˇzemo ekvivalenco reˇsitev obeh problemov. Naj boC neodvisna mnoˇzica velikosti|C| ≥kv grafuG= (V, E). Po definiciji za vse pare vozliˇsˇc u, v ∈C velja (u, v)∈/ E, zaradi definicije preslikaveβ v prejˇsnjem odstavku to pomeni, da velja tudi u /∈ β(v) (upoˇstevamo simetriˇcnost). Iz definicije preslikaveαv prejˇsnjem odstavku je razvidno, da za vsak parpi, pj ∈P, kjer je i 6= j, velja pi ∈ α(pj) (upoˇstevamo simetriˇcnost). Zato za vse elemente (s, p) ∈ R, kjer s ∈ S in p ∈ P velja izraz 2.1, reˇsitev izdelana iz C je tudi reˇsitev problema razmestitve.
Dokaˇzemo ˇse ekvivalenco v obratno smer. Naj bo R reˇsitev problema razmestitve, na katerega smo prevedli problem neodvisne mnoˇzice. Za vse elemente (s, p) ∈ R velja izraz 2.1. Ker je |R| = |P| ≥ k in ker za vse pare elementov pi, pj ∈ P, kjer je i 6= j, velja pi ∈ α(pj) (upoˇstevamo simetriˇcnost), saj smo tako zgoraj definirali preslikavo α, mora tudi za vse pare elementovsi, sj ∈S, ki so del reˇsitve R, veljati si ∈/ β(sj) (upoˇstevamo simetriˇcnost). Zaradi zgornje definicije preslikaveβ vemo, da to v kontekstu teorije grafov za elementasi insj pomeni (si, sj)∈/ E. Zato lahko trdimo, da je reˇsitevC ={s∈S|(s, p)∈R}tudi neodvisna mnoˇzica velikosti |C| ≥k v grafuG= (V, E).
Dokazali smo, da problem razmestitve spada v razred NP in da nanj lahko prevedemo poljuben NP-poln problem, zato lahko trdimo, da je NP-poln.
2.4 Problem podgrafnega izomorfizma
V tem poglavju bomo predstavili problem podgrafnega izomorfizma, saj bomo v nadaljevanju prikazali, kako lahko problem razmestitve pretvorimo v problem podgrafnega izomorfizma. Definicije iz teorije grafov v nadaljnjih podpoglavjih so povzete po definicijah iz knjige [27].
Za definicijo podgrafnega izomorfizma moramo najprej definirati pojma podgraf in grafni izomorfizem.
Diplomska naloga 7 Graf G0 = (VG0, EG0) je podgraf grafa G= (VG, EG), ˇce velja
VG0 ⊆VG∧EG0 ⊆EG. (2.2) Grafni izomorfizem je bijektivna preslikava vozliˇsˇc θ : VH → VG med poljubnima grafomaH = (VH, EH) in G= (VG, EG), za katero velja
{u, v} ∈EH ⇔ {θ(u), θ(v)} ∈EG. (2.3) Podgrafni izomorfizem delimo na navadni podgrafni izomorfizem, ki mu reˇcemo tudi grafni monomorfizem, in na induciran podgrafni izomorfizem.
Navadni podgrafni izomorfizem je injektivna preslikava vozliˇsˇc θ : VH → VG med vzorˇcnim (angl., pattern) grafom H = (VH, EH) in ciljnim (angl., target) grafomG= (VG, EG), za katero velja
{u, v} ∈EH ⇒ {θ(u), θ(v)} ∈EG. (2.4) Induciran podgrafni izomorfizem je injektivna preslikava vozliˇsˇcθ:VH → VG med vzorˇcnim (angl., pattern) grafom H = (VH, EH) in ciljnim (angl., target) grafomG= (VG, EG), za katero velja enaˇcba 2.3.
Razlika med navadnim in induciranim podgrafnim izomorfizmom je, da navadni dopuˇsˇca obstoj dodatnih povezav v ciljnem grafu, inducirani pa ne.
V okviru te diplomske naloge se bomo osredotoˇcili na navadni podgrafni izomorfizem.
Poznamo veˇc vrst problemov podgrafnega izomorfizma, mi bomo obrav- navali odloˇcitveni problem. Odloˇcitveni problem podgrafnega izomorfizma odgovarja na vpraˇsanje: “Ali med podanima grafoma G in H obstaja pod- grafni izomorfizem?”. Problem je NP-poln, kot je to dokazano v [6].
2.5 Reˇ sevanje problema razmestitve
Problem razmestitve bomo reˇsevali po metodi prevedbe na znan problem.
Prevedbo izvedemo tako, da iz mnoˇzic P in S v problemu razmestitve izde- lamo grafa H inG za problem podgrafnega izomorfizma.
Graf H bo graf oseb, kjer bodo povezane tiste osebe, med katerimi velja vsaj ena omejitev. Predpostavimo, da so vse omejitve enakovredne in da veljajo za obe osebi hkrati, to pomeni, da bo graf H neusmerjen. Mnoˇzico vozliˇsˇc VH bo predstavljala mnoˇzica oseb P, povezave EH pa bomo izdelali med vsemi pari oseb u, v ∈P, za katere velja
u∈α(v)∧v ∈α(u). (2.5)
Graf G bo graf sedeˇznih mest, kjer bodo povezana tista sedeˇzna mesta, ki niso sosednja. Mnoˇzico vozliˇsˇcVG bo predstavljala mnoˇzica sedeˇznih mest S, povezaveEG pa bomo izdelali med vsemi pari sedeˇznih mest u, v ∈ S, za katere velja
u /∈β(v)∧v /∈β(u). (2.6) Pri reˇsevanje problema podgrafnega izomorfizma nas torej zanima, ali v grafu sedeˇznih mestGobstaja tak podgraf G0, ki je izomorfen grafu oseb H.
2.5.1 Primer prevedbe
Oglejmo si primer prevedbe problema razmestitve na problem podgrafnega izomorfizma. Recimo, da ˇzelimo prevesti spodaj opisan problem razmestitve.
P ={p1, p2, p3, p4} S ={s1, s2, s3, s4, s5, s6} α(p1) = {p2, p3} β(s1) = {s2, s3} α(p2) = {p1, p3, p4} β(s2) = {s1, s4} α(p3) = {p1, p2, p4} β(s3) ={s1, s4, s5}
α(p4) = {p2, p3} β(s4) ={s2, s3, s6} β(s5) = {s3, s6} β(s6) = {s4, s5}
Najprej izdelamo graf H = (VH, EH) iz moˇzice P in preslikave α nad elementi mnoˇzice P
VH =P ={p1, p2, p3, p4}
EH ={(p1, p2),(p1, p3),(p2, p3),(p2, p4),(p3, p4)}.
Diplomska naloga 9 Nato izdelamo graf G = (VG, EG). Pozorni smo na preslikavo β, ki vsa- kemu sedeˇznemu mestu priredi mnoˇzico sosednjih sedeˇznih mest. Povezave v mnoˇzici EG ˇzelimo izdelati za sedeˇzna mesta, ki niso sosednja, zato mora za vsak par sedeˇznih mest u, v ∈EG veljati enaˇcba 2.6. Tako dobimo graf
VG=S ={s1, s2, s3, s4, s5, s6}
EG={(s1, s4),(s1, s5),(s1, s6),(s2, s3),(s2, s5),(s2, s6),(s3, s6),(s4, s5)}.
Slika 2.1 prikazuje na novo izdelana grafa H in G.
p1
p2 p3
p4
s1 s2
s3 s4
s5 s6
Slika 2.1: Grafa H in G
2.6 Reˇ sevanje podgrafnega izomorfizma
Problem podgrafnega izomorfizma bomo reˇsevali s pomoˇcjo algoritmov knji- ˇznice SICS (Subgraph Isomorphism Constraint Satisfaction), ki je dostopna na spletnem naslovu https://git.sr.ht/~xnevs/sics. Za osnovo bomo uporabili algoritem LFCBJ+, ki se je izkazal za najuspeˇsnejˇsega na veˇcini testnih scenarijev [4].
Algoritem LFCBJ+ reˇsuje problem induciranega podgrafnega izomor- fizma, zato ga bomo prilagodili tako, da bo reˇseval problem navadnega pod- grafnega izomorfizma, oziroma problem grafnega monomorfizma. Iz algo- ritma LFCBJ+ bomo odstranili preverjanje nepovezanih vozliˇsˇc. V induci- ranem podgrafnem izomorfizmu je preverjanje nepovezanih vozliˇsˇc potrebno, saj morajo povezave v vzorˇcnem grafu biti ekvivalentne povezavam med iz- branimi vozliˇsˇci v ciljnem grafu, kot je to definirano z enaˇcbo 2.3. V nava- dnem podgrafnem izomorfizmu preverjanje nepovezanih vozliˇsˇc ni potrebno,
saj je iz implikacije v enaˇcbi 2.4 razvidno, da ima lahko ciljni graf doda- tne povezave med izbranimi vozliˇsˇci. Prilagojen algoritem bomo poimenovali LFCBJ+M.
Algoritem LFCBJ+M bo implementiran s kombinacijo dveh tehnik se- stopanja: leno preverjanje vnaprej (angl., lazy forward checking, LFC) in seskakovanje (angl.,backjumping, BJ). Poleg tega bomo v algoritmu upora- bljali spodnje izboljˇsave:
vrstni red preiskovanja najmoˇcnejˇsa omejitev najprej (angl., greatest constraint first, GCF),
izpeljane omejitve o stopnjah vozliˇsˇc,
implementacija mnoˇzic z bitnimi polji.
Tehnike in izboljˇsave so podrobneje opisane v [4].
Poglavje 3
Analiza obstojeˇ cih reˇ sitev
V tem poglavju bomo pregledali obstojeˇce spletne aplikacije za izdelavo sedeˇznih redov. Ker obstaja ogromno razliˇcnih spletnih aplikacij za izdelavo sedeˇznih redov, se bomo pri iskanju reˇsitev ustrezno omejili. Ne zanimajo nas aplikacije, namenjene vizualizaciji prostorov in sedeˇznih mest, saj ne omogoˇcajo samodejne razmestitve oseb [24, 26]. Prav tako nas ne zanimajo celovite reˇsitve za spletno rezervacijo sedeˇznih mest na glasbenih ali ˇsportnih dogodkih. Takˇsne reˇsitve ponavadi ne upoˇstevajo omejitev med osebami, zraven tega pa implementirajo veliko funkcionalnosti, ki za naˇs problem raz- mestitve niso pomembne [23].
Iskanje spletnih aplikacij za izdelavo razmestitve vrne veliko podobnih rezultatov. Najpogostejˇse so aplikacije za samodejno izdelavo sedeˇznega reda uˇcencev. Pojavi se tudi nekaj aplikacij za samodejno izdelavo sedeˇznega reda oseb na poroki. Aplikacije, ki bi samodejno razmestile tekmovalce na tekmovanju iz znanja, praktiˇcno ni. V nadaljevanju bomo pregledali dve spletni aplikaciji za samodejno razmestitev uˇcencev v uˇcilnici.
Spletne aplikacije za izdelavo sedeˇznega reda uˇcencev so si zelo podobne in v veˇcini implementirajo enake funkcionalnosti: uporabniˇski vmesnik za vnos uˇcencev, uporabniˇski vmesnik za izdelavo postavitve sedeˇzev v uˇcilnici, funkcijo za samodejno razmestitev uˇcencev na sedeˇze in uporabniˇski vmesnik za prikaz razmestitve uˇcencev. Izdelava postavitve sedeˇzev in funkcija za
11
samodejno razmestitev sta v pregledanih primerih zelo omejeni.
3.1 Aplikacija Mega Seating Plan
Dober predstavnik veˇcine aplikacij za izdelavo sedeˇznega reda uˇcencev je Mega Seating Plan [15]. Uporabniˇski vmesnik za vnos uˇcencev (slika 3.1) omogoˇca enostaven vnos podatkov. Stolpci v tabeli z uˇcenci so statiˇcno definirani, zato jih uporabnik ne more dodajati ali preimenovati in s tem prilagoditi tabelo za svoje potrebe.
Slika 3.1: Uporabniˇski vmesnik za vnos uˇcencev v aplikaciji Mega Seating Plan
Na uporabniˇskem vmesniku za izdelavo postavitve sedeˇzev lahko uporab- nik vnese ime uˇcilnice in doloˇci lokacije sedeˇzev s klikanjem po sivem polju, kot je prikazano na sliki 3.2. Tak naˇcin postavljanja sedeˇzev omogoˇca izde- lavo izkljuˇcno mreˇzne (vrstice in stolpci) postavitve sedeˇznih mest. Raziskave so pokazale, da mreˇzna postavitev slabo vpliva na sodelovanje uˇcencev zaradi razliˇcne oddaljenosti od uˇcitelja in da obstajajo druge vrste postavitev (npr.:
Diplomska naloga 13 polkroˇzna), ki znatno poveˇcajo ˇstevilo postavljenih vpraˇsanj iz strani uˇcencev in s tem tudi raven sodelovanja [14]. Iz postavitve prav tako ni razvidno, na kakˇsen naˇcin je doloˇcena sosednost sedeˇznih mest.
Slika 3.2: Uporabniˇski vmesnik za izdelavo postavitve sedeˇzev v aplikaciji Mega Seating Plan
Ko vnesemo podatke o uˇcencih in izdelamo postavitev sedeˇzev, lahko zaˇzenemo samodejno razmestitev uˇcencev na sedeˇzna mesta (slika 3.3). Ob- stajajo ˇstiri strategije samodejne razmestitve. Prva strategija se imenuje
”fant-punca”, kjer so uˇcenci razmeˇsˇceni izmeniˇcno po spolu, dokler je to mogoˇce, nato pa so skupaj posedeni ˇse vsi ostali uˇcenci enakega spola. Druga strategija vsakiˇc izdela nakljuˇcno razmestitev. Tretja in ˇcetrta strategija raz- mestita uˇcence po abecedi glede na ime oziroma priimek. Obstaja ˇse ”naˇcin umikanja”, kjer lahko uporabnik oznaˇci poljubno ˇstevilo uˇcencev, za katere ne ˇzeli, da sedijo skupaj. Funkcionalnost ”naˇcin umikanja”vˇcasih sploh ne upoˇsteva pogojev, v primeru, da oznaˇcimo veˇc kot polovico uˇcencev, pa jih spet razmesti nakljuˇcno. Kompleksnejˇsih omejitev pri izdelavi razmestitve aplikacija ne upoˇsteva.
Slika 3.3: Uporabniˇski vmesnik za prikaz razmestitve v aplikaciji Mega Sea- ting Plan
Diplomska naloga 15
3.2 Aplikacija ClickSchool Seating Planner
Med pregledanimi aplikacijami izstopa ClickSchool Seating Planner [5]. Kljub preprostemu izgledu ponuja uporabniku veliko veˇc svobode pri izdelavi sede- ˇznega reda kot ostale aplikacije.
Aplikacija ima uporabniˇski vmesnik za izbiro vnaprej pripravljenih po- stavitev sedeˇzev, kot je prikazano na sliki 3.4. Izbrana postavitev sedeˇzev se uporabi kot osnovna postavitev, ki jo lahko uporabnik dodatno uredi.
Slika 3.4: Uporabniˇski vmesnik za izbiro pripravljenih postavitev sedeˇzev v aplikaciji ClickSchool Seating Planner
Uporabniˇski vmesnik za vnos uˇcencev (slika 3.5) omogoˇca vnos podatkov za poljubno ˇstevilo uˇcencev. Uporabnik lahko dodaja in preimenuje stolpce v tabeli, ki predstavljajo atribute uˇcencev in s tem prilagodi tabelo za svoje potrebe. Na tem vmesniku lahko uporabnik za posamezen stolpec doloˇci, ali ˇzeli uˇcence zdruˇzevati oziroma razsedati glede na vrednosti stolpca. To predstavlja glavno prednost te spletne aplikacije. Poleg tega je uˇcence mogoˇce razmestiti tudi nakljuˇcno in po zaˇcetnicah priimkov.
Na uporabniˇskem vmesniku za izdelavo postavitev sedeˇzev (slika 3.6) se uporabniku prikaˇze postavitev, izbrana na vmesniku na sliki 3.4, ki jo lahko uporabnik prilagodi. Prikaˇzejo se tudi razmeˇsˇceni uˇcenci iz vmesnika na sliki 3.5. Sedeˇzi so postavljeni v mreˇznem sistemu, uporabnik jih lahko poljubno premika po poljih mreˇze, jih odstranjuje in dodaja nove sedeˇze na polja, ki so trenutno prazna. S stranskimi gumbi je mogoˇce mreˇzo razˇsiriti po stolpcih in vrsticah.
Aplikacija implementira ˇse dva uporabniˇska vmesnika za prikaz razmesti- tve. Vmesnik na sliki 3.8 prikazuje uˇcence zdruˇzene po mizah, vmesnik na sliki 3.7 pa prikazuje razmestitev v obliki tabele.
Ceprav je aplikacija ClickSchool funkcionalno zelo dodelana, ima vseenoˇ nekaj teˇzav. Razsedanje oziroma grupiranje uˇcencev glede na njihove atri- bute (slika 3.5) lahko uporabnik izvaja samo za en stolpec namesto po veˇc stolpcih hkrati. Poleg tega se izkaˇze, da je algoritem za razmeˇsˇcanje poˇzreˇsen, saj upoˇsteva pogoj za razsedanje oziroma grupiranje, dokler je to mogoˇce, preostala prosta mesta pa zapolni nakljuˇcno. Teˇzava se pojavi tudi pri de- finiciji sosednosti sedeˇznih mest. Sedeˇzna mesta so predstavljena v mreˇzni obliki, zato aplikacija privzame, da sta dve sedeˇzni mesti sosednji, ˇce leˇzita v sosednjih poljih na mreˇzi. Poleg tega privzame tudi, da sosednost po- meni sedenje za isto mizo (slika 3.8). Zgoraj navedene teˇzave zelo omejujejo uporabnika pri izdelavi poljubnega sedeˇznega reda.
Diplomska naloga 17
Slika 3.5: Uporabniˇski vmesnik za vnos uˇcencev v aplikaciji ClickSchool Se- ating Planner
Slika 3.6: Uporabniˇski vmesnik za izdelavo postavitve sedeˇzev v aplikaciji ClickSchool Seating Planner
Slika 3.7: Uporabniˇski vmesnik za prikaz razmestitve uˇcencev v obliki tabele v aplikaciji ClickSchool Seating Planner
Diplomska naloga 19
Slika 3.8: Uporabniˇski vmesnik za prikaz razmestitve uˇcencev po mizah v aplikaciji ClickSchool Seating Planner
3.3 Povzetek analize obstojeˇ cih reˇ sitev
Najpogostejˇse teˇzave v obstojeˇcih reˇsitvah problema razmestitve, ki smo jih analizirali v tem poglavju, so:
atributi, s katerimi opiˇsemo uˇcenca, so veˇcinoma doloˇceni vnaprej, upo- rabnik jih ne more prilagoditi za svoje potrebe,
sedeˇzi so v uˇcilnico postavljeni v obliki mreˇze, kar je velika omejitev pri doloˇcanju sosednosti med sedeˇzi,
za avtomatsko razmeˇsˇcanje uˇcencev na sedeˇze sta veˇcinoma na voljo le nakljuˇcna razmestitev in razmestitev po imenu ali priimku. Aplikacija, ki bi omogoˇcala razmestitev uˇcencev glede na veˇc atributov hkrati, ne obstaja.
Naslednje poglavje je namenjeno predstavitvi in opisu spletne aplikacije, ki reˇsuje zgoraj navedene teˇzave.
Poglavje 4
Razvoj spletne aplikacije
V tem poglavju bomo predstavili razvoj spletne aplikacije za problem razme- stitve. Najprej bomo opisali podatkovni model in funkcionalnosti aplikacije, nato bomo na kratko predstavili uporabljene tehnologije za izdelavo aplika- cije. Poglavje bomo zakljuˇcili z opisom arhitekture spletne aplikacije.
Konceptualno bo spletna aplikacija predstavljala prevajalnik, ki bo po- datke problema razmestitve, ki jih vnese uporabnik, prevedla v obliko podat- kov problema podgrafnega izomorfizma in jih predala algoritmu, ki je opisan v poglavju 2.6. Ko bo algoritem konˇcal z izvajanjem, bo aplikacija prevzela njegove rezultate in jih pretvorila nazaj v obliko, ki bo primerna za prikaz uporabniku.
4.1 Podatkovni model in funkcionalnosti
Podatkovni model bomo predstavili z E-R diagramom. Uporabili bomo logiˇcni model, saj je bolj podroben od konceptualnega modela. Prav tako nas v tem trenutku ne zanima, na kakˇsen naˇcin bo podatkovni model imple- mentiran, zato ne bomo uporabili fiziˇcnega modela.
Kot je prikazano na sliki 4.1, bo model vseboval entitete: users, se- ating plans, persons, attributes, person attributes, seats, seat links in per- son on seats, ki so spodaj podrobneje opisane.
21
Slika 4.1: Logiˇcna shema podatkovnega modela
Entiteta users bo vsebovala podatke o uporabniˇskih raˇcunih aplikacije:
id: enoliˇcni identifikator za vsak uporabniˇski raˇcun,
username: uporabniˇsko ime,
email: elektronski naslov uporabniˇskega raˇcuna,
pw hash vrednost, ki jo ustvari zgoˇsˇcevalna funkcija SHA3 256 za geslo uporabniˇskega raˇcuna [10],
created at: datum izdelave uporabniˇskega raˇcuna.
Entiteta seating plans bo vsebovala osnovne podatke o sedeˇznih redih:
seating plan id: enoliˇcni identifikator za vsak sedeˇzni red,
owned by: enoliˇcni identifikator uporabnika, ki je ustvaril sedeˇzni red,
name: ime sedeˇznega reda,
Diplomska naloga 23
created at: datum izdelave sedeˇznega reda,
finished: podatek, ki nam pove, ali je bil sedeˇzni red uspeˇsno izdelan.
Entiteta persons bo vsebovala podatke o osebah, ki jih bomo v sklopu sedeˇznega reda posedali:
person id: enoliˇcni identifikator za vsako osebo,
seating plan id: enoliˇcni identifikator sedeˇznega reda, ki mu oseba pri- pada,
name surname: ime in priimek osebe.
Entiteta attributes bo vsebovala podatke o lastnostih, na podlagi katerih bomo omejevali posedanje oseb:
attribute id: enoliˇcni identifikator za vsako lastnost,
seating plan id: enoliˇcni identifikator sedeˇznega reda,
name: ime lastnosti.
Entiteta person attributes bo vsebovala vrednost lastnosti za doloˇceno osebo:
attribute id: enoliˇcni identifikator lastnosti,
person id: enoliˇcni identifikator osebe,
value: vrednost lastnosti.
Entiteta seats bo vsebovala podatke o sedeˇzih, na katere bomo posedali osebe:
seat id: enoliˇcni identifikator za vsak sedeˇz,
seating plan id: enoliˇcni identifikator sedeˇznega reda, ki mu sedeˇz pri- pada,
local seat id: lokalni enoliˇcni identifikator sedeˇza znotraj trenutnega sedeˇznega reda.
Entiteta seat links bo vsebovala podatke o sosednostih sedeˇzev, ki bodo predstavljene kot povezave med dvema sedeˇzema:
seat link id: enoliˇcni identifikator za vsako povezavo,
seating plan id: enoliˇcni identifikator sedeˇznega reda,
from seat id: enoliˇcni identifikator sedeˇza, pri katerem se povezava zaˇcne,
to seat id: enoliˇcni identifikator sedeˇza, pri katerem se povezava konˇca.
Entiteta person on seat bo vsebovala podatke o tem, katera oseba sedi na katerem sedeˇzu:
person on seat id: enoliˇcni identifikator za vsako posedanje,
seating plan id: enoliˇcni identifikator sedeˇznega reda,
person id: enoliˇcni identifikator osebe, ki sedi na sedeˇzu v poljuseat id
seat id: enoliˇcni identifikator sedeˇza, na katerem sedi oseba iz polja person id.
Funkcionalnosti, ki jih bo spletna aplikacija implementirala, so predsta- vljene v diagramu primerov uporabe na sliki 4.2.
Uporabniki aplikacije bodo razdeljeni v dve vlogi, in sicer neprijavljeni uporabniki in prijavljeni uporabniki. Neprijavljeni uporabniki bodo lahko dostopali samo do vmesnika za prijavo, drugih pravic v aplikaciji ne bodo imeli. Prijavljeni uporabniki bodo lahko dostopali do vmesnika z navodili uporabe, do vmesnika za pregled sedeˇznih redov, do vmesnika za pregled in urejanje oseb in njihovih lastnosti, do vmesnika za pregled in urejanje sedeˇzev in povezav med sedeˇzi, do vmesnika za izdelavo sedeˇznega reda ter do vmesnika za odjavo.
Diplomska naloga 25
Slika 4.2: Primeri uporabe spletne aplikacije
Funkcionalnosti prijave in odjave bosta uporabnikom omogoˇcali avtenti- kacijo in avtorizacijo v spletni aplikaciji preko preprostih vmesnikov. Vme- snik za prijavo bo zajemal polja za vnos uporabniˇskega imena in gesla ter gumb za prijavo. Vmesnik za odjavo bo zajemal samo gumb za odjavo in bo dostopen na vseh vmesnikih, do katerih bodo dostopali prijavljeni upo- rabniki. Avtorizacija uporabnikov v spletni aplikaciji bo potekala s pomoˇcjo ˇzetonov za dostop, ki bodo oblike JSON Web Token (v nadaljevanju JWT) in bodo izdelani po protokolu OAuth 2.0, medtem ko bo avtentikacija potekala po protokolu OpenID Connect. Ker je protokol OpenID Connect defini- ran kot dodatna plast nad protokolom OAuth 2.0, nam takˇsna konfiguracija omogoˇca zdruˇzitev avtentikacijskih in avtorizacijskih podatkov v en JWT ˇzeton [12, 19, 20].
Funkcionalnost pregleda oseb in njihovih lastnosti bo predstavljala prvo od treh glavnih funkcionalnosti spletne aplikacije. Poleg pregleda podatkov o osebah in njihovih lastnostih bo razˇsirjena s tremi dodatnimi funkcional- nostmi: urejanje oseb, urejanje nabora lastnosti in urejanje lastnosti oseb.
V sklopu funkcionalnosti urejanja oseb bo uporabnik lahko dodajal, poime- noval in odstranjeval posamezne osebe, za katere bo kasneje izdelal sedeˇzni red. Funkcionalnost urejanja nabora lastnosti bo uporabnikom omogoˇcala, da poljubno doloˇcijo nabor lastnosti oseb. Funkcionalnost urejanja lastnosti oseb bo omogoˇcala, da se uporabnikom doloˇcijo vrednosti za vsako lastnost iz nabora lastnosti. Enake vrednosti lastnosti oseb bodo delovale kot omejitve sedenja pri izdelavi sedeˇznega reda.
Funkcionalnost pregleda sedeˇzev predstavlja drugo od treh glavnih funk- cionalnosti spletne aplikacije. Poleg pregleda sedeˇzev in sosednosti med njimi bo razˇsirjena z dvema dodatnima funkcionalnostma: urejanje sedeˇzev in ure- janje sosednosti med dvema sedeˇzema. Funkcionalnost urejanja sedeˇzev bo omogoˇcala dodajanje in odstranjevanje sedeˇzev, na katere bomo posedali osebe pri izdelavi sedeˇznega reda. Funkcionalnost urejanja sosednosti med dvema sedeˇzema bo uporabnikom omogoˇcala, da dva sedeˇza oznaˇcijo kot sosednja. Sosednost bo v spletni aplikaciji predstavljena kot povezava med dvema sedeˇzema.
Funkcionalnost izdelave sedeˇznega reda predstavlja zadnjo glavno funkci- onalnost spletne aplikacije. V sklopu te funkcionalnosti bo uporabnik lahko izdelal sedeˇzni red za osebe in sedeˇze glede na zgoraj opisane funkcionalnosti.
Izdelava sedeˇznega reda bo potekala po spodnjem postopku:
1. Pretvorba podatkov o osebah v graf oseb in pretvorba podatkov o sedeˇzih v graf sedeˇzev.
2. Predaja grafov o osebah in sedeˇzih zunanjemu sistemu SICS, ki nad njima izvede algoritem LFCBJ+M za iskanje podgrafnega izomorfizma in vrne rezultat.
3. Prejem rezultata zunanjega sistema SICS in pretvorba rezultata v obliko,
Diplomska naloga 27 primerno za shranjevanje in prikaz v spletni aplikaciji.
4. Prikaz pretvorjenih podatkov uporabniku.
Kot je razvidno iz zgornjega postopka, bo funkcionalnost komunicirala z zu- nanjim sistemom SICS [4]. Smisleno je omeniti, da je to edina funkcionalnost spletne aplikacije, ki komunicira z zunanjimi sistemi.
4.2 Uporabljene tehnologije
V tem poglavju so navedeni kratki opisi tehnologij, ki predstavljajo temelje spletne aplikacije za problem razmestitve.
4.2.1 Angular
Angular je odprtokodna platforma za razvoj spletnih aplikacij. Platforma je bila v zaˇcetku namenjena predvsem razvoju spletih aplikacij na eni strani, vendar se je s pomoˇcjo tehnologije (angl., Angular Universal) uspeˇsno prila- godila tudi razvoju modernih spletnih aplikacij, ki prehajajo nazaj na upo- dabljanje (angl., rendering) na streˇzniku. Angular omogoˇca hiter razvoj spletnih aplikacij predvsem zaradi velikega nabora knjiˇznic, ki med drugim pokrivajo usmerjanje zahtevkov, komunikacijo z zalednimi sistemi, pripravo vnosnih obrazcev in avtorizacijo [2, 3].
Osnovni gradniki platforme se imenujejo komponente. Glavna ideja kom- ponent je, da jih razvijalec definira samo enkrat, nato pa jih lahko v spletni aplikaciji veˇckrat uporabi. Logika v komponentah je napisana v jeziku Type- Script, medtem ko je izgled komponente doloˇcen s HTML in CSS. Namesto CSS lahko razvijalec uporabi kakˇsen drug jezik, npr. SASS, ki ga Angular prevede v CSS [25].
Angular je razvilo podjetje Google.
4.2.2 Nginx
Nginx zdruˇzuje veliko razliˇcnih plaˇcljivih in odprtokodnih tehnologij. Za po- trebe razvoja naˇse spletne aplikacije bomo uporabili odprtokodni posredniˇski streˇznik (angl., proxy server), imenovan NGINX Open Source, ki zraven iz- delave skupne vhode toˇcke za celotno aplikacijo omogoˇca tudi uravnoteˇzenje obremenitve med zalednimi streˇzniki (angl., load balancing) in serviranje statiˇcnih podakov iz predpomnilnika [18].
4.2.3 Rust
Rust je eden mlajˇsih programskih jezikov. Prva verzija je bila objavljena leta 2010. Njegova hitrost je primerljiva s C in C++, torej gre za enega hitrejˇsih jezikov. Velike hitrosti izvajanja dosega iz dveh glavnih razlogov. Prviˇc, za izvajanje ne uporablja navideznega stroja, vsa koda se prevede v binarne da- toteke sistema. Drugiˇc, med izvajanjem ne uporablja sproˇsˇcanja pomnilnika (angl., garbage collector). Od drugih programskih jezikov se razlikuje tudi po tem, da nima tipa null, da so vse spremenljivke privzeto konstantne, ter da lahko en objekt v pomnilniku referencira samo ena spremenljivka. Zadnja omejitev omogoˇca zelo varno veˇcnitno programiranje [22].
Zaradi hitrega ˇcasa izvajanja in podobne semantike jeziku C++, je Rust obiˇcajno opredeljen kot sistemski programski jezik. To pa ne pomeni, da ni primeren za razvoj ostalih programskih reˇsitev. V Rustu lahko izdelamo CLI aplikacije, lahko ga prevedemo v WebAssembly kodo in z njo poganjamo hitre spletne aplikacije, ali pa z njim izdelamo REST streˇznik, kot bomo to naredili v sklopu naˇse diplomske naloge.
4.2.4 Actix Web
Actix Web je ogrodje za izdelavo spletnih storitev v programskem jeziku Rust. Ogrodje ima modularno arhitekturo, kar pomeni, da obstaja osnovna (angl.,core) knjiˇznjica za sprejemanje HTTP in HTTPS povezav, ki jo lahko s pomoˇcjo modulov razˇsirjamo in prilagajamo. V kontekstu jezika Rust mo-
Diplomska naloga 29 dule imenujemo zaboji (angl., crates). Obstaja veliko razliˇcnih modulov. V naˇsi diplomski nalogi bomo uporabili modul za povezavo s podatkovno bazo PostgreSQL, modul za nastavljanje atributov CORS v glavi HTTP, modul za serializacijo in deserializacijo podatkov ter kriptografska modula za ge- neriranje zgoˇsˇcenih vrednosti SHA3-256 uporabniˇskih gesel in za izdelavo avtentikacijskih ˇzetonov JWT [1].
4.2.5 PostgreSQL
PostgreSQL je ena najbolj znanih odprtokodnih objektno-relacijskih podat- kovnih baz. Od drugih relacijskih podatkovnih baz se razlikuje po moˇznosti izdelave lastnih podatkovnih tipov, ki se lahko uporabljajo pri definiciji stolp- cev v tabelah. Privzeto podpira tudi bolj kompleksne znane podatkovne tipe, kot sta JSON in XML [21].
V sklopu naˇse diplomske naloge bomo na podatkovni bazi PostgreSQL definirali in uporabljali podatkovni model, ki je opisan v poglavju 4.1.
4.3 Arhitektura spletne aplikacije
Arhitektura spletne aplikacije sledi modernim principom razvoja spletnih reˇsitev. Namesto ene monolitne aplikacije na enem streˇzniku bomo izde- lali veˇc mikrostoritev, ki bodo lahko porazdeljene po veˇc streˇznikih. Vsaka mikrostoritev bo opravljala natanˇcno doloˇceno nalogo v aplikaciji. Takˇsna arhitektura ima doloˇcene prednosti in slabosti v primerjavi z monolitno ar- hitekturo.
V tem poglavju bomo najprej predstavili mikrostoritveno arhitekturo, nato si bomo ogledali orodje Docker, ki nam omogoˇca hitro izdelavo in upo- rabo posameznih storitev. Za konec bomo predstavili naloge in obseg posa- mezne mikrostoritve v aplikaciji. Tekom poglavja se bomo sklicevali na sliko 4.3, ki predstavlja pregled celotne arhitekture spletne aplikacije.
Slika 4.3: Arhitektura spletne aplikacije
Diplomska naloga 31
4.3.1 Lastnosti mikrostoritvene arhitekture
Ideja mikrostoritvene arhitekture je razdelitev kompleksne aplikacije na manj- ˇse dele, ki opravljajo toˇcno doloˇceno nalogo. Te dele imenujemo mikrostori- tve. Spodaj so opisane glavne lastnosti mikrostoritvene arhitekture [13, 16].
Organiziranost
Vsaka mikrostoritev ima toˇcno doloˇceno nalogo in namen, zato jo je laˇzje organizirati, saj znotraj ene mikrostoritve ni potrebno upoˇstevati delovanja ostalih mikrostoritev. Organiziranost takˇsne arhitekture je poslediˇcno boljˇsa, kot organiziranost monolitne arhitekture.
ˇSibka sklopljenost
Ker je notranje delovanje posamezne mikrostoritve skrito ostalim mikrosto- ritvam, med sabo pa komunicirajo preko izpostavljenih javnih API vmesni- kov, je sklopljenost med mikrostoritvami ˇsibka (angl., loose coupling). To pomeni, da sprememba v notranjem delovanju ene mikrostoritve ne bo pov- zroˇcila teˇzav pri delovanju druge mikrostoritve, kot je to pogosto pri veˇcjih monolitnih aplikacijah.
Skalabilnost
Poznamo dve vrsti skalabilnosti: horizontalno in vertikalno. Horizontalna skalabilnost predstavlja zmoˇznost dodajanja instanc aplikacije in razvrˇsˇcanje prometa med njimi. Vertikalna skalabilnost predstavlja zmoˇznost poveˇcanja procesne moˇci ene konkretne instance aplikacije, tako da lahko prejme in ob- dela veˇc prometa v krajˇsem ˇcasu. Monolitne aplikacije imajo veliko teˇzav s horizontalno skalabilnostjo, saj so kompleksne in velike ter potrebujejo spe- cifiˇcno prilagojeno okolje izvajanja, zato se obiˇcajno skalirajo vertikalno, kar pa je lahko drago. Mikrostoritve so narejene za horizontalno skaliranje, saj lahko poveˇcamo ˇstevilo instanc samo za tisto storitev, ki ima veˇcjo obreme- nitev, drugih pa ne spreminjamo. Iz tega razloga so se razvila tudi orodja za dinamiˇcno skaliranje mikrostoritev, ki samodejno poveˇcujejo in zmanjˇsujejo
ˇstevilo instanc, glede na trenutno obremenjenost.
Odpornost na izpade
V povezavi s prejˇsnjo lastnostjo, nam veˇc instanc na fiziˇcno loˇcenih streˇznikih poveˇca odpornost na izpade, ko pride do teˇzav v enem okolju izvajanja mi- krostoritve.
Vzporedni razvoj
Ker so mikrostoritve med sabo neodvisne, jih lahko razliˇcne ekipe razvijajo vzporedno, kar pospeˇsi hitrost razvoja celotne aplikacije.
Neodvisnost tehnologij
Dokler je komunikacija med mikrostoritvami ustrezno doloˇcena, so lahko razliˇcne mikrostoritve izdelane s pomoˇcjo razliˇcnih tehnologij, glede na ˇzelje in zahteve njihovih razvijalcev.
Neodvisnost postavitev
Postavitev doloˇcene mikrostoritve na produkcijsko okolje je neodvisna od ostalih delov aplikacije, za razliko od monolitne aplikacije, kjer je vsakiˇc po- trebna namestitev celotne aplikacije. To omogoˇca vzporedno postavitev stare in nove verzije mikrostoritve pri izvajanju posodobitev in postopen prehod na novo verzijo (angl., canary deployment), s ˇcimer doseˇzemo neprekinjeno delovanje aplikacije.
Viˇsji operativni davek
Glavna slabost mikrostoritev je viˇsji operativni davek. Pojavi se zaradi do- datnih komunikacij med mikrostoritvami in potrebe po virtualnih strojih ali posebnih vsebnikih, na katerih so mikrostoritve postavljene.
4.3.2 Okolje izvajanja
Mikrostoritve spletne aplikacije, ki jih bomo razvili, bodo postavljene v vseb- nike Docker (angl., Docker container) in se bodo izvajale v okolju Docker.
Diplomska naloga 33
Slika 4.4: Arhitektura orodja Docker
Docker je odprtokodno orodje za virtualizacijo na nivoju operacijskega sistema (angl., OS-level virtualization). V primerjavi s tradicionalno virtua- lizacijo celotnih operacijskih sistemov nam Docker omogoˇca boljˇso izrablje- nost sistemskih virov, zmanjˇsan ˇcas zagona in poenoten postopek priprave vsebnikov, ne glede na gostiteljski operacijski sistem in strojno opremo. Slika 4.4 prikazuje arhitekturo Docker. [7].
Vsebniki (angl., containers) so osnovne enote okolja Docker. Njihova naloga je, da zapakirajo program in njegove odvisnosti. Ti paketi si na operacijskem sistemu delijo vire strojne opreme, vendar lahko dostopajo samo do prostora, ki jim je bil dodeljen. S tem so med sabo navidezno loˇceni.
Vsebniki se izdelajo na podlagi naˇcrtov, ki jih imenujemo slike Docker (angl., Docker image) [9].
Slike Docker so torej naˇcrti, na podlagi katerih se izdelajo vsebniki Doc- ker. Slike so statiˇcne in shranjene bodisi na lokalnem, ali pa v spletnem repozitoriju. Vsaka slika Docker je lahko osnova za izdelavo nove slike Doc- ker. Sestavljene so iz zaporednih slojev. En sloj slike zdruˇzuje doloˇceno ˇstevilo razlik od prejˇsnjega sloja. Takˇsna zgradba omogoˇca Dockerju, da pri posodobitvah slike ni potrebno izdelati celotne slike o zaˇcetka - posodobijo se samo sloji, ki so bili spremenjeni in sloji nad njimi.
Slike Docker se izdelajo na podlagi datotek, ki jih imenujemo Dockerfile.
Gre za tekstovno datoteko, ki vsebuje nabor ukazov. Iz vsakega ukaza se izdela nov sloj slike Docker. Postopek izdelave slike sproˇzimo z ukazom docker build. V nadaljevanju bomo predstavili datoteke Dockerfile za naˇso spletno aplikacijo in jih opisali.
1 F R O M r u s t : 1 . 5 2 as b u i l d e r
2 W O R K D I R / usr / src / project - seater - api
3 C O P Y . .
4 RUN c a r g o i n s t a l l - - p a t h .
5
6 F R O M d e b i a n : buster - s l i m
7 RUN apt - get u p d a t e && apt - get i n s t a l l - y libpq - dev
8 C O P Y - - f r o m = b u i l d e r / usr / l o c a l / c a r g o / bin / project - seater - api / usr / l o c a l / bin / project - seater - api
9 C O P Y ./ s i c s _ e x e c u t a b l e / s u b G r a p h I s o / usr / l o c a l / bin / s u b G r a p h I s o
10
11 CMD [" project - seater - api "]
Koda 4.1: Dockerfile za Actix Web API in knjiˇznico SICS
Datoteka Dockerfile, prikazana v izseku kode 4.1, izdela sliko, ki vsebuje Actix Web API in knjiˇznico SICS, kot to prikazuje slika 4.3. Prvi ukazFROM doloˇca, katera slika bo uporabljena kot osnova za izdelavo nove slike. V tem primeru bo to slika rust:1.52, ki ima pripravljena vsa orodja za delo s programskim jezikom Rust. Sliko rust:1.52 poimenujemo builder. Ukaz WORKDIR v drugi vrstici nastavi delovni imenik na sliki. Ukaz COPY prenese datoteke iz trenutnega imenika na gostiteljskem sistemu v trenutni imenik na sliki. Ukaz RUN v ˇcetrti vrstici poˇzene program cargo install, ki izvede namestitev streˇznika Actix Web API. V ˇsesti vrstici se pojavi drugi FROM ukaz, kar pomeni, da se izdela nova slika. Novo sliko ustvarimo, ker slika rust:1.52 vsebuje ogromno dodatnih orodij za Rust, ki zelo poveˇcajo velikost celotne slike, za naˇs program pa niso potrebna. V drugo sliko zato v sedmi vrstici datoteke Dockerfile namestimo samo dodatne knjiˇznice, ki jih bo naˇs program potreboval in nato v osmi vrstici prenesemo nameˇsˇcen program iz prve slike v drugo sliko. V deveti vrstici na sliko prenesemo ˇse knjiˇznico
Diplomska naloga 35 SICS, do katere bo dostopal streˇznik Actix Web API. Ukaz CMD v zadnji vrstici doloˇca, kateri ukaz se bo izvedel, ko bomo pognali nov vsebnik iz zgornje slike. Ukaz, ki je doloˇcen v tej vrstici, bo pognal streˇznik Actix Web API.
1 F R O M n g i n x : 1 . 1 9
2
3 RUN m k d i r / l o g s
4
5 C O P Y n g i n x . c o n f / etc / n g i n x / n g i n x . c o n f a
Koda 4.2: Dockerfile za Nginx
Datoteka Dockerfile za izdelavo streˇznika Nginx, prikazana v izseku kode 4.2, izdela novo sliko na podlagi slike nginx:1.19. Osnovni sliki doda mapo, v kateri se bo izdelala datoteka z zapisi dostopov do aplikacije in datoteka z zapisi napak na aplikaciji. V peti vrstici se iz trenutnega imenika na gosti- teljskem sistemu v trenutni imenik na sliki prenese konfiguracijska datoteka nginx.conf, katero bomo podrobneje predstavili v poglavju 4.3.4.
Za podatkovno bazo PostgreSQL nimamo izdelane datoteke Dockerfile, saj bomo uporabili obstojeˇco sliko Docker postgres:13 iz spletnega repozi- torija Dockerhub. Sliko bomo prilagodili z dodatnimi okoljskimi spremen- ljivkami. S spremenljivkoPOSTGRES_DBbomo doloˇcili ime podatkovne baze, s spremenljivko POSTGRES_USER bomo doloˇcili uporabnika, s katerim bomo dostopali do podatkovne baze in s spremenljivko POSTGRES_PASSWORDbomo doloˇcili geslo uporabnika.
Vsebnike lahko iz zgoraj izdelanih slik Docker poˇzenemo z ukazomdocker run. Pri veˇcjem ˇstevilu vsebnikov postane takˇsen naˇcin poganjanja kom- pleksen in nepregleden. Zato bomo za izdelavo vsebnikov uporabili orodje docker-compose [8]. Orodje potrebuje konfiguracijsko datoteko, na podlagi katere lahko naenkrat izdelamo vse vsebnike naˇse aplikacije. Konfiguracijska datoteka je predstavljena v izseku kode 4.3.
1 v e r s i o n : " 3.8 "
2 s e r v i c e s :
3 p o s t g r e s - db :
4 i m a g e : " p o s t g r e s "
5 c o n t a i n e r _ n a m e : " p o s t g r e s - db "
6 p o r t s :
7 - " 5 4 3 2 : 5 4 3 2 "
8 n e t w o r k s :
9 - project - seater - net
10 v o l u m e s :
11 - p g d a t a :/ var / lib / p o s t g r e s q l / d a t a
12 e n v i r o n m e n t :
13 - P O S T G R E S _ P A S S W O R D =${ P O S T G R E S _ P A S S W O R D }
14 - P O S T G R E S _ U S E R =${ P O S T G R E S _ U S E R }
15 - P O S T G R E S _ D B =${ P O S T G R E S _ D B }
16 project - seater - api :
17 b u i l d : ./ api
18 i m a g e : " project - seater - api "
19 c o n t a i n e r _ n a m e : " project - seater - api "
20 d e p e n d s _ o n :
21 - " p o s t g r e s - db "
22 p o r t s :
23 - " 8 0 8 0 : 8 0 8 0 "
24 n e t w o r k s :
25 - project - seater - net
26 e n v i r o n m e n t :
27 - D A T A B A S E _ U R L =${ D A T A B A S E _ U R L }
28 - D O M A I N =${ D O M A I N }
29 - P O R T =${ P O R T }
30 - S E C R E T _ K E Y =${ S E C R E T _ K E Y }
31 - G R A P H S _ P A T H =/ g r a p h s
32 - P E R S O N S _ G R A P H _ F I L E N A M E = p e r s o n s _ g r a p h . j s o n
33 - S E A T S _ G R A P H _ F I L E N A M E = i n v e r t e d _ s e a t s _ g r a p h . j s o n
34 nginx - s e r v e r :
35 b u i l d : ./ n g i n x
36 i m a g e : " nginx - s e r v e r "
37 c o n t a i n e r _ n a m e : " nginx - s e r v e r "
38 d e p e n d s _ o n :
39 - " project - seater - api "
40 p o r t s :
41 - " 8 0 : 8 0 "
Diplomska naloga 37
42 n e t w o r k s :
43 - project - seater - net
44 v o l u m e s :
45 - / var / www :/ d a t a / www
46
47 n e t w o r k s :
48 project - seater - net :
49 n a m e : project - seater - net
50
51 v o l u m e s :
52 p g d a t a :
Koda 4.3: Konfiguracijska datoteka Docker-compose
Datoteka je napisana v obliki YAML [28]. Njena vsebina je razdeljena na tri glavne sklope: services, networks in volumes. Sklop networks je namenjen izdelavi omreˇzij, preko katerih bodo povezani vsebniki Docker. V naˇsem primeru je to samo eno omreˇzje. Ker so velikosti vsebnikov statiˇcne in se zato stanje vsebnika ob ponovnem zagonu ne ohranja, uporabimo sklop volumes, v katerem rezerviramo trajni prostor na gostiteljskem sistemu za bazo PostgreSQL. V najbolj obseˇznem sklopu services doloˇcimo postavi- tev Docker vsebnikov. Postavitev vsebnika za streˇznik Actix Web API se zaˇcne na ˇsestnajsti vrstici. Tu mu doloˇcimo ime - project-seater-api.
Na sedemnjasti vrstici doloˇcimo lokacijo datoteke Dockerfile, predstavljene v izseku kode 4.1, iz katere se bo izdelala slika za vsebnik. V naslednjih dveh vrsticah doloˇcimo ime slike in vsebnika, ki je v tem primeru enako. v dvajseti vrstici doloˇcimo, da trenutni vsebnik za delovanje potrebuje vsebnik postgres-db. Nato doloˇcimo vrata, ki jih bo vsebnik izpostavil in omreˇzje, s katerim bo povezan. V ˇsestindvajseti vrstici doloˇcimo okoljske spremenljivke, na vsebniku, ki jih bo Actix Web API streˇznik potreboval za delovanje in s tem zakljuˇcimo postavitev vsebnika.
4.3.3 Aplikacija Angular
Aplikacija Angular predstavlja uporabniˇski vmesnik spletne aplikacije. Za razliko od ostalih delov aplikacije na sliki 4.3, aplikacija Angular ne teˇce v vsebniku Docker, temveˇc v brskalniku uporabnika. Aplikacijo si uporabnik v brskalnik prenese ob obisku naslova URL, na katerem obravnava HTTP zahtevke posredniˇski streˇznik Nginx, ki je opisan v naslednjem poglavju.
4.3.4 Posredniˇ ski streˇ znik Nginx
Posredniˇski streˇznik Nginx predstavlja skupno vhodno toˇcko v spletno apli- kacijo. Naloga posredniˇskega streˇznika je, da najprej servira aplikacijo An- gular za prenos v brskalnik uporabnika, nato pa aplikaciji Angular servira podatke iz Actix Web API streˇznika, ko jih le-ta zahteva. V primeru velike obremenitve API streˇznika, nam posredniˇski streˇznik omogoˇca tudi urav- noteˇzenje obremenitve na veˇc instanc API streˇznika. Konfiguracija posre- dniˇskega streˇznika se nahaja v datotekinginx.conf, ki je spodaj podrobneje opisana.
1 u s e r n g i n x ;
2 w o r k e r _ p r o c e s s e s 1;
3
4 e r r o r _ l o g / l o g s / e r r o r . log ;
5 pid / l o g s / n g i n x . pid ;
6 7
8 e v e n t s {
9 w o r k e r _ c o n n e c t i o n s 1 0 2 4 ;
10 }
11 12
13 h t t p {
14 i n c l u d e / etc / n g i n x / m i m e . t y p e s ;
15 d e f a u l t _ t y p e a p p l i c a t i o n / octet - s t r e a m ;
16
Diplomska naloga 39
17 l o g _ f o r m a t m a i n ’$r e m o t e _ a d d r - $r e m o t e _ u s e r [$t i m e _ l o c a l ] "$r e q u e s t " ’
18 ’$s t a t u s $b o d y _ b y t e s _ s e n t "$h t t p _ r e f e r e r " ’
19 ’ "$h t t p _ u s e r _ a g e n t " "$h t t p _ x _ f o r w a r d e d _ f o r " ’;
20
21 a c c e s s _ l o g / l o g s /a c c e s s. log m a i n ;
22
23 s e n d f i l e on ;
24
25 k e e p a l i v e _ t i m e o u t 65;
26
27 s e r v e r {
28 l i s t e n 80;
29
30 l o c a t i o n / {
31 r o o t / d a t a / www / project - seater - app ;
32 i n d e x i n d e x . h t m l i n d e x . htm ;
33 t r y _ f i l e s $u r i $u r i / / i n d e x . h t m l ;
34 }
35
36 l o c a t i o n / api {
37 r e w r i t e / api / ( . * ) /$1 b r e a k;
38 p r o x y _ s e t _ h e a d e r X - Real - IP $r e m o t e _ a d d r ;
39 p r o x y _ s e t _ h e a d e r X - F o r w a r d e d - For
$p r o x y _ a d d _ x _ f o r w a r d e d _ f o r ;
40 p r o x y _ s e t _ h e a d e r H o s t $h t t p _ h o s t ;
41 p r o x y _ s e t _ h e a d e r X - NginX - P r o x y t r u e ;
42 p r o x y _ p a s s h t t p :// project - seater - api : 8 0 8 0 ;
43 p r o x y _ r e d i r e c t off ;
44 }
45 }
46 }
Koda 4.4: Konfiguracijska datoteka nginx.conf
Med vrsticami 1 in 10 doloˇcimo, koliko procesov streˇznika Nginx ˇzelimo izdelati, kje se bosta nahajali datoteka za zapis napak in datoteka z identifi- katorji procesov streˇznika Nginx ter koliko odprtih povezav na proces bomo
dovolili.
V bloku med trinajsto in ˇsestinˇstirideseto vrstico opiˇsemo, na kakˇsen naˇcin bo posredniˇski streˇznik obravnaval HTTP zahtevke. Izpostavili bomo najpomembnejˇse dele. V sedemnajsti vrstici doloˇcimo format zapisov o do- stopu do streˇznika, ki se bodo zapisovali v datoteko, doloˇceno v vrstici enain- dvajset. V osemindvajseti vrstici doloˇcimo vrata, ki bodo odprta za HTTP zahtevke. V naˇsem primeru so to vrata 80, ki so privzeta vrata za HTTP zahtevke. V vrsticah trideset in ˇsestintrideset doloˇcimo, na katerih poteh naslova URL bo streˇznik sprejemal HTTP povezave in kaj bo na doloˇceni poti serviral. Na poti /, ki predstavlja ime streˇznika brez dodatne poti, bo streˇznik serviral Angular aplikacijo preko datoteke index.html, ki se bo naloˇzila v uporabnikov brskalnik. HTTP zahtevke na poti /api bo streˇznik posredoval Actix Web API streˇzniku v procesiranje.
Takˇsna postavitev posredniˇskega streˇznika nam omogoˇca enostaven pre- hod iz HTTP na HTTPS povezavo, ki poskrbi za ˇsifriranje podatkov med uporabnikom in streˇznikom, saj je potrebno le pridobiti certifikat in ga dodati v konfiguracijo.
4.3.5 Streˇ znik Actix Web in knjiˇ znica SICS
Streˇznik Actix Web in knjiˇznica SICS sta zdruˇzena v eno sliko, saj streˇznik Actix Web potrebuje knjiˇznico SICS za eno od glavnih funkcionalnosti spletne aplikacije – doloˇcanje podgrafnega izomorfizma. V tem poglavju si bomo ogledali postavitev obeh delov.
Streˇznik Actix Web je sestavljen iz:
glavne funkcije, ki se izvede ob zagonu streˇznika in poskrbi za ustre- zno postavitev streˇznika,
kontrolerjev, ki doloˇcajo, kaj se izvede za HTTP zahtevke na razliˇcnih naslovih URL,
modelov, ki sluˇzijo za preslikavo podatkov iz tabel v podatkovni bazi
Diplomska naloga 41 PostgresSQL v podatkovne strukture, ki jih pozna jezik Rust in obra- tno.
Knjiˇznica SICS vsebuje vmesnik, ki pridobi dva grafa v obliki JSON, ju pretvori v obliko, ki je razumljiva knjiˇznici SICS, poskusi doloˇciti podgrafni izomorfizem med njima s pomoˇcjo algoritma LFCBJ+M ter vrne rezultat v obliki JSON.
4.3.6 Podatkovna baza PostgreSQL
Podatkovna baza PostgreSQL je vzpostavljena v loˇceni sliki Docker in vsebuje podatkovni model, ki smo ga opisali v poglavju 4.1. Velikost vsebnikov je med izvajanjem omejena, medtem ko se lahko velikost podatkov na bazi spreminja. Zaradi tega se bazni podatki ne zapisujejo v vsebnik, ampak se nahajajo na disku gostiteljskega sistema. PostgreSQL vsebnik do podatkov zgolj dostopa in z njimi manipulira. Na takˇsen naˇcin lahko velikost podatkov raste, medtem ko velikost PostgreSQL vsebnika ostaja enaka.
Poglavje 5
Predstavitev spletne aplikacije
V tem poglavju bomo predstavili uporabniˇski vmesnik in uporabo spletne aplikacije. Ob vstopu v aplikacijo se uporabniku prikaˇze vmesnik za prijavo, prikazan na sliki 5.1. Vmesnik vsebuje polji za vnos uporabniˇskega imena in gesla, gumb za potrditev podatkov in proˇzenje prijave ter animiran logotip spletne aplikacije. V primeru nepravilnega vnosa zahtevanih podatkov se uporabniku prikaˇzejo ustrezna obvestila, kot je prikazano na sliki 5.3.
Slika 5.1: Uporabniˇski vmesnik za prijavo v spletno aplikacijo
Na ostalih vmesnikih se prikazuje meni na vrhu aplikacije (slika 5.2). Meni 43
vsebuje hiperpovezavi do vmesnika s pregledom sedeˇznih redov in do vme- snika za pomoˇc pri uporabi spletne aplikacije ter gumb za odjavo iz spletne aplikacije.
Slika 5.2: Meni na vrhu spletne aplikacije
Slika 5.3: Obvestila na uporabniˇskem vmesniku za prijavo v spletno aplikacijo Ko se uporabnik uspeˇsno prijavi, se mu prikaˇze vmesnik s pregledom sedeˇznih redov, prikazan na sliki 5.4. Vmesnik vsebuje osnovne podatke za vsak sedeˇzni red, ki ga je uporabnik ustvaril. Za vsak sedeˇzni red obstaja tudi gumb Izbriˇsi, ki uporabniku omogoˇca izbris sedeˇznega reda. Ob kliku na gumbNov sedeˇzni red se prikaˇze modalno okno, s pomoˇcjo katerega lahko uporabnik ustvari nov sedeˇzni red. Pri izdelavi novega sedeˇznega reda mora uporabnik vnesti naziv sedeˇznega reda, kot prikazuje slika 5.5.
S klikom na naziv sedeˇznega reda se uporabnik premakne na vmesnik za prikaz podrobnosti sedeˇznega reda (slika 5.6). Vmesnik je sestavljen iz
Diplomska naloga 45
Slika 5.4: Uporabniˇski vmesnik za pregled sedeˇzni redov v spletni aplikaciji
Slika 5.5: Modalno okno za izdelavo novega sedeˇznega reda v spletni aplikaciji
Slika 5.6: Komponenta z osebami na uporabniˇskem vmesniku za pregled podrobnosti sedeˇznega reda v spletni aplikaciji
stranskega menija in treh komponent: osebe, sedeˇzna mesta in sedeˇzni red.
Privzeto se prikaˇze komponenta z osebami. Na tej komponenti lahko upo- rabnik doloˇci, katere lastnosti oseb ˇzeli beleˇziti. Na podlagi lastnosti se bodo izdelale omejitve med osebami pri izdelavi sedeˇznega reda. Prav tako lahko uporabnik na tej komponenti dodaja in briˇse osebe ter ureja njihove lastnosti.
Na komponenti s sedeˇznimi mesti (slika 5.7) so sedeˇzna mesta prikazana v obliki vozliˇsˇc grafa, sosednost med dvema sedeˇznima mestoma pa je pri- kazana v obliki povezave med dvema voziˇsˇcema. S klikom na gumb Uredi se uporabniku prikaˇze meni, v katerem lahko dodaja in odstranjuje sedeˇzna mesta in sosednosti med njimi.
Na zadnji komponenti je prikazan sedeˇzni red (slika 5.8). Sedeˇzni red se izdela na podlagi podatkov iz prejˇsnjih dveh komponent. V sedeˇznem redu so prikazana sedeˇzna mesta in osebe, ki sedijo na njih. S klikom na gumb Izdelaj sedeˇzni red lahko uporabnik izdela nov sedeˇzni red, ˇce ˇse ne obstaja ali ˇce s trenutnim ni zadovoljen.
Diplomska naloga 47
Slika 5.7: Komponenta s sedeˇznimi mesti na uporabniˇskem vmesniku za pregled podrobnosti sedeˇznega reda v spletni aplikaciji
Slika 5.8: Komponenta s prikazom sedeˇznega reda na uporabniˇskem vme- sniku za pregled podrobnosti sedeˇznega reda v spletni aplikaciji
