A Hozzárendelési feladat szemléltetése Java programozási nyelven szakdolgozat
Szilárd András
III. programozó matematikus
Dr. Csendes Tibor témavezet®
Szegedi Tudományegyetem, Természettudományi Kar, Alkalmazott Informatikai Tanszék
Szeged
2004
Feladatkiírás A Hozzárendelési feladat az operációkutatás egyik fontos alapfeladata, megoldására a többi között az ún. Magyar módszer is jól alkalmazható. Jelenleg a szegedi programozó szakokon több kurzus anyagának is részét képezi a probléma. (Operációkutatás I., Kombinatorikus optimalizálás). Ezért hasznos lenne egy olyan program, amellyel ellen®rizni lehet a megoldandó feladatokat. Jelen szakdolgozat f® célkit¶zése, hogy a hallgató egy általa választott programozási nyelven, implementáljon egy olyan számítógépes programot, amely helyesen megoldja az ún. Hozzárendelési feladatot. A megoldás menete támaszkodjon a Magyar módszer néven ismert eljárásra. A program alapvet® feladata az, hogy helyesen oldja meg a futási id®ben megadott, tetsz®leges hozzárendelési feladatokat. A további funkciók közé tartozik az, hogy legalább két üzemmódban legyen képes a feladatok megoldását végezni: egyikben részletes üzeneteket kell generálnia az eljárás során, míg a másikban elegend® a végeredményt bemutatnia. A részletes, magyarázó szöveges üzenetek megjelenítésével egyid®ben, vizuális szemléltetést is megkívánunk a programtól, oktatási szempontok gyelembe vételével.
i
Tartalmi összefoglaló Szakdolgozatom kit¶zött témája a Hozzárendelési feladat, Magyar módszerrel történ® megoldásának szemléltetése volt, tetsz®legesen választott programozási nyelven. A feladatot sikerrel oldottam meg Java programozási nyelven, s®t a nyilvánvaló kívánalmakon túl további el®nyös szempontokat is gyelembe vettem már a tervezés során. Dolgozatomban el®ször ismertetem a Hozzárendelési feladatot egy egyszer¶ példán keresztül, majd bemutatom az operációkutatásból ismert matematikai modelljét. Ezután részletesen tárgyalom a probléma hatékony megoldására szolgáló Magyar módszert. A dolgozat érdemi részét a számítógépes megoldáshoz felhasznált ötletek, technikák, módszerek alkotják. Ennek els® fejezetében röviden ismertetem a Java nyelvet, amelyet a megoldáshoz alkalmaztam. Majd röviden kitérek olyan részletekre, amelyek fontosak voltak a megvalósítás szempontjából. Az ezt követ® fejezetek részleteiben elemzik a szoftver létrehozásának lépéseit. Elmagyarázom, hogy mi indokolta egy-egy döntésem, azokban az esetekben, ahol esetleg több megoldási mód is kínálkozott volna. Végül példákon keresztül illusztrálom a kapott eredményeket. A létrehozott szoftver a Java-nak köszönhet®en végrehajtható kód szintjén architektúra-független, képes önálló- és hálózati alkalmazásként is m¶ködni, három különböz® üzemmódban képes a feladatok kezelésére (a feladatmegoldásokat kísér® üzenetek és a gra kus szemléltetés részletességét tekintve), több nyelven (jelenleg magyarul és angolul) is tud.
Kulcsszavak: Java, gra kus szemléltetés, Hozzárendelési feladat, Magyar módszer
ii
Tartalomjegyzék Feladatkiírás
i
Tartalmi összefoglaló
ii
Bevezetés
1
A Hozzárendelési feladat . . . . . . . . . . . . . . . . . . . . . . . . . . A Hozzárendelési feladat megoldása Magyar módszerrel . . . . . . Meghatározások . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A Magyar módszer leírása . . . . . . . . . . . . . . . . . . . . . . . .
A feladat megoldása
Alkalmazott eszközök . . . . . . . . . . . . . . . . . . . . . . . . . . . . A Java programozási nyelv . . . Java applikáció vs. Java applet . AWT vs. Swing . . . . . . . . Szálak a Java-ban . . . . . . . Java csomagok (package) . . . JAR (Java ARchive) . . . . . . Policytool . . . . . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
Az alapvet® feladatok megvalósítása Az ap csomag . . . . . . . . . . . . . Az APBase osztály . . . . . . . . . .
. . . . . . . . . A MyList2D osztály . . . . . . . . . Az ap csomag m¶ködése . . . . . . . További feladatok megvalósítása . . . A gaps csomag . . . . . . . . . . . . A GAPSStarter osztály . . . . . . . A GAPS osztály . . . . . . . . . . . A GAPSPanel osztály . . . . . . . . A GAPSThread osztály . . . . . . . Az APData osztály
iii
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
1 2 2 2
4
4 4 5 6 6 6 7 7 8 9 9 10 11 11 15 15 15 17 18 18
Az AssignmentMatrixPanel osztály . . . . . . . . . . . . . . . . . . . 21 Az AboutDialog osztály . . . . . . . . . . . . . . . . . . . . . . . . . 23 A Verbosity osztály . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
A table csomag . . . . . . . A MyTableDialog osztály . A MyTableEditor osztály . Az IntegerField osztály . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Extra funkciók megvalósítása . . . . . . . . . . . . A többnyelv¶ség megvalósítása . . . . . . . . . . Ábra és szöveg mentése közvetlenül a programból A gyorsítóbillenty¶k alkalmazása . . . . . . . . . Beépített példa feladatok . . . . . . . . . . . . . . Technikai részletek . . . . . . . . . . . . . . . . . . A szoftver fájlokba szervezése . . . . . . . . . . . A szoftver fordítása . . . . . . . . . . . . . . . . . A HTML-oldal beállításai . . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
24 24 24 25 26 26 26 27 28 29 29 29 30
A szoftver m¶ködés közben, tesztelés
31
Összefoglalás
40
Irodalomjegyzék
42
Nyilatkozat
43
Köszönetnyilvánítás
44
Függelék
45
Els® példa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Második példa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Források a WWW-n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 A Java programozási nyelvvel kapcsolatos oldalak . . . . . . . . . . . 45 Algoritmusok szemléltetésével kapcsolatos oldalak . . . . . . . . . . . 45 Operációkutatással kapcsolatos oldalak . . . . . . . . . . . . . . . . . 45
iv
Bevezetés A Hozzárendelési feladat A Hozzárendelési feladat lényege jól szemléltethet® a következ® példával: adott bizonyos számú dolgozó és ugyanennyi, egymástól független munka; mindegyik dolgozó képes elvégezni bármelyik munkát, továbbá az egyes dolgozók adott munkákra vonatkozó költségei ismertek. A feladat az, hogy minden egyes dolgozóhoz rendeljünk pontosan egy munkát, méghozzá olyan módon, hogy az összes feladat legyen elvégezve, az összköltség minimális értéke mellett. A feladat több módon is kiterjeszthet® illetve sz¶kíthet®, ám mi csak a fentieknek megfelel® modellt tárgyaljuk.1 Jelöljük n-nel a dolgozók számát, cij -vel pedig a j edik munka költségét, amennyiben azt az i-edik dolgozó végzi el (i = 1, . . . , n; j =
1, . . . , n)! Tetsz®leges 1 ≤ i, j ≤ n indexpárra legyen ( xij =
1, ha az i-edik dolgozó végzi el a j -edik munkát, 0 különben.
A probléma a következ® optimumszámítási modellel írható le: n X
xit = 1 (i = 1, . . . , n)
t=1 n X
xtj = 1 (j = 1, . . . , n)
t=1
xij ∈ {0, 1} (i = 1, . . . , n; j = 1, . . . , n) n X n X
(1)
cij xij = z → min
i=1 j=1
A Hozzárendelési feladat az operációkutatás egyik régóta ismert, napjainkra lényegében megoldott problémája. Kezdetben a nyers er® módszerével próbálták meg1
A Hozzárendelési feladatnál általánosabb a tiltott hozzárendelések kezelése és az ún. Szállítási feladat, speciálisabb pl. a Házasságkötési játék néven ismert probléma.
1
közelíteni a feladatot, de ez az út az akkori id®k legfejlettebb számítógépes teljesítménye mellett már 10 × 10-es feladatok esetén is járhatatlannak bizonyult. Kés®bb Kuhn sikerrel dolgozott ki egy valóban használható eljárást, amely König maximum-párosítási algoritmusán és Egerváry redukciós eljárásán alapult[1]. Kuhn az 1955-ben közölt eljárásának a Magyar módszer nevet adta, utalva arra, hogy munkáját a két nagy magyar matematikus ihlette. A továbbiakban Imreh Balázs Operációkutatás c. könyvére[2] építve ismertetjük a módszer lényegét.
A Hozzárendelési feladat megoldása Magyar módszerrel Meghatározások Független 0-rendszer Adott mátrix 0 elemeinek egy rendszerét független 0rendszernek nevezzük, ha a mátrix minden sora és minden oszlopa legfeljebb egy elemét tartalmazza a rendszernek. Valamely mátrixban esetleg több független 0rendszer is kijelölhet®, és maximális számú független 0-rendszerb®l is több lehet.
0∗ A független 0-rendszer elemeit a továbbiakban 0∗ -gal fogjuk jelölni.
Kötött sor (oszlop) Egy mátrix valamely sorát (oszlopát) kötöttnek nevezzük, ha mellette (felette) egy + jel áll.
Szabad elem Egy mátrix valamely elemét szabad elemnek nevezzük, ha nem kötött sem a sora, sem az oszlopa.
Szabad nulla Az a 0, amely szabad elem is egyben.
A Magyar módszer leírása El®készít® rész. A C költségmátrix i-edik sorából rendre vonjuk ki az i-edik sor elemeinek minimumát (i = 1, . . . , n), és az el®álló mátrixot jelölje C ! A C mátrix
j -edik oszlopának elemeib®l rendre vonjuk ki az illet® oszlop elemeinek minimumát (j = 1, . . . , n), és jelölje a kapott mátrixot C (0) ! C (0) -ban oszlopfolytonosan alakítsunk ki független 0-rendszert, azaz oszlopról oszlopra haladva (j = 1, . . . , n) a tekintett oszlopból választható 0-k közül mindig a legkisebb sorindex¶t vegyük fel a független 0-rendszerbe! Ezek után r értéke legyen 0, majd folytassuk az eljárást az Iterációs résszel !
Iterációs rész (r. iteráció) 1. lépés Ha a C (r) -ben kijelölt független 0-rendszer elemeinek száma n, akkor vége 2
az eljárásnak. Ellenkez® esetben kössük le C (r) -ben a 0∗ -okat tartalmazó oszlopokat, és folytassuk az eljárást a 2. lépéssel!
2. lépés Keressünk sorfolytonosan szabad 0-t! Amennyiben nincs szabad 0, akkor az 5. lépéssel folytatjuk, különben meg kell vizsgálnunk az illet® szabad 0 sorát. Ha ez a sor 0∗ -ot tartalmaz, akkor a 3. lépés, ellenkez® esetben a 4. lépés következik.
3. lépés A tekintett szabad 0-t lássuk el vessz®vel (00 ), kössük le a sorát és oldjuk fel a sorában lév® 0∗ oszlopának lekötését! Az eljárás a 2. lépéssel folytatódik. 4. lépés A tekintett szabad 0-t lássuk el vessz®vel (00 ), és ebb®l a 00 -b®l kiindulva képezzünk láncot! A láncképzés a következ®k szerint megy: minden láncbeli 00 -t az oszlopában lev® 0∗ követ a láncban, és minden 0∗ -ra, a sorában található 00 -vel folytatódik a lánc feltéve, hogy vannak ilyen elemek, különben a láncképzés véget ér. Ezek után legyen C (r+1) a jelölések nélküli, aktuális C (r) mátrix, és lássuk el ∗ -gal (r+1)
a cij
(r)
(r)
(r)
(r)
elemet, ha cij ≡ 0∗ és cij nem szerepel a láncban, vagy cij ≡ 00 és cij
eleme volt a láncnak! Végül növeljük meg r értékét 1-gyel, és folytassuk az eljárást az 1. lépéssel!
5. lépés Képezzük a szabad elemek minimumát, majd ezt az értéket vonjuk ki az összes szabad elemb®l és adjuk hozzá a kétszeresen kötött (soruk és oszlopuk is le van kötve) elemekhez! Ezt követ®en, az átalakított mátrixot tekintve aktuális
C (r) mátrixnak, folytassuk az eljárást a 2. lépéssel! Megjegyzések A láncképzés során el®fordulhat, hogy a lánc egyetlen (00 ) elemb®l áll, ilyenkor elfajuló láncról beszélünk. Ennek értelmezése az, hogy ezzel az elemmel közvetlenül b®víthet® az el®z®ekben el®állított független 0-rendszer. Belátható, hogy a szükséges iterációk száma legfeljebb n − 1. A módszer további el®nyös tulajdonsága, hogy kisebb módosításokkal alkalmazható az általánosabb, ún. Szállítási feladat megoldására (ld. pl. [2]-t!).
3
A feladat megoldása Alkalmazott eszközök A kit¶zött feladatot Java programozási nyelven oldottam meg, bár a probléma megoldásához szükséges alapvet® szempontoknak több olyan programozási nyelv is megfelelt volna, amelyet kell® mértékben ismerek (c/opengl, tcl/tk), úgy érzem a Java további el®nyökkel is rendelkezik, melyek motiválták választásom. A Java egy a c++-hoz meglehet®sen hasonló szintaktikájú általános célú, objektum orientált nyelv. E produktivitását tekintve mindenképpen hatékony nyelv segítségével könnyedén kialakítható pl. több nyelv¶ felhasználói felület, a weben keresztül történ® futtatásra alkalmas program (ún. applet). Választásom tehát a Java-ra esett, ebben a nyelvben kívántam tovább mélyíteni tudásom. Ennek megfelel®en magáról a Java programozási nyelvr®l szólok pár szót.
A Java programozási nyelv A Java viszonylag atal nyelv, alig több mint tíz éve, 1991-ben kezdték el tervezni, fejleszteni. 1994-ben a Java fejleszt®i megcélozták az Internet-et. (Ne feledjük, az els® gra kus böngész®, a Mosaic alig egy éve létezett akkor!) A nyelv er®södését jelzi, hogy 1994 ®szére megszületett az els® Java-ban írt Java-fordító. 1995-ben megjelenik a Java kereskedelmi forgalomban, majd 1996-ban kiadják az 1.0-ás Java Development Kit-et. A Java azóta is igen dinamikusan fejl®dik az 1.2-es változat 1998-as jelent®s újratervezéseit követ®en (Java Foundation Classes, Swing, Java2) , jelenleg az 1.4-es f® verziószámnál tart. Éppen ezen dolgozat írása közben jelent meg az 1.5.0Beta1-es változat (45. oldal). A Java platform Java Application Programming Interface-b®l és Java Virtual Machine-ból áll (ld. az 1. ábrát!). A Java api-k az egyéb nyelvekb®l ismert könyvtáraknak felelnek meg, amiket a programozó kényelmesen felhasználhat programjaiban.2 A Java forráskódot el®ször le kell fordítani egy köztes, ún. bájt-kódra, majd 2
Az Java iránt érdekl®d®k ugye tudják, hogy érdemes minél többet olvasni az api dokumentációját? Megtekinthet® pl. itt: http://java.sun.com/j2se/1.4.2/docs/api/.
4
ezt a hordozható bájt-kódot a jvm interpretálja. Ennek a hordozhatóságnak persze ára van, ami legjobban talán a futásid®kben érhet® tetten. Ma már azonban, sokak számára elérhet® az a számítási sebesség, amely mellett inkább a Java által nyújtott el®nyök kerülhetnek el®térbe.
Java nyelvû program Java API-k
Java Virtual Machine Számítógépes operációs rendszer 1. ábra. A Java platform kapcsolódása az operációs rendszerekhez és a Java nyelv¶ progra-
mokhoz. Ez az igen egyszer¶ sematikus ábra azt szemlélteti, hogy miként ékel®dik a Java platform (jvm, Java api) rétege az operációs rendszer és a Java bájt-kód közé.
Java applikáció vs. Java applet Java applikációknak a Java nyelv¶, önállóan m¶köd® alkalmazásokat hívjuk, szemben az applet-tel, amely a Java api dokumentáció meghatározása szerint egy olyan kis program, amely egy másik alkalmazásba van ágyazva.3 Azokat az applet-eket, amelyeket web-oldalakba ágyazott m¶ködésre tervezünk az Applet (vagy újabban inkább a JApplet) osztályból kell származtatnunk. Ezek az osztályok biztosítják a standard felületet az applet és környezete között. A JApplet osztály némileg inkompatíbilis a korábbi Applet osztállyal, ui. a contentPane kell hogy legyen a JApplet minden gyermekének (komponensének) szül®je (tulajdonosa). Azaz a korábbi applet.add(child);
helyett, az applet.getContentPane().add(child);
módszerre van szükség a komponensek applet-re helyezésekor. Ugyanez igaz az elrendezés menedzserekre, a komponensek eldobására stb. Fontos megjegyezni, hogy a web-böngész®kb®l indított Java applet-ek biztonsági okokból igen korlátozott jogosultsággal rendelkeznek rendszerünk felett, ellentétben az önállóan futtatható változataikkal, amelyek az adott operációs rendszernek megfelel® szokásos jogokkal bírnak. Azaz, egy böngész®b®l futtatott Java applet, az alapértelmezett beállításoknak köszönhet®en, nem képes a lokális fájlrendszert olvasni, írni stb. 3
Valójában a határok könnyen elmosódnak, hiszen általában megoldható, hogy egy Java program képes legyen applet-ként és önálló alkalmazásként is m¶ködni (egyetlen forráskódról van szó).
5
A szakdolgozatomban tárgyalt szoftver önálló alkalmazás és applet is egyben. Ehhez a kódnak csak a töredékét kellett felkészítenem erre a kett®s szerepre. Az applet el®nye, hogy hálózaton keresztül is elérhet®vé teszi az alkalmazást, az esetleges verzió frissítésekr®l nem a felhasználónak kell gondoskodnia, biztonságosabb. Az applikáció el®nye, hogy mindig elérhet® rendszerünkön, nem kell megvárni a letöltési id®t.
AWT vs. Swing A Java 1.0 gui (Graphical User Interface Gra kus Felhasználói Felület) könyvtárának eredeti célja az volt, hogy a programozók számára olyan felületet kínáljon, amely jól mutat mindegyik platformon. Az Abstract Window Toolkit (awt) nem érte el célját, köszönhet®en az elkapkodott tervezésnek, kivitelezésnek[3].4 Gyengécske megjelenése és a benne lev® sok megszorítás újabb megoldásokért kiáltott. A helyzet némiképp javult a Java 1.1-ben bevezetett eseménykezeléssel, valamint a JavaBeans-szel. A pontot az -re a Java 2 (jdk 1.2) tette fel, a Java Foundation Classes bevezetésével, amelynek gui részét Swing-nek hívják. A dolgozatomban részletezett szoftver az újabb, jobb Swing gui-t használja, csak a szükséges minimális mértékben tartalmaz awt elemeket.
Szálak a Java-ban Az objektumok lehet®vé teszik, hogy a programot önálló részekre bontsuk. El®fordul azonban, hogy arra is szükségünk van, bizonyos részek önállóan futó alfeladatokat lássanak el ezeket a független alfeladatokat szálaknak nevezzük. A többszálúságnak sok lehetséges felhasználási módja létezik, de általában arra szolgál, hogy egy bizonyos eseményre, eszközre való várakozás ne tartsa fel az egész programot. Gyakorlatban ez azt jelenti, hogy a processzen belül létrehozunk egy szálat, amelyet az eseményhez, eszközhöz rendelünk, és a program többi részét®l függetlenül futtatjuk. A megvalósított szoftverben alkalmazom a szálakat, a felhasználói interakciók jobb kezelése érdekében.
Java csomagok (package) Nagyobb feladatok esetén feltétlenül hasznos a meglév® osztályokat valamilyen módon elkülöníteni, pl. a névütközések elkerülése végett. Erre szolgálnak a csomagok. 4
Aki nem tudott annak idején megküzdeni az awt-vel, az lépjen újra szorítóba és próbáljon egy Swing -et!
6
A Java osztályokat könnyen csomagokba szervezhetjük, ehhez mindössze arra van szükség, hogy az összetartozó osztályokat közös könyvtárba helyezzük (melynek neve lehet®leg utal a csomag rendeltetésére). Eztán az osztályokat tartalmazó fájlok els® sorában feltüntetjük a csomag nevét, amely megegyezik annak a könyvtárnak a nevével, amelyben található. A szakdolgozatomban ismertetend® szoftver alkalmazza a csomagokat, a jobb áttekinthet®ség és az esetleges újra felhasználhatóság érdekében.
JAR (Java ARchive) Az elkészített Java alkalmazások terjesztéséhez, telepítéséhez célszer¶ a Java, jar elnevezés¶ tömörít® és csomagoló eszközét használnunk. A jar fájlok formátuma lényegében kompatíbilis az igen elterjedt zip fájl formátummal. A jar fájlok alkalmazása igen el®nyös a web-es applet-ek esetében. Ahhoz ugyanis, hogy egy applet betölt®djön a böngész®be, minden egyes alkotórészének le kell tölt®dnie a kliens gépére. Ez több fájl esetén több kommunikációt igényel a kliens és a szerver között, nem is beszélve a tömörítéssel elérhet® méretcsökkenésr®l. A dolgozatomban tárgyalt csomagokat és a futásukhoz szükséges állományokat egy tömörített Java archívumba foglaltam, a könnyebb hordozhatóság és az applet letöltési idejének csökkentése érdekében.
Policytool A Java Futtató Környezet (jre) részét képezi a Policytool nev¶ eszköz, amelynek akkor vesszük hasznát, ha szeretnénk egy applet-et több jogosultsággal felruházni, mint az alapértelmezésben szerepl®, igen szigorú biztonsági beállítások. Az eszköz részletes ismertetésére nem áll módomban kitérni, ajánlom a 45. oldalon szerepl® hivatkozást. A szoftver applet-ként való futtatásakor, a Policytool nev¶ standard Java eszközt kell alkalmaznunk ahhoz, hogy a programban jelenlév® minden lehet®séget kiaknázhassunk.5 Természetesen, ha önálló alkalmazásként indítjuk a programot, a teljes fegyvertár rendelkezésünkre áll.
További részletekhez ajánlom a 45. oldalon található- és [3] irodalmakat.
5
A Policytool-t érint® részeket ld. a 26. oldalon!
7
Az alapvet® feladatok megvalósítása Az implementált szoftver alapvet® feladatának nyilvánvalóan a Hozzárendelési feladatok, Magyar módszerrel történ® helyes megoldását kell tekintenünk. A forráskód6 teljes egészében angol nyelv¶ (a megjegyzések, elnevezések is), hiszen gyakorlatilag ez a programozás nyelve napjainkban, továbbá azért is, mert nem tartom helyesnek az ékezet nélküli magyar szavak használatát, legkevésbé a vegyes nyelv¶ kifejezéseket.7 A f® célkit¶zésnek megfelel®en, els® lépésként egy olyan csomagot (package) hoztam létre, amely a fenti feladat számítógépes ábrázolásához szükséges adatszerkezeteket és ezen adatszerkezeteken végzend® m¶veleteket tartalmazza. Mivel a kés®bbiekben erre a csomagra olyan felszínt szerettem volna húzni, amely kell® részletességgel tudja, hogy egy adott eljárás éppen mit csinál, ezért ennek lehet®ségét már most meg kellett valósítanom. Erre a feladatra absztrakt metódusokat használtam, hiszen pontosan még nem ismert, hogy a magasabb szinten lév® felszín hogyan kívánja szemléltetni az aktuális lépést.
GAPS Starter
GAPS
table package
ap package
APBase
GAPS Panel
GAPS Thread
APData
MyList2D
Assignment Matrix Panel
My My TableDialog TableEditor
gaps package
Integer Field
2. ábra. A létrehozott legfontosabb osztályok viszonya. Az ábrán a fejlesztés során létre-
hozott legfontosabb osztályok viszonya látható, továbbá az egyes osztályokat tartalmazó csomagokat is feltüntettem.
Talán ezekb®l is érezhet® már, hogy a problémát lehet®leg sok szintre próbáltam tagolni, a magukban is életképes csomagok, önálló osztályok és metódusok elkülönítésével. Ez a megközelítés általában igen hasznos, hiszen pl. a (tovább)fejlesztést, hibajavítást nagy mértékben megkönnyíti. Jelen probléma esetén azonban, ezt a szemléletet id®nként nehezen kivitelezhet®nek találtam, de az alábbi csomag és az ebben szerepl® metódusok úgy hiszem jól körülhatároltak, funkciójuk elég világosan de niált. 6 7
Helytakarékosság céljából, tömörebben közlöm a forráskód megfelel® részeit. A szárnyaló gondolatok többé nem szárnyalnak. . . Amúgy értjük, hogy mi az elszével ?
8
Az ap csomag Az ap csomag (Assignment Problem package) a Hozzárendelési feladatot leíró osztályokat tartalmazza, ez a szoftver motorja. A következ® három osztályt foglalja magába:
• az APBase osztály a Hozzárendelési feladatot Magyar módszerrel megoldó absztrakt alaposztály, • az APData elnevezés¶ osztály a feladatot leíró adatszerkezeteket és a rajtuk végezhet® m¶veleteket tartalmazza, • a MyList2D a csomag legegyszer¶bb osztálya, a feladatmegoldás láncképzéshez szükséges egysége. A fenti három osztály forráskódja nagyjából 900 sort tesz ki, ezért a teljes feladat megoldásának ez volt a kisebb és valójában könnyebb része.
Az APBase osztály Az APBase (alap)osztályra szöveges- és gra kus felhasználói felületet is építhetünk. Az elképzelésem az volt, hogy a feladatmegoldó algoritmus, futása során üzeneteket küld: az eljárás megfelel® pontjain sendMsgXXX() elnevezés¶ metódushívásokat helyeztem el, ám ezek a metódusok mind absztrakt eljárások. A célom az volt, hogy ez az osztály egyfajta alaposztályként szolgáljon, amelyre építkezve ezeket az absztrakt eljárásokat tartalommal töltjük meg. Az APBase osztály tehát maga is absztrakt, hiszen absztrakt metódusokat tartalmaz. (Java-ban egy adott osztályban lev® egyetlen absztrakt metódus is kikényszeríti azt, hogy maga az osztály is absztrakt legyen.) Absztrakt osztályokból érthet® okokból nem hozható létre objektum, viszont a leszármazási láncban szerepelhetnek. Itt jegyzem meg, hogy Java-ban (az interface-ekt®l eltekintve) a leszármazottaknak, csak egyetlen szül® osztályuk lehet. Ez id®nként igen kényelmetlen, de így a többszörös öröklésnél esetenként felmerül® problémák nem léteznek, és talán nagyobb hangsúlyt kap a gondos tervezés is. Az APBase osztály publikus (public) és védett (protected) adatokat nem tartalmaz, két privát (private) elérés¶ adata egy APData típusú objektumból és a lehetséges maximális költséget meghatározó, véglegesített statikus ( nal static) egész érték¶ adatból áll. Publikus eljárásai a konstruktora és a getAssignment elnevezés¶ metódusa. Ez utóbbi egy egészeket tartalmazó tömb referenciáját adja vissza. Ez a visszaadott tömb azt írja le sorról sorra, hogy egy adott sor hányadik oszlopában található a 0∗ elem, vagyis ez a tömb reprezentálja a független 0-rendszert. A 9
getAssignment() metódus a Magyar módszer egyes lépéseit a bevezet®ben ismertetett leírásnak megfelel®en tartalmazza (11. oldal). Az absztrakt sendMsgXXX() metódusok azért védett elérés¶ek, mert ezeket a metódusokat közvetlenül csak az APBase osztály kívánja meghívni. A Magyar módszert, mint eljárást csak ez az osztály kell, hogy részleteiben ismerje. Privát eljárásai a Magyar módszernek megfelel® lépésekb®l (stepX()) és az azokat még elemibb lépésekre bontó metódusokból állnak (pl. makeChain(), amely a lánckészítésért felel®s).
Az APData osztály Az APData osztály a megoldáshoz szükséges alacsonyabb szint¶ algoritmusokat és adatszerkezeteket tartalmazza a lánc kivételével, amelyet a MyList2D osztály valósít meg. Ez el®bbi osztály csak privát elérés¶ adatokkal dolgozik, ellenben minden metódusa publikus. Az osztály eljárásai között olyan elemi m¶veleteket találunk, mint pl. egy oszlop (sor) lekötése vagy felszabadítása, a nullák megjelölése vagy éppen a jelölések megszüntetése. A fenti osztály egyik privát elérés¶ adata a MyList2D osztály egyik példánya, amelyet kés®bb részletesen bemutatok. Az APData osztály tartalmazza a Hozzárendelési feladat költségmátrixát, annak dimenzióját, számon tartja a 0∗ és 00 elemeket, a kötött sorokat és oszlopokat, a kérdéses szabad nulla sorát és oszlopát, valamint a kérdéses 0∗ oszlopát. Az adatok tárolásához szükséges helyek lefoglalását természetesen dinamikusan oldottam meg, valamint a helyigényüket próbáltam csökkenteni. Kihasználtam ui. a Magyar módszer két speciális tulajdonságát:
• adott sorban legfeljebb egy 00 található (adott oszlopban esetleg több 00 is lehet), • adott sorban és adott oszlopban legfeljebb egy 0∗ található. Ennek megfelel®en, a 00 és 0∗ elemek feljegyzését egy-egy n elem¶, egészeket tartalmazó tömb használatával valósítottam meg. Ez céljainknak megfelel®, hiszen így az adatok visszanyerése elég kényelmes és elég gyors is (21. oldal). Valójában még egy speciális tulajdonságot is kihasználtam: a legtöbb nyelven sorfolytonosan, balról jobbra írunk. Ha esetleg nem ilyen nyelv¶ adatvisszanyerésre lenne szükség, az újabb meggondolásokat igényelne az adattárolás és visszanyerés hatékonyságainak tekintetében. Érdemes egy kicsit részletesebben megnéznünk, hogyan valósítható meg az, hogy az osztály privát adatai referenciákon keresztül se legyenek módosíthatóak. Pl.: public int []getZeroStars() { int []stars = new int[nDim]; for(int i = 0; i < nDim; i++) {
10
}
stars[i] = zeroStars[i]; } return stars;
A fenti kódrészletb®l az látható, hogy lényegében a zeroStars[] privát elérés¶nek szánt adat másolatának referenciáját (stars ) adom vissza a metódust hívó eljárásnak, amely így már nem lesz képes módosítani az eredeti adatot.
A MyList2D osztály A MyList2D osztályt a Magyar módszerben szerepl® láncképzés megvalósítása érdekében alakítottam ki. Azért hoztam létre egy önálló egységet ehhez a feladathoz, hogy egy esetlegesen hatékonyabb adatszerkezetre vagy algoritmusra való áttérés még könnyebben megvalósítható legyen. Az osztály alapjául a standard Java könyvtárban szerepl® Polygon osztály szolgált, de azon lényeges egyszer¶sítéseket hajtottam végre. Az osztálynak három metódusa van, mind publikusan hozzáférhet®. Az egyik listába helyezi a cij mátrix elem (i, j) indexeit, a másik lekérdezi, hogy az (i, j) indexpár megtalálható-e a listában, a harmadik pedig kiüríti a listát. Valójában ez utóbbi m¶velet hatékonysági okokból csak 0-ra állítja a listában található elemek számát, hiszen a Java-ban alapvet®en nincs mód a foglalt memória felszabadítására (mindez automatikusan a háttérben történik).
Az ap csomag m¶ködése Ebben a fejezetben az ap csomag m¶ködésér®l szólok részletesebben, hiszen a f® célkit¶zéseknek megfelel®en ez a szoftver legfontosabb, másrészt egyik legáttekinthet®bb része. package ap; public abstract class APBase { public APBase(int costs[][]) { apData = new APData(costs); } public int [] getAssignment() { int rep = 0; int step = 1; apData.reset(); step0(); while(true) { switch( step ) { case 1: if(step1(rep)) { return apData.getZeroStars(); } step = 2; break; case 2:
11
}
} ...
}
}
step = step2(); break; case 3: step3(); step = 2; break; case 4: step4(); step = 1; rep += 1; break; case 5: step5(); step = 2; break; default: break;
A fenti kódrészlet az APBase osztály konstruktorát és a Magyar módszert megvalósító, algoritmikus keretet mutatja. Az els® sorban azt jeleztem, hogy az osztály az
ap csomagba tartozik. Látható, hogy a konstruktorban egy APData típusú objektumot hozunk létre, amelyet a paraméterként kapott költségmátrixszal inicializálunk. Mivel csak egy konstruktort határoztam meg az osztályhoz, ezért garantált, hogy az osztályból létrejöv® objektumok mind megfelel®en vannak inicializálva természetesen amennyiben az APData osztály helyesen m¶ködik. Az APBase típusú objektum életre hívása után, másik publikus eljárását, a getAssignment() metódust hívhatjuk meg. Ez a költségmátrix alapján, a 2. oldalon ismertetett Magyar módszer segítségével egy optimális hozzárendelést határoz meg. Az eljárás során nyilván kell tartanunk, hogy hányadik iteráció és hányadik lépés következik, el®bbire a rep (repetition ismétlés), utóbbira a step (lépés) egész érték¶ lokális változók szolgálnak. A helyes kezd®értékek beállítása után, az APData típusú apData objektum reset() metódusát hívtam meg, amely lehet®vé teszi az APData osztály újra inicializálását a költségmátrix ismételt megadása nélkül. Ezt követ®en végrehajtjuk a Magyar módszer el®készít® lépését, amelyet a step0() metódussal valósítottam meg. Itt gondoskodtam a sor- és oszlopminimumokkal végzett módosításokról (preconditionCostMatrix()), majd a független 0-rendszer kialakításáról. private void step0() { preconditionCostMatrix(); makeIndependentZeroSystem(); }
A költségmátrix el®készítése után, a getAssingment() metódus egy while12
ciklusban található, switch-elágazás segítségével gondoskodik arról, hogy a módszer lépései a megfelel® sorrendben legyenek végrehajtva. Mivel a step változó értéke kezdetben 1 volt, ennek megfelel®en a case 1 ág kerül el®ször kiértékelésre. Itt a step1() metódust hívjuk meg a rep paraméterrel (erre a paraméterátadásra csak azért volt szükség, hogy a megfelel® itt nem idézett sendMsgXXX() üzenet meg tudja jeleníteni azt az információt, hogy hányadik iterációban ért véget az eljárás). private boolean step1(int rep) { if(apData.getNumberOfZeroStars() == apData.getDimension()) { return true; } tieColumns(); return false; }
A fenti step1() függvény egy boolean típusú értéket ad vissza, amely igaz érték¶, amennyiben optimális hozzárendelést találtunk az adott iterációban (a független 0-rendszer elemszáma megfelel®), hamis érték¶ ellenkez® esetben. Ha ez utóbbi (hamis) ágra kerülünk, akkor a return utasítást megel®zi a megfelel® oszlopok lekötése (tieColumns()), ahogy azt a Magyar módszer ismertetésénél láttuk. A visszaadott értéknek megfelel®en, vagy visszaadjuk az optimális hozzárendelést leíró egész értékeket tartalmazó tömb referenciáját, vagy rátérünk a második lépésre a következ® while-ciklusban (step = 2). A második lépést megvalósító, step2() elnevezés¶ metódus sem sokkal összetettebb a lehetséges visszatérési értékét tekintve, amely három értéket vehet fel. private int step2() { if(!hasFreeZero()) { return 5; } else { int row = apData.getRowOfFreeZero(); if(!apData.hasRowZeroStar(row)) { return 4; } else { apData.setColumnOfZeroStarInRow(row); return 3; } } }
Amennyiben nincs szabad nulla, az eljárást az ötödik lépéssel folytatjuk a következ® ciklusban (return 5;), különben a módszernek megfelel®en megvizsgáljuk az illet® szabad 0 sorát (row). Ha ez a sor nem tartalmaz 0∗ -ot, akkor a negyedik lépés következik (return 4;), ellenkez® esetben a harmadik lépéssel folytatjuk (return 3;), ahol viszont fel kell jegyeznünk, hogy melyik volt a kérdéses 0∗ oszlopa. A harmadik vagy ötödik lépést elvégezve, a második lépésre térünk vissza (step = 2); míg a negyedik lépés után újabb iterációba kezdünk (rep += 1), az els® lépést®l kezd®d®en (step = 1). Most lássuk ezeket kicsit részletesebben! private void step3() { int row = apData.getRowOfFreeZero();
13
int col = apData.getColumnOfFreeZero();
}
apData.setZeroMark(row, col); apData.setRowTied(row); apData.setColumnFree(apData.getColumnOfZeroStar());
Azaz a harmadik lépésben 0 -vel jelöljük meg a talált szabad nullát (setZeroMark(row, col)), majd lekötjük sorát (setRowTied(row)), valamint felszabadítjuk a sor 0∗ -ot tartalmazó oszlopát. (Ezért kellett feljegyeznünk a második lépésben, hogy hányadik oszlopban található a szabad nulla sorában lév® 0∗ .) private void step4() { makeChain(apData.getRowOfFreeZero(), apData.getColumnOfFreeZero()); remakeMatrices(); }
Az eljárásnak megfelel®en a negyedik lépésben megkezdjük a láncképzést a talált szabad nullától elindulva (makeChain()), majd a kapott láncnak megfelel®en, a mátrixban módosítjuk a bejegyzéseket (0, 00 , 0∗ ). private void step5() { reconditionCostMatrix(); }
A Magyar módszer ötödik lépése egyszer¶en a költségmátrix speciális átalakítását írja el®, amelyet ezen a szinten a fentiekkel összhangban nem részleteztem tovább.
14
További feladatok megvalósítása A f® feladat mellett amely a Hozzárendelési feladat, Magyar módszerrel megvalósított számítógépes megoldását jelentette , a következ®ket tekintettem kiegészít® feladatoknak:
• legalább két üzemmód, amely az eljárást kísér® szöveges üzenetek részletességét jellemzi, • gra kus szemléltetés, amely a szöveges üzeneteket kíséri. Valójában amit megvalósítottam, az ennél jóval több, hiszen ha csak azt vesszük gyelembe, hogy három jól elkülöníthet® m¶ködési módot terveztem és valósítottam meg a szoftverben, valamint az esetleges oktatási szempontok érdekében, a [2] jegyzet jelöléseihez h¶ gra kus szemléltetést választottam, már ez is szép eredménynek tekinthet®.8 Hasonló jelleg¶ feladatok számítógépes megjelenítésekor, találkozhatunk az ember számára ebben az esetben nem túl szemléletes, ám jóval egyszer¶bben kivitelezhet® színkódos megoldásokkal. A kezdeti nehézségek után valójában bennem is felmerült, hogy a könnyebb utat választom, azonban ragaszkodtam eredeti elképzelésemhez, amely végül jóval esztétikusabb és a felhasználó számára könnyebben áttekinthet® eredményt adott.
A gaps csomag A gaps csomag (Graphic Assignment Problem Solver Gra kus Hozzárendelési Feladat Megoldó) az ap csomagra épülve, a gra kus felhasználói felület (gui) kialakításáért- és az ismertetett eljárás (2. oldal) gra kus megjelenítéséért felel®s. Kb. 2000 sorával ez a szoftver gra kus motor ja. A részletek ismertetése el®tt, elöljáróban annyit, hogy a GAPSStarter osztály indítja be a gra kus motor t. A GAPS osztály a gra kus felület váza, míg a GAPSPanel keretet biztosít az AssignmentMatrixPanel osztálynak, amely a számunkra legérdekesebb tevékenységet, a szemléltetést végzi.
A GAPSStarter osztály A GAPSStarter (GAPS Indító) osztály a JApplet-b®l származik, azaz alapvet®en applet-ként funkcionál. Azonban tartalmaz egy public static void main(String args[]) 8
A szoftverben található további hasznos lehet®ségekr®l a 26. oldaltól kezdve számolok be.
15
metódust, amely lehet®vé teszi, hogy közvetlenül is életre keltsük. Itt kell el®készíteni programunk arra a kett®s szerepre, hogy applet-ként és önálló alkalmazásként is elindíthassuk. Valójában ez egy igen egyszer¶ (de nagyszer¶) dolog. A legfontosabb sorok ehhez a következ®k: JFrame f = new JFrame(); JApplet applet = new JApplet(); applet.init(); f.setContentPane(applet.getContentPane()); f.setVisible(true); applet.start();
Itt f egy JFrame típusú objektum, amelynek tartalom paneljét (ContentPane), az applet-ként elindított alkalmazás, tartalom paneljére állítjuk be. Innent®l kezdve lényegében ugyanúgy m¶ködnek. Egyetlen boolean típusú változó használatával azt is feljegyezhetjük, hogy miként indították az alkalmazást, vagyis az appletill. applikáció-speci kus kód is elkülöníthet®.9 A tárgyalt osztály vizuálisan lényegében csak egy JButton-t tartalmaz. Ezt aktivizálva a GAPS osztály egyik példányát hívjuk életre (ld. a 3. ábrát!). Az osztály alapötlete onnan származik, hogy a GAPS osztály nagyobb szabadságot kaphasson azáltal, hogy böngész®be ágyazott futtatása esetén ne a web-oldal részeként, hanem önálló ablakban jelenjen meg. Gyakorlatilag ez az ablak tetsz®leges átméretezésére ad lehet®séget, amely az igényesebb felhasználó természetes kívánságát elégíti ki.
Web-oldalba ágyazott applet Beágyazott indító gomb Önálló ablakban futó applet 3. ábra. Az ábra bal oldalán látható, applet-et indító (web-oldalba ágyazott) indító gomb
és az önálló ablakban futó applet kombinációja el®nyösebbnek t¶nik, mint a jobb oldalon látható megoldás, amely a tisztán web-oldalba ágyazott applet lehet®ségét illusztrálja.
Programomban a jobbnak t¶n®, önálló ablakban futó megoldást választottam, továbbá a kényelmesebb, gyorsabb használhatóság érdekében, az ablak a képerny® középre igazítva jelenik meg. A legtöbb ablakkezel® menedzser ui. automatikusan a képerny® bal fels® sarkába vagy véletlenszer¶ helyre igazítja a felbukkanó új ablakokat. 9
Tipp: a main() metódus csak akkor hajtódik végre, ha alkalmazásként hívták meg a programot.
16
A GAPS osztály A GAPS osztály szintén a JApplet osztályt b®víti (extends), azaz bel®le származik. Ezt az osztályt tisztán applet-ként való futtatásra terveztem, és a fentebb ismertetett okok miatt alkottam meg számára a GAPSStarter osztályt. A GAPS osztály megvalósítja (implements) az ActionListener interfészt, amelyre a menü-események kezelése miatt volt szükségem. Az osztály konstruktorában egy képerny® közepére centrált keretet hozok létre. Majd a konstruktorból meghívom az applet start() metódusát, amely közvetve az init() metódus végrehajtását kezdi meg. Az init() metódusban létrehozom és elhelyezem a menüt és egy alapértelmezett konstruktorral hívott GAPSPanel objektumot. Az applet-ekben meglév®, felülde niálható stop() metóduson keresztül gyelmeztetem a GAPSPanel-t, hogy befejezheti m¶ködését, hiszen a web-oldalt elhagyták vagy a programból kilépni szándékozott a felhasználó. Az osztály által kínált menüb®l kiválasztva lehet elindítani az újabb feladatok bevitelét, azok újra futtatását, a beállítások módosítását, a szerz®i információk megjelenítését. A menü további beállítási lehet®ségeir®l csak a 26. oldaltól kezdve írok részletesebben. Ennek oka az, hogy bár nagyon hasznosnak találom mindet az eredeti f® célkit¶zést®l kicsit távolabb állnak. A kiválóan dokumentált és jól felépített Java könyvtárra jellemz®, hogy egy olyan dialógus ablak megvalósítása, amely arra kérdez rá, valóban ki akarunk-e lépni a programból, pár sorból áll csupán, elrontani sem lehet. Lényegében ezt a megoldást alkalmaztam erre a célra: private boolean isExitConfirmed() { Object []options = {"Yes", "No"}; int n = JOptionPane.showOptionDialog(this, "Are you sure?", "About exit", JOptionPane.YES_NO_OPTION, JOptionPane.QUESTION_MESSAGE, null, options, options[0]); if(n == JOptionPane.YES_OPTION) { return true; } return false; }
Amennyiben igaz értéket kapunk vissza kiadom a f.dispose();
utasítást, amely megszünteti a vizuális komponenseket tartalmazó, JFrame típusú objektumot.10 10
A keret (frame) képerny®re centrálását a következ® módon oldottam meg:
Pontosabban nem megszüntetésr®l van szó, hanem arról, hogy elenged minden általa és gyermekei által lekötött natív er®forrást.
17
private void setFrameCentered(JFrame frame, int width, int height) { GraphicsEnvironment ge = GraphicsEnvironment.getLocalGraphicsEnvironment(); Rectangle r = ge.getMaximumWindowBounds(); if(width > r.width) { width = r.width; } if(height > r.height) { height = r.height; } Point p = ge.getCenterPoint(); frame.setBounds(p.x - width/2, p.y - height/2, width, height); }
A GAPSPanel osztály A GAPSPanel-t a JPanel osztályból hoztam létre, azzal a céllal, hogy a GAPSThread vizuális komponenseit tárolja. Nevezetesen egy AssignmentMatrixPanel típusú panelt középen és egy JButton típusú nyomógombot alatta. A két komponenst a GAPSThread osztály egyik példánya helyezi el rajta (ld. lentebb), amelyet a megfelel® konstruktorból indítunk. public GAPSPanel(int costs[][], Locale locale, Verbosity verbosity) { gapsThread = new GAPSThread(this, costs, locale, verbosity); }
Publikus removeNotify() metódusában gyelmeztetem az esetlegesen futó GAPSThread szálat, hogy fejezze be m¶ködését, hiszen a komponens megsz¶nik, további lépéseket már nem kell végrehajtania a Magyar módszerb®l.
A GAPSThread osztály Végül elérkeztünk az egyik legfontosabb osztályhoz, ez az osztály tölti fel tartalommal az APBase absztrakt metódusait! A GAPSThread ennek megfelel®en az APBase osztályból származik, ezért be kell hívnia az ap csomagot. A GAPSThread osztály konstruktorában megkapja
• szül®je referenciáját, • a költségmátrixot, amellyel dolgoznia kell, • az aktuális nyelvre vonatkozó beállításokat, • a kívánt m¶ködési módot, amely az üzenetek kiírásának részletességét határozza meg. A konstruktorban, az átadott paraméterekkel inicializálom az osztályt, majd létrehozom a fentebb említett nyomógombot, panelt is. A gomb (continueButton) célja, hogy használatával lehet®vé váljon a felhasználó és a program interakciója a szemléltetett eljárás végrehajtása során. A következ® módon lehetséges ezt elegánsan megoldani: 18
continueButton.addActionListener( new ActionListener() { public void actionPerformed(ActionEvent e) { doContinue(); } });
Ez a megoldás jó példa a Java eseménykezelésére, valamint a névtelen objektumok használatára. A Java-t kevésbé ismer®knek szokatlannak t¶nhet a fenti kódrészlet, ezért részletesebben elmagyarázom, mir®l is van szó. A continueButton egy JButton típusú objektum, amelynek meghívjuk az (AbstractButton-tól származó) addActionListener() metódusát. Ez a metódus nem túl meglep® egy ActionListener interfésszel bíró objektumot vár paraméterként. Most jön a trükk! Ott helyben létrehozunk egy névtelen, ActionListener típusú interfészt megvalósító objektumot. Mivel az interfész egy olyan osztály, amelynek minden metódusa absztrakt, ezért ahhoz hogy bel®le objektumot hozhassunk létre, meg kell valósítanunk minden egyes metódusát. A fenti interfésznek csak egyetlen metódusa van, a void actionPerformed(ActionEvent e)
ezért az a három sor középen. (Az actionPerformed() metódus egy ActionEvent típusú objektumot vár paraméterként, amit most nem használunk fel.) Mit kaptunk végül? Egy olyan nyomógombot, amelyet bármikor aktivizálva (lenyomva) végrehajtódik a doContinue() metódus. Elegáns megoldás, nem?11 Még egy fontos dolgot kell áttekintenünk ahhoz, hogy a további magyarázatokat folytathassam. Ez pedig a szálak kezelése, melyr®l egy rövid bevezetés a 6. oldalon olvasható. Java-ban alapvet®en kétféleképpen hozhatunk létre szálakat programjainkban. Az egyik megoldás szerint: class ComputingThread extends Thread { ... public void run() { // computing... } ... }
A szál bef¶zése programunk szövetébe a következ® módon történik: ComputingThread t = new ComputingThread(...); t.start(); 11
Bonyolultabb (értsd: több soros) eseménykezelés esetén, nem célszer¶ ezt a megoldást választani, a kód áttekinthetetlensége miatt. Ilyenkor pl. a (fenti esetben a nyomógombot) deklaráló osztálynak kell megvalósítania az interfész metódusait.
19
Ennek a megoldásnak az a szépséghibája, hogy Java-ban az interfészek kivételével csak egyszeres ágú öröklés lehetséges. De ahogy a Galaxis Útikalauz Stopposoknak mondja: Ne ess pánikba! Valóban, van megoldás arra az esetre is, ha szeretnénk valamely másik osztálynak fenntartani a szül®i el®jogokat. Íme: class ComputationRunner implements Runnable { ... public void run() { // computing... } ... }
A szál elindítása ebben az esetben egy kicsit másként néz ki: ComputationRunner r = new ComputationRunner(...); new Thread(r).start();
Mint korábban említettem, a GAPSThread osztály az APBase absztrakt alaposztályból származik, ezért a második megoldási módot valósítottam meg.12 Az osztály konstruktorában, a szál létrehozása el®tt, meg kell gy®z®dnünk arról, hogy az AssignmentMatrixPanel típusú objektum készen áll a kimen® üzenetek fogadására. Pontosabban arról van szó, hogy ha létrehoztunk egy gui objektumot, azt csak az esetleges szálak gyelembevételével szabad módosítani (thread-safety). Vagyis hibát követhetünk el, ha egy másik szálról akarjuk azt a gra kus objektumot módosítani, amely még az esemény-közvetít® szálon (event-dispatching thread) várakozik frissítésre. Pl. hibás megközelítés esetén, nem garantált, hogy a panel gra kus háttere készen áll már, amikor az üzeneteket küldeni szeretnénk rá kirajzolásra.13 B®vebb leírásokra pl. a 45. oldalon található Java leckék között lelünk. Ezeknek megfelel®en, én lényegében így oldottam meg a fenti problémákat: public GAPSThread(GAPSPanel owner, int costs[][], Locale locale, Verbosity verbosity) { super(costs); ... amp = new AssignmentMatrixPanel(costs); owner.add(amp, BorderLayout.CENTER); continueButton = new JButton(" "); continueButton.addActionListener(...); owner.add(continueButton, BorderLayout.SOUTH); owner.setVisible(true); // Do not add GUI code after this line! myThread = new Thread(this); myThread.start();
} 12
Az osztály elnevezése ezek ellenére mégis GAPSThread, és nem GAPSRunner, hiszen végeredményben mégis csak szálról van szó. 13 Vigyázat! Amint meghívjuk a szál start() metódusát, több független szálon kell gondolkodnunk.
20
Az osztály legterjedelmesebb részét a megvalósítandó metódusok teszik ki. Ezekben a metódusokban a következ® sémát követtem: protected void sendMsgXXX(...) { if(currentVerbosity.getLevel() == Verbosity.HIGHEST_LEVEL) { ... } else if(currentVerbosity.getLevel() == Verbosity.MEDIUM_LEVEL) { ... } else { ... } }
Az egyes if-else-ágakban az aktuális üzenetnek, nyelvnek és részletességnek megfelel®, gra kus szemléltetés- ill. szöveges magyarázat kiadására vonatkozó utasítások találhatóak. Az elágaztatások helyett, esetleg létrehozhattam volna több különböz® osztályt az egyes szinteknek megfelel®en, de akkor azt a lehet®séget veszítettük volna el, hogy futás közben módosítsuk a kezdetben beállított üzemmódot. A futás közbeni üzemmód váltásnak pedig van értelme, hiszen könnyen elképzelhet®, hogy a felhasználó az adott feladat megoldásának különböz® részeit különböz® részletességgel szeretné megtekinteni. Az osztálynak mivel vállalta, hogy megvalósítja a Runnable interfészt meg kell határoznia a run() metódust. Ez ilyen egyszer¶en fest ezek után: public void run() { super.getAssignment(); }
Akárcsak eddig, a super itt is a szül® osztályt szimbolizálja. Vagyis meghívtam az ®s osztály getAssignment() metódusát, amely során rendre végrehajtódnak az eljárásba ékelt sendMsgXXX() metódusok. Ezek pedig itt a GAPSThread osztályban, az aktuális futási módnak megfelel® részletességgel generálják üzeneteiket, amelyeket az AssignmentMatrixPanel fogad.
Az AssignmentMatrixPanel osztály Az AssignmentMatrixPanel osztályban valósítottam meg azokat a m¶veleteket, amelyek a szakdolgozatban kit¶zött szemléltetéshez szükségesek. Az osztály két legfontosabb vizuális komponense a görgethet® tartókba14 helyezett JTextAreaill. JPanel típusú objektumok. El®bbiben a megoldást kísér®, szöveges üzeneteket helyezem el, utóbbiban a gra kus ábrázolást végzem. Megjegyzem, hogy a konstruktorban átvett, egészeket tartalmazó költségmátrixot átalakítom karakterláncokat (String) tartalmazó cellákká. Ez azért t¶nt számomra el®nyösebbnek, mert így kényelmesen végezhet®k a cellák tartalmán olyan átalakítások, mint pl. egy 0 megjelölése 0 -vel, vagy éppen egy 0∗ átalakítása 0-vá. 14
Egész pontosan a JScrollPane-r®l van szó.
21
Az infoArea elnevezés¶, JTextArea típusú, szöveges üzeneteket tartalmazó komponens kezelése meglehet®sen egyszer¶. A kapott karakterláncot egyszer¶en hozzáf¶zöm a korábbi szöveghez, majd gondoskodom a szöveg automatikus görgetésér®l, a kurzor (caret) szöveg végére helyezésével. Az alapelv itt látható: public void printMsg(String s) { infoArea.append(s); infoArea.setCaretPosition(infoArea.getDocument().getLength()); }
A 10. oldalon említett 0∗ -ok visszanyerését az alább látható módon oldottam meg. A független 0-rendszert leíró mátrixot soronként írom ki a komponensre, egyessel jelezve azt, ha az adott nulla eleme a független 0-rendszernek, nullával, ha nem. public void printMsg(int []zeroStars) { int x; for(int i = 0; i < n; i++) { x = zeroStars[i]; for(int j = 0; j < n; j++) { if(x == j) { infoArea.append("1 "); } else { infoArea.append("0 "); } } infoArea.append("\n"); } infoArea.append("\n"); infoArea.setCaretPosition(infoArea.getDocument().getLength()); }
A gra kus megjelenítésért felel®s komponens el®készítése valamivel több munkát igényel, de megéri a fáradságot. Az osztály konstruktorában található a következ®, itt csak vázlatosan lejegyzett kódrészlet: drawingPanel = new JPanel() { protected void paintComponent(Graphics g) { super.paintComponent(g); Graphics2D g2D = (Graphics2D)g; if(firstTime) { bufferedImage = (BufferedImage)createImage(size.width, size.height); graphics2D = bufferedImage.createGraphics(); ... firstTime = false; }
};
}
g2D.drawImage(bi, 0, 0, this);
A drawingPanel komponens paintComponent() metódusát ott helyben felül írtam. Természetesen a rstTime boolean típusú változó kezdetben igaz logikai értékkel bír. A Dimension típusú, size elnevezés¶ paraméter átadásakor, a változónak a gra ka kívánt méretét kell tartalmaznia. 22
Mire jó ez az egész? Amit ezzel a módszerrel nyerünk az a puerelt graphics2D objektum, amelyre ezután bármikor rajzolhatunk, és újrafestésnél a puer tartalma villódzás nélkül megjelenik a képerny®n.15 Lássunk egy egyszer¶ példát, amely egy vonallal áthúzza a kívánt sort! (Ez a m¶velet a Magyar módszer ötödik lépésében szerepel, segítségével könnyebben számba vehet®k a szabad-, az egyszeresen- ill. kétszeresen lekötött elemek.) public void drawLineThroughRow(int row) { int y = topMargin + FONT_SIZE + row*(cellHeight + cellVerticalSpace) + cellHeight/2 - 1; int left = leftMargin; int right = left + n*cellWidth + (n-1)*cellHSpace - 1; graphics2D.drawLine(left, y, right, y); drawingPanel.repaint(left, y, right-left, y+1);
}
Megjegyzés Ez az osztály valószín¶leg jól hasznosítható lenne pl. a Szállítási feladat szemléltetéséhez is.
Az AboutDialog osztály Az osztály egy kis dialógus ablakot kínál fel nyugtázásra, amelyben a programról és a szerz®r®l közöl pár soros információt. A többi épít®elemt®l való függetlensége indokolja önállóságát. Kis módosítással könnyen általánosabbá lehetne tenni, és akkor egy igazán kényelmesen újra hasznosítható komponenst nyernénk.
A Verbosity osztály Ez az osztály a gaps csomag legegyszer¶bb darabja, feladata mindössze annyi, hogy segítségével elrejtsük a b®beszéd¶ség (verbosity) szintjeit, tároljuk annak beállítható értékeit. Akárcsak az el®bb, az osztály haszna az implementáció elrejtésben és az újra hasznosíthatóságban keresend®. Jelenleg három jól elkülöníthet® szintet határoztam meg, a Magyar módszerhez igazodva. A három szintnek megfelel®en, a következ® információk kerülnek kiírásra:
• a kezdeti költségmátrix, a talált optimális hozzárendelés, az iterációk száma, a teljes költség (indítás után nem igényel felhasználói interakciót)
• a fentiek kiegészítve a mátrix el®készítésével, az átalakítások során kapott mátrixokkal (az egyes lépések megkezdésekor kíván felhasználói interakciót) 15
Ismer®sek a régi, villódzó gra kájú awt-s Java animációk?
23
• a fentieken túl az aktuálisan vizsgált sor, oszlop, elem és azok állapota (kötött, szabad, jelölt stb.)
A table csomag Ez a csomag a gra kus felhasználói felületen keresztül történ® adatbevitelért felel®s, segítségével egészeket tartalmazó mátrixokat lehet bekérni a felhasználótól. Az IntegerField osztály felel®s azért, hogy csak egész értékekkel lehessen feltölteni a mátrixokat. A MyTableEditor a mez®k mátrixba rendezéséért felel®s, míg a MyTableDialog az egész érték¶ mez®ket tartalmazó mátrix megjelenítéséért felel. Az érdekl®d® olvasó sok ötletet meríthet pl. a 45. oldalon felsorolt, idevágó leckékb®l.
A MyTableDialog osztály Ez az osztály a JDialog-ból származik, viszont az általam megvalósított getValues() metódusán keresztül egészeket tartalmazó mátrixok referenciájának visszaadására is képes. Konstruktorát a következ®re terveztem: public MyTableDialog(
}
...
Frame owner, String caption, int dimensionOfMatrix, int minimumValue, int maximumValue, int defaultValue, String keyI18N, Locale currentLocale
) {
Ilyen módon lehet®ség nyílik korlátok közé szorítani-, alapértelmezett értékkel ellátni a bekérend® mátrix elemeit, valamint a nyelvi beállításoknak megfelel®en üzenetet kiírni arra vonatkozólag, hogy milyen bemenetet is várunk. Ez az osztály azonban csak egyfajta keretként m¶ködik, a piszkos munkát a következ® osztályok végzik.
A MyTableEditor osztály A MyTableEditor osztály már csak az itt látható adatokat kapja meg konstruktorában, amely elegend® is m¶ködéséhez: public MyTableEditor(
}
...
int int int int
dimensionOfMatrix, minimumValue, maximumValue, defaultValue
24
) {
Ez az osztály beágyazva egy AbstractTableModel osztályt tartalmaz, amely Integer típusú cellák kezelésére van felkészítve. A táblázat fejlécében feltüntetem az oszlopok sorszámát, segítend® az eligazodást nagyobb mátrixokban.
Az IntegerField osztály Ez az osztály a JTextField-b®l származik, itt történik az egyes cellák kezelése. Néhány egyszer¶ módszerrel elérhet®, hogy ne fogadjuk el a hibásan formázott karakterláncokat, valamint azokat az egészeket, amelyek a beállított értéktartományon kívül esnek. Ezekben az esetekben jelzem, hogy szabálytalanság történt, valamint beállítom az alapértelmezett értéket az adott cellára.
Megjegyzés Az érték szerkesztését nyugtázással kell befejezni (pl. az Enter billenty¶ leütésével, vagy egy másik cellára váltással).
25
Extra funkciók megvalósítása A többnyelv¶ség megvalósítása E funkció megvalósítását az a tény motiválta, hogy ma már nem lehet eladni igényesebb szoftvereket egyetlen nyelv alkalmazásával. A Java pedig könnyedén lehet®vé teszi több nyelv rugalmas használatát is. A program többnyelv¶ségének megteremtését a GAPS osztály következ® beállításaival értem el: private Locale []locales = {new Locale("en", "US"), new Locale("hu", "HU")}; private Locale currentLocale; private ResourceBundle messagesBundle;
Majd az alábbi metódust használtam a nyelv megváltoztatására: private void setMyLocale(Locale locale) { currentLocale = locale; messagesBundle = ResourceBundle.getBundle("APMessagesBundle", locale); }
Az APMessagesBundle.properties ill. APMessagesBundle_xx_XX.properties nev¶, szöveges fájlok egyenl®ségjellel elválasztva kulcsokat és értékeket tartalmaznak. (Pl.: Step0=El®készít® lépés.) A kulcsnak megfelel® érték kiválasztása pedig például így történhet: String internationalizedString = messagesBundle.getString("Step0");
A Java api-ban rendelkezésre álló osztályok segítségével a programozó ennél többre is képes lehet. Az éles szem¶ felhasználó meg gyelheti ezt, a számokat is magukba foglaló, különböz® nyelv¶ kiírások összevetésekor. Pl.: Tying the 1. column és A(z) 1. oszlop lekötése.16
Ábra és szöveg mentése közvetlenül a programból E funkció kialakításához az AssignmentMatrixPanel a MouseListener és KeyListener interfészeket valósította meg. Amennyiben a fenti panel két ábrázolást végz® komponense birtokolja a fókuszt, és leütjük a megfelel® billenty¶t (s: save), vagy kattintunk az egér adott gombjával (második vagy harmadik), a panelek tartalma mentésre kerül. Az eljárást illusztráló ábrákat png (Portable Network Graphics) formátumban írom fájlba, míg a kísér® leírásokat egy egyszer¶ szöveges fájlként. 16
Lássuk például az egérrel történ® mentésre vonatkozó kódrészletet!
Lehet®ség lenne a nével®k automatikusan helyes kiválasztására, de ezt a többletmunkát ezen a szinten nem vállaltam.
26
public void mouseClicked(MouseEvent me) { int btn = me.getButton(); if(btn == MouseEvent.BUTTON3 || btn == MouseEvent.BUTTON2) { saveContent(); } }
Mivel csak a megfelel® komponensek hallgatóznak egér- és billenty¶ esemény után, ezért nem vizsgálom meg az esemény forrását. Azt viszont le kell kérdeznünk, hogy az egér melyik gombja (vagy melyik billenty¶) váltotta ki az eseményt. A megfelel® esetekben, a saveContent() privát metódust hívom meg, amely lényegét tekintve a következ®: private void saveContent() { File filePIC = new File("matrix.png"); try { ImageIO.write(bi, "png", filePIC); } catch(IOException ioe) { ... }
}
File fileTXT = new File("solution.txt"); try { FileOutputStream fos = new FileOutputStream(fileTXT); fos.write(infoArea.getText().getBytes()); fos.close(); } catch(IOException ioe) { ... }
Látható, hogy a gra kára alkalmazott technika milyen hasznos, gyakorlatilag egyetlen sorral képesek vagyunk fájlba írni a kívánt tartalmat. Hasonló megoldást kínál a JTextArea is, hiszen a szöveges fájl mentése sem t¶nik bonyolultnak. Dolgozatom 31. oldalától kezdve konkrét példákkal igyekszem illusztrálni ezt a lehet®séget és az el®z® módszert.
Megjegyzések A tárgyalt funkció bizonyos el®készületeket igényel, ha a szoftvert applet-ként futtatjuk. A Policytool nev¶ standard Java eszközre lehet szükségünk, amellyel feljogosíthatjuk a programot fájlok írására stb. A 45. oldalon található címeken járhatunk a részletek után. Az ismertetett m¶ködési módot els®sorban oktatási célból gondolom hasznosnak, mert így tetsz®leges feladat akár igen részletes megoldásának ismertetéséhez, nem kell bajlódni az illusztráló ábrák elkészítésével.
A gyorsítóbillenty¶k alkalmazása Ezen lehet®ség legnagyobb nyertesei azok a mozgáskorlátozott emberek, akik képtelenek a számítógépes egér használatára. Azonban mások számára is hasznos lehet ez a funkció. Tapasztalatom szerint, a program teljes érték¶en használható 27
gyorsítóbillenty¶k (ún. mnemonic: alt + a menü elem els® karaktere)-, tab- és navigációs billenty¶k segítségével. Megjegyzem, hogy a mentési lehet®ség az s billenty¶ leütésével érhet® el. A nyelvvel dinamikusan változó gyorsítóbillenty¶k beállítása, a fentebb említettek ismeretében, meglehet®sen egyszer¶: String str = menuBundle.getString("XXX"); xxxMenuItem.setText(str); xxxMenuItem.setMnemonic(str.charAt(0));
Beépített példa feladatok A szoftverbe négy beépített példát helyeztem el, amelyek hasznát leginkább a tesztelések során láttam. Kezdetben ui. még nem volt adatbevitelre lehet®ség, de ezen példák segítségével már akkor lehetett tesztelni az alapvet® eljárásokat. Kés®bb pedig, a gra kus felhasználói felület hozzávet®leges elkészülte után, nem kellett minduntalan újabb és újabb feladatokat betáplálni ahhoz, hogy a kisebb-nagyobb esztétikai, technikai hibákat kijavíthassam. Ha kés®bb feleslegesnek bizonyulna ez a funkció, nem okoz semmiféle problémát a kódból való eltávolítása. A példákat, az itt látható vázlatnak megfelel®en, a JMenuItem (AbstractButtontól örökölt) doClick() metódusának hívásával indítottam el automatikusan: private void startExample(int i) { switch(i) { case ...: costMatrix = new int[][] { {..., ..., ...}, ... {..., ..., ...} }; break; ... } againMenuItem.doClick(); }
28
Technikai részletek Kezdetben egy gnu make le-t használtam a gyakran kiadott parancsok automatizálására, azonban ez Java-ra nem bizonyult olyan hatékonynak, mint pl. a c nyelvre, ezért egy saját shell szkripttel cseréltem fel. Ma már pedig tudom, hogy legközelebb az Ant elnevezés¶ eszközt fogom használatba venni.17
A szoftver fájlokba szervezése A fejlesztés során, ahogy n®tt a szoftver mérete, hamar eljött az az id®, hogy elkezdtem a rendszert struktúrálni. Az alábbi könyvtárszerkezetet hoztam létre, a fejlesztés f®könyvtárában: ./bak ./classes ./doc ./html ./messages ./src
A bak könyvtár a módosítás el®tti, tömörített formátumú mentéseket tartalmazza (BAcK-up). Tömörítéshez a zip programot használtam, mert tapasztalatom szerint ez található meg a legtöbb rendszeren, így a mentés is hordozhatóbb. A clas-
ses könyvtár kezdetben a manifest.mf elnevezés¶ fájlt tartalmazta, amely a jar fájl m¶ködéséhez szükséges, majd ebbe a könyvtárba kerültek a lefordított osztályok (class-ok). A doc könyvtár a programozó számára tartalmaz hasznos információkat: mi a következ® fontos feladat, tapasztalt hibák stb. A html könyvtárban az applet m¶ködéséhez szükséges oldalakat és a szoftverhez tartozó leírásokat helyeztem el, html formátumban. A programban olvasható, idegen- és magyar nyelv¶ üzeneteket
tartalmazó fájlokat messages bejegyzés alatt találjuk. A src könyvtár a forráskódot rejti az ap, gaps és table alkönyvtárak alatt.
A szoftver fordítása A programot a fejlesztés f®könyvtárából az alábbi módon fordíthatjuk le, majd csomagolhatjuk össze egy jar fájlba: javac -deprecation -sourcepath src src/*/*.java -d classes cp messages/*.properties classes/ cd classes jar cmf MANIFEST.MF gaps.jar */*.class *.properties 17
Kedves olvasó, te ne járd végig feleslegesen a fenti utat!
29
A HTML-oldal beállításai A html-oldal testébe, minimálisan az alábbiakat kell írnunk ahhoz, hogy web-es felületen keresztül is m¶ködtethessük a programot:
