Academiejaar 2005 – 2006
Departement Industriële Wetenschappen BME - CTL Schoonmeersstraat 52 - 9000 Gent
Diagrameditor met layoutoptimalisatie
Eindwerk voorgedragen tot het behalen van het diploma van INDUSTRIEEL INGENIEUR INFORMATICA
Steven DE GROOTE Promotor:
Wijnand SCHEPENS
Diagrameditor met layoutoptimalisatie
Voorwoord
Vooreerst wil ik Dhr. Wijnand Schepens bedanken voor het voorstel van dit onderwerp en de begeleiding tijdens de uitwerking ervan. Gedurende de hele loop van het project was er voldoende sturing en vrijheid om tot een goed eindresultaat te komen. Zijn positieve ingesteldheid en persoonlijke interesse heeft tot een beter resultaat geleid dan wat anders mogelijk was. Daarnaast moet ik ook mijn familie bedanken voor de steun en hulp die ze me gaven. Hoewel niet hun vakgebied waren ze er altijd om te luisteren naar mijn frustraties en vorderingen. Hun oprechte mening bij tests of uitleg waren een grote hulp. Verder zijn er nog talrijke medestudenten en vrienden die een voorlopige versie van het programma getest hebben en daarmee waardevolle informatie hebben gegeven over de pijnpunten in het project.
Steven De Groote Gent, mei 2006
2
Steven De Groote
Diagrameditor met layoutoptimalisatie
Abstract Een diagram bestaat uit elementen en relaties. Deze thesis bespreekt de ontwikkeling van een framework en een front end applicatie om dergelijk diagram op te slaan en te bewerken. Beide onderdelen worden geïmplementeerd in Java. In het framework wordt een diagram hiërarchisch opgeslagen in twee gescheiden boomstructuren. Een XML pluginsysteem zorgt hierin voor dynamische uitbreidingsmogelijkheden. De front end laat doorgedreven visueel ontwerp van een diagram toe. Het biedt een visuele boomstructuur en een property inspector voor elk diagramelement. De lay-out van een diagram kan bovendien geoptimaliseerd worden met simulated annealing. Het geïmplementeerde algoritme wisselt knoopposities tot een visueel aantrekkelijk diagram wordt bekomen. Overlappende knopen worden vermeden terwijl de totale taklengte wordt geminimaliseerd. De applicatie kan bovendien de iteraties van het algoritme op het scherm tonen en de gebruiker toelaten tussen te komen tijdens de werking ervan.
A diagram consists of elements and relations. This thesis reviews on the development of a framework and a front end application to store and provide editing of such a diagram. Both modules have been developed in Java. The framework is built so that it stores a diagram in a hierarchical form, more precisely in two tree structures. An XML based plugin system provides for dynamic extensibility. The front end application allows for advanced visual design of a diagram. It can display each element in a visual tree structure and makes use of a property inspector to display each element. Moreover, the layout of a diagram can be optimised by simulated annealing. The implemented algorithm switches nodes from their position in order to generate a better formed diagram. Overlapping elements are avoided while the aim is to reduce the total length of the edges in the diagram to a minimum. The front end application can, during the running of the optimisation, visualise each step and allow the user to intervene.
3
Steven De Groote
Diagrameditor met layoutoptimalisatie
Inhoudsopgave Voorwoord ....................................................................................................................... 2 Abstract............................................................................................................................ 3 Inhoudsopgave ................................................................................................................. 4 Figurenlijst ....................................................................................................................... 7 Inleiding ........................................................................................................................... 8 1
Project ...................................................................................................................... 9 1.1
Situering................................................................................................................................... 9
1.2
Doelstellingen .......................................................................................................................... 9
1.3 Technologie ........................................................................................................................... 10 1.3.1 Gebruikersplatform ........................................................................................................... 10 1.3.2 Ontwikkelplatform............................................................................................................ 10
2
Analyse .................................................................................................................. 12 2.1 Diagram als data .................................................................................................................... 12 2.1.1 Structurele eigenschappen................................................................................................. 12 2.1.2 Lay-out gebonden eigenschappen ..................................................................................... 13
3
2.2
Grafisch bewerken ................................................................................................................. 14
2.3
Klassenstructuur .................................................................................................................... 14
Framework ............................................................................................................. 16 3.1 Boomstructuur ....................................................................................................................... 16 3.1.1 Diagram als boom ............................................................................................................. 16 3.1.2 Implementatie ................................................................................................................... 17 3.2 Structuur ................................................................................................................................ 19 3.2.1 Klassenstructuur................................................................................................................ 19 3.2.2 Diagramelementen ............................................................................................................ 20 3.2.2.1 Knopen .................................................................................................................... 20 3.2.2.2 Takken..................................................................................................................... 21 3.2.3 Relatieve positionering ..................................................................................................... 21 3.2.4 Verbindingspunten bij knopen .......................................................................................... 22 3.2.4.1 Principe.................................................................................................................... 22 3.2.4.2 Conversie................................................................................................................. 22 3.2.5 Aanknopingspunten aan verbindingen .............................................................................. 23 3.2.6 Subdiagram en groepen..................................................................................................... 23 3.2.7 Scheiden van berekenen en tekenen.................................................................................. 24 3.2.7.1 Positie caching......................................................................................................... 24 3.2.7.2 Afhankelijkheden tussen verbindingen.................................................................... 25 3.2.8 Tekenen............................................................................................................................. 26 3.2.8.1 Infinite layering ....................................................................................................... 26 3.2.8.2 Delegatie.................................................................................................................. 27 3.2.8.3 Bézier subdivision ................................................................................................... 29 3.2.9 Selectie.............................................................................................................................. 32 3.2.10 Wijzigingen .................................................................................................................. 32 3.2.11 Serialisatie .................................................................................................................... 33 3.2.12 Generatie ...................................................................................................................... 34
4
Steven De Groote
Diagrameditor met layoutoptimalisatie
4
Front end ................................................................................................................ 36 4.1 Functionaliteit ........................................................................................................................ 36 4.1.1 Use-Case diagram ............................................................................................................. 36 4.1.2 Overzicht........................................................................................................................... 37 4.1.2.1 Invoer en uitvoer ..................................................................................................... 37 4.1.2.2 Configuratie............................................................................................................. 37 4.1.2.3 Bewerken................................................................................................................. 37 4.1.2.4 Lay-out .................................................................................................................... 38 4.2 Implementatie ........................................................................................................................ 39 4.2.1 Klassenstructuur................................................................................................................ 39 4.2.2 Koppeling met mediator.................................................................................................... 39 4.2.3 Configuratie en plugin systeem......................................................................................... 40 4.2.3.1 Observable settings.................................................................................................. 41 4.2.3.2 XML configuratiebestanden .................................................................................... 42 4.2.3.3 Plugins voor uitbreidbaarheid.................................................................................. 42 4.3 User interface......................................................................................................................... 44 4.3.1 Algemeen .......................................................................................................................... 44 4.3.2 Acties ................................................................................................................................ 45 4.3.3 Sneltoetsen en iconen........................................................................................................ 45 4.3.4 Dynamische menu’s.......................................................................................................... 45 4.3.5 Canvas............................................................................................................................... 46 4.3.5.1 Functie..................................................................................................................... 46 4.3.5.2 Grafische selectie .................................................................................................... 47 4.3.5.3 Elementen verslepen................................................................................................ 47 4.3.6 Diagramboom ................................................................................................................... 49 4.3.7 Eigenschappenlijst ............................................................................................................ 50 4.3.7.1 Overzicht ................................................................................................................. 50 4.3.7.2 Editors voor eigenschappen..................................................................................... 50 4.3.7.3 Typeconversie ......................................................................................................... 52
5
Automatische lay-out............................................................................................. 54 5.1
Overzicht ............................................................................................................................... 54
5.2
Visualisatie van het verloop................................................................................................... 54
5.3 Eenvoudige lay-outwijzigingen ............................................................................................. 55 5.3.1 Knopenreeks uitlijnen ....................................................................................................... 55 5.3.2 Knopen geometrisch positioneren..................................................................................... 55 5.4 Simulated annealing............................................................................................................... 56 5.4.1 Methode ............................................................................................................................ 56 5.4.2 Vaste knoopposities .......................................................................................................... 58 5.4.2.1 Verloop.................................................................................................................... 58 5.4.2.2 Energiefunctie ......................................................................................................... 58 5.4.2.3 Startwaarden............................................................................................................ 60 5.4.2.4 Stopvoorwaarden..................................................................................................... 61
6
Tests ....................................................................................................................... 62 6.1 Interne programmatesten ....................................................................................................... 62 6.1.1 Functionaliteit ................................................................................................................... 62 6.1.2 Automatische lay-out ........................................................................................................ 62 6.1.3 Performantie...................................................................................................................... 63 6.2
Externe acceptatietesten......................................................................................................... 63
7
Algemeen besluit ................................................................................................... 64
8
Referentielijst......................................................................................................... 66 5
Steven De Groote
Diagrameditor met layoutoptimalisatie 8.1
Boeken ................................................................................................................................... 66
8.2
Electronische bronnen ........................................................................................................... 66
Bijlage I Diagrammen uit de analyse............................................................................. 67 Bijlage II Klassendiagrammen....................................................................................... 74 Bijlage III Inhoud cd-rom .............................................................................................. 77 Bijlage IV Codestructuur ............................................................................................... 78 Bijlage V Testinformatie van annealing ........................................................................ 80 Bijlage VI Lijst van bugs ............................................................................................... 83
6
Steven De Groote
Diagrameditor met layoutoptimalisatie
Figurenlijst Figuur 1 : Voorbeeldiagram........................................................................................... 16 Figuur 2 : Structuurboom............................................................................................... 18 Figuur 3 : Beknopte klassenstructuur van het framework ............................................. 19 Figuur 4 : Takvolgorde .................................................................................................. 25 Figuur 5 : Circulaire afhankelijkheid............................................................................. 25 Figuur 6 : Kubische Bézier (links), kwadratische Bézier (rechts)................................. 30 Figuur 7 : Use cases voor de GUI.................................................................................. 36 Figuur 8 : Kernklassen van de GUI ............................................................................... 39 Figuur 9 : Mediator pattern in de GUI........................................................................... 40 Figuur 10 : Structuur van de GUI .................................................................................. 44 Figuur 11 : Aangepaste editors ...................................................................................... 51 Figuur 12 : Wijzigen van takeinde................................................................................. 52 Figuur 13 : Wijzigen van lettertype ............................................................................... 52 Figuur 14 : Layouter infobalk........................................................................................ 54 Figuur 15 : Opwaartse transitie...................................................................................... 59
7
Steven De Groote
Diagrameditor met layoutoptimalisatie
Inleiding Een afbeelding zegt vaak veel meer dan een stukje tekst. Omdat veel mensen eenvoudiger een afbeelding kunnen onthouden dan een alinea die een aantal verbanden uiteen zet, zijn de meeste technische boeken voorzien van tal van gestructureerde illustraties, ook wel diagrammen genoemd. Als we even denken aan toepassingen als een organigram, stamboom, een elektronisch schema, databankschema, projectplanning, … is het duidelijk dat diagrammen bijzonder veel gebruikt worden. In deze thesis verstaan we onder een diagram een soort verzameling van elementen die kunnen verbonden worden met elkaar. Een diagram wordt in deze vorm vooral gebruikt als illustratie en is meestal voorzien van tekst, kleur en allerhande visuele extra’s. Omwille van deze esthetische waarde ligt het niet voor de hand om een diagram te ontwerpen. Deze tekst bespreekt hoe een Javaprogramma werd ontwikkeld waarmee grafisch diagrammen kunnen worden getekend. Er werd een uitbreidbare structuur gebouwd waarmee diagrammen kunnen worden opgeslagen. Op basis hiervan kunnen ook andere programma’s ontwikkeld worden. Om de functionaliteit van het programma te demonstreren – en meteen ook te testen – werden zo goed als alle diagrammen in deze scriptie daarmee getekend. De UML schema’s en klassendiagrammen werden echter wel aangemaakt met gespecialiseerde applicaties. De codefragmenten in deze scriptie zijn bovendien louter ter illustratie en niet volledig. Vaak is enkel de essentie opgenomen of werd de code vereenvoudigd. Elk fragment werd daarbij voorzien van Nederlandstalige commentaar. De volledige programmacode die tijdens dit project ontwikkeld werd is te vinden op bijgevoegde CD-ROM. Bovendien is daarop ook een volledige API geplaatst die uitgebreide uitleg geeft over de klassen en functies.
8
Steven De Groote
Diagrameditor met layoutoptimalisatie
1
Project
1.1
Situering
Diagrammen kunnen visueel het verband aantonen tussen verschillende objecten. Het is daarbij onbelangrijk of die objecten van dezelfde soort zijn. Elk diagram bestaat uit een aantal elementen die verbonden kunnen zijn met relaties. Het is echter niet alleen de structuur die van belang is, maar ook de grafische vormgeving. Omdat punten en lijnen op zich zelden een betekenis hebben, worden elementen in een diagram vaak voorzien van een vorm, een kleur, tekst of zelfs afbeeldingen. Hoewel het principe vrij eenvoudig is mag het ontwerpen van een gestructureerd diagram niet onderschat worden. Om een diagram duidelijk te maken voor de lezer is de plaats van de elementen van zeer groot belang. Een organigram waarin een bediende boven de directeur-generaal wordt weergegeven leidt al snel tot overbodige verwarring. Wanneer men een diagram ziet, lijkt de structuur vaak vanzelfsprekend, maar de manier waarop men daartoe komt is dat niet altijd.
1.2
Doelstellingen
Het is duidelijk dat diagrammen zeer veel gebruikt worden, zowel om een eenvoudig verband duidelijk te maken als om een ingewikkelde illustratie voor te stellen. Om dat ontwerp eenvoudig te maken, werd in dit thesisproject een programma ontwikkeld om diagrammen te ontwerpen. Omdat ook de lay-out bepalend is voor de kwaliteit van het diagram, bespreken we ook een aantal mogelijkheden hoe de lay-out van een diagram kan aangepast worden zodat het eenvoudig wordt om dit snel te begrijpen. Daaronder verstaan we zowel eenvoudige wijzigingen zoals uitlijnen van knopen, als geavanceerde optimalisaties zoals met simulated annealing1. We stellen als doel het diagram zo te verbeteren dat het zo duidelijk mogelijk wordt voor elke lezer. Voorgaande wordt gerealiseerd door een applicatie in twee lagen. Afgeschermd van de gebruiker bevat de datalaag het eigenlijke diagram met alle informatie nodig zodat het eenduidig is bepaald. Omdat diagrammen echter grafische elementen zijn bevat deze structuur ook informatie over de plaats van de elementen. Deze laag wordt in de rest van deze scriptie besproken als framework2.
1
Simulated annealing: Techniek die toepasbaar is om combinatorische problemen op te lossen. Wordt hier toegepast om de lay-out van diagrammen te verbeteren (zie 5. Automatische layout). 2
Framework: Een collectie van klassen die functies voorzien om door een cliënt gebruikt te worden. Het is een uitbreidbare beschrijving van een model dat enkel nut heeft wanneer het als component gebruikt wordt in een cliënt applicatie. 9
Steven De Groote
Diagrameditor met layoutoptimalisatie
Daarbovenop is een grafische schil voorzien waardoor een diagram visueel kan gewijzigd worden. Het is belangrijk in te zien dat deze implementatie slechts een mogelijke gebruikersinterface (GUI) is. Het bepaalt de manier waarop een diagram bewerkt kan worden. Omdat de structuur van het diagram onafhankelijk is van deze van de GUI kan een alternatieve GUI ontwikkeld worden die zich anders gedraagt naar de gebruiker toe.
1.3
Technologie
1.3.1
Gebruikersplatform
De applicatie werd ontwikkeld voor Java 5 en vereist daarom voor iedereen die het wil uitvoeren een Java 5 virtual machine of recenter. Bovendien is ook nog jdom.jar nodig, een API die eenvoudig schrijven en lezen van XML bestanden vanuit java toelaat. Het wordt in de GUI implementatie gebruikt om de configuratiebestanden te laden en terug op te slaan in een leesbaar formaat. Dit pakket is te vinden op http://www.jdom.org/.
1.3.2
Ontwikkelplatform
De volledige ontwikkeling van de applicatie gebeurde in Java. Er werd voor deze technologie gekozen omdat bij eerdere projecten en tijdens een stage al gebruik gemaakt werd van het .NET-platform. Sun Java is daarom een nieuwe uitdaging. De ontwikkeling van Java is de laatste jaren sterk versneld en heeft al belangrijke snelheidsverbeteringen opgeleverd in de laatste versie. Java 6 beta is bovendien ook al klaar en belooft opnieuw een grote stap voorwaarts. De technologie zal aan dit ontwikkeltempo zeker niet moeten onderdoen voor .NET. Uiteraard dankzij Java is de ontwikkelde applicatie dan ook op elk besturingssysteem uit te voeren. Met de stijgende populariteit van Linux is dit een belangrijk aspect. Alle code, zowel voor het testprogramma als voor de uiteindelijke diagramapplicatie werd voorzien van uitgebreide commentaar. Ook voor ieder package en elke klasse is commentaar voorzien in Javadoc stijl. Dit betekent dat in de API van beide applicaties – te vinden op bijgevoegde CD-ROM – er voldoende documentatie aanwezig is om de werking van de functies te begrijpen. In die API zijn bovendien alle externe packages, zoals de standaard Java package en de jdom.jar gelinkt zodat de API zeer volledig en bruikbaar is. Bij de ontwikkeling werden onder andere volgende applicaties gebruikt: •
1
Java 5 J2SE Development Kit (JDK) en Runtime Environment (JRE) update 6 (gratis): Binnen het programma zelf werd, vooral voor de opbouw van de diagram datastructuur, intensief gebruik gemaakt van de Java Beans1 specificatie. Uiteindelijk biedt dit niets dan voordelen, gezien de code meer verstaanbaar is
Java Bean: Herbruikbare Java component met precies gedefinieerde naamgeving van functies. 10
Steven De Groote
Diagrameditor met layoutoptimalisatie
voor Javaontwikkelaars en de toegang tot de objecten eenvoudig wordt met introspectie1. Op deze manier was het mogelijk alle eigenschappen van diagramelementen flexibel op het scherm in de GUI te passen.
1
•
Eclipse SDK 3.1.2 (gratis in “Eclipse foundation user agreement”): Ontwikkelomgeving voor Java die het coderen vele malen versnelt. Werkt bovendien een stuk efficiënter en eenvoudiger dan NetBeans.
•
Borland Together Architect 2006 for Eclipse (marktwaarde $5000): Hiermee werden eenvoudig klassendiagrammen aangemaakt uit het codeproject van eclipse.
•
GNU Image Manipulation Program (GIMP) (gratis onder de “GNU public licence, GPL”): Bewerken van afbeeldingen en iconen gebruikt in de grafische user interface.
•
PDFcreator (gratis onder GPL licentie): Aanmaken van de pdf’s voor scriptie en dergelijke.
Introspectie: Dynamische detectie van de methodes en eigenschappen van een Javaobject. 11
Steven De Groote
Diagrameditor met layoutoptimalisatie
2
Analyse
2.1
Diagram als data
Diagrammen kunnen een zeer uiteenlopende structuur hebben. Ze zijn verwant met grafen, zij het dan dat er veel minder beperkingen bestaan voor de elementen. Zo is een graaf beperkt tot knopen die onderling verbonden kunnen worden met takken. Elk van deze knopen heeft hierbij een gelijkaardige inhoud. Een graaf is een soort abstracte gegevensstructuur die ontwikkeld werd om tal van problemen oplosbaar te maken. Gezien het zelf een structuur voor gegevens is kan een graaf op velerlei manieren voorgesteld worden. Op de duidelijkheid na voor de presentatie ervan is de positionering van knopen en takken bij een graaf namelijk onbelangrijk. In diagrammen zijn er echter meer mogelijkheden die niet allemaal voor de hand liggen. Waar een graaf op zichzelf kan bestaan zonder grafische voorstelling, is dit zinloos voor een diagram. Hoewel diagrammen ook kunnen gebruikt worden om gegevens op te slaan (gezien hun verwantschap met grafen), zijn ze in de eerste plaats een voorstelling van die gegevens. Een diagram bevat bijgevolg wel informatie over de lay-out. Posities van knopen, de vorm van verbindingen en andere presentatiegegevens zijn eigen aan het diagram en essentieel om het voor te stellen. Zo is het bijvoorbeeld belangrijk dat een hiërarchische structuur in een diagram ook hiërarchisch voorgesteld wordt. De plaats van de elementen is daarom niet willekeurig. Bovendien zijn diagramknopen geen zelfstandige entiteiten, maar containers: elke knoop is meestal een samenstelling van elementen. Algemeen kunnen we stellen dat een diagram er duidelijk en goed ontworpen moet uitzien. Het heeft met andere woorden zelden zin elke knoop identiek voor te stellen, gezien een “lezer” niet zal begrijpen wat het diagram voorstelt. Om een inzicht te krijgen in de structuur van een diagram, bijzondere eigenschappen en veel gebruikte manieren om iets voor te stellen, werden bestaande diagrammen verzameld en geanalyseerd. Een deel van die diagrammen is terug te vinden in Bijlage I. De belangrijkste aspecten zijn onder te verdelen in de structurele (2.1.1) en de lay-out gebonden eigenschappen (2.1.2). Gezien een diagram echter een grafische voorstelling is, zijn beide zeer nauw met elkaar verwant.
2.1.1
Structurele eigenschappen
Onder deze groep beschouwen we alle eigenschappen van een diagram die hetzelfde blijven als we de lay-out van het diagram wijzigen. Door knopen te verplaatsen, kleuren te wijzigen en vormen aan te passen, zal geen van deze eigenschappen veranderen. Volgende elementen kunnen voorkomen in een diagram: •
In knopen komen takken toe en/of vertrekken er takken naar andere knopen. Er kunnen tussen twee knopen bovendien meerdere gelijkaardige verbindingen voorkomen, al dan niet in dezelfde richting. 12
Steven De Groote
Diagrameditor met layoutoptimalisatie
•
Een tak is een lijn die een relatie aanduidt. Belangrijk hierbij is dat er niet noodzakelijk twee knopen verbonden worden. Een tak kan immers ook verbonden zijn aan een andere verbinding, of ook een uiteinde hebben waar geen zichtbare knoop aan gekoppeld is.
•
Verbindingen hebben steeds twee of meerdere uiteinden. Ze kunnen meerdere elementen met elkaar verbinden.
•
In sommige uitzonderlijke gevallen komt een diagram voor als subdiagram in een ander. Het wordt dan beschouwd als een soort groep van elementen (knopen en takken) dat binnen het grotere diagram opgenomen wordt en kan verbonden zijn met andere knopen.
Deze eigenschappen zijn bijzonder eenvoudig, maar tonen meteen ook de mogelijkheden van een diagram aan. In de ontwikkeling van de editor1 werd dan ook vooropgesteld dat alle voorgenoemde elementen mogelijk moesten zijn.
2.1.2
Lay-out gebonden eigenschappen
Deze eigenschappen bepalen de manier waarop de structuur voorgesteld wordt. Voor een diagram is dit bijzonder belangrijk gezien een goede voorstelling helpt bij een snel begrip van de voorstelling. De lay-out van diagrammen is sterk uiteenlopend, maar zowel knopen als verbindingen worden meestal gelijkaardig voorgesteld binnen eenzelfde diagram: •
Het uiteinde van een verbinding wordt dikwijls aangeduid door een pijlvorm, een label of een andere indicatie. Deze kunnen zowel identiek als verschillend zijn bij het einde en het begin van de verbinding. Aan de knoop worden takken dikwijls verbonden aan hoekpunten of aan het midden van een zijde.
•
Bij knopen en takken wordt meestal een label voorzien. De positie ervan is sterk uiteenlopend. In sommige gevallen worden meerdere labels op een knoop voorzien, specifiek aan de hoekpunten of uiteinden. De richting van die tekst hangt in sommige gevallen zelfs af van de richting van de tak.
•
Verbindingen worden aangeduid door een lijntype, kleur, dikte en vooral een vorm. We kunnen een onderscheid maken tussen rechte, rechthoekige (orthogonale), kromme (Bézier, bspline, …) en gebroken verbindingen (polyline).
•
Knopen worden vaak gerangschikt op horizontale of verticale lijnen. Meestal omdat ze verbonden zijn met elkaar door een aantal verbindingen. Algemeen stellen we vast dat verbonden knopen dicht bij elkaar te vinden zijn. Deze eigenschap is bijna altijd van toepassing op alle knopen van een diagram en wordt onder andere gebruikt bij hiërarchische structuren.
1
Editor: front end gedeelte van de applicatie dat gebruik maakt van het framework om grafisch diagrammen aan te maken en te bewerken. 13
Steven De Groote
Diagrameditor met layoutoptimalisatie
•
2.2
Een knoop wordt voorgesteld door een punt, een afbeelding, een geometrische figuur of een samenstelling van deze elementen. Meestal is daarbij ook een label voorzien.
Grafisch bewerken
Uiteraard bestaan er al een aantal andere programma’s die ook toelaten diagrammen aan te maken en te bewerken. De meeste hiervan bestaan bovendien al geruime tijd, waardoor ze al zeer uitgebreide mogelijkheden bieden. Om de best mogelijke gebruikersinterface te kunnen ontwikkelen werden Dia 0.95, Microsoft Visio 2003 en SmartDraw Suite 7.01 uitgeprobeerd. Bij elk van deze programma’s zijn een aantal belangrijke tekortkomingen aan het licht gekomen waarvoor deze thesis een betere oplossing biedt: •
Bij de selectie van een element zijn de eigenschappen van een element niet onmiddellijk duidelijk. Deze moeten eerst opgevraagd worden alvorens de gebruiker ze kan bekijken of bewerken. Dit wordt opgelost met de in 4.3.7 besproken eigenschappenlijst.
•
In Dia kan geen enkel element geroteerd worden. Dit is een belangrijk gebrek dat in de thesisapplicatie zelfs nog wordt aangevuld door rotaties afhankelijk te maken van de ouderknoop (zie 3.2.3 Relatieve positionering).
•
In Dia is het niet mogelijk om op meerdere plaatsen langs een verbinding een label te voorzien. Voor dat label is het dan zelfs niet mogelijk om die tekst schuin afgebeeld te krijgen. In het ontwikkelde framework zijn met aanknopingspunten aan een verbinding (3.2.5) beide wel mogelijk.
•
Microsoft Visio laat niet toe om zelf, door middel van eigen ontwikkelingen of extra’s van derden functionaliteit toe te voegen aan het programma. Het pluginsysteem uit 4.2.3 laat dit wel toe.
Verder zijn de GUI en een aantal functies voor het bewerken van een diagram in de ontwikkelde applicatie geïnspireerd op deze geteste programma’s. Alle functies die voorzien zijn in deze beschikbare applicaties kunnen bovendien geïmplementeerd worden in deze thesisapplicatie door verbeteringen aan te brengen in de GUI en/of het framework uit te breiden met extra klassen.
2.3
Klassenstructuur
De structuur van het klassendiagram is bijzonder belangrijk voor een framework. Het moet de mogelijkheid bieden tot uitbreiding zonder dat bestaande klassen moeten aangepast worden. Bovendien mag de aard van de uitbreidingen niet beperkt worden en moet eender welk soort diagram kunnen voorgesteld worden, al dan niet gebruik makend van een dergelijke uitbreiding. Voordat met een implementatie werd gestart werd het klassenschema opgebouwd. Er werden enkel schema’s uitgetekend en onderzocht op de mogelijkheden en beperkingen daarvan. Bijna dagelijks werden wijzigingen doorgevoerd. In de eerste versie van de klassenstructuur was er zelfs nog geen sprake van een hiërarchische structuur om een 14
Steven De Groote
Diagrameditor met layoutoptimalisatie
diagram in op te slaan. Problemen die ontdekt werden in vroegere schema’s leidden echter tot deze structuur die heel wat nieuwe mogelijkheden opende. Tijdens deze analyse werd ook een testprogramma ontwikkeld om een aantal mogelijkheden voor grafisch bewerken in Java te verkennen. Ook hiermee werden al snel problemen ontdekt die opgelost konden worden door wijzigingen in het klassendiagram. Het programma, dat ook op bijgevoegde CD-ROM te vinden is, heeft een canvas dat een eenvoudige graaf kan tekenen. Alle knopen zijn cirkels en alle takken rechte lijnen. Grafisch selecteren van elementen werd ook uitgetest doordat de gebruiker knopen kan verplaatsen. Deze ontwikkeling van de klassenstructuur duurde ongeveer twee maanden alvorens met de implementatie van de applicatie te beginnen. Het klassendiagram was op dat moment in grote lijnen definitief, zij het dat er nadien nog enkele benamingen veranderd zijn. De structuur liet in die vorm al toe om een diagram te bevatten met alle structurele en lay-outgebonden eigenschappen die uit de analyse (zie hoger) bleken. De wijzigingen tijdens de implementatie zijn er slechts gekomen vanwege het Java platform of om de mogelijkheden in verband met de hiërarchische opslagstructuur van een diagram (zie 3.1 Boomstructuur) te vergroten.
15
Steven De Groote
Diagrameditor met layoutoptimalisatie
3
Framework
3.1
Boomstructuur
3.1.1
Diagram als boom
Zoals eerder al vermeld, is een diagram een vrij complexe, grafische voorstelling met weinig beperkingen voor de knopen. Uit de analyse bleek al dat knopen zo goed als altijd samengestelde elementen zijn. Als we veronderstellen – dat blijkt ook uit de analyse – dat er altijd één element het belangrijkste is dan is een samengestelde knoop een combinatie van een “ouderknoop”1 met een aantal “kindknopen”2. Dit aantal kinderen is in theorie zelfs onbeperkt. Belangrijk hierbij is de manier waarop de afzonderlijk elementen samengesteld zijn tot de hele knoop: de ouderknoop en zijn kinderen bepalen samen het uitzicht van de hele node (knoop). De positie van de kinderen is bijgevolg afhankelijk van de ouderknoop en meestal gelijksoortig aan andere knopen in hetzelfde diagram.
Figuur 1 : Voorbeeldiagram
Toegepast op het eenvoudige diagram in Figuur 1 zijn A, B en C ouderknopen omdat ze onmiddellijk aan het diagram gekoppeld zijn. A en B zijn met elkaar in hun middelpunt verbonden met tak1 waarop een punt X is aangebracht in het midden van de verbindingslijn. Tak 2 toont dan weer een relatie tussen knoop C – een eenvoudig punt – en het punt X op tak 1. Omdat de positie van het label “Uitleg” bij de knoop A hoort en “tekstlabel” bij X hoort, kunnen we die elementen beschouwen als kindknopen van hun ouders. Een diagram bestaat dus uit een aantal samengestelde knopen met daartussen enkele verbindingen. Hoewel dit wel het geval is in dit voorbeeld, vertrekken die verbindingen niet altijd vanuit het middelpunt van een knoop. Het is mogelijk dat een tak met een knoop verbonden is aan een hoekpunt. Sterker nog, een tak kan eigenlijk eender welk
1
Ouderknoop: Knoop die direct kind is van het diagram. Ze zijn dus nooit kind van een andere knoop maar kunnen wel ouder zijn van een aantal andere knopen.
2
Kindknoop: Een knoop die als ouder een andere knoop of een diagramtak heeft. Deze ouderkind relatie komt enkel tot uiting in de boomstructuur van het diagram en is niet zichtbaar in een grafische afdruk ervan. 16
Steven De Groote
Diagrameditor met layoutoptimalisatie
knopenpaar met elkaar verbinden, onafhankelijk of dat ouderknopen, kindknopen of knopen zijn die aan een verbinding vastgekoppeld zijn. Dit principe met ouderknopen en kindknopen en de eigenschappen die blijken uit de analyse maken het mogelijk een diagram te beschouwen als een soort boomstructuur. Die boomstructuur bevat dan alle kinderen, samen met een lijst van alle takken die in dat diagram voorkomen. Waar de meeste programma’s gebruik maken van lineaire structuren met kruisverwijzingen hebben bomen, als opslagstructuur voor een diagram, een aantal niet te onderschatten voordelen: • • • •
3.1.2
Knopen kunnen samengesteld worden door een object met kinderen aan te maken. Een kindknoop kan eigenschappen overerven van zijn ouder. Een knoop verwijderen kan snel omdat alle kinderen onmiddellijk gevonden kunnen worden. De positie van een kindknoop kan afhankelijk zijn van de positie van zijn ouderknoop.
Implementatie
Door de elementen van het diagram in een boom op te slaan, kunnen we van al deze voordelen gebruik maken. Gezien die elementen vaak slechts een aantal directe kinderen hebben – en dus geen kleinkinderen – is in bijna alle gevallen de boom slechts enkele lagen diep. Het diagram kan dan beschouwd worden als de wortel van de boom. De elementen van dat diagram zitten opgeslagen in de diepere lagen in de boomstructuur. Diagramverbindingen kunnen echter van elkaar afhankelijk zijn. Het is met andere woorden belangrijk om een volgorde voor de takken bij te houden die zal bepalen welke verbinding het eerst verwerkt of getekend moet worden (3.2.7.2. Afhankelijkheden tussen verbindingen). Om dat te vereenvoudigen, kunnen we de diagramboom opdelen in twee kleinere deelbomen: een knopenboom en een takkenboom. In de knopenboom zitten dan alle ouderknopen en hun kinderen, terwijl in de takkenboom alle diagramverbindingen samen met hun kinderen worden opgeslagen. Abstract bestaat een diagram dus uit een boom die gesplitst kan worden in een knopenboom en een takkenboom. Deze grote elementenboom is echter alleen een algemene opvatting, maar wordt niet als dusdanig geïmplementeerd. In plaats daarvan worden de ouderknopen van het diagram opgeslagen in een HashSet daar hun volgorde onbelangrijk is (de toegangtijd tot de knopen is hierdoor trouwens O(1)). De takken zitten verzameld in een zelf ontwikkelde SortedEdgeCollection. Ze worden daarin gesorteerd, rekening houdend met hun onderlinge afhankelijkheden: // Set van alle ouderknopen. private HashSet
points; // Verzameling van alle diagramtakken, opgeslagen als een DAG. private SortedEdgeCollection edges;
17
Steven De Groote
Diagrameditor met layoutoptimalisatie
Figuur 2 : Structuurboom
De structuurboom van het voorbeelddiagram in Figuur 1 is voorgesteld in Figuur 2. De scheiding van beide deelbomen is in deze figuur duidelijk zichtbaar en biedt belangrijke mogelijkheden. Ten eerste is er de analogie met grafen, die met deze diagramstructuur eenvoudig kunnen opgeslagen worden. Belangrijker is echter dat een verbinding in het diagram eender welk paar knopen met elkaar kan verbinden. De knoop aan het ene einde van de verbinding mag dus op een andere diepte in de knopenboom liggen dan de knoop aan het andere einde van de verbinding. In Figuur 2 zijn de puntknopen voorgesteld door rode elementen, de vormknopen door blauwe elementen en de diagramverbindingen door groene rechthoeken. Volle verbindinglijnen stellen een ouder-kindrelatie voor en vormen de structuurboom. Zo is Ellips A de ouderknoop van het label “uitleg” en heeft het bovendien een viertal – waarvan er slechts twee afgebeeld in de figuur – verbindingspunten (zie 3.2.4. Verbindingspunten bij knopen). Het label met tekst “uitleg” heeft op zijn beurt ook verbindingspunten om de gebruiker de kans te geven een verbinding te koppelen aan de rand van een vormknoop. Een stippellijn in de figuur wijst op een referentie. Er zijn voor elke diagramverbinding twee referenties naar andere knopen. Ze stellen de begin- en eindknoop voor van die verbinding. Voor tak 1 zijn die referenties gericht op Ellips A en Ellips B. Bij tak 2 is het beginpunt ook een ouderknoop in het diagram: punt C. Het eindpunt is echter een aanknopingspunt van tak 1. Het wijst erop dat tak 2 afhankelijk is van tak 1 en steeds na tak 1 verwerkt of getekend moet worden. De knopenboom bevat op de eerste laag – de directe kinderen van het diagram – alle knopen die geen kind zijn van een andere knoop of tak (de ouderknopen). De takkenboom bevat op de eerste laag alle verbindingen van het diagram. Op diepere lagen kunnen zich, in beide bomen, knopen bevinden. In de knopenboom zijn dit allemaal OffsetNode objecten met als ouderknoop een element uit de eerste laag. In de takkenboom zitten er op de tweede laag enkel EdgePoint objecten (knopen die enkel aan een diagramverbinding kunnen vastgekoppeld worden, 3.2.5). Dieper in de hiërarchie kunnen in beide deelbomen enkel nog OffsetNode-objecten (zowel puntknopen als vormknopen) voorkomen. Elke positie – en in feite de hele transformatie, inclusief rotatie en vergroten – van een OffsetNode wordt gedefinieerd als een offset relatief ten opzichte van zijn ouder. De 18
Steven De Groote
Diagrameditor met layoutoptimalisatie
wortel kan dan beschouwd worden als een knoop in de oorsprong van het tekenvlak. De absolute positie van een knoop kan dan bepaald worden door in de boom naar dat element af te dalen en alle transformaties van de gepasseerde elementen samen te voegen. Op die manier worden de kinderen steeds bij de ouderknoop gehouden wanneer die bewerkt wordt. De precieze implementatie en werkingen van deze aspecten komen verder in dit hoofdstuk aan bod.
3.2
Structuur
3.2.1
Klassenstructuur
Figuur 3 : Beknopte klassenstructuur van het framework
19
Steven De Groote
Diagrameditor met layoutoptimalisatie
Bovenstaande figuur is een verkleinde klassenstructuur van het framework. Dit diagram toont enkel de relaties tussen de klassen met hun naam, en verbergt functies, klasseveriabelen en bean properties1 van de gewone klassen. Een uitgebreidere klassenstructuur van het framework is te vinden in Bijlage II. Het is niet onbelangrijk te weten dat elk van deze klassen zo ontworpen is, zodat alle eigenschappen toegankelijk zijn met functies zoals die voorgeschreven zijn in de Java beans specificatie. Zoals blijkt uit voorgaand schema, kan op een diagram elk soort DiagramElement getoond worden. De twee belangrijkste groepen daarin zijn Node die elementen voorstellen (knopen, tekst, een afbeelding, …) en Edge die de verbinding vormen tussen precies twee Node objecten.
3.2.2
Diagramelementen
3.2.2.1 Knopen Een knoop, ook wel node genoemd, betekent voor de structuur van het diagram niets meer dan een plaats waar takken kunnen vertrekken en aankomen. Voor de lay-out van het diagram is ook de vormgeving en positie van belang. Op deze twee grafische criteria kunnen we vier grote groepen onderscheiden:
1
•
De eenvoudigste van alle knopen is een OffsetPoint. Dit is een punt dat zijn positie bepaald ziet door een x- en y-coördinaat. Net zoals voor elk ander knooptype dat gepositioneerd wordt met een offset is die positie echter afhankelijk van de plaats van zijn ouder in het diagram. Deze relatieve positionering wordt besproken in 3.2.3.
•
Als tweede type is er de OffsetArea (of vormknoop) dat zonder twijfel het meest gebruikt wordt in diagrammen. Hoewel ook gepositioneerd met coördinaten, bevat dit type knoop een vorm en meteen ook een oppervlakte. Die oppervlakte kan zowel opgevuld zijn met een afbeelding uit een bestand, tekst of een kleur – eventueel zelfs transparant. Door dit type knoop van het framework uit te breiden, is het zelfs mogelijk eender welke figuur te tonen. Verder zijn in het framework klassen geïmplementeerd voor rechthoeken, afgeronde rechthoeken en ellipsen.
•
Een derde type knoop is voorzien om meedere verbindingspunten te hebben bij een OffsetArea. Het ConnectionPoint is een punt dat niet kan aangemaakt worden door een gebruiker, maar voorzien wordt door een vormknoop. Wanneer die gewijzigd wordt, zal die er meteen ook voor zorgen dat de positie van de verbindingspunten correct blijft. Verbindingspunten worden meestal voorzien aan de rand van een vormknoop. Ze geven de gebruiker meer vrijheid om te kiezen waar precies een verbinding aan een vormknoop moet gekoppeld worden. Het middelpunt van die vormknoop is namelijk niet altijd de beste of duidelijkste oplossing. Er wordt dieper ingegaan op deze verbindingspunten in 3.2.4.
Bean property: Eigenschappen van een Javabean object die gelezen en/of gewijzigd worden. 20
Steven De Groote
Diagrameditor met layoutoptimalisatie
•
Tenslotte is er het EdgePoint, een punt dat als enige zijn positie niet bepaald ziet door een offset ten opzichte van de positie van zijn ouderknoop. Een EdgePoint is daarentegen altijd vastgekoppeld aan een verbinding tussen 2 andere knopen. Zijn positie is bepaald door één getal: een fractie die aanduidt waar langs de verbindingslijn deze knoop moet worden getekend. Meer over deze aanknopingspunten is te vinden in 3.2.5.
3.2.2.2 Takken Takken zijn de verbindingen die een relatie aanduiden tussen twee elementen in het diagram. Hoewel er verschillende types zijn, werd hier gekozen om geen enkele klasse te laten overerven van Edge. In plaats daarvan is de klasse universeel en slaat die zijn eigenschappen op als klassenvariabelen. Het maakt de toegang tot een tak daarom eenvormig, onafhankelijk van welke vorm de verbinding precies is. Deze vorm, in het bijzonder de manier hoe beide eindpunten met elkaar worden verbonden, wordt bepaald door een EdgePath object. Het zijn precies de verschillende klassen die overerven van deze interface die voor verschillende types van takken zorgen. Zo zijn er in de huidige versie rechte en gebroken verbindingen, maar kan de functionaliteit eenvoudig uitgebreid worden met Bézier1 of BSpline2 krommes. Het werk hiertoe beperkt zich tot het implementeren van de juiste interfaces en de klasse te registreren in het plugin systeem van de applicatie. Voor het overige kan het uitzicht van een tak gewijzigd worden door het lijntype, de kleur en het toewijzen van pijlen aan de uiteinden van de verbinding. Ook pijltypes (klassen die de klasse Arrow uitbreiden) kunnen toegevoegd worden met het plugin systeem zoals besproken in 4.2.3.
3.2.3
Relatieve positionering
Samenhangend met de boomstructuur voor een diagram zijn ook de posities van alle knopen opgeslagen als relatieve coördinaten ten opzichte van hun ouder. Het blijft echter niet bij positionering. Knopen kunnen onafhankelijk van elkaar gedraaid en vergroot of verkleind worden. Deze transformaties voor de positie worden voor elk element bijgehouden als een Transformation object. Dit bevat informatie over de rotatie, de vergroting en de verschuiving ten opzichte van zijn ouder. Voor elementen die geen ouder hebben (ouderknopen en takken) is deze offset meteen absoluut. Een kind daarvan kent zijn absolute positie dan door een samenstelling te maken van de positie van zijn ouder met zijn eigen offset. Analoog is voor elk element de absolute positie eenduidig bepaald.
1
Bézier curve: Kromme bepaald door 3 of 4 controlepunten. Werd ontwikkeld door Pierre Bézier voor Renault.
2
BSpline: Kromme samengesteld uit opeenvolgende Bézier-curves zodat de tweede afgeleide van de lijnstukken gelijk zijn in de controlepunten. 21
Steven De Groote
Diagrameditor met layoutoptimalisatie
Voor EdgePoint elementen is de positionering enigszins anders: de positie voor deze punten wordt berekend aan de hand van de positie van de tak waarvan hij kind is. Deze punten bezitten echter wel instelbare rotatie- en vergrotingseigenschappen. Wanneer dus een knoop wordt verplaatst, wordt enkel de positie-informatie van die knoop gewijzigd. Vermits de kinderen relatief gepositioneerd zijn, zullen deze automatisch mee volgen. Ook hier geldt hetzelfde voor rotatie, vergroting en verkleining. Dit heeft echter tot gevolg dat wanneer een knoop – met daarop een kindelement, zoals bijvoorbeeld een label – gedraaid wordt, die tekst ook zal meedraaien. Omdat dit meestal niet gewenst is, kan door de “relatieve” eigenschap van dat kind uit te schakelen, vermeden worden dat de rotatie en vergroting van de ouder invloed hebben op die van het kind. Dit kan grafisch in de eigenschappenlijst (zie 4.3.7) van dat element.
3.2.4
Verbindingspunten bij knopen
3.2.4.1 Principe Hoewel het voor een punt duidelijk is waar takken vertrekken of aankomen, is dit veel minder vanzelfsprekend bij een Node die een oppervlakte omvat. Beide hebben echter een positiepunt, dat voor een vormknoop of OffsetArea het centrum van dat gebied is. Uit de analyse blijkt dat een verbinding niet alleen naar het midden van de vormknoop wijst, maar in sommige gevallen eindigt in een speciaal punt – zoals een hoekpunt of buigpunt – langs de rand van die vorm. In alle gevallen wordt de verbinding uiteraard niet over de knoop getekend, maar eindigt ze aan de rand ervan (zie 3.2.8. Tekenen). Verbindingen tekenen van middelpunt tot middelpunt is wel sluitend om een graaf voor te stellen, maar geheel ontoereikend voor diagrammen. Om meer vrijheid te laten aan de gebruiker worden vormknopen voorzien van een aantal verbindingspunten. Die zijn in het framework ingebouwd met de klasse ConnectionPoint. Deze punten liggen op de rand van een vormknoop en zijn in feite niets anders dan OffsetPoints met een paar bijzondere eigenschappen. Wanneer zo’n verbindingspunt namelijk verschoven wordt dan enkel de knoop waar dat punt bij hoort – zijn ouderknoop – verschuiven. Op die manier blijft het verbindingspunt altijd op dezelfde relatieve positie ten opzichte van zijn ouder. Verder zijn verbindingspunten standaard niet zichtbaar en worden ze alleen gemarkeerd wanneer een tak getekend wordt. Gewone punten in het diagram worden standaard voorgesteld door een zwart punt. Precies omdat deze verbindingspunten ook Nodes zijn, kan een diagramverbinding eraan vasthaken. Gezien ook deze punten een relatieve positionering hebben, schuiven, draaien en herschalen ze mee met hun ouder, zodat ze steeds, zonder extra werk, precies op de rand van de figuur blijven staan.
3.2.4.2 Conversie De verschillende types van OffsetArea hebben allemaal een verschillende vorm maar kunnen onderling geconverteerd worden. Een knoop in het diagram die bijvoorbeeld 22
Steven De Groote
Diagrameditor met layoutoptimalisatie
een ellipsvorm heeft, kan bijgevolg omgezet worden naar een rechthoek zonder dat die knoop verwijderd moet worden. Bij dit converteren blijven alle gemeenschappelijke eigenschappen (zoals randdikte en vulkleur) bovendien ongewijzigd. Met verschillende figuren komen echter ook andere verbindingspunten overeen. Het aantal en de plaats van die punten kan namelijk verschillen. Zo heeft een rechthoek 9 verbindingspunten, en een cirkel of afgeronde rechthoek slechts 4. Om dit op te vangen werd in OffsetArea een functie voorzien die opgeroepen wordt telkens als een vorm naar een andere omgezet wordt. De functie zorgt ervoor dat de eindpunten van de verbindingen zo weinig mogelijk van plaats veranderen, of ook, dat ter vervanging van het oude verbindingspunt de tak wordt gekoppeld aan het dichtst mogelijke nieuwe verbindingspunt langs die knoopomtrek. De invloed die de conversie van een vormknoop heeft op de rest van het diagram wordt tot een minimum beperkt.
3.2.5
Aanknopingspunten aan verbindingen
In tegenstelling tot grafen, waar verbindingen niets anders doen dan twee knopen verbinden, kunnen in een diagram verbindingen gemaakt worden met meer dan twee uiteinden. Bovendien is het vaak nuttig om een label of een figuur langs die verbinding te voorzien. Om dit te realiseren kan een EdgePoint aan een verbinding gekoppeld worden. Dit is een punt dat zich altijd langs een diagramverbinding bevindt. Zijn positie is bepaald door een getal variërend van 0 tot 100, zodanig dat 0 gelijk is aan de plaats waar de verbinding vertrekt, 100 het verbindingseinde is en 50 precies halfweg de verbinding ligt. Gezien dit een punt is, kunnen er andere takken aan gekoppeld worden zodat het lijkt alsof er één tak is met meerdere uiteinden. Het aanknopingspunt is net zoals elke andere knoop in staat om kindknopen te hebben. Door een tekstknoop als kind toe te voegen, krijgen we een label langs de tak dat zal meeschuiven wanneer die tak verdraaid of verschoven wordt. Het is bovendien mogelijk – gelijkaardig aan de relatieve rotatie – te bepalen of de elementen aan het aanknopingspunt moeten meedraaien met een tak. Wanneer dit ingeschakeld is, wordt de draaihoek van de tak op de plaats van het aanknopingspunt gekoppeld en toegevoegd aan de rotatie die voor dat aanknopingspunt werd ingesteld. Een tekst langs een tak kan bijgevolg zo ingesteld worden dat het steeds eenzelfde hoek met de tak of de horizontale insluit.
3.2.6
Subdiagram en groepen
Van bij het begin van de analyse werd voorop gesteld dat groepen of subdiagrammen mogelijk moesten zijn. Het is handig en soms hard nodig dat elementen samen genomen kunnen worden. Er werd dan ook meteen in de klassenstructuur gezorgd dat het mogelijk was om een diagram in een diagram op te nemen. Na verloop van tijd werd echter duidelijk dat met een boomstructuur, subdiagrammen op zich een overbodige luxe waren. Een subdiagram kan immers eenvoudig gemaakt worden door alle elementen van dat diagram aan een gemeenschappelijk ouderpunt te hangen. Als we in plaats van een ouderpunt een vormknoop als ouder nemen, is het zelfs mogelijk een rand of 23
Steven De Groote
Diagrameditor met layoutoptimalisatie
achtergrondkleur voor het hele subdiagram te voorzien. Alle elementen in dit subdiagram zullen samen de transformaties van hun ouder ondergaan en zich gedragen als een groep. Het verdraaien of verschuiven van het ouderelement heeft dan tot gevolg dat alle kinderen ook verdraaien of verschuiven. Bovendien is het voor echte subdiagrammen een probleem om verbindingen te maken. Alle verbindingen van een diagram worden immers in het diagramobject opgeslagen. Een paar knopen van verschillende diagrammen met elkaar verbinden was daarom onmogelijk. De klasse Diagram werd vervolgens herwerkt zodat deze niet meer erfde van een diagrampunt, maar enkel een implementatie is van DiagramElementContainer, een interface die trouwens door elk diagramobject geïmplementeerd wordt. Het resultaat is dat, hoewel de elementen gegroepeerd zijn, ze zich niet in een afzonderlijk genest diagram bevinden. Een diagramverbinding kan vervolgens transparant een paar knopen met elkaar verbinden die niet in dezelfde groep – en dus niet dezelfde ouderknoop hebben – zitten.
3.2.7
Scheiden van berekenen en tekenen
Omdat een diagram een grafisch object is, zijn er een aantal berekeningen nodig voor de elementen die ervoor zorgen dat knopen en takken geselecteerd, gewijzigd en getekend kunnen worden. Dit voorafgaand werk zorgt voor een juiste positionering van de elementen in het diagram en wordt in de programmacode aangeduid als “rendering”. Tijdens het verschuiven van een programmavenster, selecteren van een element en scrollen in het canvas is het telkens nodig om het scherm te vernieuwen en dus te tekenen. Gezien het diagram in deze gevallen zelf niet wijzigt, zijn er ook geen berekeningen nodig die de posities bepalen van de knopen. Het renderen kan hier met andere woorden overgeslagen worden. Vanwege de voordelen voor de performantie werden deze rendering fase en tekenfase gescheiden van elkaar. Let wel dat het tekenen enkel mag gebeuren als het diagram correct werd gerenderd – de elementen op de juiste plaats werden gezet – en er nadien geen andere wijzigingen gebeurden. Mede door het cachen van de posities (zie onder) zou tekenen na diagramwijzigingen en zonder renderen vooraf tot onverwachtse resultaten leiden.
3.2.7.1 Positie caching Een element grafisch selecteren uit een diagram gebeurt per niveau in de boom, waarbij de kinderen van de wortel worden onderzocht wanneer er nog niets werd geselecteerd. Is dit wel het geval, dan wordt gezocht in de kinderen van het geselecteerde element. Wordt er een geldig element gevonden, dan wordt het geselecteerd. Zoniet wordt de huidige selectie teniet gedaan. Bij dat onderzoek wordt een klikpositie vergeleken met het gebied die een knoop met zijn kinderen samen inneemt. De vraag is nu, hoe kennen we deze oppervlakte? Het spreekt voor zich dat deze controle zo efficiënt mogelijk moet gebeuren, gezien selecteren door klikken een bijzonder frequente operatie is. Om dit te realiseren wordt voor elk element afzonderlijk het gebied op het canvas bepaald. Dit gebied wordt 24
Steven De Groote
Diagrameditor met layoutoptimalisatie
onmiddellijk daarna tijdelijk opgeslagen – gecachet – met absolute coördinaten. Wanneer er geklikt wordt om te selecteren kan dan het klikpunt vergeleken worden met de opgeslagen oppervlakte. Een knoop kan dan zelf het gebied bepalen dat hij omvat samen met zijn kinderen door zijn gebied samen te voegen met dat van al zijn kinderen. De berekening van deze gebieden en het tijdelijk opslaan ervan gebeurt tijdens het renderen van de diagramelementen. Het zou immers nutteloos zijn deze operaties telkens te moeten uitvoeren wanneer er getekend moet worden zonder voorafgaande diagramwijzigingen.
3.2.7.2 Afhankelijkheden tussen verbindingen In een klassieke voorstelling van een graaf is een verbinding een relatie tussen twee onafhankelijke knopen. Diagrammen leggen echter minder beperkingen op voor de verbindingen, waardoor deze niet altijd onafhankelijke elementen zijn.
Figuur 4 : Takvolgorde
In Figuur 4 is een voorbeelddiagram getekend waaruit blijkt dat de volgorde van berekening wel van belang is. We moeten er immers op letten dat het renderen van tak 1 afgerond is voordat met tak 2 gestart kan worden. Zolang tak 1 niet volledig bepaald is, is de positie van X immers onbepaald en kunnen we onmogelijk beginnen met het berekenen van tak 2.
Figuur 5 : Circulaire afhankelijkheid
Het gaat zelfs nog verder: Figuur 5 toont hoe de gebruiker het diagram zo kan wijzigen dat er circulaire afhankelijkheden kunnen ontstaan binnen het diagram. Het uiteindelijk resultaat zou ertoe leiden dat tak 1 moet getekend worden na tak 3 en tak 3 na tak 2. Maar tak 2 kan zelf nog niet getekend worden gezien eerst tak 1 moet afgewerkt zijn. Het is op deze manier dus niet mogelijk een dergelijk diagram te realiseren.
25
Steven De Groote
Diagrameditor met layoutoptimalisatie
Om deze afhankelijkheden en circulaire problemen in goede banen te leiden, worden de takken van een diagram opgeslagen in een “directed acyclic graph” (DAG)1. In deze SortedEdgeCollection zijn de knopen in de DAG de takken uit het diagram. De DAG verbindingen zijn dan weer de afhankelijkheden tussen de diagramtakken. Op die manier bepaalt de topologische volgorde meteen ook de volgorde waarin de takken kunnen afgehandeld worden. De implementatie van de DAG is als volgt: private HashMap<Edge, LinkedList<Edge>> dag;
Dit houdt een lijst bij van alle diagramtakken – objecten van het type Edge – met daarbij een lijst van de diagramtakken die ervan afhankelijk zijn. Daar intern bij het wijzigen van een tak vaak de tak en zijn afhankelijkheden snel moeten gevonden worden, is een HashMap met O(1) toegangstijd een goede oplossing. Hoewel de iteratiesnelheid door alle takken hierdoor afneemt (evenredig met de capaciteit i.p.v. het aantal elementen) is dit geen bezwaar voor de map. Bij het tekenen (wat frequenter gebeurt dan renderen) wordt immers niet deze structuur gebruikt om alle takken te doorlopen (zie 3.2.8.1. Infinite layering). Wanneer nu een tak aan een andere wordt gekoppeld, controleert de applicatie of er dichtbij een aanknopingspunt op die bestaande tak ligt. Is dit het geval dan wordt de verbinding die gewijzigd wordt daaraan gekoppeld. Zoniet dan wordt op die plaats een aanknopingspunt (EdgePoint) aangemaakt en wordt de gewijzigde tak eraan vastgekoppeld. Na de aanpassingen worden de afhankelijkheden in de DAG gewijzigd. Meteen wordt gecontroleerd op lussen en zal de wijziging niet doorgevoerd worden indien daardoor een lus – en dus ook circulaire afhankelijkheid van diagramtakken – ontstaat. De wijziging in het diagram wordt dan ongedaan gemaakt en de tak zo geplaatst zodat het visueel hetzelfde resultaat weergeeft. Meestal – indien geen ander punt in aanmerking komt – wordt hiervoor in het diagram een nieuw punt aangemaakt op de plaats waar in eerste instantie het aanknopingspunt geplaatst werd. Hoewel hiermee de onderlinge volgorde voor het renderen van de takken volledig bepaald is, kan het renderen van de takken pas gebeuren als alle knopen van het diagram al gepositioneerd zijn. Zowel het beginpunt als het eindpunt van een diagramverbinding moet immers correct gepositioneerd zijn voordat de oppervlakte van de verbinding berekend kan worden. Renderen gebeurt dus eerst voor alle knopen in volgorde zoals ze in de knopenboom gevonden worden voordat de takken in topologische DAG-volgorde worden gepositioneerd.
3.2.8
Tekenen
3.2.8.1 Infinite layering Gezien het grote aantal objecten dat kan voorkomen in een diagram zijn overlappingen tussen enkele elementen niet ondenkbaar. Net zoals in veel andere applicaties wordt 1
“Directed acyclic graph”: Bijzonder type gerichte graaf waarin geen lussen voorkomen. Deze familie wordt veel gebruikt voor projectplanning. De topologische volgorde geeft in dat geval de volgorde van uitvoering van de taken aan. 26
Steven De Groote
Diagrameditor met layoutoptimalisatie
hier voorzien in layering: hiermee kan willekeurig gekozen worden welk element op de voorgrond of in de achtergrond moet afgebeeld worden. Het verschil is echter dat er geen vast aantal lagen zijn waarin de elementen geschikt kunnen worden. In het diagram is volgende structuur opgenomen: private LinkedList elements;
Deze lijst bevat op elk moment alle takken en alle ouderknopen van het diagram. Wanneer nu een element naar voor of achter wordt geschoven, wordt die in de lijst met zijn voorganger of opvolger van plaats verwisseld. Deze lijst bepaalt dus meteen de volgorde waarin de knopen getekend worden. Deze die laatst getekend wordt, lijkt dus altijd bovenaan te liggen. Hoewel deze collectie dus enkel zorgt voor het rangschikken van de ouderknopen en takken, kan elke knoop naar voor of achter in een laag opgeschoven worden. Dat is mogelijk omdat elke knoop afzonderlijk ook zijn kinderen bijhoudt in een “gelinkte lijst”. Als een element – een kindknoop – in die lijst naar voor geschoven wordt zal die kindknoop ook meteen naar de voorgrond komen. Het laatste element in de lijst wordt zo altijd achter zijn broers – kindknopen die dezelfde knoop als ouder hebben – getekend. Het betekent meteen dat een kindknoop altijd vóór zijn ouder zal getekend worden. Nergens in de geanalyseerde diagrammen werd trouwens een voorbeeld gevonden waar dit niet zo is. Als nu een willekeurige knoop helemaal naar voor moet geschoven worden, zal de knoop aan zijn ouder vragen om naar voor geschoven te worden. Die ouder zal dan op zijn beurt aan zijn eigen ouder vragen om naar de voorgrond te komen. Wanneer we na herhaling van dit proces bij de boomwortel aankomen is het werk verricht en staat de knoop in de voorgrond. Dit systeem verloopt uiteraard analoog voor een knoop die helemaal naar de achtergrond moet geschoven worden. Er zijn dus evenveel lagen als elementen waarbij elke laag precies één element met zijn eventuele kinderen bevat.
3.2.8.2 Delegatie Wanneer het diagram op het canvas getekend moet worden, zal dat canvas aan het diagram vragen zich te tekenen. Het diagram doet dit echter niet zelf, maar delegeert dat naar alle kinderen. Zo worden alle ouderknopen en diagramtakken afgelopen om zich te tekenen op het scherm. Hoewel die elementen eerst zichzelf tekenen, zullen zij op hun beurt aan de kinderen vragen om dat daarna ook zelfstandig te doen. Op die manier wordt het hele diagram getekend tijdens een soort wandeling door de structuurboom. Tijdens dit doorlopen wordt een transformatieobject – een instantie van de eerder besproken klasse Transformation (zie ook 3.2.3) – doorgegeven. In een ouderknoop wordt deze transformatie eerst gecombineerd met de transformatie van die knoop. Daarna zal de knoop zichzelf tekenen. Vervolgens worden alle kinderen getekend op basis van de doorgegeven transformatie, zodat hun relatieve positionering absoluut wordt. Telkens als dieper in de boom naar kinderen gegaan wordt, wijzigt dit transformatieobject zodat elk element op de juiste plaats getekend wordt. Als de 27
Steven De Groote
Diagrameditor met layoutoptimalisatie
kinderen getekend zijn en de ouderknoop afgehandeld is wordt de transformatie hersteld naar zijn beginwaarden. Voor een OffsetPoint – het eenvoudigste diagramelement – ziet dat er als volgt uit: public void render(AffineTransform t, Diagram diagram, double zoomFactor) { // Sla de huidige transformatie op AffineTransform tSaved = (AffineTransform)t.clone(); // Combineer de transformaties t = transformation.doAfter(t); // Bereken dit element renderComponent(t, diagram, zoomFactor); // Vraag nu hetzelfde aan de kinderen for (OffsetNode p : coupled) { p.render(t, diagram, zoomFactor); } // Herstel de originele transformatie t = tSaved; }
Er werd gekozen om de render()-functie af te beelden daar deze eenvoudiger is dan draw() en toch dezelfde principes hanteert. Het is duidelijk dat deze werkwijze niet alleen geldt voor knopen maar ook analoog toegepast wordt voor de verbindingen in het diagram. Ze tekenen dus ook zichzelf en vragen dan aan de eventuele kinderen – die alleen aanknopingspunten kunnen zijn – om dat ook te doen. Deze delegatie heeft een aantal belangrijke voordelen. Vooral voor takken biedt dit interessante mogelijkheden die zelfs bij uitbreiding met plugins op een unieke manier behandeld worden. Zoals al vermeld, worden nieuwe vormen van verbindingen gemaakt door een nieuw type EdgePath te maken. Hoewel de vorm van de diagramverbinding door dit pad bepaald wordt, is het de Edge klasse die instaat voor het tekenen van de verbinding zelf. Dat tekenen gebeurt analoog als voor een OffsetPoint door eerst de tak zelf te tekenen en daarna de kinderen – die hier alleen EdgePoint instanties kunnen zijn – te vragen dat ook te doen. De diagramverbinding vraagt dus eigenlijk aan het pad wat getekend moet worden. Daarvoor zijn er een aantal functies in de interface EdgePath ontworpen waarvan de implementatie voor elk type pad verschillend kan zijn (en meestal is). public abstract class ControllableEdgePath implements EdgePath { // Vraag het pad van de tak zoals die op het canvas moet getekend worden public GeneralPath getPath(); // Geef de lijst van controlepunten public LinkedList getControlPoints(); // Geef een pad dat alle extra selectietekens beschrijft. public GeneralPath getSelectionMarks();
28
Steven De Groote
Diagrameditor met layoutoptimalisatie
// Geef de hoek die de tak maakt met de horizontale // op afstand d langs de tak (in procenten) public double getAngleAtDistance(double d); // Geef de hoek met de horizontale aan het takeinde public double getAngleAtTarget(); public double getAngleAtSource(); ... }
De combinatie van de functies zoals voorzien in EdgePath en ControllableEdgePath geven genoeg informatie aan Edge om eender welk mogelijk pad te tekenen. Zo kan een Bézier-curve met controlepunten getekend worden door: •
Edge tekent de lijn van de diagramtak door via getPath() op te vragen waar de
•
Edge tekent de controlepunten om de Bézier-curve te wijzigen door elk punt op het canvas te tekenen dat hij ontvangt van getControlPoints().
•
Controlelijnen zoals een verbinding tussen een controlepunt en een eindpunt worden getekend als getSelectionMarks() iets teruggeeft.
lijn moet komen. Andere uiterlijke instellingen zoals kleur en lijntype worden dan toegepast op dat pad door de Edge klasse zelf.
Het systeem werkt analoog voor andere types van verbindingen. Zo heeft een rechtlijnige verbinding (StraighEdgePath) geen controlepunten of selectietekens. Een gebroken lijn (PolylineEdgePath) heeft dan weer als controlepunten de buigpunten van de verbindingslijn. Controlelijnen zijn hier niet aanwezig. Voorgaande werkwijze heeft als voordeel dat de manier waarop elk van deze punten getekend worden (kleur, lijntype, …) onafhankelijk is van de implementatie van EdgePath. Zo blijft het uitzicht van een diagram uniform en eenvoudiger om te bewerken.
3.2.8.3 Bézier subdivision Hoewel het eenvoudig is om een tak met het midden van een OffsetArea (vormknoop) te laten verbinden, is het niet de bedoeling dat die tak dan ook over dat gebied getekend wordt. Er zijn twee alternatieven om dit te verhinderen. Het eenvoudigste is ervoor te zorgen dat de knoop getekend wordt als de tak al afgehandeld werd. Dit zou betekenen dat er over het andere gebied geschreven wordt. Vermits we echter met layering de gebruiker de kans geven te kiezen welk element er bovenaan ligt, is deze oplossing niet mogelijk. Het tweede en enig mogelijke alternatief is het snijpunt van de tak en de figuur te berekenen. De tak hoeft dan enkel getekend te worden tot in dat berekende snijpunt. Het ligt bovendien niet voor de hand om dan ook de eventuele pijl, die aan die tak is toegewezen, op de juiste plaats en in de juiste richting te tekenen. Bovendien kunnen die figuren eender welke vorm hebben en is het niet mogelijk het snijpunt op eenvoudige manier uit te rekenen. De omtrek kan immers bestaan uit rechte lijnstukken, maar ook uit kwadratische en kubische curven. 29
Steven De Groote
Diagrameditor met layoutoptimalisatie
Om voor deze verschillende geometrische vormen het juiste snijpunt te kunnen berekenen, wordt systematisch rond de figuur gelopen en elk stuk van de omtrek getest op een snijpunt met de tak. Er zijn hierbij 3 soorten segmenten: •
Rechte: In dit geval wordt een snijpunt tussen de twee lijnstukken berekend met een methode beschreven door P. Bourke1 (1989) zodat een minimum aan berekeningen nodig is.
•
Kubische Bézier: Dit is een tweedegraads curve met twee eindpunten en één controlepunt. Door de curve telkens in twee te delen en verder te gaan met het juiste deel kan het snijpunt gevonden worden (zie Figuur 6).
•
Kwadratische Bézier: Een derdegraads curve met twee eindpunten en twee controlepunten. In Java worden bijvoorbeeld cirkels voorgesteld als vier opeenvolgende kwarten, waarbij elk kwart een kwadratische Bézier is. Ook hier wordt subdivisie toegepast (zie Figuur 6).
Figuur 6 : Kubische Bézier (links), kwadratische Bézier (rechts)
Bovenstaande figuren tonen een kubische en een kwadratische Bézier-curve. Om een snijpunt met een dergelijke kromme te bepalen wordt subdivision2 toegepast volgens het algoritme van de Casteljau3: •
Voor de curve wordt eerst een “minimax-box” bepaald. Dit is de kleinst mogelijke rechthoek parallel aan beide coördinaatassen die zowel beide eindpunten als de controlepunten van de curve bevat.
•
Als de lijn de Bézier-curve snijdt dan moet deze op zijn minst ook de gevonden minimax-box snijden. Is dit niet het geval dan is er zeker geen snijpunt met de curve.
1
Paul Bourke: Prof. aan de universiteit van Swinburne, Australië. Doet onderzoek naar 3D opslagformaten, computergrafiek en “computational geometry”.
2
Subdivision: Systematisch verdelen van een probleem. In dit geval delen we een Bézier-curve op in twee gelijke delen, controleren elk deel en gaan dan verder met één van de delen tot een oplossing is gevonden.
3
Paul de Casteljau (1910 - 1999): ingenieur bij Citroen ontwikkelde deze methode voor de berekening van een Bézier-curve. 30
Steven De Groote
Diagrameditor met layoutoptimalisatie
•
Is er echter wel een snijpunt, dan kunnen we de curve opdelen zoals in bovenstaande figuren. Telkens worden de middens van de verbindingslijnen tussen de controlepunten met elkaar verbonden. Voor een kubische Bézier is het midden van deze nieuwe lijn (12-23) onmiddellijk het verdeelpunt voor het linkse en rechtse deel van de curve. Zoals op de figuur duidelijk is, krijgen we voor een kwadratische curve twee lijnen (12-23 en 23-34) waarvan opnieuw de middens met elkaar verbonden worden. Het resultaat is het lijnstuk 123-134 waarvan het midden precies het midden van de curve is. De linkse curve is dan bepaald door 1,12, 123,1234 terwijl het rechtse deel gedefinieerd is met 1234,134,34,4.
•
Elk deel is opnieuw zelf een Bézier-curve van dezelfde orde als de oorspronkelijke. Voor beide delen wordt een minimax-box berekend en getest op snijden met het gegeven lijnstuk. Als één van beide snijdt met dat lijnstuk dan hernemen we het algoritme met dit deel van de curve. Is er echter geen snijpunt met de minimax-boxen dan is er, analoog als hierboven, ook geen snijpunt met de Bézier.
Voorgaande stappen worden herhaald zolang de juiste minimax-box niet kleiner is dan een bepaalde tolerantie. Eens aan deze voorwaarde voldaan is, beschouwen we het midden van deze rechthoek als het snijpunt. In de applicatie wordt deze tolerantie bovendien aangepast aan de zoomfactor1. Wanneer immers de afbeelding verkleind wordt door uitzoomen, is er een kleinere precisie nodig dan bij een ver ingezoomd beeld. Als het diagram afgebeeld wordt op reële grootte, wordt het onderverdelen beëindigd als de oppervlakte van de minimaxbox kleiner is dan 0.75 punten2. Afhankelijk van de zoomfactor kan deze precisie variëren tussen 0.1 en 3. Deze waarden geven voor zoomen tussen 1% en 500% zeer correcte snijpunten. Uiteraard heeft het aanpassen van deze precisie een positieve invloed op de performantie, hoewel het aantal iteraties bij de berekening van het snijpunt beperkt blijft. Gezien de curve steeds gehalveerd wordt, is de performantie O(lg n) waarbij “n” evenredig is met de lengte van de originele curve. Van zodra er een snijpunt gevonden is, wordt de rondgang afgebroken en dit snijpunt als enige punt in acht genomen. In zeldzame gevallen (die met de geïmplementeerde taktypes niet mogelijk zijn) kan een tak de knoop meerdere keren snijden. Ook in dat geval wordt het eerst gevonden punt als hét snijpunt beschouwd. Hoewel dit goed uitvalt voor een rechthoek (voor elke zijde bepalen of er een snijpunt is), is dit voor een cirkel zeker geen optimale oplossing. Voor deze speciale gevallen is het in het framework steeds mogelijk om een snellere implementatie te voorzien in het specifieke OffsetArea type.
1
Zoomfactor: waarde variërend tussen 0.01 en oneindig die een indicatie geeft van de zoom die de gebruiker toepast. Eén komt hierbij overeen met een afbeelding op reële grootte. 2
Beeldpunt: gelijk aan een pixel wanneer er niet vergroot of verkleind wordt. Een punt waarmee grafisch gerekend wordt is gelijk aan pixel/zoomfactor. 31
Steven De Groote
Diagrameditor met layoutoptimalisatie
3.2.9
Selectie
De selectie van een element in een diagram dat opgeslagen is in een boomstructuur vereist wat extra duiding. Om alles centraal in goede banen te leiden is er een Selection klasse gebouwd waarvan er steeds één object bestaat wanneer er een diagram is. Dit object houdt voor elk geselecteerd element een pad bij vanaf de wortel (het diagram zelf) tot en met het geselecteerde element. Een dergelijk diagrampad beschrijft waar het geselecteerde element zich in de diagramboom bevindt. In het pad – een lijst van diagramelementen – staat als eerste telkens een ouderknoop of een diagramverbinding. De volgende elementen in de lijst zijn dan telkens kinderen van het voorgaande element in de lijst. Een geselecteerd element kan zo precies gevonden worden in de boom door de elementen te volgen uit dat pad. Op het einde van de lijst vinden we het geselecteerde diagramelement. public class Selection implements Iterable { private ArrayList selections; ... } public class DiagramPath implements Iterable { private LinkedList path; ... }
Precies omdat de diagramelementen in boomvorm zijn opgeslagen, biedt dit een aantal complicaties voor het aanpassen van de selectie. Wanneer immers een diagramelement geselecteerd wordt, zijn meteen ook zijn kinderen geselecteerd. Als nu een element wordt toegevoegd aan een bestaande selectie, wordt eerst gecontroleerd of een ouder van dat nieuwe element al geselecteerd was. Is dat het geval dan wordt de selectie niet gewijzigd. Alle kinderen van de geselecteerde ouder zijn immers al geselecteerd. In het geval er al een kind van de knoop geselecteerd is, wordt het selectiepad naar dat kind ingekort tot het nieuwe element dat toegevoegd moet worden aan de selectie. In beide gevallen wordt er dus geen extra pad opgeslagen in de selectie. Verder is het nog belangrijk op te merken dat de volgorde van de elementen in een selectie belangrijk is. Vaak wil de gebruiker immers meerdere elementen selecteren. Het eerste daarvan speelt daarbij een speciale rol in de selectie. Zo is het voor de gebruikersinterface (GUI) belangrijk aan te duiden welk element het eerste is omdat aligneren van een knopenreeks in 5.3.1 daarvan gebruik maakt. Het selectieobject biedt bovendien ook nog de mogelijkheid aan andere klassen om ernaar te luisteren zodat zij onmiddellijk verwittigd worden bij een wijziging. Daartoe vuurt een selectieobject een SelectionChangeEvent object af om de luisteraars op de hoogte te houden.
3.2.10 Wijzigingen Net als bij een selectie vuurt een Diagram ook gebeurtenisobjecten af wanneer er een knoop in het diagram wijzigt. Ook bij toevoegen of verwijderen van knopen worden alle geïnteresseerde objecten van de wijzigingen geïnformeerd. In tegenstelling tot een SelectionChangeEvent bevat een DiagramChangeEvent echter wel extra informatie voor de luisterklassen. 32
Steven De Groote
Diagrameditor met layoutoptimalisatie
public class DiagramChangeEvent extends EventObject { // Definitie van de actietypes public enum ActionType { ADD, DELETE, EDIT, NEW }; // Eigenschappen van de gebeurtenis opslaan private ActionType actionType; private DiagramElement diagramElement; ... }
Bovenstaand code-extract toont de belangrijkste delen van een DiagramChangeEvent. Wanneer een luisterklasse dit opvangt, kan die achterhalen welk element er gewijzigd werd en welke actie daarbij werd uitgevoerd. De belangrijkste gebeurtenisobjecten zien er als volgt uit: •
Als een element in het diagram werd toegevoegd is het actietype ActionType.ADD en bevat het afgevuurde DiagramChangeEvent object een referentie naar dat toegevoegde element.
•
Het actietype ActionType.DELETE duidt op het verwijderen van een diagramelement. Hoewel dat element dan losgekoppeld is van het diagram – en dus geen ouder meer heeft – bevat het gebeurtenisobject wel een referentie naar dat element.
•
Voor een wijziging aan een element is het actietype ActionType.EDIT met een referentie naar het gewijzigde element.
•
Wanneer een nieuw diagram geladen wordt, is het actietype van de gebeurtenis ActionType.NEW.
3.2.11 Serialisatie Voor het opslaan van een diagram naar een bestand is het nodig dat objecten kunnen omgezet worden naar binaire code. In Java is dat vrij eenvoudig te implementeren door alle klassen van het framework Serializable te maken. Dit houdt in dat elk object – zowel het diagram als zijn elementen en bijhorende objecten – zichzelf correct kan wegschrijven naar een gegevensstroom en er zich ook terug uit kan opbouwen. Een diagramobject en zijn kinderen bevatten alle informatie nodig om het diagram te tonen en op te bouwen. Het is duidelijk dat dit meteen ook alles (en zelfs meer) bevat als we dit willen wegschrijven naar een bestand. Voor tal van klassen van het framework werden daarom speciale schrijf- en leesfuncties voorzien om het opslaan correct te laten verlopen. Bij de implementatie zijn er echter een aantal onverwachtse problemen opgedoken. Een Point2D bijvoorbeeld, waarmee de offsets van de diagramelementen opgeslagen worden, is standaard niet serialiseerbaar. Verder waren er ook klassen die zowel final als niet Serializable gedeclareerd zijn door Sun1. Een aantal van die problemen worden beschouwd als bug in Java 5. Sommige daarvan (zoals het Point2D probleem) zullen opgelost worden in Java 6. 1
Sun Microsystems Inc werd opgericht in 1982 en creëerde het Java platform rond 1990. 33
Steven De Groote
Diagrameditor met layoutoptimalisatie
Om te vermijden dat we moeten steunen op Java 6 beta, werd voor elk van deze problemen een oplossing ontworpen: •
De standaard Point2D.Double werd uitgebreid door een zelf geschreven Point2D klasse. Dit heeft niet alleen het probleem opgelost, maar laat bovendien toe om vrij eenvoudig in het programma de berekeningen van double naar float om te zetten (Sun Java bug 4263142).
•
De klasse BasicStroke is een klasse waarvan de objecten een lijntype beschrijven. Het spreekt voor zich dat hiervan veel objecten gebruikt worden. Omdat deze klasse niet serialiseerbaar en ook niet uitgebreid kan worden, werd een BasicStrokeSerializer ontwikkeld (Sun Java bug 4305099).
•
Verder is zowat geen enkele klasse uit Java.awt.geom te serialiseren, zodat voor elk type knoop die een vorm heeft (rechthoek, cirkel, afbeelding, tekst) zelf het opslaan en laden afgehandeld moet worden. Hoewel het geen echte Java bug is, vereist het wel extra code voor elke subklasse van OffsetArea.
Het mag ook duidelijk zijn dat de oppervlaktes die voor elk diagramelement berekend worden tijdens het renderen niet worden opgeslagen. Gezien het diagram toch onmiddellijk terug gerenderd wordt bij opening zou dit onnodig veel plaats innemen.
3.2.12 Generatie Een diagram opbouwen kan soms vrij veel werk vragen. Dikwijls wil men echter snel tot een diagram komen zonder daaraan veel werk te moeten verrichten. Dit is bijvoorbeeld nuttig ter demonstratie of om een illustratie aan te maken. Om de gebruiker of een applicatie toe te laten snel een willekeurig diagram op de bouwen werd de groep Generator ontwikkeld. Elke generator genereert een andere diagram en kan met andere parameters ingesteld worden. Er zijn drie verschillende generatoren geïmplementeerd: •
ExampleDiagramGenerator: Een generator bouwt een klein diagram op dat alle
•
LinearDiagramGenerator: Deze generator bouwt dynamisch een graaf met
•
RandomDiagramGenerator: Ook hier wordt een graaf met genummerde knopen
mogelijkheden van het framework demonstreert. Dit diagram is bij elke generatie identiek en werd gebruikt tijdens tests (zie 6.1. Interne programmatesten). genummerde knopen. Alle knopen zijn met elkaar verbonden zodat elke knoop, behalve de eerste en de laatste, verbonden is met twee andere knopen. Men kan bij de start van de generatie het aantal gewenste knopen in het diagram instellen. dynamisch aangemaakt. Hierbij worden zoveel knopen en takken aangemaakt zoals de gebruiker instelt bij het begin van de generatie.
34
Steven De Groote
Diagrameditor met layoutoptimalisatie
Hoewel dit een beperkte lijst is, zijn de mogelijkheden voor generatie onbeperkt. Met behulp van het pluginsysteem kunnen andere generatoren immers eenvoudig toegevoegd worden.
35
Steven De Groote
Diagrameditor met layoutoptimalisatie
4
Front end
4.1
Functionaliteit
4.1.1
Use-Case diagram
Figuur 7 : Use cases voor de GUI
36
Steven De Groote
Diagrameditor met layoutoptimalisatie
4.1.2
Overzicht
Figuur 7 : Use cases voor de GUI geeft een overzicht van de mogelijke acties die de gebruiker kan ondernemen via de grafische interface. Er zijn 4 grote groepen te onderscheiden:
4.1.2.1 Invoer en uitvoer Het spreekt voor zich dat net zoals tekst en afbeeldingen, een gebruiker eveneens zijn diagram wil kunnen opslaan. Diagrammen kunnen daarom worden opgeslagen in binair formaat met de extensie “dgm” (een zelf gekozen nieuw extensie). Hiertoe wordt een diagram weggeschreven zoals het geserialiseerd wordt door het framework. De GUI zorgt hier enkel voor de keuze van bestandsnaam en het eigenlijke opslaan. De serialisatie van de klassen in het framework werd al besproken in 3.2.11. Omdat een diagram ook een grafisch object is ligt het voor de hand dat het kan opgeslagen worden als een afbeelding. Dit kan snel in de user interface met de optie uitvoer in het programmamenu. Het diagram wordt hierbij volledig naar het bestand geschreven zonder overbodige witruimte er rond. Voor deze uitvoer worden bitmap, windows bitmap, jpeg- en png-bestanden ondersteund. De diagramgeneratoren zijn ook onder deze categorie ondergebracht. Ze kunnen immers een nieuw diagram aanmaken op basis van een aantal gebruikersinstellingen. Deze klassen kwamen al aan bod in 3.2.12.
4.1.2.2 Configuratie Uiteraard kan een gebruiker ook een aantal instellingen in het programma wijzigen die voor hem het gebruik vereenvoudigen. Daarmee samenhangend zijn er ook instellingen die het programma voor zichzelf moet bijhouden en het registreren van plugins. De precieze implementatie van deze elementen wordt verder besproken in 4.2.3.3 (Plugins voor uitbreidbaarheid).
4.1.2.3 Bewerken In de groep “bewerken” wordt alles gegroepeerd waarbij de gebruiker iets kan wijzigen. Dat omvat niet alleen wijzigingen in het diagram, maar ook bijvoorbeeld inzoomen of scrollen. De belangrijkste items zijn: •
Toevoegen, verwijderen en bewerken van knopen kan overal waar ze getoond worden. Het verwijderen heeft trouwens tot gevolg dat alle kindknopen en de verbonden takken ook verwijderd worden. Deze acties kunnen uitgevoerd worden via het menu, de Del-toets en het pop-upmenu bij het geselecteerde element.
•
Selecteren van elementen kan op elke plaats in de user interface waar ze getoond worden. Samen met de voorgaande mogelijkheid is dit belangrijk voor de gebruiksvriendelijkheid. Elementen kunnen geselecteerd worden door te klikken (eventueel in combinatie met Ctrl voor meerdere selectie), Ctrl+A om alle elementen te selecteren of door een rechthoek te slepen waarbij elk element dat zich daarin bevindt, geselecteerd zal worden bij het eindigen van de actie. 37
Steven De Groote
Diagrameditor met layoutoptimalisatie
•
In- en uitzoomen kan in het canvas1 om elementen eenvoudiger te kunnen selecteren of bekijken. Waar elk diagramelement zal mee vergroten of verkleinen, zullen controlepunten, controlelijnen en klikgebieden dit niet doen. Anders heeft het zoomen natuurlijk geen eenvoudigere selectie tot gevolg.
•
Individuele elementen kunnen bewerkt worden door de eigenschappen ervan te veranderen in de eigenschappenlijst (property box, zie ook 4.3.7). Daarin worden alle eigenschappen op een gelijkaardige manier getoond.
•
Wijzigen van de laag waarop een element zich bevindt. Ook dit kan op alle plaatsen waar het element getoond wordt. Zo kan een element naar voor, naar achter, helemaal naar de voorgrond of helemaal naar de achtergrond geschoven worden. Dit wordt voorzien door met Action objecten de layering functies van het framework aan te spreken.
4.1.2.4 Lay-out Uiteraard kan de gebruiker manueel de lay-out van het diagram aanpassen door knopen te selecteren en ze vervolgende te verslepen naar een andere plaats in het diagram. Daarnaast kunnen nog de eigenschappen veranderd worden in de eigenschappenlijst. Omdat het ordelijk weergeven van knopen en verbindingen belangrijk is voor een diagram, worden er ook een aantal automatische methodes voorzien. Deze maken het voor de gebruiker eenvoudig om snel een gestructureerd diagram te construeren. Bij dit lay-outen kunnen alle grafische aspecten van het diagram (kleuren, vormen, knoopposities, verbindingstypes, enz.) veranderen. Welke dat zijn, hangt af van de gebruiker. In geen geval wordt de structuur aangepast. Er wordt immers alleen een andere voorstelling voor een diagram gemaakt. De verschillende mogelijkheden en hun implementatie worden besproken in Hoofdstuk 5.
1
Canvas: Grafisch paneel dat het diagram op scherm toont. In het canvas kan gescrolld en ingezoomd worden op het diagram. Een uitgebreide uitleg is te vinden in 4.3.5. 38
Steven De Groote
Diagrameditor met layoutoptimalisatie
4.2
Implementatie
4.2.1
Klassenstructuur
Figuur 8 : Kernklassen van de GUI
Figuur 8 toont een overzicht van de belangrijkste klassen in de gebruikersinterface. Het volledige schema met alle functies en eigenschappen is te vinden in Bijlage II. Het EditorWindow speelt een centrale rol in de lay-out van het programma, daar het het programmavenster opvult. Het omvat de diagramboom (DiagramTreePanel), het canvas (DiagramCanvas) en de eigenschappenlijst (PropertyBox) en zorgt voor interactie tussen de panelen door de mediatorklassen (zie 4.2.2).
4.2.2
Koppeling met mediator
De user interface bestaat uit 3 elementen die samen op hetzelfde diagram en selectie object werken. Het canvas is hiervan het centrale element. Hiermee kan de gebruiker zowel het diagram aanpassen (door verslepen, verwijderen, toevoegen) als een ander element selecteren. Het lijkt dus voor de hand te liggen dat het canvas de andere panelen op de hoogte brengt wanneer het diagram of de selectie wijzigt. 39
Steven De Groote
Diagrameditor met layoutoptimalisatie
Jammer genoeg brengt dat een aantal belangrijke problemen met zich mee. Het zou impliceren dat het canvas het diagram beheert, wat eigenlijk niet helemaal correct is. De eigenlijke beheerder is het EditorWindow object dat de panelen op het scherm toont. Bovendien kan de gebruiker via de andere panelen ook wijzigingen in het diagram aanbrengen. Elk paneel moet op die manier weet hebben van alle andere panelen zodat ze allemaal gesynchroniseerd blijven. Een extra paneel toevoegen aan de gebruikerinterface zou daarom ook wijzigingen vereisen in elk paneel. Het mediator pattern biedt hiertoe een oplossing: het beschrijft een manier voor interactie tussen verschillende componenten – hier de panelen – door middel van een derde object. Om een nauwe onderlinge koppeling tussen de panelen zelf te vermijden, beschouwen we Diagram en Selection als mediatoren. Deze objecten bevatten eigenlijk de data die de grafische panelen op het scherm tonen en wijzigbaar maken.
Figuur 9 : Mediator pattern in de GUI
Zoals uit bovenstaande figuur blijkt, informeren de grafische panelen de mediator(en) van een wijziging. Deze panelen worden in de mediator context aangeduid als “collega’s”. Een mediator informeert dan op zijn beurt zijn collega’s van een wijziging. Wanneer zij daarvan op de hoogte worden gesteld, kunnen ze indien nodig de grafische voorstelling wijzigen om consistent te blijven met het diagram en de selectie. De afzonderlijke panelen, die de voorstelling verzorgen, hoeven niets van elkaar af te weten. Een wijziging in de code van een van de panelen heeft bijgevolg ook geen invloed op een van zijn collega’s.
4.2.3
Configuratie en plugin systeem
Een applicatie bevat meestal een aantal instellingen die het gebruik ervan voor de gebruiker vereenvoudigen en consistent houden. Zo worden zaken opgeslagen als de bestandsnaam van het huidige diagram, gebruikersvoorkeuren voor de user interface, 40
Steven De Groote
Diagrameditor met layoutoptimalisatie
maar ook plugins die de functionaliteit van het programma uitbreiden. We kunnen deze instellingen in 3 groepen opdelen, verschillend in hun scope1: •
Sessie: Dit omvat alle instellingen die slechts bewaard blijven tijdens de uitvoering van het programma. Een voorbeeld hiervan is bijhouden of het huidige diagram gewijzigd werd sinds de laatste keer dat het opgeslagen werd.
•
Gebruiker: De gebruikersinstellingen worden bewaard in een XML bestand (user.xml) zodat ze terug dezelfde waarden aannemen wanneer de applicatie opnieuw wordt opgestart. Zo kan de bestandsnaam van het laatst geopende diagram bijgehouden worden, zodat het snel opnieuw kan geopend worden bij een volgende sessie.
•
Applicatie: Deze worden eveneens opgeslagen in een XML bestand (application.xml) om evidente redenen. Belangrijk hierbij is dat het een aantal klassen beschrijft die gebruikt kunnen worden in het framework. Dit bestand is de kern van het plugin systeem.
Lezen en schrijven van de configuratiebestanden gebeurt met behulp van de JDOM XML parser in plaats van de standaard JAXP. Hoewel het ook lukt, genereert JAXP enkel XML code op één enkele lijn. Vanwege de eenvoud voor het debuggen en de gebruiksvriendelijkheid voor het toevoegen van plugins in een geformatteerd XML bestand wordt JDOM gebruikt.
4.2.3.1 Observable settings Alle voorgaande instellingen, hoewel in verschillende bestanden opgeslagen, worden bijgehouden in één enkel Settings object dat geladen wordt bij de start van de applicatie. Is er echter een bestand niet leesbaar, dan worden de standaard instellingen gebruikt. Elke groep instellingen wordt in dit object bijgehouden als een map waarbij elk element is geïdentificeerd door de naam van de instelling: public class Settings extends Observable implements Serializable { ... // Instellingen voor de applicatie, plugins private HashMap<String, Object> applicationSettings; // Gebruikersinstellingen private HashMap<String, Object> userSettings; // Sessieveriabelen private HashMap<String, Object> sessionSettings; }
Omdat meerdere elementen binnen de front end hun eigenschappen wijzigen afhankelijk van een instelling in de applicatie, werden de instellingen ontworpen volgens het “observer design pattern”. Dit komt erop neer dat Settings het Subject is en andere geïnteresseerde klassen Observer zijn. Wanneer een instelling wordt gewijzigd, zal Settings de luisteraars hiervan op de hoogte brengen zodat zij zichzelf kunnen aanpassen. Elk object dat de instellingen wil observeren, moet zich bijgevolg eerst registreren. Dit sluit meteen aan bij de gecentraliseerde aanpak voor het Settings
1
Scope: toepassingsgebied van de instellingen of variabelen. 41
Steven De Groote
Diagrameditor met layoutoptimalisatie
object en zorgt voor een strikte scheiding tussen de instellingsgegevens en de grafische impact ervan. Er is bovendien gekozen om het Settings object zelf te implementeren en op te slaan naar XML. Hoewel er in Java standaard voorzieningen zijn om applicatie-instellingen op te slaan, is de locatie ervan afhankelijk van het besturingssysteem. Zo zouden deze op een computer met MS Windows opgeslagen worden in het register, zodat het moeilijk zou worden om eenvoudig plugins te registreren.
4.2.3.2 XML configuratiebestanden Om de syntax van de XML bestanden niet afhankelijk te maken van Java versies (dit zou het geval zijn bij gebruik van Java long term bean persistence) werden eigen XML tags uitgewerkt om de plugins en gebruikersinstellingen te beschrijven. Voor zowel application.xml als voor user.xml geldt dat er één settings tag is die een aantal property-tags bevat. Een user.xml kan er bijvoorbeeld zo uit zien: <settings> <property name="confirmOnClose" type="java.lang.Boolean">true <property name="filename">null
Een application.xml is standaard van de vorm: <settings> <property name="diagramGenerators" type="java.util.HashSet"> - diagram.generate.ExampleDiagramGenerator
- diagram.generate.RandomDiagramGenerator
- diagram.generate.LinearDiagramGenerator
... <property name="arrowTypes" type="java.util.HashSet"> - diagram.TriangleArrow
- diagram.NotchedArrow
- diagram.DiamondArrow
De property-tags zijn precies de instellingen die worden opgeslagen in het Settings object. In beide bestanden kunnen zowel samengestelde als enkelvoudige eigenschappen gedefinieerd worden. In voorgaande user.xml zijn zowel confirmOnClose en filename enkelvoudige eigenschappen. Bovenstaande application.xml bevat daarentegen alleen samengestelde eigenschappen. Deze tags bevatten dan op hun beurt meerdere items.
4.2.3.3 Plugins voor uitbreidbaarheid Het diagram framework dat al besproken werd, is zo ontwikkeld dat het mogelijkheden biedt tot extensieve uitbreiding. Om hieraan tegemoet te komen kan het framework eenvoudig uitgebreid worden via het application.xml bestand. Om een plugin te bouwen, is het voldoende om de juiste klasse over te erven en daar zelf een implementatie van de maken. Vervolgens moet deze ingepakt worden in een jar-bestand en in de directory van diagram.jar – het applicatiebestand voor dit 42
Steven De Groote
Diagrameditor met layoutoptimalisatie
programma – geplaatst worden. Omdat een dergelijk plugin-archiefbestand meedere bestanden kan bevatten, kunnen plugins samen in een pakket gestopt worden. Wanneer bijvoorbeeld een nieuw type pijl aangemaakt werd (een uitbreiding van Arrow), is het voldoende in application.xml een extra item toe te voegen in de property arrowTypes. Als dat nieuwe pijltype (bvb. plugin.NewArrow) toegevoegd wordt aan de arrowType eigenschap van voorgaande application.xml dan is het resultaat: <property name="arrowTypes" type="java.util.HashSet"> - diagram.TriangleArrow
- diagram.NotchedArrow
- diagram.DiamondArrow
- plugin.NewArrow
Het toegevoegde item – en zo ook elk bestaand item – bevat dan de volledige naam van de klasse. Wanneer de eerstvolgende keer de applicatie wordt opgestart, zal er een extra keuzemogelijkheid zijn wanneer de gebruiker het pijltype voor een verbinding wil instellen. De front end applicatie ondersteunt plugins van volgende types: •
diagramGenerators: Uitbreidingen op diagram.generate.Generator die een
•
shapeTypes: Uitbreidingen op diagram.OffsetArea waarin een knooptype kan beschreven worden. Gezien deze elementen zelf ook de positie van hun verbindingspunten bepalen, is het heel eenvoudig op deze manier standaard vormen te voorzien. Zo kunnen voor electronische diagrammen een diodeknoop, een led of een transistor1 eenvoudig ontworpen worden met de verbindingspunten precies volgens de voorschriften.
•
edgePathTypes:
•
arrowTypes: Verschillende vormen die zowel aan het begin als aan het einde
diagram kunnen genereren.
Specificaties om het verloop van een verbinding te beschrijven. Voor de hand liggende uitbreidingen zijn verbindingen die orthogonaal2 of volgens een Bézier-curve lopen.
van een verbinding toegewezen kunnen worden. Een voor de hand liggende uitbreiding hier, is een kraaienpootje om een één-op-veel-relatie in een ERD diagram voor te stellen.
Meteen is hiermee duidelijk dat op deze manier uitbreidingen kunnen gemaakt worden zoals electronics.jar, die allerlei plugin klassen bevat om snel een elektronisch schema te kunnen tekenen.
1
Diode, led, transistor: eenvoudige elektronica onderdelen die vaak voorgesteld worden in een diagram.
2
Orthogonale verbinding: Tak in het diagram waarvan elk lijnstuk horizontaal of vertikaal loopt. 43
Steven De Groote
Diagrameditor met layoutoptimalisatie
4.3
User interface
4.3.1
Algemeen
De grafische interface is belangrijk om onmiddellijk de aandacht van de gebruiker te trekken. Als het programma bij de eerste oogopslag als moeilijk of ingewikkeld wordt ervaren, is de kans klein dat die mening nog wordt herzien. Om dat te verhinderen, is de lay-out gestructureerd zoals andere programma’s – zie ook 2.2 Grafisch bewerken – met meerdere panelen.
Figuur 10 : Structuur van de GUI
Zo is bijna overal een eigenschappenbox links onderaan of rechts onderaan het scherm te vinden. Daarom werd deze onder de diagramboom geplaatst. Er is uiteraard aandacht besteed aan de aanpassingsmogelijkheden zodat elk paneel een variabele grootte heeft. Elk paneel past zich bij vergroten of verkleinen van het programmavenster aan zoals men verwacht: het canvas neemt alle ruimte in die niet gebruikt wordt door de panelen met een vaste standaard grootte. Omdat het hier een Java programma betreft, is het mogelijk dat het programma wordt uigevoerd in verschillende lay-outs. Hoewel het normaal wordt uitgevoerd met de standaard Java lay-out (MetalLookAndFeel) zijn, om problemen te vermijden, een paar tests uitgevoerd met andere GUI managers. De belangrijkste problemen die het gebruik van het programma bemoeilijkten werden hierbij opgelost. Een perfecte lay-out voor
44
Steven De Groote
Diagrameditor met layoutoptimalisatie
elke GUI manager is echter onmogelijk vanwege nog een aantal mankementen1 in Java Virtual Machine.
4.3.2
Acties
Omwille van de gebruiksvriendelijkheid kunnen de meeste acties vanaf meerdere knoppen of menu-items uitgevoerd worden. Omdat die uiteraard overal in de interface dezelfde functie bieden, worden elke functie geïmplementeerd als een Action. Zo zijn er in totaal een twintigtal acties ontwikkeld die de gebruiker toelaten het diagram te wijzigen. Een voorbeeld hiervan is een element helemaal naar de voorgrond te plaatsen. Dit kan in het programma uitgevoerd worden via de menubalk, een paar knoppen bij de eigenschappenlijst en een item in het pop-upmenu wanneer op een element rechts geklikt wordt. De meeste van die acties zijn bovendien luisteraars voor wijzigingen in het diagram. Sommige luisteren daarbovenop nog eens naar selectiewijzigingen. Uitlijnen van een reeks knopen kan bijvoorbeeld alleen als er meerdere knopen zijn geselecteerd. De opbouw met behulp van acties laat trouwens toe om bij verdere ontwikkeling een undo-mogelijkheid ervoor te voorzien. In de front end applicatie is daartoe al een aanzet gemaakt. Er moet echter voor elke actie een afzonderlijke edit-klasse aangemaakt worden, wat uiteraard vrij veel werk vergt.
4.3.3
Sneltoetsen en iconen
Samen met de verschillende plaatsen om acties uit te voeren, zijn er bij de meeste ook sneltoetsen en iconen voorzien. Ze maken het gebruik eenvoudiger en de herkenbaarheid groter. De iconen worden bovendien mee in het uitvoerbare diagram.jar ingepakt. Bij de start van het programma worden ze vervolgens in het geheugen uitgepakt zodat ze kunnen afgebeeld worden. De installatie wordt daarmee voor de gebruiker uiteraard vereenvoudigd.
4.3.4
Dynamische menu’s
Eerder werd al besproken dat het framework kan uitgebreid worden met het pluginsysteem door nieuwe klassen te ontwikkelen en te registreren. De grafische interface moet, na toevoegen van deze plugins, dan wel nog de mogelijkheid bieden om gebruik te maken van deze nieuwe functionaliteit. Er zijn verschillende plaatsen in het programma waar dynamische menu-items en selectielijsten nodig zijn:
1
GUI mankementen in Java: perfecte eenvormigheid tussen verschillende lay-outs in Java is een probleem waar de taal al een tijdje mee kampt. Verbeteringen werden geboekt in Java 5 met onder andere een nieuwe lay-out. Een aantal verdere verbeteringen zijn nog in ontwikkeling voor Java 6 of later. 45
Steven De Groote
Diagrameditor met layoutoptimalisatie
•
De keuzelijst boven de eigenschappenlijst laat toe om vormknopen tussen elkaar te converteren. De elementen uit deze lijst zijn dan alle mogelijke knooptypes waarnaar conversie kan worden uitgevoerd. Meer over deze keuzelijst is nog te vinden in 4.3.7.3. Typeconversie.
•
Als de gebruiker een pijltype wil kiezen kan hij in de editor (afgebeeld in Figuur 12 : Wijzigen van takeinde) daarvoor kiezen uit een lijst van beschikbare pijltypes. Ook deze lijst wordt dynamisch geladen.
•
Net als pijlen en vormknopen kunnen generatoren (zie 3.2.12) aan de applicatie worden toegevoegd als een pluginklasse. De generatoren zijn echter bereikbaar via het hoofdmenu in het programma. Er worden hier dus geen lijstitems dynamisch toegevoegd, maar wel menu-items in de groep “genereer diagram”.
Hoewel voor de gebruiker totaal verschillend, is de werking van het dynamisch laden gelijkaardig in alle drie de gevallen. Voor de dynamische keuzelijst van typeconversie ziet de implementatie er ongeveer als volgt uit (foutafhandeling en typeconversie werden voor de duidelijkheid weggelaten): // Haal de lijst van mogelijke vormknopen op uit de instellingen Set<String> shapeTypes = Settings.current().getAppSetting("shapeTypes")); // Overloop alle opgehaalde vormknopen for (String type : shapeTypes) { // De vormknoop laden en toevoegen aan de lijst cmbCast.addItem(new ClassListItem(Class.forName(type).getSimpleName(), type)); }
In dit voorbeeld wordt aan korte beschrijving van de klasse opgehaald om het element te omschrijven in de lijst. Waar hier een lijst-item aangemaakt wordt, worden voor de generatoren telkens acties aangemaakt en toegevoegd aan het menu. Telkens worden echter bij de programma-instellingen de items opnieuw opgevraagd en vervolgens dynamisch aangemaakt. Wanneer er echter één van die elementen niet kan geladen worden – om eender welke reden dan ook – wordt het element eenvoudigweg niet toegevoegd in de lijst. Het zal daarmee de verdere werking van het programma niet in het gedrang brengen.
4.3.5
Canvas
4.3.5.1 Functie Het canvas geeft de grafische voorstelling van het diagram weer. Dit is meteen ook de belangrijkste component op de user interface. Het is voorzien van schuifbalken – indien nodig – en een zoomfunctie. Er kan met behulp van het menu, de knoppenbalk en de muis (Ctrl+Scroll) in- of uitgezoomd worden met een minimum van 1% van de originele grootte. Passend in het de structuur met Acties zijn ook hier de meeste zaken ook uitvoerbaar vanuit andere panelen of menu’s.
46
Steven De Groote
Diagrameditor met layoutoptimalisatie
4.3.5.2 Grafische selectie Selecties in het canvas gebeuren steeds met tussenkomst van een DiagramSelector. Dit is een object dat zorg draagt van wijzigingen in de selectie van elementen. Elke functie van de selector geeft na uitvoer een indicatie van de wijziging – de teruggeefwaarde van de functie – terug. Het kan immers dat een actie van de gebruiker geen selectiewijziging tot gevolg heeft. Wanneer rekening gehouden wordt met die teruggeefwaarde kan vermeden worden dat de figuur opnieuw getekend wordt wanneer er niets veranderd is. Door een andere Selector te implementeren, kan een ander selectiegedrag gecreëerd worden. Het huidige gedrag hangt nauw samen met de boomstructuur waarin de elementen zich bevinden. Wanneer we een element proberen te selecteren dat op het tweede niveau onder de diagramwortel zit, moeten we namelijk twee keer klikken. Per klik wordt immers geprobeerd een niveau dieper in de hiërarchie af te dalen. Hierbij wordt in de kinderen van de geselecteerde knoop gezocht naar een element dat onder de muisklik valt. Dit overlopen is evenredig met het aantal kinderen en stopt als een kind gevonden is. Is dit niet het geval, dan wordt de selectie ongedaan gemaakt. Om de knoop te vinden die onder een punt ligt – de muisklik – , worden in het slechtste geval alle kindknopen van de, op dat moment, geselecteerde knoop overlopen. Indien er geen selectie is op dat moment worden alle knopen op diepte één in de knopenboom doorzocht. Bij dat overlopen, stelt elke knoop zijn samengestelde oppervlakte op – door die van zichzelf en van zijn kinderen samen te voegen – en wordt getest of het zoekpunt binnen die oppervlakte valt. Omwille van de boomstructuur blijft het aantal elementen dat hierbij moet doorzocht worden toch enigszins beperkt. Om meerdere elementen te selecteren, kan de Ctrl-toets gebruikt worden of kan een rechthoek gesleept worden die de te selecteren elementen omvat. Het eerst geselecteerde element blijft trouwens rood aangeduid. Het speelt een belangrijke rol bij het uitlijnen van een aantal knopen (zie 5.3 Eenvoudige lay-outwijzigingen). Indien er meerdere elementen geselecteerd zijn, kunnen zij echter door beperkingen in de Selector slechts kindknopen van dezelfde ouderknoop zijn.
4.3.5.3 Elementen verslepen Een object op het canvas verslepen mag dan wel een voor de hand liggende operatie lijken, toch treden er een paar complicaties op. Een element van plaats verschuiven met de muis is uiteraard eenvoudig wanneer dat een direct kindelement is in het diagram. Door de muisverschuiving te vermenigvuldigen met de zoomfactor krijgen we de reële verschuiving voor de positiecoördinaten van het diagramelement. Het wordt echter gecompliceerder waneer een knoop een kindelement is van een ouderknoop. Die ouderknoop kan immers een vergroting of een rotatie bepalen. Het is duidelijk dat dan de verschuiving voor dat element niet meer correct berekend kan worden door enkel rekening te houden met de zoomfactor. Wanneer voor het ouderelement een draaiing van 90 graden zou gedefinieerd zijn, zou bij een verschuiving naar rechts het geselecteerde kindelement op het canvas naar onder bewegen.
47
Steven De Groote
Diagrameditor met layoutoptimalisatie
De kindknopen zijn echter niet de enige die een eigen behandeling vereisen. Aanknopingspunten langs takken bijvoorbeeld mogen niet zomaar ergens naartoe gesleept worden, maar kunnen slechts bewegen langs de lijn van de diagramtak. Er zijn dan ook nog die takken zelf. Ook deze elementen kunnen versleept worden. Om dat alles in goede banen te leiden is elk DiagramElement voorzien van een move() functie. De implementatie is verschillend voor de drie voorgenoemde gevallen. Voor ouderknopen is het effect van move() trouwens identiek aan het rechtstreeks wijzigen van de coördinaten (de offset in het Transformation object van die knoop). Ten eerste zijn er de knopen die kinderen zijn van andere knopen in het diagram. Om ze op correcte wijze te kunnen verslepen moet er rekening gehouden worden met de rotatie en de vergroting die in de ouder en eventuele grootouders ingesteld zijn. Er wordt voor de actieve knoop – deze die versleept moet worden – een totale transformatie samengesteld uit de transformaties van zijn ouder en grootouders. De waarden waarmee de x- en y-offset van het element moet veranderen, worden als volgt berekend: // Haal de rotatie op van enkel de geselecteerde knoop double beta = transformation.getRotation(); // Roteer het element in de omgekeerde richting transformation.rotate(-beta); // De coordinaten transformeren naar de nieuwe waarde if (alfa != 0 && Math.abs(alfa) != Math.PI) { double x = deltax*Math.cos(alfa) + deltay*Math.sin(alfa); double y = -deltax*Math.sin(alfa) + deltay*Math.cos(alfa); transformation.translate(x/afx.getScaleX(), y/afx.getScaleY()); } else { transformation.translate(deltax/afx.getScaleX(), deltay/afx.getScaleY()); } // Zet de rotatie terug als origineel transformation.rotate(beta);
Voordat een wijziging in de offset wordt opgeslagen, wordt de rotatie van het versleepte element tijdelijk ongedaan gemaakt. Een transformatie wordt namelijk opgeslagen als een 3x3 matrix. Wanneer de rotatie van een element veranderd wordt, wijzigt dit vier getallen in die matrix, waaronder ook de vergroting. Omdat uit een AffineTransform object – een standaard klasse voor transformaties in Java – op geen enkele manier is op te maken welke rotatie er is ingesteld, houdt het zelfgemaakte Transformation dit bij. Door de rotatie tijdelijk ongedaan te maken krijgen we de normale vergroting van het object, zodat met de verschuiving kan begonnen worden. Nadien wordt de rotatie uiteraard hersteld. Ten tweede beschouwen we het verslepen van diagramtakken. Deze elementen zijn uiteraard directe kinderen in het diagram – ze zijn immers de elementen op de eerste laag van de takkenboom – en zijn dus niet onderhevig aan samengestelde transformaties. Het verslepen van een tak resulteert altijd in het verslepen van alle controlepunten en beide eindpunten. De positie van een diagramtak wordt immers volledig bepaald door de plaats van zijn eind- en controlepunten. Ook hierbij is waakzaamheid geboden. Als de gebruiker bijvoorbeeld zowel een diagramtak als één of beide van zijn eindpunten selecteert, dan bestaat het risico dat die eindpunten twee keer verschoven worden – en dus dubbel zo snel zullen verschuiven 48
Steven De Groote
Diagrameditor met layoutoptimalisatie
dan de andere verschoven elementen. Om dat te verhinderen is de collectie selectieelementen niet dezelfde als de sleepelementen. Bij het starten van een sleepactie wordt die laatste groep opgebouwd door dubbels over te slaan. Verder is het nog belangrijk om te vermelden dat, wanneer een eindpunt van een gefixeerde tak versleept wordt, dit meteen resulteert in het meeschuiven van die tak en zijn andere uiteinde. Als laatste zijn er aanknopingspunten aan die diagramtakken. Dit is een ingewikkelde groep omdat deze punten hun transformatie enkel te weten kunnen komen door een berekening uit te voeren op de tak waar ze bijhoren. De move() functie wordt voor EdgePoints daarom als volgt geïmplementeerd: public void move(double deltax, double deltay) { // Bereken de nieuwe positie waar de gebruiker het punt wenst Point2D moveTo = new Point2D(canvasPos.getX()+deltax, canvasPos.getY()+deltay); // De diagramtak berekent dan het punt langs de verbinding daar dichtst bij double fraction = edge.getPath().getDistanceFromSource(moveTo); // Zorg ervoor dat dit langs de tak ligt if (fraction > 1) fraction = 1; else if (fraction < 0) fraction = 0; // Sla de instellingen op this.setDistanceFromSource(fraction); }
Uit voorgaande code blijkt dat het eigenlijk de diagramverbinding is die de nieuwe positie van het aanknopingspunt bepaalt. De positiecoördinaat is een getal dat aanduidt waar, langs de verbinding dat aanknopingspunt zich bevindt (zie ook 3.2.5). Deze manier van werken laat toe om de aanknopingspunten langs het pad van de tak te laten bewegen, onafhankelijk of dit een rechte lijn is, een polyline, een Bézier curve of iets anders.
4.3.6
Diagramboom
De diagramboom geeft een boomstructuur weer van het diagram zoals die ongeveer ook opgeslagen wordt door het framework. Het toont een lijst van de knopen en takken met daaronder hun kinderen. Elk element is zo opgebouwd dat het een icoon krijgt afhankelijk van het elementtype. Om een gelijkaardige functionaliteit te bieden zoals die in het canvas (gezien dat immers slechts een alternatieve voorstelling is), wordt bij rechts klikken hetzelfde popupmenu getoond als in het canvas. Op dezelfde manier kunnen ook elementen verwijderd, geselecteerd en toegevoegd worden. De boomstructuur biedt echter ook functies die niet in de andere panelen kunnen uitgevoerd worden. Een knoop kan in de diagramboom eenvoudig aan een ander element gekoppeld worden. Zo kan een knoop naar een willekeurige andere knoop gesleept worden om deze als kind van de nieuwe ouderknoop te beschouwen. Hiertoe is een DnDJtree ontworpen die het verslepen van knopen toelaat wanneer dit volgens de diagramstructuur mogelijk is. Wijzigingen in deze structuur worden dan onmiddellijk gemeld aan de eerder vermelde mediatoren die de andere panelen op de hoogte brengen.
49
Steven De Groote
Diagrameditor met layoutoptimalisatie
Met behulp van het actietype in een DiagramChangeEvent (zie 3.2.10) kan de boom trouwens snel de wijzigingen in het diagram tonen. Wanneer er een element verwijderd of toegevoegd wordt zal niet de hele boom opnieuw worden opgebouwd – wat zou nodig zijn indien we niet wisten wat voor wijziging er gebeurd is – maar wordt het juiste element onmiddellijk verwijderd of toegevoegd op de juiste plaats in de boom.
4.3.7
Eigenschappenlijst
4.3.7.1 Overzicht De eigenschappenlijst is ontworpen naar de gelijkaardige component in standaard .NET, onder andere aanwezig in Microsoft Visual Studio™. Zoals eerder al vermeld, zijn de diagramelementen in het framework opgebouwd zodat ze de Java Beans richtlijnen volgen. Deze “property box” maakt daar handig gebruik van door, met behulp van introspectie, de eigenschappen van het object op te vragen. Voor elke eigenschap wordt bovendien extra informatie getoond in een veld onder de eigenschappenlijst. Dat veld werd speciaal ontwikkeld voor deze lijst zodat het zijn grootte automatisch aanpast aan de lengte van de uitleg. Het toont de korte beschrijving van de eigenschap die op dat moment in de eigenschappenlijst geselecteerd is of bewerkt wordt. De eigenschappenlijst wordt automatisch aangepast wanneer een ander element in het diagram geselecteerd wordt. De lijst luistert daartoe naar wijzigingen in de selectie en toont onmiddellijk het geselecteerde element. Hierbij worden alle eigenschappen opgevraagd die zichtbaar mogen zijn voor de gebruiker. Zo is voor Transformation (het object dat de rotatie en offset bijhoudt van een OffsetPoint) een BeanInfo gemaakt zodat de “shear”1 eigenschap verborgen wordt en alle publieke eigenschappen voorzien zijn van een korte beschrijving. Als er in het diagram meerdere elementen geselecteerd zijn dan worden enkel de eigenschappen van het eerste element getoond. Er wordt trouwens niet alleen naar selectiewijzigingen gekeken, maar ook naar veranderingen aan de geselecteerde knoop. Zo zal het verslepen van een knoop in het canvas onmiddellijk tot gevolg hebben dat de weergegeven coördinaten van die knoop in de eigenschappenlijst geüpdatet worden. De lijst is daarmee steeds synchroon met de andere panelen in de GUI.
4.3.7.2 Editors voor eigenschappen Hoewel de eigenschappen van een totaal verschillend type kunnen zijn, moeten ze wel getoond kunnen worden in een tabelcel. Voor elk objecttype dat kan voorkomen in de property box als een eigenschap, moet er dus een speciale editor/renderer voorzien worden om die eigenschap op een gebruiksvriendelijke manier te kunnen wijzigen. Standaard wordt er immers een tekstveld gekozen, wat voor objecten onwenselijk is. Het bewerken van de objectwaarde in dit tekstveld resulteert nooit in het wijzigen van
1
Shear: een soort transformatie waarbij één van de coördinaten ongewijzigd blijft en de andere vermenigvuldigd met een arbitraire factor. Shear kan bijvoorbeeld een rechthoek naar een parallellogram transformeren. 50
Steven De Groote
Diagrameditor met layoutoptimalisatie
de eigenschap, gezien eigenlijk de referentie ernaar gewijzigd wordt. Men zou de eigenschap steeds op null instellen. Alle editors zijn ondergebracht in een eigen package gui.editor en zijn allemaal een uitbreiding op AbstractPropertyEditor. Dit zorgt ervoor dat de editors in de “property-box” gelijkaardig kunnen behandeld worden en op eenzelfde manier reageren op gebeurtenissen. Elke “editor” is meteen ook een renderer zodat er geen afzonderlijke klasse nodig is om de eigenschap ook te tonen wanneer deze niet bewerkt wordt. Ze hebben daarom een verschillend uitzicht zoals Figuur 11 aantoont. Hierin zijn de editors getoond voor kleuren, lijntypes, lettertypes en verbindingseinden. In de meeste gevallen kan de waarde onmiddellijk aangepast worden door invulvelden en selectielijsten. Zoniet wordt een scherm getoond aangepast aan die editor.
Figuur 11 : Aangepaste editors
Volgende editors zijn ontworpen om elk eigenschapstype te tonen en het bewerken ervan mogelijk te maken: •
ArrowBoxEditor: Laat toe om het pijltype aan het einde van een tak te
wijzigen. In de tabel zelf wordt een voorbeeld getoond, maar het wijzigen gebeurt met een extra venster, afgebeeld in Figuur 12. Daarin kan geopteerd worden om geen pijl te tonen of een pijl te selecteren uit één van de geregistreerde pijltypes (zie 4.2.3 Configuratie en plugin systeem). Verder kan eender welke vulkleur en contour kleur gekozen worden voor de pijl. Het is belangrijk hierbij op te merken dat er ook voor transparant en “inherited”1 kan gekozen worden. Deze laatste optie stelt de kleur gelijk aan die van de tak waarop de pijl wordt geplaatst.
•
BasicStrokeEditor: Hiermee kan het lijntype van een verbinding veranderd
•
ColorBoxEditor: Toont een selectielijst die speciaal ontwikkeld werd om kleuren te kiezen. De ColorPicker toont een aantal standaard kleuren als
worden. Zowel de dikte als het patroon kunnen gewijzigd worden zonder een extra scherm.
opties, maar geeft ook de mogelijkheid om transparantie te kiezen of zelf een kleur in de stellen uit een kleurenpallet. Deze klasse wordt ook gebruikt door de hoger vermelde ArrowBoxEditor, zij het dan met andere instellingen zodat daar ook “inherited” kan gekozen worden. 1
Inherited: Overerven van een eigenschap zodat die dezelfde waarde krijgt als bij zijn ouder. 51
Steven De Groote
Diagrameditor met layoutoptimalisatie
•
EdgePathEditor: Takken kunnen verschillende paden aannemen om hun twee eindpunten met elkaar te verbinden. Dit pad is echter slechts een eigenschap van de verbinding en kan eenvoudig gewijzigd worden door in deze editor uit de selectielijst een ander padtype te kiezen. Er kan in deze lijst gekozen worden uit alle padtypes die geregistreerd zijn in het plugin systeem van de applicatie.
•
FontBoxEditor: Geeft een voorbeeld van het huidige lettertype in de tabel en kan gewijzigd worden in een nieuw modaal venster zoals afgebeeld in Figuur 13. Er kan hierin gekozen worden uit alle geïnstalleerde lettertypes op het systeem samen met de gebruikelijke instellingen als lettergrootte, cursief en vet.
•
ImagePathEditor: Dit toont het pad naar een afbeelding en laat toe om een
afbeelding te selecteren vanuit het bestandssysteem.
Figuur 12 : Wijzigen van takeinde
Figuur 13 : Wijzigen van lettertype
Verder zijn er ook nog editors voor tekst, getallen (tekstveld met validatie op numerieke invoer), logische waarden (een checkbox met een tekstveld dat de huidige waarde extra aangeeft) en een voor punten (met een x en y positie). Nadat een editor geregistreerd is bij de PropertyEditorManager, een standaard Java klasse, kan deze geladen worden indien het objecttype van de eigenschap gekend is. Een speciale eigenschap van elke OffsetNode is de transformatie. Omdat dit zo frequent voorkomt en zowel de positie als de rotatie bepaalt, wordt dit speciaal behandeld. De eigenschappen hiervan worden namelijk getoond in een subgroep van de “property-box”. Deze constructie is volledig dynamisch en kan eenvoudig uitgebreid worden om ook andere eigenschappen als subgroepen voor te stellen. Om dit te doen is het voldoende in de code de klasse toe te voegen die als groep moet getoond worden. Elke groep wordt bovendien voorzien van een titel – de naam van de eigenschap – en kan samengeklapt worden door de gebruiker.
4.3.7.3 Typeconversie De eigenschappenlijst of “property-box” omvat niet alleen de tabel met eigenschappen van het diagramelement, maar toont ook nog een conversiebox en een paar knoppen 52
Steven De Groote
Diagrameditor met layoutoptimalisatie
waarmee het element naar de voorgrond of achtergrond kan geschoven worden (zie 3.2.8.1). Wanneer het geselecteerde element een knoop is met een oppervlakte kan deze gewijzigd worden naar een ander type vormknoop. Welke conversies er mogelijk zijn, is afhankelijk van de geregistreerde klassen. Zoals hoger al besproken, kunnen nieuwe vormknopen toegevoegd worden door een klasse te registreren in de XML configuratiebestanden (4.2.3). Onmiddellijk wanneer een ander type gekozen is, wordt het diagram aangepast en de andere panelen van de GUI daarover geïnformeerd. Het omzetten van knooptypes wordt afgehandeld door het framework zoals uitgelegd in 3.2.4.2.
53
Steven De Groote
Diagrameditor met layoutoptimalisatie
5
Automatische lay-out
5.1
Overzicht
Om automatisch de lay-out van een diagram te wijzigen, kunnen we twee groepen methodes onderscheiden. Een eerste, de “eenvoudige” lay-outwijzigingen zijn niet-iteratieve methodes die onmiddellijk de nodige wijzigingen doorvoeren. Ze nemen een zeer korte tijd in beslag en vereisen daarom geen berichten voor de gebruiker. Een tweede groep zijn de stapsgewijze of iteratieve algoritmen waarvan de uitvoertijd niet (altijd) op voorhand vast staat. De simulated annealing die hier werd geïmplementeerd – zie de bespreking in 5.4 –, behoort bij deze groep, omdat knopen elk na elkaar verplaatst en geëvalueerd worden. Omdat deze algoritmen dezelfde soort handeling een aantal keer na elkaar uitvoeren, kan het proces een zichtbare wachttijd tot gevolg hebben vooraleer een optimale oplossing is gevonden. Elke layouter1 ontwikkeld voor dit framework kan daarom in een eigen thread lopen. Daartoe zijn een aantal algemene klassen voorzien waar gebruik kan van gemaakt worden bij ontwikkeling van nieuwe layouters. Onder deze hulpobjecten is er een gedeeld controleobject om de synchronisatie tussen verschillende threads – het programma versus de thread van de layouter – te coördineren. Hoewel ook de eenvoudige layouters in een eigen thread kunnen uitgevoerd worden, is dat vooral interessant voor iteratieve processen. Het laat de gebruiker toe om tijdens de berekeningen, eigenschappen van elementen te wijzigen of te zoomen op het canvas.
5.2
Visualisatie van het verloop
De iteraties van een layouter algoritme kunnen op het scherm getoond worden als de gebruiker dat wil. De informatiebalk die zichtbaar is tijdens de loop van het algoritme laat zelfs toe het algoritme te pauzeren of helemaal te stoppen (Figuur 14 : Layouter infobalk). Deze balk verbergt zich bovendien automatisch wanneer het algoritme voltooid is.
Figuur 14 : Layouter infobalk
1
Layouter: Algoritmeklasse die de lay-out van een diagram wijzigt. 54
Steven De Groote
Diagrameditor met layoutoptimalisatie
Ook hier is aandacht besteed aan de user interface naar verschillende platformen toe: de achtergrondkleur en paneelrand worden opgehaald uit GUI instellingen die afhankelijk zijn van het besturingssysteem en de gekozen Java GUI manager. Bij de start van een “langdurig” algoritme wordt telkens de infobalk geregistreerd als LayouterListener. Hierdoor blijft het steeds op de hoogte van wijzigingen die uitgevoerd werden door het layouter algoritme. De LayouterListener kan twee soorten gebeurtenissen opvangen: public interface LayouterListener extends EventListener { public void lay-outChanged(LayouterEvent event); public void lay-outDone(LayouterEvent event); }
Hij wordt bericht bij elke iteratiestap (voor het annealing algoritme in 5.4 is dit telkens wanneer een transitie geaccepteerd wordt) en wanneer het algoritme afgelopen is. Door de thread van het algoritme te synchroniseren met het programma kan, na x aantal iteraties of na verloop van een tijdsinterval (zoals hier geïmplementeerd), de huidige diagramsituatie in het canvas getoond worden. Door de afzonderlijke thread hangt de uitvoeringssnelheid van het algoritme niet af van het tekenen. De berekeningen gaan immers gewoon door, onafhankelijk of het diagram op het scherm getekend wordt of niet.
5.3
Eenvoudige lay-outwijzigingen
5.3.1
Knopenreeks uitlijnen
Het is dikwijls overzichtelijk om knopen die een verband hebben met elkaar – al dan niet door de verbinding met een tak – op een rechte uit te lijnen. Hiertoe kunnen meerdere knopen geselecteerd worden en vervolgens uitgelijnd worden op dezelfde positie als de eerst geselecteerde knoop. Die eerste knoop is steeds de referentie voor uitlijningen en wordt altijd anders aangeduid dan de rest van de selectie. Uitlijnen plaatst alle geselecteerde knopen op een rechte en verandert maximaal één coördinaat van de geselecteerde knopen. Bij horizontaal uitlijnen bijvoorbeeld, blijft de horizontale positie dus onveranderd. De knopen worden dus niet op een raster uitgelijnd. Na uitlijning hebben alle knopen de x-coördinaat (voor horizontaal aligneren) of de y-coördinaat (voor vertikaal aligneren) gemeenschappelijk met de referentieknoop.
5.3.2
Knopen geometrisch positioneren
In tegenstelling tot het uitlijnen van een knopenreeks gaat het hier steeds om alle knopen in een diagram. Het spreekt voor zich dat een diagram in veel gevallen duidelijk is wanneer de knopen volgens een vaste, geometrische structuur zijn gepositioneerd. Dit is niet het geval als takrichtingen en knooptypes van belang zijn voor de structuur van het diagram. In dat laatste geval heeft de gebruiker er baat bij slechts enkele knopen uit te lijnen. In de applicatie zijn er tot dusver twee mogelijkheden om alle knopen geometrisch te positioneren: 55
Steven De Groote
Diagrameditor met layoutoptimalisatie
•
Alle knopen op een cirkel. Hoewel de standaardwaarde berekend wordt aan de hand van het aantal knopen, kan de gebruiker zelf nog de straal van deze cirkel wijzigen.
•
Knopen op een raster plaatsen. Het raster wordt zo berekend dat er ongeveer evenveel rijen als kolommen zijn. Het resulterende diagram bevat dan een raster met knopen die zowel horizontaal als vertikaal even ver van elkaar verwijderd staan. De afstand tussen de knopen wordt daarbij afgeleid uit de gemiddelde oppervlakte die elke knoop inneemt. Deze oppervlaktes worden slechts benaderend bepaald uit de minimax-boxen van de knoopoppervlaktes.
Opnieuw wijzigen deze methodes de lay-out onmiddellijk zonder de structuur van het diagram te wijzigen. Na afloop is het diagram nog steeds hetzelfde, zij het dan met gewijzigde knoopposities. Nadien kunnen die posities nog verbeterd worden door een optimalisatie met annealing uit te voeren.
5.4
Simulated annealing
5.4.1
Methode
Simulated annealing (SA) is een flexibele methode voor het optimaliseren van moeilijke combinatorische problemen. Het is met succes toegepast op een aantal klassieke NP-complete problemen zoals het “travelling salesman” probleem. Pas vrij recent werd ontdekt dat de methode ook bruikbaar was om grafische problemen op te lossen. Het SA algoritme wordt vooral toegepast op problemen die in het algemeen moeilijk of niet efficiënt op te lossen zijn. Wanneer men op een model een kostfunctie kan definiëren, is het ook mogelijk de waarde van die functie iteratief te verminderen. Wanneer deze functie goed gekozen wordt, komen we uiteindelijk bij een goede oplossing. Gebruikelijke iteratieve methodes gaan gelijkaardig te werk. Beginnend bij een initiële kost, bouwt elke iteratie van het algoritme een nieuwe configuratie die geëvalueerd wordt. Wanneer blijkt dat de totale kost van de nieuwe structuur lager is dan de voorgaande, wordt verder gegaan met deze structuur tot er aan een stopvoorwaarde is voldaan. Het probleem hierbij is echter dat deze algoritmes vaak vast komen te zitten in “lokale minima”. Dit komt erop neer dat voor een kleine groep de oplossing optimaal is terwijl dit voor het geheel niet het geval is. Simulated annealing probeert hieraan het hoofd te bieden door ook opwaartse transities1 toe te laten. Het systeem is gebaseerd op natuurlijke kristallisatie wanneer een vloeistof wordt afgekoeld. Door in sommige gevallen configuraties te aanvaarden die een hogere kost hebben dan de voorgaande, kunnen die lokale minima omzeild worden. Wanneer een vloeistof wordt afgekoeld tot onder zijn smeltpunt, daalt de totale energie in die vloeistof. Bij het uitharden komt warmte-energie vrij. Wanneer de vloeistof 1
Opwaartse transitie: Overgang van een configuratie naar een andere, waarbij de nieuwe configuratie slechter is dan de originele. 56
Steven De Groote
Diagrameditor met layoutoptimalisatie
volledig verhard is, hebben de moleculen een lagere energietoestand bereikt en zitten ze dichter bij elkaar. Snelle afkoeling van een zuivere stof heeft een amorfe structuur als resultaat. Wanneer echter voldoende traag afgekoeld wordt, vormt zich een kristallijne structuur die een lagere energie-inhoud heeft dan die stof in amorfe toestand. Het gebrek aan lokale minima wijst op een globale evenwichtssituatie waarbij alle moleculen een minimale energie bezitten. In deze structuur volgt de energie van het model uit de Maxwell-Boltzmann verdeling1:
1
f (E) ≈
E
e kT Hierin is f() de kans dat het systeem de energie E heeft bij een absolute (dus altijd positieve) temperatuur, T, met k de constante van Boltzmann. Omdat dit een exponentiële functie is blijft f() voor eender welke T en E altijd groter dan nul. Metropolis2 bedacht in 1953 een methode om dit te simuleren. Als we voorgaande functie beschouwen in een toestandsovergang van E1 naar E2 dan geeft de waarde e
-
E2- E1 T
de kans weer om die transitie te aanvaarden. Wanneer E2 kleiner is dan E1, wordt deze bijgevolg steeds aanvaard. Is dit niet het geval, dan is het nog steeds mogelijk om de opwaartse transitie te accepteren. Die kans daalt echter naarmate de temperatuur van het systeem daalt. Om simulated annealing goed te laten functioneren, moeten twee naburige toestanden met energie E1 en E2 weinig afwijken van elkaar – naburige toestanden zijn gemakkelijk uit elkaar af te leiden, maar kunnen daarbij wel een groot energieverschil hebben. Verder moet analoog aan de natuurlijke basis, de temperatuur traag dalen om te vermijden dat zich lokale minima vormen waar stappen in volgende iteraties niet meer uit kunnen. De begintemperatuur is ook van belang. Bij een te hoge starttemperatuur worden er onnodig veel iteraties gedaan bij het begin van het proces. Als met een te lage temperatuur wordt gestart, kan er ook niet meer tot een optimale oplossing gekomen worden. De techniek is niet echt snel en vereist behoorlijk wat iteraties en temperatuurstappen vooraleer een goede oplossing gevonden wordt. In alle gevallen convergeert het algoritme naar een optimale oplossing en is het uiteindelijke resultaat daar dicht bij in
1
Maxwell-Boltzmann verdeling: Probabilistische functie die de verdeling beschrijft van energie tussen verschillende maar identieke deeltjes. Het beschrijft het fenomeen dat met zeer kleine kans er deeltjes kunnen voorkomen die een veel hogere energie bezitten dan het gemiddelde. De curve is vlakker bij hogere temperaturen en impliceert een bredere verspreiding van deeltjes met hoge energie.
2
Nicholas Constantine Metropolis was in 1953 medeauteur van een artikel over een techniek die de basis vormde voor het SA algoritme. 57
Steven De Groote
Diagrameditor met layoutoptimalisatie
de buurt. Dit wil zeggen dat nooit kan gegarandeerd worden dat bij afloop van de annealing procedure de allerbeste configuratie werd gevonden. Wanneer we dit toepassen op diagrammen kunnen we de knopen beschouwen als de moleculen in een vloeistof. Afhankelijk van het gewenste resultaat kunnen de knopen en de verbindingen de totale energie van het diagram bepalen. Tijdens de annealing proberen we vervolgens die energie te verlagen door knopen van plaats te wisselen.
5.4.2
Vaste knoopposities
5.4.2.1 Verloop Voor een diagram is het belangrijk dat de gebruiker alle inspraak heeft in de lay-out. Soms kan hij echter geholpen worden door automatische verbeteringen. Volgende methode is een implementatie, gebaseerd op simulated annealing, die probeert de totale lengte van de takken minimaal te maken in het diagram. Bovendien wordt bij dit proces gepoogd de overlappingen in knopen minimaal te houden. Hierbij worden echter de knopen niet afzonderlijk verschoven naar een willekeurige plaats, maar enkel verwisseld met de plaats van een andere knoop. Het resulterende diagram zal daarom nog steeds dezelfde knoopposities hebben zoals de gebruiker dit wenst. Deze implementatie werkt in het bijzonder goed indien knopen op willekeurige afstand van elkaar geplaatst zijn, zodat er een verschil is in taklengte. In deze gevallen wordt meestal met de standaard startinstellingen de meest optimale configuratie gevonden. Andere structuren, zoals bijvoorbeeld wanneer alle knopen op een cirkel liggen, resulteren gegarandeerd in een goede oplossing. Over het algemeen is die oplossing echter minder optimaal dan met willekeurige knoopposities. In elke temperatuurstap – de periode waarin de temperatuur constant blijft – wordt een constant aantal iteraties uitgevoerd. Deze waarde wordt bepaald door het aantal knopen te vermenigvuldigen met een constant getal. Er werd voor deze aanpak gekozen omdat voor grotere diagrammen er overbodig werk wordt gedaan indien dit O(n²) zou zijn. Diagrammen zijn bovendien zo goed als altijd “ijl” waardoor we bij deze beperking geen rekening houden met de verbindingen. Binnen deze iteratie worden telkens twee knopen willekeurig gekozen en vervolgens verwisseld van plaats.
5.4.2.2 Energiefunctie Het belangrijkste is, net zoals bij elk annealing-algoritme de energiefunctie. Om zowel overlappingen te vermijden als de taklengte minimaal te maken moeten beide elementen hun invloed hebben op de waarde van deze functie. De energiefunctie bestaat daarom uit twee termen die samen de totale energie voorstellen van een configuratie van het diagram. De eerste term in deze wiskundige functie geeft een indicatie van de totale taklengte in het diagram. Daartoe worden de kwadraten van die lengtes opgeteld. Deze taklengte vormt de basis voor de optimalisatie. De tweede term zorgt voor een extra kost wanneer er zich overlappende knopen voordoen in het diagram. Tijdens het overlopen van de elementen wordt van elke 58
Steven De Groote
Diagrameditor met layoutoptimalisatie
knoop zijn oppervlakte opgevraagd en gecontroleerd op intersectie met de oppervlakte van alle tot dan toe overlopen knopen. Bij intersectie wordt met een unie-operatie1 de overlapping bepaald. Het resultaat is een willekeurige vorm met als omtrek lijnstukken, kwadratische en/of kubische Bézier-curven (dit zijn de secties van de omtrek). Omdat het inefficiënt is hiervan de oppervlakte te berekenen, wordt eerst een minimax-box van deze vorm bepaald. Een rondgang langs de omtrek van deze overlapping geeft meteen die minimax-box als we voor elke sectie de eigen minimax-box toevoegen aan die van de overlapping. De oppervlakte hiervan wordt vermenigvuldigd met een normaliserende factor en toegevoegd bij de energiefunctie. Afsluitend wordt dan de oppervlakte van de behandelde knoop nog toegevoegd aan de samengestelde knoopoppervlakte – van de tot dan toe overlopen knopen – door samenvoegen van polygonen met behulp van het Weiler-Atherton2 algoritme. Het is duidelijk dat samenvoegen van grote polygonen vrij traag kan zijn. Daarom nemen we ook de oppervlakte van de takken niet op in de samengestelde oppervlakte die gebruikt wordt om overlappingen te testen. Dit heeft als resultaat dat de snelheid aanvaardbaar blijft. Hierdoor wordt in de energiefunctie geen rekening gehouden met takken die over de oppervlakte van een knoop lopen. Experimenten wijzen echter uit dat het streven naar minimale taklengte ervoor zorgt dat deze problemen zelden voorkomen. Opwaartse transitie
Kans op opwaartse transitie
100 90 80 70
-dE=10
60
-dE=20
50
-dE=100
40
-dE=50
30 20 10
0, 89 0, 57
2, 16 1, 38
8, 25 5, 28 3, 38
12 0, 00 76 ,8 0 49 ,1 5 31 ,4 6 20 ,1 3 12 ,8 8
0
Temperatuur
Figuur 15 : Opwaartse transitie
1
Unie-operatie: in deze context een geometrische unie die het gemeenschappelijk deel van twee figuren als resultaat oplevert.
2
Weiler-Atherton algoritme: Algoritme dat kan gebruikt worden om intersectie en unie tussen polygonen te bepalen. Deze polygonen kunnen bovendien gaten bevatten. Dit gebeurt door beide vormen rond te lopen langs hun secties en deze te volgen. De performantie ervan is O(mn) waarbij “m” het aantal omtreksecties is in de ene polygoon, en “n” die in de tweede. Dit algoritme is de standaard implementatie bij intersectie en unie operaties van Area objecten in Java. 59
Steven De Groote
Diagrameditor met layoutoptimalisatie
De energiefunctie vereiste verder een aantal correcties met wegingsfactoren. In het annealing proces moet de kans op een positieve transitie namelijk geleidelijk dalen met de dalende temperatuur. Het verloop van deze kans in dit algoritme is afgebeeld in Figuur 15. Men moet ervoor zorgen dat er bij de begintemperatuur zo goed als geen beperkingen zijn op opwaartse transities, maar dat die kans zeer geleidelijk naar nul moet neigen. Te snelle of te trage daling levert nooit de gewenste resultaten. Tempfactor: Begintemperatuur: Tempfactor 0,8 0,8 0,8 0,8 0,8 0,8 0,8 0,8 0,8 0,8 0,8 0,8 0,8
0,8 120
Temperatuur 120,000 96,000 76,800 61,440 49,152 39,322 31,457 25,166 20,133 16,106 12,885 10,308 8,246
-dE=10 92,00444146 90,10751057 87,79125134 84,97947607 81,59105739 77,54489314 72,76817821 67,208914 60,85322474 53,74703322 46,01962981 37,90346392 29,7405247
Kans op opwaartse transitie (%) -dE=20 -dE=50 84,64817249 65,92406302 81,19363462 59,40253206 77,07303812 52,15022622 72,21511353 44,31698901 66,57100646 36,15869994 60,13210452 28,03922523 52,9520776 20,40363338 45,17038121 13,71306041 37,03114961 8,344839471 28,8874358 4,485103642 21,17806328 2,064028093 14,36672577 0,782338143 8,844988092 0,232671469
-dE=100 43,45982085 35,28660815 27,19646095 19,63995515 13,07451581 7,861981513 4,163082552 1,880480259 0,696363458 0,201161547 0,04260212 0,00612053 0,00054136
Tabel 1 : Kans op opwaartse transitie
Voorgaande tabel toont aan hoe de kans op opwaartse transitie evolueert. Naarmate de temperatuur hoger is, worden ook meer opwaartse transities toegelaten. Welke worden toegelaten is dan weer afhankelijk van het energieverschil, waar een kleine stijging in energie natuurlijk altijd een grotere kans heeft dan een grotere.
5.4.2.3 Startwaarden Simulated annealing is zo breed toepasbaar dat, voor een snelle en goede oplossing, een aantal beginwaarden correct moeten geconfigureerd worden. Een configuratiepaneel, ontwikkeld enkel voor dit algoritme, laat toe om de belangrijkste parameters te wijzigen. De begintemperatuur, de snelheid waarmee deze temperatuur daalt na elke temperatuurstap en het gewicht van overlappingen in de energie kunnen aangepast worden om het resultaat te verbeteren. Voor de belangrijkste, de initiële temperatuur, wordt bovendien een standaard waarde berekend afhankelijk van het diagram. Uit de beginenergie wordt een temperatuur afgeleid om voor elk diagram een goed resultaat te behalen met de standaard instellingen. Bij een tweede methode was deze begintemperatuur afhankelijk van de totale oppervlakte die het diagram inneemt bij het begin van het algoritme en het aantal elementen ervan. Dit bleek echter niet voor alle diagrammen toepasbaar omdat de (toevallige) positie van enkele knopen de oppervlakte van het diagram enorm kunnen vergroten. Het resultaat was dikwijls een te hoge starttemperatuur zodat onnodig werk werd verricht.
60
Steven De Groote
Diagrameditor met layoutoptimalisatie
5.4.2.4 Stopvoorwaarden Tijdens de ontwikkeling van het algoritme werden bovendien een aantal verschillende stopvoorwaarden uitgeprobeerd om het algoritme zo snel mogelijk te laten ophouden maar toch een zo goed mogelijk eindresultaat af te leveren. Een absolute limiet op het aantal stappen bleek geen goede oplossing. Hoewel het toegepast wordt voor een aantal andere implementaties die wel knopen verschuiven is het niet effectief voor dit algoritme. Wanneer de knopen dicht bij elkaar liggen zijn er vaak meer stappen nodig om tot een goede configuratie te komen. Gebruikers die bovendien het algoritme niet kennen, weten niet hoe de waarde in te stellen wanneer zij dat kunnen. Veel beter was het om een minimumtemperatuur vast te leggen. Wanneer onder die temperatuur gegaan wordt, houdt het algoritme op. Tests wezen uit dat de beste resultaten bereikt worden bij 5 tot 10 graden. Verdere iteraties leveren meestal nog weinig op. Een hogere stoptemperatuur is bij iets grotere diagrammen – van 20 en meer knopen – onvoldoende. Voor heel kleine diagrammen blijkt trouwens dat na één enkele stap de beste oplossing al is gevonden. Omdat binnen een temperatuurstap een constant aantal iteraties worden uitgevoerd, is de kans immers groter dat de optimale configuratie snel wordt gevonden. Twee maatregelen die zorgen voor een vroegtijdig einde van het algoritme beperken overbodige operaties in het geval snel een optimale oplossing gevonden werd. Vooreerst wordt het aantal achtereenvolgende geweigerde transities bijgehouden. Wanneer dit een vooraf ingestelde – door tests bepaalde – waarde bereikt, wordt de lopende iteratie beëindigd. Bovendien wordt, wanneer twee achtereenvolgende temperatuurstappen geen geaccepteerde transities opleveren, de verwerking stopgezet en de toestand als optimaal beschouwd.
61
Steven De Groote
Diagrameditor met layoutoptimalisatie
6
Tests
De tests van de diagram applicatie zijn te verdelen in twee grote fases. Ten eerste werden continu tijdens de ontwikkeling van het programma tests uitgevoerd. In de volgende fase werd het programma naar een tiental andere mensen gestuurd met de vraag om het programma uit te proberen.
6.1
Interne programmatesten
6.1.1
Functionaliteit
Om het testen vlot te laten verlopen en snel tekortkomingen op te sporen, werd van bij het begin van de ontwikkeling een diagram in code geprogrammeerd om ermee te testen. Naargelang de ontwikkeling vorderde werden elementen toegevoegd aan dit diagram om alle nieuw geschreven functies te kunnen evalueren. Hierbij horen ook het tests van de lay-out op verschillende platformen met verscheidene GUI managers. Java laat toe die zelf in te stellen. Om maximale compatibiliteit te verzekeren was het soms nodig een aantal esthetische veranderingen aan te brengen zodat het programma gebruiksvriendelijk is op elk platform. Gedurende de uitvoering van deze tests werden alle problemen bijgehouden in een buglist (bijlage VI). Deze buglist bevat niet alleen problemen, maar ook nieuwe zaken die moesten geïmplementeerd worden, wijzigingen in de user interface,… Kortom alles wat er nog te doen was na de eerste fase van implementatie werd hierin samengevat om uiteindelijk tot een goed resultaat te komen.
6.1.2
Automatische lay-out
Naast deze tests werden voor de automatische lay-out uitgebreide tests uitgevoerd met heel verschillende diagrammen. Op basis hiervan werd het annealing algoritme bijgesteld om de kans op positieve transitie traag te laten dalen. Ook de stopvoorwaarden werden bepaald door uitvoerige tests. Diagrammen die daarvoor gebruikt werden, zijn door een generator aangemaakt en bevatten 5 tot 100 knopen. Telkens werd voor hetzelfde diagram de optimalisatie opnieuw uitgevoerd nadat de knopen op een cirkel geplaatst werden. De optimalisatie door middel van het annealing algoritme werd talrijke malen heruitgevoerd op verschillende willekeurig gegenereerde diagrammen. Bij elke uitvoering werden statistieken bijgehouden waardoor het algoritme verder kon geoptimaliseerd worden. Deze tests tonen aan dat het algoritme niet steeds dezelfde oplossing geeft. Een herhaalde uitvoering levert vaak betere, maar in sommige gevallen ook slechtere resultaten op.
62
Steven De Groote
Diagrameditor met layoutoptimalisatie
6.1.3
Performantie
Na de belangrijkste ontwikkelingen werd verder nog gekeken of de performantie niet verbeterd kon worden. Met behulp van tijdsopnames gedurende een aantal frequent uitgevoerde operaties konden de tijdskritische elementen in het programma verbeterd worden. De twee belangrijkste verbeteringen zijn: •
Updates in de eigenschappenlijst namen relatief veel tijd in beslag. Tijdens het slepen van een knoop worden de coördinaten immers onmiddellijk ook veranderd in de eigenschappenlijst. Omdat telkens opnieuw de eigenschappen ophalen vrij traag is, worden de editors opgeslagen in een lijst en bijgehouden zolang de selectie niet verandert. Het verslepen van knopen is daarmee zichtbaar sneller geworden.
•
Door die tijdsopnames werd ook ontdekt dat renderen van het hele diagram ongeveer 5 keer langer in beslag neemt dan het tekenen ervan. Om de annealing een stuk sneller te laten werken werden render opties gemaakt in het diagram, zodat slechts een aantal gespecifieerde elementen opnieuw gepositioneerd worden. Na elke wissel van knopen in de iteraties worden daarom enkel beide knopen en de takken opnieuw berekend. Van die takken weten we immers niet welke gewijzigd zijn, en is het niet duidelijk welke afhankelijk is van een andere tak. Optimalisaties die voordien 15 minuten duurden zijn dan na iets meer dan 3 minuten afgerond.
6.2
Externe acceptatietesten
Hoewel vanaf begin december reeds regelmatig aan anderen gevraagd werd zaken te testen, zijn de externe testen vooral uitgevoerd in een fase waarbij naar een tiental mensen een testprogramma gestuurd werd. De testers waren niet alleen mede studenten, maar ook leken. Een gebruiksvriendelijk programma moet immers voor iedereen duidelijk zijn. De opgave voor die personen was eenvoudig. Ze werden gevraagd een diagram te tekenen gelijkaardig aan een stamboom. Het resultaat dat daarbij bekomen werd, was echter bijkomstig. Omdat het programma toen nog niet volledig afgewerkt was, werden dikwijls dezelfde ergernissen geuit. Tijdens deze testronde zijn een 20-tal bugs gemeld en uitbreidingen aangevraagd. Het overgrote deel van de meldingen werden geïmplementeerd of opgelost. Andere nog openstaande problemen (vooral uitbreidingen) zijn opgenomen in de buglist, te vinden in Bijlage VI. Net zoals bij de interne werden bij de externe tests statistieken bijgehouden van het annealing algoritme. De standaard uitvoer en foutmeldingen werden daarvoor omgeleid naar bestanden en later opgevraagd om de werking van het algoritme te verduidelijken en eventueel te verbeteren.
63
Steven De Groote
Diagrameditor met layoutoptimalisatie
7
Algemeen besluit
De keuze voor Java is de juiste gebleken. Het platform in versie 5 biedt belangrijke snelheidsvoordelen die in het bijzonder goed tot uiting komen in dit programma. Helaas is in Java geen standaard eigenschappenlijst (property box) beschikbaar zoals die er wel is in .NET. Verder zijn een aantal vrij eenvoudige klassen niet om te zetten naar een binaire string zodat het opslaan en laden van diagrammen bemoeilijkt werd. Enkele van deze tekortkomingen worden opgelost in de aanstaande release van Java, versie 6. Gezien die nieuwe versie echter op het moment van schrijven in beta fase zit, werd besloten om gebruik te blijven maken van versie 5. Nieuwe Java versies staan namelijk niet altijd bekend om hun stabiliteit, waar Java 5 al een goed ontwikkeld product is. De grafische interface werd zo ontwikkeld om gebruiksvriendelijk te zijn. Deze thesis was niet alleen een verkenning van een groep technieken en algoritmen, maar is tevens een aanzet om andere tekenprogramma’s voor diagrammen te overtreffen. Zo is er veel aandacht besteed aan toetsencombinaties in zowel menu’s als sneltoetsen in de andere panelen. Het spreekt voor zich dat er altijd ruimte is voor verbetering. Software is immers nooit af. Eén van die mogelijke verbeteringen is een mechanisme te ontwikkelen dat bij een muisklik efficiënter het dichtste punt bij die klik kan vinden. Hoewel met de boomstructuur het lineair doorlopen van de elementen in de meeste diagrammen geen probleem is, zijn er snellere methoden om dit te realiseren. Voor de bruikbaarheid van een grafisch programma is het nuttig om acties ongedaan te kunnen maken. Hoewel al heel wat voorbereidingen zijn getroffen moet voor elk type actie een speciale undo1 mogelijkheid gemaakt worden. De GUI voorziet echter wel al in een datastructuur voor het opslaan van die acties, samen met knoppen om echt ongedaan te maken of opnieuw uit te voeren. Het huidige programma is niet in staat iets ongedaan te maken zonder verdere ontwikkeling. Tenslotte wil ik nog opmerken dat deze applicatie ontwikkeld werd als basis voor een zeer uitgebreid diagram programma. Het kan al gebruikt worden om zo goed als elk diagram te ontwikkelen en bevat in de user interface belangrijke panelen – zoals de diagramboom en eigenschappenlijst – opdat met een eenvoudige GUI een geavanceerd diagram kan getekend worden. Een terugblik op dit project wijst uit dat aan de belangrijkste doelstellingen voldaan is. Ten eerste werd het breed toepasbaar framework volledig geïmplementeerd. Tot nu toe heb ik tijdens de ontwikkeling en vooraf in de analyse geen enkel diagram gezien dat niet kan opgeslagen worden met dit framework. De gebruiker wordt daar dus op geen enkele manier beperkt.
1
Undo: functie waarbij een vorige actie ongedaan wordt gemaakt. 64
Steven De Groote
Diagrameditor met layoutoptimalisatie
Ten tweede werd de front end ontwikkeld die gebruik maakt van dit framework. Het laat de gebruiker toe om alle mogelijke functies van het framework te benutten. In tegenstelling tot andere commerciële editors geeft het de gebruiker steeds een overzicht in boomvorm en – dit werd in geen enkel ander diagramprogramma gevonden – toont het voor het geselecteerde element alle beschikbare eigenschappen. Om echt snel een diagram te tekenen is er nog wat meer ontwikkeling nodig. Zo kan bijvoorbeeld een orthogonale verbinding, of het toepassen van eigenschappen op meerdere elementen tegelijk handig zijn. Verder werden nog een aantal belangrijke uitbreidingen geïmplementeerd. Elk diagram kan immers eenvoudig worden opgeslagen als een diagrambestand en uitgevoerd worden naar een afbeelding in vier verschillende bestandsformaten. De grootste uitbreiding is echter de lay-out geworden. Elke afzonderlijke functie die helpt voor de lay-out van het diagram is een nuttige voor de gebruiker, daar het zijn werk versnelt. Het annealing proces is daarvan het meeste geavanceerde. Er is bovendien voor gezorgd dat extra methodes eenvoudig kunnen toegevoegd worden om de lay-out van een diagram nog meer specifiek te verbeteren. Uiteindelijk blijkt dat de uitgebreide analyse en vele verschillende versies van klassendiagrammen geleid hebben tot een framework dat geen echte functionele tekortkomingen heeft. Het kan uiteraard uitgebreid worden om meer mogelijkheden te bieden, maar beperkt geenszins de functionaliteit van die uitbreidingen.
65
Steven De Groote
Diagrameditor met layoutoptimalisatie
8
Referentielijst
8.1
Boeken
Di Battista e. a. , (1999), Graph Drawing - Algorithms for the visualisation of graphs, Prentice Hall. Cooper, J. W. , (2000), Design Patterns - Java Companion, Addison Wesley. Oaks, S. en Wong, H. , (1999) , Java Threads, 2de editie, O’Reilly. Stevens, P. en Pooley, R. , (2000), Toepassing van UML - Software engineering met objecten en componenten, Nederlandse vertaling door Academic Service, Harlow Essex, Pearson Education Limited.
8.2
Electronische bronnen
Barsky, B. A. , (1985), Arbitrary subdivision of Bézier-curves, internet, Berkely, University of California, internet, nr. UCB/CSD 86/265. Bourke P. , Intersection point of two lines (2 dimensions) [WWW] http://astronomy.swin.edu.au/~pbourke/geometry/lineline2d/ Davidson, R. , Harel, D. , (1996), Drawing graphs nicely with simulated annealing, internet, ACM transactions on Graphics, Weizman institute of Science, vol. 15, nr. 4, p. 301. Flanagan, D. en McLaughlin, B. ,(2004), Java 1.5 Tiger - A Developer’s Notebook, internet, eerste druk, O’Reilly. How to write doc comments for the Javadoc tool, Java Tutorial [WWW] http://java.sun.com/j2se/javadoc/writingdoccomments/
Kickpatrick, S., Gelatt Jr., C. D. en Vecchi, M. P., (1983), Optimisation by simulated annealing, internet, Science, volume 220, p. 671. Lay-out components with a spring container, Java Tutorial [WWW] http://java.sun.com/docs/books/tutorial/uiswing/lay-out/example-1dot4/
Stern, Jeffrey A. , (1995), A Simulated Annealing Algorithm for Combinatorica Graphs in Mathematica, internet, Irvine, University of California. The energy distribution function [WWW] http://hyperphysics.phy-astr.gsu.edu/hbase/quantum/disfcn.html
66
Steven De Groote
Diagrameditor met layoutoptimalisatie
Bijlage I Diagrammen uit de analyse Een aantal willekeurige diagrammen werden geanalyseerd om de eigenschappen van diagrammen en hun verschillen ten opzichte van grafen duidelijk te kunnen bepalen. Volgende lijst is niet volledig (in totaal werden er meer dan 70 diagrammen bekeken en vergeleken) maar bevat wel de belangrijkste en meest verschillende: •
Diagram 1 : Schema van de werking van SDRAM http://kelp.or.kr/korweblog/upload/30/20041215095917/SDRAM-diagram.jpg
•
Diagram 2 : Menselijke cel interactie http://celldesigner.org/documents/images/Fig%208%20Process%20Diagram%2 0NF-kappaB%20ver.1.11.png
•
Diagram 3: Elektronische bedrading http://www.aoruk.com/images/7030blk.gif
•
Diagram 4: UML2 diagram van universiteitssysteem http://www.agilemodeling.com/images/models/componentDiagramUML2.jpg
•
Diagram 5: Pentium 2 Structured computer organisation, 4th ed, Andrew S. Tanenbaum
•
Diagram 6: Busarchitectuur Structured computer organisation, 4th ed, Andrew S. Tanenbaum
•
Diagram 7: Pipelining Structured computer organisation, 4th ed, Andrew S. Tanenbaum
•
Diagram 8: Simultane verwerking van processen Structured computer organisation, 4th ed, Andrew S. Tanenbaum
•
Diagram 9: Relaties tussen Shell objecten http://www.conceptdraw.com/products/img/ScreenShots/cd5/uml/CDBasicObje ctsScheme.gif
•
Diagram 10: boom van klassen en afgeleide klassen uit een Java programma
•
Diagram 11: infoset klassen http://www.w3.org/2000/10/swap/infoset/infoset-diagram.png
•
Diagram 12: Voorbeeld van esthetische lay-out http://vlado.fmf.uni-lj.si/pub/gd/01/afmain2.png
67
Steven De Groote
Diagrameditor met layoutoptimalisatie
Diagram 1
Diagram 2
68
Steven De Groote
Diagrameditor met layoutoptimalisatie
Diagram 3
Diagram 4
69
Steven De Groote
Diagrameditor met layoutoptimalisatie
Diagram 5
Diagram 6
70
Steven De Groote
Diagrameditor met layoutoptimalisatie
Diagram 7
Diagram 8
71
Steven De Groote
Diagrameditor met layoutoptimalisatie
Diagram 9
72
Steven De Groote
Diagrameditor met layoutoptimalisatie
Diagram 10
Diagram 11
Diagram 12
73
Steven De Groote
Diagrameditor met layoutoptimalisatie
Bijlage II Klassendiagrammen Op de volgende pagina’s is een overzicht van de klassen in diagram en GUI te vinden. Het eerste beschrijft het framework en in het package “gui” bevinden zich de belangrijkste klassen voor de gebruikersinterface. De andere packages zijn niet opgenomen daar zij vooral een hulp zijn voor beide afgebeelde packages. De twee schema’s tonen de klassen met hun relaties en de eigenschappen ervan. Operaties en subklassen van elke klasse zijn niet afgebeeld gezien het onmogelijk is om dit leesbaar af te drukken. Voor een volledige lijst van de methodes en hun functies verwijzen we naar bijgevoegde CD-ROM. Daarop is onder andere de broncode en een volledige API te vinden van alle geïmplementeerde klassen.
74
Steven De Groote
Diagrameditor met layoutoptimalisatie
75
Steven De Groote
Diagrameditor met layoutoptimalisatie
76
Steven De Groote
Diagrameditor met layoutoptimalisatie
Bijlage III Inhoud cd-rom De inhoud van de bijgevoegde cd-rom is als volgt gestructureerd:
Waarbij de test directory alles bevat met betrekking tot het testprogramma, en diagram alles over de diagram editor. De submappen hebben volgende inhoud: •
api: bevat een javadoc voor het betreffende programma.
•
bin: uitvoerbare bestanden en een korte uitleg hoe deze geïnstalleerd moeten worden.
•
src: de volledige broncode van de applicatie.
In de hoofdmap is verder nog een digitale versie van dit document te vinden, de poster die gebruikt werd tijdens de postersessie en het thesisvoorstel.
77
Steven De Groote
Diagrameditor met layoutoptimalisatie
Bijlage IV Codestructuur Alle pakketten in de code werden op een logische manier opgebouwd met een duidelijke scheiding tussen het framework deel en de front end. Volgende pagina illustreert de beknopte structuur waarbij de inhoud van deelpakketten niet wordt getoond. Volgende zijn de belangrijkste onderdelen in de structuur: •
Diagram: omvat alle code die het framework definieert en implementeert. o Event: Klassen met betrekking tot selectie en diagram gebeurtenissen o Generate: De diagramgeneratoren o Lay-out: Algoritmeklassen die zorgen voor wijzigingen in het uitzicht van een diagram. Hieronder zitten onder andere de annealing layouter en klassen voor knooppositionering.
•
Geom: Klassen nodig om een geometrische structuur zoals een diagram te beschrijven en te bewerken.
•
Gui: Geheel aan front end voorzieningen. o Action: Actie klassen om vanuit de grafische user interface het framework te wijzigen. o Edit: Elke klasse in dit package beschrijft een bepaalde bewerking. Instanties van een van deze klassen bevatten informatie voor het ongedaan maken van een actie. o Editor: Panelen gebruikt in de property box. Elke klasse is een editor die kan gebruikt worden om een object van een specifiek datatype te wijzigen. o Lay-out: Grafische panelen om een layouter te configureren. Een klasse hieruit staat meestal in rechtstreeks verband met een klasse uit diagram.lay-out.
•
Io: Elke klasse – exclusief abstracte klassen en interfaces – hierin beschrijft de invoer of uitvoer van een diagram van en naar een bestandstype.
•
Util: Hulpklassen die voor elke gui implementatie nuttig kunnen zijn.
78
Steven De Groote
Diagrameditor met layoutoptimalisatie
79
Steven De Groote
Diagrameditor met layoutoptimalisatie
Bijlage V Testinformatie van annealing Op volgende pagina’s is een extract te vinden uit de uitvoer die opgeslagen werd tijdens tests van het annealing proces. In totaal werden ongeveer 70 optimalisaties uitgevoerd – zowel voor en nadat een aantal wijzigingen werden aangebracht – op verschillende diagrammen in de periode dat de uitvoer opgeslagen werd. Het spreekt voor zich dat het niet mogelijk of nuttig zou zijn alles hier onder te brengen. Er is daarom slechts een klein deel afgeprint om een idee te geven over de testgegevens waarmee gewerkt werd. Een nadere kijk op de bijgevoegde data maakt duidelijk dat het aantal positieve transities – in de data aangeduid als “boltzmannaccepts” – langzaam daalt naarmate het algoritme vordert. Het is namelijk op die manier dat de beste resultaten bekomen worden. Met deze gegevens was het mogelijk om het algoritme in de meeste gevallen sneller uitgevoerd te krijgen. Er werd daarbij wel vooropgesteld dat het eindresultaat daar niet onder te lijden had. Na de verbeteringen aan de standaard begintemperatuur, de iteraties in elke temperatuurstap en de stopvoorwaarden is het proces gemiddeld 15% sneller geworden.
80
Steven De Groote
Diagrameditor met layoutoptimalisatie
Area: 80 - 1341 ++----++--Starting fixedannealinglayouter Calculated best starting temp: 81.74204288524213 Starting temp: 81.0 Initial energy: 48937 , Nodes: 80 , Edges: 79 Number of accepts: 210 with boltzmanaccepts: 61 (with average dE = -1850) Number of rejects: 5 Number of accepts: 117 with boltzmanaccepts: 50 (with average dE = -2009) Number of rejects: 22 Number of accepts: 86 with boltzmanaccepts: 38 (with average dE = -2065) Number of rejects: 16 Number of accepts: 68 with boltzmanaccepts: 25 (with average dE = -2056) Number of rejects: 10 Number of accepts: 61 with boltzmanaccepts: 28 (with average dE = -2129) Number of rejects: 10 Number of accepts: 53 with boltzmanaccepts: 28 (with average dE = -2132) Number of rejects: 6 Number of accepts: 41 with boltzmanaccepts: 16 (with average dE = -2139) Number of rejects: 33 Number of accepts: 31 with boltzmanaccepts: 13 (with average dE = -2182) Number of rejects: 34 Number of accepts: 23 with boltzmanaccepts: 10 (with average dE = -2176) Number of rejects: 90 Number of accepts: 23 with boltzmanaccepts: 11 (with average dE = -2124) Number of rejects: 125 Number of accepts: 30 with boltzmanaccepts: 11 (with average dE = -2119) Number of rejects: 39 Number of accepts: 16 with boltzmanaccepts: 8 (with average dE = -2202) Number of rejects: 401 Number of accepts: 17 with boltzmanaccepts: 4 (with average dE = -2169) Number of rejects: 42 Number of accepts: 11 with boltzmanaccepts: 7 (with average dE = -2149) Number of rejects: 110 Number of accepts: 15 with boltzmanaccepts: 4 (with average dE = -2256) Number of rejects: 58 ++----++--Finished at temperature: 7.075691747201386 with final energy: 2963 ++----++--Starting fixedannealinglayouter Calculated best starting temp: 53.23518787649966 Starting temp: 53.0 Initial energy: 18413 , Nodes: 80 , Edges: 79 Number of accepts: 142 with boltzmanaccepts: 45 (with average dE = -1886) Number of rejects: 13 Number of accepts: 74 with boltzmanaccepts: 29 (with average dE = -2009) Number of rejects: 41 Number of accepts: 50 with boltzmanaccepts: 17 (with average dE = -2100) Number of rejects: 47 Number of accepts: 42 with boltzmanaccepts: 19 (with average dE = -2188) Number of rejects: 11 Number of accepts: 40 with boltzmanaccepts: 18 (with average dE = -2129) Number of rejects: 39 Area: 16 - 600 ++----++--Starting fixedannealinglayouter Calculated best starting temp: 23.438048235879215 Starting temp: 23.0 Initial energy: 2145 , Nodes: 16 , Edges: 19 Number of accepts: 31 with boltzmanaccepts: 12 (with average dE = -307) Number of rejects: 3 Number of accepts: 14 with boltzmanaccepts: 10 (with average dE = -369) Number of rejects: 20 Number of accepts: 4 with boltzmanaccepts: 3 (with average dE = -344) Number of rejects: 81 Number of accepts: 13 with boltzmanaccepts: 10 (with average dE = -334) Number of rejects: 32 Number of accepts: 3 with boltzmanaccepts: 3 (with average dE = -373) Number of rejects: 81 Number of accepts: 1 with boltzmanaccepts: 1 (with average dE = -371) Number of rejects: 81 Number of accepts: 10 with boltzmanaccepts: 10 (with average dE = -333) Number of rejects: 81 ++----++--Finished at temperature: 7.373273030468749 with final energy: 932 ++----++--Starting fixedannealinglayouter Calculated best starting temp: 17.261629326299868 Starting temp: 17.0 Initial energy: 772 , Nodes: 16 , Edges: 19 Number of accepts: 14 with boltzmanaccepts: 12 (with average dE = -328) Number of rejects: 21
81
Steven De Groote
Diagrameditor met layoutoptimalisatie
Number of accepts: 17 with boltzmanaccepts: 13 (with average dE = -344) Number of rejects: 12 Number of accepts: 22 with boltzmanaccepts: 13 (with average dE = -353) Number of rejects: 9 Number of accepts: 12 with boltzmanaccepts: 8 (with average dE = -348) Number of rejects: 52 ++----++--Finished at temperature: 7.542990312499999 with final energy: 689 ++----++--Starting fixedannealinglayouter Calculated best starting temp: 18.082988974836116 Starting temp: 18.0 Initial energy: 915 , Nodes: 16 , Edges: 19 Number of accepts: 71 with boltzmanaccepts: 43 (with average dE = -95) Number of rejects: 24 Number of accepts: 68 with boltzmanaccepts: 46 (with average dE = -99) Number of rejects: 17 Number of accepts: 25 with boltzmanaccepts: 21 (with average dE = -112) Number of rejects: 5 Number of accepts: 24 with boltzmanaccepts: 19 (with average dE = -116) Number of rejects: 61 Number of accepts: 17 with boltzmanaccepts: 11 (with average dE = -113) Number of rejects: 81 ++----++--Finished at temperature: 7.986695624999999 with final energy: 267 ++----++--Starting fixedannealinglayouter Calculated best starting temp: 17.988882709181134 Starting temp: 17.0 Initial energy: 898 , Nodes: 17 , Edges: 22 Number of accepts: 62 with boltzmanaccepts: 28 (with average dE = -122) Number of rejects: 3 Number of accepts: 43 with boltzmanaccepts: 25 (with average dE = -140) Number of rejects: 5 Number of accepts: 23 with boltzmanaccepts: 14 (with average dE = -140) Number of rejects: 2 Number of accepts: 38 with boltzmanaccepts: 23 (with average dE = -140) Number of rejects: 7 Number of accepts: 36 with boltzmanaccepts: 21 (with average dE = -147) Number of rejects: 20 ++----++--Finished at temperature: 7.542990312499999 with final energy: 363 ++----++--Starting fixedannealinglayouter Calculated best starting temp: 14.350852961085884 Starting temp: 14.0 Initial energy: 403 , Nodes: 17 , Edges: 22 Number of accepts: 33 with boltzmanaccepts: 24 (with average dE = -150) Number of rejects: 7 Number of accepts: 39 with boltzmanaccepts: 24 (with average dE = -129) Number of rejects: 1 Number of accepts: 43 with boltzmanaccepts: 25 (with average dE = -140) Number of rejects: 2 Number of accepts: 35 with boltzmanaccepts: 23 (with average dE = -144) Number of rejects: 23 ++----++--Finished at temperature: 7.308087499999999 with final energy: 412 Area: 40 - 948 ++----++--Starting fixedannealinglayouter Calculated best starting temp: 37.7003554037845 Starting temp: 37.0 Initial energy: 7933 , Nodes: 40 , Edges: 39 Number of accepts: 107 with boltzmanaccepts: 38 (with average dE = -690) Number of rejects: 5 Number of accepts: 62 with boltzmanaccepts: 37 (with average dE = -730) Number of rejects: 2 Number of accepts: 49 with boltzmanaccepts: 19 (with average dE = -819) Number of rejects: 1 Number of accepts: 42 with boltzmanaccepts: 21 (with average dE = -780) Number of rejects: 2 Number of accepts: 25 with boltzmanaccepts: 11 (with average dE = -826) Number of rejects: 4 Number of accepts: 22 with boltzmanaccepts: 11 (with average dE = -864) Number of rejects: 72 Number of accepts: 12 with boltzmanaccepts: 6 (with average dE = -866) Number of rejects: 52 Number of accepts: 1 with boltzmanaccepts: 1 (with average dE = -828) Number of rejects: 201 Number of accepts: 5 with boltzmanaccepts: 1 (with average dE = -852) Number of rejects: 201 Number of accepts: 1 with boltzmanaccepts: 0 (with average dE = -824) Number of rejects: 201 ++----++--Finished at temperature: 7.2843529606067365 with final energy: 1074
82
Steven De Groote
Diagrameditor met layoutoptimalisatie
Bijlage VI Lijst van bugs Volgende lijst zijn bugs die tijdens de ontwikkeling van de applicatie aan het licht zijn gekomen en niet onmiddellijk werden opgelost. Problemen die bij het opmerken direct werden verholpen zijn natuurlijk niet opgenomen in die lijst. Op moment van schrijven zijn bovendien zo goed als alle bekende bugs verholpen. Iconen in programma laden uit JAR
10/11/2005
Gebruiker mag ConnectionPoint niet verslepen
16/02/2006
Splitsen van paint naar render() + paint()
2/12/2005
Verslepen van edgepoint enkel langs edge
30/10/2005
Rendervolgorde van de takken volgens een DAG
23/12/2005
Centraal zoomen onder de muispijl
26/11/2005
Shapeklassen voor uitbreidbaarheid naar oa driehoeken
4/01/2006
Pijlen op takken mee roteren
25/10/2005
Rotatie van knopen rond middelpunt, niet rond hoekpunt
31/12/2005
Klikgebieden niet meeschalen met het zoomen
10/01/2006
Afbeeldingen als knopen
30/11/2005
Refresh probleem bij propertybox
5/01/2006
Selectie in diagramboom ook kinderen van element selecteren
23/12/2005
Layering vanuit de eigenschappenlijst
30/12/2005
Centraal opslaan van programmainstellingen
5/11/2005
Plugins met xml
12/11/2005
Tekstveld indicator voor zooming
30/12/2005
Conversie van verschillende shapes
11/02/2006
Pop-up menu in canvas en diagramboom
7/01/2006
Instellingen Obversable maken volgens observer pattern
5/01/2006
Pijlen, taktypes en vormen als pluggable maken
7/02/2006
Verslepen van gefixeerde edges
12/01/2006
Toevoegen van diagramelementen
8/01/2006
Uitlegveld in eigenschappenlijst toevoegen
26/12/2005
Afbeeldingen als knopen verschaalbaar maken
5/01/2006
Polyline edge met controlepunten
15/02/2006
Selectie niet veranderen bij controlepunt selectie, enkel slepen
15/02/2006
Pijleditor (paneel om pijl te wijzigen voor een tak)
10/01/2006
Nieuwe kleurselectie met voorstellen en eigen selectie
9/01/2006
Toevoegen van elementen op muispositie
8/01/2006
Conversie van verschillende taktypes
10/02/2006
Verslepen van elementen in de diagramboom
12/02/2006
Verslepen van controlepunten van verbindingen
13/02/2006
Samenklappen van groepen in eigenschappenlijst - vernieuwen
15/02/2006
Verslepen van punt gaat schuin voor gedraaide knopen
15/02/2006
Export naar afbeeldingen slaat in slechte bestandsnaam op
5/05/2006
Afbeeldingen naar uitvoer zijn te groot
5/05/2006
83
Steven De Groote