Az első részben bemutatott tárolási formák közül a két legegyszerűbb, így a megértést és az algoritmusok áttekinthetőségét leginkább segítő tárolási módszert, a mátrixos és az éltárolásos módszert szeretnénk tovább vizsgálgatni, hiszen ezek a statikus adatszerkezettel modellezhető/programozható struktúrák jóval egyszerűbben kezelhetők mint dinamikus társaik.

Mivel az alapfogalmak már ismertek (1. rész) és az egyszerű, input jellegű felhasználáson is túl vagyunk (2. rész) rátérhetünk a 'húsba vágóbb' algoritmusokra is, nevezetesen az elemi adatkarbantartási manipulációk (mint pl. új él felvétele, pont törlése, stb.) 'mögött meghúzódó' tevékenységek tárgyalására. Azaz hogyan 'vezetődnek át' a gráf adatok módosításai a fent említett két tárolási formán.

Pontok karbantartása

A kétféle tárolási módszer különbözősége, amint ez már korábban kiderült, az élek tárolásában rejlik, a pontokat mindkét esetben egy egydimenziós tömbben, pontazonosító szerint növekvő sorrendben tárolhatjuk. Példánkban a rendezettség 'csupán' a gyorsabb pontkeresést segíti majd.

Ezen ponttömbbön könnyen átvezethetők a pontmódosítások, hiszen csak a rendezettség megtartására kell ügyelnünk. De nézzük meg az ehhez szükséges tevékenységeket egy kicsit részletesebben.

Új pont felvétele

- Meg kell keresnünk az új pont helyét. (A keresés történhet binárisan is, természetesen az új pont azonosítója szerint)

- Helyet kell készítenünk a tömbben az új pontnak, az elemek hátraléptetésével

- Az új pont adatai betehetők a tömb 'megüresedett' helyére

- A pontok számát növelnünk kell eggyel

Pont törlése teljesen analóg módon történhet a pontok előremásolásával, a darabszám csökkentésével.

A pont adatok módosítása még ennél is egyszerűbb, ha nem engedjük meg a pontazonosítók módosítását, hiszen

- A pontot megkeressük

- Adatait kiajánljuk módosításra

- Majd a megváltozott adatú pontot 'visszatesszük' a tömbbe (a régi helyére)

Kicsit problémásabb a dolog ha megengedjük az azonosító módosítását is, de ez az eset visszavezethető a 'régi' pont törlésére és az 'új' pont felvételére. Ez persze nem csak a pontokra igaz, hanem általában is, következésképpen az élekre is. Az azonosítók egyedi voltát természetesen ekkor is biztosítanunk kell!

A pontkarbantartás vonzatai az élekre nézve.

Mátrixos tárolás

Itt szinte teljesen analóg módon átvezethetők a ponttömb megváltozásai, hiszen a pontokból kimenő élek adatait az élmátrixok sorai, a bejövőkét pedig az oszlopai tárolják, így itt is meg kell tennünk a helykészítés, ill. az előremásolás lépéseit, csak itt már sorokat ill. oszlopokat kell léptetnünk.

A sorok hátraléptetésével az új pont kimenőéleinek az oszlopok léptetésével pedig a bejövőéleinek készítünk helyet. Hasonló módon a sorok/oszlopok előreléptetésével az adott pont kimenő/bejövő éleit törölhetjük.

Természetesen új pont felvétele esetén, a helykészítés után törölnünk kell az illető ponthoz tartozó sor és oszlop tartalmát, rögzítve ezzel azt a tényt, miszerint az új pontnak nincsenek (még) élei.

Éltárolás

Amint az kiderült már az első részben, a helytakarékosabb tárolással időt vesztünk, no persze nem a bonyolultabb algoritmusok elkészítésének plussz idejére gondolunk itt elsősorban, hanem a módosításoknak az adatstruktúrán történő átvezetésére, de még mindig jobb egy kicsit talán bonyolultabban megoldani az adatok tárolását és kezelését, mint (pl. a mátrixos tárolás teljesíthetetlen memóriaigénye miatt) sehogy!

Új pont felvétele

- Tekintettel arra, hogy egy új pont felvételével az adott pont helyétől kezdődő pontok eggyel hátrébb fognak 'csúszni', az 'őrájuk mutató' pontindexek értékeit rendre meg kell növelnünk eggyel az élek tömbben.

- A mutatótömbben is helyet kell készítenünk az új pont számára, s ez, a ponttömbhöz hasonlóan, az elemek hátraléptetésével megoldható. (Megjegyezzük azonban, hogy a 'megüresedett' helyen maradt érték, ami a léptetés miatt megegyezik majd a következő pont élindexével, éppen azt fejezi ki, hogy az új pontnak nincsen (még) éle, vagyis ezt az értéket nem kell/szabad változtatnunk.) Mivel az utolsó pont éleinek 'végét' a mutató tömb PontDb+1. eleme jelzi, ezért a hátraléptetést 'innentől' kell majd elkezdenünk.

Pont törlése

1. ábra

A felvétel analógiájára a törlés már könnyen elvégezhető, csökkentve a törlendő pont 'utáni' pontokra 'mutató' élvégpontindexeket, valamint elvégezve a mutató tömb előreléptetését. (Ha a törlendő pontnak lenne még kimenő éle, akkor az előreléptetéssel az őt megelőző pont 'kapná meg' ezeket az éleket, ezért a pont törlése előtt célszerű valamennyi élét törölni.)

A pontadatok módosítása ennél a tárolási formánál sincs kihatással az élekre, hiszen a ponttömbben nem mozdulnak el helyükről a pontok.

 

Élek karbantartása

Mátrixos tárolás

Aki idáig eljutott az olvasásban az igazán megérdemli azt a kis 'felüdülést', amit a mátrixos tárolási forma élkezelése biztosít számunkra. Uis elegendő a kezdő és a végpont ponttömbbeli indexe s egy mátrixelem hivatkozással azt teszünk a kérdéses éllel amit akarunk. Mármint az ott lévő érték módosításával 'felvehetünk' is és 'törölhetünk' is. (Példáinkban egy él hiányát a 0 hosszérték jelöli.)

Éltárolás

Amennyire kényelmes és röviden elintézhető volt a mátrixos eset, gondolom a kedves olvasó is sejti, hogy az éltárolásos forma már nem lesz ennyire 'kánaán'.

Kezdjük mindjárt a legegyszerűbbel! Hogyan keressünk meg egy élt?

Mivel egy élt a kezdő és végpontjával azonosítunk, ezen információk alapján igen gyorsan megtalálhatjuk a keresett élt. Uis a mutatótömb segítségével egyből behatárolhatjuk azon éltömb tartományt, ahol az adott kezdőpont élei találhatók, s mivel itt végpont szerint rendezettek az élek, akár binárisan is kereshetjük az adott élt.

Új él felvétele

- Meg kell keresnünk az élt az éltömbben. Mint minden keresés, igy ez is alkalmas arra, hogy ha nem találja meg a keresett élt, akkor visszaadja azt a sorszámot/indexet, ahová a keresett él beilleszkedik az élek közé. (Természetesen, ha már szerepel a felveendő él az élek között, akkor nem vehetjük fel mégegyszer.)

- Az így visszakapott helyre kell majd hátraléptetéssel beszúrni az új élünket. Előtte azonban célszerű ezen 'élmozgatásokat' leadminisztrálnunk a pontokhoz tartozó mutató tömbben. Mivel csak a felveendő új él kezdőpontja 'utáni' pontok kimenőéleit érinti ez a hátraléptetés, így csak ezen pontok mutatóit kell eggyel megnövelnünk. (Vegyük észre, hogy a kezdőponthoz tartozó mutató index nem fog megváltozni.)

- Növelnünk kell az élek számát eggyel.

Él törlése

A fentiek alapján az éltörléssel már könnyen elbánunk. Csak címszavakban:

- Az él megkeresése

- A kezdőpont 'mögötti' pontok (beleértve a PontDb+1. 'pontot' is) mutató indexeinek csökkentése

- Az él törlése az éltömbből előreléptetéssel

- Az élek darabszámának csökkentése

Ezzel pontot is tehetünk az adatkarbantartásra, azzal a rövid kiegészítéssel, hogy az éladatok módosítása ennél a tárolási formánál sem okoz problémát, hiszen az élek nem mozdulnak el a helyükről, csupán néhány éljellemző adat (pl. útkategória) íródik felül.

 

Archiválás

A hálózat/gráf adatainak megőrzése, adatfájlokban való tárolása, onnan való betöltése az adatkarbantartás kulcsfontosságú része. A kérdés nem is az, hogy tároljuk-e lemezen az adatainkat vagy sem, hanem inkább az, hogy milyen formában tároljuk? Nagyobb adathalmazok esetén többnyire megtalálhatók a szövegfájlok is, mint input-output adathordozók, hiszen a szövegformátumot valamennyi fejlesztőrendszer/szoftver képes kezelni és az adatok bennük könnyen és gyorsan javíthatók, bővíthetők. Az adatokat azonban elsődlegesen a gyors adatelérést, a könnyű kezelést biztosító, az adott fejlesztőrendszer (pl. C, Borland Pascal, stb.) által támogatott adatfájlokban célszerű tárolni.

Példaprogramunk az első részben ismertetett egyszerű szövegfájlt használja, amelyben először a pontok, majd az élek adatai tárolódnak. Ennek beolvasáskor van szerepe, hiszen a kezdetben üressé tett gráf egyszerűen 'felépíthető' a karbantartó alapeljárásokkal, hiszen a pontok az élek nélkül is felvehetők, s mire az élekre 'kerül a sor', a pontadatok már rendelkezésre állnak a ponttömbben.

2. ábra

A betöltést megkönnyítendő, készítettünk egy egyszerű fájlkiválasztó eljárást is, amellyel a grafikus képernyőn, egy sorban megjelenő 'választéklistából' lehet a kívánt NET kiterjesztésű adatfájl nevét kiválasztani.

Következő alkalommal már használni is fogjuk az eddig csak tárolt, később már kirajzolt, most pedig már karbantartott gráfunkat, bemutatva rajta a legrövidebb utak kereső algoritmusait.

Témánk végére érve most is szeretnék néhány gyakorló feladatot kitűzni:

Engedjük meg a pontazonosítók módosítását!

Bővítsük úgy a fájlkiválasztó eljárásunkat, hogy a fájlok neveit névsor szerint ajánlja ki.