Ha egy feladatot számítógép segítségével akarunk megoldani, sok esetben találunk olyan programot, amellyel (esetleg a feladatunk kisebb átalakításával, a kész és általunk nem módosítható program képességeihez, szolgáltatásaihoz való alkalmazkodással) különösebb számítástechnikai szaktudás nélkül, csupán a program felhasználói útmutatóját tanulmányozva és követve, a problémánk megoldható, a munkánk elvégezhető. Ilyen például egy jó táblázatkezelő program, amely nem túl bonyolult adatgyűjtési, nyilvántartási, statisztikai sőt könyvelési feladatok megoldója is lehet.

Ha ilyen programot nem találunk, mert problémánk egyedi, speciális, vagy nem is keresünk, mert célunk éppen a számítástechnikai programtervezés és programozás eszközeinek, módszereinek tanulmányozása, elsajátítása, akkor a számítógépre vitel folyamatában első, és sok esetben legnehezebb dolgunk egy megfelelő számítástechnikai modell keresése, megalkotása.

Ez a modell szükségképpen egy formális, matematikai pontossággal leírható, definiálható és számítástechnikai eljárásokkal, algoritmusokkal kezelhető modell kell hogy legyen, hiszen célja és értelme éppen az, hogy a feladat meghatározását átvigye az emberek közti, ennélfogva általában pontatlan és könnyen félreértelmezhető információcsere szintjéről a pontosan dolgozó és csak egyértelműen definiált utasításokat végrehajtani képes számítógép szintjére, vagyis röviden fogalmazva: a feladat a modell segítségével beprogramozható legyen.

A modellek a valósághoz képest természetesen egyszerűsítésekkel, általánosításokkal élnek. Nem tartalmazzák a feladat szempontjából elhanyagolható adatokat, jellemzőket, hiszen a jó modell kritériuma a fentiek mellett a viszonylagos egyszerűség, a lényeg kiemelése is. Ilyen értelemben például egy közönséges turisztikai várostérkép jó modellje a városnak arra a célra, hogy egy idegen eligazodjon benne, holott nem tartalmazza többek közt a házak magasságát, vagy az utcák pontos szélességét. Persze egy autós turista számára már csak egy olyan térkép tekinthető jónak, amelyről a legfontosabb közlekedési szabályozások (pl. egyirányú utcaszakaszok) is leolvashatók.

A feladatok egy részénél a leginkább megfelelő modellt a gráfok illetve hálózatok világában lelhetjük fel. Arról hogy mi egy gráf ill. egy hálózat mindenkinek vannak többé - kevésbé kialakult fogalmai, hiszen hallott már úthálózatról, telefonhálózatról, kereskedelmi hálózatról vagy éppen ügynökhálózatról (és még sokféle más hálózatról is), ezek egy részével a mindennapi életében, munkájában kapcsolatba is került. Érezzük, hogy ezek között van egy a konkrét megjelenési formától, sőt a funkciótól is független mélyebb szerkezeti, struktúrális hasonlóság, az amit a gráf és hálózat matematikai fogalma fejez ki.

A jelen cikkel induló programozástechnikai sorozat célja az, hogy bevezető, alapozó jelleggel megismertesse az olvasót a gráfok és hálózatok mint számítástechnikai modellek alapfogalmaival, alapvető kezelési módszereivel és eszközeivel. Tárgyaljuk a számítógépes tárolás, a grafikus megjelenítés kérdéseit, a legfontosabb karbantartási és lekérdezési funkciók megvalósítását. Megismerünk néhány, célját illetően közérthető, nem túl bonyolult hálózatkezelő algoritmust. Az ismertetett eljárások többségét grafikus megjelenítéssel, a működés grafikus követésével is demonstráljuk. Az egyes témák természetesen nem függetlenek, a közlési sorrendben egymásra épülő cikk és programsorozatról van szó.

Kipróbálható, futtatható algoritmusok közléséhez természetesen szükség van egy hordozó, közvetítő közegre, erre a célra a Borland Turbo Pascal 7.0 (DOS) nyelvet illetve programfejlesztő környezetet választottuk. Ez, feltevésünk szerint általában hozzáférhető, és meggyőződésünk szerint a legalkalmasabb eszköz ilyen célra, mert az adat és vezérlési struktúrák bő választékával rendelkezik, és emellett nem kell sok más olyan dologgal is foglalkoznunk, amelyek célunk szempontjából közömbösek, és csupán a fejlesztési - futtatási környezetből adódnának.

A téma természetesen komoly gyakorlati jelentőséggel is rendelkezik. Ezekkel a modellekkel oldanak meg - persze itt a gyakorlati alkalmazásoknak megfelelően megnövelt és bővített, tár és futásidő szempontjából optimalizált, igényes megjelenítési környezetben elhelyezett alkalmazásokról van szó - sok és sokféle tervezési, optimalizálási és más egyéb feladatot. Néhány ilyen feladatkör: szállítási tervek készítése, közlekedési hálózatok tervezése és vizsgálata, összetett, egymásra épülő résztevékenységekből álló feladatok (pl. egy házépítés) ütemezése, pszichológiai és szociológiai vizsgálatok, elektromos hálózatok tervezése és analízise.

Alapfogalmak

Az alábbiakban nem matematikai jellegű definíciókat adunk, inkább a programtervezésben elegendő pontosságú, intuitív fogalmak kialakítására törekszünk.

Gráfon bizonyos objektumok és a köztük fennálló közvetlen kapcsolatok halmazát értjük. Két objektum között vagy van vagy nincs közvetlen kapcsolat. Az objektumok és a kapcsolatok további jellemzői itt közömbösek. Nevezzük az objektumokat pontoknak, a kapcsolatokat éleknek. Grafikus ábrázolásban a pontokat egyszerű geometriai alakzatokkal (kör, négyzet ...), az éleket a pontokat összekötő szakaszokkal szoktuk jelölni (1. ábra). Nézzünk két példát:

  • A pontok emberek, két pont között akkor van él, ha a két ember ismeri egymást. Lehet a megfelelő gráf akár az 1. ábra is. Viszont, ha egy olyan szervezetről van szó, ahol mindenki csak a saját főnökét és saját beosztottjait ismerheti (pl. egy illegális szervezet), akkor a megfelelő gráf inkább a 2. ábrán látható lesz. (Az ilyen speciális struktúrájú gráfokat fa gráfoknak nevezzük.)
  • Egy város utcahálózatának kereszteződései legyenek a pontok, az összekötő szakaszok az élek. Ilyen gráf lehet pl. a 3. ábra.

Ezek után vezessünk be még néhány fogalmat, elnevezést:

Egyszerű gráf az olyan gráf, amelyben bármely két pont között legfeljebb egy él van és nincs hurokél (hurokél: egy pont önmagával való kapcsolata pl. egy olyan útszakasz, amelynek kezdő és végpontja azonos). Mi itt csak egyszerű gráfokkal foglalkozunk, példáink ilyenek, algoritmusaink is ezekre vonatkoznak.

Teljes gráf az olyan gráf, amelyben bármely két pont között van él. Például egy baráti társaság, ahol mindenki ismeri egymást (4. ábra).

Irányított gráf az olyan gráf, amelyben az élekhez irányítást is rendelünk, kifejezve ezzel a nem feltétlenül szimmetrikus kapcsolatokat. Az él irányítása nyilvánvalóan éppen háromféle lehet, egy a és egy b pont viszonylatában:

- az a -ból a b -be mutató (csak az a - b kapcsolat áll fenn)

- a b -ből az a-ba mutató (csak a b - a kapcsolat áll fenn)

- mindkét irányban mutató (mind az a - b, mind a b - a kapcsolat fennáll)

Példák irányított gráfokra:

  • A pontok emberek, az a-ból b-be akkor mutat él, ha a utasításokat adhat b -nek (5. ábra).
  • A pontok közlekedési csomópontok, az a-ból b-be akkor mutat él, ha az ezirányú közlekedés lehetséges (az egyirányú útszakaszok nem szimmetrikus kapcsolatok).(6.a ábra).

Sok esetben egyszerűbb rajzban a szimmetrikus (mindkét irányú) kapcsolatokat az irányítás nélkül jelölni (6.b ábra), máskor viszont kifejezőbb (gondoljunk például egy utcaszakasz két oldalára) a kétirányú él elnevezés helyett két darab egyirányú élről beszélni és a rajzi ábrázolásmódban is ezt követni (6.c ábra).

A modellezendő problémák jelentős részében nem csak a pontok közti kapcsolatok megléte vagy hiánya fontos, hanem az is, hogy a kapcsolathoz egy mennyiség, mérőszám is tartozzon, például egy közlekedési hálózat a-ból b-be mutató éle milyen hosszú, vagy (egy átlagos sebességet feltételezve) mennyi idő alatt jutunk el az élen haladva az egyik pontból a másikba. Ha a modellünket ezzel bővítjük, vagyis az élekhez mérő, súlyozó számokat rendelünk, akkor már hálózatról beszélünk. Irányított gráf esetén ezek a számok irányonként is különbözhetnek, tehát egy kétirányú él két irányához tartozhat két különböző érték. Az alkalmazásokban általában nem csak az élekhez, hanem a pontokhoz is tartoznak ilyen számok, például egy közlekedési csomópont esetén a térképi koordináták vagy a forgalomirányítás módját (pl. lámpás, egyenrangú) leíró adatok.

A hálózat tehát a kapcsolatokat leíró gráf valamint a pontokhoz és az élekhez tartozó adatok, a pontjellemzők és az éljellemzők együttese. Ennek tárolási és feldolgozási kérdéseivel foglalkozunk.

A tárolás kérdései

A számítástechnikai modellekben elsődlegesen megoldandó részfeladat az azonosítás, tehát a hálózati pontokhoz és élekhez egyértelmű, és programmal kezelhető elnevezéseket, azonosítókat kell rendelnünk. Elsődleges a pontok azonosítása, az éleké ezekre már könnyen visszavezethető.

A pontok 'természetes' vagyis a modellezendő feladatbeli azonosítója általában egy hosszú 'beszélő' jellegű kód, mint pl. a személyi szám vagy közlekedési hálózatnál a keresztező két út neve. Ezt a számítástechnikai modellben egyszerűsítjük, egy sorszámmá transzformáljuk. (Persze az eredeti azonosító - sorszámazonosító megfeleltetést külön tárolnunk kell, hogy az eredményadatokat az eredeti azonosítási rendszerben is közölni tudjuk.) Mi itt a példáinknál és a példaprogramokban is egyszerűen megbetűzzük a pontokat, valamelyik ponttól kezdve, abc sorrend szerint haladva és csak az angol abc kisbetűit (a..z) használva. Nyilván így csak maximum 26 pontos hálózatokat vehetünk fel, de célunknak ez is megfelel, a demonstrációhoz az elvek és módszerek szemléltetéséhez ez is elegendő.

Az éleket az általuk össszekapcsolt két ponttal azonosítjuk, tehát az a és b közti élet ab jelöli, illetve ha a gráf irányított akkor ab jelöli az a -ból a b -be mutató, ba pedig a fordított irányú élet (vagyis az él másik irányítását) .

Az azonosítási kérdést megoldva már lehetséges, hogy kapcsolatot keressünk a hálózat és a programozásban használatos, a programnyelvben (Pascal) leírható adatszerkezetek között.

Mint a programozás elemeiből tudjuk, a legegyszerűbb adatszerkezetek a tömbök, amelyek azonos típusú értékeket egy vagy több dimenzióban sorszám (index) szerint elrendezve tárolnak. Közvetlenül adódik egy egyszerű, az alkalmazott legbonyolultabb tömbről mátrixos tárolási formának nevezett adatszerkezet. Ebben a pontjellemzőket a pontsorszámmal (nevezzük ezt pontindexnek) indexelve egydimenziós tömbökben, az éljellemzőket (irányítás szerint bontva) a kétdimenziós tömbökben, mátrixokban tároljuk. Példaképpen nézzük a 7. ábra hálózatát. Ezt egy úthálózatnak feltételezve a gráfhoz három pontjellemzőt veszünk fel: T a csomópont típusa (egyjegyű szám, az ábrán a pontokhoz írt kis számok), X és Y a csomópont koordinátái (az ábrán nincs feltüntetve). Az éljellemzők száma kettő: egyik az útszakasz hossza (H), a másik az útszakasz minőségét kifejező kategóriakód (K), (az ábrán az élek mellett nagyobb ill. kisebb számokkal feltüntetve). A példában feltételezzük, hogy a hossz és a kategória mindkét irányban ugyanaz. A hálózat mátrixosan tárolt alakja a 8. ábrán látható.

Egy adatszerkezet megválasztásánál, minősítésénél számítástechnikai szempontból általában három fő tényező veendő tekintetbe:

- a tárkihasználás és az operatív tárban való tárolhatóság

- a karbantarthatóság vagyis a változások átvezetésének műveletigénye

- a lekérdezhetőség vagyis az információkinyerés műveletigénye

Az első tényező számításigényes feladatoknál - és a hálózatkezelő algoritmusok ilyenek - kiemelt fontosságú, hiszen a háttértár használata nagyságrendekkel lassítja a számításokat. A második tényező fontossága attól függ milyen gyakoriak a változások. A harmadik tényezőt illetően jellemző lekérdezési mód a pont és éljellemzők kötetlen, véletlenszerű sorrendű elérése. Vizsgáljuk meg mind a mátrixos tárolást mind a még ezután részletezendő tárolási módszereket e szempontok szerint. Bármelyik tárolási formát is nézzük, a pontjellemzőkkel nincs, illetve kevesebb a probléma, a kérdés lényege az éljellemzők tárolása.

A mátrix tárkihasználása erősen függ a gráftól. Mint könnyen beláthatjuk, legjobb a tárkihasználás a teljes gráfok esetén, hiszen ezeknél csak a főátló tartalma a redundáns információ. Az un. ritka gráfoknál, amelyeknél az elvben lehetséges kapcsolatoknak csak nagyon kis része valósul meg, a mátrix ebből a szempontból nagyon gazdaságtalan. Például egy 1000 pontos hálózat 999000 irányított élet tartalmazhatna, de ha ez pl. egy közlekedési hálózat, akkor az élek száma nagy valószínűséggel 5000 alatt van, tehát a kihasználtság az 1 százalékot sem éri el. Az operatív tárban való tárolhatóság csak nem nagy hálózatoknál kivitelezhető. Példának véve egy 4 bájton tárolható éljellemzőt, ennek mátrixa 100 pontos hálózatnál 40000 bájt egy egyszerű PC -n is teljesíthető, 1000 pont esetén a 4 millió bájtos mátrixhoz már komolyabb kiépítettség kell, 10000 pontnál a tárolásra már nem is gondolhatunk.

A mátrix karbantarthatósága kedvező. Élet felvenni, törölni, él vagy pontjellemzőt módosítani nagyon egyszerű, hiszen csak át kell írni egy tömbelemet. Az új pont felvétele vagy törlése már műveletigényesebb, hiszen ez sorok és oszlopok mozgatását igényli.

A mátrix lekérdezhetősége optimális, a lehető leggyorsabb és legegyszerűbb módon jutunk el az azonosítótól a jellemzőig. Pontjellemzőnél ez egy, éljellemzőnél két indexelést jelent.

Sajnos, a gyakorlati méretű feladatok többségénél előnyei ellenére sem választhatjuk a mátrixtárolást a hatalmas tárigény miatt. Keresni kell a tárolási redundancia csökkentését, esetleg a másik két szempont rovására is.

A következő, csak egydimenziós tömböket alkalmazó módszer lényege az éltárolás, vagyis az az elv, hogy csak a ténylegesen meglévő kapcsolatok jellemzőit tároljuk, az élek bizonyos rendezettsége szerint. Az adatszerkezetet a 7. ábra hálózatára a 9. ábra szemlélteti. Mint ebből látható, az éljellemzőket tömören, egy a kezdőpont (Kp) szerint rendezett sorban tároljuk, az M mutatóérték mondja meg, hogy a sor mely szakasza tartozik egy-egy kezdőponthoz, és ez a Vp pontindex értékkel, együtt határozza meg az élt.

Az éltárolás tárkihasználása nagyon jó, a memóriaigény az élek számával lineárisan nő, többezer sőt néhány tízezer élet tartalmazó hálózat is tárolható a ma már elérhető, átlagosnak tekinthető személyi számítógépes memóriaméretben (4 - 16 Mbájt).

A számítástechnikai modellezésnél általánosan érvényesül az, hogy tárat csak idő, időt pedig tár árán nyerhetünk. Várható tehát, hogy az éltárolás karbantarthatósága és lekérdezhetősége a mátrixénál rosszabb lesz. Akár új élet veszünk fel, akár meglévőt törölünk (vagy pontot törölünk), a tömör tárolás miatt a tömbelemek egy részét meg kell mozgatni, át kell pakolni. Az éljellemzők eléréséhez a kezdőpontsorszámmal az M mutatót indexelve a neki megfelelő részszakaszt ugyan egy lépésben elérjük, de innen kiindulva a már keresni kell a végpontot. A keresés meggyorsítása céljából célszerű a Vp soron belül az azonos kezdőponthoz tartozó végpontindexeket rendezetten tartani. Minél ritkább a hálózat, annál gyorsabb átlagosan a lekérdezés.

Ha a gyors karbantarthatóságot tesszük meg fő szempontnak akkor a memóriaigényt (az éltároláshoz képest) nem nagy mértékben növelve gondolhatunk egy dinamikus összetett listaszerkezetre is, amely kétféle, egy pont és egy éljellegű listaelemből (rekordból ) építkezik, a jellemzőket a rekordokban tárolva, a kapcsolatokat mutatókkal (pointer) megvalósítva (10. ábra, az ábrán csak a hálózat egy része szerepel, de a módszer ebből is látható). Ebben élet, pontot felvenni vagy törölni egyszerűen lehet, hiszen az éltárolással ellentétben adatokat nem kell mozgatni, a funkciók mutatók felvételével törlésével és átirányításával megoldhatók. A tárigény is kedvező, hiszen az adatokon kívül csak a pointereknek kell tárhely. A lekérdezhetőség már kevésbé jó, hiszen listákon való lépkedéssel jutunk el az adatokhoz, ami mindig lassúbb mint a tömbökben való keresés.

 

Természetesen a hatékonyabb karbantarthatóság és lekérdezhetőség céljából - újabb adatszerkezeti elemek felvételével - további tárolási módokat is alkalmazhatunk. Erre csak egy példát hozunk: ha a listaszerkezetet egy olyan tömbbel bővítjük, amely minden ponthoz egy a listaszerkezetben a pontra mutató pointert tartalmaz, az élkeresést lerövidíthetjük, hiszen a kezdőpontot nem kell a listaszerkezetben megkeresni (11. ábra).

Példaprogramok

A cikksorozatunkat a lemezmellékleten kísérő példaprogramsorozathoz egy egységes grafikus képernyős felhasználói felület tartozik, a programoknak a Borland Turbo Pascal 7.0 fejlesztőrendszerben való fordításához és futtatásához az ezt megvalósító unitok is szükségesek. Ez a programcsomag a Dr. Marton László: Bevezetés a Pascal nyelvű programozásba (NOVADAT Bt. Győr 1996) című könyv része, itteni felhasználása és közlése a kiadó és a szerző engedélyével történik. Itt a unitok interface részét forrásnyelvi formában, magukat a unitokat lefordított (TPU) közöljük. További információk erről a programcsomagról a hivatkozott könyvben találhatók.

A példaprogramoknál természetesen egy külső, háttértárbeli hálózatmegadási forma definiálása is szükséges. Egy hálózat adatait egy szövegfájlban tároljuk, a fájlazonosítók kiterjesztés része egységesen NET lesz, név része tetszőleges DOS fájlnév. Ez a képernyőkön is megjelenik hálózatnévként. A szövegfájlok szerkezete:

pontok száma

pontazonosító pontjellemző ... pontjellemző

...

pontazonosító pontjellemző ... pontjellemző

irányított élek száma

élazonosító éljellemző ... éljellemző

...

élazonosító éljellemző ... éljellemző

Konkrét példafájlok a lemezmellékleten találhatók.

A példasorozat első része tartalmazza az egyes tárolási formák közti átalakítás eljárásait, a grafikus megjelenítés első, egyszerű változatát valamint egy, a grafikus képernyőn direkt módon kirajzolható koordinátájú négyzetrács hálózatot/gráfot generáló eljárást.

A grafikus megjelenítés általános problémáiról, azok megoldási módszereiről, és a grafikus lekérdezések megvalósításáról a következő részben olvashatunk majd. Ebben - az előbb említett generáló eljárásunkkal - már 'nagy', a képernyőn direkt módon nem ábrázolható - gráfot is előállítunk.

Cikkeink végén mindig kitűzünk majd néhány egyszerűbb feladatot, amelyek megoldása alapja lehet a téma jobb, mélyebb megismerésének ill. példaprogramjaink univerzálisabbá tételének.

Feladat:

Gondoljuk meg, (egy kicsit a részletesen később tárgyalandó karbantartásra is előretekintve), hogy milyen előnyei illetve hátrányai vannak az éltárolás módszerénél az M kezdőélmutató alkalmazásának, mondjuk ahhoz képest, hogy helyette (a Vp -hez hasonlóan) minden élhez közvetlenül odaírnánk a kezdőpontindexet.