Tartalomjegyzék TARTALOMJEGYZÉK...1 BEVEZETŐ...3 FELHASZNÁLÓI DOKUMENTÁCIÓ...4

Tartalomjegyzék TARTALOMJEGYZÉK.............................................................................................1 BEVEZETŐ.................................................................................................................3 FELHASZNÁLÓI DOKUMENTÁCIÓ .....................................................................4 1.

Felhasználói felület ........................................................................................4

2.

Ábrázolás ablak .............................................................................................8

3.

Tömb Ábrázolás ablak ...................................................................................9

4.

Gráf importálása ..........................................................................................10

5.

Gráf generálás..............................................................................................12

6.

Élsúly intervallum megadása........................................................................12

Algoritmusok ..........................................................................................................12 1.

Szélességi bejárás ........................................................................................13

2.

Dijkstra algoritmus.......................................................................................14

3.

Bellmann-Ford algoritmus ...........................................................................15

4.

Prim algoritmus ...........................................................................................15

5.

Warshall-Floyd algoritmus...........................................................................16

FEJLESZTŐI DOKUMENTÁCIÓ..........................................................................18 1.

Használati esetek..........................................................................................18 1.1 Gráf szerkesztése .....................................................................................18 1.2 Algoritmusok szemléltetése......................................................................18 1.3 Kiegészítő funkciók .................................................................................18

2.

Felhasználói felület megjelenési terve ..........................................................19 2.1 Vezérlő elemek és kezdeti beállításaik......................................................20 2.2 Gráf szerkesztése .....................................................................................23

3.

Osztályok.....................................................................................................26 3.1 GrafAlgoForm osztály..............................................................................27 3.2 Gráf osztály..............................................................................................29 3.3 Él osztály .................................................................................................34 3.4 Csúcs osztály ...........................................................................................35 3.5 Algoritmus osztály ...................................................................................35 3.6 egyLepes osztály......................................................................................44

3.7 bejartEl struktúra......................................................................................45 3.8 Szövegek osztály:.....................................................................................46 3.9 Konkrét algoritmus osztályok...................................................................47 3.9.1 Szélességi bejárás osztály .............................................................47 3.9.2 Dijkstra algoritmus osztály ...........................................................51 3.9.3 Prim algoritmus osztály ................................................................55 3.9.4 Bellmann-Ford algoritmus osztály ................................................58 3.9.5 Warshall-Floyd algoritmus osztály................................................61

4.

3.10

WarshellegyLepes ................................................................................65

3.11

AlgoKezelo osztály ..............................................................................66

3.12

PriorityQueue osztály ...........................................................................67

3.13

SorElem struktúra.................................................................................69

3.14

Abrazolas osztály .................................................................................70

3.15

TombAbrazolas osztály ........................................................................72

3.16

TombControl osztály............................................................................75

3.17

MatrixControl osztály...........................................................................77

3.18

SorControl............................................................................................79

3.19

GrafGeneral osztály..............................................................................80

3.20

VelElsuly osztály .................................................................................81

3.21

AlgoNevek osztály ...............................................................................81

3.22

Szinek osztály ......................................................................................81

Tesztelési terv ..............................................................................................82

ÖSSZEGZÉS .............................................................................................................87 IRODALOMJEGYZÉK ...........................................................................................88

2

Bevezető Szakdolgozatom témája gráfbejáró algoritmusok, egy forrásból induló, és minden csúcspárra minimális költségű utakat kereső algoritmusok szemléltetése és az algoritmusok működésének elmagyarázása. A program célja, hogy az azt használó a program segítségével az implementált algoritmusokat kipróbálhassa, megértse működésüket. Ehhez a programnak tudnia kell felhasználóbarát módon, könnyen kezelhető kezelőfelületet nyújtania a gráf szerkesztéséhez, amin az algoritmus tanulmányozható, az algoritmusok futtatásához, gráf mentéséhez, korábban szerkesztett gráf betöltéséhez. A futást lehessen szüneteltetni, hogy a működési mechanizmus jobban követhető legyen. Oktatási, szemléltetési célból az algoritmusok legyenek animálhatóak, hogy működésüket magyarázat mellett is lehessen követni. Lépésenkénti futásnál minden lépés könnyen áttanulmányozható, lehessen visszalépni, ha egy lépés nem volt világos, de ha csak a végeredmény fontos, akkor azt is gyorsan meg lehessen jeleníteni. A program a szélességi bejárás, Dijkstra, Prim, Bellmann-Ford, Warshall-Floyd algoritmusok működését hivatott szemléltetni, de fontos, hogy könnyen kibővíthető legyen más gráfalgoritmusokkal is. Köszönettel tartozom Kőhegyi János tanár úr támogatásáért, Bodnár Katalin, Molnár András és Fráter Tamás hallgatótársaim ötleteiért és teszteléseiért.

3

Felhasználói dokumentáció 1.

Felhasználói felület Indítás után az alábbi ablak látható:

1. Rajzterület 2. Algoritmus futási módjának beállítása 3. Gráf mátrixos illetve éllistás megjelenítésének be-/kikapcsolása 4. Gráf csúcsméretének beállítása 5. Gráf ábrázolásának módja 6. Gráf irányítottságának beállítása 7. Gráf élsúlyozott, illetve csúcscímkézett legyen-e 8. Státuszsor 9. Menü 1. Rajzterület: Itt lehet a gráfot szerkeszteni, ha algoritmus nem fut. 

Új csúcs elhelyezése: bal egérgomb kattintással



Csúcs kijelölése: bal egérgombbal csúcsra kattintás, a csúcs színe pirosra változik. Start csúcsból induló algoritmus csak akkor indítható, ha egy csúcs ki van

4

jelölve. 

Csúcs mozgatása: jobb egérgombbal a mozgatni kívánt csúcsra kattintva, és a gombot

nyomva

tartva

a

csúcs

átmozgatható a kívánt helyre. Mozgatás közben a csúcs zöld színű, halványzöld színnel pedig látható az eredeti helye. 

Csúcs törlése: Kijeölt csúcs a „Delete” gombbal törölhető.



Kijelölt

csúcs

cimkéjének

szerkesztése:

(ha

a

„Csúcscimkézett” mező be van jelölve) „Insert” billentyű megnyomása után a csúcs címkéje átírható. A címke szerkesztését az „Enter”-rel lehet befejezni. (Figyelem! Két csúcsnak nem lehet azonos a címkéje!) 

Él rajzolása két csúcs között: bal egérgomb nyomva tartása mellett két csúcs összekötése. Ha a gráf élsúlyozott, az gomb elengedése után lehetőség van az él súlyának beállítására.



Él rajzolása új csúcsokkal: üres területre bal gombbal kattintás, és gomb nyomva tartásával az egér húzása az él kívánt végpontjához, ami lehet egy már meglévő csúcs és üres terület is.



Él kijelölése: bal egérgombbal kattintás az élre, a kijelölt él pirosra változik.



Él törlése: Kijelölt él a „Delete” gombbal törölhető.



Kijelölt él súlyának szerkesztése: (ha az „Élsúlyozott” mező be van jelölve) „Insert” billentyű megnyomása után az él súlyát átírható. A súly racionális szám lehet. A súlyszerkesztés az „Enter”-rel fejezhető be.

2. Algoritmus futási módjának beállítása: Algoritmus kiválasztására, futási módjának beállítására szolgál. 

Indít gomb: Az algoritmus szemléltetésének indítása (ha van kijelölt csúcs, vagy a Warshall-Floyd

algoritmus

fog

futni).

5

Algoritmus szemléltetése közben a gráfot nem lehet szerkeszteni. Algoritmus futása közben „Stop” a gomb felirata. Megnyomásával az algoritmus leáll, újra lehet a gráfot szerkeszteni. 

Legördülő menü: Kiválasztható, hogy melyik algoritmus legyen szemléltetve. (Algoritmus futása közben nem módosítható)



„Lépésenként” mező: ha be van jelölve, az algoritmus lépésenként fog futni. A „->” feliratú gombbal lehet az algoritmus következő lépését megnézni, a „<-” feliratúval az előző lépésre lehet visszalépni. (Algoritmus futása közben módosítható)



„Animálás” mező: ha be van jelölve, az algoritmus folyamatosan fog futni. A futás sebessége az alatta levő csúszkával állítható. Futás közben a „<-” és „->” gombok helyén „Szünet” feliratú gomb látható, amivel a futás szüneteltethető. Ha nincs bejelölve, az algoritmus indítása után egyből az algoritmus végállapota látható. Megjegyzés: Algoritmus futása közben váltani lehet a „Animálásos” és a „Lépésenkénti”

futás

között.

(Algoritmus

futása

közben

nem

módosítható) 

„Tömbök mutatása” mező: Ha be van jelölve, algoritmus futása közben egy másik ablakban látható az algoritmus által használt tömbök, mátrixok, sorok, valamint magyarázat az egyes lépésekhez. (Algoritmus futása közben módosítható)

3. Gráf mátrixos illetve éllistás megjelenítésének be-/kikapcsolása 4. Gráf csúcsméretének beállítása: A csúszkával beállítható a csúcs mérete 0 és 20 között. A csúszka fölötti számra kattintva a csúcsméret „kézzel” is beállítható, azonban a méretet itt is 0 és 20 között kell megadni. (Algoritmus futása közben módosítható) 5. Gráf ábrázolásának módja: Kiválasztható, hogy a gráf mátrixosan, vagy éllistásan legyen ábrázolva. Az ábrázolás változása látható a „Ábrázolás” ablakban, valamint az algoritmus futása is e szerint történik. (Algoritmus futása közben nem módosítható) 6. Gráf irányítottságának beállítása: Beállítható, hogy a gráf irányított, vagy irányítatlan legyen-e. A változtatás látható a gráfon és az „Ábrázolás”

6

ablakban is. Ha a gráf szerkesztése irányítatlanul történik, és később a gráf irányítottra lesz módosítva, az élek iránya az lesz, amilyen irányban a rajzolásuk történt. Figyelem: „Irányított” állapotról „Irányítatlan” állapotra váltásnál, ha van a gráfnak negatív élköltsége, akkor negatív kör keletkezik, ha van kettő hosszú köre, párhuzamos élek keletkeznek, a gráf nem lesz egyszerű (Algoritmus nem futtatható). (Algoritmus futása közben nem módosítható) 7. Gráf

élsúlyozott,

illetve csúcscímkézett legyen-e:

Az élsúlyozás

változtatása megjelenik a gráfon és az „Ábrázolás” ablakban is. Ha a gráf csúcscímkézetlen, az „Ábrázolás” ablakban a csúcsok címkéje helyén azok belső azonosítója látható. (Algoritmus futása közben nem módosítható) 8. Státuszsor: az aktuálisan végrehajtható műveletekről, illetve algoritmus futása közben az algoritmus aktuális lépéséről tájékoztat 9. Menü: 

Fájl: 

Új: Új gráf készítése. Régit törli.



Mentés:

Gráf

mentése

.graf

kiterjesztéssel. 

Megnyitás: .graf kiterjesztésű gráf betöltése





Gráf exportálása: Gráf mentése szöveges állományba



Gráf importálása: Gráf betöltése szöveges fájlból



Kilépés: Program bezárása.

Beállítások: 

Ne méretezze át a gráfot: Ha ez be van jelölve, az ablak átméretezésével a gráf mérete nem változik.



Gráf generálás: Egy véletlen gráf generálása.



Véletlen élsúly: Új él rajzolásakor véletlenszerűen választ a program élsúlyt egy adott intervallumból.



Élsúly intervallum megadása: Beállítható, hogy a program mely intervallumból válasszon ki élsúlyt.

7



Ábrázolás „Ábrázolás”

mindig

felül:

ablak

mindig

felül legyen látható 

Tömb

ábrázolás

felül:

„Tömb

mindig

ábrázolás”

ablak mindig felül legyen látható  2.

Segítség: Segítség a program használatához.

Ábrázolás ablak A gráf mátrixos illetve éllistás tárolását szemléltető ablak. Az „Ábrázolás mutatása” mezővel lehet az ablak megjelenítését ki- illetve bekapcsolni.

2.1

Mátrixos ábrázolás: Legyen n a csúcsok száma. „A gráfot egy n  n -es mátrixban ábrázoljuk, ahol az oszlopokat és a sorokat rendre a csúcsokkal indexeljük. Egy mezőben akkor van 1-es, ha a hozzá tartozó oszlop által meghatározott csúcs szomszédja a sor által meghatározott csúcsnak.” [2] „Ha súlyozott a gráf, akkor a súlyokat is el kell tárolni. Ezt is a mátrixon belül oldjuk meg. A súly valós számokat vehet fel. Természetesen adódik, hogy ahol előzőleg 1-est írtunk, azaz létezett az illető él, oda most írjuk be az él költségét. […] Vezessük be a  élsúlyt, és a nem létező élek esetén a mátrix megfelelő helyére írjunk  -t. Egy ilyen "élen" csak végtelen nagy költséggel

tudunk

végighaladni

(tehát

nem

tudunk).”

[2]

A könnyebb áttekinthetőség érdekében a program a „∞” helyett „-” jel szerepel az ábrázolásban. Az oszlop- és sorazonosítók a gráf csúcscímkéi, ha a „Csúcscimke” mező be van jelölve, ha nincs, a gráf csúcsainak belső azonosítói jelennek meg. „A helyfoglalás mindig ugyanakkora, független az élek számától, a mátrix 8

méretével n2-tel arányos. (Az n pontú teljes gráfnak is ekkora a helyfoglalása.) Tehát sűrű gráfok esetén érdemes használni, hogy ne legyen túl nagy a helypazarlás.” [2] 2.2

Éllistás ábrázolás: „Vegyünk fel, egy mutatókat tartalmazó Adj[1..n] tömböt (a csúcsokkal indexeljük a tömböt). A tömbben lévő mutatók mutatnak az éllistákra. Irányított gráf esetén, az éllisták listaelemei reprezentálják az éleket. Az élnek megfelelő listaelemet abban a listában tároljuk, amelyik csúcsból kiindul az él, és a célcsúcs címét (tömb indexét, címkéjét stb.) eltároljuk a listaelemben. […] Irányítatlan gráf esetén, egy élnek két listaelemet feleltetünk meg. Élsúlyozott gráf esetén, az él súlyát is a listaelemben

fogjuk

tárolni.”

[2]

A tömb és listaelem azonosítók a gráf csúcscímkéi, ha a „Csúcscimke” mező be van jelölve, ha nincs, a gráf csúcsainak belső azonosítói jelennek meg. „Mivel a memóriaigény az élek számával 2

arányos, ezért az éllistás ábrázolást ritka gráfok ( E  V ) esetén szokták használni. Ugyanis sűrű gráf esetén a szomszédsági mátrixhoz képest, itt még jelentkezik, a listák láncolásából származó (mutatók), plusz helyfoglalás.” [2] 3.

Tömb Ábrázolás ablak Az algoritmusok futása során használt tömböket (Warshall-Floyd algoritmus esetén

mátrixokat),

valamint

az

sort

aktuálisan

ábrázolja, végrehajtott

lépésről ad tájékoztatást. Tömbök: Szülő és távolság tömbök, melyek

a

csúcs

cimkéivel

vannak

indexelve. Szülő tömb esetén a „/” a nilpointert jelenti. 9

Sor: A tömbök alatt helyezkedik el. Szélességi bejárás esetén sor, Dijkstra és Prim algoritmus esetén minimumválasztó elsőbbségi sor. Mátrix: Warshall-Floyd algoritmus esetén a tömbök és a sor helyén a „Legrövidebb utak D mátrixa”, a „Megelőzési mátrix” és a „Tranzitív lezárt mátrix” található. A sor- és oszlopazonosítóik a gráf csúcscímkéi. A „Tranzitív lezárt mátrix”-ban „-” jelöli, ha a sor- és oszlopazonosító által meghatározott csúcsok között nincs út, „+” ha van. Magyarázat: algoritmus

Az lépéseit

írja ki. A benne lévő szöveg kijelölhető, a kijelölt sorok a vágólapra másolódnak. 4.

Gráf importálása Lehetőség van gráf importálására szövegfájlból. A fájl három blokkból álljon: 1. Gráf beállításai 2. Gráf csúcsai 3. Gráf élei A fájlban a ## jel a megjegyzés jele, a # sor az egyes blokkok elválasztására szolgál. 1. Gráf beállításai: #beallitasok Itt adhatók meg különböző kulcsszavak, amikkel a gráf tulajdonságait lehet megadni: ellistas: Gráf ábrázolása éllistás legyen matrixos: Gráf ábrázolása mátrixos legyen sulyozott: Gráf súlyozott legyen sulyozatlan: Gráf súlyozatlan legyen csucscimkezett: Gráf csúcscimkézett legyen cimkezetlen: Gráf csúcscimkézetlen legyen iranyitott: Gráf irányított legyen iranyitatlan: Gráf irányítatlan legyen

10

Amennyiben valamelyik tulajdonságra nincs beállítás, a program az aktuális állapotai szerint állítja be a hiányzó tulajdonság értékét. 2. Gráf csúcsai: #csucslista Ebben a szakaszban adhatók meg a gráf csúcsai. Minden sorba a gráf egy csúcsa kerül az alábbiak szerint: Csúcscímke

X koordináta Y koordináta

Példa: 1

152

86

A koordináták valós számok lehetnek, és 0-nál nagyobbnak kell lenniük. A (0,0) pont a „Rajzterület” bal felső sarka. Tipp: Célszerű az X koordinátákat 20 és 734, az Y koordinátákat 20 és 489 között megadni. Megjegyzés: Két csúcsnak nem lehet ugyanaz a címkéje. 3. Gráf élei: #ellista Ebben a blokkban a gráf élei állíthatóak be. Minden sorba a gráf egy éle kerül az alábbiak szerint: Kezdőcsúcs Végcsúcs Példa: 1

3

Élsúly

2

A Kezdő és Végcsúcs egy-egy, a csúcsoknál megadott Csúcscimke, az élsúly pedig egy valós szám. Megjegyzés: Hurokélt nem lehet megadni. Példa: #beallitasok ellistas sulyozott csucscimkezett iranyitott #csucslista ## cimke x koordináta y koordináta S 135 182 A 314 172 C 139 312 B 319 300 #ellista ## kezdőcsúcs végcsúcs élsúly S A 7 S C 3 A B 2

11

5.

Gráf generálás Lehetőség van véletlen gráf generálására megadott csúcsszám, két csúcs közötti élvalószínűség megadása alapján. Csúcsok száma: 1 és 200 között lehet. Valószínűség csúcs

között

valószínűséggel

mező:

Két

mekkora legyen

él.

Két tizedesjegy pontossággal lehet megadni az értékét. Véletlen élsúlyok: ha be van jelölve, az alatta lévő értékek közötti véletlen élsúlyokat generál, különben az élsúly minden élen 1 lesz. Az élsúly -1000 és 1000 közötti egész szám lehet. 6.

Élsúly intervallum megadása Amennyiben a „Véletlen élsúly” be van jelölve, az ebben az ablakban beállított intervallumból választ a program az új élnek élsúlyt. Az élsúly -100 és 100 közötti egész szám lehet.

Algoritmusok Algoritmust futtathatunk folyamatosan az „Animálás” mező bejelölésével, lépésenként a „Lépésenként” mező bejelölésével, és háttérben az „Animálás” és a „Lépésenként” mezők üresen hagyásával. Ilyenkor egyből a végeredmény jelenik meg. Ha az „Animálás” és a „Lépésenként” is be van jelölve, az algoritmus lépésenként fog futni. Ha az „Animálás” mező be van jelölve, az algoritmus futása közben lehet váltani a lépésenkénti és a folyamatos futás között a „Lépésenként” mező ki-, illetve bekapcsolásával. A folyamatos futás a „Szünet” gombbal szüneteltethető, majd a „Folytat” gombbal folytatható. Lépésenkénti futás esetén a „->” gombbal lehet az

12

algoritmus következő lépésére lépni. Lehetőség van visszalépni az algoritmusban a „<-” gombbal. Folyamatos futás esetén a futási sebesség a Sebesség csúszkával állítható. Az algoritmus futását befejezni, és visszatérni a gráf szerkesztéséhez a „Stop” gombbal lehet. 1.

Szélességi bejárás „Adott

G

=

(V,

E)

irányított vagy irányítatlan gráf és egy kitüntetett s kezdő

csúcs

szélességi

esetén

a

keresés

módszeresen megvizsgálja G éleit, és így „rátalál" minden

s-ből

csúcsra.

Kiszámítja

elérhető az

elérhető csúcsok távolságát (legkevesebb él) s-től. Létrehoz egy s gyökerű „szélességi fát", amely tartalmazza az összes elérhető csúcsot. A szélességi fában sből v-be vezető út a „legrövidebb" s-ből v-be vezető útnak felel meg G-ben bármely s-ből elérhető v csúcsra. Legrövidebb útnak most a legkevesebb élből álló utat nevezzük. Az algoritmus egyaránt alkalmazható irányított vagy irányítatlan gráfok esetén. A szélességi keresés elnevezés onnan ered, hogy az algoritmus a már elért és a még felfedezetlen csúcsok közötti határvonalat egyenletesen terjeszti ki a határ teljes széltében. Az algoritmus eljut az összes olyan csúcsba, amely s-től k távolságra van, mielőtt egy k + 1 távolságra levő csúcsot elérne. Az algoritmus a bejárás pillanatnyi állapotát a csúcsok fehér, szürke, illetve fekete színezésével tartja számon. Kezdetben minden csúcs fehér, és később szürkére, majd feketére változhat. Egy csúcs elértté válik, amikor először rátalálunk a keresés során, és ezután a színe nem lehet fehér. Így a szürke és fekete csúcsok már elért csúcsok, de a szélességi keresés megkülönbözteti ezeket is, hogy a keresés jellege szélességi maradjon. Ha (u, v)  E és u fekete, akkor v fekete vagy szürke lehet; azaz, egy fekete csúcs összes szomszédja elért csúcs. A szürke csúcsoknak lehetnek

13

fehér szomszédjaik; ezek alkotják az elért és még felfedezetlen csúcsok közötti határt.” [1] Az algoritmus futtatása előtt ki kell jelölni egy kezdőcsúcsot, amiből az algoritmus elindul. Az algoritmus nem veszi figyelembe az élsúlyokat, ezért a futás előtt a gráfot átalakítja élsúlyozatlanná. Futás közben az elért csúcsok kezdőcsúcstól való távolsága az adott csúcshoz vezető élen látható. 2.

Dijkstra algoritmus A

Dijkstra

algoritmus

legrövidebb utakat keres egy

adott

csúcsból

kiindulva minden más csúcsba. A gráfnak nem lehet negatív élsúlya. Két pont közötti út költsége az

úton

lévő

élek

súlyának összege. Az algoritmus a bejárás pillanatnyi állapotát a csúcsok fehér, szürke, illetve fekete színezésével tartja számon. Kezdetben minden csúcs fehér, és később szürkére, majd feketére változhat. Az algoritmus minden lépésben a legkisebb legrövidebb-út becslésű u  V fehér csúcsot választja ki, u-t feketére festi, és minden u-ból kivezető éllel egy-egy közelítést végez. Egy Q minimum-elsőbbségi sorral tartja nyilván a nem fekete csúcsokat, amelyek azok d értékeivel vannak indexelve. A Dijkstra-algoritmus mohó stratégiát alkalmaz, hiszen mindig a „legkönnyebb”, a „legközelebbi” csúcsot választja ki a fehér csúcsok közül, hogy azután feketére színezze. [1] Az algoritmus futtatása előtt ki kell jelölni egy kezdőcsúcsot, amiből az algoritmus elindul. Amennyiben negatív élsúlyt tartalmaz a gráf, az algoritmus nem indul el. Futás közben az elért csúcsokhoz vezető éleken a kezdőcsúcsból az adott csúcsba vezető út költsége látható.

14

3.

Bellmann-Ford algoritmus „A Bellman-Ford-algoritmus az adott kezdőcsúcsból induló legrövidebb utak problémáját abban az általánosabb esetben oldja meg, amikor az élek között negatív súlyúakat is találhatunk.

Adott

egy

w:E→R súlyfüggvénnyel súlyozott irányított G = (V,

E)

gráf,

kezdőcsúcs

az

ahol

a

s.

A

Bellman-Ford-algoritmus egy logikai értéket ad vissza annak jelölésére, hogy van vagy nincs a kezdőcsúcsból elérhető negatív kör. Ha van ilyen kör, az algoritmus jelzi, hogy nem létezik megoldás. Ha nincs ilyen kör, akkor az algoritmus előállítja a legrövidebb utakat és azok súlyait. A Bellman-Ford-algoritmus a fokozatos közelítés technikáját alkalmazza, bármelyik v  V csúcsnál az s kezdőcsúcsból odavezető legrövidebb út súlyára adott d[v] becslését ismételten csökkenti mindaddig, amíg az eléri annak tényleges δ(s,v) értéket. Az algoritmus akkor és csak akkor tér vissza

IGAZ

értékkel, ha a gráf nem tartalmaz a kezdőcsúcsból elérhető negatív köröket.” [1] Az algoritmus futtatása előtt ki kell jelölni egy kezdőcsúcsot, amiből az algoritmus elindul. A csúcsok színe kezdetben fehér, az elért csúcs szürke, az adott csúcshoz tartozó iterációs ciklus végén fekete. Negatív összsúlyú kör esetén az algoritmus futása után figyelmeztet. Futás közben az elért csúcsokhoz vezető éleken a kezdőcsúcsból az adott csúcsba vezető út költsége látható. 4.

Prim algoritmus „A Prim-algoritmus működése nagyon hasonlít Dijkstra legrövidebb utakat kereső algoritmusáéhoz. Prim algoritmusában a bejárt élek mindig egyetlen fát formáznak. […] A fa építése egy tetszőlegesen kiválasztott r gyökérpontból indul, és addig növekszik, amíg a V összes csúcsa nem kerül be a fába. Minden lépésben azt a könnyű élt vesszük hozzá a fához, amelyik egy fabeli és egy fán kívüli csúcsot köt össze. […] Amikor az algoritmus befejeződik a bejárt élek minimális feszítőfát alkotnak. Ez a stratégia mohó, mivel minden lépésben egy 15

olyan éllel bővíti a fát, amely a lehető legkisebb mértékben növeli a fa teljes súlyát. […] A fában még nem szereplő csúcsok a végrehajtás közben egy kulcs értéken alapuló Q elsőbbségi sorban helyezkednek el. A d[v] valamelyik fabeli csúccsal összekötő minimális súlyú él súlya; amennyiben nincs

ilyen

él,

akkor

megállapodás szerint d[v] = ∞. A π[v] érték a v csúcs fabeli szülőjét

adja

Amikor

az

meg.

[…]

algoritmus

befejeződik, a Q elsőbbségi sor üres.” [1] Az algoritmus futtatása előtt ki kell jelölni egy kezdőcsúcsot, amiből az algoritmus elindul. Kezdetben az összes csúcsot fehérre színezi, egy csúcs szürkére változik, ha bekerül a fába, feketére, ha az összes szomszédja a fában van. Futást közben az elért csúcsokhoz vezető éleken az adott csúcsba vezető él súlya látható. 5.

Warshall-Floyd algoritmus „Adott

egy

élsúlyozott, irányítás

G=(V,E)

irányított nélküli,

összköltségű

vagy negatív

irányított

kört

nem tartalmazó véges gráf. Minden u, v  V csúcsra, uból

v-be

vezető

legkisebb

költségű utat határozza meg. Legyen egy p  v1 , v 2 ,..., v m egyszerű út belső csúcsa p minden v1-től és vm-től különböző csúcsa, azaz v 2 ,..., v m 1  halmaz elemei.

16

n iterációs lépés után kapjuk meg a megoldást, mely iterációs lépések során folyamatosan fenntartjuk a D(k) mátrixunkra a következő invariáns tulajdonságot: a k-adik iteráció lefutása után (i, j ) csúcspárra D(k)[i,j] azon i ~ j utak legrövidebbjeinek a hosszát tartalmazza, amelyek közbülső csúcsai k-nál nem nagyobb sorszámúak. Tehát k=n esetén (i, j ) csúcspárra D(n)[i,j] az i ~ j utak legrövidebbjeinek a hosszát, azaz a feladat megoldását tartalmazza. Az algoritmus n iterációs lépésben, az n2-es mátrix minden elemére konstans számú műveletet végez, így T (n)  (n 3 ) . Ez egy stabil algoritmus, mivel legjobb, legrosszabb és átlagos esetben is azonos a műveletigénye. Tranzitív lezárt: A gráf egy u pontjából el tudunk-e jutni egy v pontjába, azaz létezik-e út u-ból v-be.” [2] „A Floyd-Warshall-algoritmussal megegyezően a futási idő Θ(n3) lesz. A gyakorlatban azonban sok esetben gyorsabban hajtódnak végre az egyetlen bites adatokon vett logikai műveletek, mint az egész számokon végzett aritmetikai műveletek. További előny a tranzitív lezárt közvetlen keresésekor, hogy az egész értékek helyett csak logikai értékeket kell tárolni. Így a tárigény a FloydWarshall-algoritmushoz képest annyiszor kisebb, amennyi bitet számítógépünk egy egész szám tárolására használ.” [1] Az algoritmus futtatása előtt nem szükséges kezdőcsúcsot kijelölni. Kezdetben az algoritmus az összes csúcs színét fehérre állítja. Az aktuális iterációs ciklusban vizsgált közbülső csúcs színe szürke, ha talál utat az algoritmus ezen keresztül két csúcs között, akkor ezen csúcsok színe fekete lesz, köztük az él pedig kiemelésre kerül. Ha negatív összsúlyú kört talál az algoritmus, akkor leáll. Az algoritmus befejeződése után egy csúcsra kattintva a csúcsból elérhető csúcsokhoz tartozó legkisebb költségű utak láthatóak.

17

Fejlesztői dokumentáció 1.

Használati esetek

1.1

Gráf szerkesztése

1.2



Új csúcs, él rajzolása



Csúcs, él kijelölése



Csúcs, él törlése



Csúcs címkéjének módosítása



Él súlyának módosítása



Csúcs mozgatása



Csúcs méretének beállítása



Gráf irányítottságának beállítása



Gráf súlyozottságának beállítása



Csúcscímkézettség beállítása



Mátrixos, illetve éllistás tárolás beállítása

Algoritmusok szemléltetése 

Algoritmus futtatása



„Animált”, „Lépésenkénti” végrehajtás esetén az aktuális lépés megjelenítése

 1.3 1.3.1

Eredmény kirajzolása

Kiegészítő funkciók Algoritmus vezérlők: 

Szemléltetés módjának kiválasztása (csak az eredmény, animált, lépésenként)



Algoritmus kiválasztása



Algoritmus sebességének beállítása „Animált” esetben



Algoritmushoz

használt

tömbök,

mátrixok,

sorok,

magyarázat

megjelenítésének be- illetve kikapcsolása

18

1.3.2

1.3.3

Tárolás: 

Gráf mentése



Gráf betöltése



Gráf mentése szövegfájlba



Gráf betöltése szövegfájlból



Új gráf készítése

Beállítások: 

Ablak

átméretezésnél

a

gráf

átméretezésének

tiltása,

illetve

engedélyezése 

Gráf generálása



Új él rajzolásánál véletlen élsúly generálása



Véletlen élsúly intervallumának beállítása



„Ábrázolás” és „Tömb ábrázolás” ablakok mindig előtérben legyenek-e

1.3.4

Segítség a program használatához

1.3.5

Kilépés

2.

Felhasználói felület megjelenési terve A felhasználói felület az Elemi alkalmazások fejlesztése 3. tárgy előadása során ismertetett „Prim algoritmusának demonstrálása” alapján készült [5]. A form két fő részből áll: bal oldalon egy panel helyezkedik el, ahol a gráfot készíthető, jobb oldalon a gráf beállításait végző és az algoritmus kiválasztásához és futtatásához szükséges vezérlők vannak. A státuszsorban lévő szövegek segítik a gráf szerkesztését, valamint az algoritmus futása közben információt adnak az aktuális lépésről.

19

2.1

Vezérlő elemek és kezdeti beállításaik

Név

Funkció

this

Típus

Felirat

GrafAlgoForm Gráf Algoritmusok

panel1

Gráf szerkesztése, algoritmusok

Panel

szemléltetése textBoxSuly

Él súlyának megadása

TextBox

panel2

Gráf beállításai és az algoritmus Panel futási tulajdonságainak beállításához szükséges vezérlők

groupBox3

GroupBox

Algoritmus vezérlők

buttonIndit

Algoritmus indítása (leállítása, ha Button

Indít, (Leállít)

fut) checkBoxLepes Lépésenkénti végrehajtás

CheckBox

Lépésenként

be/kikapcsolása comboBoxAlgo Algoritmus választása

ComboBox

ritmus

20

buttonSzunet

Animált futás szüneteltetése,

Button

Szünet, (Folytat)

Button

<-

Button

->

checkBoxAnim Animált futás bekapcsolása

CheckBox

Animálás

trackBar1

TrackBar

folytatása buttonElozo

Lépésenkénti futás esetén az előző állapotra visszalépés

buttonKov

Lépésenkénti futás esetén a következő állapotra lépés

sebességcsúszka

checkBoxTomb Tömb ábrázolás bekapcsolása

CheckBox

Abr

mutatása

checkBoxAbraz Ábrázolás ablak bekapcsolása

CheckBox

olasBe

Ábrázolás mutatása

groupBox4 trackBarCsucs

Tömbök

GroupBox csúcs méretének beállítása

TrackBar

csúcs méretének beállítása

TextBox

Csúcsméret

meret textBoxCsM groupBox2

GroupBox

Ábrázolás

radioMatrix

Gráf mátrixos ábrázolása

RadioButton

Mátrixos

radioEllista

Gráf éllistás ábrázolása

RadioButton

Éllistás

GroupBox

Gráftípus

groupBox1 radioIr

Irányított gráf

RadioButton

Irányított

radioIrtatlan

Irányítatlan gráf

RadioButton

Irányítatlan

CheckBox

Élsúlyozott

Csúcscímkézés bekapcsolása

CheckBox

Csúcscímke

menuStrip1

Menüsor

MenuStrip

fájlToolStrip

Fájl menü

ToolStripMen Fájl

checkBoxElSul Élsúlyozás bekapcsolása y checkBoxCsCi mke

MenuItem

uItem

újToolStripMen menü

ToolStripMenu Új

uItem

Item

21

mentésToolStri menü

ToolStripMenu Mentés

pMenuItem

Item

megnyitásTool

menü

ToolStripMenu Megnyitás

StripMenuItem

Item

gráfExportálása menü

ToolStripMenu Gráf exportálása

ToolStripMenu

Item

Item gráfImportálása menü

ToolStripMenu Gráf importálása

ToolStripMenu

Item

Item KilépésToolStri menü

ToolStripMenu Kilépés

pMenuItem

Item

BeallitsoktoolS Beállítások menü

ToolStripMen Beállítások

tripMenuItem

uItem

1 AtmereteztoolS Gráf ablakkal méretezésének

ToolStripMenu Ne méretezze át

tripMenuItem

beállítása

Item

grafgeneralasT

Gráf generálása

ToolStripMenu Gráf generálás

oolStripMenuIt

a gráfot

Item

em veletlenElsulyT Véletlen élsúlyok generálása

ToolStripMenu Véletlen élsúly

oolStripMenuIt

Item

em élsúlyIntervallu Véletlen élsúlyok

ToolStripMenu Élsúly

mMegadásaToo intervallumának megadása

Item

lStripMenuItem

intervallum megadása

toolStripMenuIt Ábrázolás ablak mindig látható

ToolStripMenu Ábrázolás

em1

Item

legyen

mindig felül

toolStripMenuIt Tömb ábrázolás ablak mindig

ToolStripMenu Tömb ábrázolás

em2

Item

látható legyen

mindig felül

segítségToolSt Súgó állomány megnyitása

ToolStripMen Segítség

ripMenuItem

uItem

statusStrip1

Státuszsor

statusStrip

22

StatusLabel 2.2

Segítő feliratok megjelenítése

StatusLabel

Gráf szerkesztése Gráf szerkesztése az Elemi alkalmazások fejlesztése 3. tárgy előadása során ismertetett „Prim algoritmusának demonstrálása” alapján készült [5]. Gráf szerkesztéséhez egy saját felsorolási típus bevezetése: Statusz: alap, csucsKijelol, elKijelol, elRajzol, csucsMozgat Gráf szerkesztése közben az aktuális állapot egy Statusz típusú „állapot” változó és az egér állapotának segítségével van számon tartva. Ezek alapján lehet meghatározni, hogy milyen műveletet kell végrehajtani a gráfon. Állapotok: 

alap: a gráf alaphelyzetben van, nincs kijelölve sem éle, sem csúcsa, egérgombok nincsenek lenyomva. Jobb egérgombbal nem csúcsra kattintva a szerkesztés ebbe az állapotba kerül.



csucsKijelol: bal egérgomb lenyomva és elengedve egy csúcson. A kijelölt csúcs piros. „Indít” gomb elérhető. „Insert” gomb lenyomása után csúcscimke egy textboxban szerkeszthető. Szerkesztés az „Enter” lenyomásával fejezhető be.



elKijelol: bal egérgomb lenyomva és elengedve egy élen. A kijelölt él piros.

„Insert”

gomb

lenyomása

után

élsúly

egy

textboxban

szerkeszthető. Szerkesztés az „Enter” lenyomásával fejezhető be. 

elRajzol: bal egérgomb lenyomva és egér mozog. A lenyomás helyének pozíciója és az aktuális pozíció eltér. Egérgomb elengedése után az él súlya szerkeszthető. Szerkesztés az „Enter” lenyomásával fejezhető be.



csucsMozgat: jobb egérgomb lenyomása csúcs felett. Egér mozgatásával a csúcs mozgatható. Csúcs új pozíciója, ahol az egérgomb elengedve.

23

Gráf, algoritmus beállításaink használati esetei:  buttonIndit_Click: algoritmus elindítása  checkBoxLepes_CheckedChanged: algoritmus futásának lépésenkénti beállítása  buttonSzunet_Click: Animált futás szüneteltetése  buttonKov_Click: Lépésenkénti futás léptetése  buttonElozo_Click: Lépésenkénti futás előző lépése  comboBoxAlgoritmus_SelectedIndexChanged:

Ha

a

választott

algoritmus Warshall-Floyd, akkor az „Indít” gomb elérhető csúcskijelölés nélkül is  checkBoxAnim_CheckedChanged: Algoritmus futása animált legyen  trackBar1_Scroll: animált futás sebességének állítása  checkBoxTombAbr_CheckedChanged:

Tömb

ábrázolás

futáskor

látszódjon-e  checkBoxAbrazolasBe_CheckedChanged: Ábrázolás ablak bekapcsolása  trackBarCsucsmeret_Scroll: Csúcs méretének beállítása  textBoxCsM_TextChanged: Csúcs méretének beállítása  radioMatrix_CheckedChanged/radioEllista_CheckedChanged:

a

gráf

éllistás vagy mátrixos tárolású legyen-e

24

 radioIr_CheckedChanged/radioIrtatlan_CheckedChanged: gráf irányított vagy irányítatlan legyen-e  checkBoxElSuly_CheckedChanged: gráf élsúlyozásának beállítása  checkBoxCsCimke_CheckedChanged: Csúcscimkézés beállítása Menüsor használati esetei: 

újToolStripMenuItem_Click: új gráf rajzolása. Ha fut algoritmus, akkor leállítja, ha történt változás a gráfon, akkor rákérdez a mentésére, törli a gráfot alap állapotba áll



mentésToolStripMenuItem_Click: gráf mentése. Ha fut algoritmus, akkor leállítja.



megnyitásToolStripMenuItem_Click:

gráf

megnyitása.

Ha

fut

algoritmus, akkor leállítja, ha történt változás a gráfon, akkor rákérdez a mentésére. Gráf tulajdonságainak beállítás a vezérlőkön. 

kilépésToolStripMenuItem_Click: kilpés a programból. új gráf rajzolása. Ha fut algoritmus, akkor leállítja, ha történt változás a gráfon, akkor rákérdez a mentésére.



gráfExportálásaToolStripMenuItem_Click: gráf exportálása szövegfájlba. Ha fut algoritmus, akkor leállítja.



gráfImportálásaToolStripMenuItem_Click:

egy

gráf

importálása

szövegfájlból. Ha fut algoritmus, akkor leállítja, ha történt változás a gráfon, akkor rákérdez a mentésére. 

AtmereteztoolStripMenuItem_Click:

gráf

ablakkal

együtt

történő

átméretezésének leállítása/engedélyezése 

grafgeneralasToolStripMenuItem_Click: gráf generálásához szükséges ablak megnyitása



veletlenElsulyToolStripMenuItem_Click:

él

rajzolásánál

adott

intervallumból véletlen élsúly választása 

élsúlyIntervallumMegadásaToolStripMenuItem_Click: véletlen élsúly intervallumának beállítására szolgáló ablak megnyitása



toolStripMenuItem1_Click/toolStripMenuItem2_Click: Ábrázolás illetve Tömb ábrázolás ablakok mindig előtérben legyenek-e



segítségToolStripMenuItem_Click: Súgó ablak megnyitása

25

3.

Osztályok A főbb osztályok kapcsolata:

A teljes osztálydiagram:

26

3.1

GrafAlgoForm osztály Program vezérlését végző osztály. Gráf megjelenítését, szerkesztését, algoritmus kiválasztását végzi, kiegészítő funkciók elérését biztosítja a „Felhasználói felület megjelenési terve” fejezetben ismertetettek szerint.

3.1.1

Adattagok: típus

név

leírás

Public: Graf

gr

Gráf

PointF

kezdo

Kezdőcsúcs tárolási pozíciója

PointF

veg

Végcsúcs tárolási pozíciója

PointF

kezdo_r

Kezdőcsúcs rajzolási pozíciója

PointF

veg_r

Végcsúcs rajzolási pozíciója

AlgoKezelo

algo

Algoritmus vezérlése

Abrazolas

abra

Ábrázolás ablak

Private:

TombAbrazolas ta

Tömb ábrázolás ablak

VelElsuly

velelsuly

Véletlen élsúly ablak

AlgoNevek

an

Algoritmus nevek

Szinek

szinek

Gráf ábrázolásához, szerkesztéséhez használt színek

Statusz

allapot

Állapotváltozó a gráf szerkesztéséhez

bool

abrazolas

Ábrázolás ablak látszódjon-e

bool

velsuly

Véletlen élsúlyok legyenek-e élrajzolásnál

bool

dirtyflag

Változott-e a gráf

float

regi_width,

Ablak előző szélessége, magassága

regi_height int

lx, ly

Ablak helye betöltésnél

Random

velszam

Véletlenszám a véletlen élsúlyokhoz

int

minVel, maxVel

Véletlen élsúlyok intervallumának szélei

bool

van_abrazolas

Létezik-e az abra ablak

int

x_kulonbseg_abra abra ablak és főablak x koordinátáinak

27

különbsége int

y_kulonbseg_abra abra ablak és főablak y koordinátáinak különbsége

bool

van_tomb

int

x_kulonbseg_tomb ta ablak és főablak x koordinátáinak

Létezik-e ta ablak különbsége

int

y_kulonbseg_tomb ta ablak és főablak y koordinátáinak különbsége

bool

ta_felul

ta ablak mindig felül van-e

bool

abra_felul

abra ablak mindig felül van-e

bool

algo_fut

Fut-e az algoritmus

int

sebesseg

Algoritmus futásának sebessége

Hashtable

csucs_szotar

Szótár az algoritmusokhoz használt gráf

Hashtable

csucs_szotar2

csúcsainak és a szerkesztési gráf csúcsainak megfeleltetésére.

3.1.2

Metódusok: név

típus

leírás

Private: bool Panelben(int x, int y)

x és y koordinátájú pont panel1-ben van-e.

void ElSulySzerkesztes()

kezdo_r és veg_r pozíciójú csúcsokra illeszkedő él élsúlyának szerkesztése.

void CsucsCimkeSzerkesztes() kezdo_r pozíciójú csúcs címkéjének szerkesztése. void ElSulyMentes(),

Szerkesztett élsúly/csúcscímke elmentése.

CsucsCimkeMentes() Public: void EnabledBeallit(bool l)

Gráf típusát leíró vezérlők elérhetőségét l-re állítja.

void AlgoLeallit()

Leállítja az algoritmust.

void NemKellKezdoCsucs()

AlgoNevek hasonló nevű függvényét hívja meg.

28

3.1.3

void Abrazolo()

abra ábrázoló függvényeit hívja meg.

void HelyValtozas()

abra és ta helyét változtatja.

abra eseménykezelői: név

leírás

abra_Scroll

Ablak ki görgetésénél váltódik ki. Újrarajzolja az ábrázolást.

abra_LocationChanged

Meghívja a Abrazolas_LocationChanged2()-t és újrarajzolja az ábrázolást.

abra_ResizeEnd 3.2

Újrarajzolja az ábrázolást.

Gráf osztály A gráf szerkesztés közben éllistásan van tárolva. Algoritmus szemléltetéséhez a gráfot át kell alakítani egyszerűbb éllistás, illetve mátrixos szerkezetűre. A gráf csúcsai egy ArrayList-ben vannak tárolva Csucs típusú objektumokként. Az élek a csúcsok elek ArrayList-jében El típusú objektumokként vannak tárolva.

3.2.1

Adattagok: láthatóság public

típus

név

ArrayList Csucslista

leírás Csucs típusú objektumokban tárolja a gráf csúcsait

public

int

csucsazon

Csúcsok belső azonosítója, minden új csúcs készítésénél 1-gyel nő az értéke.

public

int

csucsmeret

Csúcs sugarának a mérete pixelben.

public

int

elvastagsag

Él vastagsága pixelben.

private

float

k_szelesseg

Konstans értékek. Ebben a méretben

private

float

k_magassag

tárolja a program a gráfot. Ez alapján számolja ki a csúcsok megjelenítéséhez szükséges koordinátákat.

public

bool

ellistas

Gráf éllistás-e

public

bool

sulyozott

Gráf élsúlyozott-e

public

bool

iranyitott

Gráf irányított-e

29

public

bool

csucscimkezett Gráf csúcscímkézett-e

public

bool

atmeretez

Átméretezésnél a gráfot kell-e a panelhez méretezni

private 3.2.2

Szinek

szinek

A gráf kirajzolásához használt színek

Publikus metódusok: típus

név

leírás

Graf()

Konstruktor, példányosítja a Csucslistat, és a csucsazon-t 1-re állítja.

void

Torles()

Kiüríti az összes csúcs éllistáját, és a csúcslistát.

bool

UresGraf()

Igazzal tér vissza, ha a gráfnak nincs egy csúcsa sem.

Graf

Iranytalanit()

A gráf irányítatlan párjával tér vissza.

float

getSzelesseg()

Tárolási szélesség lekérdezése.

float

getMagassag()

Tárolási magasság lekérdezése.

string Exportalas()

Gráf átalakítása szöveges formátumra.

bool

Importalas(StreamReader

sr-ben lévő szövegfájlból a szöveges gráfot

sr)

alakítja Graf típusúvá. Igazzal tér vissza, ha az átalakítás hibátlanul lezajlott.

Csúcsműveletek típus bool

név Letezik(int n)

leírás Eldönti, hogy n-nel megegyező cs_szam-ú csúcs létezik-e.

bool

Letezik(Point p)

Eldönti, hogy a p pozíción van-e csúcs

bool

VanEle(int n)

Eldönti, hogy az n csúcsszámú csúcsnak van-e éle.

int

AktCsucs(Point p)

Visszaadja a p pozíciójú csúcs csúcsszámát, hiba esetén -1 a visszatérési érték.

30

Point AktCsucs(int p)

Visszaadja a p csúcsszámú csúcs pozícióját, hiba esetén (-1,-1) a visszatérési érték.

Csucs AktCsucsC(int cs_azon)

Visszaadja a cs_azon azonosítójú csúcsot.

void

CsucsHozzaAd(Point p)

p pozíciójú új csúcs létrehozása, és Csúcslistába pakolása, növeli a csucsazon értékét.

void

CsucsTorles(Point p)

Törli a p pozíciójú csúcsot a csúcslistából, és az éllistákból.

void

CsucsMozgat(Point p, Point q)

p pozíciójú csúcs pozícióját áthelyezi q pozícióra.

string MiaCimkeje(int csucsazon)

Visszaadja a csucsazon csúcsazonosítójú csúcs címkéjét.

void

CimkeModosit(int cs_azon, string Módosítja a cs_azon azonosítójú cimke)

csúcs címkéjét cimke-re Létezést is ellenőriz.

bool int

NincsMegIlyenCimke(int

Igazzal tér vissza, ha cimke címkéjű

cs_azon, string cimke)

csúcs még nem létezik.

CsucsSzamLekerdez()

Csucslista elemszámát adja vissza.

Élműveletek típus bool

név

Leírás

LetezikEl(Point p, Point q) Eldönti, hogy létezik-e a p kezdő és q végpontú él. Vizsgálja, hogy a p és q pozíciójú csúcsok léteznek-e.

bool

LetezikEl(int p, int q)

Eldönti, hogy létezik-e a p kezdő és q végpontú él. Vizsgálja, hogy a p és q azonosítójú csúcsok léteznek-e.

31

bool

LetezikEl(int p, int q, out

Eldönti, hogy létezik-e a p kezdő és q

El talalt_el)

végpontú él. Ha létezik, visszaadja ezt a talalt_el változóban. Vizsgálja, hogy a p és q azonosítójú csúcsok léteznek-e.

void

ElHozzaAd(int kezdo, int

Kezdo csúcshoz hozzáad egy új élt veg

veg, double suly)

végponttal és suly súllyal. Csúcsok létezését ellenőrzi.

void

ElTorles(int kezdo, int veg, Törli a kezdo csúcsból induló veg int suly)

végponttal és suly súllyal rendelkező élt. Csúcsok létezését ellenőrzi.

void

ElTorles(int kezdo, int veg) Törli a kezdo csúcsból induló veg végponttal rendelkező élt. Csúcsok létezését ellenőrzi.

void

ElSulyModosit(int kezdo,

Módosítja a kezdo csúcsból induló veg

int veg, double suly)

végponttal rendelkező él súlyát. Csúcsok létezését ellenőrzi.

double ElSulyLekerdez(int kezdo,

int

Visszaadja a kezdo csúcsból induló veg

int veg)

végponttal rendelkező él súlyát.

ElSzamLekerdez()

Gráf éleinek a számával tér vissza.

Rajzolás, megjelenítés műveletei típus bool

név

leírás

KozeliCsucs(Point p, out

Ha a p pozíció közelében

Csucs talaltcsucs)

csucsmeret távolságnyira van csúcs, akkor igazzal tér vissza, és talaltcsucs-nak beállítja az adott csúcsot.

bool

ponttav(int x, int y, out int z)

x és y távolságát számolja ki. Visszaadja a távolságot a z változóban, visszatérési értéke: kisebb-e a távolság, mint csucsmeret.

32

bool

IlleszkedoEl(Point p, out

Megvizsgálja, hogy a p pont

Point kezdo, out Point veg)

illeszkedik-e egy élre, ha igen, igazzal tér vissza, kezdo és veg-ben visszaadja az él két végpontját.

Point

Vegpont(Point kezdo, Point

Kiszámolja, hogy az él rajzolása

veg, int sugar)

meddig tartson (hol metszi az él a sugar sugarú, veg középpontú körvonalat). Számoláshoz arányokat vizsgál.

Point

Kezdopont(Point kezdo, Point Kiszámolja, hogy az él rajzolása veg, int sugar)

honnan induljon (hol metszi az él a sugar sugarú, kezdo középpontú körvonalat). Számoláshoz arányokat vizsgál.

void

PointF

Rajzolas(Graphics g, float

Gráf kirajzolását végzi. szelesseg

szelesseg, float magassag)

és magassag a panel1 méretei.

Koordinata_tarolt2rajz(PointF Pontot tárolt koordinátáról rajzolási csp, float uw, float uh)

koordinátára számolja. Argumentumában: pont, szélességi és magassági adatok

PointF

Koordinata_rajz2tarolt(PointF Pontot rajzolási koordinátáról tárolási csp, float uw, float uh)

koordinátára számolja. Argumentumában: pont, szélességi és magassági adatok

void

CsucsCimkeBeiras(string s,

s címke beírása (x,y) koordinátájú

Font f, Brush ecset, float x,

csúcsba.

float y, Graphics g) Font PointF

BetumeretValtoztatas(Font

betu méretét állítja át betumeret-

betu, float betumeret)

re.

ElSulyHely(PointF k, PointF

k kezdőpontú, v végpontú él

v, Graphics g, string s, Font f) élsúlyának (s) helyét számolja ki.

33

Transzformálás: típus int

név

leírás

Matrixra_alakit(out double[,] graf, Gráfot algoritmus futásához out Hashtable csucs_szotar, out

alkalmas mátrixos tárolású gráffá

Hashtable csucs_szotar2)

(graf) alakítja. 0-val tér vissza, ha sikerül, 2-vel, ha párhuzamos élt talál.

int

Ellistara_alakit(out List<El>[]

Gráfot algoritmus futásához

graf, out Hashtable csucs_szotar,

alkalmas éllistás tárolású gráffá

out Hashtable csucs_szotar2)

(graf) alakítja. 0-val tér vissza, ha sikerül, 2-vel, ha párhuzamos élt talál.

3.3

Él osztály Gráf egy élét tárolja.

3.3.1

3.3.2

Adattagok: láthatóság

típus

név

leírás

public

int

csucsba

végcsúcs

public

double

suly

él súlya

Publikus metódusok: név El()

leírás Konstruktor, a csucsba-t 0-nak választja, a suly-t 1-re állítja.

El(int cs, double s)

Konstruktor, a csucsba-t cs-nek állítja be, a sulyt s-nek.

34

3.4

Csúcs osztály Gráf egy csúcsát és a csúcsból induló éleket tárolja.

3.4.1

Adattagok: láthatóság

típus

név

leírás

public

int

cs_szam

csúcs belső egyedi azonosítója

public

PointF

p

csúcs koordinátái

public

ArrayList

elek

csúcsból induló élek listája (El típusú objektumokat tárol)

public 3.4.2

string

címke

csúcs címkéje

Publikus metódusok: név

leírás

Csucs()

Konstruktor

Csucs(int cs, PointF q)

Konstruktor, a cs_szam-ot cs-nek állítja be, a koordinátákat q-nak, inicializálja az éllistát, a cimke-t a cs_szam-nak választja.

3.5

Algoritmus osztály Absztrakt osztály. A konkrét algoritmusok ősosztálya.

Az algoritmus aktuális állapotát egy felsorolási típus (Statusz) tartja számon (Jelentősége animált és lépésenkénti futásnál van): 

init: Algoritmus kezdeti inicializálása. Összes csúcs (kivéve a kezdőcsúcs) színét fehérre, távolságát végtelenre, szülőjét nilre állítja (kivéve Warshall-Floyd algoritmusnál).

35



kezdobe: Kezdőcsúcs beállítása (színét szürkére, távolságát 0-ra, szülőjét nilre állítja), sor kezdeti beállítása (ha az algoritmus használ sort).



kivesz: Sort használó algoritmusoknál vizsgálja a sor ürességét, a sorból kivesz egy elemet (Bellmann-Ford és Warshall-Floyd algoritmusoknál más szerepe van: a for ciklus feltételét ellenőrzi).



szomszedok: Az algoritmus lényegi lépései. Az aktuális u csúcs szomszédait vizsgálja végig és végrehajtja az algoritmus magját.



fekete: Az u csúcsot feketére festi. (Warshall-Floyd algoritmus nem használja ezt az állapotot).



vege: Az algoritmus futása befejeződött.

Algoritmusok általános sémája (Kivéve Warshall-Floyd algoritmus):

Az algoritmus minden lépését lementi egy verembe, aminek a segítségével a veremből olvasással egyszerűen lehet visszalépni az algoritmusban. Az algoritmus egy állapotát az egyLepes osztály egy példánya tárolja. 3.5.1

Adattagok:

láthatóság típus

név

leírás

protected

Graf

G

Eredeti gráfra hivatkozik

public

bool

lepesenkent

Algoritmus lépésenként fut-e

public

bool

animalt

Algoritmus animáltan fut-e

public

bool

fut

Fut-e még az algoritmus

public

bool

ellistas

Gráf éllistás vagy mátrixos tárolású-e

36

protected

Graphics

rajzolas

Rajzobjektum, panelre rajzolja az algoritmus lépéseit.

protected

Hashtable

csucs_szotar

Futási csúcsszám - csúcs belső azonosítója megfeleltetése.

protected

Hashtable

csucs_szotar2 Csúcs belső azonosítója - futási csúcsszám megfeleltetése.

public

int

szelesseg

Rajzpanel szélessége

public

int

magassag

Rajzpanel magassága

protected

Color[]

szin

Algoritmusokhoz használt szín tömb

protected

double[]

d

Algoritmusokhoz használt távolság tömb

protected

int[]

szulo

Algoritmusokhoz használt szülőtömb

protected

int

meret

Tömbök mérete (csúcsok darabszáma)

protected

List<El>[]

Adj

Éllistákat tároló tömb. A tömb indexei a csúcsok futási csúcsszámai.

protected

double[,]

C

Szomszédsági mátrix

protected

int

start

Kezdőcsúcs futási csúcsszáma

protected

int

u

Aktuális kezdőcsúcs futási csúcsszáma

public

Timer

idozito

Időzítő az animált futáshoz

protected

Stack<egyLe tortenet

Algoritmus lépéseit tároló verem

pes> protected

int

sebesseg

Animált futás sebessége. (Idozito tick eseményének késleltetése)

protected

TombAbrazo ta

Tömb ábrázolás ablakra hivatkozás.

las protected

Szovegek

sz

Algoritmus magyarázó szövegeit tartalmazó osztály.

protected

Szinek

szinek

Algoritmus által használt színek

protected

Statusz

allapot

Algoritmus aktuális futási állapotát tárolja.

protected

int

szomszedok_i Lépésenkénti és animált futásnál az u csúcs szomszédjának aktuális indexét tárolja. 37

protected

int

sormuvelet

Műveletszámlálás: sorba pakolás, sorból kivétel

protected

int

ertekadas

Műveletszámlálás: kezdeti értékadások, inicializálás, start csúcs beállítása.

protected

int

uresevizsg

Műveletszámlálás: van-e még szomszéd az éllistában.

protected

int

listavizsgalat

Műveletszámlálás: fehér szomszéd értékadásai.

public

int

osszesmuvelet Műveletszámlálás: összes művelet. Értéke mindig nő, amikor az előző műveletszámlálók közül bármelyiknek nő az értéke.

protected

int

nil

nil értéke: int.MaxValue

protected

int

vegtelen

végtelen érték: int.MaxValue

protected

double

dvegtelen

végtelen érték: double.MaxValue

3.5.2

Metódusok:

Public: típus

név

leírás

void

AlgoritmusInit(ref Graf

Algoritmus kezdeti beállításai, példányosítja a

graf, bool l, bool a, bool f, szinek, idozito változókat, tortenet Graphics r, ref Hashtable

vermet, állapotot init-re állítja,

cssz1, ref Hashtable

műveletszámlálókat kinullázza.

cssz2, int sz, int m, int s,

Argumentumban: gráf, lépésenként-e,

ref TombAbrazolas

animált-e, fut-e, rajzobjektum, 2 szótár, panel

tomba, bool ellista)

szélesség, magasság, sebesség, tömb ábrázolás, éllistás-e

void

IdozitoStop()

Leállítja az időzítőt, ha a futás animált.

void

IdozitoStart()

Elindítja az időzítőt, ha a futás animált.

void

IdozitoIntervalModosit(int Beállítja az idozito Interval adattagját nn)

re.

38

string MiaCimkeje(int index)

Visszaadja az index azonosítójú csúcs címkéjét.

virtual Verembe()

Verembe teszi az algoritmus aktuális állapotát

void virtual LephetekMegVissza()

Lépésenkénti futás esetén lehet-e még

bool

visszalépni az algoritmusban.

bool

LephetekMegElore()

Lépésenkénti futás esetén lehet-e még előre lépni az algoritmusban.

Protected: típus

név

leírás

virtual void

NemOsszefuggoGraf()

Gráf összefüggőségét vizsgálja.

double

Elsuly(int u, int v)

Visszaadja az u és v csúcs közti él súlyát. Ha nincs él, végtelennel tér vissza (double.MaxValue).

Rajzolás függvényei (public) típus

név

leírás

void

CsucsFestes(int u, Color cs_szin) cs_szin színűre festi a panelen az u csúcsot.

virtual void ElRajzolas(int u, int v)

u és v csúcsok között zöld élt rajzol a

void

panelre.

virtual void ElRajzolas(int u, int v,

c színűre festi az u és v közötti élt a

void

panelen.

Color c)

virtual void ElsulyLefed(int u, int v,

c színű téglalapot rajzol az u és v közti

void

él élsúlyára a panelen.

Color c)

virtual Kirajzol()

Kirajzolja a panelre az algoritmus

void

eddigi lépéseit.

void

setRajzolas(Graphics g)

Beállítja a rajzolas objektumot.

39

Éllistás algoritmus függvényei (public) típus

név

leírás

void

Ellista_Folyamatos(ref List<El>[]

Folyamatos futás esetén (nem

Adj, int start)

lépésenkénti) elindítja az algoritmust start kezdőcsúccsal (animált futásnál az időzítőt, teljes futásnál lefuttatja a teljes algoritmust).

abstract Ellista_teljes(ref List<El>[] Adj,

Algoritmus teljes lefutása start

void

int start)

kezdőcsúccsal.

void

Ellista_Lepesenkent(ref List<El>[] Lépésenkénti futás esetén elindítja Adj, int start)

az algoritmust start kezdőcsúccsal.

virtual

Ellista_KovetkezoLepes()

Lépésenkénti és animált futást

void

koordinálja.

Éllistás algoritmus függvényei (protected) típus

név

leírás

virtual Ellista_idozito_Tick(object Idozito eseménykezelője. void

sender, EventArgs e)

Ellista_KovetkezoLepes()-t hívja meg.

virtual Ellista_Kivesz()

Beállítja u értékét.

void void

Ellista_Szomszedok(El e)

Az u csúcsból induló e élre végrehajtja az algoritmus magját.

virtual Ellista_Fekete()

u csúcsot feketére színezi.

void virtual Ellista_eloInit(ref

Az algoritmus kezdeti beállításait végzi el

void

(meret, szin, d, szulo tömbök

List<El>[] Adj, int start)

kezdőértékeinek beállítása).

40

Mátrixos algoritmus függvényei (public) típus

név

leírás

void

Matrix_Folyamatos(ref double[,] Folyamatos futás esetén (nem C, int start)

lépésenkénti) elindítja az algoritmust start kezdőcsúccsal (animált futásnál az időzítőt, teljes futásnál lefuttatja a teljes algoritmust).

abstract Matrix_teljes(ref double[,] C, int

Algoritmus teljes lefutása start

void

start)

kezdőcsúccsal.

void

Matrix_Lepesenkent(ref

Lépésenkénti futás esetén elindítja az

double[,] C, int start)

algoritmust start kezdőcsúccsal.

Matrix_KovetkezoLepes()

Lépésenkénti és animált futást

virtual void

koordinálja.

Mátrixos algoritmus függvényei (protected) típus

név

leírás

virtual Matrix_idozito_Tick(object Idozito eseménykezelője. void

sender, EventArgs e)

Matrix_KovetkezoLepes()-t hívja meg.

void

Matrix_Kivesz()

void

Matrix_Szomszedok(int v) Gráf mátrixának (u,v) indexű elemére

Beállítja u értékét. végrehajtja az algoritmus magját.

virtual Matrix_Fekete()

u csúcsot feketére színezi.

void virtual Matrix_eloInit(ref

Az algoritmus kezdeti beállításait végzi el

void

(meret, szin, d, szulo tömbök

double[,] C, int start)

kezdőértékeinek beállítása).

41

Éllistás és mátrixos algoritmus közös függvényei (public) típus

név

leírás

virtual void ElozoLepes()

Lépésenkénti futás esetén a visszalépést végzi el a tortenet veremben lévő utolsó állapot alapján.

virtual void Muveletigeny()

Az algoritmus műveletigényét írja ki.

Éllistás és mátrixos algoritmus közös függvényei (protected) típus

név

leírás

void

Init(int u)

Csúcs kezdeti beállításai. u csúcsot fehérre színezi, távolságtömbbeli értékét végtelenre, szülőjét nilnek választja, ha nem kezdőcsúcs.

virtual Kezdo()

Kezdőcsúcsot szürkére állítja, távolságtömbbeli értékét 0-nak,

void

szülőjét nilnek választja.

Absztrakt algoritmus függvények (protected) típus

név

leírás

abstract Urese()

A sor ürességét ellenőrzi (Bellman-Ford

bool

algoritmusnál for ciklus feltételét).

abstract SorInit()

Sor inicializálása (ha használ az algoritmus

void

sort).

abstract Sorbatesz(int n)

Elvégzi a soron a szükséges műveletet az

void

algoritmus magjának végén (ha használ sort az algoritmus). Argumentum: csúcs azonosító.

abstract SorKezdoAllapot(int

Sor kezdőállapotának beállítása (ha használ

void

sort az algoritmus). Argumentum: kezdőcsúcs

start)

azonosítója. abstract SorbolKivesz()

Kiveszi a következő elemet a sorból (sort

int

használó algoritmusnál).

abstract SorUjraFeltolt(ArrayList Sort kiüríti és újra feltölti elemekkel. void

AL)

Argumentum: ArrayList, ami sorrá lesz alakítva.

42

abstract Feltetel(int u, int v)

Algoritmus magjának feltételét vizsgálja

bool

éllistás tárolás esetén. Paraméterek: két szomszédos csúcs azonosítója.

abstract DUjErtek(int u, int v)

Új távolság érték beállítása. Paraméterek: két

void

szomszédos csúcs azonosítója.

abstract MFeltetel(int u, int v)

Algoritmus magjának feltételét vizsgálja

bool

mátrixos tárolás esetén. Paraméterek: két csúcs azonosítója.

abstract MVanel(int u, int v)

Megvizsgálja, hogy van-e él az u és v csúcsok

bool

között.

abstract VeremSorbaTesz(ref

tortenet verem számára átalakítja a sort.

void

Argumentum: sor, ami a tortenet verembe

ArrayList sor)

kerül. abstract Sormuveletpp()

sormuvelet értékét növeli.

void

3.5.3

Ellista_KovetkezoLepes() és Matrix_KovetkezoLepes() A két függvény nagyon hasonló. Egy if szerkezet leellenőrzi, hogy az algoritmus melyik állapotában van, és ez alapján lép: 

Init állapot: A for ciklust összehasonlítással, és a szomszedok_i változó növelésével valósítja meg. Ha a szomszedok_i kisebb, mint a meret, akkor meghívja a következő csúcsra az Init() függvényt, különben az állapot kezdobe lesz.



Kezdobe állapot: Kezdo() függvényt hívja meg, és átmegy kivesz állapotba.



Kiesz

állapot:

Ha

teljesül

az

Urese()

feltétele,

akkor

az

Ellista_Kivesz()/Matrix_Kivesz() függvényt hívja meg, és az állapotot szomszedok-ra állítja, különben az algoritmus futása a végéhez ért, az állapot vege lesz.

43



Szomszedok állapot: Éllistás futás esetén megvizsgálja, hogy az u csúcshoz tartozó éllistának az összes elemét végignézte-e. Ha még nem, akkor a következő szomszédra meghívja az Ellista_Szomszedok() függvényt. Mátrixos futás esetén azt vizsgálja, hogy a mátrix u-hoz tartozó során végigért-e mát. Ha még nem, akkor a következő oszlopra meghívja a Matrix_Szomszedok() függvényt. Ha nem teljesülnek a feltételek, az állapot fekete lesz.



Fekete

állapot:

Meghívja

az

Ellista_Fekete()

/Matrix_Fekete() függvényt, és átmegy kivesz állapotba. 

Vege állapot: Ha animált a futás, leállítja idozito-t. Gráf összefüggőséget ellenőriz, kiírja a műveletigényt, tájékoztat az algoritmus befejeződéséről, és a fut változó értéke hamis lesz.

3.6

egyLepes osztály Az algoritmus egy lépésének tárolását végző osztály.

3.6.1

Publikus adattagok: típus

név

ArrayList elek

leírás Éleket tartalmazó lista. Minden élt bejartEl típusú objektumként tartalmazza.

double[]

d

Távolságtömb

int[]

szulo

Szülőtömb

Color[]

szin

Színtömb

ArrayList Q

Q sor tárolása

ArrayList szovegek

Magyarázó szövegek tárolása.

string

allapot

Algoritmus állapotát tárolja.

int

sormuvelet

Műveletszámlálások aktuális értékeinek tárolása.

int

ertekadas

int

uresevizsg

int

listavizsgalat

int

osszesmuvelet

int

szomszedok_i Lépésenkénti és animált futásnál az u csúcs szomszédjának aktuális indexét tárolja.

44

int

u

Aktuális u csúcs tárolása.

bool

fut

Algoritmus fut változójának tárolása.

3.6.2

Konstruktor: egyLepes(double[] tav, int[] pi, Color[] c, ArrayList sor, ref ListBox lista, string a, int s, int e, int u, int l, int o, int sz, int uu, int nil, bool f)

3.7



double[] tav: Algoritmus távolság tömbje



int[] pi: Algoritmus szülő tömbje



Color[] c: Algoritmus szín tömbje



ArrayList sor: Algoritmus sorát tartalmazza



ref ListBox lista: Magyarázó szövegeket tartalmazó ListBox



string a: Algoritmus aktuális állapota szöveges formában



int s: Algoritmus sormuvelet változója



int e: Algoritmus ertekadas változója



int u: Algoritmus uresevizsg változója



int l: Algoritmus listavizsgalat változója



int o: Algoritmus osszesmuvelet változója



int sz: Algoritmus szomszedok_i változója



int uu: Algoritmus u változója



int nil: Algoritmus nil értéke



bool f: Algoritmus fut változója

bejartEl struktúra Egy bejárt élt tárol a kezdő és végcsúcs azonosítójával. Az egyLepes osztály elek ArrayList-je bejartEl objektumokban tárolja az algoritmus által már elért éleket.

3.7.1

Publikus adattagok: 

int kezdo: kezdőcsúcs csúcsazonosítója



int veg: végcsúcs csúcsazonosítója

45

3.8

Szövegek osztály: Az algoritmusok magyarázó szövegeit tartalmazó osztály. Adattagjai és metódusai egy-egy string típusú mondat, vagy mondattöredék. A konkrét algoritmusok Szövegek osztályai ebből az osztályból származnak. A konkrét algoritmusokhoz tartozó Szovegek osztály az egyes algoritmusokhoz formálja a szöveget néhány függvény felülírásával, változók értékének megváltoztatásával.

3.8.1

Publikus adattagok és metódusok: név

leírás

init

Inicializálás magyarázata.

kezdocs

Kezdőcsúcs beállításának magyarázata.

vege

Az algoritmus befejeződéséről tájékoztat.

negkor

Hibaüzenet, ha a gráf negatív kört tartalmaz.

Sorinit(string start)

Sor inicializálásánál megjelenő magyarázó szöveg. Argumentuma a kezdőcsúcs címkéje.

Sorkivesz(string csucs)

Sorból kivételt magyarázó mondat. Argumentumában annak a csúcsnak a címkéje, amit kivesz az algoritmus a sorból.

Csucsszomszed(string aktcsucs, string

Szomszéd vizsgálathoz magyarázó

szomszed, string szin)

szöveg.

Csucsszinez(string csucs, string szin)

Csúcs színezéséhez magyarázó szöveg.

46

Nemelertcsucs(string csucs, string szin, Algoritmus új csúcs vizsgálásának double d)

magyarázó szövege. Argumentumában egy csúcs, annak színe és d tömbben lévő értékének szöveges változata van.

Szomszedvizsgal(string csucs, string

Az aktuális u csúcs összes

szin)

szomszédjának vizsgálata utáni magyarázó mondat.

M_Sorkivesz(string csucs)

Sorkivesz mondat mátrixos változata.

M_Csucsszomszed(string aktcsucs,

Csucsszomszed mondat mátrixos

string szomszed, string szin, bool

változata

vanel) M_Szomszedvizsgal(string csucs,

Szomszedvizsgal mondat mátrixos

string szin)

változata

Osszmuvelet(int n)

Műveletszámok kiírása

Sormuvelet(int n) Ertekadas(int n) FeltVizsg(int n) SzomszedVizsg(int n) GrafCsucsSzam(int cs) GrafElSzam(int e) Muveletigeny(int sormuvelet, int

Összes műveletszám kiírása.

ertekadas, int uresevizsg, int

Argumentumában a műveletszámok

listavizsgalat, int osszesmuvelet)

vannak

NemOF(int n)

Gráf nemösszefüggőségéről tájékoztat

3.9

Konkrét algoritmus osztályok A konkrét algoritmusok az Algoritmus osztályból vannak származtatva.

3.9.1

Szélességi bejárás osztály Az éllistás tárolást használó algoritmus az Új algoritmusok könyv [1] alapján készült. A szélességi bejárás egy Q sort használ a futása közben. A sor a csúcsok azonosítóját tárolja.

47

Konstruktora

meghívja

az

Algoritmus

osztály

AlgoritmusInit

függvényét, és az Algoritmus osztály sz Szovegek típusú adattagját Szelessegi_Szovegek típusúként példányosítja. Az osztályban meg kell valósítani az Algoritmus osztály absztrakt metódusait. 3.9.1.1

Adattagok: Queue Q: Egészeket tároló sor

3.9.1.2

Metódusok

típus

név

Leírás

bool Urese()

Visszatérési értéke igaz, ha a Q sor hossza nem 0.

void SorInit()

Q sor példányosítása.

void Sorbatesz(int n)

n csúcsot beteszi a Q sorba.

void SorKezdoAllapot(int

Q sorba beteszi a kezdőcsúcsot (start).

start) int

SorbolKivesz()

Q sorból kiveszi az első elemet.

void SorUjraFeltolt(ArrayList Kiüríti a Q sort, és AL-ban lévő elemeket sorban AL)

beteszi Q-ba. Paraméter: ArrayList, ami sorrá lesz alakítva.

bool Feltetel(int u, int v)

Igazzal tér vissza, ha a v csúcs színe fehér. Paraméterek: két szomszédos csúcs azonosítója.

void DUjErtek(int u, int v)

v új távolságértéke u távolságértéke + 1 lesz. Paraméterek: két szomszédos csúcs azonosítója.

bool MFeltetel(int u, int v)

Igazzal tér vissza, ha van él u és v között, és v színe fehér. Paraméterek: két csúcs azonosítója.

bool MVanel(int u, int v)

Igazzal tér vissza, ha van él u és v között.

void VeremSorbaTesz(ref

Q sort átalakítja ArrayList-té az egyLepes

ArrayList sor)

osztály számára. Argumentum: tortenet verembe kerülő sor.

48

void Sormuveletpp()

Sorba helyezés és kivétel műveletigénye Ο(1), ezért a sormuvelet változó és az osszesmuvelet változó értékét 1-gyel növeli.

void Ellista_teljes(ref

Algoritmus teljes lefutása start kezdőcsúccsal.

List<El>[] Adj, int start) void Matrix_teljes(ref

Algoritmus teljes lefutása start kezdőcsúccsal.

double[,] C, int start)

3.9.1.3

Éllistás algoritmus teljes lefutás 

Kezdeti

beállítások:

Az

algoritmus

először a meret változóban eltárolja az éllista hosszát, majd a szin, d és szulo tömböket

példányosítja

meret

hossznyira, init magyarázatot ír ki a magyarázat ListBox-ba, az állapotot init-re állítja. 

Init

állapot:

különböző

Összes

csúcs

távolságtömbbeli

kezdőcsúcstól

színét értékét

fehérre, végtelenre,

szülőjét nilre állítja. Minden lépésben az ertekadas

változó

értékét

növeli.

A csúcsok kezdeti beállítása után az algoritmus állapota kezdobe lesz. Kezdőcsúcs beállításáról magyarázatot ad az algoritmus. 

Kezdobe állapot: Kezdőcsúcs színét szürkére, távolságát 0-ra, szülőjét nilre állítja.

Az

ertekadas

számláló

értékét

növeli.

Inicializálja a Q sort (példányosítja, és beleteszi a start csúcsot), és magyarázatot ad az inicializálásról. A sormuvelet változó értékét növeli. Lementi a tortenet verembe az aktuális állapotot. Az algoritmus átmegy kivesz állapotba. 

Kivesz állapot: Amíg a Q sorban van elem kiveszi az első elemet a sorból és beteszi az u változóba. Magyarázatot ad, hogy melyik csúcsot vette ki a sorból. Sormuvelet értékét növeli. Végigmegy az u csúcs szomszédain. 49

értékét

Uresvizsg

növeli

a

ciklusmag

minden

lefutása.

Átmegy szomszedok állapotba. 

Szomszedok állapot: A v változó értéke u egy szomszédja lesz. Magyarázatot ad a talált szomszédról. Ha a v csúcsot még nem érte el a bejárás (színe fehér), akkor a színét szürkére, távolságát az u távolságánál eggyel nagyobbra, szülőjét u-ra állítja, és beteszi a Q sorba. Magyarázatot ad a bejárás új elért csúcsáról. és

Sormuvelet

listavizsgalat

értékét

növeli.

Az összes szomszéd vizsgálata után az algoritmus állapota fekete lesz. 

Fekete állapot: u csúcsot feketére színezi, erről magyarázatot is ad, és lementi

a

verembe

az

aktuális

állapotot.

Ha a Q sorban van még elem, kivesz állapotba megy, ha kiürül, kilép a ciklusból, és kirajzolja a szélességi bejárás eredményét, majd átmegy vege állapotba. 

Vege állapot: Ellenőrzi a gráf összefüggőségét, kiírja a bejárás műveletigényét, és tájékoztat az algoritmus befejeződéséről.

3.9.1.4

Mátrixos algoritmus teljes lefutás 

Kezdeti

beállítások:

Az

algoritmus

először a meret változóban eltárolja a csúcsok számát, majd a szin, d és szulo tömböket példányosítja meret hossznyira, init magyarázatot ír ki. Az állapotot init-re állítja. 

Init

állapot:

különböző

Összes

csúcs

távolságtömbbeli

kezdőcsúcstól

színét értékét

fehérre, végtelenre,

szülőjét nilre állítja. Minden lépésben az ertekadas

változó

értékét

növeli.

A csúcsok kezdeti beállítása után az algoritmus állapota kezdobe lesz. Kezdőcsúcs beállításáról magyarázatot ad az algoritmus.

50



Kezdobe állapot: Kezdőcsúcs színét szürkére, távolságát 0-ra, szülőjét nilre állítja. Az ertekadas számláló értékét növeli. Inicializálja a Q sort (példányosítja, és beleteszi a start csúcsot), és magyarázatot ad az inicializálásról. A sormuvelet változó értékét növeli. Lementi a tortenet verembe az aktuális állapotot. Az algoritmus átmegy kivesz állapotba.



Kivesz állapot: Amíg a Q sorban van elem kiveszi az első elemet a sorból és beteszi az u változóba. Magyarázatot ad, hogy melyik csúcsot vette ki a sorból. Sormuvelet értékét növeli. Végigmegy a mátrix u csúcshoz tartozó során. A v változó értéke a mátrix oszlopindexe. Uresvizsg értékét növeli a ciklusmag minden lefutása. Átmegy szomszedok állapotba.



Szomszedok állapot: Magyarázatot ad az u és v csúcs kapcsolatáról, és v színéről. Megvizsgálja, hogy v az u szomszédja-e, és hogy v elért csúcs-e. Ha szomszédok és v először elért csúcs (színe fehér, akkor a színét szürkére, távolságát az u távolságánál eggyel nagyobbra, szülőjét u-ra állítja, és beteszi a Q sorba. Magyarázatot ad a bejárás új elért csúcsáról. Sormuvelet és listavizsgalat értékét növeli. Miután végigért az u során az algoritmus állapota fekete lesz.



Fekete állapot: u csúcsot feketére színezi, erről magyarázatot is ad, és lementi a verembe az aktuális állapotot. Ha a Q sorban van még elem, kivesz állapotba megy, ha kiürül, kilép a ciklusból, és kirajzolja a szélességi bejárás eredményét, majd átmegy vege állapotba.



Vege állapot: Ellenőrzi a gráf összefüggőségét, kiírja a bejárás műveletigényét, és tájékoztat az algoritmus befejeződéséről.

3.9.2

Dijkstra algoritmus osztály Az algoritmus az Algoritmusok és adatszerkezetek tárgy előadása és gyakorlata alapján a szélességi bejárás színezési technikáját felhasználva készült. A Dijkstra algoritmus egy Q minimumválasztó elsőbbségi sort használ futása közben. A sor a csúcsok azonosítóját és távolságát tárolja.

51

Konstruktora

meghívja

az

Algoritmus

osztály

AlgoritmusInit

függvényét, és az Algoritmus osztály sz Szovegek típusú adattagját Dijkstra_Szovegek típusúként példányosítja. Az osztályban meg kell valósítani az Algoritmus osztály absztrakt metódusait. 3.9.2.1

Adattagok: PriorityQueue Q: minimum választó elsőbbségi sor

3.9.2.2

Metódusok

típus

név

bool Urese()

Leírás Visszatérési értéke igaz, ha a Q elsőbbségi sor nem üres.

void SorInit()

Q elsőbbségi sor példányosítása.

void Sorbatesz(int n)

Helyreállítja a Q elsőbbségi sort. Paraméter: csúcs azonosító.

void SorKezdoAllapot(int start)

Q elsőbbségi sort feltölti a csúcsokkal. Növeli sormuvelet értékét. Paraméter: kezdőcsúcs azonosítója.

int

SorbolKivesz()

Q-ból kiveszi a legkisebb költségű elemet.

void SorUjraFeltolt(ArrayList Kiüríti a Q-t, és AL-ban lévő elemeket beteszi QAL) bool Feltetel(int u, int v)

ba. Igazzal tér vissza, ha rövidebb utat talál v-be (u csúcs költsége + u és v közötti él költsége kisebb, mint v csúcs költsége) és a v csúcs színe nem fekete.

void DUjErtek(int u, int v)

v új távolságértéke u távolságértéke + u és v közti él költsége lesz.

bool MFeltetel(int u, int v)

Igazzal tér vissza, ha van él u és v között, és v színe nem fekete és ha rövidebb utat talál v-be un keresztül.

bool MVanel(int u, int v)

Igazzal tér vissza, ha van él u és v között.

52

void VeremSorbaTesz(ref

Q-t átalakítja ArrayList-té az egyLepes

ArrayList sor)

osztály számára.

void Sormuveletpp()

Sorba helyezés műveletigénye Θ(1), a kivételé Θ(n). Ezeket a műveletigényeket a PriorityQueue osztály számolja, ezzel az értékkel növeli a sormuvelet változó és az osszesmuvelet változó értékét.

void NemOsszefuggoGraf()

Ha maradt az algoritmus végén végtelen költséggel elérhető csúcs, akkor a gráf nem összefüggő.

void Ellista_teljes(ref

Algoritmus teljes lefutása.

List<El>[] Adj, int start) void Matrix_teljes(ref

Algoritmus teljes lefutása.

double[,] C, int start) 3.9.2.3

Éllistás algoritmus teljes lefutás 

Kezdeti beállítások, Init állapot: Ugyanaz, mint Szélességi bejárásnál.



Kezdobe állapot: Kezdőcsúcs színét szürkére, távolságát 0-ra, szülőjét nilre állítja. Az ertekadas számláló értékét növeli. Inicializálja a Q elsőbbségi sort (példányosítja, és feltölti a csúcsokkal), és magyarázatot ad az inicializálásról. A sormuvelet változó értékét növeli. Lementi a tortenet verembe az

aktuális

algoritmus

állapotot. átmegy

Az kivesz

állapotba. 

Kivesz állapot: Amíg a Q sorban van elem kiveszi a legkisebb költségű elemet a sorból és beteszi az u változóba. Magyarázatot ad, hogy melyik csúcsot

vette

ki

a

sorból.

Sormuvelet értékét növeli.

53

Végigmegy az u csúcs szomszédain. Uresvizsg értékét növeli a ciklusmag minden lefutása. Átmegy szomszedok állapotba. 

Szomszedok állapot: A v változó értéke u egy szomszédja lesz. Magyarázatot ad a talált szomszédról. Ha a v csúcs még nem fekete és az új út költsége v-be kisebb, mint az aktuális, akkor a színét szürkére, távolságát az új távolságra, szülőjét u-ra állítja, és helyreállítja a Q elsőbbségi sort. Magyarázatot ad a v-be menő új legrövidebb útról. Sormuvelet és listavizsgalat értékét növeli. Az összes szomszéd vizsgálata után az algoritmus állapota fekete lesz.

 3.9.2.4

Fekete, vege állapot: Ugyanaz, mint Szélességi bejárásnál. Mátrixos algoritmus teljes lefutás



Kezdeti beállítások, init állapot: Ugyanaz, mint Szélességi bejárásnál.



Kezdobe állapot: Kezdőcsúcs színét szürkére, távolságát 0-ra, szülőjét nilre állítja. Az ertekadas számláló értékét növeli. Inicializálja a Q elsőbbségi sort (példányosítja, és feltölti a csúcsokkal), és magyarázatot ad az inicializálásról. A sormuvelet változó értékét növeli. Lementi a tortenet verembe az aktuális állapotot. Az algoritmus átmegy kivesz állapotba.



Kivesz állapot: Amíg a Q sorban van elem kiveszi a legkisebb költségű elemet a sorból és beteszi az u változóba.

Magyarázatot

ad,

hogy

melyik csúcsot vette ki a sorból. Sormuvelet

értékét

növeli.

Végigmegy a mátrix u csúcshoz tartozó során. A v változó értéke a mátrix oszlopindexe.

Uresvizsg

értékét

növeli a ciklusmag minden lefutása. Átmegy szomszedok állapotba. 

Szomszedok állapot: Magyarázatot ad

54

az u és v csúcs kapcsolatáról, és v színéről. Ha v az u szomszédja és v még nem fekete és az új út költsége v-be kisebb, mint az aktuális, akkor a színét szürkére, távolságát az új távolságra, szülőjét u-ra állítja, és helyreállítja a Q elsőbbségi sort. Magyarázatot ad a v-be menő új legrövidebb útról. Sormuvelet és listavizsgalat értékét növeli. Miután végigért az u során az algoritmus állapota fekete lesz.  3.9.3

Fekete, vege állapot: Ugyanaz, mint Szélességi bejárásnál. Prim algoritmus osztály

Az algoritmus az Algoritmusok és adatszerkezetek tárgy előadása és gyakorlata alapján a szélességi bejárás színezési technikáját felhasználva készült. A Prim algoritmus egy Q minimumválasztó elsőbbségi sort használ futása közben. A sor a csúcsok azonosítóját és távolságát tárolja. Konstruktora

meghívja

az

Algoritmus

osztály

AlgoritmusInit

függvényét, és az Algoritmus osztály sz Szovegek típusú adattagját Prim_Szovegek típusúként példányosítja. Az osztályban meg kell valósítani az Algoritmus osztály absztrakt metódusait. 3.9.3.1

Adattagok: PriorityQueue Q: minimum választó elsőbbségi sor

3.9.3.2

Metódusok név

típus bool Urese()

Leírás Visszatérési értéke igaz, ha a Q elsőbbségi sor nem üres.

void SorInit()

Q elsőbbségi sor példányosítása.

void Sorbatesz(int n)

Helyreállítja a Q elsőbbségi sort. Paraméter: csúcs azonosító.

void SorKezdoAllapot(int start)

Q elsőbbségi sort feltölti a csúcsokkal. Növeli sormuvelet értékét. Paraméter: kezdőcsúcs azonosítója.

int

SorbolKivesz()

Q-ból kiveszi a legkisebb költségű elemet.

55

void SorUjraFeltolt(ArrayList Kiüríti a Q-t, és AL-ban lévő elemeket beteszi QAL) bool Feltetel(int u, int v)

ba. Igazzal tér vissza, ha u és v csúcs közötti él költsége kisebb, mint v költsége és v színe nem fekete.

void DUjErtek(int u, int v)

v új távolságértéke u és v közti él költsége lesz.

bool MFeltetel(int u, int v)

Igazzal tér vissza, ha van él u és v között, és az él költsége kisebb, mint v költsége, és v színe nem fekete.

bool MVanel(int u, int v)

Igazzal tér vissza, ha van él u és v között.

void VeremSorbaTesz(ref

Q-t átalakítja ArrayList-té az egyLepes

ArrayList sor) void Sormuveletpp()

osztály számára. Sorba helyezés műveletigénye Θ(1), a kivételé Θ(n). Ezeket a műveletigényeket a PriorityQueue osztály számolja, ezzel az értékkel növeli a sormuvelet változó és az osszesmuvelet változó értékét.

void NemOsszefuggoGraf()

Ha maradt az algoritmus végén végtelen költséggel elérhető csúcs, akkor a gráf nem összefüggő.

void Ellista_teljes(ref

Algoritmus teljes lefutása.

List<El>[] Adj, int start) void Matrix_teljes(ref

Algoritmus teljes lefutása.

double[,] C, int start)

56

3.9.3.3

Éllistás algoritmus teljes lefutás 

Kezdeti beállítások, Init állapot: Ugyanaz, mint Szélességi bejárásnál.



Kezdobe, kivesz állapot: Ugyanaz, mint Dijkstra algoritmusnál.



Szomszedok állapot: A v változó értéke u egy szomszédja lesz. Magyarázatot ad a talált szomszédról. Ha a v csúcs még nem fekete és az u és v közti él költsége kisebb, mint v csúcs költségértéke, akkor a színét szürkére,

költségértékét

az

él

költségére, szülőjét u-ra állítja, és helyreállítja a Q elsőbbségi sort. Magyarázatot ad a v-vel történt változásokról.

és

Sormuvelet

listavizsgalat értékét növeli. Az összes szomszéd vizsgálata után az algoritmus állapota fekete lesz.  3.9.3.4

Fekete, vege állapot: Ugyanaz, mint Szélességi bejárásnál. Mátrixos algoritmus teljes lefutás



Kezdeti

beállítások,

init

állapot:

Ugyanaz, mint Szélességi bejárásnál. 

Kezdobe, kivesz állapot: Ugyanaz, mint Dijkstra algoritmusnál.



Szomszedok állapot: Magyarázatot ad az u és v csúcs kapcsolatáról, és v színéről. Ha v az u szomszédja és v még nem fekete és az u és v közti él költsége kisebb, mint v csúcs

költségértéke,

akkor

a

színét

szürkére, költségértékét az él költségére, szülőjét u-ra állítja, és helyreállítja a Q elsőbbségi sort. Magyarázatot ad a v-vel történt változásokról. Sormuvelet és

57

listavizsgalat értékét növeli. Miután végigért az u során az algoritmus állapota fekete lesz.  3.9.4

Fekete, vege állapot: Ugyanaz, mint Szélességi bejárásnál. Bellmann-Ford algoritmus osztály

Az algoritmus az Algoritmusok és adatszerkezetek tárgy előadása és gyakorlata alapján a szélességi bejárás színezési technikáját felhasználva készült. A Bellmann-Ford algoritmus az eddigiekkel ellentétben nem használ sort. Minden iterációs lépésben végigmegy az összes élen. Konstruktora

meghívja

az

Algoritmus

osztály

AlgoritmusInit

függvényét, és az Algoritmus osztály sz Szovegek típusú adattagját Bellmann_Szovegek típusúként példányosítja. Az osztályban meg kell valósítani az Algoritmus osztály absztrakt metódusait. 3.9.4.1

Adattagok: int forindex: iterációs lépés indexváltozója. int uindex: Adj tömb indexváltozója

3.9.4.2

Metódusok

típus

név

bool Urese()

Leírás Ellenőrzi, hogy végigért-e az élek listáján/mátrix összes során, valamint ha szükséges, ellenőrzi a külső for ciklus változóját és lépteti.

void SorInit()

Forindex, uindex és u értékét 0-ra állítja.

int

SorbolKivesz()

void Ellista_Fekete()

Adj tömb indexét/mátrix sorindexét lépteti. Iterációs lépés végén feketére színezi a forindex azonosítójú csúcsot.

bool Feltetel(int u, int v)

Igazzal tér vissza, ha rövidebb utat talál v-be (u csúcs költsége + u és v közötti él költsége kisebb, mint v csúcs költsége) és a v csúcs színe nem fekete.

58

void DUjErtek(int u, int v)

v új távolságértéke u távolságértéke + u és v közti él költsége lesz.

bool MFeltetel(int u, int v)

Igazzal tér vissza, ha van él u és v között, és v színe nem fekete és ha rövidebb utat talál v-be u-n keresztül.

bool MVanel(int u, int v)

Igazzal tér vissza, ha van él u és v között.

void Matrix_Fekete()

Iterációs lépés végén feketére színei a forindex azonosítójú csúcsot

void NemOsszefuggoGraf()

Ha maradt az algoritmus végén végtelen költséggel elérhető csúcs, akkor a gráf nem összefüggő.

bool NegativKorokEllenorzese(ref Ha talál rövidebb utat, akkor tartalmaz List<El>[] Adj, double[] d)

negatív összköltségű kört a gráf, és hamissal

bool NegativKorokEllenorzese(ref tér vissza. double[,] C, double[] d) void Ellista_teljes(ref List<El>[]

Algoritmus teljes lefutása.

Adj, int start) void Matrix_teljes(ref double[,]

Algoritmus teljes lefutása.

C, int start)

3.9.4.3

Éllistás algoritmus teljes lefutás 

Kezdeti beállítások, Init állapot: Ugyanaz, mint Szélességi bejárásnál.



Kezdobe állapot: Kezdőcsúcs színét szürkére, távolságát 0-ra, szülőjét nilre

állítja.

Az

ertekadas

számláló értékét növeli. Lementi a tortenet verembe az aktuális állapotot. Az algoritmus átmegy kivesz állapotba. 

Kivesz

állapot:

Iterációs

lépés

59

csúcsszám-1-szer (meret-1) fut le. Minden iterációs lépés elején tájékoztat, hogy hányadik iterációs lépés következik, majd végigmegy az összes csúcson (két ciklussal: külső for ciklus az Adj tömbön az u változóval, belső foreach az Adj[u]-ban lévő éleken). Uresvizsg értékét minden él növeli. 

Szomszedok állapot: A v változó értéke Adj[u] egy éle lesz. Magyarázatot ad az élről. Ha az u költségértékének és az él költségének összege kisebb, mint v csúcs költségértéke, akkor a színét szürkére, költségértékét az új költségére, szülőjét u-ra állítja. Magyarázatot ad a v-vel történt változásokról. Listavizsgalat értékét növeli. Az összes él vizsgálata után az algoritmus állapota fekete lesz.



Fekete állapot: Ugyanaz, mint Szélességi bejárásnál.



Vege állapot: Összefüggőséget ellenőriz, és lefuttat még egy iterációs lépést ellenőrizni, hogy van-e negatív összköltségű kör a gráfban. Ha talál, hibaüzenetet ír ki. Végén kiírja a műveletigényt, és tájékoztat az algoritmus befejeződéséről.

3.9.4.4

Mátrixos algoritmus teljes lefutás 

Kezdeti beállítások, init állapot: Ugyanaz, mint Szélességi bejárásnál.



Kezdobe

állapot:

Kezdőcsúcs

színét szürkére, távolságát 0-ra, szülőjét

nilre

ertekadas növeli.

állítja.

számláló

Lementi

a

Az értékét

tortenet

verembe az aktuális állapotot. Az algoritmus

átmegy

kivesz

állapotba. 

Kivesz állapot: Minden iterációs lépés

elején

tájékoztat,

hogy

hányadik iterációs lépés következik, majd végigmegy az összes csúcson (két for ciklussal: külső az u változóval, belső a v változóval). Uresvizsg értékét minden lépésben növeli.

60



Szomszedok állapot: Ha van u és v között él és az u költségértékének és az él költségének összege kisebb, mint v csúcs költségértéke, akkor a színét szürkére, költségértékét az új költségére, szülőjét u-ra állítja. Magyarázatot ad a v-vel történt változásokról. Listavizsgalat értékét növeli. A mátrix minden elemének vizsgálata után az algoritmus állapota fekete lesz.



Fekete állapot: Ugyanaz, mint Szélességi bejárásnál.



Vege állapot: Összefüggőséget ellenőriz, és lefuttat még egy iterációs lépést ellenőrizni, hogy van-e negatív összköltségű kör a gráfban. Ha talál, hibaüzenetet ír ki. Végén kiírja a műveletigényt, és tájékoztat az algoritmus befejeződéséről.

3.9.5

Warshall-Floyd algoritmus osztály Az algoritmus az Algoritmusok és adatszerkezetek tárgy előadása és gyakorlata alapján készült. A Warshall-Floyd algoritmus az eddigi algoritmusoktól eltérő szerkezettel rendelkezik. Az algoritmus megelőzési mátrixot és tranzitív lezártat is számol. Az algoritmus egy lépését a WarshallegyLepes osztály egy példánya tárolja. Konstruktora

meghívja

az

Algoritmus

osztály

AlgoritmusInit

függvényét, és az Algoritmus osztály sz Szovegek típusú adattagját Warshall_Szovegek típusúként példányosítja. Az osztályban meg kell valósítani az Algoritmus osztály absztrakt metódusait. 3.9.5.1

Adattagok: típus

név

leírás

double[,]

D

Távolság mátrix

int[,]

P

Megelőzési mátrix

bool[,]

W

Tranzitív lezárt mátrix

Stack<WarshellegyLepes> tortenet2

Történet verem

ArrayList

Azok az élek, amik mentén új

aktelek

61

legrövidebb utat talált.

3.9.5.2

int

szomszedok_j Ciklusváltozó

int

szomszedok_k Ciklusváltozó

Metódusok: név

típus

leírás

void Matrix_KovetkezoLepes() Animált és lépésenkénti futást koordinálja hasonlóképpen, mint az Algoritmusok osztály hasonló függvénye. void Matrix_idozito_Tick(objec Ha az állapot nem vege, meghívja a t sender, EventArgs e)

Matrix_KovetkezoLepes()-t, különben leállítja az algoritmus futását.

void Matrix_eloInit(ref double[,] C, int start) void Init(int i, int j)

Mátrixok, szin tömb, és kezdőcsúcs inicializálása. i csúcs színét fehérre állítja, D mátrixba kezdetben a C mátrix értékeit tölti, P és W mátrix kezdeti beállításai.

void Kezdo()

A szomszedok_k-adik iterációs lépéshez a szomszedok_k csúcsot szürkére állítja.

void Matrix_Szomszedok(int i, int j)

Algoritmus magja. Beállítja a W[i,j] új értékét, ha talál rövidebb utat i és j között, akkor a D és P mátrixot is módosítja.

void ElozoElekLevesz()

Előző lépés színezett csúcsait és éleit visszaszínezi, és üríti az aktelek-et.

void Ellista_KovetkezoLepes()

Éllistás algoritmus futását koordinálja. Nem init állapotokhoz a Matrix_KovetkezoLepes()-t használja.

void Ellista_idozito_Tick(object Ha az állapot nem vege, meghívja az sender, EventArgs e)

Ellista_KovetkezoLepes()-t, különben leállítja az algoritmus futását.

62

void Ellista_eloInit(ref List<El>[] Adj, int start) void Ellista_Init(int i, int j)

Mátrixok, szin tömb, és kezdőcsúcs inicializálása. i csúcs színét fehérre állítja, D mátrixba kezdetben az Adj tömb éllistáinak értékeit tölti, P és W mátrix kezdeti beállításai.

void ElozoLepes()

Lépésenkénti futás esetén a visszalépést végzi el a tortenet2 veremben lévő utolsó állapot alapján.

void Kiir(int i, int j)

i és j csúcs közti utat rajzolja ki a P megelőzési mátrix segítségével.

void AktElek(int i, int j, int k)

aktelek-et feltölti az i és j közti k-n átmenő legrövidebb úttal.

void AktElek(int i, int j)

aktelek-et feltölti az i és j közti legrövidebb úttal.

void LegrovidebbUtakAktCsucs Kirajzolja a csucs-ból induló összes bol(int csucs)

legrövidebb utat.

void ElRajzolas(int u, int v)

Zöld élt rajzol u és v csúcs közé.

void ElRajzolas(int u, int v,

c színű élt rajzol u és v csúcs közé.

Color c) void Kirajzol()

aktelek-ben lévő éleket rajzolja ki, és a csúcsokat színezi

void Kirajzol(Color elszin)

aktelek-ben lévő éleket rajzolja ki elszin színnel és a csúcsokat színezi

void ElKirajzol(Color elszin)

Csak az aktelek-ben lévő éleket rajzolja ki elszin színnel

void ElsulyLefed()

aktelek élsúlyait törli le.

void Verembe()

Verembe teszi az algoritmus aktuális állapotát.

void Muveletigeny()

Az algoritmus műveletigényét írja ki.

bool LephetekMegVissza()

Igazzal tér vissza, ha lépésenkénti futás esetén, lehet még visszalépni az algoritmusban.

63

bool NegativKorVan()

Igazzal tér vissza, ha negatív összköltségű kört talál.

void CMatrixBeallit(ref

Algoritmus C mátrixát állítja be.

double[,] CC) bool Urese()

Visszatérési értéke igaz, ha a szomszedok_i kisebb, mint a csúcsok száma.

bool MFeltetel(int u, int v)

Igazzal tér vissza, ha az u és v csúcsok között a szomszedok_k azonosítójú csúcson átmenő rövidebb utat talál.

void Ellista_teljes(ref

Algoritmus teljes lefutása.

List<El>[] Adj, int start) void Matrix_teljes(ref double[,] Algoritmus teljes lefutása. C, int start) 3.9.5.3

Mátrixos algoritmus teljes lefutás 

Kezdeti beállítások: Beállítja a meret változót, példányosítja a D, P és W mátrixokat és szin tömböt, és ezeket feltölti az alapértékekkel.



Init

állapot:

D

elemeit

C

elemeivel tölti fel, beállítja P-t és W-t. ertekadas változót minden lépésben növeli. Végén lementi a verembe az állapotot. Elindítja a külső for ciklust. A futó index k. Átmegy kezdobe állapotba. 

Kezdobe állapot: Kiírja, hogy hányadik iterációs lépés következik. Elindítja a belső ciklusokat, amivel végigmegy a mátrixok összes elemén (i, j változóval). Átmegy szomszedok állapotba.



Szomszedok állapot: Tájékoztat, hogy mely csúcsok közti utakat vizsgálja. Megvizsgálja, hogy talált-es rövidebb utat k csúcson keresztül i és j között.

64

Ha talált, a D mátrixban az i és j-hez tartozó értéket módosítja az új költségre, a megelőzési mátrixot is módosítja az új útnak megfelelően. Frissíti W mátrixot. Növeli listavizsgalat értékét. Ellenőrzi, hogy negatív összköltségű köre futott-e az algoritmus. Ha igen, befejezi az algoritmus futását. Növeli uresvizsg értékét, és lementi a verembe az algoritmus állapotát. Ha véget ér a külső ciklus, az algoritmus átmegy vege állapotba. 

Vege állapot: Kiírja a műveletigényt, és tájékoztat az algoritmus befejeződéséről. Fut változót hamisra állítja, ha kapott kezdőcsúcsot az algoritmus, kirajzolja a belőle induló legrövidebb utakat. Ezután csúcsra kattintással az adott csúcsból induló legrövidebb utakat rajzolja ki.

3.9.5.4

Éllistás algoritmus teljes lefutás 

Kezdeti beállítások: Beállítja a meret változót, példányosítja a D, P és W mátrixokat és szin tömböt, és ezeket feltölti az alapértékekkel.



Init állapot: D elemeit az éllista elemeivel tölti fel, beállítja P-t és W-t.

ertekadas

változót

minden lépésben növeli. Végén lementi a verembe az állapotot. Elindítja a külső for ciklust. A futó index k, és átmegy kezdobe állapotba. 

Kezdobe állapot: Kezdőcsúcs színét szürkére, távolságát 0-ra, szülőjét nilre állítja. Az ertekadas számláló értékét növeli. Lementi a tortenet2 verembe az aktuális állapotot. Az algoritmus átmegy kivesz állapotba. Innentől a függvény futása megegyezik a Matrix_teljes() futásával.

3.10

WarshellegyLepes A Warshall algoritmus egy lépését tárolja. Ugyanolyan, mint az egyLepes osztály, csak a tömbök helyett mátrixokat használ.

65

3.11

AlgoKezelo osztály Kapcsolatot tart a GrafAlgoForm és az Algoritmus osztály között. Konstruktora beállítja a változók értékét, alg változót az a megfelelő algoritmus szerint példányosítja.

3.11.1

Adattagok: típus

láthatóság private

string

név

leírás

melyikalgoritmus Annak az algoritmusnak a nevét tartalmazza, ami fut.

public

bool

fut

Fut-e még az algoritmus

public

int

szelesseg

Rajzpanel szélessége

public

int

magassag

Rajzpanel magassága

public

int

sebesseg

Animált futás sebessége. (Idozito tick eseményének késleltetése)

3.11.2

private

AlgoNevek nevek

Algoritmus neveket tartalmazza.

private

Algoritmus alg

Algoritmus

Metódusok: Az Algoritmus osztályban lévő függvényekkel megegyező nevű függvények az Algoritmus osztály megfelelő függvényét hívják meg. típus void

név

leírás

setMelyikAlgoritmus(string

nev-re állítja a

nev)

melyikalgoritmus változó értékét.

string getMelyikAlgoritmus() void

Visszatérési értéke a futó algoritmus.

LegrovidebbUtakAktCsucsbol Warshall-Floyd algoritmus esetén az n (int n)

csúcsból induló legrövidebb utakat kirajzoló függvényt hívja meg.

bool

getFut()

Lekérdezi az alg fut változójának értékét.

void

setFut(bool l)

l-re állítja az algoritmus fut változójának értékét.

66

void

setSzelesseg(int szel)

szel-re állítja az algoritmus szelesseg változóját.

void

setMagassag(int mag)

mag-ra állítja az algoritmus magassag változóját.

void

setRajzolas(Graphics g)

Meghívja az algoritmus setRajzolas függvényét g paraméterrel.

bool

3.12

FeltetelEllenoriz(ref Graf

Igazzal tér vissza, ha a graf nem

graf)

tartalmaz negatív költségű élt.

PriorityQueue osztály Minimumválasztó prioritásos sort megvalósító osztály. Megvalósítása [3] alapján rendezetlen tömbös reprezentációval készült. Paraméter nélküli konstruktora példányosítja sor-t, muveletszamlalo-t és osszesmuvelet-et 0-ra állítja. Paraméteres konstruktora példányosítja sor-t a kapott ArrayList szerint, muveletszamlalo-t és osszesmuvelet-et a paraméterben kapott értékre állítja.

3.12.1

Adattagok: láthatóság

típus

név

protected

ArrayList sor

private

int

leírás Prioritásos sort tárolja

muveletszamlalo Számolja az egyes műveletek műveletigényét.

private

int

osszesmuvelet

A sor létezése során az összes végrehajtott művelet műveletigényét számolja.

67

3.12.2

Metódusok: látható

típus

név

leírás

Insert(int e, double p)

Új SorElem-et szúr be a sor-ba

ság public

void

e értékkel, és p prioritással. public

void

Insert(SorElem s)

s-t beteszi a sor-ba.

public

void

Insert(El e)

Új SorElem-et szúr be a sor-ba e él végcsúcsával és súlyával.

private int

MinKer()

Visszatérési értéke a legkisebb prioritású elem indexe.

public

void

DelMin()

Törli a legkisebb prioritású elemet.

public

SorElem Min()

Legkisebb prioritású SorElemmel tér vissza.

public

SorElem MinDel()

Visszaadja és törli a legkisebb prioritású SorElem-et.

private void

DelIndex(int n)

Törli az n indexű elemet a sorból

public

bool

IsEmpty()

Igazzal tér vissza, ha nem üres a sor.

public

void

Clear()

Kiüríti sor-t.

public

int

Count()

sor hosszával tér vissza.

public

PriorityQ Clone()

Másolatot készít az elsőbbségi

ueue

sorról.

public

ArrayList ToArrayList()

ArrayList-té alakítja sor-t.

public

Array

ToArray()

Array-é alakítja sor-t.

public

void

Feltolt(double[] d)

d elemeivel tölti fel az elsőbbségi sort.

public

void

Helyreallit(int i,

Helyreállítja a prioritásos sort: i

double p)

érték prioritását p-re változtatja.

68

public

void

setErtek(int i, int e)

i indexű elem ertek-ét e-re változtatja.

private void private int

setPrioritas(int i,

i indexű elem prioritas-át p-

double p)

re változtatja.

IndexOf(int e)

e ertek-ű elem indexét adja vissza.

public

int

getMuveletszam()

muveletszamlalo értékét adja vissza.

public

int

getsetMuveletszam()

Visszaadja muveletszamlalo értékét és 0-ra állítja.

public

int

getOsszesMuvelet()

osszesmuvelet értékét adja vissza.

public

void

Nullaz()

muveletszamlalo értékét 0ra állítja

private void

Novel()

muveletszamlalo és osszesmuvelet értékét növeli 1-gyel.

private void

Novel(int n)

muveletszamlalo és osszesmuvelet értékét növeli n-nel.

public

void

setMuveletszam(int n) muveletszamlalo értékét nre állítja.

public

3.13

void

setOsszesMuvelet(int

osszesmuvelet értékét n-re

n)

állítja.

SorElem struktúra PriorityQueue egy elemét tárolja. Konstruktora az ertek és prioritas adattagokat állítja be.

3.13.1

Adattagok: double prioritas:

Prioritást tartalmazza

int ertek:

Elsőbbségi sorban tárolandó elem

69

3.13.2

Publikus metódusok: típus

név

void

setErtek(int e)

ertek-et e-re állítja

void

setPrioritas(double p)

prioritas-t p-re állítja

int

getErtek()

ertek-kel tér vissza

double getPrioritas() 3.14

leírás

prioritas-sal tér vissza

Abrazolas osztály Gráf éllistás, illetve mátrixos megjelenítéséért felelős osztály.

3.14.1

Adattagok: Felhasználói felület: Panel panel1: panel, amin ábrázolja a gráf tárolását. Private: 

int panelmeret: Az ábrázolás objektumainak mérete.



int csucsszam: Gráf csúcsainak száma.



Font betu: Betű a kiíráshoz.



Font betu_v: Vastag betű a kiíráshoz.



Brush ecset: Fekete ecset.



Pen toll: Fekete toll.



Pen toll_v: Fekete vastag toll.

Public: 

int x_bal, x_jobb, y_fent, y_lent: Ablak melyik van megfelelő távolságra (és milyen távolságra) a főablaktól, hogy az ragadhasson a főablakhoz.



bool ragad: Ablak együtt mozogjon-e a főablakkal.



bool fo_aktiv: Főablak aktív ablak-e.



bool automeretezes: Ablak együtt változzon-e a panellel.

70

3.14.2

Metódusok: látható típus

név

leírás

ság public

void

Matrix(ref Graf graf)

graf-t mátrixosan ábrázolja.

public

void

Ellista(ref Graf graf)

graf-t éllistásan ábrázolja.

public

void

Atmeretez(int ujmeretX, int

ujmeretX és ujmeretY

ujmeretY, ref Graf graf)

átméretezi az ablakot és ábrázolja a graf-t

public public

void int

Atmeretez(int ujmeretX, int

ujmeretX és ujmeretY

ujmeretY)

átméretezi az ablakot.

Csucsszam(ref Graf graaf)

graaf csúcsainak számával tér vissza.

private void

Abrazolas_Load(object sender,

x_bal, x_jobb,

EventArgs e)

y_fent, y_lent értékét 0-ra, ragad-ot igazra állítja.

public

void

Abrazolas_LocationChanged2() Ablak helyzetváltoztatása esetén a ragad-ot állítja be.

public

Font

ElemBeiras(string s, Font f,

Kiszámolja, hogy s

Graphics g)

szövegnek mekkora betűmérete legyen.

static

Font

public public

BetumeretValtoztatas(Font

betu betűméretét

betu, float betumeret)

betumeret-re változtatja.

Point KozepreIgazit(int x, int y, string Kiszámolja, hogy hol s, Font f, Graphics g)

kezdődjön az s szöveg rajzolása.

public

void

PanelMeretez(int szelesseg, int

A panel szélességét

magassag)

szelesseg-re, magasságát magassag-ra állítja.

71

3.15

TombAbrazolas osztály Algoritmus futása közben a tömböket/mátrixokat, sort, magyarázatot tartalmazó ablak. Konstruktora beállítja a szotar, gr, meret és statusLabel adattagok értékét.

3.15.1

Adattagok: Felhasználói felület: 

ListBox listBox_magyarazat: Magyarázatokat tartalmazza.



ListBox

listBox_magyarazat2:

Magyarázatok

Warshall-Floyd

algoritmus esetén. 

SorControl sorControl1: Sor ábrázolása.



TombControl tombControl_d: d tömböt ábrázolja.



TombControl tombControl_szulo: szulo tömböt ábrázolja.



MatrixControl matrixControlD: D mátrixot ábrázolja Warshall-Floyd algoritmus esetén.



MatrixControl matrixControlP: P mátrixot ábrázolja Warshall-Floyd algoritmus esetén.



MatrixControl matrixControlW: W mátrixot ábrázolja Warshall-Floyd algoritmus esetén.

Private: 

int meret: Gráf csúcsszáma



Hashtable szotar: Algoritmusos gráf – szerkesztési gráf csúcsainak megfeleltetését tartalmazza



Graf gr: Szerkesztési gráf



ToolStripStatusLabel

statusLabel:

hivatkozás

a

GrafAlgoForm

StatusLabel-jére, hogy változtathassa a feliratát. Public: 

int x_bal, x_jobb, y_fent, y_lent: Ablak melyik oldalról van megfelelő távolságra (és milyen távolságra) a főablaktól, hogy az ragadhasson a főablakhoz.



bool ragad: Ablak együtt mozogjon-e a főablakkal.



bool fo_aktiv: Főablak aktív ablak-e. 72

3.15.2

Publikus metódusok: típus

név

string Cimke(int index)

leírás index azonosítójú csúcs címkéjével tér vissza.

void

Tomb_vs_Matrix(bool matrixe) Beállítja, hogy a mátrixok, vagy a tömbök látszódjanak-e.

Tömbök függvényei: void

Szulo_abrazolas()

Beállítja a szülőtömb ábrázolás méretét, nevét és üríti.

void

D_abrazolas()

Beállítja a távolságtömb ábrázolás méretét, nevét és üríti.

void

FejlecModosit(int meret)

A tombControl-ok fejlécét a csúcs címkéire állítja be.

void

Q_abrazolas(string neve)

sorControl1 nevét neve-re állítja.

void

Q_abrazolas(Queue Q)

Beállítja sorControl1 nevét, és feltölti Q elemeivel.

void

Q_abrazolas(Array tomb, string sorControl1 nevét neve-re neve)

void

void

void

állítja és feltölti tomb elemeivel.

Szulo_modosit(int index, string tombControl_szulo indexadat)

edik tagját adat-ra módosítja.

D_modosit(int index, string

tombControl_d index-edik

adat)

tagját adat-ra módosítja.

Q_betesz(String mit)

sorControl1-be beteszi a mit azonosítójú csúcsot.

void

Q_kivesz()

sorControl1-ből kiveszi az első elemet.

void

Q_kivesz(int index)

sorControl1-ből kiveszi az index indexű elemet.

void

Szulo_modosit(int[] szulo)

tombControl_szulo-t módosítja szulo-vel.

73

void

D_modosit(double[] d)

tombControl_d-t módosítja dvel.

void

Q_feltolt(Queue q)

sorControl1-be beteszi q-t.

void

Q_feltolt(Array q)

sorControl1-be beteszi q-t.

void

Q_urit()

sorControl1-t kiüríti.

void

Szulo_urit()

tombControl_szulo-t kiüríti.

void

D_urit()

tombControl_d-t kiüríti.

void

sorControl1_Visible(bool l)

Beállítja sorControl1 láthatóságát.

void

d_NevBeallit(string nev)

Beállítja tombControl_d nevét.

Mátrixok függvényei: void

Dmatrix_abrazolas()

Beállítja matrixControlD /

void

Pmatrix_abrazolas()

matrixControlP /

void

Wmatrix_abrazolas()

matrixControlW nevét, méretét, és kiüríti.

void

Dmatrix_abrazolas(int meret)

Beállítja matrixControlD /

void

Pmatrix_abrazolas(int meret)

matrixControlP /

void

Wmatrix_abrazolas(int meret)

matrixControlW nevét, méretét, és feltölti üres elemekkel (matrixControlW-t hamissal).

void

MatrixFejlecModosit(int meret) Mátrixok fejlécét átállítja csúcscímkékre.

void void

Dmatrix_modosit(int x, int y,

matrixControlD /

string adat)

matrixControlP x,y indexű

Pmatrix_modosit(int x, int y,

elemét adat-ra állítja.

string adat) void

Wmatrix_modosit(int x, int y,

matrixControlW x,y indexű

bool l)

elemét l-re állítja.

void

Dmatrix_modosit(double[,] d)

matrixControlD /

void

Pmatrix_modosit(int[,] szulo)

matrixControlP /

void

Wmatrix_modosit(bool[,] w)

matrixControlW értékeit a paraméterül kapott mátrixra cseréli.

74

void

Dmatrix_urit()

matrixControlD /

void

Pmatrix_urit()

matrixControlP /

void

Wmatrix_urit()

matrixControlW vezérlőket kiüresíti.

Magyarázat függvényei: void

MagyarazatAdd(string s)

Hozzáadja a magyarázathoz s-t.

void

MagyarazatUrit()

listBox_magyarazat-ot kiüríti.

void

MagyarazatUtolsotTorol()

listBox_magyarazat legutoljára hozzáadott elemét törli.

string getMagyarazatElso()

listBox_magyarazat legutoljára hozzáadott elemével tér vissza.

Események (Private): void

TombAbrazolas_Load

Beállítja az ablak pozícióját, x_bal, x_jobb, y_fent, y_lent értékét 0-ra, ragad értékét igazra állítja.

void void

TombAbrazolas_LocationChan

ragad értékét állítja be, ha változik

ged

a helyzete az ablaknak.

listBox_magyarazat_SelectedIn listBox_magyarazat kijelölt dexChanged

void

elemeit vágólapra másolja.

listBox_magyarazat2_SelectedI listBox_magyarazat2 kijelölt ndexChanged

3.16

elemeit vágólapra másolja.

TombControl osztály Tömbök

ábrázolására

szolgál.

Label-ekben

tárolja a

tömb elemeit.

Konstruktora példányosítja panel-t, és beállítja a pozícióját, méreteit, és a vezérlő nevét. 3.16.1

Privát adattagok: Felhasználói felület: 

Label nev: Vezérlő nevét tartalmazza.



FlowLayoutPanel flowLayoutPanel1: Ezen helyezkedik el a nev és a panel.

75



TableLayoutPanel panel: Panel a tömb elemeinek és indexeinek kirajzolásához.

3.16.2



Label[] fejlectomb: Fejléceket (indexeket) tároló tömb.



Label[] adattomb: Az ábrázolandó tömb elemeit tároló tömb.



float[] szelesseg: Az egyes elemek szélességét tároló tömb.



ColumnStyle[] oszlopstilus: panel oszlopainak stílusait tárolja.



float szorzo: A vezérlő szélességének beállításához korrigáló változó.

Publikus metódusok: típus

név

leírás

void NevBeallit(string s)

nev feliratát s-re állítja.

void PanelBeallit(int s_szam,

Példányosítja oszlopstilus-t, panel

int o_szam)

sor és oszlopszámát s_szam és o_szamnak állítja, és beállítja az oszlopstílusokat.

void PanelStyle()

panel oszlopainak és sorainak stílusát állítja be. (A függvény a [4] példakódja alapján készült.)

void TombKeszit(int meret)

meret eleműre készíti el panel-t, inicializálja a fejlectomb, adattomb, szelesseg tömböket és feltölti alapértékekkel.

void ErtekModosit(int index, string adat)

Módosítja az adattomb index indexű elemének értékét adat-ra.

void FejlecModosit(int index, Módosítja a fejlectomb index indexű string adat) void FontModosit(Font font)

elemének értékét adat-ra. font-ra módosítja az adattomb, fejlectomb betűit.

void PanelMeretezes()

Beállítja panel méretét.

void SzelessegValtozas(int

index indexű oszlopban lévő szövegek

index)

hossza alapján állítja be a szelesseg tömb index indexű elemét.

76

3.17

MatrixControl osztály Mátrixok ábrázolására szolgál. Label-ekben tárolja a mátrix elemeit. Konstruktora példányosítja matrixpanel-t, és beállítja a pozícióját, méreteit, és a vezérlő nevét.

3.17.1

Privát adattagok: Felhasználói felület: 

Label nev: Vezérlő nevét tartalmazza.



FlowLayoutPanel flowLayoutPanel1: Ezen helyezkedik el a matrixpanel.



TableLayoutPanel matrixpanel: Panel a mátrix elemeinek és indexeinek kirajzolásához.



Label[] fejlectomb: Vízszintes fejlécét tartalmazó tömb.



Label[] fejlectomb2: Függőleges fejlécét tartalmazó tömb.



Label[,] adattomb: Ábrázolandó mátrix elemeit tartalmazó mátrix.



float[] szelesseg: matrixpanel oszlopainak szélességét tartalmazó tömb.



float[]

oszlopmaxszelesseg:

matrixpanel

minden

oszlopának

legszélesebb elemének szélességét tartalmazza. 

float[] sormaxmagassag: matrixpanel minden sorának legmagasabb elemének magasságát tartalmazza.



ColumnStyle[] oszlopstilus: matrixpanel oszlopainak stílusait tárolja



RowStyle[] sorstilus: matrixpanel sorainak stílusait tárolja



float szorzo: Vezérlő szélességének és magasságának beállításához korrigáló változó.



float minszelesseg, minmagassag: Minimum szélesség és magasság tárolása.

3.17.2

Metódusok: név

típus

leírás

Private: void

MinErtekBeallit()

Beállítja a cellák minimális szélességét, és magasságát.

77

float

AdattombMaxWidth(int j)

adattomb j-edik oszlopa legszélesebb elemének szélességét adja vissza.

void

AdattombWidthValtoztat(i

adattomb j-edik oszlopa minden

nt j, int meret)

elemének szélességét meret-re állítja.

Public: void NevBeallit(string s)

nev feliratát s-re állítja.

void PanelBeallit(int s_szam, int

Példányosítja oszlopstilus-t és

o_szam)

sorstilus-t, matrixpanel sor és oszlopszámát s_szam és o_szam-nak állítja, és beállítja az oszlop- és sorstílusokat.

void PanelStyle()

matrixpanel oszlopainak és sorainak stílusát állítja be. (A függvény a [4] példakódja alapján készült.)

void MatrixKeszit(int meret)

(meret+1 * meret+1) eleműre készíti el matrixpanel-t (+1 a fejlécek miatt), inicializálja a fejlectomb, fejlectomb2, adattomb, szelesseg, oszlopmaxszelesseg, sormaxmagassag tömböket és feltölti alapértékekkel.

void ControlMeretezes()

Beállítja a vezérlő szélességét és magasságát.

void ErtekModosit(int x, int y, string adat) void FejlecModosit(int index, string adat)

Módosítja az adattomb (x,y) indexű elemének értékét adat-ra. Módosítja a fejlectomb és fejlectomb2 index indexű elemének értékét adat-ra.

void FontModosit(Font font)

font-ra módosítja az adattomb, fejlectomb és fejlectomb2 betűit.

78

void PanelMeretezes()

Beállítja matrixpanel méretét.

void SzelessegValtozas(int

index indexű oszlopban lévő szövegek

index)

hossza alapján állítja be a szelesseg tömb index indexű elemét.

3.18

SorControl Sor ábrázolására szolgál. Label-ekben tárolja a sor elemeit. Konstruktora beállítja flowLayoutPanel1 méreteit, és a vezrélő nevét.

3.18.1

3.18.2

Felhasználói felület: 

Label nev: Vezérlő nevét tartalmazza.



FlowLayoutPanel flowLayoutPanel1: Sor elemeit tartalmazza.

Publikus metódusok: név

típus

leírás

void NevBeallit(string s)

nev feliratát s-re állítja.

void Betesz(Label l)

l-t hozzáadja a flowLayoutPanel1hez.

void Betesz(String mit)

Létrehoz egy Label-t mit felirattal, és beteszi flowLayoutPanel1-be.

void Betesz(String mit, int hova) void EldobElso()

mit szöveget beteszi a vezérlőbe a hova indexű helyre. flowLayoutPanel1-ből kiszedi az első elemet.

void Eldob(int index)

flowLayoutPanel1-ből kiszedi az index indexű elemet.

void Urit()

Kiüríti flowLayoutPanel1-t.

void Betesz(Queue q)

q elemeit sorban hozzáadja a vezérlőhöz.

void ElsoSzinez(Color c)

flowLayoutPanel1 első elemét c színűre festi.

void OsszesBetumeret(int meret)

flowLayoutPanel1 összes elemének betűméretét meret-re állítja.

79

void ElsoBetumeret(int meret)

flowLayoutPanel1 első elemének betűméretét meret-re állítja.

3.19

GrafGeneral osztály Gráf generálható megadott csúcsszám, és csúcsok közti élvalószínűség érték megadásával. Konstruktora beállítja a szelesseg, magassag és graf változókat

3.19.1

3.19.2

Privát adattagok: 

int szelesseg, magassag: Rajzterület szélessége és magassága



Graf graf: Gráf

Felhasználói felület: Név numeric_csszam

Funkció

Típus

Csúcsok számát

NumericUpDown

lehet megadni. numeric_vlsz

Egyéb Minimum: 0, Maximum: 100

Csúcsok közti él NumericUpDown valószínűsége állítható be.

checkBox_veletlen Véletlen

CheckBox

élsúlyokkal

Felirat: Véletlen élsúlyok

generálja-e a gráfot. numeric_min

Véletlen élsúly

NumericUpDown

alsó határa numeric_max

Véletlen élsúly

Maximum: 1000 NumericUpDown

Legenerálja a

Minimum: -1000, Maximum: 1000

felső határa button_ok

Minimum: -1000,

Button

Felirat: OK

Button

Felirat: Mégsem

gráfot és bezárja az ablakot. button_megse

Bezárja az ablakot generálás nélkül.

80

3.19.3

Események: név

leírás

button_ok_Click

Gráf generálását végzi el a felületen megadott paraméterek szerint és bezárja az ablakot.

button_megse_Click Bezárja az ablakot. 3.20

VelElsuly osztály Véletlen élsúly intervallumát állítja be. Button_Ok eseménykezelője bezárja az ablakot.

3.20.1

Felhasználói felület: Név min

Funkció Véletlen élsúly alsó

Típus

NumericUpDown Minimum: -100,

határa max

Maximum: 100

Véletlen élsúly felső

NumericUpDown Minimum: -100,

határa buttonOk 3.20.2

Maximum: 100

Bezárja az ablakot

Button

Felirat: Rendben

Publikus metódusok: név

típus int

getMinimum()

leírás Visszatér min értékével.

void setMinimum(int n)

Beállítja min értékét n-re.

int

Visszatér max értékével.

getMaximum()

void setMaximum(int n) 3.21

Egyéb

Beállítja max értékét n-re.

AlgoNevek osztály String típusú adattagjai az implementált algoritmusok neveit tárolják. Egyetlen függvénye, NemKellKezdoCsucs(string

a) igazzal tér vissza, ha az

algoritmus futásához nem kell kijelölni kezdőcsúcsot. 3.22

Szinek osztály Program által használt színeket tárolja. Adattagjai színek.

81

3.22.1

Publikus metódusok: típus

név

leírás

string MiaSzine(Color c)

c színét adja vissza magyarul.

string MiaSzineEng(Color c) c színét adja vissza angolul. void

AlapBeallitas()

AlgoAlapBeallitas()-t és GrafAlapBeallitas()-t hívja meg.

void

AlgoAlapBeallitas()

Algoritmusokhoz használt színeket állítja alapértékekre.

void

GrafAlapBeallitas()

Gráf ábrázolásához, és szerkesztéséhez használt színeket állítja alapértékekre.

4. 4.1 4.1.1

Tesztelési terv Gráfok szerkesztése Csúcsok elhelyezése, törlése, szerkesztése 

Két csúcs egymásra helyezése: Nem lehetséges, az első csúcs kijelölésre kerül.



Címke szerkesztése: o Azonos

címkék:

Nem

lehet két azonos címkéjű csúcs a gráfban. o Hosszú címke: Címke a csúcsban van. 

Kijelölt

csúcs

törlés

Delete

gombbal:

Csúcshoz kapcsolódó élek törlődnek.  4.1.2

Csúcs mozgatása: Él mozog a csúccsal együtt.

Élek elhelyezése, törlése, élsúly szerkesztése 

Élrajzolás: Két csúcs között.



Élrajzolás: Kezdőcsúcs, vagy végcsúcs, vagy mindkettő új csúcs.



Kijelölt él törlése Delete gombbal.

82



Élsúly szerkesztés: o Élsúly természetes szám o Élsúly valós szám o Élsúly nem szám: Automatikusan 1 lesz az élsúly.

4.1.3

Beállítások 

Csúcscímkézett: Eltűnik a csúcscímke, ha nincs bejelölve, Ábrázolás ablakban címkék helyett belső azonosító. Újra bejelölésnél címkék visszaállnak.



Élsúlyozott: Élsúlyok kirajzolása megszűnik, ha nincs bejelölve, Ábrázolás ablak is ennek megfelelően változik. Újra bejelölésnél élsúlyok újra látszódnak.



Gráftípus: Irányítatlan esetben élek végén nincsenek nyilak, Ábrázolás ablak

is

irányítatlan

gráfot

ábrázol.

Irányított

esetben

nyilak

megjelennek, ábrázolás ablak irányított gráfot ábrázol. 

Ábrázolás: A kiválasztásnak megfelelően az ábrázolás változik.



Csúcsméret: Csúszka segítségével módosítható. Szövegmezőbe gépelve 0 és 20 közé eső egész értéket beállítja, intervallumon kívülit az értékhez közelebbi intervallumhatárra állítja, valós szám és szöveg esetén az utolsó helyes értéket állítja be.



„Ábrázolás mutatása” és „Tömbök mutatása” jelölőnégyzet kijelölés változtatásának hatására az ablakok megjelennek, eltűnnek.



Algoritmus vezérlők: o Sebesség: algoritmus futási sebessége változik o „Animálás”, „Lépésenként” jelölőnégyzet megfelelő működése o „<-” és „->” gombok csak akkor elérhetőek, ha az adott irányban lehet lépni. o „Indít” gomb csak akkor elérhető ha az algoritmus indítható

4.1.4

Státuszsor megfelelően változik

83

4.2

Algoritmusok működése Gráfok tesztelésénél az algoritmus futása tesztelésre kerül éllistás, mátrixos ábrázolással animált, lépésenkénti, teljes futással élsúlyos, súlyozatlan, irányított, irányítatlan esetben.

4.2.1

Szélesség bejárás: 

Új algoritmusok [1]-ban lévő példagráfra rendben lefut.



Futás előtt a gráfot élsúlyozatlanná alakítja.



1 csúcsot tartalmazó gráfra rendben lefut.



Üres gráf: „Indít” gomb ilyenkor nem lehet aktív.



Algoritmus futás közben a gráf nem szerkeszthető.

4.2.2

Dijkstra algoritmus: 

Új algoritmusok [1]-ban lévő példagráfra rendben lefut.



Negatív élsúlyt tartalmazó gráf: hibaüzenetet ad a program.

4.2.3



1 csúcsot tartalmazó gráfra rendben lefut.



Üres gráf: „Indít” gomb ilyenkor nem lehet aktív.



Algoritmus futás közben a gráf nem szerkeszthető.

Bellmann-Ford algoritmus: 

Új

algoritmusok

[1]-ban

lévő

példagráfra rendben lefut. 

Negatív élsúlyra rendben lefut.



Negatív összköltségű kör: Algoritmus végén még egy iterációs lépés ellenőrzi a negatív kört.



1 csúcsot tartalmazó gráfra rendben lefut.



Üres gráf: „Indít” gomb ilyenkor nem lehet aktív.



Algoritmus futás közben a gráf nem szerkeszthető.

84

4.2.4

4.2.5

Prim algoritmus: 

Új algoritmusok [1]-ban lévő példagráfra rendben lefut.



Negatív élsúlyra rendben lefut.



1 csúcsot tartalmazó gráfra rendben lefut.



Üres gráf: „Indít” gomb ilyenkor nem lehet aktív.



Algoritmus futás közben a gráf nem szerkeszthető.

Warshall-Floyd algoritmus: 

Új

algoritmusok

[1]-ban

lévő

példagráfra rendben lefut. 

Negatív élsúlyra rendben lefut.



Negatív összköltségű kör:



1 csúcsot tartalmazó gráfra rendben lefut.



Üres gráf: „Indít” gomb ilyenkor nem lehet aktív.



Algoritmus futás közben a gráf nem szerkeszthető.



Algoritmus végén csúcsok kijelölhetők, a kijelölt csúcsból a legrövidebb út látható.

4.3

Gráf importálása Hibás sorok esetén a hibás sorokat kihagyja, és folytatja az importálást, végén kiírja a hibákat.

85

4.4

4.5

Gráf generálás 

Nem adható meg rossz számérték



Véletlen élsúly intervallumának alsó határa nagyobb, mint felső határ:

Véletlen élsúly intervallum Nem adható meg hibás számérték. Ha az intervallumának alsó határa nagyobb, mint felső határ, a két számot megcseréli.

86

Összegzés A program az implementált algoritmusok szemléltetésével közelebb hozza a gráfalgoritmusok világát a hallgatókhoz. Megismerkedhetnek a gráfalgoritmusok működésével,

az

előadásokon

és

gyakorlatokon

bemutatott

algoritmusokat

kipróbálhatják, működésüket könnyebben megérthetik. A magyarázó szövegek segítségével az algoritmus futásáról részletes információkat kaphatnak. Az algoritmus futásának végén az elvégzett műveletek számából megállípítható az egyes algoritmusok gyorsasága, az éllistás és mátrixos tárolás esetén a műveletigény eltérése. A gráfok szerkesztése egyszerű, az éppen elérhető funkciókról a státuszsor tájékoztat, a „Segítség” menüponttal pedig pontos leírás olvasható a program használatáról, az algoritmusok működési elvéről. A gráfok grafikus megjelenítése mellett megtekinthető azok tárolási struktúrája is, így nem csak az algoritmusok könnyebb megértéséhez nyújt segítséget a program, hanem a gráf számítógépes tárolása is tanulmányozható. A program az oktatókat is segítheti a gráfalgoritmusok tanításánál. A gráfok elmenthetők, így akár órákra való felkészülésnél előre elkészíthetők, és az órán csak be kell tölteni, és a kívánt algoritmus akár animáltan, akár lépésenként szemléltethető mind mátrixos, mind éllistás tárolású gráf esetén. A program további fejlesztési iránya lehet újabb algoritmusok implementálása, a gráfok ábrázolásának testreszabása (programban megjelenő színek átállítása, élvastagság, stb.), az elkészült gráf nyomtatása. A dokumentációban használt UML diagramok Violet UML Editor-ral [7], a struktogramok pedig NSD Editor-ral készültek [8].

87

Irodalomjegyzék [1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Új Algoritmusok, Scolar kiadó, 2003, [992], ISBN 978 963 9193 90 1 [2] http://people.inf.elte.hu/fekete/docs_2/grafalg/grafalg.htm (2009-05-27) [3] http://people.inf.elte.hu/fekete/docs_1/jegyzet2-2.pdf (2009-06-06) [4] http://msdn.microsoft.com/enus/library/system.windows.forms.tablelayoutcolumnstylecollection.aspx (2009-06-06) [5] http://people.inf.elte.hu/gt/eaf/eaf3/eaf3.html (2009-06-07) [6] http://www.softwareonline.hu/ (2009-06-07) [7] http://alexdp.free.fr/violetumleditor/page.php (2009-06-07) [8] http://diuf.unifr.ch/softeng/student-projects/completed/kalt/NSD.html (2009-06-07)

88