Automatikus elrendező algoritmusok vizsgálata gráfminták megjelenítésére

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

A szoftverfejlesztés világában egyre jobban elterjed a modellvezérelt fejlesztés. Ez a módszer a hangsúlyt az elkészítendő rendszer modelljének létrehozására teszi. Egy modellvezérelt módon tervezett rendszer teljes modellje, gyakran túl sok elemből állhat, a megfelelő átlátás és egyszerű megértés szempontjából. Ezen segít a modellek feletti lekérdezés. A megfelelő deklaratívan megadott kényszerek segítségével ez a teljes modell leszűkíthető egy kisebb elemszámú részmodellre. Ezzel egy jobban átlátható részhalmazát kapjuk a teljes modellnek. Ezen részhalmaz grafikus ábrázolása gyakran gráfoknak történő megfeleltetéssel történik, a szöveges reprezentációval szemben, még jobban könnyítve ezzel az emberi agy számára a feldolgozást, megértést.

A modellek létrehozására a legnépszerűbb eszköz, az Eclipse alapokra épülő Eclipse Modeling Framework (későbbiekben EMF). A modell-lekérdezések definiálását a Méréstechnika és Információs Rendszerek tanszéken fejlesztett EMF-IncQuery modul teszi lehetővé. Ezek gráfként való ábrázolását pedig a Zest-tel valósíthatjuk meg. A Zest beépülésével nem csak lehetőséget kapunk gráfok tetszőleges ábrázolására, hanem előre megírt elrendező algoritmusokat is. Ám ezek lefuttatásából származó elrendezések gyakran kívánni valót hagynak maguk után.

A gráfoknak megfeleltetett modellek a rendszertől függően nagyon különbözőek lehetnek. Ebből következően egy rendező algoritmus megfelelő eredményt nyújt egy bizonyos részgráfra, de egy másikra ez már koránt sem biztos, hogy igaz lesz. A Zest beépülve az Eclipsebe lehetővé teszi új algoritmusok implementálását, amiket már lehet specifikálni az adott gráfra. Ezen felül a már meglévő algoritmusok kiegészíthetők modellspecifikus, vagy olyan általánosabb részekkel, amit a felhasználó az összes ábrázolandó gráfra kiterjesztene.

A dolgozatomban a már meglévő algoritmusok vizsgálata után az általam kiegészített Sugiyama algoritmust fogom bemutatni. Az általam implementált új heurisztikákkal jobb elrendezések érhetőek el, melyek szintén bemutatásra kerülnek. A kiterjesztések megvalósításánál fontos szempont volt, hogy alkalmazhatóak legyenek más elrendező algoritmusok használatakor is.

Letölthető fájlok

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