MagistrskodeloMentor:prof.dr.BorutRobi£Ljubljana,2021 ALGORITEMZAOKTILINEARNOSHEMATIZACIJOOMREšIJ UNIVERZAVLJUBLJANIFAKULTETAZAMATEMATIKOINFIZIKOFAKULTETAZARAƒUNALNI’TVOININFORMATIKORa£unalni²tvoinmatematika2.stopnjaDomenKeglevi£

UNIVERZA V LJUBLJANI

FAKULTETA ZA MATEMATIKO IN FIZIKO

FAKULTETA ZA RAƒUNALNI’TVO IN INFORMATIKO Ra£unalni²tvo in matematika 2. stopnja

Domen Keglevi£

ALGORITEM ZA OKTILINEARNO SHEMATIZACIJO OMREšIJ

Magistrsko delo

Mentor: prof. dr. Borut Robi£

Ljubljana, 2021

Kazalo

Program dela v

1 Uvod 1

1.1 Struktura dela . . . 1

2 O shematizaciji 3 2.1 Osnovni pojmi . . . 4

2.2 O kompleksnosti problema . . . 10

2.3 Zna£ilnosti preglednih risb . . . 15

2.4 Pregled predhodnih pristopov . . . 16

2.4.1 Poenostavljanje poti . . . 16

2.4.2 Pristop z delovanjem sil . . . 17

2.4.3 Lokalna optimizacija . . . 17

2.4.4 Celo²tevilski program . . . 18

2.4.5 Drugi pristopi . . . 19

2.5 Povezani problemi . . . 19

2.5.1 Pozicija label . . . 19

2.5.2 Kriºanja prog . . . 20

2.5.3 Dinami£nost . . . 21

3 Algoritem 22 3.1 Trapezna dekompozicija . . . 22

3.1.1 Algoritem . . . 27

3.1.2 Uporabljene strukture in £asovna zahtevnost . . . 29

3.1.3 Pravilnost delovanja . . . 29

3.2 Oktilinearizacija . . . 30

3.2.1 Izgradnja oktilinearne poti . . . 31

3.2.2 Obmo£ja . . . 34

3.2.3 Algoritem . . . 36

3.2.4 Ra£unska zahtevnost in pravilnost delovanja . . . 36

3.2.5 Opombe . . . 38

3.3 Kompaktikacija . . . 40

3.3.1 Raz²irjeni graf trapezne dekompozicije . . . 41

3.3.2 Celo²tevilski program . . . 44

3.3.3 Spremenljivke . . . 48

3.3.4 Robni pogoji . . . 49

3.3.5 Kriterijska funkcija . . . 51

3.3.6 Algoritem . . . 52

3.3.7 Opombe . . . 53

3.4 Implementacija in rezultati . . . 53

4 Zaklju£ek 56

Literatura 59

A Primeri 61

A.1 Montreal . . . 61

A.2 Washington . . . 62

A.3 Dunaj . . . 63

A.4 Sydney . . . 64

A.5 Karlsruhe . . . 65

A.6 London . . . 66

Program dela

Magistrsko delo naj predstavi problem oktilinearne shematizacije grafov. Razi²£e naj vlogo razdelitve ravnine na trapeze v tem problemu. Nato naj razvije algoritem za shematizacijo, ki uporablja razdelitev ravnine na trapeze in ga v okviru tega dela tudi implementira. Dobljeni algoritem naj se aplicira na risbah podzemne ºeleznice ve£jih mest po svetu in njegovo u£inkovitost primerja z drugimi pristopi.

Osnovna literatura

[17] M. Nöllenburg, Automated drawing of metro maps, teh. por. 25, Universität Karlsruhe, 2005, doi: 10.5445/IR/1000004123

[7] M. de Berg in dr., Computational Geometry: Algorithms and Applications, Springer, 2008

[25] H.-Y. Wu in dr., A survey on transit map layout from design, machine, and human perspectives, Computer Graphics Forum 39(3) (2020) 619646, doi:

https://doi.org/10.1111/cgf.14030

Podpis mentorja:

Algoritem za oktilinearno shematizacijo omreºij Povzetek

Risba grafa, ki ima povezave narisane z vodoravnimi, navpi£nimi in diagonalnimi da- ljicami, se imenuje oktilinearna risba. Tak²ne risbe veljajo za pregledne in se pogosto uporabljajo za prikaz geografskih omreºij kot je zemljevid podzemne ºeleznice ve£jih mest. Zaradi ²tevila omreºij in raznolikosti risb nastane potreba po njihovem avto- matskem generiranju. Izkaºe se, da je to ra£unsko zahteven problem in algoritmi, ki to po£nejo morajo narediti kompromis med £asovno zahtevnostjo in kvaliteto izhoda. V tej magistrski nalogi je predstavljen nov algoritem, ki problem razdeli na dva koraka. Najprej generira risbo, ki je oktilinearna in ima vozli²£a na istih koordinatah kot vhodni podatki. Nato tak²no risbo izbolj²uje s spreminjanjem dol- ºin povezav. To je formulirano v obliki linearnega celo²tevilskega programa. Izkaºe se, da ima tak pristop ve£ zaºeljenih lastnosti in da je njegova £asovna zahtevnost konkuren£na v primerjavi z drugimi pristopi.

Algorithm for schematization of octilinear graph drawings Abstract

Graph drawing with edges that consist of horizontal, vertical and diagonal nite lines is called octilinear drawing. Such drawings are considered clear and easy to read and are often used to represent networks such as metro maps. Because of large number of networks and dierent features that can be put on a drawing, there is a need to generate them automatically. However, this is computationally expensive and algorithms that aim to do this must make tradeos between eciency and quality of the result. Here we present a new algorithm which generates octilinear drawing from geographical data in two steps. In the rst step it generates octilinear map which has unchanged coordinates of original vertices. In the second step it improves upon result of the rst step by correcting edge lengths. This is formulated as an integer linear program. This algorithm has many benecial properties and its running time is competitive with several other approaches.

Math. Subj. Class. (2010): 68W01, 68R10, 90C10

Klju£ne besede: Algoritmi, risanje grafov, celo²tevilsko programiranje Keywords: Algorithms, graph drawing, integer programming

1 Uvod

Omreºja in gra se spontano pojavijo na mnogih podro£jih. Eno izmed teh po- dro£ij je kartograja. Kartograja se ukvarja z izdelavo zemljevidov, na katerih med drugim ºelimo prikazati omreºja kot so ceste, reke in ºeleznice. Ker ima vsak zemljevid le omejeno koli£ino prostora in ker natan£en geografski prikaz ni vedno najprimernej²a oblika vizualizacije, se pogosto odlo£imo, da ga poenostavimo. To lahko storimo na veliko razli£nih na£inov.

Henry Charles Beck je leta 1931 izdelal shematski prikaz londonske podzemne ºeleznice (slika 1). Njegov prikaz ne ohranja natan£nih geografskih lokacij ºelezni²kih postaj, temve£ le njihovo pribliºno razporeditev. Pri tem je sledil nekaterim na£elom, za katere je menil, da vodijo do preglednega zemljevida. Eno od teh na£el je, da so vse linije prikazane kot vodoravne, navpi£ne ali diagonalne £rte. Tak²en prikaz se imenuje oktilinearna risba in se je izkazal kot pregleden in berljiv. Hitro je postal uspe²nica ne le za prikaz londonske podzemne ºeleznice, temve£ tudi drugih po svetu.

Slika 1: Londonska podzemna ºeleznica, Henry Beck, 1931 [4].

Tak²ne risbe se je od za£etka izdelovalo ro£no. To je £asovno zamudno, saj je potrebno vsako risbo izdelati od za£etka. Poleg tega je teºavno tudi spreminjanje ºe obstoje£e risbe, saj se avtobusne ali ºelezni²ke proge ob£asno spremenijo. Zaradi tega se je pojavila potreba, da se tak²ne risbe generira avtomatsko iz podatkov o geografski legi prog in postaj. Tema te magistrske naloge je predstavitev preteklih del na tem podro£ju in implementacija novega algoritma za generiranje tak²nih risb.

1.1 Struktura dela

V poglavju 2 je podana natan£nej²a denicija problema s katerim se ukvarjamo in nekaj osnovnih rezultatov o njegovi ra£unski zahtevnosti. Naveden je pregled po-

dro£ja in opisani pristopi, ki so bili do zdaj uporabljeni. Razloºeni so tudi tesno povezani problemi, ki se pojavijo pri obravnavanju tak²nih risb (problem postavlja- nja label in problem vrstnega reda izrisa prog).

V poglavju 3 je predstavljen nov algoritem za shematizacijo, ki je na majhnih in srednje velikih podatkih hiter in vrne pregledno oktilinearno risbo. Ta algoritem kot podrutino uporablja razdelitev ravnine na trapeze. Tak²na razdelitev je opi- sana v podpoglavju 3.1, kjer je naveden tudi u£inkovit algoritem za njen izra£un.

Glavna transformacija, ki jo izvede algoritem za shematizacijo, poteka v dveh kora- kih. Prvi je izdelava risbe, kjer vozli²£a ostanejo na istih koordinatah in ki ima vse povezave oktilinearne. Ta korak imenujemo oktilinearizacija in je opisan v podpo- glavju 3.2. Drugi korak je postopno izbolj²evanje te risbe s spreminjanjem dolºin povezav. Ta problem imenujemo problem kompaktikacije oktilinearne risbe grafa.

Njegove robne pogoje lahko opi²emo s pomo£jo pojmov iz teorije grafov. S pomo£jo tak²nega opisa ga nato formuliramo kot linearni celo²tevilski program. To je opi- sano v podpoglavju 3.3. Sledi podpoglavje 3.4, kjer so predstavljeni eksperimentalni rezultati od implementacije celotnega algoritma.

Na koncu v poglavju 4 podamo kratek zaklju£ek dela.

2 O shematizaciji

Oglejmo si sliko 2 na kateri so prikazane proge mestne ºeleznice v Sydneyu. Na levi je njihov natan£en geografski prikaz. Nanj lahko gledamo kot na ravninsko risbo nekega grafa. Vsaka povezava predstavlja en del neke proge in vsako vozli²£e neko postajo.

Na desni vidimo shematsko risbo prog in postaj. Ta ima povezave le v vodoravni, navpi£ni in diagonalni smeri (oktilinearnost). Poleg sprememb v koordinatah linij ima tudi pobarvane proge in vklju£uje imena postaj. Ta dva vidika sta lo£ena in nanju v tem delu ne bomo osredoto£eni. Naloga algoritma za shematizacijo je, da izvorno ravninsko risbo transformira v novo risbo, ki natan£no geometrijo izvorne risbe poenostavi in jo naredi bolj pregledno. Ta proces se imenuje shematizacija.

Tukaj bomo obravnavali shematizacijo v oktilinearno obliko, v splo²nem pa je na izhodu lahko tudi kak²na druga oblika.

Slika 2: Levo: geografska lega mestne ºeleznice v Sydneyu. Desno: shematski prikaz ºeleznice v Sydneyu [21].

Algoritmi za shematizacijo morajo zadostiti ve£ razli£nim zahtevam. Te so si med sabo lahko nasprotujo£e. Npr. po eni strani je zaºeljeno, da imajo povezave na shematski risbi enakomerno dolºino, in po drugi, da £imbolj sledijo izvornemu geografskemu poteku. Vsem tak²nim zahtevam ni moºno hkrati zadostiti in zato se i²£e kompromis, kjer imajo nekatere zahteve ve£jo vlogo kot druge.

Obstaja veliko poskusov, kako tak²ne algoritme narediti. Glavni izziv vsakega takega poskusa je, kako se omejiti na smiselno druºino re²itev, ki po eni strani vsebuje dobre shematske risbe in je po drugi strani ra£unsko dosegljiva. V splo²nem se izkaºe, da hitrej²i algoritmi pogosto vrnejo manj pregledne risbe, po£asnej²i, ki vrnejo kvalitetnej²e risbe, pa imajo zaradi po£asnosti omejeno uporabnost.

V nadaljevanju tega poglavja je problem shematizacije predstavljen v matema- ti£ni obliki. Nato je izpeljan izrek, ki opisuje njegovo kompleksnost. Izkaºe se, da ta problem spada med N P-teºke probleme. Zaradi tega ve£ina poskusov, ki se s tem problemom ukvarja, spada med hevristike in razli£ne oblike lokalnih optimizacij.

2.1 Osnovni pojmi

Uporabljali bomo pojme iz teorije grafov in ra£unske geometrije, zato najprej pono- vimo njihove denicije.

Graf G podan z mnoºico vozli²£ V in mnoºico povezav E ⊆ V ×V. Stopnja vozli²£a v ∈ V je ²tevilo povezav, ki ima v za eno od kraji²£. Najniºjo stopnjo ozna£imo z δ_G in najvi²jo z ∆_G. Sose²£ina vozli²£a v je mnoºica vseh tistih vozli²£, ki so kraji²£a kak²ne izmed povezav, ki vsebuje v. Tak²ne povezave imenujemo tudi inciden£ne povezave od vozli²£a v.

Subdivizija grafaGje graf, ki je iz grafa Gdobljen tako, da se neko povezavoeiz Gzamenja s potjo P_k (t.j. grafom z vozli²£i{1, . . . , k} in povezavami{(i, i+ 1)|i= 1, . . . , k−1}).

Minor grafa G je graf, ki je iz grafa G dobljen tako, da se neko povezavo e iz G odstrani, njuni kraji²£i pa zdruºi v eno vozli²£e. To vozli²£e ima za inciden£ne povezave vse tiste povezave, ki sta jih prej imeli kraji²£i povezave e. Pri tem se morebitna podvajanja povezav odstrani.

Vloºitev grafa G v ravnino je podana s preslikavo f : V → R², ki vsakemu vozli²£u v ∈V priredi to£ko v ravnini f(v)∈R², in mnoºico krivulj{γ_uv}uv∈E, kjer ima vsaka krivulja γ : [0,1] → R² za£etno to£ko v γ(0) = f(u) in kon£no to£ko v γ(1) = f(v). Pri tem morajo biti slike vozli²£ paroma razli£ne in povezave se ne smejo kriºati. Kadar je iz konteksta razvidno, da govorimo o slikah vozli²£ in povezav, izpu²£amo razlikovanje med vozli²£em in njegovo sliko oz. povezavo in njeno sliko. Vloºitev v ravnino imenujemo tudi risba grafa G in jo ozna£imo z Γ. Graf je ravninski, £e zanj obstaja vloºitev v ravnino.

Denicija 2.1. Poligonalna pot je mnoºica daljic {D1, D2, . . . , Dk}, kjer se daljici D_i inD_i+1, i= 1, . . . , k−1, stikata v enem kraji²£u, sicer pa so paroma disjunktne.

Poligonalna pot je ortogonalna, £e so vse daljice vodoravne ali navpi£ne. Druga£e re£eno, vsaka daljica zado²£a enemu izmed pogojev:

(P1) y(u) = y(v) (P2) x(u) = x(v)

Pri temx(·)iny(·)ozna£ujetaxoz. ykoordinato vozli²£a. Med dvema zaporednima daljicama je zavoj, £e zado²£ata razli£nemu pogoju. Poligonalna pot je oktilinearna,

£e so vse daljice vodoravne, navpi£ne ali diagonalne. Druga£e re£eno, vsaka daljica zado²£a pogoju (P1), (P2) ali pogoju

(P3) |x(u)−x(v)|=|y(u)−y(v)|

Analogno kot za ortogonalno pot tudi za oktilinearno pot pravimo, da ima zavoj, £e dve zaporedni daljici zado²£ata razli£nemu pogoju.

Denicija 2.2. Naj bo G ravninski graf z risbo Γ. Ortogonalna risba grafa G je tak²na ravninska risba, kjer je vsaka povezava ortogonalna pot. ƒe ortogonalna risba nima zavojev, jo imenujemo preprosta ortogonalna risba.

Slika 3: Levo: poligonalna pot. Sredina: ortogonalna pot. Desno: oktilinearna pot.

Slika 4: Levo: ortogonalna risba. Desno: preprosta ortogonalna risba.

Opazimo, da v grafu z ortogonalno risbo velja ∆G ≤ 4, saj bi sicer vsaj dve povezavi s skupnim kraji²£em leºali ena £ez drugo. Primer ortogonalne risbe in preproste ortogonalne risbe je na sliki 4.

Denicija 2.3. Naj bo G ravninski graf. Oktilinearna risba grafa G je tak²na ravninska risba, kjer je vsaka povezava oktilinearna pot. ƒe oktilinearna risba nima zavojev, jo imenujemo preprosta oktilinearna risba.

Podobno kot prej opazimo, da v grafu, ki ima oktilinearno risbo, velja ∆_G≤8.

Slika 5: Levo: oktilinearna risba. Desno: preprosta oktilinearna risba.

S pomo£jo denicije 2.3 lahko na² problem opi²emo na naslednji na£in. Recimo, da imamo dan ravninski graf G z najve£jo stopnjo ∆_G ≤ 8, in njegovo ravninsko risboΓ. I²£emo tak²no transformacijo risbe Γ, ki nam vrne oktilinearno risbo.

Tak²nih transformacij je v splo²nem lahko veliko. Tukaj nas zanimajo £im pre- glednej²e oktilinearne risbe. Lastnosti preglednih risb bomo podrobneje opredelili v poglavju 2.3, zaenkrat navedimo le eno nujno lastnost. Ta je, da ima za vsako vozli²£e grafa G oktilinearna risba enak cikli£ni vrstni inciden£nih povezav kot iz- vorna risba. Na sliki 6 vidimo risbo nekega grafa in dve razli£ni oktilinearni risbi.

Pregledna je v tem primeru sredinska risba, saj ohranja cikli£ni vrstni red povezav okrog vsakega vozli²£a.

Slika 6: Risba grafa G in dve njegovi razli£ni oktilinearni risbi.

Gra z vozli²£i stopnje ve£ kot 8 V primeru, da ima graf najve£jo stopnjo ve£jo od 8, ne moremo neposredno priti do njegove oktilinearne risbe. Kljub temu obstaja ve£ razli£nih pristopov, ki pomagajo priti do risbe, ki le malo odstopa od oktilinearne. Eden izmed njih je, da graf za£asno preoblikujemo v nov graf, ki ima najve£jo stopnjo kve£jemu 8. Shematizacijo nato izvedemo na tem grafu. Ko pri- demo do oktilinearne risbe jo v majhni meri preoblikujemo, da vozli²£a in povezave ustrezajo izvornemu grafu.

To lahko naredimo na slede£ na£in. Naj bov vozli²£e s stopnjo deg(v)>8. Na vsaki inciden£ni povezavi odv naredimo subdivizijo in nova vmesna vozli²£a cikli£no poveºemo med sabo (slika 7 sredina). Sose²£ina od v tako postanejo le nova vozli²£a od subdivizije. Nato odstranimo vozli²£e v in njegove inciden£ne povezave. Nova vozli²£a imajo stopnjo kve£jemu 3 (slika 7 desno) in inducirajo ve£kotnik s toliko ogli²£i, kot je bila stopnja vozli²£a v. To naredimo za vsa vozli²£a, ki imajo stopnjo ve£jo od 8, in dobimo graf z najve£jo stopnjo 8. Shematizacijo nato izvedemo na tem novem grafu. Na koncu, ko pridemo do oktilinearne risbe, v sredino induciranih ve£kotnikov postavimo originalna vozli²£a ter jih poveºemo z ogli²£i ve£kotnika. Nato odstranimo pomoºne povezave in vozli²£a na ogli²£ih in tako dobimo shematizacijo izvornega grafa.

To ni edini moºni pristop kako obravnavati grafe, ki imajo najve£jo stopnjo ve£jo kot 8. Druga£ne vrste ideja je, da naredimo nej²o mreºo in dopu²£amo, da gre iz nekega vozli²£a ve£ povezav vzporedno po nej²i mreºi. V primeru ortogonalnih risb sta to naredila Föÿmeier in Kaufmann [9].

Slika 7: Levo: vozli²£e stopnje ve£ kot 8. Sredina: subdivizija inciden£nih povezav in pomoºne povezave. Desno: pomoºne povezave in pomoºna vozli²£a s stopnjo 3.

Algoritmi pometanja

Algoritmi pometanja so neformalna druºina algoritmov iz podro£ja ra£unske ge- ometrije. Obravnavajo probleme na ravnini R², obi£ajno opremljene z Evklidsko metriko. Re²itev dane naloge i²£ejo s pomo£jo t.i. pometanja, ki je dobilo ime zaradi spominjanja na pometanje z metlo.

Ideja algoritmov pometanja je, da se £ez ravnino premikamo s premico, pri £emer se pri nekaterih to£kah ustavimo in izvedemo operacije, ki so potrebne za izra£un re²itve dane naloge. To£ke, pri katerih se ustavimo, imenujemo dogodki. Te to£ke lahko sortiramo, obi£ajno leksikografsko, vendar niso nujno vedno vse znane vna- prej. Hranimo jih v prednostni vrsti, ki jo sproti posodabljamo. Za obravnavanje dogodkov hranimo ²e dodatno strukturo, ki jo imenujemo stanje. Ta nam pomaga hraniti informacijo o tem kateri objekti so ob naslednjem dogodku relevantni za po- sodabljanje izhoda. Algoritem se zaklju£i, ko premica s katero pometamo, pride £ez celotno ravnino.

Psevdokoda za splo²en algoritem pometanja je napisana v algoritmu 1. Pri vsa- kem problemu posebej je potrebno dolo£iti kaj so dogodki, kak²na je struktura stanja in kako se obravnava vsak dogodek. Obi£ajen potek je, da se dogodke leksikograf- sko sortira, za kar je potrebno O(nlogn) operacij, in nato obravnava vsakega v konstantnem ali logaritemskem £asu.

Algoritem 1 Splo²en algoritem pometanja

1: procedure AlgoritemPometanja(V)

2: Q← prazna prednostna vrsta za dogodke

3: inicializacija Q

4: S ← struktura stanja

5: K ← struktura izhoda

6: while Q ni prazna do

7: q ←Q.pop_f ront()

8: obravnavaj(q, Q, S, K)

9: posodobi(S)

10: end while

11: return K

12: end procedure

Nekateri problemi, ki so na u£inkovit na£in re²ljivi z algoritmi pometanja so iskanje prese£i²£ mnoºice daljic, iskanje preseka, unije ali razlike dveh poligonov in izgradnja Voronoijevega diagrama [7].

Linearno programiranje

Matemati£na optimizacija se ukvarja s problemom iskanja najve£je ali najmanj²e vrednosti dane funkcijef :X →Rpri danih robnih pogojih. Funkcijof imenujemo kriterijska funkcija. Kadar je funkcija f linearna preslikava f : Rⁿ → R in robni pogoji linearne neenakosti, problem imenujemo linearni program.

Naj bo A∈ R^m×n in b,c ∈Rⁿ. Linearni program lahko zapi²emo kot re²evanje

naslednje ena£be

I²£emo min c^⊤x Pri pogojih Ax≤b

x≥0, x_i ∈R

(2.1)

Znanih je ve£ algoritmov, ki to nalogo re²ijo. Eden je simpleks algoritem [6], ki ima v najslab²em primeru eksponentno £asovno zahtevnost, vendar se izkaºe, da je na prakti£nih primerih hiter in uporaben. Uporabljajo se tudi metode notranje to£ke, ki zagotavljajo re²itev v polinomskem £asu. Tak²en je algoritem Karmar- karja [12].

ƒe v zgornji nalogi zahtevamo, da mora biti re²itevxcelo²tevilska, torejx_i ∈Zza

∀i, potem nalogo imenujemo celo²tevilski linearni program. S pomo£jo neenakosti v robnih pogojih lahko vrednostix_i omejimo na izbrane intervaleI_i ⊂Z. V posebnem primeru, ko x_i omejimo na mnoºico {0,1}, problem imenujemo 0-1 celo²tevilski program oz. binarni celo²tevilski program.

V celo²tevilskem programu obi£ajno predpostavljamo, da jeA ∈Z^m×n in b,c∈ Zⁿ. V splo²ni obliki ga zapi²emo kot re²evanje naslednje naloge:

I²£emo min c^⊤x Pri pogojih Ax≤b

x≥0, x_i ∈Z

(2.2)

Opomba 2.4. Naloga 2.2 je N P-polna.

Dokaz. To lahko vidimo tako, da neko N P-polno nalogo zapi²emo v obliki na- loge 2.2. To bomo storili za iskanje vozli²£nega pokritja grafa G. Ozna£imo z V mnoºico vozli²£ in E mnoºico povezav grafa G. Vozli²£no pokritje je tak²na naj- manj²a podmnoºica vozli²£ V^′ ⊂V, da je unija njihovih inciden£nih povezav enaka mnoºici E. Re²itev naslednjega binarnega celo²tevilskega programa je vozli²£no pokritje grafa G:

I²£emo min ∑︂

v∈V

x_v

Pri pogojih xu +xv ≥1 ∀uv ∈E x_v ∈ {0,1} ∀v ∈V

Relaksacija celo²tevilskega programa je opustitev pogoja, da mora biti re²itev celo²tevilska. Tak²en program je moºno re²iti v polinomskem £asu tako kot na- vaden linearni program (2.1). Njegova re²itev predstavlja spodnjo mejo za re²itev celo²tevilskega programa.

Re²evanje celo²tevilskega programa (2.2) je moºno s pomo£jo metode razveji in omeji (ang. branch and bound). Ta metoda prei²£e prostor vseh moºnih re²itev tako, da rekurzivno razdeli problem na manj²e podprobleme. Te tvorijo drevo podpro- blemov, pri £emer vsaka veja hrani oceno najbolj²e moºne re²itve. ƒe ima trenuten

kandidat za re²itev bolj²o vrednost kriterijske funkcije kot je ocena za neko vejo v drevesu podproblemov, potem se lahko to vejo presko£i. Na ta na£in se prei²£e celoten prostor re²itev in vrne optimalno.

V algoritmu (2) je splo²na shema za metodo razveji in omeji. Pri tem je z l_loc ozna£ena ocena veje poddrevesa inu_glob trenutna najbolj²a moºna re²itev. Obe sta pridobljeni z re²evanjem relaksacije celo²tevilskega programa.

Algoritem 2 Splo²en pristop metode razveji in omeji Vhod Naloga N, i²£emoarg min{c^⊤x|Ax≤b,x≥0}

Izhod Re²itev od N

Začetek Konec

Inicializacija

Izračun lokalne spodnje meje lloc in globalne

zgornje meje uglob

Izhod

Prazen seznam

l_loc < u_glob

Izberi

Razveji

Rešljiv Zavrzi

da ne

ne

da da

ne

Druga£na metoda za re²evanje celo²tevilskega programa je metoda ravninskih rezov (ang. cutting-plane method). To je iterativna metoda, ki v vsakem koraku izra£una re²itev relaksacije celo²tevilskega programa. V primeru, da ta re²itev ni celo²tevilska, poi²£e ravnino, ki razmejuje re²itev relaksacije in mnoºico potencialnih celo²tevilskih re²itev. Ta ravnina se imenuje prerezna ravnina. Njen obstoj sledi iz teorije linearnega programiranja. S prerezno ravnino je deniran nov robni pogoj, ki se ga v naslednjem koraku doda v program. To se iterativno ponavlja toliko £asa, dokler ne pridemo do celo²tevilske re²itve.

Izkaºe se, da je metoda ravninskih rezov samo po sebi po£asna, vendar je upo- rabna v kombinaciji z metodo razveji in omeji. Preden slednja razveji problem na dva manj²a podproblema, lahko izra£una prerezno ravnino in v podproblem vklju£i dodaten robni pogoj, ki je z njo dolo£en. Ta kombinirana metoda se imenuje razveji in odreºi (ang. branch and cut) in je implementirana v knjiºnici COIN-OR [1], ki je kasneje uporabljena v tej magistrski nalogi.

2.2 O kompleksnosti problema

Zanima nas kak²na je kompleksnost problema shematizacije. Najprej se omejimo na ortogonalne risbe in nato nadaljujemo s tem kaj je pri oktilinearnih risbah druga£e.

Denicija 2.5. Naj bo graf G ravninski graf z risbo Γ, ki ima najve£jo stopnjo vozli²£ kve£jemu 4. Problem OrtoRisba je odlo£itveni problem, ki odlo£i ali je moºno risbo Γ transformirati v ortogonalno risbo, ki ima enak cikli£ni vrstni red povezav okrog vsakega vozli²£a kot risba Γ.

Ta problem je preprostej²i kot splo²na oktilinearna risba in v zvezi z njim je Tamassia [22] pokazal naslednji znani izrek.

Izrek 2.6 (Tamassia). Naj bo G ravninski graf z risbo Γ, ki ima stopnjo vozli²£

najve£ 4. Potem obstaja algoritem s polinomsko £asovno zahtevnostjo, ki re²uje problem OrtoRisba.

V dokazu tega izreka je navedel algoritem, ki tak²no risbo konstruira. Natan£- neje, podal je algoritem za transformacijo v risbo, ki ima vse povezave iz zaporedja vodoravnih in navpi£nih daljic, ki imajo najmanj²e moºno ²tevilo zavojev in kjer risba ohranja cikli£ni vrstni red povezav okrog vsakega vozli²£a. Izkaºe se, da nje- govega algoritma ni moºno posplo²iti na primer, ko dovolimo diagonalne povezave in stopnjo vozli²£ do 8.

Denicija 2.7. Naj bo graf G ravninski graf z risbo Γ, ki ima najve£jo stopnjo vozli²£ kve£jemu 8. Problem OktiRisba je odlo£itveni problem, ki odlo£i ali je moºno risbo Γ transformirati v preprosto oktilinearno risbo, ki ima enak cikli£ni vrstni red povezav okrog vsakega vozli²£a kot risba Γ.

Problem OktiRisba je N P-teºek problem. To bomo v nadaljevanju pokazali tako, da ga bomo prevedli na problem Ravninski 3-SAT, za katerega je znano, da jeN P-poln. Slednjega bomo najprej opisali in nato pokazali kako se v polinomskem

£asu nanj prevede OktiRisba. Dokaz je povzet po [17].

Najprej se spomnimo na propozicijsko logiko in formule, ki v njej nastopajo.

Te so sestavljene iz spremenljivk, ki lahko zavzamejo vrednosti {0,1}, in logi£nih veznikov, ki jih poveºejo v formulo. Literal je oznaka za spremenljivko ali njeno negacijo (x_i ali ¬x_i), klavzula pa za disjunkcijo literalov (npr. x_i ∨ ¬x_j ∨ ¬x_k ∨ x_k). Spomnimo se, da lahko poljubno formulo v propozicijski logiki zapi²emo v konjunktivni normalni obliki (KNO). Ta oblika uporablja le logi£ne veznike ∧,∨in

¬ ter formulo zapi²e kot konjunkcijo klavzul.

Denicija 2.8. Naj bo {x_i} mnoºica spremenljivk in {C_j} mnoºica klavzul (obe kon£ni). Odlo£itveni problem SAT spra²uje ali obstajajo tak²ne vrednosti spremen- ljivk xi, da je formula⋀︁

Cj resni£na.

Cook-Levinov izrek pove, da je zgornji odlo£itveni problem N P-poln. Nas bo zanimal soroden problem, ki opazuje le manj²i del formul, ki lahko nastopajo v problemu SAT. Gre za tak²ne formule, ki jim lahko priredimo dolo£en ravninski graf.

Denicija 2.9. Naj boX ={x₁, . . . , x_n}mnoºica spremenljivk inC ={C₁, . . . , C_k} mnoºica tak²nih klavzul, kjer vsaka vsebuje kve£jemu tri literale. Formuliφ=⋀︁

C_j priredimo graf spremenljivk in klavzulH_φ, ki je deniran na naslednji na£in. Vozli²£a grafaH_φ predstavlja mnoºicaX∪C. Povezava poteka med dvema vozli²£ema u in v, £e je izpolnjen eden izmed pogojev:

1. u=x₁ in v =x_n.

2. u=x_i in v =x_i+1 zai= 1, . . . , n−1.

3. u=x_i in v =C_j, pri £emer klavzulaC_j vsebuje literal spremenljivke x_i.

ƒe je graf H_φ ravninski, potem pravimo, da je φ ravninska formula.

Ravninskost grafa lahko preverimo v £asu O(n)in zato tudi ali je dana formula φravninska formula. Risbo grafa lahko v£asih prikaºemo tako, da vozli²£a nari²emo kot kvadrate ali pravokotnike ter povezave kot vodoravne oz. navpi£ne £rte. Knuth in Raghunathan [14] sta pokazala, da je na ta na£in moºno graf vozli²£ in povezav H_φ narisati tako, da so kvadrati, ki predstavljajo spremenljivke, na isti vi²ini, in da povezave do klavzul potekajo po eni navpi£ni in eni vodoravni £rti (razen morda povezave medx₁ in x_n). Ta prikaz lahko vidimo na sliki 8.

x1 x2 x3 x4

C2

C1

C3

x5

C5 C6

C4

Slika 8: Graf spremenljivk in klavzul H_φ neke ravninske formule φ.

Denicija 2.10. Odlo£itveni problem Ravninski 3-SAT spra²uje, ali je dana rav- ninska formulaφ izpolnjiva.

Izkaºe se, da je tudi problem Ravninski 3-SATN P-poln [15]. Zato lahko risbo grafa spremenljivk in klavzul uporabimo tako, da druge probleme prevedemo na iskanje sorodne risbe, ki ohranja informacijo o izpolnjivosti formule φ. Ta ideja bo uporabljena v dokazu naslednjega izreka.

Trditev 2.11 (Nollenburg). Problem OktiRisba je N P-teºek.

Dokaz. Re²evanje problema Ravninski 3-SAT bomo v polinomskem £asu prevedli na re²evanje problema OktiRisba. To bomo storili tako, da bomo za poljubno ravninsko formulo φ na²li tak²en ravninski graf G(φ), da ga bo moºno narisati kot preprost oktilinearen graf natanko tedaj, ko je formulaφ izpolnjiva. Od tod bo

sledil izrek, saj bi vsak algoritem za generiranje tak²ne risbe s tem re²il tudi problem Ravninski 3-SAT.

Naj bo torej φpoljubna ravninska formula in naj bo H_φ pripadajo£i graf spre- menljivk in povezav. GrafG(φ)bomo konstruirali s pomo£jo risbeH_φ. To naredimo tako, da posamezne dele grafa H_φ zamenjamo z novimi pomoºnimi slikami (orig.

gadget). Zamenjave, ki jih izvedemo, so slede£e:

1. Vozli²£a, ki predstavljajo spremenljivke zamenjamo s pomoºno sliko za spre- menljivke.

2. Vozli²£a, ki predstavljajo klavzule zamenjamo s pomoºno sliko za klavzule.

3. Navpi£ne dele povezav od spremenljivk do klavzul zamenjamo s tunelom, ki vodi od pomoºne slike za spremenljivke do pomoºne slike za klavzule.

Pomoºne slike bomo denirali v nadaljevanju. Njihov namen je, da se skupaj sesta- vijo v nov graf, ki bo predstavljal G(φ).

Pomoºna slika za spremenljivke je zastavljena tako, da jo je v preprosti okti- linearni risbi moºno narisati samo na dva na£ina. Ta dva na£ina interpretiramo kot binarni vrednosti pripadajo£e spremenljivke. Naj box_i neka spremenljivka inξ_i njena pomoºna slika. Sliko sestavlja zunanje ogrodje in notranji gibljivi del. Gibljivi del se lahko pomika vodoravno v dve moºni poziciji, levo in desno. ƒe je v poziciji levo, potem to ustreza vrednosti spremenljivke x_i = 1, £e je desno pa vrednosti x_i = 0. Navzgor in navzdol vodijo tuneli do pomoºnih slik za klavzule, ki vsebujejo literal spremenljivke x_i. Tunelov je toliko kot je klavzul, kjer nastopa literal te spre- menljivke. Po sredini vsakega tunela poteka lo£en navpi£en gibljivi del. Ta je lahko postavljen v poziciji navzgor ali navzdol. Primer tak²ne pomoºne slike je prikazan na sliki 9.

Utemeljiti moramo, da je tako zastavljeno pomoºno sliko ξ_i res moºno narisati le tako, da imajo gibljivi deli na voljo zgolj dve poziciji. Na sliki 9 opazimo, da ξ_i sestavljajo trikotniki, ki so zloºeni skupaj v ve£je strukture. Trikotnik ABC, ki ima stranico AC narisano navpi£no, je v oktilinearni risbi moºno narisati le na tri na£ine. Prikazani so na sliki 10. ’tirje tak²ni trikotniki na enoli£en na£in tvorijo

²katlico kot na sliki 10 (desno).

’katlice lahko zloºimo skupaj, da dobimo zunanje ogrodje in notranje gibljive dele. Opis pomoºne slike ξ_i do zdaj je enoli£no dolo£en, vendar mu manjkajo po- vezave med ogrodjem in gibljivimi deli (vodoravnimi in navpi£nimi). Premislimo na kak²en na£in lahko ²katlice med sabo poveºemo. ƒe poveºemo dva para ²katlic, potem dobimo tri moºne slike, saj en vmesni trikotnik lahko nari²emo na tri na£ine (preostali vmesni trikotniki so potem natanko dolo£eni). Prikazani so na sliki 11a.

šelimo se izogniti eni izmed moºnosti, saj ho£emo imeti le dve moºni poziciji. To lahko naredimo tako, da opazujemo par treh ²katlic, ki ima na eni strani pomoºni trikotnik, kot na sliki 11b. V tem primeru imamo le dve veljavni moºnosti, saj se sicer robovi dotikajo. Tak²no konstrukcijo uporabimo za povezavo zunanjega ogrodja z notranjimi gibljivimi deli. Tako zastavljeno pomoºno sliko je zato na oktilinearen na£in moºno narisati le tako, da imajo gibljivi deli na voljo le dve poziciji.

Vodoravni in navpi£ni gibljivi deli so povezani na slede£ na£in. Denimo, da poteka tunel navzgor. V tistih klavzulah, kjer nastopa x_i brez negacije, imajo v pri- meru, da je vodoravni gibljivi del v poziciji levo (x_i = 1), navpi£ni gibljivi deli dovolj

Slika 9: Zgoraj: pomoºna slika od spremenljivke z osrednjim gibljivim delom v poziciji levo. Spodaj: pomoºna slika od spremenljivke z osrednjim gibljivim delom v poziciji desno.

Slika 10: Trije na£ini risbe trikotnika, £e je stranica AC navpi£na in edini na£in risbe kvadrata iz ²tirih trikotnikov.

prostora, da so postavljeni v pozicijo navzdol. ƒe je vodoravni gibljivi del v poziciji desno (x_i = 0), potem so navpi£ni gibljivi deli lahko samo v poziciji navzgor. To doseºemo tako, da v vodoravnem gibljivem delu naredimo vdolbine, ki omogo£ajo

(a)

(b)

navpi£nim gibljivim delom spremembo pozicije. Te vdolbine so postavljene tako, da so dosegljive samo ob primerni poziciji vodoravnega gibljivega dela. Za primer lite- ralov z negacijo ali navpi£nih tunelov, ki potekajo pod pomoºno sliko spremenljivke, se vloge na ustrezen na£in zamenjajo.

Sedaj si oglejmo pomoºno sliko za klavzule. Ta bo imela osrednji del in tri tunele, ki vodijo do treh spremenljivk, ki v klavzuli nastopajo kot literali. Osrednji del je tokrat sestavljen iz treh gibljivih delov, ki ustrezajo trem literalom, ki nastopajo v klavzuli. Ozna£imo te tri literale z l_i, l_j in l_k (v tem vrstnem redu). Osrednji del bo moºno narisati le tedaj, ko je klavzula izpolnjiva oz. kot ima vsaj eden od literalov vrednost 1. Levi gibljivi del se lahko nari²e samo v poziciji levo ali desno.

Osrednji gibljivi del se lahko nari²e v ²tirih pozicijah: kombinacije levo-desno in gor-dol. Desni gibljivi del, se lahko nari²e le v poziciji levo ali desno. Od vsakega gibljivega dela poteka tunel do pripadajo£e spremenljivke. V osrednjem delu tunela je kot prej navpi£en gibljivi del. Tunel in navpi£ni gibljivi del sta isti objekt kot v pomoºni sliki za spremenljivko. Primer pomoºne slike za klavzulo je prikazan na sliki 12.

Oglejmo si kako so osrednji gibljivi povezani med sabo. Denimo, da ima literal li vrednost 1. To omogo£a levemu gibljivemu delu, da je v poziciji levo. Posledica tega je, da sta v poziciji levo lahko tudi osrednji in desni del, kar je kombinacija, ki jo je vedno moºno narisati. Denimo, da ima literal l_j vrednost 1. To pomeni, da je narisan v poziciji navzdol (navzdol levo ali navzdol desno), kar omogo£a levemu in desnemu gibljivemu delu poljubno pozicijo. Tudi to kombinacijo je moºno narisati v oktilinearni risbi. Denimo, da ima literal l_k vrednost1. V tem primeru je narisan v poziciji desno, kar omogo£a osrednjemu in levemu gibljivemu delu, da zavzameta kakr²nokoli pozicijo. Kot prej tudi ta kombinacija dovoljuje oktilinearno risbo.

Premislimo, da pomoºne slike za klavzulo ni moºno narisati, £e imajo vsi trije literali vrednost 0. V tem primeru je levi gibljivi del nujno narisan v poziciji desno in desni gibljivi del v poziciji levo. To pa pomeni, da za osrednji gibljivi del ne ostane dovolj prostora brez dotikanja preostalega dela risbe.

Na ta na£in nari²emo vse pomoºne slike in dobimo risbo G(φ). Tak²no risbo je po konstrukciji moºno narisati natanko tedaj, ko obstajajo tak²ne vrednosti spre-

Slika 12: Pomoºna slika za klavzulo.

menljivk x_i, da so vse klavzule veljavne oz. da je formula φizpolnjiva.

Risba z manj zavoji je bolj zaºelena kot risba z veliko zavoji, vendar zgornji izrek v splo²nem prepre£uje, da bi u£inkovito na²li risbo z najmanj²im moºnim ²tevilom zavojev. Prakti£na posledica tega izreka je torej ta, da mora algoritem vsaj glede optimalnosti ²tevila zavojev sprejeti kompromis, £e ºeli v doglednem £asu vrniti rezultat.

2.3 Zna£ilnosti preglednih risb

Do zdaj smo od shematizacije pri£akovali le to, da ohranja cikli£ni vrstni red povezav od izvorne risbe. Ta pogoj sam po sebi ²e ne zagotavlja pregledne risbe. Te morajo zado²£ati ²e drugim dodatnim zna£ilnostim, do katerih lahko pridemo na dva na£ina.

Prvi na£in je, da izhajamo iz tega kako hitro uporabniki najdejo informacije na risbah z razli£nimi zna£ilnostmi. Tiste risbe, kjer hitro najdejo iskane informacije,

smatramo za bolj pregledne. Stott in Rodgers [20] sta naredila vpra²alnik, ki to izmeri. Uporabnikom sta dala razli£ne risbe na katerih so morali najti poti med razli£nimi postajami in odgovarjati na vpra²anja kot je "ƒez najmanj koliko postaj gre pot od postaje A do postaje B?". Izkazalo se je, da je povpre£en £as do odgovora na njunih shematskih risbah manj²i kot na izvornih geografskih.

Drugi na£in je, da najdemo skupne zna£ilnosti risb, ki so jih gra£ni oblikovalci naredili na roke za proge potni²kega prometa ve£jih mest po svetu. Predpostavljamo, da so risbe, ki jih imajo uporabniki raj²i in so bolj raz²irjene, tudi bolj pregledne.

Tako pridemo do naslednjega seznama zna£ilnosti.

(Z1) Cikli£ni vrstni red povezav okrog vozli²£ se ohranja. ƒe to ni izpolnjeno, potem je orientacija uporabnika v resni£nem svetu zelo okrnjena.

(Z2) Relativna pozicija vozli²£ se ohranja. ƒe je v izvorni risbi postaja P₁ severno od postaje P₂, potem tako ostane tudi v shematski risbi vsaj za postaje, ki so blizu.

(Z3) ’tevilo zavojev vsake proge je majhno. To pripomore, da uporabnik lahko hitro sledi poteku vsake proge.

(Z4) Koti med povezavami s skupnim kraji²£em so £imve£ji, saj je topim kotom laºje slediti kot ostrim.

(Z5) Povezave naj bodo ve£je od neke minimalne dolºine.

(Z6) Skupna dolºina povezav naj bo £immanj²a.

(Z7) Dolºine povezav naj bodo £imbolj enakomerne.

(Z8) Potek povezav naj odraºa izvorno risbo.

Te zna£ilnosti ni teºko zapisati s formulami in jih lahko uporabimo kot kriterij pri ocenjevanju preglednosti. Vsem ni moºno vedno zadostiti, zato se je potrebno odlo£iti kako jih obteºiti. Nekatere lahko smatramo kot nujne, nekatere pa lahko upo²tevamo le do neke mere. Med razli£nimi avtorji prihaja do razlik glede odlo£itve o tem kako pomembna je dolo£ena zna£ilnost.

2.4 Pregled predhodnih pristopov

Obstaja vrsta razli£nih poskusov kako se lotiti problema oktilinearne shematizacije.

Navedli bomo nekaj glavnih pristopov in njihovih avtorjev.

2.4.1 Poenostavljanje poti

Merrick in Gudmundsson [16] sta naredila shematizacijo risbe grafa s pomo£jo she- matizacije posamezne poti. Predstavila sta algoritem, ki za izbrano mnoºico dovo- ljenih smeri C in dano pot P, vrne novo pot P^′. Ta je podobna originalni potiP in poteka le v smereh C ter ima minimalno ²tevilo zavojev. S pomo£jo tega algoritma izdelata shematizacijo risbe tako, da posamezne povezave vhodne risbe postavita v

vrsto glede na pomembnost. Nato jih eno za drugo shematizirata in tako zgradita shematsko risbo. Algoritem je hiter, vendar ob£asno vrne rezultat, ki precej odstopa od zna£ilnosti preglednih risb.

Cabello [3] predstavi kombinatori£ni pristop, ki zagotavlja omejeno ²tevilo zavo- jev in potrebuje leO(nlogn)£asa. Pri tem koordinat vozli²£ ne spreminja in vedno vrne re²itev, kadar obstaja.

2.4.2 Pristop z delovanjem sil

Ideja pristopa z delovanjem sil je ta, da se za vsako vozli²£ev izra£una silo, s katero nanjo delujejo vsa ostala vozli²£a in povezave grafa G. Nato se vozli²£e premakne za majhno vrednost v tej smeri. Pri tem je sila lahko denirana na razli£ne na£ine, obi£ajno je odvisna od oddaljenosti in sosednosti. Dve vozli²£i, ki sta sosednji se privla£ita. Dve vozli²£i, ki nista sosednji, se odbijata, pri £emer velikost sile pada z oddaljenostjo. Tak pristop predstavi Hong [11], ki uvede ²e eno dodatno silo, ki jo imenuje magnetna sila. Ta rotira povezave okrog njihove sredinske to£ke, v tisti smeri, ki je najbliºja eni od oktilinearnih smeri. S tem se posku²a £imbolj pribliºati oktilinearnosti. Algoritem iterativno izra£unava premike to£k, dokler ne postanejo zelo majhni. Izkaºe se, da je hiter, vendar ne zagotavlja oktilinearnosti in kvaliteta risbe ni dovolj dobra za prakti£no uporabo.

Chivers [5] predstavi izbolj²ano razli£ico tega pristopa, ki spreminja velikost sil v odvisnosti od £asa (oz. ²tevila iteracij). Na za£etku prevladujeta privla£na in odbojna sila, nato se njun vpliv zmanj²uje in se pove£uje vpliv magnetne sile. Skupaj z nekaj postprocesiranja je pri²el do bistvenih izbolj²av tega pristopa, ²e vedno pa ne zagotavlja oktilinearnosti.

2.4.3 Lokalna optimizacija

Metode lokalne optimizacije so hevristi£ne metode, ki za£etno re²itev postopno iz- bolj²ujejo do tak²ne, ki v £imve£ji meri zado²£a kriterijski funkciji. Postopno izbolj-

²evanje se odvija v mnoºici dopustnih re²itev. Vsaka dopustna re²itev ima mnoºico sosedov, v katere se lahko algoritem premakne v naslednjem koraku. Ta izbira je lahko deterministi£na ali nedeterministi£na. Razli£ne metode se razlikujejo v tem kako denirajo sose²£ino in kako izbirajo re²itev za naslednji korak. Ta splo²en okvir lahko strnemo v algoritem 3.

Algoritem 3 Lokalna optimizacija

1: procedure LokalnaOptimizacija

2: x← poljubna re²itev

3: S(x)← sose²£ina od x

4: while ∃y∈S(x) :f(y)< f(x) do

5: x←y

6: end while

7: return x

8: end procedure

Na podro£ju generiranja oktilinearnih risb je bilo apliciranih ve£ razli£nih metod lokalne optimizacije.

Anand et al [2] aplicira simulirano ohlajanje na problem shematizacije. V vsa- kem koraku vozli²£a malo perturbira in oceni ustreznost dobljene risbe. Novo risbo sprejme z neko verjetnostjo, ki je odvisna od ustreznosti in postopek ponavlja.

Stott in Rodgers [20] opisujeta pristop z ve£kriterijsko optimizacijo. Vsako vozli-

²£e se premika znotraj omejenega pravokotnika okrog vozli²£a. Velikost pravokotnika se v vsaki iteraciji zmanj²a. Za izogibanje obti£anju v lokalnih minimumih se v vsaki iteraciji identicira podmnoºice vozli²£, ki se jih premika so£asno v enaki smeri. Po- zicioniranje label se obravnava skupaj s shematizacijo risbe. Ustreznost nove risbe po premiku vozli²£a, podmnoºice vozli²£ ali labele, se ocenjuje kot uteºeno povpre£je posameznih kriterijev, ki opredeljujejo pregledno oktilinearno risbo.

Galvão [10] predstavi genetski algoritem za shematizacijo. Risbo grafa razdeli na disjunktne poti in jih opi²e s pomo£jo polarnih koordinat. Pot je zaporedje to£k in vsaka naslednja to£ka je opisana s polarnimi koordinatami glede na prej²njo to£ko. Ena pot denira en kromosom. Mutacije in kriºanja kromosomov so de- nirane kot spremembe v polarnih koordinatah to£k. Tako zgradi novo populacijo in oceni njihovo ustreznost glede na kriterije shematizacije. Pozicioniranje label ni obravnavano.

Pomankljivost pristopov lokalne optimizacije je, da ne zagotavljajo oktilinearno- sti in ne ohranjajo nujno cikli£nega vrstnega reda povezav okrog vozli²£. Ve£krat tudi obti£ijo v lokalnih minimumih.

2.4.4 Celo²tevilski program

Nöllenburg [18] shematizacijo in pozicioniranje label formulira v obliki linearnega celo²tevilskega programa.

Kriterij za ocenjevanje kvalitete shematizacije razdeli na krepke pogoje (hard constraints) in ²ibke pogoje (soft constraints). Krepki pogoji so tisti, ki nastopajo v robnih pogojih od celo²tevilskega programa in jim mora biti nujno zado²£eno.

Mednje spadajo:

(H1) Vse povezave morajo biti oktilinearne.

(H2) Cikli£ni vrstni red okrog vsake povezave se mora ohranjati.

(H3) Vsaka povezava ve£ja ali enaka minimalni dolºini l_min.

(H4) Poljubni dve povezavi, ki nista inciden£ni, morata biti oddaljeni najmanj za minimalno razdaljo d_min.

’ibki pogoji nastopajo v kriterijski funkciji in jim je lahko zado²£eno le do neke mere. Mednje spadajo:

(S1) Vsaka proga mora imeti £immanj²e ²tevilo zavojev. ƒe ima zavoje, potem morajo potekati pod kotom, ki je £im bliºje π (t.j. izogibanje ostrim kotom).

(S2) Relativna pozicija vsakega para vozli²£ se ohranja v £im ve£ji meri. Druga£e povedano, kot med x-osjo in vektorjemv−u mora biti £imbolj podoben kotu

med x-osjo in vektorjem Γ(v)−Γ(u), kjer sta u in v vozli²£i vhodnega grafa inΓ preslikava, ki podaja shematizacijo.

(S3) Skupna dolºina povezav je £im manj²a.

Mnoºico spremenljivk sestavljajo nove koordinate vozli²£ in pomoºne spremen- ljivke, ki opisujejo pogoje za npr. ²tevilo zavojev. Skupno ²tevilo spremenljivk in povezav je O(m²), kjer je m ²tevilo povezav. Ta program vrne kvalitetno risbo, njegova pomankljivost pa je nepredvidljiva in visoka £asovna zahtevnost.

ƒasovno zahtevnost tega programa je izbolj²al Oke [19], ki opusti zahtevo o celo²tevilskih koordinatah in formulira manj stroge robne pogoje.

2.4.5 Drugi pristopi

Wang in Ming [24] predstavita formulacijo v obliki optimizacijske naloge, ki vse- buje kvadrati£ne £lene. Imenujeta jo focus+context. Ta obmo£je neke izbrane proge deformira tako, da je proga in njen kontekst v ospredju in narisan v pregledni ok- tilinearni obliki, preostali del risbe pa je lahko bolj zgo²£en. Optimizacijsko nalogo re²ita s pomo£jo metode konjugiranega gradienta. Algoritem je hiter in za omejen primer uporabe vrne pregledno risbo.

Wang in Peng [23] predstavita ²e eno formulacijo v obliki optimizacijske naloge s kvadrati£nimi £leni. Ta lokacije nekaterih postaj pusti ksne in druge premika, da na koncu dobi oktilinearno risbo. Namen tega pristopa je, da sluºi kot pripomo£ek za polavtomatsko izdelavo shematske risbe. Gra£ni oblikovalec se odlo£a katere postaje pusti ksne in s pomo£jo algoritma postopoma pride do pregledne risbe.

Uporaba strojnega u£enja za generiranje oktilinearnih risb je ²e neraziskano po- dro£je.

2.5 Povezani problemi

ƒe si ²e enkrat ogledamo sliko 1, vidimo, da poleg oktilinearnih povezav vsebuje tudi labele, ki ozna£ujejo imena postaj, in pobarvane proge, ki ozna£ujejo kje poteka vsaka posamezna proga. Poleg tega je bila ta risba narejena leta 1931 in ne odraºa dana²njih prog podzemne ºeleznice v Londonu. Ta opaºanja nas vodijo do treh problemov, ki so povezani z iskanjem pregledne risbe.

2.5.1 Pozicija label

Labele prikazujejo ime postaje in so obi£ajno postavljene v njeni bliºini. Pri tem obstaja ve£ razli£nih moºnosti kam jo postaviti, pri £emer so nekatere moºnosti bolj pregledne in zato bolj zaºeljene. Dobra postavitev label ima naslednje lastnosti:

(L1) Vse postaje imajo labelo.

(L2) Labela leºi blizu postaje.

(L3) Labele so dovolj velike za celotno ime postaje.

(L4) Labele se med sabo ne prekrivajo.

(L5) Labele ne prekrivajo prog ali postaj.

(L6) Labele vzdolº iste proge ne menjajo strani.

Obi£ajno se okrog lokacije postaje dolo£i moºen prostor za labelo (slika 13 levo) in nato s pomo£jo izbranega algoritma, ki £imbolj upo²teva lastnosti (L1)-(L6), dolo£i njeno natan£no pozicijo. Kadar je vzdolº nekega odseka ve£ postaj, za katere ºelimo, da imajo labele na enaki poziciji, se jih pogosto obravnava s pomo£jo pomoºnega paralelograma (slika 13 desno).

Slika 13: Levo: nekatere moºnosti za pozicijo labele blizu vozli²£a. Desno: labele na isti strani poti se lahko obravnava s pomo£jo pomoºnega paralelograma.

Za iskanje prostora in postavljanje label obstajata dva pristopa. Prvi je, da se najprej izdela oktilinearno risbo in se nato loti iskanja pozicij label. Na ta na£in je tako izdelava risbe kot postavljanje label £asovno u£inkovitej²e, vendar je kon£ni rezultat slab²e kvalitete, saj ksna risba omeji moºne pozicije label. Drugi pristop je, da sta izdelava risbe in postavljanje label integrirana v en algoritem. To se lahko stori tako, da se zraven vsake postaje postavi prazen pravokotnik ali paralelogram, ki predstavlja prostor za labelo. Nato se pri iskanju risbe izdela primerno velikost tega pravokotnika (ali paralelograma) in na koncu vanj izpi²e napis.

2.5.2 Kriºanja prog

Na kon£ni risbi je potek vsake proge prikazan s svojo barvo. Proge potekajo preko ve£ povezav vhodnega grafa in na vsaki povezavi se lahko pojavi ve£ prog. Ker ne ºelimo, da pri izrisu leºijo ena £ez drugo, je potrebno izbrati vrstni red izrisa. Izkaºe se, da vrstni red vpliva na to, ali se izris prog kriºa in da razli£en vrstni red vodi v razli£no ²tevilo kriºanj. To lahko vidimo na sliki 14.

Slika 14: Levo: dve kriºanji. Desno: tri kriºanja.

Matemati£no gledano proge ustrezajo mnoºici poti P, ki pokrijejo vse povezave grafa G. Vrstni red izrisa prog lahko opi²emo kot preslikavo f :E×P →N0. Ta vsaki poti na vsaki povezavi priredi zaporedno mesto, kjer naj se izri²e. Pri tem vrednost 0 interpretiramo tako, da pot ne poteka preko dane povezave. Kriºanje dveh poti se zgodi na vozli²£ih. Dve poti se kriºata, kadar je vrstni red njunih inci- den£nih povezav okrog vozli²£a alternirajo£ (slika 15). Naloga minimizacije ²tevila kriºanj je iskanje tak²ne preslikave f, ki inducira minimalno ²tevilo kriºanj. Izkaºe se, da je ta problemN P-poln [8].

V V

Slika 15: Levo: ne-alternirajo£i vrstni red okrog vozli²£av. Desno: alternirajo£i red okrog vozli²£a v.

Variacija tega problema je, da ne opazujemo kriºanja posameznih prog, tem- ve£ proge, ki pridejo in grejo po istih povezavah, zdruºimo v en blok prog. Nato pre²tevamo koliko je kriºanj blokov prog. To lahko vidimo na sliki 16.

Slika 16: Eno kriºanje dveh blokov oz. ²tiri kriºanja posameznih prog.

Ta variacija problema je zanimiva predvsem za shematske prikaze elektri£nih omreºij, kjer se pojavlja ve£je ²tevilo vodnikov, ki potekajo po skupnih daljnovodih.

2.5.3 Dinami£nost

Ob£asno se dogajajo spremembe v vhodnih podatkih, saj se spremenijo ali uvedejo nove proge in spremenijo ali dodajo nove postaje. Ve£ina dozdaj²njih pristopov je osredoto£ena na izdelavo stati£ne risbe. Risbo generirajo v celoti in se ne ozirajo na to ali bi sprememba v vhodnih podatkih vodila do zelo podobne ali izrazito druga£ne risbe. Nadgraditev teh pristopov za dinami£no generiranje risb je malo raziskano podro£je. Izjema je Chivers [5], ki je svoj pristop z vzmetmi in magnetnimi silami raz²iril na dinami£no razli£ico.

3 Algoritem

Predstavili bomo nov algoritem za oktilinearno shematizacijo. Ta vhodno risbo transformira v dveh korakih. V prvem koraku vsa vozli²£a vhodnega grafa pusti na istih koordinatah in transformira le potek povezav, da postanejo oktilinearna.

S tem se zagotovi oktilinearnost povezav, pri £emer se ohranja cikli£ni vrstni red povezav okrog vsakega vozli²£a in relativne pozicije vozli²£. Pomankljivost dobljene risbe je predvsem neenakomerna dolºina povezav. S tem se ukvarja drugi korak algoritma. Ta poda kombinatori£ni opis pogojev, ki morajo veljati, £e ºelimo dolºino neke povezave spremeniti in ob tem ohranjati oktilinearnost in izgled preostalega dela risbe. Te pogoje formuliramo v obliki linearnega celo²tevilskega programa, katerega re²itev inducira podgraf, ki ga je moºno translirati in ohranjati vse zaºeljene lastnosti.

Oba koraka kot podrutino uporabljata razdelitev ravnine na trapeze. To je ta- k²na mnoºica trapezov, ki pokrije ravnino in ima povezave vhodnega grafa na osnov- nicah ali krakih trapezov. Tak²no konstrukcijo je moºno uporabiti na ve£ na£inov.

V prvem koraku je uporabljena tako, da se s pomo£jo pomikanja po osnovnicah trapezov, ki leºijo v vodoravni, navpi£ni ali diagonalni smeri, pride do oktilinearnih poligonalnih poti. V drugem koraku pa je uporabljena tako, da s pomo£jo sosedno- sti trapezov posku²amo najti cikel (pod dolo£enimi pogoji), ki razdeli risbo grafa na dva dela. Povezava, ki ji ºelimo spremeniti dolºino poteka iz zunanjosti cikla v notranjost. Vozli²£a znotraj cikla dolo£ajo podgraf, ki ga je moºno translirati, pri

£emer se oktilinearnost in cikli£ni vrstni red povezav okrog vozli²£ ohranja. Vozli²£a in povezave, ki leºijo v zunanjosti cikla, ostanejo nespremenjene.

V nadaljevanju je najprej denirana trapezna dekompozicija ravnine in nato opisana oba koraka algoritma.

3.1 Trapezna dekompozicija

Osnovna ideja trapezne dekompozicije je, da s pomo£jo ravninske risbe grafa Grav- nino razdelimo na trapeze na tak na£in, da so osnovnice od vseh trapezov vzporedne.

Kraki trapezov leºijo na povezavah, razen kadar je kak²na od povezav vzporedna z osnovnicami (v tem primeru je del osnovnic). Naklon osnovnic je lahko poljuben.

Zaradi tega so trapezi lahko zarotirani in zato tudi dekompozicija ni enoli£na.

Denicija 3.1. Naj bo G ravninski graf z risbo Γ, kjer je vsaka povezava daljica.

Naj bo α ∈ [0,2π). Naj bo risba Γ vsebovana v dovolj velikem pravokotniku R, ki je zarotiran za kotα. ƒe iz vsakega vozli²£av ∈Gnari²emo pomoºni ravni £rti pod kotom α, dokler ne zadanemo neko povezavo grafa G, vozli²£e grafa G ali stranico pravokotnikaR, potem dobimo risbo nekega grafa. Lica tega grafa razdelijo ravnino na disjunktne mnoºice. Vsako lice je trapez, pravokotnik ali trikotnik (slika 17), razen zunanjega lica, ki je ravnina brez R. Na pravokotnike in trikotnike gledamo kot na poseben primer trapezov. Dobljeno razdelitev ravnine imenujemo trapezna dekompozicija ravnine glede na graf G in risboΓ v smeriα. Kadar je kontekst jasen uporabljamo skraj²an izraz trapezna dekompozicija ravnine.

V nadaljevanju se omejimo na primer, ko so osnovnice trapezov navpi£ne. V

Slika 17: Trapezna dekompozicija ravnine glede na grafG, kjer so osnovnice trapezov navpi£ne.

drugih primerih lahko risbo zarotiramo in sledimo istim argumentom kot za ta pri- mer.

Opomba 3.2. Vedno obstaja enoli£no dolo£en najbolj levi in najbolj desni trapez.

Dokaz. Ker ima G kon£no mnogo vozli²£, v njegovi risbi obstaja mnoºica tak²nih, ki imajo najmanj²o x-koordinato. Ozna£imo jo zLV. Naj bo mnoºica LE mnoºica povezav iz G med vozli²£i iz L_V. Na levi od L_V in L_E ni nobenega vozli²£a ali povezave. Naj bo K mnoºica ravnih £rt, £e iz vozli²£ L_V nari²emo £rte navzgor in navzdol do prvega vozli²£a v LV ali stranice pravokotnika R (kot v deniciji trapezne dekompozicije). Tedaj unija £rtL_E∪K poteka od spodnjega do zgornjega roba pravokotnika R in predstavlja desno stranico najbolj levega trapeza. Podobno za najbolj desni trapez.

Opomba 3.3. Vsako vozli²£e v trapezni dekompoziciji ima stopnjo vsaj2.

Dokaz. Naj bo v poljubno vozli²£e. Po konstrukciji je v bodisi vozli²£e grafa G, bodisi ogli²£e pravokotnika R, bodisi kon£na to£ka navpi£ne £rte do neke povezave grafa G ali stranice pravokotnika R. V prvem primeru je deg(v) ≥ 2, saj v de- kompoziciji obstajata vsaj povezavi navzgor in navzdol, lahko pa ²e kak²na iz grafa G. V drugem primeru je deg(v) = 2, saj gre za ogli²£e pravokotnika R. V tretjem primeru je bodisideg(v) = 3, kadar je kon£na to£ka navpi£ne £rte v notranjosti neke povezave grafa G ali stranice R, bodisi deg(v) ≥ 2, £e sovpada z nekim vozli²£em grafaG. Sledi, da je deg(v)≥2.

Opomba 3.4. Vsako (notranje) lice trapezne dekompozicije je konveksno.

Dokaz. Potreben in zadosten pogoj za konveksnost mnogokotnika je, da ima vse notranje kote manj²e ali enake π. Premislimo, da je ta pogoj je izpolnjen. ƒe gre za ogli²£e, ki izhaja iz vozli²£a grafa G, potem po deniciji trapezne dekompozicije iz njega izhajata vsaj povezavi navzgor in navzdol. Torej je notranji kot vsakega sosednjega lica manj²i ali enakπ. ƒe gre za ogli²£e pravkotnikaR, potem je notranji

kot enak ^π₂. ƒe gre za ogli²£e, ki je kon£na to£ka navpi£ne £rte, potem ta razdeli povezavo grafa G ali stranico R na dve (kolinearni) povezavi in notranji koti sose- dnjih lic so ponovno manj²i ali enaki π. Sledi, da so (notranja) lica dekompozicije konveksna.

Trditev 3.5. Vsako notranje lice trapezne dekompozicije je trapez. Pri tem na trikotnike in pravokotnike gledamo kot na poseben primer trapezov.

Dokaz. Naj bo f notranje lice. Najprej premislimo, da je na levo in desno stran omejeno z navpi£nima £rtama (lahko dolºine 0) in da na robu ne vsebuje drugih navpi£nih £rt. Vozli²£a na robu od f so podmnoºica vozli²£ izG in vozli²£ na koncu pomoºnih navpi£nih £rt. Ker jih je kon£no mnogo, obstajata vozli²£i z najve£jo in najmanj²oxkoordinato, ki sta tudi vozli²£i grafaG. To drºi, saj ima vsaka navpi£na pomoºna povezava ali povezava grafaG, vsaj na enem izmed kraji²£ vozli²£e grafaG. Ozna£imo ju z v_min in v_max in za£asno predpostavimo, da sta enoli£no dolo£eni. Po deniciji trapezne dekompozicije iz v_min in v_max izhajata navpi£ni povezavi. Lahko sta del lica f, vendar ne nujno. Premislimo, da nobena druga navpi£na povezava e_vert ne more biti del lica f. ƒe bi bila, potem leºi na koordinati med v_min inv_max. Po opombi 3.4 vemo, da jef konveksno. Torej mora notranjost odf leºati bodisi na levi bodisi na desni strani ode_vert. Vendar od tod sledi, da daljica od notranje strani povezave e_vert do vsaj enega izmed vozli²£ v_min ali v_max pre£ka zunanjost (slika 18).

Torej tak²na navpi£na povezava ne more obstajati. V primeru, dav_min inv_max nista enoli£ni, potem so preostala vozli²£a z isto x koordinato povezana z navpi£nimi povezavami. Res, saj bi v nasprotnem primeru v okolici dveh tak²nih vozli²£ na²li notranji to£ki, med katerima daljica pre£ka zunanjost (podobno kot na sliki 18), kar je v protislovju s konveksnostjo.

v_min v_max

e_vert

Slika 18: Lice lahko vsebuje navpi£ne povezave le skrajno levo ali desno, sicer kr²i konveksnost.

šelimo ²e videti, da sta leva in desna navpi£na £rta zgoraj in spodaj povezani z ravno £rto. Od tod bo sledilo, da je f trapez. Naj bo l_max vozli²£e, ki ima med najbolj levimi vozli²£i najve£jo y koordinato. Podobno naj bo r_max vozli²£e, ki ima med najbolj desnimi vozli²£i najve£joykoordinato. Vemo, da morata bitil_maxinr_max povezani in da mora biti notranjost na spodnji strani povezav med njima. šelimo videti, da sta povezani zgolj z ravno £rto. Recimo, da nista. To pomeni, da vmes obstaja vsaj eno dodatno vozli²£e iz grafa G. Po deniciji trapezne dekompozicije morata iz njega izhajati navpi£ni £rti. To je protislovje, saj ima lice f navpi£no £rto na robu zgolj skrajno levo in skrajno desno in nobenih drugih.

Sledi, da ima f na levi in desni navpi£no £rto, ki sta zgoraj in spodaj povezani z ravno £rto. Torej je f trapez (navpi£ni £rti sta osnovnici, povezavi med njima pa kraka).

Trditev 3.6. Naj bo f poljubno lice trapezne dekompozicije. Potem leva in desna osnovnica vsebujeta (vsaka) vsaj eno vozli²£e iz G, kraka pa ne vsebujeta nobenega vozli²£a iz G, razen morda v kraji²£u.

Dokaz. Naj bo f poljubno lice. Opazimo, da je osnovnica unija povezav iz G, vozli²£ iz G in pomoºnih £rt. ƒe je pomoºna £rta del osnovnice, potem je vozli²£e od koder pomoºna £rta izhaja tudi del osnovnice. ƒe je povezava del osnovnice, potem sta tudi njeni kraji²£i del osnovnice. Sledi, da je v uniji vsaj eno vozli²£e iz G. V notranjosti krakov ne nastopa nobeno vozli²£e, saj bi sicer med levo in desno osnovnico po deniciji trapezne dekompozicije obstajala navpi£na £rta.

Trditev 3.7. Naj bo Gravinski graf z n vozli²£i. Ozna£imo trapezno dekompozicijo grafaG z T(G)in nanjo gledamo kot na graf. Potem je T(G)ravninski graf z O(n) vozli²£i in povezavami.

Dokaz. Ravninskost sledi iz denicije, saj se navpi£ne £rte ne kriºajo in zato ne morejo inducirati minorja ali subdivizije odK₅aliK_3,3. Premislimo koliko je vT(G) vozli²£. Po deniciji trapezne dekompozicije iz vsakega vozli²£a grafa G nari²emo pomoºno £rto navzgor in navzdol. Torej vsako vozli²£e iz G inducira najve£ 2novi vozli²£i vT(G). Zato je vT(G)kve£jemun+ 2n+ 4 vozli²£, pri £emer se²tevanec4 nastopa zaradi ²tirih ogli²£ pravokotnikaR. Premislimo kak²no je ²tevilo povezav v T(G). Naj bom ²tevilo povezav v grafu G. Po deniciji trapezne dekompozicije iz vsakega vozli²£a v Gpoteka navpi£na £rta navzgor in navzdol. Kraji²£e te navpi£ne

£rte je na vozli²£u grafaG, povezavi grafa Gali stranici pravokotnika R. V zadnjih dveh primerih navpi£na £rta razdeli povezavo vGoz. stranico odR na dve povezavi v T(G). Sledi, da v T(G) nastopa kve£jemu m + 2n+ 2n + 4 povezav. Ker je m∈ O(n), je ²tevilo povezav vT(G) tudi v O(n).

Trapezna dekompozicija se pogosto uporablja v povezavi s poizvedbo v katerem licu leºi dana to£ka. V tem primeru nam pomaga izdelati naklju£nostno podat- kovno strukturo, ki na to vpra²anje odgovori v pri£akovanem O(logn) £asa (knjiga [7], poglavje 6). V na²em primeru nas ne bodo zanimale poizvedbe to£k, temve£

informacija o tem kateri trapezi so sosednji. V ta namen deniramo (multi)graf trapezne dekompozicije.

Denicija 3.8. Naj boGravninski graf s trapezno dekompozicijo, ki ima osnovnice trapezov v navpi£ni smeri. Graf trapezne dekompozicije je (multi)graf, ki ima za vozli²£a notranja lica trapezne dekompozicije, povezave pa potekajo med tistimi sosednjimi lici, ki imajo skupno navpi£no £rto.

Zgled lahko vidimo na sliki 19. V zgornji deniciji nastopa sosednost le v primeru skupne navpi£ne £rte, na kateri sta osnovnici trapezov, ne pa tudi drugih skupnih

£rt, na katerih leºijo kraki. To denicijo je moºno raz²iriti tudi za primere skupnih krakov. To bomo storili kasneje v poglavju 3.3, ko bomo tak²no raz²irjeno denicijo tudi potrebovali.

Na podoben na£in lahko deniramo graf trapezne dekompozicije v smeri, ki ni navpi£na.

Slika 19: Levo: trapezna dekompozicija grafa G. Desno: graf trapezne dekompozi- cije.

Opomba 3.9. Graf trapezne dekompozicije ni nujno povezan (npr. slika 19).

Opomba 3.10. V splo²nem je graf trapezne dekompozicije pravi multigraf, saj imamo med dvema trapezoma lahko ve£ kot eno povezavo. Primer je graf poti P_n narisan navpi£no (slika 20). Ta primer pokaºe tudi, da je stopnja vozli²£ lahkoO(n).

R

Pn

Slika 20: Graf trapezne dekompozicije potiP_n.

Trditev 3.11. Naj boG ravinski graf zn vozli²£i inT_G graf trapezne dekompozicije.

Potem je TG ravninski graf z O(n) vozli²£i in povezavami.

Dokaz. Ravninskost lahko premislimo tako, da nari²emo ravninsko risbo. Po deni- ciji 3.8 so vozli²£a odT_Glica trapezne dekompozicije. Ta so po trditvi 3.5 trapezi. V vsakem trapezu si izberemo poljubno to£ko v notranjosti in ker so trapezi konveksni lahko nari²emo ravno £rto do katerekoli to£ke na robu. V posebnem primeru, ko si dva sosednja trapeza delita del osnovnice, lahko iz notranjosti enega in drugega nari²emo ravni £rti do neke to£ke na skupnem delu roba. To storimo za vse sosednje

trapeze, vedno iz iste to£ke v notranjosti, da se £rte ne sekajo. Tako dobimo rav- ninsko risbo odT_G. Ker je ²tevilo lic trapezne dekompozicije O(n)je ²tevilo vozli²£

in povezav v T_G tudi O(n). 3.1.1 Algoritem

Navedli bomo algoritem za u£inkovit izra£un trapezne dekompozicije. Uporabili bomo algoritem pometanja. Njegova osnovna ideja je naslednja. Z navpi£no pre- mico p pometamo od leve proti desni. Dogodki so to£ke vhodnega grafa, urejene leksikografsko. Vsi dogodki so znani vnaprej, vendar se jih obravnava po blokih.

Blok dogodkov je mnoºica zaporednih dogodkov z isto x koordinato, ki leºijo med dvema povezavama vG(slika 21). Ti dve povezavi nimata nobeno kraji²£e na tej x koordinati. Med dogodki iz istega bloka ne poteka nobena druga povezava iz G, ki pre£ka xkoordinato dogodkov (je nima na kraji²£u) in ki bi imela en del dogodkov na eni strani in drug del na drugi strani. V tem primeru bi se blok razdelil na dva manj²a bloka. Stanje je urejeno binarno iskalno drevo in hrani trapeze, ki sekajo premico p. Trapezi v stanju so urejeni glede na nara²£ajo£oykoordinato prese£i²£a zgornjega roba trapeza s premicop. Stanje se posodablja po obravnavi bloka dogod- kov. Na izhod vrnemo seznam vozli²£, ki predstavljajo trapeze, in seznam povezav med njimi. Vsak trapez hrani kazalce na vozli²£a in povezave, ki tvorijo njegovi osnovnici, in dva kazalca na povezavi, ki tvorita njegova kraka.

Slika 21: Blok dogodkov leºi na isti x-koordinati med dvema povezavama.

Na za£etku dodamo na izhod najbolj levi trapez, nato sledi obravnava blokov dogodkov. Ta poteka v dveh zankah. Zunanja zanka obravnava prvi dogodek v bloku in pri tem na izhod doda novo vozli²£e, ki predstavlja trapez desno spodaj pod trenutnim dogodkom. Hkrati doda tudi novo povezavo s trapezom levo spodaj, ki ga prebere iz stanja. Pri dodajanju nove povezave se posodobita oba trapeza, levi in desni, saj hranita informacijo o sosedih.

Nato notranja zanka nadaljuje z obravnavo tega dogodka in vseh preostalih do- godkov v tem bloku. Za vsak dogodek se sprehodi £ez njegove inciden£ne daljice na desni strani in vsaki£ na izhod doda en nov trapez. Pri tem shrani informacijo o zgornji in spodnji daljici, ki ga omejuje, saj to predstavlja njegova kraka. Ob za- dnji (najvi²ji) inciden£ni daljici na izhod doda tudi povezavo z najvi²jim trapezom

na levi strani dogodka, ki ga prebere iz stanja. Nato nadaljuje isto obravnavo pri naslednjem dogodku.

Ko zanka pride do zadnjega dogodka v bloku se posodobi stanje. Posodobi se tako, da se odstranijo vsi trapezi, ko so bili na levi strani bloka dogodkov, in dodajo vsi novi, ki so na desni.

Psevdokoda je napisana v algoritmu 4.

Algoritem 4 Trapezna dekompozicija

1: procedure TrapeznaDekompozicija(V, E)

2: ▷ Inicializacija

3: V_out, E_out ← prazna seznama ▷ Vozli²£a in povezave izhodnega grafa

4: D ←seznam vozli²£ V ▷ Dogodki

5: D.sort() ▷Leksikografsko sortiramo

6: l₀ ← nov trapez ▷ Najbolj levi trapez

7: S ← prazno dvoji²ko iskalno drevo ▷ Trenutno stanje

8: S.insert(l₀)

9: V_out.push(l₀)

10: ▷ Obravnava dogodkov

11: for i= 1; i≤D.size(); i+ + do

12: l_start ←S.upper_bound(D[i]) ▷Trapez spodaj levo, ki vsebuje D[i]

13: r_start← nov trapez ▷Nov trapez spodaj desno, ki vsebuje D[i]

14: e← nova povezava med l_start inr_start

15: E_out.push(e)

16: V_new ← prazen seznam trapezov ▷Novi trapezi na desni

17: V_new.push(r_start)

18: l_cur ←l_start ▷ Trenutni levi trapez

19: current_block ←True

20: while current_block do ▷ Obravnava bloka

21: I_l ←leve inciden£ne povezave od D[i]

22: if ¬I_l.empty()then

23: l_cur←I_l.upper() ▷ Trapez levo zgoraj odD[i]

24: end if

25: I_r ←desne inciden£ne povezave od D[i]

26: for j = 1, . . . , I_r.size() do ▷Novi trapezi na desni

27: r ← novi trapez na desni

28: V_new.push(r)

29: end for

30: r ←V_new.last() ▷ Trapez desno zgoraj odD[i]

31: e← nova povezava med l_cur inr

32: E_out.push(e)

33: if i+ 1≤D.size() then ▷Pogoji za trenutni blok

34: same_x←same_x(D[i], D[i+ 1])

35: same_block ←same_block(D[i], D[i+ 1])

36: current_block ←same_x and same_block

37: else

38: current_block ←False

39: end if