G RÁF SZIMULÁCIÓ AZ OKTATÁSBAN

BUDAPESTI MŰSZAKI FŐISKOLA Neumann János Informatikai Kar Informatikai Automatizált Rendszerek Szakirány Humánfejlesztési- és Módszertani Intézet Mérnök Tanári Képzés

GRÁF SZIMULÁCIÓ AZ OKTATÁSBAN

Név: BEDŐK DÁVID Konzulens: DR. HASSAN ELSAYED Dátum: 2006. május 02.

Gráf szimuláció az oktatásban

BUDAPESTI MŰSZAKI FŐISKOLA

TARTALOMJEGYZÉK TARTALOMJEGYZÉK...............................................................................................................................2 1 – CÉL MEGHATÁROZÁS ......................................................................................................................4 2 – MEGVALÓSÍTÁSI TERV....................................................................................................................5 2.1 HELYZET ÉS PROBLÉMAELEMEZÉS .......................................................................................................5 2.2 FONTOSABB RÉSZFELADATOK BEMUTATÁSA .......................................................................................5 2.3 ALKALMAZOTT MÓDSZEREK ................................................................................................................5 2.4 ÉRTÉKELÉSI PONTOK KIJELÖLÉSE, ÉRTÉKELÉSI KRITÉRIUMOK MEGADÁSA .........................................5 2.5 PROJEKT DOKUMENTÁCIÓ FELÉPÍTÉSE .................................................................................................6 2.6 AZ EREDMÉNYEK HASZNOSÍTHATÓSÁGA, TERJESZTHETŐSÉGE ..........................................................6 3 – IRODALOMKUTATÁS .......................................................................................................................7 3.1 JÁTÉKOK A TÖRTÉNELEMBEN ...............................................................................................................7 3.2 A JÁTÉK, A SZIMULÁCIÓ ÉS AZ ESETTANULMÁNY AZ OKTATÁSBAN ...................................................8 3.3 LEHETŐSÉGEK ÉS KORLÁTOK A HAZAI JÁTÉKKULTÚRA KITERJESZTÉSÉBEN .....................................11 3.4 A SZÁMÍTÓGÉP, MINT OKTATÁSI ESZKÖZ ..........................................................................................12 3.5 LABVIEW, MINT A SZÁMÍTÓGÉPES SZIMULÁCIÓ ESZKÖZE.................................................................14 4 – GRAPHS AND SPANNING TREES ...............................................................................................17 4.1 - A PROGRAMRÓL ÁLTALÁBAN ..........................................................................................................17 4.2 GRÁF, MINT MATEMATIKAI FOGALOM...............................................................................................17 4.2.1 Néhány alapfogalom ..............................................................................................................17 4.2.2 - Gráfok.....................................................................................................................................18 4.2.3 - Gráfok ábrázolása................................................................................................................18 4.2.4 - Minimális költségtérítésű feszítőfa ....................................................................................20 4.2.5 - Legrövidebb út ......................................................................................................................21 4.3- FELHASZNÁLÓI KÉZIKÖNYV .............................................................................................................25 4.31 - Új gráf létrehozása ................................................................................................................25 4.3.2 - Gráf megnyitása...................................................................................................................28 4.3.3 - Globális beállítási lehetőségek............................................................................................28 4.3.4 - Lokális beállítások................................................................................................................31 4.3.5 - Új gráf pont felvétele............................................................................................................31 4.3.6 - Új él felvétele a gráfba .........................................................................................................34 4.3.7 - Gráf pontok és élek módosítása illetve törlése .................................................................35 4.3.8 - Gráf tulajdonságainak utólagos beállítási lehetősége ...................................................36 4.3.9 - Az aktuális súly illetve gráf pont adat beállítása ............................................................36 4.3.10 - Gráf mentése .......................................................................................................................37 4.3.11 - Kapcsolatmátrix generálása .............................................................................................37 4.3.12 - Legrövidebb út meghatározása Dijkstra algoritmusa alapján...................................39 4.3.13 – Szerkesztés gyorsítása ......................................................................................................41 4.3.14 – Tömegesen felvett élek és gráf pontok módosítása és törlése.....................................46 4.3.15 – Útkeresés egyszerűbb formája ........................................................................................47 4.4 - FEJLESZTŐI DOKUMENTÁCIÓ ...........................................................................................................50 4.4.1 - A programról.........................................................................................................................50 4.4.2 - A TObject3D osztály .............................................................................................................51 4.4.3 - A TGraph osztály..................................................................................................................54 4.4.4 – A TypeUnit további részei ..................................................................................................64 5 – TÁRGYSZÓ JEGYZÉK.......................................................................................................................66 6 – SZAKIRODALOM ÉS FORRÁSJEGYZÉK ....................................................................................67

2/67



6.1 – FORRÁSJEGYZÉK...............................................................................................................................67 6.2 – LINK GYŰJTEMÉNY ...........................................................................................................................67

3/67



1 – CÉL MEGHATÁROZÁS A tanításra, avagy oktatásra nézve véleményem szerint nem létezik olyan módszer, melyet elsajátítva bármit képesek vagyunk a lehető legjobban átadni a hallgatóság számára. Nem lehet azonos módszerekkel irodalmat tanítani, és matematikát. El sem tudnánk képzelni történelem órát térképek, vagy számítástechnikát gépek nélkül. Ezek a dolgok kézenfekvőek, hisz elmondani, hogy merre van a Havas-alföld körülményes, megmutatva a térképen azonban nemcsak egyszerűbb, de szemléletesebb is egy földrajzóra során. Ellenben mi keresni valója van egy számítógépes programnak egy matematika, rajz, a vagy mesterséges intelligencia órán? Bár megfelelően magas szinten ez a kérdés fel sem merül, hiszen léteznek olyan összetett matematikai problémák, melyeket ma már csak számítógépek tudnak véges időn belül megoldani, de vajon segítheti-e az oktatást az, hogyha adott elméleti problémákat a gyakorlatban is szemügyre veszünk? Természetesen igen. Ugyanúgy, mint ahogy könnyíti, egyszerűvé és ugyanakkor változatossá teszi a tanulást egy térkép jelenléte történelem órán, a matematika órán is van helye egy számítógépnek. A „Gráf szimuláció az oktatásban” című projekt célja bemutatni és igazolni a fentebb leírtakat, valamint megvalósítani egy szimulációs programot a matematika területéről. A szimulációs programok általában rendelkeznek az „önálló tanulás” eszközeivel is. A témakör elméleti alapjait megismerteti a felhasználóval, példákat mutat be, majd ellenőrzés céljából feladatokat oldat meg, melyek értékeléséből is tanulni lehet. A program magas szintű nyelven fog elkészülni, Microsoft Windows operációs rendszer alá.

4/67



2 – MEGVALÓSÍTÁSI TERV 2.1 Helyzet és problémaelemezés Külföldön, főleg az Amerikai Egyesült Államokban és Nyugat-Európában már az 1960-as, 1970-es években elkezdődött a szimulációs és játék programok ipari készítése, és elterjedése az oktatásban és képzésben. Magyarország csak az utóbbi időben ismerte fel ennek előnyeit, és alkalmazta a gyakorlatban. Ehhez a szemlélethez társulva a „Gráf szimuláció az oktatásban” projekt elkészít egy szimulációs programot.

2.2 Fontosabb részfeladatok bemutatása Mindenek előtt teszünk egy történelmi kitérőt arra nézve, hogy a játékok fejlődése mi módon kapcsolódik össze a szimulációs programok kialakulásáig, majd az irodalomkutatás kereteiben megvizsgáljuk, hogy miért alkalmazzák világszerte az oktatásban és a képzésben a szimulációs módszereket. Rátérünk arra is, hogy mi lehet az oka annak, hogy Magyarországon késve jelentkezett ez a technika, és megoldási javaslatokat is teszünk. Megemlítjük a LabView nevű programozási nyelvet, mely szorosan kötődik a szimulációs programok készítéséhez, valamint teszünk kitérőt arra nézve, hogy a számítógép mi módon kapcsolódik a nevelés folyamatába. Természetesen a legfontosabb részfeladatok közé tartozik a szimulációs program megvalósítása, implementálása magas szintű programozási nyelven. A program a matematika tárgykörére épülve a gráfokkal fog foglalkozni (a program elnevezése Graphs and Spanning Trees lesz). A „Gráf szimuláció az oktatásban” projekt tartalmazni fogja a program felhasználói és fejlesztői kézikönyvét, valamint kitér az alkalmazás alkalmazhatóságára, előnyeire, illetve hátrányaira. Végül, összefoglaló gyanánt a fejlesztés során összegyűjtött tapasztalataimat megfogalmazva ötleteket ad arra nézve, hogy hogyan készítsünk magunk olyan szimulációs programokat, melyek a magyarországi oktatás és képzés folyamatába beilleszkednek.

2.3 Alkalmazott módszerek A szimulációs program magas szintű programozási nyelven lesz elkészítve. A gráfokkal foglalkozó Graphs and Spanning Trees nevű alkalmazás Borland Delphi 7 rendszerben készül.

2.4 Értékelési pontok kijelölése, értékelési kritériumok megadása Az elkészült program használhatóságát szakirányú konzulensek segítségével a Budapesti Műszaki Főiskola hallgatósága fogja tesztelni. A

5/67



tesztelés elkezdéséhez a program funkcióinak jelentős részét implementálni szükséges, így ez a projekt közepe tájékán lesz esedékes először. Amennyiben a hallgatóság felhasználóbarát módon képes az elkészült programot kezelni, valamint segít számukra az érintett témát könnyebben megtanulni, elsajátítani, a projekt eléri célját.

2.5 Projekt dokumentáció felépítése A dokumentáció a cél meghatározásával kezdődik, jelen megvalósítási tervvel és irodalomkutatással folytatódik. Mindezek után egy nulladik szintű rendszerterv keretében a programok elméleti hátterével, valamint a programok által kitűzött konkrét célok megfogalmazásával folytatódik, majd bemutatásra kerül a két program felhasználói és fejlesztői kézikönyve. A dokumentáció legvégén a fejlesztés során összegyűjtött tapasztalatok fogalmazódnak meg.

2.6 Az eredmények hasznosíthatósága, terjeszthetősége A projekt elsődleges célja, hogy az elkészült program segítse a hallgatóságot a megvalósított problémakör megértésében. Az alkalmazások ingyenesen elérhetőek lesznek az Interneten, amennyiben e cél megvalósul.

6/67



3 – IRODALOMKUTATÁS 3.1 Játékok a történelemben A szimuláció és a játékok szoros kapcsolatban állnak egymással, ezt majd a későbbiekben látni fogjuk. Előtte azonban tekintsük át a játékok fejlődésének fontosabb lépéseit történelmünkben. Játékokat azért készített az ember, hogy kikapcsolódjon, szórakozzon. Legalábbis így gondoljuk legtöbben, azonban az sem véletlen, hogy a legtöbb táblás játék valamelyest a harcászati stratégiához kötődik. Valamelyest szimulálja a harcmező eseményeit, és a győztes stratégia általában a harcmezőn is győzelemre vezet. Természetesen nagy általánosságokban beszélve. Az egyik legrégebbi fent maradt játéktáblát El-Mahasznában találták (FelsőEgyiptom). Kora 75oo-8ooo évre tehető. A tábla 3x6 mezős, agyagból készült, és 11 kúp alakú figura tartozik hozzá. Egy másik híres lelet az Ur városából (Dél-Mezopotámia) származik. Ez agyagból készült kb. 46oo évvel ezelőtt (FORRÁSJEGYZÉK: 3-I). Sokak szerint a legrégebbi táblás játék a még ma is játszott „gó”. Az első írásos feljegyzés Konfuciustól származik i.e. 5oo-ból. A gó harci játék, a tábla a lakatlan világot jelképezi, amelyet minden oldalról tenger vesz körül (FORRÁSJEGYZÉK: 3-II). A harci játékok sorából nem felejthetjük ki a sakkot sem. A sakk őse valószínűleg egy indiai hadijáték (csaturanga), mely a VI. században keletkezett, írásos emlékek már a VII. századból vannak róla. A csaturangát négyzet alakú, 64 egyforma színű mezőn játszották. A csatura (négy) és az anga (tagozat) szavak összetétele az akkori négy fegyvernemre (gyalogság, lovasság, harci szekerek és elefántok) utal (FORRÁSJEGYZÉK: 3-III). A sakkban két játékos vezeti a küzdelmet két egyenlő erővel küzdő hadsereg között. Az eredmény kimenetele a két fél tudásától, stratégiai felkészültségétől függ. Megjegyzendő azonban, hogy ma már nem csupán az emberek tudnak sakkozni, hanem a „gépek” is, sőt mi több, jobb eredményességgel. A legkézenfekvőbb megoldás arra nézve, hogy sakkprogramot készítsünk, hogy eltároljuk a történelem eddig feljegyzett híres sakk játszmáit, és mikor az emberi játékos lép, és egy helyzet előáll, a gép „nem tesz mást”, mint a memóriájában keres egy olyan játszmát, ahol azonos helyzetek mellett a gép színe nyert. Egy fokkal összetettebb megoldás, hogy a gép már az első lépés után képes végigjátszani a partit sok száz lépésre előre, minden lehetőséget megvizsgálva. Ha a „végigjátszása” végén az ember nyer, az adott utat nem választja. Ilyen memóriával, kombinációs képességgel mi nem rendelkezünk, így a legjobb sakkozó is nehezen képes felvenni a versenyt a gépekkel szemben (általában sakk gépek másik sakk gépekkel játszanak). Kelet-Európába a 900-as évek körül jutott el a sakk bizánci közvetítéssel, az első írásos emlék Nyugat-Európából (Spanyolország) 1008-ból származik. 7/67



A hadijátékokat a XIX. században két csoportba sorolták. Az egyiket bonyolult és merev szabályok, valóságos helyzetek jellemezték (rigid), melyben a háborús helyzetek váratlan fordulatait a dobókocka határozta meg. Ennek a típusnak a játszásához számos térkép és táblázatra volt szükség, és tényleges értéke abban ált, hogy tanította a stratégiákat a játékban résztvevőkkel. A másik csoportja a hadijátékoknak a taktikára helyezte a fő hangsúlyt. A „rigid” játékok egyik első képviselője 1778-ból származik (Kriegspiel), melyhez számos térképet rajzoltak. Az ilyen játékok elterjedése azonban csak az 1870-es évektől jellemző. Az első mai értelemben vett katonai játékot Poroszországban készítették. Ma már szinte minden hadseregben használnak a kiképzés részeként ehhez hasonló módszereket. A számítógépek elterjedésével a hosszú előkészületeket igénylő „rigid” típusú játékok kerültek előtérbe (a hosszú előkészületekben segít a számítógép). Az 1960-as években az Egyesült Államok a számítógépek segítségét is felhasználta a vietnámi háborúban (FORRÁSJEGYZÉK: 3-IV). Mindezek után elmondható, hogy a fenti „játékok” már nem a szórakozást szolgálják elsősorban. Valós helyzetekben kipróbálják azokat a dolgokat, melyeket a „játékban” sikerrel alkalmaztak. Az ilyen típusú játékokat szimulációs eszközöknek hívjuk. Ez hát a történelmi kapcsolat a játék, és a szimuláció között.

3.2 A játék, a szimuláció és az esettanulmány az oktatásban A legkülönfélébb tudományterületek vezető tudósainak és kutatóinak egybehangzó véleménye az, hogy az egyes nemzetek, csoportok kiemelkedését a nemzetek fejlődéséért vívott harcban nagyban befolyásolni fogja az, hogy az emberek mennyire lesznek képesek szembenézni szokatlan problémákkal, mennyire lesznek képesek figyelembe venni a különböző nézőpontok által nyújtott megoldási lehetőségeket. Az ilyen nézőpontok felismerésében segíthetnek minket többek között a játékok és a szimulációk, így ezek szerepe kiemelkedő e téren. E módszerek nagymértékben fejlesztik a kreativitást, a problémamegoldó és döntéshozatali készséget. Sok szakember a jövő nyelvének tekinti a játék- és szimulációs módszereket (FORRÁSJEGYZÉK: 3-V). Elsősorban az Egyesült Államokban és Nagy-Britanniában a játék és szimuláció alapú gyakorlatok elterjedése ugrásszerűen megnövekedett mind az oktatásban, mind a képzésben. A játékok, szimulációk és esettanulmányok sokoldalú és rugalmas eszközök lehetnek nemcsak az oktatási, képzési, hanem a nevelési célok elérésében is. A szimuláció során megszerzett gyakorlat alapján a részvevő jelöltek lényegesen hamarabb és könnyebben jutnak el a helyes döntésig, mint azon társaik, melyek nem vettek részt szimulációs gyakorlatokban. Nem véletlen az sem, hogy az üzleti életben és a vezetőképzésben hamar elterjedt a módszer. 8/67



Az ipari és a katonai felhasználás mellett természetesen az oktatásban és a képzésben betöltött szerepe a legjelentősebb a szimulációs programoknak. Az első publikációk 1962-ben jelentek meg (Hemphil-Griffits-Frederiksen: Administrative Performance and Personality; Kersh, B. Y.: The Classroom Simulator). Az új törekvések azonban kezdetben csak az Amerikai Egyesült Államokban jelentek meg, egy évtizeddel később aztán Európában is. A szimulációs módszerek fejlődése ma már folyamatos szerte a világon. Éppen a legutóbbi időkben (az audiovizuális technika intenzív fejlődésével) vált a pedagógusok előtt egyre világosabbá, egyértelműbbé, hogy a taneszköz különösen a taneszközök együtteseinek megjelenése - magasabb hatékonyságot biztosíthat a tartalom feldolgozásában (FORRÁSJEGYZÉK: 3-VI). Az 1970-es évek kutatásai igazolták, hogy a játék, szimuláció és esettanulmány néven ismert gyakorlatok szoros összefüggésben vannak egymással. Ezt elsőként Reid ismerte fel 1977-ben (Ábra 1).

Ábra 1: Reid Az ábra (Ábra 1) egészen pontosan nem Reidtől származik, hanem az ő munkásságát felhasználva Ellington, Addinall és Percival készítette (FORRÁSJEGYZÉK: 3-VII). Az ábráról leolvasható, hogy a játék-szimuláció-esettanulmány gyakorlattípusok hét különböző kategóriába sorolhatóak, amiből 3 „tiszta” és 4 9/67



„hibrid” típusú gyakorlat. Érdemes áttekinteni a 3 alaptípus definícióját, hogy a teljes ábra érthető és világos legyen. A játék Abt (FORRÁSJEGYZÉK: 3-VIII) megfogalmazása szerint a következő: „A játék bármilyen verseny (játékos magatartás, játékos tevékenység) ellenfelek (játékosok) között, amely kényszer (játékszabályok) szerint folyik valamely cél (nyerés, győzelem) érdekében.”. Játékos lehet bármely ember, a feladatot megfogalmazó tanár, avagy egy számítógép is. Shubik (FORRÁSJEGYZÉK: 3-IX) megfogalmazása szerint a szimuláció „…egy rendszernek vagy szervezetnek egy másik rendszerre vagy szervezetre való leképezését foglalja magába úgy, hogy az az eredeti rendszer lényeges viselkedési hasonlóságát tartalmazza. A szimulátor rendszerint egyszerűbb, mint a szimulált rendszer, amely elemzés és kezelés céljaira sokkal alkalmasabb.”. Megjegyzem azonban, hogy számos más definíció is létezik az adott fogalomra. Az esettanulmány (case study) „a valóságos esetekből kiválasztott olyan adatokon alapszik, amelyek alkalmasak arra, hogy helyesen tudjunk bemutatni egy speciális jelenséget, vagy pedig gyakorolni egy különleges döntési eljárást” (FORRÁSJEGYZÉK: 3-X). A kutatók többségének véleménye ma már megegyezik abban, hogy a játékok sorozata, a szimulációk és az esettanulmányok többé-kevésbé átfedik egymást. A hibrid típusú gyakorlatokban pedig egyszerre egy vagy több osztály jellemzői ismerhetők fel, ami hallatlanul növeli a variációs lehetőségek számát a tervezésben. A három nagy osztály között az átfedések teljesek. A játék és szimulációs technikák pontosítására Romiszowski készített egy másik ábrát is (Ábra 2), mely gyakorlati megközelítésben mutatja be az összefüggéseket és kapcsolatokat.

Ábra 2: Romiszowski

10/67



Az Ábra 2-ről az is jól leolvasható, hogy ma már a szimulációs gyakorlatokban a szimulációk és esettanulmányok mellett a szerepjátékok is beletartoznak. Mindezek után megfogalmazhatjuk, hogy milyen elvárásaink lehetnek az „oktatási szimuláció” fogalommal szemben: ¾ legyen modell külső megjelenésében és/vagy hatásában ¾ legyen alkalmas arra, hogy a tanulók tudják kezelni, működtetni (manipulálni) tanulás céljából A modell rendszerint egyszerűsített vázlata az eredeti rendszernek, tárgynak vagy folyamatnak. Egy modellnek a valóságot mindig hűen kell tükröznie, bármilyen aspektusából is vizsgáljuk. A modellből - a valósághoz képest - mindig elhagyhatók azok a részek, amelyeket nem kívánunk tanulmányozni. Az oktatójátékok feladata, hogy segítsék a tanulókat a széles körű és általános oktatási célok - mint az alapjártasságok/készségek, általános ismeretek/tudás - elérésében. A készség (fejlesztő) játékok célja, hogy segítsék a tanulókat bizonyos speciális, sok esetben a munkával (szakmával) kapcsolatos célok megvalósításában. A szimulációs játékok egyszerre kínálják mindazokat a lehetőségeket és módszereket, amelyeket külön-külön biztosítanak a játékok és a szimulációs technikák. A játékok versenyfaktora és a szimulációk sokoldalúsága teszi a szimulációs játékot - nemcsak a nevelésben és oktatásban - kétségtelenül az egyik legsokoldalúbb és leghatékonyabb műveleti eszközzé.

3.3 Lehetőségek és korlátok a hazai játékkultúra kiterjesztésében Külföldön az 1960-as években látható robbanásszerű fejlődés a játék- és szimulációs módszerek terén. Miért nem kapcsolódott be Magyarország ebbe a hullámba? A dolog oka valószínűleg az, hogy nyugaton jó üzleti érzékkel rendelkező emberek fantáziát láttak benne, és támogatták, itthon azonban nem. Az ilyen játékok és szimulációk tervezése, gyártása és forgalmazása jelentős hasznot hoz, és az angolszász országok nagy felvevőpiacával szemben mi nehezen tudunk lépést tartani (egy angol nyelven írt programot könnyebb eladni külföldre, mint egy magyar nyelven írtat). Magyarországon a kis felvevő piac miatt a költséges tervezés és gyártás nem térül meg, így nem éri meg ilyenbe beruházni. Egy esetleges megoldás erre, hogy azon programokat, melyek olyan szakterületbe tartoznak, ahol például az angol elterjedt nyelv (pl. informatika), nem magyarul, hanem angolul készítünk el. Ugyancsak lehetőség van arra, hogy a program változtatása nélkül többnyelvű programot készítsünk egy egyszerű nyelv állomány lecserélésével.

11/67



A magyarországi helyzeten természetesen változtatni érdemes, így más módszereket célszerű keresni. Az egyik ilyen módszer előtt nézzük meg Kupisiewicz lényegre mutató megállapítását: "… nem kizárólag a taneszközök határozzák meg a didaktikai munka és nevelés végső eredményét, viszont gazdagítják az oktatási módszereket, ezáltal hozzájárulnak ezek hatékonyságának növeléséhez…" Nagy Sándor véleménye szerint általánosságban fogalmazva nem a taneszközökre nézve állunk rosszul, hanem a software-ek terén. Külföldön már hosszú idő óta sikerrel használnak úgynevezett „nem hardware” megoldásokat, melyekből Magyarországnak sajnos hiánya van. Legkézenfekvőbb lehetőség, hogy a hiányzó software elemeket pótoljuk, hogy a pedagógusok – esetleg a hallgatóság bevonásával közösen – valósítják meg ezeket.

3.4 A számítógép, mint oktatási eszköz Egy szimulációs feladat bemutatására számos segédeszközünk lehet. Elképzelhető például egy valós fizikai modell. Az ilyen jellegű prezentálása egy problémának valahol a kísérlet és a szimuláció között van. Azonban, ha egy problémát számítógépen mutatunk be (és természetesen „valós” környezetében nem kötődik szorosan számítógépekhez a téma), akkor számítógépes szimulációról beszélhetünk. Vizsgáljuk meg, hogy az oktatástechnológia folyamatába hol kapcsolódik be a számítógép, valamint mik a használatának előnyei, illetve hátrányai (FORRÁSJEGYZÉK: 3-XI). Minden kornak, korszaknak megvannak azon oktatási eszközei, melyek használata „divatos”. Egy időben az írásvetítő volt az, amit felfedezett az oktatás, tanulmányok születtek arról, hogy mennyivel jobb, mint a kréta. Ma ugyanígy a számítógép van ebben a helyzetben. Ennek ellenére a számítógép nem tudja kiváltani az eddigi módszereket, mivel minden módszernek vannak olyan tulajdonságai, melyek kiemelkedőek a többihez viszonyítva. A kréta, vagy a tanár egészségét jobban figyelembe vevő tábla filc használatával a hallgatóság a gondolkodás folyamatát ismerheti meg. Ugyanerre a célra bár léteznek számítógépes megoldások is, véleményem szerint ezek az otthoni tanulás kiegészítésére alkalmasak (felidézi az órán tanár által sorrendben bemutatott feladatmegoldást), nem pedig órai használatara. A tankönyv, mint oktatási eszköz szerepe ma még kiemelkedő, és egyértelműen több előnnyel jár, mint egy úgynevezett e-book, azaz számítógépen olvasható párja. A diák, ha számítógép előtt ül, és olvasnia kell a monitort hosszú órákon keresztül, akkor ennek a tudásnak a hatékonysága nem lesz megfelelő, nem beszélve arról, hogy mind a szeme, mind a gerincoszlopa károsodhat. Sokkal kényelmesebb ágyon feküdni, átfordulni, sétálni, buszon olvasni, élni az életet, miközben bármikor elővehetjük a tankönyvet, hogy tanuljunk, mint adott helyhez fixen kötve elsajátítani az elméleti tudást.

12/67



Véleményem szerint azonban ennek látható a közeljövőben a megváltozása. Kezdenek elterjedni a tenyérgépek (Pocket PC) és a tábla PC-k (Tablet PC), melyek alkalmasak méretüknél fogva arra, hogy szinte bárhol úgy tudjuk forgatni őket, mint egy könyvet, ráadásul egyéb járulékos előnyökkel is jár, melyeket talán említeni sem érdemes (Pl. sokan zenehallgatás mellett hatékonyabban tudnak tanulni, ez egy hordozható számítógép segítségével bármikor elérhető, avagy, csak hogy a legkézenfekvőbbet említsem, egy Tablet PC-n könyvtárnyi irodalmat cipelhetünk magunkkal, így ha hirtelen ahhoz van kedvünk, elolvashatunk egy verset, majd visszatérhetünk tanulmányainkhoz). Térjünk rá a számítógépre. Nyirati László véleménye szerint „csak azokon a területeken lehet az oktatásban hatékonyan felhasználni, amely területeken a mindennapi életben is érezhetően jelen lesz. Mivel várhatóan egyre több ilyen terület jelenik meg, ahol a számítógép szerepet kap, egyre több szempont jöhet az oktatásban is a számítógép, vagy a számítógéppel segített tanulás módszereihez”. Mire is jó egy számítógép az oktatási folyamatban? A kérdés megválaszolása ma már kézenfekvő: ¾ Ahol írásos feladat előkerül, ott a szövegszerkesztők, táblázatkezelők segítségével a tanár munkája kényelmesebb, gyorsabb, egységesebb lesz, melynek hasznát a diákok is megélik. ¾ Az előadásokat kísérő prezentációkat erre alkalmas software-ekkel el lehet készíteni, és projekttor segítségével ki lehet vetíteni. ¾ Szinte nem létezik olyan bemutatható, szemléltethető dolog, melyet nem lehet számítógépre ültetni. Képeket, hangokat, videókat digitalizálhatunk be, és mutathatjuk be a hallgatóságnak számítógép segítségével. ¾ Minden az órán bemutatott, kivetített anyagot a diákok könnyen elérhetik otthon is, amennyiben a tanár elérhetővé teszi azt (pl. Internet segítségével). ¾ Számos szakmai tárgy, mint pl. elektronika, számítástechnika, építészet használ számítógépeket, hiszen maga az ipar is alkalmazza őket. ¾ Amennyiben minden diák számítógép előtt ül az órán, lehetőség van interaktív feladatok megoldására, melyből a tanár azonnal pontos képet kaphat az egyes emberek felkészültségéből, avagy hogy sikerült-e átadnia a tudást, vagy még gyakorlásra szorulnak a hallgatók. ¾ Elsősorban a felsőoktatásban, a rugalmasabb időbeosztás és nagyobb távolságok miatt a tanár és hallgató közötti internetes levelezés (e-mail) a kapcsolattartásnak fontos eleme. ¾ Még bizonyosan lehetne találni felhasználási területeket, azonban legvégül a jelen projekt számára legfontosabbat említsük meg: a számítógépes szimulációt. Két oktatási eszközt szorosan kapcsolni szoktak a számítógépekhez, mégpedig a multimédiát, és az Internetet, így ezekkel is érdemes foglalkoznunk.

13/67



A multimédia szerepét Nyirati László úgy látja, mint a „teljes irodalmat”. Nem tanítható minden egyes könyv az iskolákban (sajnos csak töredéke annak, mint amit minden embernek ajánlott lenne elolvasni), mégis sokan vannak, akik olvasnak iskolán kívül is. A multimédiás anyagok elkészítése sok munkával jár, és kevés sikerrel. Jelenleg még üzletileg sem éri meg, mert általában többletinformációkat tartalmaz, nem pedig a számon kért anyagot, valamint – mint már említettem – nem kényelmes számítógép előtt ülve tanulni. Ennek ellenére a haszna vitathatatlan, az otthoni tanulás remek eszköze, és az iskolán kívüli ismeretszerzést és információgyűjtést gyorsítja, segíti. Az Internethez Nyirati László egy másik hasonlatot hoz fel, miszerint szerepe olyan, mint a TV-é, a haveroké, az utcáé. Az Internettel a diákok, mint társalgási eszközzel találkoznak (számos egyéb lehetőség mellett persze), és mint ilyennek a nevelésre tett hatása kiemelkedő (mint ahogy a TV-nek, haveroknak, utcának). A „jó” tanárnak ezt a saját előnyére érdemes fordítania, megmutatva a diáknak a hatékony és jó irányú felhasználását.

3.5 LabView, mint a számítógépes szimuláció eszköze A „Gráf szimuláció az oktatásban” projektből véleményem szerint nem szabad kihagyni a LabView program rövid bemutatását. A LabView eredetileg folyamatirányításra és mérésadatgyűjtésre szánt alkalmazás volt, mára azonban egy teljes értékű általános programozási nyelv lett. Programozni grafikusan, a Gnyelv szabályait figyelembe véve lehet. A LabView programok (VI-ok) két részből állnak, egy grafikus felhasználói felületből, és a tényleges programot tartalmazó diagramból. Segítségével minimális programozási tudás ismeretében lehet többek között szimulációs feladatokat is készíteni. Aki jártas magas, avagy alacsony szintű programozási nyelvekben, annak sokszor körülményes lehet megoldani egy adott problémát folyamatmodell segítségével, ezért van lehetőségünk arra is, hogy a LabView VI programunkba beékeljünk C++ forráskódot! Bár a projekt céljától eltér a LabView programok elemzése, megemlítem, hogy volt szerencsém egy úgynevezett „Inverted Pendulum” feladat megoldását elvégezni Norvégiában LabView segítségével. Az „Inverted Pendulum” egy irányítástechnikai probléma, melyet egy seprű egy ujjon való egyensúlyozásához tudnék hasonlítani. Ezt a feladatot kell egy modell, egy a modellt állandóan vevő kamera, és a számítógépen futó LabView program segítségével megoldani. A működő szimulációs feladat eredménye, hogy a számítógép gyakorlatilag bármeddig képes „egyensúlyozni a seprűvel”, amíg a fényviszonyok megfelelőek (kamera képe miatt fontos). A fenti program bemutatása rendkívül terjedelmes lenne, ezért szemléltetésképpen egy sokkal egyszerűbb feladatot fogunk elkészíteni LabView programban. A feladat legyen az, hogy megadott két számot kivonunk egymásból, de minden esetben a nagyobbat vonjuk ki a kisebből (a feladatnak számos különböző megoldása van, mi egyet mutatunk most be)! 14/67



A probléma matematikai hátterével természetesen senkinek sincs problémája, a szimuláció célja nem is a felhasználhatóság, csupán a LabView bemutatása. Legelső lépésben megtervezzük a grafikus felületünket. Szükségünk lesz két olyan mezőre, ahova beírhatjuk a két számot, valamint egy olyanra, ahol az eredmény megjelenik (Ábra 3).

Ábra 3: LabView Front panel A STOP gomb szerepe az, hogy a programunk addig fog futni, míg a STOP gombot meg nem nyomjuk. Ha ezzel kész vagyunk, akkor el kell készíteni a tényleges programot. Ezt az (Ábra 4) tartalmazza.

15/67



Ábra 4: LabView Black Diagram Ha futtatjuk a programunkat (Ábra 5 és Ábra 6), akkor megfigyelhetjük, hogy függetlenül attól, hogy melyik mezőbe írunk nagyobb számot, a végeredmény minden esetben a két szám különbségének abszolút értéke lesz (a feladatot természetesen abszolút érték jel használatával is meg lehetett volna valósítani).

Ábra 5: Futás eredménye I

Ábra 6: Futás eredménye II

16/67



4 – GRAPHS AND SPANNING TREES 4.1 - A programról általában A Graphs and spanning trees (Gráfok és feszítőfák) alkalmazás egy szimulációs program. Modellezni lehet vele a gráfok problémakörébe tartozó feladatokat. Ide lehet sorolni egy egyszerű matematikai problémától kezdve egy összetett térképprogramig mindent, sőt, akár elvont fogalmak szintjén értelmezve, gráfok segítségével akár gondolkodásmód is bemutatható! Az alkalmazás egy úgynevezett MDI Application, azaz egy többdokumentumos alkalmazás, mint például a Microsoft Word, vagy az Adobe Photoshop. Ebből következik, hogy egyszerre több gráffal is tudunk dolgozni általa, és mindegyiket egymástól függetlenül tudjuk kezelni. A gráfnak tudunk új csomópontokat, új éleket felvenni, módosítani, avagy törölni. Be tudjuk állítani a gráf típusát, tulajdonságait és bizonyos mértékig konvertálni is tudunk gráfokat. Személyre szabhatjuk, hogy a három dimenzióban mozgó gráfunk képén milyen információk jelenjenek meg, és mindezek milyen színnel, betűtípussal, stb. Képesek vagyunk adott feltételek megadása mellett kapcsolatmátrix készítésére, valamint ha ezt megtettük, akkor Dijkstra algoritmusa segítségével meg tudjuk bármely két pont között határozni a legrövidebb utat (adott súly szerint). A program a későbbiekben szomszédsági listák elkészítésére is alkalmas lesz, valamint többféle útkereső algoritmust fog tudni kezelni. Mélységi és szélességi bejárás alapján tudunk majd információt keresni, és lehetőségeink között lesz a gráf alapján egy feszítőfa elkészítése is. Az útkeresés során számos információt tudunk gyűjteni, mely listázása nehézkesen átlátható. Tervbe van véve egy script nyelv elkészítése, melynek segítségével a töménytelen információt szűrni fogjuk tudni. Mindenezek lehetőségek felsorolásszintű bemutatása után egy nagyon fontos dologot meg kell említeni: mik is azok a gráfok valójában? Ahhoz, hogy a gráfokkal dolgozzunk, hogy felhasználjuk őket munkánk, tanulmányaink során, néhány alapfogalommal tisztában kell lennünk. Az alkalmazés későbbi verzióiban ezen előtanulmányokat a felhasználó is megteheti majd interaktív bemutató keretében!

4.2 Gráf, mint matematikai fogalom 4.2.1 Néhány alapfogalom • Hurok él: olyan él, melynek kezdő és végpontja azonos csúcsból indul, illetve érkezik. • Szomszéd pontok: A és B szomszéd pontok, ha a gráfban van él A és B között • Fokszám: Megadja, hogy egy adott pontra hány él illeszkedik.

17/67

Gráf szimuláció az oktatásban • •


Izolált pont: olyan pont, amelyre nem illeszkedik él, azaz fokszáma nulla. Többszörös élek: Ugyanazon kezdő és végpontokat tartalmazzák.

4.2.2 - Gráfok Sokféle gráf létezik (a gráf egy absztrakt adatszerkezet), és mindegyiknek megvan a maga felhasználási területe. Csak felsorolás szinten nézzük ezeket végig: • Egyszerű összefüggő gráf • Egyszerű nem összefüggő gráf • Irányított összefüggő gráf • Irányított nem összefüggő gráf • Súlyozott összefüggő gráf • Súlyozott nem összefüggő gráf • Irányított és súlyozott összefüggő gráf • Irányított és súlyozott nem összefüggő gráf • Speciális gráf (hurokmentes, minimum távolság limit, többszörös élek stb…) Természetesen a teljesség igényével azok vannak felsorolva, melyekkel már találkoztam. A program mindegyik gráftípust támogatni fogja. Egy adott problémának a szimulálásához nekünk majd a megfelelő modellt kell megépítenünk. Például egy térképprogramhoz nekünk egy súlyozott és irányított összefüggő gráfra lesz szükségünk, ami nem hurokmentes, tartalmazhat többszörös éleket. 4.2.3 - Gráfok ábrázolása Gráfok ábrázolására is többféle módszer létezik, és a legtöbb esetben függ a gráf típusától. Nézzünk először egy egyszerű gráfot, amit statikus adatstruktúrával tárolunk (nagyon redundáns megoldás). A kapcsolatmátrixszal történő tárolást a (7. ábra) mutatja. X 1 2 3 4 5 6 7

1 H I H I H H H

2 I H I H H I H

3 H I H I I H H

4 I H I H H H H

5 H H I H H I I

6 H I H H I H I

7 H H H H I I H

7. ábra - Kapcsolatmátrixos ábrázolás Talán jól látszik az ábráról pár dolog: • Egy adott i, j a mátrixban I (igaz) vagy H (hamis) érétket vehet fel.

18/67

Gráf szimuláció az oktatásban • • •


Adott i, j igaz lesz, ha i és j között létezik él. A főátlón lévő értékek mindig hamisak, amennyiben a gráfban nincsenek hurok élek. A statikus mátrix a főátlóra szimmetrikus.

Lehetőség van dinamikus tárolásra is, ezt a (8. ábra) alapján lehet elképzelni.

8. ábra - Szomszédsági lista Ezt a tárolási elemet nevezik szomszédsági listának. A harmadik lehetséges módszert már nem rajzolom fel, de könnyen el lehet képzelni egy teljesen dinamikus struktúrát, melynél a statikus mutató vektort felváltja egy olyan dinamikus adatszerkezet, mely elemeinek két mutató mezeje van. Tegyük fel, hogy az új gráfunk súlyozott és irányított, vannak benne többszörös élek. Ekkor a kapcsolatmátrixát a (9. ábra) prezentálja (a gráf ábrája nem méretarányos). X 1 2 3 4 5 6 7

1 0 20 0 10 0 0 0

2 0 0 25 0 0 0 0

3 0 0 0 0 35 0 0

4 10 0 5 0 0 0 0

5 6 7 0 0 0 0 40 0 35 0 0 0 0 0 0 15 0 0 0 30 17 30 0

9. ábra - Súlyozott, irányított gráf Ami látszik a kapcsolatmátrixról: • Megszűnt a szimmetria az irányítottság miatt. • Csak ott szimmetrikusak az értékek, ahol többszörös él van. • Ott, ahol nincs él, ott 0 szerepel.

19/67



4.2.4 - Minimális költségtérítésű feszítőfa A feszítőfa fogalma: Egy g gráfnak egy másik F gráf feszítőfája, ha F tartalmazza G összes pontját, további pontokat nem tartalmaz és G élei közül annyit tartalmaz, amennyi F-et összefüggővé teszi, de F körmentes (fa). A minimális költségű feszítőfa fogalma: Egy G gráf minimális költségű feszítő fája az a fa-gráf, amely feszítőfája G-nek, és G összes lehetséges feszítőfája közül éleinek összes hossza a legkisebb (elképzelhető több megoldás is). Algoritmusa MinfeszFa(i) PriSorInit(Sor) Segéd.pont:=i Segéd.súly:=0 PriSorBa(Sor,Segéd) Érintett(i):=0 Ciklus PriSorBól(Sor,Segéd) i:=Segéd.pont ÉletBeilleszt(Fa,Érintett(i),i) Ciklus j:=1-től N-ig Ha A(i,j)>0 akkor Ha Érintett(j)=NEMÉRINTETT akkor Segéd.pont:=j Segéd.súly:=A(i,j) PriSorba(Sor,Segéd) Érintett(j):=i különben VanRövidebb(Sor,j,A(i,j),Volt) Ha Volt akkor Érintett(j):=i elágazás vége elágazás vége elágazás vége Ciklus vége amíg nem(PriSorÜres(Sor)) Eljárás vége

20/67



Megjegyzések: NEMÉRINTETT az az érték, amely jelzi, hogy egy adott pontot a bejárás során már érintettünk, vagy sem. Kezdetben Érintett() vektor minden eleme ezt tartalmazza. Életbeilleszt (G,x,y) a G gráfba az x,y pontok közé élet illeszt be VanRövidebb (Sor,a,b,Volt) megvizsgálja, hogy szerepel-e az „a” pont a prioritási sorban, ha igen, akkor megvizsgálja, hogy a „b” súlynál nagyobb-e az ott szereplő pont súlya. Ha igen, akkor kicseréli ezt a pontot az „a” pontra, amelynek „b” a súlya. Ha a sor így módosul, akkor Volt=igaz lesz. 4.2.5 - Legrövidebb út Fogalama A legrövidebb út fogalmát kétféleképpen értelmezhetjük: • A kiindulópontból a végpontig milyen úton kell haladnunk, hogy kevesebb csomóponton lépjünk át, mint bármely más úton? Ennél a feladatnál akár súlyozatlan, akár súlyozott, kezelhetjük úgy a gráfot, mintha éleinek hosszúsága (súlya) egységnyi lenne. • A kiindulópontból a végpontig milyen úton kell haladnunk, hogy az utat alkotó élek összes hossza kisebb legyen, mint bármely más út esetén? Ennél a feladat természetesen súlyozott gráfot feltételez. Egyértelműen látszik, hogy a második eset sokkal általánosabb, ráadásul a térképprogramhoz is ez van közelebb, így ezzel foglalkozok a továbbiakban. A probléma megoldására számos algoritmust dolgoztak ki. Ezek közül alapvetőnek számít a neves holland matematikus Dijkstra 1959-ben közölt algoritmusa, ezért itt is ezt ismertetem. Az algoritmus lényege Lássuk el a gráf minden pontját egy címkével, amely a következő adatokat tartalmazza: • a pillanatnyilag ismert legrövidebb úton az adott pont milyen távolságra van a kiindulóponttól (kezdetben legyen ez az adat minden pont esetén végtelen nagy) • az adott pontnak melyik az a szomszédos pontja, amely felől haladva az előbbi távolságot kaptuk Egy csomópont címkéje kétféle lehet: • ideiglenes: még lehetséges, hogy más irányból rövidebb utat is találunk hozzá a kiindulópontból 21/67



•

állandó: a kiindulópontból már minden hozzá vezető utat megvizsgáltunk, s rövidebb út nem lehetséges Az algoritmus lényege az, hogy meghatározzuk minden pont legrövidebb távolságát a kiindulóponttól számítva, s mivel minden pont címkéje tartalmazza azt is, hogy ezen úton melyik pont előzi meg, a végponttól visszafelé haladva meghatározhatjuk a két pont közötti legrövidebb utat. Nézzük ezt most egy példán keresztül (10. ábra).

22/67



10. ábra - A legrövidebb út algoritmus Az algoritmus részletesebben 1. Inicializáljuk a gráf-pontok legrövidebb útjait tároló adatszerkezetet. 2. Az aktuális pont legyen a kiinduló pont 3. Járjuk be az aktuális pont minden ideiglenes szomszédját (szélességi bejárás). Ha találunk olyan szomszéd pontot, amelyhez az aktuális pont felől rálépve rövidebb úton jutnánk el a kiinduló ponttól, mint a címkében rögzített korábbi irányból, akkor e pont címkéjét módosítjuk. A módosítás: a kezdőponttól mért távolságnak beírjuk az új irányból mért távolságot, a megelőző pont helyére pedig az aktuális pontot. 4. A gráf összes ideiglenes címkéjét megvizsgálva kiválasztjuk azt a pontot, amely az ideiglenesek közül a legrövidebb úton érhető el a kezdőpontból, vagyis azt, amelyiknek a címkéjében a hosszúság értéke a legkisebb. E pont címkéjét véglegesre állítjuk, ezzel jelezve, hogy e ponthoz nem vezethet a már bejegyzettnél rövidebb út. 5. Legyen most az így kiválasztott pont az aktuális.

23/67



6. Ismételjük a 3. résztől a műveletet egészen addig, amíg az aktuális pont azonos nem lesz a végponttal. Az algoritmus pszeudokódja LegrövidebbÚt (A, kezdő, vég, N) Init(állapot) aktuális:=kezdő állapot[aktuális].hossz:=0 állapot[aktuális].címke:=VÉGLEGES ismétlés SzomszédokBejárása(A,N,aktuális,állapot) aktuális:=Minimum(állapot,N) állapot[aktuális].címke:=VÉGLEGES amíg aktuális=vég EredményKiírása(állapot,kezdő,vég) Eljárás vége SzomszédokBejárása(A,N,aktuális,állapot) Ciklus i:=1-től N-ig Ha (A[aktuális,i]<>0) és (állapot[i].címke=IDEINGLENES) akkor Ha (állapot[aktuális].hossz+A[aktuális,i])<állapot[i].hossz akkor állapot[i].előző:=aktuális állapot[i].hossz:= állapot[aktuális].hossz+A[aktuális,i] Elágazás vége Elágazás vége Ciklus vége Eljárás vége A fenti algoritmusban ’A’ jelöli a gráf kapcsolatmátrixát, ’N’ pedig a gráf pontjainak számát.

24/67



4.3- Felhasználói kézikönyv

11. ábra: Képernyőkép indítás után 4.31 - Új gráf létrehozása A [File|New graph] (File menü New graph parancsa) hatására a gráf tulajdonságait beállító ablakot láthatunk (12. ábra). Itt számos adatot megadhatunk, mely a gráfunk működését a jövőben erősen befolyásolni fogja. Vannak olyan tulajdonságok, melyek csak itt állíthatóak, és vannak, melyek módosítására a program későbbi részén is lesz lehetőség.

25/67



12. ábra: Új gráf létrehozása A gráf nevét (Name of graph) mindenképp adjuk meg, különben NonameGraph lesz a munkánk neve, és amennyiben ezt a nevet meghagyjuk, a következő NonameGraph felülírhatja ezen gráfunkat (amennyiben nem adunk meg nevet, a program figyelmeztet minket, hogy a későbbiekben ne felejtsük beállítani). A gráf neve lesz elmentés után egy könyvtár neve, benne számos különböző kiterjesztésű file-lal, melyeknek a nevük szintén az itt megadott (a gráf betöltéséhez természetesen minden file-ra szükségünk lesz). A gráf típusát se felejtsük el beállítani (Type of graph). Négy alapvetően különböző gráfot ismer a program. Az egyszerű gráf (Simple graph) pontokból, és azokat összekötő élekből áll. Az irányított gráf (Guided graph) éleinek irányítottságot adhatunk, a súlyozott gráf esetén (Weighted graph) pedig súlyértékeket. Az utolsó lehetőség az utóbbi kettő kombinációja (Guided weighted graph), mely például egy térkép program szimulációjához is szükséges lehet. Beállíthatjuk a tárolás típusát (Storage), hogy statikus, avagy dinamikus legyen-e, de ez a lehetőség még nincs kihasználva. Egyelőre minden gráf teljesen statikus adatszerkezetekből épül fel. A többszörös élek (Multiple edges) engedélyezése, illetve tiltása még szintén nincs implementálva. Nagyon fontos, és csak itt megadható tulajdonsága egy gráfnak a grafikus mérete! Ez egy kép méretét jelenti, melyre a gráf csomópontokat elhelyezhetjük

26/67



három dimenzióban. Minimálisan ez az érték 300 (nem is enged a program kisebb értéket megadni), azaz egy 300x300x300-as kockában tudunk dolgozni, mégpedig koordináták nyelvén szólva mind az X, Y és Z tengely esetén az értelmezési tartomány a (-150;150) intervallum. Egy megjegyzést is tárolhatunk minden gráf esetén (Comment), melynek a megadása természetesen nem kötelező. Mindezek mellett lehetőségünk van két lista elkészítésére is még szintén ebben az ablakban: gráf pontok adatai (Data of graph points) és súlyvektor beállítása (Multiple weights). Mindkét esetben tíz elemet vehetünk fel a listába (statikus esetben), és minden elemnek beállíthatjuk a nevét (Item name), típusát (Item type) és alapértelmezett értékét (Default value)(13. ábra). A név alapján tudjuk majd azonosítani. Az alapértelmezett érték megadása nem kötelező (ha nem adjuk meg, beállít helyettünk egy értéket a program). De mire is jók ezek nekünk?

13. ábra: Új elem hozzáadása a gráf-pontok illetve a súlyvektor listájába Minden gráf pont esetén tárolhatunk tíz különféle értéket az adott típusnak megfelelően, melyeket aztán script programok írása esetén fel tudunk használni, és/vagy modellezés során hasznos információkkal tudjuk ellátni a gráfunk csúcspontjait. Térképprogram esetén például, itt tárolhatjuk majd az olyan kiegészítő információkat, hogy az adott pont most egy járdán van-e, avagy egy zebrán, stb. Az élek esetén ugyanezen az elven működik a súlyvektor megadása. Nem csupán egy súly tartozhat egy élhez, hanem minden élhez egy maximum tízelemű vektor tartozik (statikus esetben). Térképprogram esetén egyik súly tárolhatja a két gráf pont közötti út hosszát, egy másik az adott úton a maximális haladási sebességet, a harmadik azonosíthatja a felület típusát (aszfalt, földút, stb.), stb. Lényegében a KRESZ szabályok figyelembevétele e két lista segítségével megvalósulhat, amennyiben a szimulációs programmal egy komolyabb térképprogram motorját szeretnénk elkészíteni! Ezt a két listát még a későbbiekben is tudjuk majd szerkeszteni.

27/67



14. ábra: Egy létrehozott új gráf 4.3.2 - Gráf megnyitása A [File|Open graph] hatására egy standard file megnyitó ablakban a (*.grp) file-okat tudjuk megnyitni. Ez egy szöveges állomány, mely lényegében a gráf alapvető tulajdonságait tárolja. Szükséges, hogy abban a könyvtárban, ahonnan megnyitottuk a *.grp file-t, legyen további öt azonos nevű állomány is (*.das, *.dat, *.edg, *.pnt, *.was)! Ezen állományok mind egytől egyik binárisak. 4.3.3 - Globális beállítási lehetőségek A program számos beállítási lehetőséggel rendelkezik, melyek minden megnyitott gráfra hatással vannak. Ezeket a [Setting] menüben találhatjuk. Nézzük elszőször a [Setting|Show information on graph] menüpontot. Itt azokat a vizuális tényezőket tudjuk beállítani, mely a gráfunkon megjelenő adatok kinézetét befolyásolják (15. ábra).

28/67



15. ábra: Megjelenítési beállítások A gráf grafikai megjelenése és azon információk, melyek a gráfon megjelennek egymástól függetlenül kezelhetők. Meg lehet adni, hogy az egyes gráf pontoknál, valamint az egyes élek esetén milyen információ jelenjen meg. Beállíthatjuk, hogy a pontok illetve élek sorszáma (Serial of graph points/Serial of graph edges), avagy neve (Name of graph points if allow/Name of graph edges if allow) jelenjen meg, és lehetőségünk van kikapcsolni mindenféle információ megjelenítését is (none). Továbbá megadhatjuk, hogy valamelyik adatmező, illetve súlymező jelenjen meg (One datum of graph points/One weight of graph edges). Amennyiben a gráf pontok vagy az élek nevét állítjuk be, és vannak olyan pontok/élek, melyeknek nincs beállítva név érték (majd később visszatérünk arra, hogy mit lehet beállítani az egyes pontok és élek esetén), akkor nem jelenik meg semmi az adott pontnál/élnél. Meg lehet adni a gráfok hátterének színét (Background color), valamint hogy a gráfon megjelenő szövegek háttere felülírja-e a képet, vagy ne (érdemes kipróbálni, hogy ki melyik variációt látja át jobban)(Texts overwrite the graphics). A gráfon megjelenő feliratok színét egyesével meg tudjuk adni. Ehhez kattintsunk az adott rádiógomb melletti kis színezett téglalapra. Van arra is lehetőségünk, hogy egy kattintásra minden él és gráf-pont színét egy előre megadottra állítsunk be (Use adjusted colors). Ezáltal bináris képet kaphatunk (ha kikapcsoljuk a feliratokat, vagy beállítjuk azokat is erre a színre). Az élek és a gráf-pontok színét egyesével tudjuk majd beállítani felvételükkor. Mindenféle felirat betűtípusa egységes. Ezt a „Set font” gombra kattintva tudjuk beállítani. 29/67



Utolsó lehetőségként - ebben a menüben - az út színét adhatjuk meg (Way color). Ez lesz a színe azon éleknek, melyek az útkeresés eredményében „részt vesznek”. Térjünk át a [Setting|Global constants] menüpontra. Itt a legtöbb tényező csak információt közöl a felhasználóval, beállítani egyáltalán nem, vagy majd csak a program későbbi verzióban lesz lehetséges (16. ábra).

16. ábra: Globális konstansok és változók A statikus jellegből adódóan gráfunknak vannak bizonyos számbeli korlátai. Ezeket átállítani csak forráskód szinten lehet, ezért a felhasználó csak mint információ láthatja. Nézzük ezek magyarázatát sorban: • Maximális elemszáma a súlyvektornak és a pontokban tárolható adat tömbnek (Max item of weights and data). • Legfeljebb ennyi gráf-pont lehet a gráfunkban (Max graph points). • Legfeljebb ennyi él lehet a gráfunkban (Max graph edges). • Egy adott gráf-pont nem csupán egy grafikai pontnak felel meg, mivel egy kis 3D-s objektummal jelöljük meg a képen. Emiatt egy felső korlátja van ennek is. Célszerűen ez a szám lényegesen magasabb, mint a gráf-pontok maximális száma (Max graphic points). Az irányított él esetén maga az él is tartalmaz további grafikai pontokat (a nyíl miatt)! • Az előző alapján a maximális grafikai élek száma is korlátozott (Max graphic edges). • A program által használt egyedi szoftveres 3D motor képes úgynevezett robotkar kezelésére. Egy konstans meghatározza azt, hogy maximum mennyi kartagja lehet a robotunknak. Ez fixen három ebben a programban, mivel nincs kihasználva a 3D motor ezen funkciója (Max arm of 3D objects). 30/67



•

Manuálisan tudunk készíteni egyedi mintákat arra nézve, hogy egy gráfpont hogyan nézzen ki. Egy konstans tárolja, hogy egy ilyen minta maximum mennyi grafikai pontból állhat. A grafikai élek száma nincs korlátozva (Max graphic points of each shapes). Ugyanitt le tudjuk olvasni a sémák listáját tároló szöveges file nevét (Shape List file name), valamint az alapértelmezett könyvtárát a sémáknak (Shape files directory) és a gráfoknak (Save directory). A jelenlegi verzióban még két változó értékét tudjuk leolvasni és módosítani (!) a „Global constants” menüben: az irányított él két grafikai paraméterét (Directivity Length és Directivity Length 2). Ezek funkcióját leírni nehézkes, célszerű kipróbálni, hogy módosításukkal mi változik a képen (a nyíl különböző mérete fog változni irányított gráfok esetén). 4.3.4 - Lokális beállítások Létrehozva, avagy megnyitva egy új gráfot a menüsor kiegészül számos új elemmel. A [Local Setting] menüben a gráf forgatásáért felelős grafikai ablak egy vizuális effektjét tudjuk ki, illetve bekapcsolni (Allow animated frame/Forbid animated frame). Vizsgáljuk meg közelebbről a gráf forgatásáért felelős gombokat. Az X, Y, Z tengelyek körüli forgatásra vonatkozik a gráf megjegyzése alatt található hat nyomógomb. A szerkesztési mezőben megadható szám jelzi, hogy egy kattintásra hány fokot fordul el a gráf. A piros bal és jobb nyíl egy előre beállított ’u’ tengely körül forgatja a gráfot egy fokonként. A kis földgömbre kattintva automatiusan két tengely körül forogni fog a gráfunk (X és U tengely körül). A „Refresh” gomb bármikor hasznos lehet, ha úgy érzékeljük, hogy a módosításunk nem látható jelenleg még a gráfon. Ha a „Refresh” (frissítés) hatására sem jelentkezik a változás, akkor a hibát máshol keressük. 4.3.5 - Új gráf pont felvétele Az [Edit|Add new junction (graph point)] menüpontra kattintva tudunk az aktuális gráfunkhoz új csomópontot felvenni. Itt kell beállítanunk mindent, ami a gráf ponttal kapcsolatos (17. ábra).

31/67



17. ábra: Új gráf pont hozzáadása A pont koordinátáinak (coordinates) (X,Y,Z) felvétele történhet manuálisan, de van lehetőség az (X,Y) sík vizuális megadására is a ’#’ gombra kattintva (18. ábra) Az itt megjelenő pontok a már felvitt gráf pontokat jelképezik a könnyebb tájolás érdekében!.

32/67



18. ábra: Koordináta grafikus beállítása A sorszám (serial) mező automatikusan generálódik, szerkeszteni nem tudjuk, azonban adhatunk egy egyedi azonosítót (nevet) a csomópontnak (name), amennyiben ezt engedélyezzük (Allow name). Már említettem, hogy minden ponthoz tartozik egy 3D-s objektum, mely grafikusan fogja jelölni a képen a csomópontot. Ezt a ’Design’ panelen tudjuk beállítani. A piros bal és jobb irányú nyilakkal tudunk váltani az elérhető minták között (shape). Ilyen mintákat manuálisan bárki képes készíteni (*.shp file-ok). A program későbbi verziójában lesz lehetőség program szinten is minták létrehozására. A gráf pont színét a színes téglalapra kattintva tudjuk beállítani.

33/67



Minden gráf pont tartalmazhatja azon adatokat, melyek a gráf tulajdonságai között definiálva vannak. A bal oldali listában (Data of graph point) kiválasztva az adott elemet, majd az szerkesztési mezőbe egy értéket írva (Value), végül a ’Set’ gombra kattintva az adott csomópontnak felvittük az új adatát. A jobb oldali listában láthatjuk a beállított értékeket. Kezdetben ezek a gráf tulajdonságai között beállított alapértelmezett értékek lesznek (Default value). 4.3.6 - Új él felvétele a gráfba Miután felvittünk pár csomópontot a gráfunkba, felmerülhet az igény élek elhelyezésére is ([Edit|Add bew edge])(19. ábra). Egy gráfban él csak két csomópont között mehet. Ezt a két pontot a ’List of points’ gombokra kattintva tudjuk megadni (20. ábra). Irányítatlan gráf esetén lényegtelen, hogy melyik az egyes, és melyik a kettes pont, ellenben irányított esetben a ’Directivity’ részben ennek szerepe van! Amennyiben egy irányított élnek nem állítunk be irányítottságot (none), akkor ez olyan lesz, mintha lenne egy él A-ból B-be, és Bből A-ba is.

19. ábra: Új él felvitele A sorszám (Serial), az egyedi azonosító (name, Allow name) és a szín megadása hasonlóan történik, mint a gráf pontjai esetén. A súlyvektort a gráf súlyvektor tulajdonsága alapján tudjuk feltölteni szintén még ebben az ablakban.

34/67



20. ábra: Gráf pont kiválasztása 4.3.7 - Gráf pontok és élek módosítása illetve törlése Utólag lehetőségünk van a felvitt gráf pontok és élek teljes szerkesztésére, és törlésére is ([Edit|Edit junction][Edit|Edit edge][Edit|Delete juction (with edges)][Edit|Delete edge]). Mindegyik esetben egy listából ki kell választanunk, melyik elemmel szeretnénk dolgozni. Grafikus kijelölésre itt még nincs lehetőség. Él esetén segédinformációként kiválasztáskor megjelenik az általa összekötött csomópontok sorszáma és neve is (21. ábra)

21. ábra: Él kiválasztása

35/67



A törlés logikai, azaz fizikailag az adott csomópont illetve él nem törlődik a gráfból, csak a felhasználó többé már se látni, se szerkeszteni nem tudja. A program jelenlegi verziójában a fizikai törlés még nem készült el. 4.3.8 - Gráf tulajdonságainak utólagos beállítási lehetősége Ha utólag rájöttünk, hogy a gráfunk tulajdonságai nem a legoptimálisabbak feladatunk megoldására, néhány dolgot a [Data|Display data of graph] menüpont alatt át tudunk állítani (22. ábra).

22. ábra: A gráf tulajdonságai Adhatunk új nevet a gráfnak (gyakorlatilag így lehet elmenteni más néven a gráfot), megjegyzést és típust! A típus változásával óvatosan bánjunk, számos információt veszíthetünk általa. A csomópont adatvektorát, valamint a súlyvektort is tetszés szerint módosíthatjuk. 4.3.9 - Az aktuális súly illetve gráf pont adat beállítása Egyszerre nem jeleníthetünk meg egy élen több információt, avagy egy csomópontban több adatot. Amennyiben a [Setting|Show information on graph] menüpontban az adat- illetve súlyvektor megjelenítését jelöltük be, akkor megadhatunk egy aktuális adatot, és egy aktuális súlyt, mely a gráfon grafikailag is látszani fog. Ezt a [Format|Set current weight] menüpontban illetve a [Format|Set current data] menüpontban tehetjük meg (23. ábra).

36/67



23. ábra: Aktuális súly beállítása 4.3.10 - Gráf mentése A programban nincs automatikus mentés, és figyelmeztetni sem figyelmeztet mentésre (a jelenlegi verzió). A [File|Save graph] menüpontra kattintva a beállított gráf könyvtárba a megadott gráf névvel egy könyvtár jön létre, benne számos file-lal, melyek a gráfunk különböző adatait tárolják. Ha másodszor is elmentjük a programot azonos névvel, akkor a program figyelmeztet arra, hogy az előző állapot el fog veszni. A gráf átnevezésével (4.3.8 fejezet) ez a probléma elkerülhető. 4.3.11 - Kapcsolatmátrix generálása Számos ábrázolási formája létezik a gráfoknak. Amit a Graphs and spanning trees valósít meg, az egy teljesen egyedi TGraph nevű osztályon alapul. Lényegesen több információt képes tárolni ez a szerkezet, mint mondjuk egy hagyományos kapcsolatmátrix, bár tény, hogy maga a TGraph osztály megvalósítható lenne úgy is, hogy alapja egy kapcsolatmátrix! Ellenben egészen máshogy épül fel a TGraph osztály, melynek azonban része egyetlen statikus kapcsolatmátrix is. Az egyetlenen azért van hangsúly, mert minimum annyi mátrix kellene, amennyi súlyunk létezik. Mi itt generálni vagyunk képesek kapcsolatmátrixot egyetlen súly (vagy opcionálisan más adat) alapján a [Data|Static relation matrix] menüpontra kattintva (24. ábra).

37/67



24. ábra: Statikus kapcsolatmátrix generálása A két legördülő lista segítségével be tudjuk állítani, hogy a gráf pontok sorszáma (Show serial of points), vagy a neve jelenjen-e meg (Show name of points if allow). Ha nem állítottunk be egy csúcspontnál nevet, akkor a sorszáma fog megjelenni. A másik legördülő listában szintén kiválasztható, hogy mely súly értékei jelenjenek meg a kapcsolatmátrixban. Sőt, megadható az is, hogy az élek sorszáma jelenjen meg, avagy a nevük! Természetesen ezen utóbbi esettel számolni nem tudunk, csupán egy nézetet biztosíthat számunkra, melyet a program későbbi verziójában majd ki fogunk tudni használni, ott ugyanis lehetőség lesz a kapcsolatmátrix szerkesztésével módosítani a gráf adatait! Bezárva az ablakot (OK gombra kattintva) kapunk egy visszajelzést, hogy a gráf kapcsolatmátrixa elkészült-e! Mivel ezzel a későbbiekben számolni fogunk, ezért nem készül kapcsolatmátrix hogyha nem valós számok szerepelnek a súly értékei között. Az elkészült kapcsolatmátrix ellenőrizhető a [Pathfinding|Show relation matrix] menüpontra kattintva (25. ábra).

38/67



25. ábra: A kapcsolatmátrix 4.3.12 - Legrövidebb út meghatározása Dijkstra algoritmusa alapján Ha elkészítettünk egy kapcsolatmátrixot, lehetőségünk van legrövidebb út keresésére. A program jelenlegi változatában Dijkstra algoritmusát implementáltam. A [Pathfinding|Simple pathfinding] menüpontra kattintva (26. ábra) a kiindulási (Start point) és a cél pontot (Destination Point) lehet megadni az útkereső algoritmusnak („Set” gomb segítségével), valamint be kell állítanunk, hogy az útkeresés során használja a már memóriában lévő kapcsolatmátrixunkat.

39/67



26. ábra: Útkeresés kapcsoaltmárix segítségével A ’GO’ gombra kattintva az út (természetesen amennyiben létezik) elkészül. Az ehhez szükséges eredmény adatszerkezet megjelenik a szövegterületben (innen az algoritmus ismeretében számos plusz információ is leolvasható). Bezárva az ablakot (’OK’ gombbal) a gráfunkon a megtalált út a beállított színnel meg fog jelenni (27. ábra).

40/67



27. ábra: Legrövidebb út A és C pont között Ezzel a rövid bemutatóval végig is szaladtunk a program legalapvetőbb funkcióin, azonban a program nem csak ennyit tud! 4.3.13 – Szerkesztés gyorsítása A legnagyobb probléma gráfok szerkesztése során az adatfelvitel. Ha nagy gráfot szeretnénk készíteni, nagyon sok időre van szükség, míg minden egyes gráf pontot felviszünk, és minden egyes ezekhez tartozó élet. A gyakorlatban azonban ezen pontok és élek tulajdonságainak nagyon nagy része megegyezhet. Ennek érdekében készültek a programhoz olyan szerkesztők, melyek pontok és élek egyidejű felvitelét teszik lehetővé az előbbi módszerhez viszonyítva rendkívüli sebességgel! Ez azt jelenti, hogy egy pár száz gráf pontból és pár száz élből elkészített gráf háló negyed óra alatt elkészítehető! Válasszuk ki az [Edit|Junctions and Edges Editor] elnevezésű menüpontot (28. ábra).

41/67



28. ábra: Él és pont szerkesztő Ez a menüpont sokkal többet tud, mint amit első ránézésre gondolnánk! A bal felső sarokban beállíthatjuk, hogy mit szeretnénk felvenni (Junctiont, azaz pontot, Edge-t, azaz élet), illetve hogy szeretnénk e grafikusan szerkeszteni a már felvitt elemeket (Edit mode)! Alatta kiválaszthatjuk, hogy a majd felvitt gráf pontok milyen grafikai formát öntsenek, illetve milyen színűek legyenek (a szín élekre is vontkozik). Az „Edges and Junctions Data” résznél megadhatjuk a következő felviendő gráf pont, illetve él 3D-s Z koordinátáját (az X és Y koordinátákat grafikusan tudjuk majd beállítani!), valamint megadhatjuk az elem nevét is. Láthatunk két kijelölő négyzetet is. Ha az Edges mellett pipa van, az azt jelenti, hogy az ábrán az élek látszani fognak. Ugyanígy ha a Serials mellett is pipa van, akkor a gráf pontok sorszáma fog látszódni a 3D-s gráf vetületi képén! A Step mezővel az érzékenységet tudjuk beállítani. Ez majd arra lesz jó, hogy egyes pontokat azonosítsunk. Válasszuk ki legelőször a bal felső sarokban az új gráf pont felvételét (Junction). Állítsunk be minden számunkra szükséges információt, majd kattintsunk oda a képen, ami számunkra épp megfelelő (itt hívnám fel a figyelmet arra, hogy a képen azon gráf pontok, melyek nagyobbnak tűnnek, mint a többiek, velünk egy síkban vannak a Z tengelyt tekintve). A (29. ábra) épp ezt a 42/67



folyamatot mutatja. Felvittünk egy új gráf pontot, mely automatikusan megkapta a sorban következő gráf pont sorszámát.

29. ábra: Egy új gráf pont felvétele Ezek után váltsunk át új gráf él felvitelére! Állítsuk be itt is az él színét, esetlegesen a nevét, majd kattintsunk a képen arra a gráf pontra, ahonnan az élünk kiindul, és az egér felengedése nélkül húzzuk oda, ahol az élünk vége lesz. Segítségképpen a bal oldalon látható Serial, X, Y és Z mezők változása jelzi, hogy a kurzor épp melyik koordinátájú gráf pont felett tartózkodik! Ezt a folyamatot a (30. ábra) mutatja be. Ha mindent jól csináltunk, és az élek be rajzolása be van kapcsolva, azonnal meg is jelennek az új éleink!

43/67



30. ábra: Új gráf élek felvitele Mindezek után még ugyanezen a képernyőn arra is képesek vagyunk, hogy egy gráf pont helyzetén változtassunk a térben! Ehhez válasszuk ki az „Edit mode”-ot, mint művelet a bal felső sarokban, kattintsunk egy tetszőleges gráf pontra a képen, majd a bal felső sarokban időközben megjelent mozgató gombokra kattintva figyeljük meg, ahogyan a gráf pontunk, a hozzá tartozó összes éllel együtt átdefiniálódik! A (31. ábra) épp azt mutatja, hogy a 14-es sorszámú gráf pontot kimozdítom a helyéről.

44/67



31. ábra: Gráf pont grafikus mozgatása Az “OK” gombra kattintva az elvégzett műveletek érvényesülnek (32. ábra).

45/67



32. ábra: Műveletek véglegesítése 4.3.14 – Tömegesen felvett élek és gráf pontok módosítása és törlése A fenti módszer kiegészítéseként az [Edit|Junctions and Edges Multi Editor] menüpontot kiválasztva (33. ábra) lehetőségünk van arra, hogy egy kattintással a középső listába felvett élek és gráf pontok színét, illetve nevét egységesen beállítsuk.

46/67



33. ábra: Multi Editor 4.3.15 – Útkeresés egyszerűbb formája Ahhoz hogy egy gráfokkal foglalkozó programot hatékonyan tudjuk kezelni, alapvetően szükséges az, hogy tisztában legyünk a gráfok matematikai alapjaival, hogy meg tudjuk mondani, hogy mi is az a kapcsolatmátrix. Ennek ellenére lehetőségünk van arra, hogy ne kelljen kapcsolatmátrixot generálnunk ahhoz, hogy a Dijkstra féle legrövidebb utat meghatározzuk egy adott súlyra nézve! A program képes dinamikusan létrehozni a kapcsolatmátrixnak a számára szükséges részét, így a kapcsolatmátrixot nem szükséges a memóriában tárolni, így elkészíteni sem (34. ábra). Ennek természetesen hátránya a sebesség lesz, de ez pár száz gráf pontot tartalmazó gráfok esetén nem számottevő. Ha kapcsolatmátrix nélkül keresünk utat, természetesen meg kell adnunk azt a súlyt is, melyet felhasználva a program dinamikusan kiszámolja majd a szükséges értékeket.

47/67



34. ábra: Útkeresés kapcsolatmátrix nélkül Mi az a lépés, mely segítségével még gyorsabbá tehetjük az útkeresést? Természetesen kézenfekvő, hogy az út hosszának automatikus megállapításával. Ha például egy térképhez készített gráf pontokat arányosan veszünk fel, avagy egy alakzatot méretarányosan modellezünk (azaz amit látunk, az körülbelül megfelel a valóságnak), akkor a program képes a pontok közötti 3D-s távolság kiszámolására minden egyes pontra nézve (35. ábra).

48/67



35. ábra: Súlyok együttes szerkesztése Ugyanitt megtehetjük azt is, hogy egy megadott konstans értéket állítunk be minden él adott súlyára (a súlyt ki kell választani a listából, majd a „Set Constant” avagy a „Set Distance 3D” gombra kell kattintani a kívánt eredmény függvényében). Későbbi program verzióba bekerülhet olyan lehetőség is, hogy minden egyes súlyra megadott műveletet végrehajt a program (például kettővel való szorzás, stb.).

49/67



36. ábra: Képernyőkép

4.4 - Fejlesztői dokumentáció 4.4.1 - A programról A Graphs and spanning trees alkalmazás Borland Delphi 7 környezetben készült Pascal/Delphi szintaktikával. Microsoft Windows 32 bites környezet alatt futtatható. Többdokumentumos, úgynevezett MDIApplication, mely lehetővé teszi, hogy egy időben több gráfon dolgozzunk, és a gráfokat egymástól függetlenül tudjuk kezelni. Jelenleg 23 darab példánya van az alkalmazásnak a TForm osztályból, és három saját készítésű osztályt tartalmaz: TQWVWin, TObject3D és TGraph. Az első kettő grafikai osztályok. A TQWVWin a gráfok forgatásáért felelős panel grafikáját dolgozza át. Az összes grafikai hatását bekapcsolva a gépet meglehetősen „visszafogja”. A TObject3D osztály egy egyedi szoftveres 3D objektumok tárolásáért, és kezelésért felelős. Részleteivel a 4.4.2-es fejezet foglalkozik. Végül a TGraph osztály maga a gráf, minden adatával és műveletével. Erre a 4.4.3 fejezetben térünk ki.

50/67



4.4.2 - A TObject3D osztály A Wevi3DUnit tartalmazza elsősorban a TObject3D osztály deklarációját, a hozzá tartozó típus deklarációkat, valamint a szükséges konstansokat és változókat. METÓDUS InitObject3D DataInit AddArm AddEdge AddPoint AddPointColor AddPointWithLabel DataStart SetVector3D SetPoint4D SetCoords InitRotateUgamma InitRotXAlpha InitRotYAlpha InitRotZAlpha SetTrans

TÍPUS Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Függvény Függvény Függvény Eljárás Eljárás Eljárás Eljárás Függvény

SetNegativMatrix SetInvTrans SetTransponalt Multiplication3x1_3x3 Multiplication4x1_4x4Single Multiplication4x1_4x4 Multiplication4x1_4x4Coords DrawObject MoveManipulator

Függvény Függvény Függvény Függvény Függvény Függvény Függvény Eljárás Eljárás

GetVectorLength SetNormalVector

Függvény Függvény

LEÍRÁS Inicializálja a példányt. Inicializálja a példány pontjait, és éleit. Egy elemet ad hozzá a példányhoz. Egy élet ad hozzá egy adott elemhez. Egy pontot ad hozzá egy adott elemhez. Egy pont színét adja hozzá egy adott ponthoz. Egy pontot ad hozzá az elemhez felirattal együtt. Rögzíti az adatbevitelét egy elemnek. Egy TVector3D típusú változó értékeit állítja be. Egy TPoint4D típusú változó értékeit állítja be. A koordináta tengelyeket állítja be. Az U tengely körüli forgatás mátrixát állítja be. Az X tengely körüli forgatás mátrixát állítja be. Az Y tengely körüli forgatás mátrixát állítja be. Az Z tengely körüli forgatás mátrixát állítja be. Három tengely és egy eltolás alapján egy TTrans típusú változó értékeit állítja be. Negál egy mátrixot. Invertál egy mátrixot. Transzponál egy mátrixot. Mátrixokat szoroz (3x1_3x3). Mátrixokat szoroz (4x1_4x4). Mátrixokat szoroz (4x1_4x4). Mátrixokat szoroz (4x1_4x4). Kirajzolja a példányban tárolt elemeket. Forgatja a beállított értékek alapján a példány elemeit. Visszaadja egy TVector3D típusú változó hozzsát. Meghatározza egy TVector3D típusú változó normálvektorát.

Konstansok CONST MAXPOINTS MAXEDGES MAXARMS ACCURACY

= = = =

500; 1000; 3; 0.001;

A MAXPOINTS határozza meg, hogy maximálisan mennyi grafikai pont lehet az ábrán. A program ezen része is teljesen statikus működésre van felkészítve, a későbbi programverziók legfontosabb lépése a dinamikus tárolás megvalósítása lesz.

51/67



A MAXEDGES értelemszerűen a maximálisan ábrázolható grafikai élek számát jelenti (már többször említettem, hogy a grafikai élek és pontok száma nem egyezik meg a gráf éleinek és pontjainak számával). A MAXARMS egy belső konstans, mely korlátozásával (3 a legkisebb értéke) a TObject3D osztály egy lényeges funkcióját elérhetetlenné tesszük. Képes lenne az osztály több elem tárolására (mindegyiket külön lokális koordinátarendszerben), és ezen elemeket egy osztálypéldány tagjaiként egymáshoz képest mozgatni, forgatni tudnánk. EZ a MAXARMS határozza meg, hogy mennyi ilyen elem tárolható egy példányban. Az 1. elem nem tényleges elem, itt nem tárolhatunk adatot. Ez a bázis koordinátarendszert határozza meg. A 2.-ban tároljuk a tárgyainkat, és ennek biztonságos kezeléséhez (mutatók elérik még a következő elemet is) szükséges még egy elem. Ezért 3 az értéke minimálisan a MAXARMS-nak. Az ACCURANCY egy pontosság érték. Két valós számot az osztály már egyenlőnek tekint, ha ezen értéknél kisebb a különbség közöttük. Típusok TYPE (*** T3DObjects ***) TTrans = Array [1..4,1..4] Of Double; TVector3D = Array [1..3] Of Double; TPoint4D = Array [1..4] Of Double; TCoords = Array [1..3] Of TPoint4D; TPoints = Array [1..MAXPOINTS] Of TPoint4D; TPointsColor = Array [1..MAXPOINTS,1..3] Of Byte; TPointsLabel = Array [1..MAXPOINTS,1..2] Of ShortString; TEdges = Array [1..MAXEDGES,1..5] Of Integer; TMatrix3x3 = Array [1..3] Of TVector3D; TData = Record Active : Boolean; Prev : Byte; Next : Byte; Coords : TCoords; Offset : TVector3D; PointsDB : Integer; Points : TPoints; EdgesDB : Integer; Edges : TEdges; ResultPoints : TPoints; PointsLabel : TPointsLabel; PointsColor : TPointsColor; End; TDataArray = Array [1..MAXARMS] Of TData;

A TTrans mátrix tartalmazza a transzformációs műveleteket (forgatás, eltolás, stb.). A TVector3D egy 3D-s vektor avagy egy pont tárolására alkalmas. A TPoint4D ehhez hasonlósan a homogén koordinátás alakban képes ugyanerre. A TCoords a koordinátatengelyek homogén koordinátás alakjait tárolja. A TPoints tömbben találhatók a grafikus pontok, a TEdges tömbben pedig a grafikus élek adatai. A TPointsColor minden pontra tárolja a színét, a TPointsLabel pedig egy 52/67



feliratot, mely szintén megjelenhet, ha a beállítások ezt engedik. A TMatrix3x3 egy 3D-s környezetben tárolt mátrix. A TDataArray tárolja az egyes elemek (amiből a Graphs and spanning trees csak ténylegesen egyet használ) adatait. Változók VAR TextFont BACKGROUND DefaultColor TEXTOVERWRITE VISI_SERIALOFPOINTS VISI_NAMEOFPOINTS VISI_SERIALOFEDGES VISI_NAMEOFEDGES VISI_WEIGHT VISI_COLORS VISI_DATUM SerialOfPointsColor NameOfPointsColor SerialOfEdgesColor NameOfEdgesColor WeightColor DatumColor

: : : : : : : : : : : : : : : : :

TFont; TColor; TColor; Boolean; Boolean; Boolean; Boolean; Boolean; Boolean; Boolean; Boolean; TColor; TColor; TColor; TColor; TColor; TColor;

A változók az egyes feliratok láthatóságát, illetve színét állítják be. A TEXTOVERWRITE igaz értéke esetén a feliratok háttere átlátszó lesz. Így bár több információ lesz az ábrán, ám ezek kevésbé leolvasható formában. Az osztály TObject3D = Class (TObject) Data : TDataArray; // Az objektumok adatai OX : Integer; // Origó X koordinátája OY : Integer; // Origó Y koordinátája RotateUgamma : TTrans; // Tetszőleges U tengely körüli forgatás mátrixa (gamma szöggel) u : TPoint4D; // Az u tenngely gamma : Double; // A gamma szög (radián) Act : Byte; // Az aktuális kar. RotXAlpha : TTrans; // Az X tengely körüli forgatás mátrixa RotYAlpha : TTrans; // Az Y tengely körüli forgatás mátrixa RotZAlpha : TTrans; // Az Z tengely körüli forgatás mátrixa alpha : Double; // A X, Y, Z tengely körüli forgatás szöge. PROCEDURE InitObject3D ( KX : Integer; KY : Integer ); PROCEDURE DataInit; PROCEDURE AddArm ( num : Byte; prev : Byte; next : Byte; coords : TCoords; offset : TVector3D ); PROCEDURE AddEdge ( num : Byte; p1 : Integer; p2 : Integer; ColorR : Byte; ColorG : Byte; ColorB : Byte ); PROCEDURE AddPoint ( num : Byte; pointDB : Byte; x : Double; y : Double;

53/67



: Double ); : Byte; : Byte; : Byte; : Byte; : Byte ); PROCEDURE AddPointWithLabel ( num : Byte; pointDB : Byte; x : Double; y : Double; z : Double; PLabel : ShortString; PLabelType : ShortString ); PROCEDURE DataStart ( num : Byte ); FUNCTION SetVector3D ( x : Double; y : Double; z : Double ) : TVector3D; FUNCTION SetPoint4D ( x : Double; y : Double; z : Double; h : Double ) : TPoint4D; FUNCTION SetCoords ( X : TPoint4D; Y : TPoint4D; Z : TPoint4D ) : TCoords; PROCEDURE InitRotateUgamma ( v : TPoint4D; rad : Double ); PROCEDURE InitRotXAlpha ( rad : Double ); PROCEDURE InitRotYAlpha ( rad : Double ); PROCEDURE InitRotZAlpha ( rad : Double ); FUNCTION SetTrans ( Coords : TCoords; Offset : TVector3D ) : TTrans; FUNCTION SetNegativMatrix ( Matrix : TMatrix3x3 ) : TMatrix3x3; FUNCTION SetInvTrans ( Coords : TCoords; Offset : TVector3D ) : TTrans; FUNCTION SetTransponalt ( TT : TMatrix3x3 ) : TMatrix3x3; FUNCTION Multiplication3x1_3x3 ( Matrix : TMatrix3x3; v : TVector3D ) : TVector3D; FUNCTION Multiplication4x1_4x4Single ( Matrix : TTrans; v : TPoint4D ): TPoint4D; FUNCTION Multiplication4x1_4x4 ( v : TPoints; Matrix : TTrans; PointsDB : Integer ) : TPoints; FUNCTION Multiplication4x1_4x4Coords ( v : TCoords; Matrix : TTrans ) : TCoords; PROCEDURE DrawObject ( ManipulatorImage : TImage; Original : Boolean; PointsOrEdgesDraw : Char ); PROCEDURE MoveManipulator ( ManipulatorImage : TImage; CLRSCR : Boolean; PointsOrEdgesDraw : Char ); FUNCTION GetVectorLength ( A : TVector3D ) : Double; FUNCTION SetNormalVector ( A : TVector3D; B : TVector3D ) : TVector3D; End; PROCEDURE AddPointColor

z ( num pointDB R G B

4.4.3 - A TGraph osztály A TypeUnit része többek között a TGraph osztály is, de itt megtalálható számos, a Graphs and spanning trees-ben használt további típusok deklarálása is. METÓDUS InitGraph AddItemRecArray

TÍPUS Eljárás Eljárás

AddPoint

Eljárás

LEÍRÁS Inicializálja a gráfot. Egy elemet hozzáad egy TRecArray típusú vektorhoz. Egy gráf pontot hozzáad a gráfhoz.

54/67

Gráf szimuláció az oktatásban DeletePoint EditPoint AddEdge DeleteEdge EditEdge Draw PathfindingDijkstra DijkstraNeighbours DijkstraMinimum InitEdgeWay

Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Függvény Eljárás

SearchEdge

Függvény

BUDAPESTI MŰSZAKI FŐISKOLA Egy élet hozzáad a gráfhoz. Szerkeszt egy gráf pontot. Szerkeszt egy élet a gráfban. Logikailag töröl egy élet a gráfból. Logikailag töröl egy gráf pontot. Kirajzolja a gráfot. Dijkstra legrövidebb út kereső algoritmusa. Dijkstra algoritmusához szükséges. Dijkstra algoritmusához szükséges. Törli (inicializálja) a megtalált utat (nem lesz kijelölt út). Két pont közötti él sorszámát adja vissza, amennyiben létezik.

Algoritmusok A Draw() és a PathfindingDijkstra() algoritmusa kulcsfontosságú az osztály szempontjából, így ezek forráskódját teljes terjedelmében közlöm. Dijkstra algoritmusának pszeudó kódja már szerepelt az irodalomkutatásban is. Most nézzük meg Delphi 7 forrását. PROCEDURE TGraph.PathfindingDijkstra (

StartPoint DestinationPoint Var PFArray

: Word; : Word; : TPFArray

); Var i : Integer; act : Word; Begin For i:=1 To (PointsNum) Do Begin PFArray[i].Length:=High(Integer); PFArray[i].Prev:=0; PFArray[i].Status:=FALSE; End; act:=StartPoint; PFArray[act].Length:=0; PFArray[act].Status:=TRUE; REPEAT DijkstraNeighbours(PFArray,act); act:=DijkstraMinimum(PFArray); PFArray[act].Status:=TRUE; UNTIL (act=DestinationPoint); End; PROCEDURE TGraph.DijkstraNeighbours ( Var 55/67

Var PFArray act

: TPFArray; : Word );



i : Integer; Begin For i:=1 To (PointsNum) Do Begin If (RelationMatrix[act,i]<>0) And (Not(PFArray[i].Status)) Then Begin If (PFArray[act].Length+RelationMatrix[act,i])<(PFArray[i].Length) Then Begin PFArray[i].Prev:=act; PFArray[i].Length:=PFArray[act].Length+RelationMatrix[act,i]; End; End; End; End; FUNCTION TGraph.DijkstraMinimum ( PFArray : TPFArray ) : Word; Var min : Double; minH : Integer; i : Integer; find : Boolean; j : Integer; Begin find:=FALSE; i:=0; REPEAT Inc(i); If (Not(PFArray[i].Status)) Then Begin min:=PFArray[i].Length; minH:=i; find:=TRUE; End; UNTIL (find); If (find) Then Begin For j:=i To (PointsNum) Do Begin If (min>PFArray[j].Length) And (Not(PFArray[j].Status)) Then Begin min:=PFArray[j].Length; minH:=j; End; End; End; If (find) Then Begin Result:=minH; End Else Begin 56/67



Result:=0; End; End; PROCEDURE TGraph.Draw( Image : TImage ); Var I : Integer; TF : TextFile; Num : Integer; X : Integer; Y : Integer; Z : Integer; Numglobal : Word; AidePair : TPair; PairNum : Byte; Line : ShortString; Numglobalinfo : Word; SX : Integer; SY : Integer; SZ : Integer; Sdiv : Integer; A : TVector3D; B : TVector3D; IV : TVector3D; NV : TVector3D; Scolor : TColor; BEGIN ShowPoints.Free; ShowPoints:=TObject3D.Create; ShowPoints.InitObject3D(MaxXY Div 2,MaxXY Div 2); ShowPoints.DataInit; ShowInfo.Free; ShowInfo:=TObject3D.Create; ShowInfo.InitObject3D(MaxXY Div 2,MaxXY Div 2); ShowInfo.DataInit; ShowPoints.AddArm(1,0,2,ShowPoints.SetCoords(ShowPoints.SetPoint4D(1,0,0,1),ShowPoints. SetPoint4D(0,1,0,1),ShowPoints.SetPoint4D(0,0,1,1)),ShowPoints.SetVector3D(0,0,0)); ShowPoints.AddPoint(1,1,0,0,0); ShowPoints.DataStart(1); ShowPoints.AddArm(2,1,0,ShowPoints.SetCoords(ShowPoints.SetPoint4D(1,0,0,1),ShowPo ints.SetPoint4D(0,1,0,1),ShowPoints.SetPoint4D(0,0,1,1)),ShowPoints.SetVector3D(0,0,10)); ShowInfo.AddArm(1,0,2,ShowInfo.SetCoords(ShowInfo.SetPoint4D(1,0,0,1),ShowInfo.SetPoint 4D(0,1,0,1),ShowInfo.SetPoint4D(0,0,1,1)),ShowInfo.SetVector3D(0,0,0)); ShowInfo.AddPoint(1,1,0,0,0); ShowInfo.DataStart(1); ShowInfo.AddArm(2,1,0,ShowInfo.SetCoords(ShowInfo.SetPoint4D(1,0,0,1),ShowInfo.SetPoint 4D(0,1,0,1),ShowInfo.SetPoint4D(0,0,1,1)),ShowInfo.SetVector3D(0,0,10)); numglobal:=0; numglobalinfo:=0; For i:=1 To (PointsNum) Do Begin If (PointsArray[i].Enable) Then Begin AssignFile(TF,SHAPEDIRECTORY+PointsArray[i].Shape);

57/67



{$I-} ReSet(TF); {$I+} If (IoResult<>0) Then Begin ShowMessage('There was some error during shape file opening.'); Halt; End; Line:=''; If (VISI_SERIALOFPOINTS) Then Begin Line:=IntToStr(PointsArray[i].Serial); End; If (VISI_NAMEOFPOINTS) And (PointsArray[i].AllowName) Then Begin Line:=PointsArray[i].Name; End; If (VISI_DATUM) And (CurrentDatum<>0) Then Begin Line:=PointsArray[i].DataArray[CurrentDatum]; End; If (VISI_SERIALOFPOINTS) Or (VISI_NAMEOFPOINTS) Or (VISI_DATUM) Then Begin Inc(numglobalinfo); ShowInfo.AddPointWithLabel(2,numglobalinfo,PointsArray[i].X,PointsArray[i].Y, PointsArray[i].Z,Line,'Point'); End; ReadLn(TF,Line); ReadLn(TF,num,X,Y,Z); InitPair(AidePair,PairNum); While (Not(EoF(TF))) And (num<>0) Do Begin Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[i].X+X,PointsArray[i].Y+Y,Points Array[i].Z+Z); Inc(PairNum); AidePair[PairNum,1]:=num; AidePair[PairNum,2]:=numglobal; ReadLn(TF,num,X,Y,Z); End; While (Not(EoF(TF))) Do Begin ReadLn(TF,X,Y); X:=SearchPair(AidePair,X); Y:=SearchPair(AidePair,Y); ShowPoints.AddEdge(2,X,Y,GetRValue(PointsArray[i].Color),GetGValue(PointsAr ray[i].Color),GetBValue(PointsArray[i].Color)); End; Close(TF); End; End; For i:=1 To (EdgesNum) Do Begin If (EdgesArray[i].Enable) Then Begin Line:=''; If (VISI_SERIALOFEDGES) Then Begin Line:=IntToStr(EdgesArray[i].Serial); End;

58/67



If (VISI_NAMEOFEDGES) And (EdgesArray[i].AllowName) Then Begin Line:=EdgesArray[i].Name; End; If (VISI_WEIGHT) And (CurrentWeight<>0) Then Begin Line:=EdgesArray[i].WeightsArray[CurrentWeight]; End; If (VISI_NAMEOFEDGES) Or (VISI_SERIALOFEDGES) Or (VISI_WEIGHT) Then Begin Inc(numglobalinfo); ShowInfo.AddPointWithLabel(2,numglobalinfo,(PointsArray[EdgesArray[i].Point One].X + PointsArray[EdgesArray[i].PointTwo].X)/2,(PointsArray[EdgesArray[i].Point One].Y + PointsArray[EdgesArray[i].PointTwo].Y)/2,(PointsArray[EdgesArray[i].Point One].Z +PointsArray[EdgesArray[i].PointTwo].Z)/2,Line,'Edge'); End; Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointOne].X,PointsArr ay[EdgesArray[i].PointOne].Y,PointsArray[EdgesArray[i].PointOne].Z); Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointTwo].X,PointsArr ay[EdgesArray[i].PointTwo].Y,PointsArray[EdgesArray[i].PointTwo].Z); If (EdgesArray[i].IsWay) Then Begin SColor:=WayColor; End Else Begin SColor:=EdgesArray[i].Color; End; ShowPoints.AddEdge(2,numglobal1,numglobal,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); If (EdgesArray[i].Directivity=1) Then Begin A:=ShowPoints.SetVector3D(PointsArray[EdgesArray[i].PointOne].X,PointsArray[ EdgesArray[i].PointOne].Y,PointsArray[EdgesArray[i].PointOne].Z); B:=ShowPoints.SetVector3D(PointsArray[EdgesArray[i].PointTwo].X,PointsArray[ EdgesArray[i].PointTwo].Y,PointsArray[EdgesArray[i].PointTwo].Z); IV:=ShowPoints.SetNormalVector(A,B); NV:=ShowPoints.SetVector3D(IV[3],-IV[1],IV[2]); Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointOne].X+IV[1]* DirectivityLength+NV[1]*DirectivityLength2,PointsArray[EdgesArray[i].Point One].Y+IV[2]*DirectivityLength+NV[2]*DirectivityLength2,PointsArray[Edges Array[i].PointOne].Z+IV[3]*DirectivityLength+NV[3]*DirectivityLength2); ShowPoints.AddEdge(2,numglobal,numglobal2,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointOne].X+IV[1]* DirectivityLengthNV[1]*DirectivityLength2,PointsArray[EdgesArray[i].PointOne].Y+IV[2]*Direc tivityLengthNV[2]*DirectivityLength2,PointsArray[EdgesArray[i].PointOne].Z+IV[3]*Direc tivityLength-NV[3]*DirectivityLength2); ShowPoints.AddEdge(2,numglobal,numglobal3,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor));

59/67



NV:=ShowPoints.SetVector3D(-IV[2],-IV[3],IV[1]); Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointOne].X+IV[1]* DirectivityLength+NV[1]*DirectivityLength2,PointsArray[EdgesArray[i].Point One].Y+IV[2]*DirectivityLength+NV[2]*DirectivityLength2,PointsArray[Edges Array[i].PointOne].Z+IV[3]*DirectivityLength+NV[3]*DirectivityLength2); ShowPoints.AddEdge(2,numglobal,numglobal4,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointOne].X+IV[1]* DirectivityLengthNV[1]*DirectivityLength2,PointsArray[EdgesArray[i].PointOne].Y+IV[2]*Direc tivityLengthNV[2]*DirectivityLength2,PointsArray[EdgesArray[i].PointOne].Z+IV[3]*Direc tivityLength-NV[3]*DirectivityLength2); ShowPoints.AddEdge(2,numglobal,numglobal5,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); ShowPoints.AddEdge(2,numglobal,numglobal2,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); ShowPoints.AddEdge(2,numglobal-2,numglobal1,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); ShowPoints.AddEdge(2,numglobal-1,numglobal3,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); ShowPoints.AddEdge(2,numglobal3,numglobal,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); End; If (EdgesArray[i].Directivity=2) Then Begin A:=ShowPoints.SetVector3D(PointsArray[EdgesArray[i].PointOne].X,PointsArray[ EdgesArray[i].PointOne].Y,PointsArray[EdgesArray[i].PointOne].Z); B:=ShowPoints.SetVector3D(PointsArray[EdgesArray[i].PointTwo].X,PointsArray[ EdgesArray[i].PointTwo].Y,PointsArray[EdgesArray[i].PointTwo].Z); IV:=ShowPoints.SetNormalVector(A,B); NV:=ShowPoints.SetVector3D(IV[3],-IV[1],IV[2]); Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointTwo].XIV[1]*DirectivityLength+NV[1]*DirectivityLength2,PointsArray[EdgesArray[i]. PointTwo].YIV[2]*DirectivityLength+NV[2]*DirectivityLength2,PointsArray[EdgesArray[i]. PointTwo].Z-IV[3]*DirectivityLength+NV[3]*DirectivityLength2); ShowPoints.AddEdge(2,numglobal,numglobal1,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointTwo].XIV[1]*DirectivityLengthNV[1]*DirectivityLength2,PointsArray[EdgesArray[i].PointTwo].YIV[2]*DirectivityLengthNV[2]*DirectivityLength2,PointsArray[EdgesArray[i].PointTwo].ZIV[3]*DirectivityLength-NV[3]*DirectivityLength2); ShowPoints.AddEdge(2,numglobal,numglobal2,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); NV:=ShowPoints.SetVector3D(-IV[2],-IV[3],IV[1]); Inc(numglobal);

60/67



ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointTwo].XIV[1]*DirectivityLength+NV[1]*DirectivityLength2,PointsArray[EdgesArray[i]. PointTwo].YIV[2]*DirectivityLength+NV[2]*DirectivityLength2,PointsArray[EdgesArray[i]. PointTwo].Z-IV[3]*DirectivityLength+NV[3]*DirectivityLength2); ShowPoints.AddEdge(2,numglobal,numglobal3,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointTwo].XIV[1]*DirectivityLengthNV[1]*DirectivityLength2,PointsArray[EdgesArray[i].PointTwo].YIV[2]*DirectivityLengthNV[2]*DirectivityLength2,PointsArray[EdgesArray[i].PointTwo].ZIV[3]*DirectivityLength-NV[3]*DirectivityLength2); ShowPoints.AddEdge(2,numglobal,numglobal4,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); ShowPoints.AddEdge(2,numglobal,numglobal2,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); ShowPoints.AddEdge(2,numglobal-2,numglobal1,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); ShowPoints.AddEdge(2,numglobal-1,numglobal3,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); ShowPoints.AddEdge(2,numglobal3,numglobal,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); End; End; End; ShowPoints.DataStart(2); END;

A konstansok CONST MAXITEM MAXGRAPHPOINTS MAXGRAPHEDGES MAXSHAPEPOINTS SHAPELISTFILENAME SHAPEDIRECTORY SAVEDIRECTORY

= = = = = = =

10; 50 100 20; 'shapes.lst'; 'shape/'; 'graphs/';

A MAXITEM határozza meg, hogy statikus esetben egy élen mennyi súly, illetve egy pontban mennyi adat tárolható. A MAXGRAPHPOINTS és a MAXGRAPHEDGES a gráf pontjaira illetve éleire meghatározott statikus korlát. A MAXSHAPEPOINTS meghatározza, hogy egy gráf pont minta 3D-s objektuma maximálisan mennyi grafikai pontból állhat. A SHAPEDIRECTORY és a SAVEDIRECTORY az alapértelmezett könyvtárakat állítja be, míg a SHAPELISTFILENAME a minták listáját tároló file nevét. A változók Var DIRECTIVITYLENGTH

: Byte;

61/67

Gráf szimuláció az oktatásban DIRECTIVITYLENGTH2 WayColor


: Byte; : TColor;

A gráf irányítottságát grafikailag jelölni többféleképpen lehet. A DIRECTIVITYLENGTH és a DIRECTIVITYLENGTH2 változók lehetővé teszik, hogy hosszabb, illetve nagyobb nyilakat tudjunk megjeleníteni. A WayColor a megtalált út színét határozza meg. A típusok (*** TGraph ***) TRec

= Record ItemName : ShortString; ItemType : ShortString; DefaultValue : ShortString; End; TGraphDataArray = Array [1..MAXITEM] Of ShortString; TGraphWeightsArray = Array [1..MAXITEM] Of ShortString; TPointRec = Record Enable : Boolean; X : Double; Y : Double; Z : Double; Serial : Word; Name : ShortString; AllowName : Boolean; Shape : ShortString; Color : TColor; DataArray : TGraphDataArray; End; TEdgeRec = Record Enable : Boolean; PointOne : Word; PointTwo : Word; Serial : Word; Name : ShortString; AllowName : Boolean; Color : TColor; Directivity : Byte; WeightsArray : TGraphWeightsArray; IsWay : Boolean; End; TRecArray = Array [1..MAXITEM] Of TRec; TPointsArray = Array [1..MAXGRAPHPOINTS] Of TPointRec; TEdgesArray = Array [1..MAXGRAPHEDGES] Of TEdgeRec; TRelationMatrix = Array [1..MAXGRAPHPOINTS,1..MAXGRAPHPOINTS] Of Double; TPFRec = Record Length : Double; Prev : Word; Status : Boolean; End; TPFArray = Array [1..MAXGRAPHPOINTS] Of TPFRec;

A TRec rekord tárolja a súlyvektor illetve a pontok adatainak tulajdonságait a gráf tulajdonságai között. 62/67



A TRecArray vektor tárolja a a TRec típusú elemeket a statikus súlyvektor és gráf pont adatvektor számára. A TGraphDataArray a pontok adatainak statikus vektora szinkronban TRecArray-el. A TGraphWeightsArray a statikus súlyvektor szinkronban TRecArray-el. A TPointRec rekord tárolja egy adott gráf pont tulajdonságait. Az ’Enable’ határozza meg, hogy logikailag törölt-e az elem, avagy sem. Az ’X’,’Y’ és ’Z’ a koordinátáit határozza meg, a ’Serial’ az automatikusan generálódó sorszámát, a ’Name’ a nevét, az ’AllowName’ ennek a létezését. A ’Shape’ az adott grafikai mintát tároló file neve, a ’Color’ pedig a gráf pont színe. A ’DataArray’ tárolja a TGraphDataArray-el szinkronban a gráf csomópontjaiban tárolt adatokat. A TEdgeRec rekord a gráf éleinek tulajdonságait tárolja. Az ’Enable’ itt is a logikai törlöttségre utal, a ’Serial’, ’Name’, ’AllowName’ és ’Color’ szintén azonos jelentéssel bír, mint a gráf pontjai esetén ezt már láttuk. A ’PointOne’ és ’PointTwo’ határozza meg az él által összekötött két pont sorszámát. A ’Directivity’ ennek függvényében az irányítottságot jelölheti. Ha értéke ’0’, akkor nincs irányítottság. Irányított gráf esetében ez azt jelenti, hogy oda-vissza út létezik (ezt a későbbiekben le lehet majd tiltani, mivel előfordulhat olyan probléma, mely során ezt nem célszerű alkalmazni, azonban térkép program esetén a kétsávú utat ezzel tudjuk modellezni)! Az ’IsWay’ logikai változó igaz értéke esetén az adott él egy korábbi útszámítás során az eredmény része volt. Ilyenkor a színe a saját ’Color’ tulajdonsága helyett a ’WayColor’ lesz. A TPointsArray és a TEdgesArray tárolják a pontokat és az éleket statikus esetben. A TRelationMatrix a kapcsolatmátrix típusa. A TPFRec és a TPFArray Dijkstra legrövidebb út kereső algoritmusához szükséges. TPArray-ben fog keletkezni az eredmény. Az osztály TGraph

= Class (TObject) public // kesobbiekben private NameOfGraph : ShortString; Comment : ShortString; StorageType : ShortString; TypeOfGraph : ShortString; MultipleEdges : Boolean; Continuous : Boolean; MultipleWeight : Boolean; DataArray : TRecArray; WeightsArray : TRecArray; DANum : Byte; WANum : Byte; MaxXY : Integer; PointsArray : TPointsArray; PointsNum : Word; ShowPoints : TObject3D; EdgesNum : Word; EdgesArray : TEdgesArray; ShowInfo : TObject3D; CurrentWeight : Integer; CurrentDatum : Integer; RelationMatrix : TRelationMatrix;

63/67



public PROCEDURE InitGraph; PROCEDURE AddItemRecArray ( Var TRA : TRecArray; Var Num : Byte; ItemName : ShortString; ItemType : ShortString; DefaultValue : ShortString ); PROCEDURE AddPoint ( PointRec : TPointRec ); PROCEDURE DeletePoint ( Serial : Word ); PROCEDURE EditPoint ( PointRec : TPointRec; Serial : Word ); PROCEDURE AddEdge ( EdgeRec : TEdgeRec ); PROCEDURE DeleteEdge ( Serial : Word ); PROCEDURE EditEdge ( EdgeRec : TEdgeRec; Serial : Word ); PROCEDURE Draw ( Image : TImage ); PROCEDURE PathfindingDijkstra ( StartPoint : Word; DestinationPoint : Word; Var PFArray : TPFArray ); PROCEDURE DijkstraNeighbours ( Var PFArray : TPFArray; act : Word ); FUNCTION DijkstraMinimum ( PFArray : TPFArray ) : Word; PROCEDURE InitEdgeWay; FUNCTION SearchEdge ( PointOne : Word; PointTwo : Word ) : Word; End;

4.4.4 – A TypeUnit további részei ALPROGRAM CopyGraph

TÍPUS Eljárás

LoadShapeList LoadShape

Eljárás Eljárás

InitPair SearchPair SaveGraphToFile OpenGraphFromFile

Eljárás Függvény Eljárás Eljárás

LEÍRÁS Egy gráf attribútumait egy másik gráf attribútumaiba másolja. Betölti a minták listáját az adott file-ból. Egy mintát tölt be a TObject3D osztály egy példányába. Inicializálja a segédtömböt. A TPair-hez kapcsolódóan párokat keres. Kimenti a statikus gráfot file-ba. Betölti a statikus gráfot file-ból.

További típusok TPair

= Array [1..MAXSHAPEPOINTS,1..2] Of Word;

A TPair egy segédtömb, mely a gráf pont minták gráfhoz illesztéséhez szükséges. A probléma, melyet meg kellett oldani, hogy egy TObject3D adatmezőit (minta) egy másik TObject3D típusba (a gráfba) kellett átmásolni. Ilyenkor a pontok sorszáma megváltozik, de mivel az élek is a pontok eredeti sorszáma alapján tárolódnak, ezért az éleket párosítani kellett a pontokkal. További eljárások illetve függvények PROCEDURE CopyGraph PROCEDURE LoadShapeList PROCEDURE LoadShape PROCEDURE InitPair FUNCTION SearchPair

( Graph1 Var Graph2 ( Var ListBox ( Var Shape FileName ( Var Pair Var Num ( Pair

64/67

: : : : : : : :

TGraph; TGraph ); TListBox ); TObject3D; String ); TPair; Byte ); TPair;



local PROCEDURE SaveGraphToFile ( FileName PROCEDURE OpenGraphFromFile ( FileName

65/67

: Byte ) : Word; : ShortString ); : ShortString );



5 – TÁRGYSZÓ JEGYZÉK TÁRGYSZÓ Abt Addinall audiovizuális technika csaturanga e-book Ellington El-Mahaszna esettanulmány Frederiksen G-nyelv gó Griffits harcászati stratégia Hemphil Internet Inverted Pendulum írásvetítő játék játékok fejlődése Kersh készség játék Konfucius Kriegspiel Kupisiewicz LabView multimédia Nagy Sándor

FEJEZET 3.2 3.2 3.2 3.1 3.4 3.2 3.1 3.2 3.2 3.5 3.1 3.2 3.1 3.2 3.4 3.5 3.4 3.2 3.1 3.2 3.2 3.1 3.1 3.3 3.5 3.4 3.3

Nyirati László oktatási szimuláció oktatástechnológia oktatójáték Percival Pocket PC Poroszország Reid rigid Romiszowski sakk Shubik szerepjáték szimuláció szimulációs játék táblás játék Tablet PC tankönyv Ur városa vezetőképzés vietnámi háború

66/67

3.4 3.2 3.4 3.2 3.2 3.4 3.1 3.2 3.1 3.2 3.1 3.2 3.2 3.2 3.2 3.1 3.4 3.4 3.1 3.2 3.1



6 – SZAKIRODALOM ÉS FORRÁSJEGYZÉK 6.1 – Forrásjegyzék (3-I) Murray, H. J. R.: A history of board-games other than chess. The Clarendon press, Oxford, 1952. 12-36. o. (3-II) Novak, Z.: 50 táblás játék. Gondolat Könyvkiadó, Bp., 1982. 92. o (3-III) Gelenczei Emil: A legrégibb magyar sakkemlékek. = Barcza Gedeon: Magyar sakktörténet. Sport, Bp., 1975. 9-11. o. (3-IV) Rockler, J. M.: Applying Simulation/Gaming. On College Teaching. Jossey-Bass Publishers, San Francisco, 1978. 249. o. (3-V) Rockler, M. J: Simulation Games and Furtures Studies. World Future Society Bulletin, 1980. Jan.-Feb. 25. o. (3-VI) Nagy Sándor (1982/b): Oktatástechnológia a neveléstudomány rendszerében. OOK, Veszprém, 18. o (3-VII) Ellington-Addinall-Percival: A handbook of game design. Kogan Page, London, 1982. 11. o., f: 1,1 (3-VIII) Abt, C. C.: Games for learning. = Ellington-Addinall-Percival: i. m. 9. o. (3-IX) Shubik, M.: Games for Society…= Taylor: Guide on simulation and gaming for enviromental education. UNESCO-UNEP, 1983. 8. o. (3-X) Romiszowski, A. J.: Producing Instructional Systems. Kogan Page, London, 1984. 174. o. (3-XI) Nyirati László: A számítógép mint oktatási eszköz (1999)

6.2 – Link gyűjtemény http://www.homoludens.hu/htmlm/cik/8031barm.htm http://informatika.kodolanyi.hu/~nyirati/public/aszgazok.htm

67/67

G RÁF SZIMULÁCIÓ AZ OKTATÁSBAN

Recommend Documents