Gráfelrendező algoritmusok kiértékelése

OData támogatás
Konzulens:
Ujhelyi Zoltán
Méréstechnika és Információs Rendszerek Tanszék

Összefoglaló

A különböző tudományágakban használt adatok, az adatok közti kapcsolatok és folyamatok modellezésére nagyon gyakran a gráfok a legmegfelelőbbek. Egyszerűségük ellenére nagyon sokrétű, bonyolult modellek leírására képesek, mely történhet szöveges nyelvek használatával, objektum orientált környezetben létrehozott osztálymodellekkel és egyéb szoftveresen feldolgozható módszerek segítségével. Mivel a gráf modellek csak struktúrát írnak le, az emberi feldolgozás könnyítése érdekében, valamilyen módon meg kell jelenítenünk őket. A megjelenítéshez különböző elrendezéseket használhatunk.

A dolgozatban automatikus gráf elrendező algoritmusok kiértékeléséhez adok támogatást. A célom, hogy megvizsgáljam az elrendezéseket a választott gráf modell, algoritmus és paramétereinek függvényében. Ilyen paraméter lehet például az iterációs lépések száma vagy a rajzterület mérete.

Egy elrendezés minőségét statikus és dinamikus megjelenítési szempontok alapján mérhetjük. Egy statikus kritérium a gráf egy felrajzolását jellemzi. Ilyen például az élmetszések vagy a csomópont átfedések számának minimalizálása. A dinamikus viselkedés határozza meg, hogy a gráf modell vagy a konfiguráció módosításának hatására hogyan változik az elrendezés.

Az elemzés elvégzésére létrehozott teszt környezet lehetővé teszi, hogy az algoritmusokat különböző gráf modellekre, különböző konfigurációs beállításokkal alkalmazzuk és az elrendezést jellemző statikus és dinamikus metrikákat számoltassunk. Lehetőség van a gráf modell és az algoritmus paraméterek módosítására is, így az algoritmusok dinamikus viselkedését is vizsgálhatjuk.

Az gráf rendezések ilyenforma kiértékelésének használhatóságát három különböző működésű algoritmus vizsgálatával demonstrálom. Az eredményeimből kiderül az egyes paraméterek módosításának hatása a megjelenésre, ami alapján konfigurálni lehet az egyes algoritmusokat dinamikus viselkedésük figyelembe vételével.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.