# Het handboek van &rocs;

Tomaz
Canabrava
tomaz.canabrava@gmail.com
Andreas
Cord-Landwehr
cordlandwehr@googlemail.com

&Freek.de.Kruijf;&Jaap.Woldringh;
2009
Tomaz Canabrava
2011-2012
Andreas Cord-Landwehr
2012-12-02
1.8.0 &kde; 4.10
&FDLNotice;

&rocs; is een hulpmiddel van KDE voor de grafentheorie.

KDE
kdeedu
wiskunde
wiskunde
grafen
knoop
kant

## Inleiding

In dit hoofdstuk vindt u een overzicht van de kerneigenschappen en manier van werken met &rocs;. Als u direct wilt beginnen met werken met &rocs; raden we u aan te lezen en te gebruiken als referentie bij het schrijven van algoritmes.

### Doelen, voor wie is dit bestemd en manier van werken.

&rocs; is een IDE (werkomgeving) voor de grafentheorie, te gebruiken door iedereen die algoritmes in de grafentheorie wil ontwerpen en analyseren. Dit houdt expliciet in

- docenten die algoritmes aan hun studenten willen demonstreren,

- studenten die willen begrijpen en zien hoe een algoritme werkt,

- en verder iedereen die belang stelt in gegevensstructuren en algoritmes.

Iedereen kan &rocs; goed gebruiken voor het aanmaken van gegevensstructuren, als een krachtig hulpmiddel voor het maken van scripts voor het uitvoeren van algoritmes, en als hulpmiddel voor het uitvoeren van simulaties en experimenten.

De eerste stap in &rocs; is gewoonlijk een graaf aanmaken in het visuele bewerkingsprogramma voor grafen. U kunt dit met de hand doen, dat wil zeggen gegevenselementen toevoegen en die met elkaar verbinden, of met behulp van een van de hulpalgoritmes (indien aanwezig voor de huidige plugin voor gegevensstructuren), die u vindt in Graafdocument Hulpmiddelen Graaf aanmaken. U kunt verder waarden toekennen aan de elementen van de gegevensstructuren, met de hand, of met Graafdocument Hulpmiddelen Waarden toekennen. Tenslotte kunt u een algoritme schrijven in JavaScript en die met de zojuist aangemaakte gegevensstructuur laten uitvoeren (werken). De door uw algoritme aangebrachte veranderingen zijn dan direct zichtbaar in het visuele bewerkingsprogramma.

Schermbeeld van &rocs;.
Schermbeeld van &rocs;.

### &rocs; in een notendop

In dit deel geven we een kort overzicht van de kernelementen van &rocs;. We leggen de belangrijke begrippen uit van gegevensstructuren, de bijbehorende backends,en typen van elementen. Kennis hiervan is nodig om te kunnen begrijpen hoe in &rocs; gegevensstructuren kunnen worden aangemaakt en gewijzigd.

In het algemeen werkt men in &rocs; met projecten: wanneer &rocs; wordt gestart, wordt een leeg project aangemaakt, dat u kunt vervangen door het inlezen of importeren van een ander project. Hierbij bestaat een project zelf uit graafdocumenten en scripts.

#### Backends voor graafdocumenten en gegevensstructuren

Een graafdocument bevat de inhoud van een whiteboard, in het visuele bewerkingsprogramma voor de graaf. Hierin kan een graafdocument diverse gegevensstructuren tegelijk bevatten, maar slechts één bijbehorende backend. Er zijn backends aanwezig voor voor diverse graaftypen (algemene grafen, gekoppelde lijsten (linked lists), boomstructuren (rooted trees)), die toegevoegde functionaliteit bieden voor hun specifieke graaftypen. Dat kan het automatisch positioneren zijn van de elementen, speciale verzamelingen van pictogrammen (iconsets), of een uitgebreide verzameling van scriptfuncties, die in algoritmes kunnen worden gebruikt. (details vindt u elders in dit handboek). In een graafdocument kunt u een andere backend kiezen voor een gegevensstructuur, maar er kan hierdoor wel informatie verloren gaan (bv. kanten van een cirkel in een algemene graaf worden niet aan een boomstructuur toegevoegd, als u overschakelt naar de backend voor een boomstructuur).

Graafdocumenten vormen ook de basis voor de definitie van pijltypen en gegevenstypen.

#### Gegevensstructuren

Gegevensstructuren vormen de basis van het werken in &rocs;. U kunt er een of meer aan een graafgdocument toevoegen, gegevenselementen toevoegen (knopen, data) en pijlen, en die wijzigen in scripts. Daarom moet elke gegevensstructuur een unieke naam hebben, waarmee die in de scripts kan worden genoemd. Als gevolg van de huidig gekozen backend voor de gegevensstructuren, kan het zijn dat u de gegevensstructuren niet willekeurig kunt wijzigen (bv. een boomstructuur mag nooit een cyclische structuur bevatten). De backend voor gegevensstructuren moet passen bij de gegevensstructuur in het graafdocument.

#### Pijltypen

Met pijltypen kunt u verschillende typen van pijlen definiëren, die in de gegevensstructuren kunnen worden gebruikt. Dit betekent dat een pijltype afzonderlijk kan worden opgemaakt (vooral de kleur), en dat het eenvoudig is in uw scripts alleen pijlen te gebruiken van een bepaald type. Een typisch voorbeeld van het gebruik van pijlen is bij de implementatie van meta-kanten in gegevensstructuren die relaties visualiseren tussen gegevenselementen (bv. communicatie). Maar ook kunnen pijltypen worden gebruikt om op een elegante manier bepaalde soorten kanten te beschrijven (bijvoorbeeld in het algoritme voor het zoeken volgens de methode met de naam "depth first search").

#### Gegevenstypen

In sommige problemen met gegevensstructuren moet een verzameling van gegevenselementen in groepen met een verschillend type worden verdeeld (bv. bij "clustering" problemen en "covering" problemen). Of is het nuttig om in een algoritme een gegevenselement op te geven voor een bepaald type (bv. bij "breath first search"). Elk gegevenstype heeft zijn eigen pictogram en in uw scripts kunt u de gegevenstypen van een bepaald type eenvoudig gebruiken.

#### Dynamische eigenschappen

Elk gegevenselement en elke pijl kan vele eigenschappen hebben. Sommige hiervan zijn standaard vanuit de backend voor de gegevensstructuur. Zie voor meer hierover de documentatie van deze backend. U kunt eigenschappen toevoegen middels dynamische eigenschappen. Iedere dynamische eigenschap heeft een naam en kan elke waarde krijgen. De naam moet met een letter (a-z of A-Z) beginnen, en kan alleen letters, cijfers en '_' bevatten. Indien u een ongeldig teken gebruikt voor de naam van de eigenschap, wordt de eigenschap niet gewijzigd.

U kunt dynamische eigenschappen toevoegen in de dialogen Eigenschappen gegevens en Eigenschappen pijlen in de erbij behorende contextmenu's of met de scriptfuncties, zoals wordt uitgelegd in .

U kunt ook de scripts gebruiken. U hoeft hiervoor alleen `eigenschap_toevogen` te gebruiken, met de naam en waarde van de nieuwe eigenschap. Daarna kunt u de waarden ophalen of instellen met knoop/pijl.NaamEigenschap

Hier volgt een voorbeeld van het gebruik van dynamische eigenschappen met de backend voor grafen.

    nodes = mijnGraaf.list_nodes()
    for (var i = 0; i < nodes.lengte; ++i ){
        nodes[i].add_property("mijnEigenschap", 0)
    }
    nodes[0].mijnEigenschap = 2
    nodes[1].mijnEigenschap = nodes[0].mijnEigenschap + 2

### Instructie

In dit gedeelte maken we een voorbeeldproject aan, waarin enkele van de meest belangrijke eigenschappen van &rocs; worden gebruikt. Het doel is een graaf en een script te maken voor een eenvoudig 2-benaderingsalgoritme voor het "minimum vertex cover"- probleem. Dit houdt in het zoeken naar de kleinste deelverzameling C van de knopen van de graaf, zodat elke kant van de graaf met tenminste een knoop van C is verbonden. Het is bekend dat dit probleem "NP-hard" is, en we willen laten zien hoe we een benadering met een factor 2 kunnen vinden door een overeenkomst in de bestaande graaf te zoeken (in het volgende gebruiken we de gebruikelijke termen in graafalgoritmes: graaf is de gegevensstructuur, knopen zijn de gegevenselementen, kanten zijn de pijlen). (Noot vertaler: ik handhaaf vele Engelse benamingen, ten eerste om de gebruiker van deze tekst in de gelegenheid te stellen om naar deze namen te googlen, en ten tweede omdat ik van de meeste niet de Nederlandse naam (als die er is) ken, of kan vinden).

Ons doel is de overeenkomst zichtbaar te maken tussen de overeenkomende en de "minimum match cover". Hiervoor moeten we twee pijltypen specificeren, een voor het tonen van de overeenkomende kanten, en een voor de gewone kanten. En verder twee gegevenstypen, die gebruikt worden voor het onderscheid tussen knopen in C en knopen die niet tot C behoren.

#### Een graaf genereren

Voor de graaf-backend is in &rocs; een hulpmiddel aanwezig waarmee grafen kunnen worden aangemaakt. We gaan naar het menu Graafdocument Hulpmiddelen Graaf aanmaken. Hier genereren we een "Willekeurige graaf", met 30 knopen, 90 kanten en met het zaadje 1 (het zaadje is de startwaarde voor het genereren van willekeurige getallen; meerdere keren dit zelfde zaadje gebruiken resulteert in dezelfde, en dus reproduceerbare grafen). Tenslotte veranderen we de naam van de graaf in het paneel voor de gegevensstructuur in `testgraaf`.

#### Typen genereren

We gebruiken de knop Documenteigenschappen in het paneel voor de gegevensstructuur, voor het openen van de dialoog voor gegevens- en pijltypen, van het huidige graafdocument. We voegen een nieuw gegevenstype toe met de naam "C", dat automatisch ID (identificatienummer) `1` krijgt. Voor dit type selecteren we het pictogram voor de server. Verder gaan we naar de pagina voor de pijltypen, en selecteren een nieuw pijltype dat we "overeenkomend" gaan noemen. Dit krijgt automatisch de naam `1`, en we stellen de kleur in op blauw.

#### Het algoritme

Tenslotte moeten we het benaderingsalgoritme implementeren. Hiervoor gebruiken we het volgende:

    var E = testgraph.list_edges(); // niet verwerkte kanten
    var C = new Array();            // overeenkomende kanten
    while (E.length
    > 0) {
        var e = E[0];        // we nemen eerste kant e={u,v}
        var u = e.start();
        var v = e.end();
        e.set_type(1);        // maak kant overeenkomend
        E.shift();            // verwijder e (bv. E[0]) uit kantenlijst
        C.push(u);            // voeg u toe aan C
        C.push(v);            // voeg v toe aan C

        // merk u,v als knopen in C
        u.set_type(1);
        v.set_type(1);

        // verwijder uit E alle kanten die in u of v eindigen
        var adjacent = u.adj_edges();
        for (var i=0; i < adjacent.length; i++) {
            var index = E.indexOf(adjacent[i]); // zoek de index
            if (index!=-1) {
                E.splice(index, 1); // verwijder indien gevonden
            }
        }
        var adjacent = v.adj_edges();
        for (var i=0; i < adjacent.length; i++) {
            var index = E.indexOf(adjacent[i]); // zoek de index
            if (index!=-1) {
                E.splice(index, 1); // verwijder indien gevonden
            }
        }
    }
    output("Vertex Cover bevat " + C.length + " knopen.");

#### Het algoritme uitvoeren

Tenslotte willen we het algoritme uitvoeren (draaien, laten werken, executeren). Die kunnen we starten met de knop Uitvoeren in het controlepaneel voor scripts.

## De gebruikersinterface van &rocs;

### Algemene elementen van de gebruikersinterface

De gebruikersinterface is verdeeld in een aantal logische gedeelten, zoals getoond in onderstaand schermbeeld.

GUI-elementen van de interface van &rocs;.
GUI-elementen van de interface van &rocs;.

Documenten selecteren

  In deze bovenste menubalk moet u het huidige document en de gegevensstructuur selecteren. U kunt hierin ook gegevensstructuren aanmaken en wissen, en ook toegang krijgen tot de eigenschappen van gegevensstructuren.

Visuele graafbewerker

  Dit is het zogenaamde "whiteboard", waarin u gegevensstructuren kunt aanmaken en wijzigen. Rechtsklikken in het whiteboard, op gegevenselementen, of op pijlen, opent contextmenu's. U kunt met de hulpmiddelen in de Werkbalk visuele graafbewerker de elementen wijzigen in het visuele bewerkingsprogramma van het whiteboard.

Werkbalk voor de Werkbalk visuele graafbewerker

  In deze werkbalk zijn de hulpmiddelen beschikbaar voor het visuele bewerkingsprogramma. Met Gegevens toevoegen of Verbinding toevoegen kunnen nieuwe gegevenselementen of nieuwe pijlen worden toegevoegd. Nieuwe gegevenselementen worden toegevoegd aan de gegevensstructuur die thans is geselecteerd in de Documentkiezer. Merk op dat bij zowel Gegevens toevoegen als Verbinding toevoegen contextmenu's behoren waarin het type kan worden geselecteerd van de aan te maken gegevens of pijlen. Voor de details, zie .

Zijbalk

  Rechts vindt u de zijbalk waarin u diverse hulpmiddelen vindt om mee te werken:

  - Elementtypen: Hiermee heeft u direct toegang tot de beschikbare pijl- en gegevenstypen.

  - Journaal: Bij elk project hoort een eigen journaal waarin &eg; taken, resultaten of waarnemingen kunnen worden genoteerd.

  - Documentatie: Hiermee kunt u direct toegang krijgen tot het handboek, en zo tot de documentatie over scripts.

Bewerken van scripts

  In deze tekstverwerker kunt u algoritmes schrijven, zoals in detail is uitgelegd in . U kunt aan verschillende scriptdocumenten tegelijk werken, in verschillende tabbladen. Indien wijzigingen in een script nog niet zijn opgeslagen verschijnt er een klein schijfsymbooltje in het tabblad.

Script-uitvoer

  In dit tekstgebied staat informatie over het herstellen van fouten (debug), of de script-uitvoer van uw algoritme, afhankelijk van de selectie van de ingestelde uitvoer, bovenin. Als het script een fout meldt, wordt automatisch de debug-uitvoer geselecteerd.

Besturing

  Hierin kunt u het uitvoeren van scripts regelen. U kunt het script uitvoeren (draaien, laten wereken) dat op dit moment in de scriptbewerker is geopend, door op Uitvoeren te klikken. Een script kan tijdens het uitvoeren worden gestopt door op de knop Stop te klikken. Merk op dat het uitvoeren met de optie Enkele stap alleen bij specifieke kenwoorden stopt.(zie ).

### Werkbalken

Er zijn een aantal verschillende werkbalken beschikbaar voor het visuele bewerkingsprogramma voor grafen, waarin u met één klik over bepaalde bewerkingen kunt beschikken. Standaard worden de volgende werkbalken getoond:

- Hoofdwerkbalk

- Opmaakwerkbalk

#### Hoofdwerkbalk

In de Hoofdwerkbalk vindt u de volgende acties. Hierop klikken maakt dat uw muisaanwijzer deze actie toepast op het whiteboard van het visuele bewerkingsprogramma voor grafen:

- Verplaatsen: U kunt elementen selecteren door in het whiteboard op een lege plek te klikken, of door de muisknop ingedrukt te houden en een rechthoek te "trekken" om enige gegevenselementen en/of pijlen heen om deze elementen te selecteren, of door direct op een niet geselecteerd element te klikken om dit te selecteren. Indien u op een geselecteerd element klikt, of op een verzameling van geselecteerde elementen, kunt u die verplaatsen met de muis, met ingedrukte muisknop. Geselecteerde elementen kunnen ook met de pijltjestoetsen worden verplaatst.

- Gegeven toevoegen: Klik op een willekeurige plaats in het whiteboard van het visuele bewerkingsprogramma, om zo een nieuw gegevenselement aan te maken voor de huidig geselecteerde gegevensstructuur. Door de muisaanwijzer op de knop ingedrukt te houden, komt er een contextmenu, waarin het type kan worden gekozen van de nieuw aangemaakte gegevenselementen (alleen wanneer daarvoor meerdere typen bestaan).

- Verbinding toevoegen: Klik op een gegevenselement, houdt de muisknop ingedrukt, en trek een lijn naar een ander gegevenselement waarnaar de pijl/kant zal wijzen. Dit zal alleen lukken als het in de huidige graaf is toegestaan deze kant toe te voegen (&eg;, in een ongerichte graaf kunt u niet meerdere kanten toevoegen tussen gegevenselementen). Door de muisaanwijzer op de knop ingedrukt te houden, komt er een contextmenu, waarin het type kan worden gekozen van de nieuw aangemaakte pijlen (alleen wanneer daarvoor meerdere typen bestaan).

- Verwijderen: Klik op het element om het te verwijderen. Bij het verwijderen van een knoop worden meteen alle ermee verbonden kanten verwijderd.

- Zoom: Klik op het whiteboard, houdt de &LMB; ingedrukt, en "trek" op deze manier een rechthoek. Er wordt dan op deze rechthoek ingezoomd. U kunt ook met het muiswiel in- en uitzoomen. Door met de &LMB; te dubbelklikken wordt de originele zoom hersteld.

#### Opmaakwerkbalk

U kunt de optionele Opmaakwerkbalk toevoegen. Op een actie hierin klikken heeft direct effect op de huidig geselecteerde knopen:

- Boven: Alle gegevenselementen verticaal uitlijnen op de positie van het bovenste gegevenselement. Dit betreft alleen de verticale posities.

- Midden: De gegevenselementen uitlijnen op de verticale positie van het middelste van de geselecteerde gegevenselementen. Dit betreft alleen de verticale posities.

- Onder: Alle gegevenselementen verticaal uitlijnen op de positie van de onderste gegevenselement. Dit betreft alleen de verticale posities.

- Midden: Alle gegevenselementen uitlijnen op de horizontale positie van het meest rechtse gegevenselement. Dit betreft alleen de horizontale posities.

- Midden: Alle gegevenselementen uitlijnen op de horizontale positie van het meest rechtse gegevenselement. Dit betreft alleen de horizontale posities.

- Rechts: Alle gegevenselementen uitlijnen op de horizontale positie van het meest rechtse gegevenselement. Dit betreft alleen de horizontale posities.

- Cirkel: Lijnt de gegevenselementen uit op een cirkel, waarvan de diameter gelijk is aan de grootste afstand tussen de gegevenselementen. De gegevenselementen worden geplaatst in dezelfde volgorde, als waarin ze worden gezien vanuit het meetkundige zwaartepunt van de de gegevenselementen.

- Kruisende kanten minimaliseren: De geselecteerde gegevenselementen worden zo gerangschikt, dat het aantal elkaar kruisende verbindingen zo klein mogelijk is (met het algoritme van Fruchterman-Reingold).

### Werken met graafdocumenten

Een project in &rocs; bevat een of meer graafdocumenten die in het visuele grafische bewerkingsprogramma kunnen worden bewerkt. Verder kan elk document een willekeurig aantal gegevensstructuren bevatten. Hierbij wordt voor alle gegevensstructuren in een document dezelfde backend voor gegevensstructuren gebruikt. In deze sectie wordt beschreven hoe u tussen documenten kunt schakelen, en hoe u nieuwe kunt aanmaken.

#### De werkbalk voor het selecteren van documenten

In de werkbalk voor het selecteren van documenten selecteert u het huidige graafdocument en de huidige gegevensstructuur. Als u gegevenselementen in gegevensstructuren aanmaakt, met de hulpmiddelen in het visuele grafische bewerkingsprogramma, dan worden deze nieuwe elementen automatisch aan de huidige gegevensstructuur toegevoegd. In deze balk kunt u ook in het huidige document bestaande gegevensstructuren wissen, of nieuwe aanmaken.

- Nieuw: Hiermee maakt u een nieuwe gegevensstructuur aan, met een automatische naamgeving afkomstig van de backend voor de gegevensstructuur. De aangemaakte gegevensstructuur wordt toegevoegd aan het huidig geselecteerde graafdocument.

- Wissen: Hiermee wordt de huidig geselecteerde gegevensstructuur gewist in het huidige document.

- Eigenschappen gegevensstructuur: Openen van een dialoog voor de eigenschappen van gegevensstructuren.

- Eigenschappen document: Openen van een dialoog voor de eigenschappen van het document, alsmede die van de gegevenstypen en pijltypen in het document.

De hoofdwerkbalk.
Balk voor het selecteren van het document.

#### Aanmaken en importeren van graafdocumenten

U kunt een nieuw graafdocument aanmaken, of een bestaand document aan het project toevoegen met Project Nieuw graafdocument of met Project &rocs;-graaf importeren. U kunt ook graafdocumenten van elders importeren (zie hiervoor ).

## Het schrijven en uitvoeren (laten werken) van algoritmes in &rocs;

In &rocs; wordt intern het programma QtScript (een soort JavaScript) gebruikt. Dit betekent dat alle door u geïmplementeerde scripts in JavaScript moeten worden geschreven. Hoe JavaScript werkt, en hoe u in JavaScript programmeert, wordt in dit handboek niet beschreven, maar we leggen wel uit hoe u met gegevensstructuren, gegevenselementen en pijlen moet werken. Omdat u nooit direct het basisobject gebruikt van de gegevensstructuren, maar een dat geleverd wordt door de backend voor de huidige gegevensstructuur, wordt de functionaliteit door deze backend uitgebreid, en zult u deze speciale functionaliteit moeten bestuderen. In het bijzonder worden in de backends passende termen op hun gebied gebruikt, zoals knopen en kanten in grafen, bladeren en wortels (leafs en roots) in boomstructuren, etc.

Het is goed te weten dat veranderingen als gevolg van scripts direct hun weerslag vinden in de eigenschappen in het "whiteboard" van het visuele bewerkingsprogramma. Dat betekent dat scripts de gegevensstructuren daadwerkelijk wijzigen.

### De basiselementen van gegevensstructuren

Iedere backend levert een eigen verzameling van functies en eigenschappen voor zijn gegevensstructuren met hun elementen. Maar elke backend levert ook de functies en eigenschappen die gedefinieerd zijn voor de basisstructuur. Dit betekent dat alles dat hier wordt uitgelegd, geldt voor elke backend voor gegevensstructuren.

#### Basiseigenschappen van gegevensstructuren

Gegevensstructuren worden geïdentificeerd door hun namen. Aangenomen dat een gegevensstructuur is aangemaakt met de naam `testgraaf`, kunt u deze gegevensstructuur gebruiken door eenvoudig deze naam te noemen. Bijvoorbeeld, om een rij met alle gegevenselementen in de gegevensstructuur te verkrijgen, kunt u in het script schrijven: `testgraaf.list_nodes();`

##### Basisigenschappen en functies van gegevensstructuren

Elke gegevensstructuur `testgraaf` heeft de volgende eigenschappen die kunnen worden gelezen of geschreven met de `testgraaf.eigenschap`:

    tekenreeks voor de naam  // naam van de gegevensstructuur

#### Basiseigenschappen en functies van de gegevenselementen

Elk gegevenselement heeft de volgende eigenschappen die kunnen worden gelezen en geschreven:

    double x      // x-coördinaat huidige positie
        double y      // y-coördinaat of huidige positie
        double width  // grootte
        string value  // waarde
        int id         // unieke naam gegevenselementen
        string name   // naam
        string color  // kleur in HEXAdecimaal

Verder kan elke dynamische eigenschap van een gegevenselement worden gebruikt met behulp van zijn naam.

Bij elk gegevenselementobject horen de volgende methodes (functies):

    int type();                         // type elk gegevenselement
        int set_type(int);                  // Instellen type van gegevenselement
        void add_property(string naam,      // dynamische eigenschap toevoegen aan gegevenselement met opgegeven naam en waarde
                          string waarde);
        array adj_data();                   // lijst van aangrenzende gegevens
        array adj_pointers();               // lijst van aangrenzende pijlen
        array input_pointers();             // lijst van invoerpijlen
        array output_pointers();            // lijst van uitvoerpijlen
        array loop_pointers();              // lijst van cyclische pijlen
        array connected_pointers(doel);   // lijst van pijlen naar 'doel'
        void self_remove();                 // Dit gegevenselement wissen

#### Basiseigenschappen en functies van de pijlen

Elk pijl heeft de volgende eigenschappen die kunnen worden gelezen en geschreven:

    string color  // kleur in HEXAdecimaal
        string value  // waarde
        string name   // naam
        double width  // dikte
        string style  // waarde: dot, dash, dash dot, solid

    (vert.: dot: stip; dash: streep; solid: lijn)

Verder kan elke dynamische eigenschap van een pijl worden gebruikt met behulp van zijn naam.

Bij elk pijlobject horen de volgende methodes (functies):

    int type();                         // pijltype van pijl
        int set_type(int);                  // stel pijltype in van de pijl
        void add_property(string naam,      // dynamische eigenschap toevoegen aan gegevenselement met opgegeven naam en waarde
                          string waarde);
        node start();                       // startknoop van de pijl
        node end();                         // eindknoop van de pijl
        void self_remove();                 // deze pijl wissen

### De graafbackend

#### Eigenschappen en functies van grafen

##### Eigenschappen van de graafbackend

In de dialoog voor de eigenschappen van de gegevensstructuur kunt u instellingen doen die behoren tot de graafbackend. Hierin, met Graaftype, kunt u het type kiezen van de graaf. De betekenis van deze typen is als volgt:

- Graaf: Graaf waarin dezelfde kanten (met dezelfde begin- en eindpunten) niet meerdere keren kunnen voorkomen.

- Multigraaf: Graaf waarin dezelfde kanten (met dezelfde begin- en eindpunten) meerdere keren kunnen voorkomen.

##### Gegevensstructuur van een graaf

Gegeven een gegevensstructuurobject van het type "Graaf", kunt u de volgende functies gebruiken:

    array list_nodes();                   // lijst van alle knopen van de graaf
        array list_nodes(int type);           // lijst van alle knopen van gegeven type
        array list_edges();                   // lijst van alle kanten van de graaf
        array list_edges(int type);           // lijst van alle kanten van gegeven type
        node add_node(naam);                  // voeg nieuwe knoop toe en geef die terug
        edge add_edge(node van, node tot);    // voeg nieuwe kant toe van 'van' naar 'tot' en geef die terug
        array overlay_edges(int laagID);   // lijst van alle kanten in een gegeven laag
        edge add_overlay_edge(node van,
                              node tot,
                              int laagID); // voeg kant toe van gegeven pijltype/ in opgegeven laag (overlay)

##### Knopen van grafen

Gegeven een gegevensstructuurobject van het type "Graaf", kunt u de volgende functies gebruiken voor de knopen van de graaf, naast de eigenschappen die worden geleverd door de gegevenselementen:

    array adj_nodes();                    // lijst van alle aangrenzende knopen
        array adj_edges();                    // lijst van alle aangrenzende kanten
        array input_edges();                  // lijst van alle invoerkanten
        array output_edges();                 // lijst van alle uitvoerkanten
        array loop_edges();                   // lijst van alle kanten die met een lus met de knoop verbonden zijn
        array connected_edges(node doel);   // lijst van alle kanten die deze knoop als eindpunt hebben

##### Graafkanten

Gegeven de kanten van een gegevensstructuur van het type "Graaf", zijn alleen de eigenschappen beschikbaar van de basisgegevensstructuur.

#### Algoritmes voor graafstructuren

De backend voor grafen levert enige speciale functies, die in scripts kunnen worden gebruikt.

Berekening kortste weg

  Berekent de kortste weg tussen twee knopen start en eind. Beide knopen moeten tot dezelfde graaf behoren. In deze berekening wordt rekening gehouden met het wel of niet gericht zijn van de graaf.

          array dijkstra_shortest_path knoop start knoopeind

Kortste afstanden tussen knopen

  Berekent de kortste wegen tussen de knoop start en alle andere knopen van de graaf. In deze berekening wordt rekening gehouden met het wel of niet gericht zijn van de graaf.

          array afstanden knoop start

### De backend voor gekoppelde lijsten (Linked List)

#### Eigenschappen en functies voor gekoppelde lijsten

##### De structuur Gekoppelde lijst

Gegeven een gegevensstructuurobject van het type "Gekoppelde lijst" (Linked List), kunt u de volgende functies gebruiken:

    node begin();                           // geeft de beginknoop van de gekoppelde lijst
        setBegin(node begin):                   // instellen van de knoop begin als beginknoop van de lijst en lijst opnieuw ordenen
        createNode();                           // een nieuwe knoop aanmaken voor de lijst

##### Knopen van gekoppelde lijst

Gegeven een gegevensstructuurobject van het type "Gekoppelde lijst" (Linked List), kunt u de volgende functies gebruiken voor de knopen van de graaf, naast de eigenschappen die worden geleverd door de gegevenselementen:

    node front();                           // geeft de vorige knoop in de lijst terug

##### Kanten van gekoppelde lijst

Gegeven de kanten van een gegevensstructuur van het type "Gekoppelde lijst" (Linked List), zijn alleen de eigenschappen beschikbaar van de basisgegevensstructuur.

### De backend voor de boomstructuur

#### Eigenschappen en functies voor de boomstructuur

##### Backend voor boomstructuur

In de dialoog voor de eigenschappen van de gegevensstructuur kunt u instellingen doen die behoren tot de graafbackend. Hierin, door Alle pijlen tonen te selecteren, worden alle pijlen getoond tussen de knooppunten in de boom. Indien niet geselecteerd, worden meerdere pijlen tussen twee zelfde knooppunten als één pijl getoond.

##### De boomstructuur

Gegeven een gegevensstructuurobject van het type "Boomstructuur" (Rooted Tree), kunnen de volgende eigenschappen worden gelezen of geschreven:

    ShowAllPointers     // stel in op true (waar), voor het tonen van alle kanten, stel in op false (onwaar), als meerdere kanten als één moeten worden weergegeven.

Gegeven een gegevensstructuurobject van het type "Boomstructuur" (Rooted Tree), kunt u de volgende functies gebruiken:

    node add_data(string naam);         // voeg een knoop toe aan een boom met de gegeven naam
        void set_root_node(node root);      // stel root in als rootknoop (beginpunt) van de boom
        node root_node();                   // geef rootknoop (beginpunt) terug van de boom

##### Knopen in boomstructuur als root (beginpunt) beschouwd

Gegeven een knoopobject van het type "Boomstructuur" (Rooted Tree), kunnen de volgende eigenschappen worden gelezen of geschreven:

    int numberOfChilds                  // stel aantal in van (mogelijke) onderliggende knopen
        node left_child                     // alleen lezen: onderliggende knoop links
        node right_child                    // alleen lezen: onderliggende knoop rechts
        node node_parent                    // alleen lezen: voortbrengende  (bovenliggende) knoop

Gegeven knoopobject van het type "Boomstructuur" (Rooted Tree), kunt u de volgende functies gebruiken:

    node add_left_child(node child);    // onderliggende knoop child  links toevoegen
        node add_right_child(node child);   // onderliggende knoop child rechts toevoegen
        node add_child(node child, int i);  // child als i-de onderliggende knoop toevoegen
        node add_node_parent(node child);   // aan knoop child een voortbrengende knoop toevoegen (kan alleen als die er nog niet is)
        node left_child();                  // onderliggende knoop links teruggeven
        node right_child();                 // onderliggende knoop rechts teruggeven
        node child_at(int i);               // de i-de onderliggende knoop teruggeven
        node node_parent();                 // de voortbrengende knoop teruggeven

##### Kanten in boomstructuur

Gegeven kanten van een gegevensstructuur van het type "Boomstructuur" (Rooted Tree), zijn alleen de eigenschappen beschikbaar van de basisgegevensstructuur.

### Script uitvoeren besturen

#### Include-bestanden (ingesloten bestanden)

In scriptdocumenten kunnen andere scripts worden opgenomen. Dit is nuttig om de grootte van scripts te beperken, en voor een betere leesbaarheid. Met Scriptdocument Mogelijke Includes verkrijgt u een lijst met de reeds in &rocs; aanwezige scripts, die kunnen worden ingesloten (include). U kunt een scriptbestand met de volgende opdracht insluiten (dus toevoegen):

    include_script(string pad);            // relatieve of absolute pad naar scriptbestand

#### Scriptuitvoer

Gedurende het uitvoeren (werking) van een algoritme, worden debug (programmafouten) en programmauitvoer getoond in de Debug ∧ scriptuitvoer. Indien er een syntaxisfout in uw script wordt ontdekt, wordt de fout ook getoond als een debugbericht. Merk op dat alle programmaberichten ook in de debuguitvoer worden getoond (in een vette letter).

U kunt met de volgende functies de tekst regelen, die in de scriptuitvoer wordt getoond:

    output(string bericht);            // toont bericht als scriptuitvoer
        debug(string bericht);             // toont bericht als debug output

#### Regelen script uitvoeren

U kunt scripts op verschillende manieren uitvoeren (laten werken).

U kunt met de volgende functies de tekst regelen, die in de scriptuitvoer wordt getoond:

- Start: Script uitvoeren tot het einde.

- Stop: Stop het uitvoeren van het script (alleen wanneer een script bezig is).

- Enkele stap: Voer een enkele stap uit van het script. Een stap eindigt met de functie `interrupt()`:

      interrupt();    // einde van een stap

- Debug: Voer een stap uit in debug-modus. Hiermee wordt de debug-dialoog van QtScript geopend. (Debug is zoeken en verbeteren van programmafouten).

## Import en export

### &rocs;-projecten uitwisselen

&rocs; projecten kunnen worden geïmporteerd en geëxporteerd als archiefbestanden (`.tar.gz`-bestanden). Deze archieven kunnen worden gebruikt om projecten uit te wisselen met anderen. Importeren en exporteren doet u met Bestand Project importeren en Bestand Project exporteren.

### Import en export van graafdocumenten

Import en export naar de volgende formaten worden door &rocs; ondersteund:

- DOT-bestanden, ook wel bekend als Graphviz-bestanden.

- GML-bestanden

- Trivial Graph Format bestanden

#### Trivial Graph bestandsformaat

Trivial Graph Format (TGF) is een formaat waarin een grafiek in een eenvoudig tekstbestand wordt beschreven. Een TGF-bestand bevat een lijst van knoopdefinities, waarin knoop-ID's worden gekoppeld aan namen, gevolgd door een lijst van kanten. In dit formaat is slechts één naam mogelijk per knoop, en één waarde per kant. &rocs; beschouwt geïmporteerde grafen als niet gericht. Geëxporteerde grafen bevatten twee kanten voor elke bidirectionele verbinding (naar beide richtingen).

##### Formaatbeschrijving

- Het bestand begint met een lijst van knopen (op elke regel een knoop), gevolgd door een regel met als enige karakter een '#', gevolgd door een lijst van kanten (op elke regel een kant).

- Een knoop wordt beschreven met een geheel getal (als identificatie), gevolgd door een spatie, gevolgd door een willekeurige tekenreeks.

- Een kant wordt beschreven door twee gehele getallen (die de verbonden knopen identificeren), gescheiden door een spatie, gevolgd door een spatie, gevolgd door een willekeurige tekenreeks. Aangenomen wordt dat de gerichte kant wijst van de eerste naar de tweede geïdentificeerde knoop.

##### Voorbeeld

    1 beginknoop
    2 zender
    3 aarde
    #
    1 2 blauw
    2 1 rood
    2 3 groen

#### DOT Language / Graphviz Graph bestandsformaat

De DOT language is een taal voor het beschrijven van een graaf in klare tekst, waarin een goede voor mensen leesbare beschrijving wordt gegeven van grafen, die ook geschikt is voor het efficiënt verwerken door programma's voor het indelen van grafen. DOT is het standaard bestandsformaat voor de Graphviz programma's voor het visualiseren van grafen, maar wordt ook algemeen in andere graafprogramma's gebruikt. De gebruikelijke extensies voor DOT zijn .gv en .dot.

##### Niet ondersteunde eigenschappen

&rocs; kan elk graafbestand lezen van een graaf die volgens DOT is beschreven http://www.graphviz.org/content/dot-language. De ondersteuning van deze taal is volledig, ondanks de volgende uitzonderingen:

- subgraaf: Omdat in &rocs; het begrip subgraaf niet bestaat, worden subgrafen slechts geïmporteerd als verzamelingen van gegevenselementen en verbindingen. In het bijzonder worden verbindingen naar en van subgrafen niet geïmporteerd.

- &HTML; en &XML; attributen: Attributen (zoals tekst) die &HTML; of &XML; bevatten worden onveranderd gelezen. In het bijzonder worden aanpassingen van lettertypen en stijlen van deze attributen niet gelezen.

##### Voorbeeld

    digraph mijnGraaf {
        a -> b -> c;
        b -> d;
    }

## Dankbetuiging en licentie

&rocs;

Programma Copyright:

- Copyright 2008 Ugo Sangiori (ugorox AT gmail.com)

- Copyright 2008-2012 Tomaz Canabrava (tcanabrava AT kde.org)

- Copyright 2008-2012 Wagner Reck (wagner.reck AT gmail.com)

- Copyright 2011-2012 Andreas Cord-Landwehr (cordlandwehr AT googlemail.com)

Documentatie Copyright:

- Documentatie copyright 2009 &Anne-Marie.Mahfouf; &Anne-Marie.Mahfouf.mail;

- Documentatie copyright 2009 Tomaz Canabrava (tcanabrava AT kde.org)

- Documentatie copyright 2011-2012 Andreas Cord-Landwehr (cordlandwehr AT googlemail.com)

&meld.fouten;&vertaling.freek;&vertaling.jaap; &underFDL; &underGPL;

## Installatie

### Hoe u &rocs; kunt verkrijgen

&install.intro.documentation;

### Compileren en installeren

&install.compile.documentation;

&documentation.index;