GráfRajz fejlesztői dokumentáció

GráfRajz fejlesztői dokumentáció Fejes Ádám - FEASAAI.ELTE - [email protected]

GráfRajz fejlesztői dokumentáció Követelmények: A GráfRajz gráfokat jelenít meg grafikus eszközökkel. A gráfot többféleképpen lehet a programba betölteni. A program a gráfokat egyedi fájl szerkezetben tárolja. A fájlokból betölthetőek az előre eltárolt vagy a felhasználó által, a grafikus felület keresztül megadott és később fájlba mentett gráfok. Továbbá a programban implementálva vannak a fontosabb gráfelméleti algoritmusok, például különböző típusú fák építése. A felhasználó által megadott csúcspontokból a program folyamatosan építi a kiválasztott típusú fát. Az elkészült gráfokon szemléltethetőek a nevezetes bejárási algoritmusok által generált útvonalak.

Alapvető fogalmak:   

Grafikus eszközök: A program egyszerű grafikai elemekkel fogja ábrázolni a gráfot. A gráf csúcsait egy kör, míg az éleket egy-egy összekötő vonal fogja reprezentálni. Egyedi fájlszerkezet: Az a módszer, amivel a gráf éleit, csúcsait és egyéb adatait (irányítottság, súlyozottság) egyértelműen eltároljuk. Gráf: A gráf dolgok (csomópontok, csúcsok) és rajtuk értelmezett összeköttetések (élek) halmaza. Egy gráfot megadhatunk csúcsainak és éleinek felsorolásával, vagy szemléletesebben egy diagram formájában, ahol a pontok felelnek meg a gráf csúcsainak, az őket összekötő ívek pedig az éleknek. o Irányított / Irányítatlan gráf: Irányítatlan esetben nem tartjuk nyílván az egyes élek irányát, azaz mindkét irányban lehet rajta „közlekedni”. Irányított esetben, csak a megadott irányba haladhatunk a gráfon („egyirányú utca”). Így a két összekötött csúcs „szülő – gyerek” viszonyban van. o Súlyozott / Súlyozatlan: Súlyozott esetben az egyes élekhez nyilvántartunk egy számértéket, ami az él súlya vagy más néven költsége lesz. A súly az útkeresési algoritmusokat teheti kifinomultabbá. o Szülő – gyerek: Irányított gráf esetén a szülő csúcsból kimenő élen a gyerek csúcsba érünk, ahonnan nem léphetünk vissza (hacsak nincs visszafelé is vezető párhuzamos él). o Párhuzamos él: Párhuzamos élnek nevezzük azokat az éleket, melyek ugyanazt a két csúcsot kötik össze. o Hurok él: Hurok élnek nevezzük, azt az élt melynek kiindulási csúcsa megegyezik a cél csúcsával. o Egyszerű gráf: Az egyszerű gráfban nincsen se hurok, se párhuzamos él. o DAG: Directed Acyclic Graph, azaz irányított, körmentes gráf. o Körmentes gráf: A körmentes gráfban nem tudunk olyan utat kijelölni, melyben érintenénk egy korábban már érintett csúcsot. o Út: A gráf adott csúcsából induló „csúcs – él – csúcs” sorozat. o Fa: A fa olyan gráf melynek bármely két pontját egy és csakis egy útvonalon köthetjük össze, azaz körmentes összefüggő gráf. o Összefüggő gráf: Az összefüggő gráf bármely csúcsából bármely csúcsába vezet út.

GráfRajz fejlesztői dokumentáció Fejes Ádám - FEASAAI.ELTE - [email protected] Nem funkcionális követelmények   

A program dinamikus reagál a felhasználói interakcióra. A gráf szerkesztésekor a változások azonnal megjelennek az ábrán. A gráf szerkesztő „bolondbiztos” azaz nem engedélyez érvénytelen műveletet, szigorúan betartja a szabályokat, melyek a gráf tulajdonságának megmaradásért felelősek. Pl.: súlyozott gráfba nem enged új élt felvenni súly megadása nélkül. A program Java nyelven van implementálva, ezért futtatásához szükséges a Java virtuális gép legfrissebb verziója.

Használati eset modellek:

uc Primary Use Cases

Betöltés fáj lból

Módosítás «include» Felhasználó

Raj zolás



Betöltése fájlból: A felhasználó egy már korábban a programmal elkészített gráfot tölt be és jelenít meg. Betöltés után a felhasználó módosíthatja, majd újra elmentheti a gráfot. Előfeltétel: Szükséges egy érvényes, azaz a tárolási konvenciónak megfelelő fájl, amit a program beolvashat. Utófeltétel: A gráfban a program nem engedélyez olyan módosításokat mellyel a gráf korábban beállított tulajdonságai sérülnek. Pl.: Ha csak pozitív él költségek érvényesek, akkor a felhasználó ne vehessen fel negatív költségű élet.



Rajzolás: A betöltött gráfot a program megjeleníti.



Módosítás: A gráfon módosításokat hajthat végre a felhasználó, melyek automatikus újrarajzolást indítanak, így a változások azonnal megjelennek az ábrán.

GráfRajz fejlesztői dokumentáció Fejes Ádám - FEASAAI.ELTE - [email protected]

uc Primary Use Cases

Új gráf létrehozása

Raj zolás

«include»

«include» Felhasználó Paraméterek beállítása

Gráf építése «include»



Új gráf létrehozása: A felhasználó új gráf építésébe kezdhet. Beállítja a kezdeti paramétereket, melyek a gráf típusát határozzák meg, majd felveszi a gráf csúcsait és éleit. Előfeltétel: Utófeltétel: A bevitt adatoknak megfelelőnek kell lenniük a paraméterül adott gráf típusához. Pl.: Egyszerű gráf esetén nem engedélyezi a program a hurok és párhuzamos élek felvételét.



Paraméterek beállítása: A gráf paramétereinek megadása. Irányítottság, súlyozottság stb



Gráf építése: A felhasználó egyenként felveszi a gráf elemeit, melyek folyamatosan megjelennek az ábrán.

GráfRajz fejlesztői dokumentáció Fejes Ádám - FEASAAI.ELTE - [email protected] Képernyő terv

custom Primary Forms Új gráf

Fő képernyő Menü

Súlyozott

Új gráf Irányított

«navigate» Gráf betöltése

Csúcsok

Gráf mentése

Fa

Gráfban lévő csúcsok és élek

Rajzterület OK

Mégse «navigate» «navigate»

Csúcsot töröl

Élek

Gráf módosítása

Szabv ányos fáj lkezelő ablak

Új él Új csúcs Költség Élet töröl

Címke Csúcsból

Csúcsba Mégse

OK

«navigate» Új csúcs Új él

«navigate»

OK

Mégse

Gráf     

adatai Irányítottság Súlyozottság Fa-e? Élek száma Csúcsok száma

Gráf paraméterei

A program egy főablakból és négy párbeszédablakból fog állni. A főablak nagy részét a gráf kirajzolási terület foglalja el. Továbbá itt érhetőek el a gráf módosító funkciók, melyek egységesen az ablak jobb szélére vannak csoportosítva. A párbeszédablakok funkciói:  

 

Új gráf létrehozása: A meglévő betöltött gráfot a program bezárja és egy új, üres gráfot hoz létre helyette. A régi gráf bezárása előtt természetesen a program lehetőséget ad annak mentésére. Él hozzáadása: Az aktuálisan megnyitott gráfhoz adhat hozzá új élt. Ha a gráf súlyozott, meg kell adni egy súlyt, illetve minden esetben kötelező megadni a kiindulási és a cél csúcsot. Ha a gráf nem irányított, akkor a forrás és cél csúcs egyenrangúnak tekinthető és ezt a program figyelembe is veszi, de a párbeszéd ablak azonos lesz az irányított esetben látottal. Csúcs hozzáadása: A programnak meg kell adni egy csúcsazonosító címkét. Gráf mentése / betöltése: A program megjelenít egy Swing keretrendszerbe beépített, szabványos fájlkiválasztó ablakot, melyben elvégezhetjük a szükséges műveletet.

GráfRajz fejlesztői dokumentáció Fejes Ádám - FEASAAI.ELTE - [email protected] Szakterületi osztálydiagram

class Szakterületi

Main

GraphLogic

Graph

Tree

1 1

New GraphWindow 0..*

1 GrafRaj zWindow

Edge

0..1

0..* Node

New NodeWindow 0..1

1 MyCanv as

0..1 New EdgeWindow

Algorythms

Main: A program belépési pontja. Egy példányt fog tárolni a program ablakból. GrafRajzWindow:    

Ős: javax.swing.JFrame Sztereotípia: vezérlő / határ Példány: grafRajzWindow Feladat: Megjeleníti a fő program ablakot. Szülő ablaka a párbeszédablakoknak. Tartalmazza a rajzterületet és a program logikájáért felelős osztály példányát.

GráfRajz fejlesztői dokumentáció Fejes Ádám - FEASAAI.ELTE - [email protected]

MyCanvas:    

Ős: java.awt.Canvas Sztereotípia: határ Példány: canvas Feladat: egyszerű grafikus elemekkel megjeleníti a gráfot

GraphLogic:    

Ős: Sztereotípia: vezérlő Példány: graphLogic Feladat: Tárolja a gráfot. Kezeli a fájlműveleteket. Előkészíti a gráfot a kirajzoláshoz.

Graph:    

Ős: Sztereotípia: konténer Példány: graph Feladat: Gráf reprezentáció. Tárolja a gráf csúcsait és éleit. Éllistás megvalósítást használ.

Node:    

Ős: Sztereotípia: konténer Példány: Feladat: Egyszerű adatszerkezet, amely a gráf egy csúcsát reprezentálja. Egy azonosítót és egy listát tartalmaz a kimenő élekről.

Edge:    

Ős: Sztereotípia: konténer Példány: * Feladat: Egyszerű adatszerkezet, amely a gráf egy élét reprezentálja. Egy célcsúcsot és egy súlyt tartalmaz (ha a gráf súlyozott).

GráfRajz fejlesztői dokumentáció Fejes Ádám - FEASAAI.ELTE - [email protected]

Tree:    

Ős: Graph Sztereotípia: konténer Példány: graph Feladat: Egy speciális gráf, a fa reprezentációja. A Graph ősosztálytól annyiban tér el, hogy a gráf szerkesztése közben nem engedélyez olyan műveletek, melyek megsértenék a gráf fa tulajdonságát. Pl.: nem enged kört létrehozni a gráfban.

NewGraphWindow:    

Ős: javax.swing.JFrame Sztereotípia: határ Példány: new Feladat: Új gráf létrehozásakor megjelenő párbeszéd ablak. A gráf paramétereit lehet beállítani benne.

NewNodeWindow:    

Ős: javax.swing.JFrame Sztereotípia: határ Példány: new Feladat: Csúcs hozzáadáskor megjelenő párbeszéd ablak. Megadhatjuk benne a csúcs azonosítóját.

NewEdgeWindow:    

Ős: javax.swing.JFrame Sztereotípia: határ Példány: new Feladat: Él hozzáadásakor megjelenő párbeszéd ablak. Megadhatjuk benne az él költségét, forrás és cél csúcsát.

Algorythms:    

Ős: Sztereotípia: függvénykönyvtár Példány: Feladat: Statikus könyvtár mely gráf algoritmusokat tartalmaz.