# Handbok &rocs;

Tomaz
Canabrava
tomaz.canabrava@gmail.com
Andreas
Cord-Landwehr
cordlandwehr@googlemail.com
Stefan
Asserhäll

    stefan.asserhall@comhem.se

Översättare
2009
Tomaz Canabrava
2011-2012
Andreas Cord-Landwehr
2012-12-02
1.8.0 &kde; 4.10
&FDLNotice;

&rocs; är ett grafteoretiskt verktyg för KDE.

KDE
kdeedu
matematik
matematik
grafer
nod
båge

## Inledning

I det här kapitlet ger vi en översikt av de centrala funktionerna och arbetssättet i &rocs;. För den ivrige läsaren som direkt vill börja använda &rocs; föreslår vi att läsa åtminstone och använda som referens för att skriva algoritmer.

### Syfte, målgrupp och arbetsflöde

&rocs; är en integrerad utvecklingsmiljö för grafteori avsedd för alla som är intresserade av att konstruera och analysera grafalgoritmer. Det omfattar speciellt

- föreläsare som vill demonstrera algoritmer för sina studenter,

- studenter som vill förstå och se hur deras algoritmer fungerar,

- och alla som är intresserade av datastrukturer och algoritmer.

För alla dessa användare tillhandahåller &rocs; en lättanvänd datastruktureditor för att skapa datastrukturer, ett kraftfullt skriptverktyg för att utföra algoritmer, och flera hjälpverktyg för simuleringar och experiment.

Det vanliga arbetssättet när &rocs; används är att börja med att skapa en graf med den visuella grafeditorn. Det kan man antingen göra för hand, genom att lägga till dataelement och koppla ihop dem, eller genom att använda en av datastrukturgeneratorerna (om tillgänglig för det aktuella datastrukturgränssnittet) som finns under Grafdokument Verktyg Skapa graf . Dessutom kan man också tilldela värden till datastrukturens element, antingen för hand eller genom att använda Grafdokument Verktyg Tilldela värden. Till sist kan man skriva algoritmer i Javascript och utföra dem med datastrukturen som just har skapats. Alla ändringarna som görs av algoritmen syns direkt i den visuella grafeditorn.

En skärmbild av &rocs;.
En skärmbild av &rocs;.

### &rocs; i ett nötskal

I det här avsnittet ger vi en kortfattad översikt av de centrala delarna av &rocs;. Vi förklarar de viktiga begreppen datastruktur, datastrukturgränssnitt och elementtyper. Kännedom om dessa koncept är användbart för att förstå hur datastrukturer kan skapas och ändras i &rocs;.

I allmänhet arbetar &rocs; med projekt: när &rocs; startas skapas ett tomt projekt och du kan ersätta det genom att läsa in eller importera ett annat projekt. Härigenom består ett projekt själva av grafdokument och skript.

#### Grafdokument och datastrukturgränssnitt

Ett grafdokument representerar innehållet på en skrivtavla i den visuella grafeditorn. Härigenom kan ett grafdokument innehålla flera datastrukturer samtidigt, men bara ett datastrukturgränssnitt. Datastrukturgränssnitt finns tillgängliga för flera olika typer av grafer (allmänna grafer, länkade listor, rotade träd) och tillhandahåller ytterligare funktionalitet för sina specifika typer av grafer. Det kan vara automatisk positionering av elementen, särskilda ikonuppsättningar eller en utökad uppsättning skriptfunktioner för användning i algoritmer (för detaljinformation titta i motsvarande avsnitt av handboken). Det är möjligt att ändra datastrukturgränssnitt i ett grafdokument, även om information kan gå förlorad (t.ex. bågarna för en cirkel i en allmän graf läggs inte till i ett träd, om du byter till gränssnittet för rotat träd).

Grafdokument utgör också basen för att definiera piltyper och datatyper.

#### Datastrukturer

Datastrukturer är basen för allt arbete i &rocs;. Du kan lägga till en eller flera sådana i ett grafdokument, och dataelement (noder, datavärden) och pilar till dem, samt ändra dem med skript. För detta har varje datastruktur sitt unika namn som den går att komma åt med från skript. På grund av valet av gränssnitt för den aktuella datastrukturen kan det hända att du inte kan ändra datastrukturen helt godtyckligt (t.ex. ska ett träd aldrig innehålla en cykel). Datastrukturgränssnittet bestäms av det gränssnitt för datastrukturer associerat med motsvarande grafdokument som innehåller datastrukturen.

#### Piltyper

Med piltyper kan du definiera olika typer av pilar som ska användas av datastrukturerna. Det betyder att en piltyp kan få en individuell layout (stort sett en färg) och det är enkelt att bara komma åt pilar av en viss typ från skript. Typiska användarfall för pilar kan vara att implementera meta-bågar i datastrukturer som åskådliggör förhållanden mellan dataelement (t.ex. åskådliggör kommunikationsbehov). Men om skript dessutom ska identifiera särskilda typer av bågar (t.ex. träd och korsande bågar i djup-först sökalgoritmer), kan piltyper vara ett elegant sätt att implementera det.

#### Datatyper

I flera datastrukturproblem ska en uppsättning dataelement delas upp i grupper av olika typer (t.ex. ett klusterproblem eller täckningsproblem). Annars är det användbart att specificera en dataelementtyp för att uttrycka en specifik sort (t.ex. bredd-först sökning) när en algoritm utförs. För sådana fall kan datatyper definieras. Varje datatyp har sin egen ikon, och dataelement av en viss typ kan enkelt kommas åt från skript.

#### Dynamiska egenskaper

Varje dataelement och pil kan ha många egenskaper. Vissa av dessa egenskaper är standardvärden från datastrukturgränssnittet. Se dokumentationen av datastrukturgränssnittet för mer information. För att lägga till fler egenskaper i dataelement och pilar kan du lägga till dynamiska egenskaper till dem. Varje dynamisk egenskap identifieras med sitt namn och kan innehålla vilket tillhörande värde som helst. Namnet måste börja med en bokstav (a-z eller A-Z) och kan bara innehålla bokstäver, siffror och '_'. Om du försöker använda ett ogiltigt tecken i egenskapsnamnet ändras inte egenskapen.

Använd dialogrutorna Dataegenskaper och Pilegenskaper i de sammanhangsberoende menyerna för respektive element eller skriptfunktionerna som förklaras i , för att lägga till dynamiska egenskaper.

Du kan också använda skript. Du behöver bara använda `add_property` med namn och värde på egenskapen. Därefter kan du använda node/pointer.propertyName för att ändra eller läsa av värdena.

Här är ett exempel på hur dynamiska egenskaper används med datastrukturgränssnittet "Graf".

    nodes = myGraph.list_nodes()
    for (var i = 0; i < nodes.length; ++i ){
        nodes[i].add_property("MyProperty", 0)
    }
    nodes[0].MyProperty = 2
    nodes[1].MyProperty = nodes[0].MyProperty + 2

### Handledning

I det här avsnittet ska vi skapa ett exempelprojekt för att utforska några av de viktigaste funktionerna i &rocs;. Målet är att skapa en graf och ett skript som åskådliggör en enkel 2-approximativ algoritm för problemet med minimal hörntäckning. Minimal hörntäckning är problemet att hitta en delmängd av grafnoder C med minimal storlek, sådan att varje grafbåge är ansluten till minst en nod i C. Problemet är känt som NP-svårt, och vi vill åskådliggöra hur man hittar en approximation med faktorn 2 genom att hitta en motsvarighet i den givna grafen (i det följande använder vi de vanliga termerna för grafalgoritmer: grafen är datastrukturen, noder är dataelementen, bågar är pilarna).

Vårt mål är att åskådliggöra likheten mellan motsvarigheten och den minimala hörntäckningen. För att göra det behöver vi specificera två piltyper, en för att visa motsvarande bågar och en för att visa vanliga bågar, samt två datatyper som vi använder för att skilja på noder som ingår i C och de som inte ingår i C.

#### Skapa en graf

&rocs; levereras med ett hjälpverktyg för datastrukturgränssnittet "Graf" som kan skapa grafer. Vi går till Grafdokument Verktyg Skapa graf. Där skapar vi en "Slumpmässig graf" med 30 noder, 90 bågar och fröet 1 (fröet är startfrö för den slumpmässiga grafgenereringen, används samma frö flera gånger erhålles samma och upprepningsbara grafer). Till sist ändrar vi grafnamnet i datastrukturpanelen och kallar grafen `testgraf`.

#### Skapa typer

Vi använder knappen Dokumentegenskaper i datastrukturpanelen för att visa egenskapsdialogrutan för data- och piltyper i det aktuella grafdokumentet. I datatyperna lägger vi till en ny typ som heter "C", som automatiskt för identifieraren `1`. Vi väljer serverbilden som ikon för typen. Dessutom byter vi till piltypsidan och lägger till en ny piltyp som kallas "match". Den får automatiskt identifieraren `1`, och vi ställer in färgen till blå.

#### Algoritmen

Till sist måste vi implementera approximationsalgoritmen. Vi använder följande implementering för den:

    var E = testgraph.list_edges(); // mängden obehandlade bågar
    var C = new Array();            // matchande bågar
    while (E.length
    > 0) {
        var e = E[0];        // vi tar första bågen e={u,v}
        var u = e.start();
        var v = e.end();
        e.set_type(1);        // ställ in bågen till en matchande båge
        E.shift();            // ta bort e (dvs. E[0]) från listan av bågar
        C.push(u);            // lägg till u i C
        C.push(v);            // lägg till v i C

        // markera u,v som noder i C
        u.set_type(1);
        v.set_type(1);

        // ta bort alla bågar från E som ansluter till u eller v
        var adjacent = u.adj_edges();
        for (var i=0; i < adjacent.length; i++) {
            var index = E.indexOf(adjacent[i]); // hitta index
            if (index!=-1) {
                E.splice(index, 1); // ta bort om redan hittad
            }
        }
        var adjacent = v.adj_edges();
        for (var i=0; i < adjacent.length; i++) {
            var index = E.indexOf(adjacent[i]); // hitta index
            if (index!=-1) {
                E.splice(index, 1); // ta bort om redan hittad
            }
        }
    }
    output("Vertex Cover contains " + C.length + " nodes.");

#### Utför algoritmen

Till sist vill vi utföra algoritmen. För att göra det kan vi starta körningen med knappen Kör i skriptpanelen.

## &rocs; användargränssnitt

### Allmänna delar i användargränssnittet

Användargränssnittet är uppdelat i flera logiska delar som framgår av skärmbilden nedan.

Grafiska element i &rocs; användargränssnitt.
Grafiska element i &rocs; användargränssnitt.

Dokumentväljare

  Det aktuella dokumentet och datastrukturen måste väljas med den här menyraden längst upp. Att skapa eller ta bort datastrukturer samt att komma åt datastrukturers egenskaper är också möjligt här.

Visuell grafeditor

  Detta är skrivtavlan där datastrukturer kan skapas och ändras. Högerklicka på skrivtavlan, på dataelement eller på pilar för att visa sammanhangsberoende menyer. Du kan använda verktygen från den visuella grafeditorns verktygsrad för att ändra elementen på den visuella grafeditorns skrivtavla.

Den visuella grafeditorns verktygsrad

  Denna verktygsrad tillhandahåller alla verktyg för den visuella grafeditorn.Använd verktygen Lägg till data eller Lägg till anslutning för att skapa nya dataelement och lägga till dataelement respektive pilar. Nya dataelement läggs till i datastrukturen som för närvarande är markerad i Dokumentväljaren. Observera att både Lägg till data och Lägg till anslutning har sammanhangsberoende menyer för val av data- och piltyp för de nya elementen som ska skapas. För detaljerad information, se .

Sidorad

  Till höger finns sidoraden som tillhandahåller flera verktyg för arbetsflödet:

  - Elementtyper: Denna grafiska komponent ger direktåtkomst till de tillgängliga pil- och datatyper.

  - Journal: Varje projekt har sin egen journal som t.ex. kan användas för anteckningar om uppgifter, resultat eller observationer.

  - Dokumentation: Den här grafiska komponenten kan användas för att direkt komma åt handboken och därmed skriptdokumentationen.

Skripteditor

  I texteditorn kan algoritmer skrivas som förklaras i detalj i . Det går att arbeta med flera skriptdokument samtidigt genom att använda flera flikar. Skivsymbolen på en flik visas om skriptet innehåller osparade ändringar.

Skriptutmatning

  I det här textområdet visas antingen felsökningsinformation eller skriptutmatning från algoritmer, beroende på val av utmatningsinställning längst upp i den grafiska komponenten. Om ett fel uppstår i skriptet, väljes automatiskt felsökningsutmatning.

Styrning

  Här hittar man hur körning av algoritmerna styrs. Skriptet som för närvarande är öppet i skripteditorn kan köras med genom att klicka på Kör. Medan skriptet körs, är det möjligt att stoppa det genom att klicka på knappen Stopp. Observera att körning med Ett steg bara stoppar vid specifika nyckelord (se ).

### Verktygsrader

Det finns olika verktygsrader för den visuella grafeditorn som gör det möjligt att komma åt funktioner med bara ett klick. Med standardinställningen visas följande verktygsrader:

- Huvudverktygsrad

- Justeringsverktygsrad

#### Huvudverktygsrad

Huvudverktygsraden innehåller följande åtgärder. Att klicka på en åtgärd leder till att muspekaren utför den åtgärden på den visuella grafeditorns skrivtavla:

- Flytta: För att markera element, klicka antingen på en oanvänd plats på skrivtavlan, håll musknappen nedtryckt och rita en rektangel som innehåller några noder och/eller bågar för att markera dessa element, eller klicka annars direkt på ett omarkerat element för att markera det. Om du klickar på ett markerat element, eller en uppsättning markerade element, kan de flyttas omkring genom att hålla musknappen nedtryckt och flytta omkring musen. Det är också möjligt att flytta markerade element med piltangenterna.

- Lägg till data: Klicka på ett godtyckligt ställe på den visuella grafeditorns skrivtavla för att skapa ett nytt dataelement som hör till datastrukturen som för närvarande är markerad. Genom att hålla muspekaren nedtryckt visas en sammanhangsberoende meny där datatypen för det nyskapade dataelementen kan väljas (bara om olika datatyper finns).

- Lägg till anslutning: Klicka på ett dataelement, håll musknappen nedtryckt och rita en linje till ett annat dataelement, dit pilen/bågen ska peka. Åtgärden lyckas bara om den aktuella grafen tillåter att bågen läggs till (i en oriktad graf får t.ex. inte mer än en båge läggas till mellan två dataelement). Genom att hålla muspekaren nedtryckt, dyker en sammanhangsberoende meny upp där piltypen för de nyskapade pilarna kan väljas (bara om olika piltyper finns).

- Ta bort: Klicka på ett element för att ta bort det. Om du tar bort en nod, tas också alla intilliggande bågar bort.

- Zooma: Klicka på skrivtavlan, håll vänster musknapp nertryckt, och rita på så sätt en rektangel. Skrivtavlan zoomas till det markerade området. Använd också mushjulet för att zooma in eller ut. Ett dubbelklick med musens vänsterknapp återställer ursprunglig zoomnivå.

#### Justeringsverktygsrad

Det går att lägga till en valfri justeringsverktygsrad. Genom att klicka på ett alternativ i verktygsraden erhålls direkt en effekt på noderna som för närvarande är markerade:

- Upp: Justera dataelementen längs den vertikala positionen av det översta dataelementet. Detta påverkar bara vertikala positioner.

- Mitt: Justera dataelementen längs den vertikala positionen som anges av centrum för alla markerade noders vertikala position. Detta påverkar bara vertikala positioner.

- Bas: Justera dataelementen längs den vertikala positionen av det understa dataelementet. Detta påverkar bara vertikala positioner.

- Vänster: Justera dataelementen längs den horisontella positionen för dataelementet längst åt vänster. Detta påverkar bara horisontella positioner.

- Mitt: Justera dataelementen längs den horisontella positionen för dataelementet längst upp. Detta påverkar bara horisontella positioner.

- Höger: Justera dataelementen längs den horisontella positionen för dataelementet längst åt höger. Detta påverkar bara horisontella positioner.

- Cirkel: Justerar dataelementen längs en cirkel vars diameter är lika med den maximala avståndet mellan dataelementen. Dataelementen placeras i samma följd som ges av hur dessa dataelement ser ut från sin tyngdpunkt.

- Minimera korsande bågar: Arrangera om markerade dataelement för att minimera antal korsande anslutningar (applicerar Fruchterman-Reingold-algoritmen).

### Arbeta med grafdokument

Ett projekt i &rocs; innehåller ett eller flera grafdokument som kan redigeras med den visuella grafeditorn. Dessutom kan varje dokument innehålla ett godtyckligt antal datastrukturer. Här använder datastrukturer i ett dokument alla samma datastrukturgränssnitt. Det här avsnittet förklarar hur man byter mellan dokument och hur man skapar nya.

#### Dokumentväljarraden

Dokumentväljarraden används för att välja det aktuella grafdokumentet och dessutom den aktuella datastrukturen. Att använda det visuella grafeditorverktyget för att skapa datastrukturelement lägger automatiskt till de nyskapade elementen i den aktuella datastrukturen. Dessutom ger raden direktåtkomst för att ta bort befintliga eller skapa nya datastrukturer inne i det aktuella dokumentet.

- Ny: Åtgärden skapar en ny datastruktur med användning av ett automatiskt namngivningsmönster given av datastrukturens gränssnitt. Den skapade datastrukturen läggs till i grafdokumentet som för närvarande är valt.

- Ta bort: Åtgärden tar bort datastrukturen som för närvarande är markerad i datastrukturväljaren för det aktuella dokumentet.

- Datastrukturegenskaper: Öppna en dialogruta som ger tillgång till datastrukturens egenskaper.

- Dokumentegenskaper: Öppna en dialogruta som ger tillgång till dokumentegenskaperna samt data- och piltyperna i dokumentet.

Huvudverktygsraden.
Dokumentväljarraden

#### Skapa och Importera grafdokument

För att skapa ett nytt grafdokument, eller lägga till ett befintligt dokument i projektet, använd Projekt Nytt grafdokument eller Projekt Importera &rocs;-graf. Du kan också importera grafdokument från tredjepartsprogram (för mer om detta, se ).

## Skriva och utföra algoritmer i &rocs;

Internt använder &rocs; skriptgränssnittet QtScript, som är ett specifikt Javascript-gränssnitt. Det innebär att alla algoritmer du implementerar måste använda Javascript. Hur Javascript fungerar och hur man skriver kod för Javascript täcks inte av den här handboken, men vi beskriver hur du kommer åt datastrukturer, dataelement och pilar i dina datastrukturer via skriptgränssnittet. Eftersom du aldrig använder det grundläggande datastrukturobjektet, utan ett som tillhandahålls av det aktuella datastrukturgränssnittet, utökas datastrukturens funktionalitet av motsvarande gränssnitt, och du måste ta en titt på den specialiserade funktionaliteten. I synnerhet, använder datastrukturgränssnitt vanlig terminologi från sin domän (noder och bågar för grafer, löv och rot för träd, etc.).

Det är viktigt att känna till att ändringarna som görs av skriptgränssnittet direkt reflekteras i egenskaperna på den visuella grafeditorns skrivtavla. Sålunda ändrar skripten verkligen själva datastrukturerna.

### Grundläggande element i datastrukturer

Varje gränssnitt tillhandahåller en särskild uppsättning funktioner och egenskaper för sina datastrukturer och deras element. Men varje gränssnitt tillhandahåller också egenskaperna och funktionerna som har definierats för basdatastrukturen. Därför är allt som beskrivs i det här avsnittet tillgängligt i alla datastrukturgränssnitt.

#### Grundläggande egenskaper för datastrukturer

Datastrukturer identifieras av sina namn. Om du alltså skapade en datastruktur med namnet `testgraf` kan du komma åt den genom att bara skriva denna identifierare. För att exempelvis få ett fält med alla dataelement i den givna datastrukturen kan du skriva `testgraf.list_nodes();` i skriptet.

##### Grundläggande egenskaper och funktioner för datastrukturer

Varje datastrukturs `testgraf` har följande egenskaper som kan läsas eller skrivas av `testgraf.property`:

    string namn  // identifikation av datastrukturen

#### Grundläggande egenskaper och funktioner för dataelement

Varje dataelement har följande egenskaper som kan läsas eller skrivas:

        double x      // x-koordinat för aktuell position
        double y      // y-koordinat för aktuell position
        double width  // storlek
        string value  // värde
        int id        // unik identifierare för dataelement
        string name   // namn
        string color  // färg i hexadecimal notation

Dessutom kan varje dynamisk egenskap i ett dataelement kommas åt via sitt namn.

Varje dataelement tillhandahåller också följande metoder:

        int type();                         // dataelementets datatyp
        int set_type(int);                  // ange dataelementets datatyp
        void add_property(string name,      // lägg till dynamisk egenskap för
                          string value);    // dataelement med angivet namn och värde
        array adj_data();                   // lista över intilliggande data
        array adj_pointers();               // lista över intilliggande pilar
        array input_pointers();             // lista över pilar som pekar inåt
        array output_pointers();            // lista över pilar som pekar utåt
        array loop_pointers();              // lista över pilar som själva formar en cirkel
        array connected_pointers(target);   // lista över pilar som pekar på'target'
        void remove();                      // ta bort detta dataelement

#### Basegenskaper och funktioner för pilar

Varje pil har följande egenskaper som kan läsas eller skrivas:

        string color  // färg i hexadecimal notation
        string value  // värde
        string name   // namn
        double width  // bredd
        string style  // något av värdena: dot, dash, dash dot, solid

Dessutom kan varje dynamisk egenskap för en pil kommas åt via sitt namn.

Varje pilobjekt tillhandahåller följande metoder:

        int type();                         // pilens piltyp
        int set_type(int);                  // ange pilens piltyp
        void add_property(string name,      // lägg till dynamisk egenskap för
                          string value);    // dataelement med angivet namn och värde
        string value();
        node start();                       // startnod för pilen
        node end();                         // målnod för pilen
        void remove();                      // ta bort denna pil

### Gränssnittet för grafer

#### Grafegenskaper och funktioner

##### Specifika egenskaper i gränssnittet för grafer

Dialogrutan för datastrukturegenskaper gör det möjligt att anpassa inställningar som är specifika för grafgränssnittet. Där kan du använda Graftyp för att välja grafens typ. Betydelsen av typerna är följande:

- Graf: Graf där samma bågar (med avseende på start- och slutpunkt) inte får finnas flera gånger.

- Multigraf: Graf där likadana bågar (med avseende på start- och slutpunkt) kan finnas flera gånger.

##### Grafstrukturen

Med ett datastrukturobjekt av typen "Graph" kan du anropa följande medlemsfunktioner:

        array list_nodes();                   // lista över alla noder i grafen
        array list_nodes(int type);           // lista över alla noder av angiven typ
        array list_edges();                   // lista över alla bågar i grafen
        array list_edges(int type);           // lista över alla bågar av angiven typ
        node add_node(name);                  // lägg till och returnera noden
        edge add_edge(node from, node to);    // lägg till och returnera ny bågefrån 'from' till 'to'
        array overlay_edges(int overlayID);   // lista över alla bågar i angivet överlägg
        edge add_overlay_edge(node from,
                              node to,
                              int overlayID); // lägg till båge för given piltyp i angivet överlägg

##### Grafnoder

Med ett givet datastrukturobjekt av typen "Graph" kan du anropa följande medlemsfunktioner för grafnoderna utöver egenskaperna som tillhandahålls av dataelementen:

        array adj_nodes();                    // lista över alla intilliggande noder
        array adj_edges();                    // lista över ihopkopplade bågar
        array input_edges();                  // lista över bågar som pekar inåt
        array output_edges();                 // lista över bågar som pekar utåt
        array loop_edges();                   // lista över alla bågar som går runt till noden
        array connected_edges(node target);   // alla bågar som kopplar denna till noden 'target'

##### Grafbågar

För givna bågar i en datastruktur av typen "Graph" är bara egenskaperna för basdatastrukturen tillgängliga.

#### Algoritmer för grafstruktur

Grafgränssnittet tillhandahåller några specialfunktioner som kan användas från skriptgränssnittet.

Beräkning av kortaste vägen

  Beräknar kortaste väg mellan noderna start och slut. Båda noderna måste ingå i samma graf. Beräkningen tar hänsyn till om grafen är riktad eller inte.

          array dijkstra_shortest_path node start node end

Kortaste vägens avstånd

  Beräknar kortaste vägens avståndet från noden start till alla andra noder i grafen. Beräkningen tar hänsyn till om grafen är riktad eller inte.

          array distances node start

### Gränssnittet för länkade listor

#### Länkade listors egenskaper och funktioner

##### Länkade listors struktur

Med ett datastrukturobjekt av typen "Linked List" kan du anropa följande medlemsfunktioner:

        node begin();                           // ger huvudnoden i den länkadelistan
        setBegin(node begin):                   // ange startnod som listans början och arrangera om den
        createNode();                           // skapa en ny listnod

##### Länkade listnoder

Med ett datastrukturobjekt av typen "Linked List" kan du anropa följande medlemsfunktioner på grafnoderna utöver egenskaperna som tillhandahålls av dataelementen:

    node front();                           // returnerar nodens föregångare

##### Bågar i länkade listor

Med bågar från en datastruktur av typen "Linked List" är bara egenskaperna för basdatastrukturen tillgängliga.

### Gränssnittet för rotade träd

#### Egenskaper och funktioner för Rotat träd

##### Gränssnittet för rotade träd

Dialogrutan för datastrukturegenskaper gör det möjligt att anpassa inställningar som är specifika för trädgränssnittet. Där kan markera egenskapen Visa alla pilar för att visa alla pilar mellan trädets noder. Om den inte markeras, kombineras flera pilar mellan samma noder till en.

##### Strukturen Rotat träd

Med ett datastrukturobjekt av typen "Rooted Tree" kan följande egenskaper läsas eller skrivas:

    ShowAllPointers     // ställ in till true om alla bågar ska visas, annars false om bågar ska komprimeras

Med ett datastrukturobjekt av typen "Rooted Tree" kan du anropa följande medlemsfunktioner:

        node add_data(string name);         // lägg till en nod i trädet med givet namn
        void set_root_node(node root);      // ange rot som trädets rotnod
        node root_node();                   // returnera trädets rotnod

##### Noder i Rotat träd

Med ett nodobjekt av typen "Rooted Tree" kan följande egenskaper läsas eller skrivas:

        int numberOfChilds                  // ange nodens antal (tillåtna) underliggande noder
        node left_child                     // läs endast: den vänstra underliggande noden
        node right_child                    // läs endast: den högra underliggande noden
        node node_parent                    // läs endast: den ovanliggande noden

Med ett nodobjekt av typen "Rooted Tree" kan du anropa följande medlemsfunktioner:

        node add_left_child(node child);    // lägg till underliggande nod till vänster
        node add_right_child(node child);   // lägg till underliggande nod till höger
        node add_child(node child, int i);  // lägg till en underliggande nod som den i:te noden
        node add_node_parent(node child);   // lägg till ovanliggande nod (fungerar bara om den inte finns)
        node left_child();                  // returnera höger underliggande nod
        node right_child();                 // returnera vänster underliggande nod
        node child_at(int i);               // returnera den i:te underliggande noden
        node node_parent();                 // returnera nodens överliggande nod

##### Bågar i Rotat träd

Med bågar från en datastruktur av typen "Rooted Tree" är bara egenskaperna för basdatastrukturen tillgängliga.

### Styra körning av skript

#### Inkludera filer

Skriptdokument kan inkludera andra skript. Det kan vara användbart för att minska storleken på skriptdokumenten och förbättra läsbarheten. Genom att använda Skriptdokument Möjliga deklarationsfiler får du en lista över de skriptfiler som levererades med &rocs; som kan inkluderas. Du kan inkludera en skriptfil med följande kommando:

    include_script(string path);            // relativ eller absolut sökvägtill skriptfilen

#### Skriptutmatning

När en algoritm körs visas felsöknings- och programutdata i felsöknings- och skriptutmatning. Om skriptgränssnittet upptäcker ett syntaxfel i skriptet visas även det felet som ett felsökningsmeddelande. Observera att alla programmeddelanden också visas i felsökningsutmatningen (med fetstil).

Du kan bestämma vilken text som visas i skriptutmatningen med följande funktioner:

        output(string message);            // visar meddelandet som skriptutdata
        debug(string message);             // visar meddelandet som felsökningsutdata

#### Styr körning av skript

Det finns olika sätt att köra skripten.

Du kan bestämma vilken text som visas i skriptutmatningen med följande funktioner:

- Starta: Kör skriptet till det är klart.

- Stoppa: Stoppa körning av skript (bara tillgängligt om ett skript körs).

- Ett steg: Kör skript tills ett steg avslutas. Ett steg avslutas när skriptet anropar funktionen `interrupt()`:

      interrupt();    // avslutar ett steg

- Felsökning: Kör skript i felsökningsläge. Detta öppnar QtScripts felsökningsdialogruta.

## Import och export

### Utbyt &rocs;-projekt

&rocs;-projekt kan importeras och exporteras som arkivfiler `.tar.gz`. Dessa arkiv kan användas för att utbyta projekt. Import och export kan utföras med Arkiv Importera projekt respektive Arkiv Exportera projekt.

### Import och export av grafdokument

&rocs; stöder för närvarande import och export av följande filformat:

- DOT-filer, också kända som Graphviz-filer

- GML-filer

- Filer med Trivial Graph-format

#### Trivial Graph-filformat

Trivial Graph-formatet (TGF) är ett enkelt textbaserat filformat för att beskriva grafer. En TGF-fil består av en lista med noddefinitioner, som avbildar nod-identifierare på etiketter, följt av en lista med bågarna. Det är bara möjligt att ha en etikett per nod och ett värde per båge i detta format. &rocs; tolkar importerade grafer som oriktade grafer. Exporterade grafer innehåller två bågar per anslutning om anslutningarna är bidirektionella.

##### Formatspecifikation

- Filen börjar med en lista med noder (en nod per rad), följt av en rad med det enda tecknet "#", följt av en lista med bågar (en båge per rad).

- En nod består av ett heltal (identifierare), följt av ett mellanslag, följt av en godtycklig sträng.

- En båge består av två heltal (identifierare) åtskilda med ett mellanslag, följda av ett mellanslag, följt av en godtycklig sträng. Det antas att den riktade bågen pekar från den första identifieraren till den andra.

##### Exempel

    1 startnod
    2 sändare
    3 mottagare
    #
    1 2 blå
    2 1 röd
    2 3 grön

#### DOT-språket, Graphviz graffilformat

DOT-språket är ett grafbeskrivningsspråk med vanlig text som både tillåter en bra mänskligt läsbar representation av grafer samt en effektiv behandling av graflayoutprogram. DOT är standardfilformat för Graphviz grafvisualiseringssvit, men används också av många andra grafverktyg. De vanliga filändelserna för DOT är .gv och .dot.

##### Funktioner som inte stöds

&rocs; kan tolka alla graffiler som innehåller en graf angiven enligt språkdefinitionen för DOT http://www.graphviz.org/content/dot-language. Stödet för språkets funktioner är fullständigt, trots följande undantag:

- delgraf: På grund av avsaknaden av ett delgrafskoncept i &rocs;, importeras bara delgrafer som en uppsättning dataelement och anslutningar. I synnerhet importeras inte anslutningar till eller från delgrafer.

- &HTML;- och &XML;-attribut: Attribut (som beteckningar) som innehåller &HTML;- eller &XML;-syntax läses oförändrade. I synnerhet läses inte justeringar av teckensnitt och stilar från sådana attribut.

##### Exempel

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

## Tack till och licens

&rocs;

Program Copyright:

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

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

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

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

Dokumentation Copyright:

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

- Dokumentation copyright 2009 Tomaz Canabrava (tcanabrava SNABELA kde.org)

- Dokumentation copyright 2012 Andreas Cord-Landwehr (cordlandwehr SNABELA googlemail.com)

Översättning Stefan Asserhäll stefan.asserhall@comhem.se

&underFDL; &underGPL;

## Installation

### Hur man skaffar &rocs;

&install.intro.documentation;

### Kompilering och installation

&install.compile.documentation;

&documentation.index;