# &rocs;i käsiraamat

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

    bald@smail.ee

Tõlge eesti keelde
2009
Tomaz Canabrava
2011-2012
Andreas Cord-Landwehr
2012-12-02
1.7.80 &kde; 4.10
&FDLNotice;

&rocs; on KDE graafiteooria tööriist.

KDE
kdeedu
matemaatika
matemaatika
graafid
tipp
seos

## Sissejuhatus

Käesolev peatükk annab ülevaate &rocs;i põhiomadustest ja töövoost. Lugejatel, kes soovivad kohe hakata &rocs;i kasutama, soovitame läbi lugeda vähemalt ja võtta ette , mis selgitab, kuidas kirjutada algoritme.

### Eesmärgid, sihtrühmad ja töövoog

&rocs; on graafiteooria arenduskeskkond kõigile, keda huvitab graafialgoritmide loomine ja analüüs. See hõlmab muu hulgas

- õppejõude, kes soovivad demonstreerida algoritme oma õpilastele,

- õppureid, kes soovivad mõista ja näha algoritmide tööd,

- kõiki, kes tunnevad huvi andmestruktuuride ja algoritmide vastu.

Kõigile neile pakub &rocs; hõlpsasti pruugitava andmestruktuuride redaktori, millega luua andmestruktuure, võimsa skriptimismootori algoritmide täitmiseks ja mitu abitööriista simulatsioonide ja katsete korraldamiseks.

Tavaliselt on esimene samm &rocs;i kasutamisel graafi loomine visuaalse graafiredaktoriga. Seda võib teha käsitsi, see tähendab andmeelemente luues ja neid ühendades, või siis kasutades mõnda andmestruktuuri genereerijat (kui need on aktiivse andmestruktuuri taustaprogrammi jaoks olemas), mida pakub menüükäsk Graafidokument Tööriistad Graafi genereerimine. Samuti võib lõpuks kasutada tööriista Tööriistad Väärtuste omistamine, millega saab anda andmestruktuurielementidele väärtused. Neid saab omistada ka käsitsi. Lõpuks saab kirjutada JavaScriptis valmis oma algoritmi ja selle käivitada vastselt loodud andmestruktuuriga. Muudatused, mida algoritm andmestruktuuris teeb, on kohe näha visuaalses graafiredaktoris.

&rocs;i pilt.
&rocs;i pilt.

### &rocs;i põhitõed

Selles osas antakse lühiülevaade &rocs;i tähtsaimatest elementidest. Me selgitame olulisi andmestruktuuri, andmestruktuuri taustaprogrammi ja elemenditüübi mõisteid. Nende teadmine aitab mõista, kuidas käib &rocs;is andmestruktuuride loomine ja muutmine.

Üldiselt töötab &rocs; projektidega: &rocs;i avamisel luuakse tühi projekt, mida sa võid asendada, kui laadid või impordid mõne muu projekti. Projekt ise aga koosneb graafidokumentidest ja skriptidest.

#### Graafidokumendid ja andmestruktuuri taustaprogrammid

Graafidokument tähendab visuaalse graafiredaktori lõuendi sisu. Graafidokument võib sisaldada korraga mitut andmestruktuuri, aga ainult üht andmestruktuuri taustaprogrammi. Andmestruktuuri taustaprogramme on mitmele graafitüübile (üldised graafid, lingitud loendid, juurega puu) ja need pakuvad konkreetsele graafitüübile lisavõimalusi. Selleks võivad olla elementide automaatne paigutamine, spetsiaalsed ikoonikogumid või ka algoritmides kasutavate skriptifunktsioonide täiendamine (üksikasju vaata käsiraamatu vastavatest osadest). Võimalik on muuta graafidokumendi andmestruktuuri taustaprogrammi, kuigi sellega võib kaasneda teabekadu (näiteks ei saa üldise graafi ringi seoseid lisada puule, kui lülitud juurega puu taustaprogrammile).

Graafidokumendid on ühtlasi aluseks viida- ja andmetüüpide defineerimisel.

#### Andmestruktuurid

Andmestruktuurid on kogu &rocs;i töö alus. Neid võib lisada ühele graafidokumendile ka mitu, samuti saab lisada neile andmeelemente (sõlmed, andmed) ja viitu ning muuta neid skriptidega. Selleks on igal andmestruktuuril unikaalne nimi, mille järgi saab seda kasutada skriptis. Sõltuvalt parajasti valitud andmestruktuuri taustaprogrammist võib juhtuda, et andmestruktuure ei saa päris igatmoodi muuta (näiteks ei saa puu kunagi sisaldada tsüklit). Andmestruktuuri taustaprogrammi määrab kindlaks selle seos andmestruktuuri sisaldava graafidokumendiga.

#### Viidatüübid

Viidatüüpidega saab kindlaks määrata erinevad andmestruktuurides kasutatavad viidad. Viidatüüp võib näiteks saada konkreetse paigutuse (sisuliselt värvi) ja sellele on lihtne skriptis ligi pääseda ainult konkreetset tüüpi viita määrates. Viitade tüüpiline kasutamine on andmestruktuuride metaseoste teostamine, mis visualiseerivad andmeelementide seoseid (nt. visualiseerivad kommunikeerimishuve). Ka siis, kui sinu skript peab tuvastama konkreetset laadi sesoseid (nt. puu ja risti seoseid sügavutiotsingu algoritmi korral), on viidatüübid elegantne viis seda teostada.

#### Andmetüübid

Mitmegi andmestruktuuri probleemi korral tuleks andmeelementide kogum jagada eri tüüpi rühmadeks (näiteks klastri- või katvusprobleemide korral). Samuti võib olla tulus algoritmi täitmiseks kindlaks määrata, et andmeelemendi tüüp väljendab konkreetset tüüpi (nt. laiutiotsingu korral). Sellisel juhul on mõttekas defineerida andmetüübid. Igal andmetüübil on oma ikoon ja teatavaid andmetüüpe on hõlpus kasutada skriptides.

#### Dünaamilised omadused

Kõigil andmeelementidel ja viitadel võib olla hulk omadusi. Mõned neist on vaikeväärtused andmestruktuuri taustaprogrammist. Sellest kõneleb lähemalt andmestruktuuride taustaprogrammide dokumentatsioon. Täiendavate omaduste lisamiseks andmeelementidele ja viitadele võib neile lisada dünaamilisi omadusi. Iga dünaamilist omadust tuvastab selle nimi ning sellega võib olla seotud mis tahes väärtus. Nimi peab algama tähega ning võib sisaldada ainult tähti, numbreid ja märki '_'. Eesti täpitähti kasutada ei tohi. Kui üritad omaduse nimes kasutada mõnda keelatud märki, omadust ei muudeta.

Dünaamilise omaduse lisamiseks kasuta vastavate elementide kontekstimenüüst avatavaid dialooge Andmete omadused ja Viida omadused või skripti funktsioone, nagu selgitab .

Samuti võib kasutada skripte. Selles peab olema lihtsalt `add_property` koos omaduse nime ja väärtusega. Selle järel võib väärtuste määramiseks või hankimiseks kasutada node/pointer.propertyName.

Siin on näide, kuidas kasutada dünaamilisi omadusi andmestruktuuri taustaprogrammis "Graaf".

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

### Õppematerjal

Selles osas loome näidisprojekti, et uurida mõningaid &rocs;i tähtsamaid võimalusi. Eesmärk on luua graaf ja skript, mis näitlikustaksid minimaalse tipukatte probleemi lahendamiseks loodud lihtsat teist järku aproksimeerimise algoritmi. Minimaalse tipukatte probleemi korral püütakse leida minimaalse suurusega graafisõlmede alamhulka C, mille puhul iga graafi seos oleks ühendatud vähemalt ühe C tipuga. See probleem on NP-keerukusega ja me tahame siin näidata, kuidas leida teise järgu lähendust, leides sobivuse antud graafis (edaspidi kasutame graafialgoritmide puhul levinud mõisteid: graaf on andmestruktuur, tipud andmeelemendid, seosed viidad)

Meie eesmärk on visualiseerida sobiva ja minimaalse tipukatte vastavust. Selleks tuleb kindlaks määrata kaks viidatüüpi: üks kujutab sobivaid ja teine tavalisi seoseid, samuti kaks andmetüüpi, mida me kasutame esitamaks C-s sisalduvaid ja selles mittesisalduvaid tippe.

#### Graafi genereerimine

Andmestruktuuri taustaprogrammi "Graaf" puhul pakub &rocs; tööriista, mis võib graafe genereerida. Valime menüükäsu Graafidokument Tööriistad Graafi genereerimine. Nüüd genereerime "juhusliku graafi" 30 tipu, 90 seose ja 1 seemnega (seeme on juhusliku graafi genereerija algseeme, sama seemne mitmekordsel kasutamisel saadakse samasugused, korratavad graafid). Lõpuks muudame andmestruktuuri paneelil graafi nime ja anname sellele nimeks `testgraph`.

#### Tüüpide loomine

Avame andmestruktuuri paneeli nupuga Dokumendi omadused aktiivse graafidokumendi andme- ja viidatüüpide omaduste dialoogi. Andmetüüpide juures lisame uue tüübi "C", mis saab automaatselt ID `1`. Valime sellele tüübile ikooniks serveripildi. Nüüd lülitume viidatüübi leheküljele ja lisame uue viidatüübi "matching". See saab automaatselt ID `1` ja me anname talle sinise värvi.

#### Algoritm

Lõpuks tuleb teostada lähenduse algoritm. Selleks kasutame järgmist teostust:

    var E = testgraph.list_edges(); // set of unprocessed edges
    var C = new Array();            // matching edges
    while (E.length
    > 0) {
        var e = E[0];        // we take first edge e={u,v}
        var u = e.start();
        var v = e.end();
        e.set_type(1);        // set edge to be a matching edge
        E.shift();            // remove e (i.e., E[0]) from edge list
        C.push(u);            // add u to C
        C.push(v);            // add v to C

        // mark u,v as nodes in C
        u.set_type(1);
        v.set_type(1);

        // remove from E all edges incident to u or v
        var adjacent = u.adj_edges();
        for (var i=0; i < adjacent.length; i++) {
            var index = E.indexOf(adjacent[i]); // find the index
            if (index!=-1) {
                E.splice(index, 1); // remove it if really found
            }
        }
        var adjacent = v.adj_edges();
        for (var i=0; i < adjacent.length; i++) {
            var index = E.indexOf(adjacent[i]); // find the index
            if (index!=-1) {
                E.splice(index, 1); // remove it if really found
            }
        }
    }
    output("Tipukate sisaldab " + C.length + " tippu.");

#### Algoritmi täitmine

Lõpuks tuleb algoritm ka täita. Selleks käivitame selle skripti juhtimise paneelil klõpsuga nupule Käivita.

## &rocs;i kasutajaliides

### Kasutajaliidese põhielemendid

Kasutajaliides jaguneb mitmeks loogiliseks osaks, nagu on näha ka juuresoleval pildil.

&rocs;i liidese graafilised elemendid.
&rocs;i liidese graafilised elemendid.

Dokumendivalija

  Sellel ülal asuval menüüribal tuleb valida aktiivne dokument ja andmestruktuur. Samuti saab siin luua ja kustutada andmestruktuure ning pääseda ligi andmestruktuuri omadustele.

Visuaalne graafiredaktor

  See on lõuend, kus saab luua ja muuta andmestruktuure. Paremklõpsuga lõuendil, andmeelementidel või viitadel saab avada kontekstimenüü. Visuaalse graafiredaktori tööriistariba vahenditega saab muuta visuaalse graafiredaktori lõuendi elemente.

Visuaalse graafiredaktori riba

  Siin paiknevad kõik visuaalse graafiredaktori tööriistad. Kasutades nuppe Lisa andmed või Lisa ühendus, saab vastavalt luua uusi elemente või elemente ühendada. Uued andmeelemendid lisatakse andmestruktuuri, mis on parajasti valitud dokumendivalijas. Pane tähele, et nii nupul Lisa andmed kui ka nupul Lisa ühendus on oma kontekstimenüü, milles saab valida loodavate elementide tüübi. Täpsemalt kõneleb sellest .

Külgriba

  Paremal näeb külgriba, kus paikneb mitu töövoole tulusat tööriista:

  - Elemenditüübid: see vidin võimaldab kasutada kõiki saadaolevaid viida- ja andmetüüpe.

  - Päevik: igal projektil on oma päevik, millesse saab näiteks üles tähendada ülesanded, tulemused või vaatlusandmed.

  - Dokumentatsioon: selle vidina abil saab otse kasutada käsiraamatut ning selle vahendusel ka skripti dokumentatsiooni.

Skriptiredaktor

  Selles tekstiredaktoris saab kirjutada algoritme, nagu selgitab täpsemalt . Korraga võib tegutseda ka mitme algoritmi kallal, kasutades selleks eri kaarte. Kui skripti tehtud muudatused on salvestamata, näeb kaardi sakil väikest ketast.

Skripti väljund

  Selles tekstialas näeb kas sinu algoritmi silumisteavet või skripti väljundit sõltuvalt vidina ülaosas langetatud valikust. Kui skript tekitab vigu, valitakse automaatselt silumisväljund.

Juhtelemendid

  Siin tegeldakse skriptide töölepanekuga. Parajasti avatud skripti saab täitma asuda, kui klõpsata nupule Käivita. Skripti käivitamise järel saab selle täitmist ka peatada, kui klõpsata nupule Peata. Pane tähele, et täitmisviisi Üks samm kasutamisel peatub täitmine ainukt konkreetsete võtmesõnade juures (vt. ).

### Tööriistaribad

Siin on mitmesugused visuaalse graafiredaktori tööriistaribad, mis võimaldavad vajalikke võimalusi kasutada üheainsa klõpsuga. Vaikimisi näeb järgmisi tööriistaribasid:

- Peamine tööriistariba

- Joondusriba

#### Peamine tööriistariba

Peamine tööriistariba koosneb järgmistest toimingutest. Toimingule klõpsamine tähendab seda, et saad hiirega rakendada antud toimingu visuaalse graafiredaktori lõuendis:

- Liiguta: elementide valimiseks klõpsa lõuendi tühjal alal, hoia hiirenupp all ja joonista ristkülik, mis sisaldab mõningaid andmeelemente ja/või viitu, mis sel juhul valitakse, või klõpsa vahetult valimata elemendi peal selle valimiseks. Kui klõpsad valitud elemendil või elementidel, saab hiirenuppu all hoides ja hiirt liigutades elemente liigutada. Valitud elemente saab liigutada ka nooleklahvidega.

- Lisa andmed: klõpsa visuaalse graafiredaktori lõuendil vajalikus kohas ja loo uus andmeelement, mis kuulub parajasti valitud andmestruktuurile. Hiirekursorit nupul all hoides ilmub kontekstimenüü, mille abil saab valida loodavate andmeelementide andmetüübi (muidugi kui eri andmetüüpe saab ikka kasutada).

- Lisa ühendus: klõpsa mõnel andmeelemendil, hoia hiir all ja tõmba joon teise andmeelemendini, milleni viit/seos peab ulatuma. Seda toimingut saadab edu ainult siis, kui aktiivne graaf võimaldab sellist seost lisada (nt. orienteerimata graafil ei ole lubatud lisada kahe andmeelemendi vahele mitut seost). Hiirekursorit nupul all hoides ilmub kontekstimenüü, mille abil saab valida loodavate viitade viidatüübi (muidugi kui eri viidatüüpe saab ikka kasutada).

- Kustuta: klõpsa elemendil selle kustutamiseks. Kui kustutad tipu, kustutatakse ka kõik sellega seotud seosed.

- Suurendus: klõpsa lõuendil, hoia &HVN; all ja joonista sellega ristkülik. Lõuendit suurendatakse, nii et näed ainult valitud osa. Samuti võib suurendada või vähendada hiirerattaga. Topeltklõps &HVNga; taastab esialgse suurenduse.

#### Joondusriba

Lisada võib ka joondusriba. Mõnele selle riba toimingule klõpsates saab vahetult mõjutada parajasti valitud tippe:

- Üles: andmeelemendid joondatakse kõige ülemise andmeelemendi vertikaalse positsiooni järgi. See puudutab ainult vertikaalset positsiooni.

- Keskele: andmeelementide joondamine kõigi valitud admeelementide vertikaalsete positsioonide keskme järgi. See puudutab ainult vertikaalset positsiooni.

- Alla: andmeelemendid joondatakse kõige alumise andmeelemendi vertikaalse positsiooni järgi. See puudutab ainult vertikaalset positsiooni.

- Vasakule: andmeelemendid joondatakse kõige vasakpoolsema andmeelemendi horisontaalse positsiooni järgi. See puudutab ainult horisontaalset positsiooni.

- Keskele: andmeelemendid joondatakse kõige ülemise andmeelemendi horisontaalse positsiooni järgi. See puudutab ainult horisontaalset positsiooni.

- Paremale: andmeelemendid joondatakse kõige parempoolsema andmeelemendi horisontaalse positsiooni järgi. See puudutab ainult horisontaalset positsiooni.

- Ring: andmeelemendid joondatakse ringi, mille diameeter võrdub andmeelementide maksimaalse vahemaaga. Andmeelemendid paigutatakse samas järjekorras nagu vaates alates andmeelementide raskuskeskmest.

- Kattuvate seoste minimeerimine: valitud andmeelemendid korraldatakse ümber kattuvate seoste arvu minimeerikiseks (rakendatakse Fruchterman-Reingoldi algoritmi).

### Graafidokumentide töövoog

&rocs;i projekt koosneb vähemalt ühest graafidokumendist, mida saab muuta visuaalses graafiredaktoris. Lisaks võib iga dokument sisaldada suvalise arvu andmestruktuure. Dokumendi andmestruktuurid kasutavad kõik üht ja sama andmestruktuuri taustaprogrammi. Allpool selgitatakse, kuidas liikuda dokumentide vahel ja kuidas luua uusi.

#### Dokumendivalija riba

Dokumendivalija ribal saab valida aktiivse graafidokumendi ja ka aktiivse andmestruktuuri. Kui luua visuaalse graafiredaktori tööriistadega andmestruktuuride elemente, lisatakse need automaatselt aktiivsesse andmestruktuuri. Samuti saab selle riba abil aktiivses dokumendis kustutada olemasolevaid või luua uusi andmestruktuure.

- Uus: selle abil saab luua uue andmestruktuuri, mille puhul kasutatakse parajasti kasutusel oleva andmestruktuuri taustaprogrammi automaatset nimemustrit. Loodud andmestruktuur lisatakse aktiivsesse graafidokumenti.

- Kustuta: selle abil saab kustutada andmestruktuuri, mis on parajasti valitud aktiivse dokumendi andmestruktuuri valijas.

- Andmestruktuuri omadused: sellega saab avada dialoogi, kus näeb ja saab muuta andmestruktuuri omadusi.

- Dokumendi omadused: selle abil saab avada dialoogi, kus näeb ja saab muuta nii dokumendi omadusi kui ka dokumendi andme- ja viidatüüpe.

Peamine tööriistariba.
Dokumendivalija riba.

#### Graafidokumentide loomine ja import

Uue graafidokumendi loomiseks või olemasoleva lisamiseks projekti kasuta menüükäsku Projekt Uus graafidokument või Projekt Impordi &rocs;i graaf. Samuti võib importida mõne muu rakenduse graafidokumendi (täpsemalt kõneleb sellest ).

## Algoritmide kirjutamine ja täitmine &rocs;is

&rocs; kasutab seesmiselt QtScripti skriptimootorit, mis on otseselt JavaScripti mootor. See tähendab, et kõik teostatud algoritmid peavad kasutama JavaScripti. Kuidas JavaScript toimib ja kuidas JavaScripti koodi kirjutada, väljub käsiraamatu piiridest, ehkki me selgitame siin, kuidas pääseda skriptimootoriga ligi andmestruktuuridele, andmeelementidele ja viitadele. Et tegelikult ei kasutata kunagi vahetut andmestruktuuri objekti, vaid seda, mida pakub parajasti kasutusele andmestruktuuri taustaprogramm, laiendab vastav taustaprogramm andmestruktuuri ja sestap tuleb kasutada just seda spetsiaalset funktsionaalsust. Eriti tasub tähele panna, et andmestruktuuri taustaprogrammid kasutavad oma eripärast terminoloogiat (tipud ja seosed graafides, lehed ja juured puudes jne.).

Oluline on tähele panna, et skriptimootori tehtud muudatused kajastuvad otseselt omadustes visuaalse graafiredaktori lõuendil. Niisiis muudavad skriptid ka tegelikult andmestruktuure.

### Baasandmestruktuurielemendid

Iga taustaprogramm pakub konkreetse valiku funktsioone ja omadusi enda andmestruktuuridele ja nende elementidele. Kuid samamoodi pakub iga taustaprogramm omadusi ja funktsioone, mis kehtivad baasandmestruktuurile. Seepärast kehtib kõik siin räägitav kõigi andmestruktuuri taustaprogrammide puhul.

#### Baasandmestruktuuride omadused

Andmestruktuure tuvastatakse nende nime järgi. Oletades, et oled loonud andmestruktuuri nimega `testgraph`, saab seda andmestruktuuri kasutada lihtsalt selle identifikaatori abil. Näiteks kõigi selle andmestruktuuri andmeelementide massiivi hankimiseks tuleks skripti kirjutada `testgraph.list_nodes();`.

##### Baasandmestruktuuri omadused ja funktsioonid

Igal andmestruktuuril `testgraph` on järgmised omadused, mida saab lugeda või kirjutada `testgraph.property` vahendusel:

    string name  // andmestruktuuri identifikaator

#### Baasandmeelemendi omadused ja funktsioonid

Igal andmeelemendil on järgmised omadused, mida saab lugeda või kirjutada:

    double x      // aktiivse asukoha x-koordinaat
        double y      // aktiivse asukoha y-koordinaat
        double width  // suurus
        string value  // väärtus
        int id        // andmeelemendi unikaalne identifikaator
        string name   // nimi
        string color  // värv 16ndsüsteemis

Lisaks saab kõiki andmeelemendi dünaamilisi omadusi kasutada nende nime järgi.

Iga andmeelemendi objekt pakub järgmisi meetodeid:

    int type();                         // andmeelemendi andmetüüp
        int set_type(int);                  // andmeelemendi andmetüübi määramine
        void add_property(string name,      // määratud nime ja väärtusega dünaamilise omaduse lisamine andmeelemendile
                          string value);
        array adj_data();                   // külgnevate andmete loend
        array adj_pointers();               // külgnevate viitade loend
        array input_pointers();             // sisendviitade loend
        array output_pointers();            // väljundviitade loend
        array loop_pointers();              // silmust moodustavate viitade loend
        array connected_pointers(target);   // sihtmärgile 'target' osutavate  viitade loend
        void  remove();                     // andmeelemendi eemaldamine

#### Baasviida omadused ja funktsioonid

Igal viidal on järgmised omadused, mida saab lugeda või kirjutada:

    string color  // värv 16ndsüsteemis
        string value  // väärtus
        string name   // nimi
        double width  // laius
        string style  // stiili väärtus: punkt (dot), kriips (dash), punkt-kriips (dash dot), ühtlane (solid)

Lisaks saab kõiki viida dünaamilisi omadusi kasutada nende nime järgi.

Iga viidaobjekt pakub järgmisi meetodeid:

    int type();                         // viida viidatüüp
        int set_type(int);                  // viida viidatüübi määramine
        void add_property(string name,      // määratud nime ja väärtusega dünaamilise omaduse lisamine andmeelemendile
                          string value);
        node start();                       // viida algustipp
        node end();                         // viida sihttipp
        void remove();                      // viida eemaldamine

### Graafi taustaprogramm

#### Graafi omadused ja funktsioonid

##### Graafi taustaprogrammi eriomadused

Andmestruktuuri omaduste dialoog võimaldab kasutada graafi taustaprogrammile eripäraseid seadistusi. Graafi tüüp võimaldab valida graafi tüübi. See võib olla üks järgmistest:

- Graaf: graaf, milles ei saa mitu korda esineda samad seosed (mis on määratud algus- ja lõpp-punktiga).

- Multigraaf: graaf, milles saavad mitu korda esineda samad seosed (mis on määratud algus- ja lõpp-punktiga).

##### Graafi struktuur

Kui andmestruktuuriobjekti tüüp on "graaf", saab välja kutsuda järgmisi liikmesfunktsioone:

    array list_nodes();                   // graafi kõigi tippude loend
        array list_nodes(int type);           // kõigi antud tüüpi tippude loend
        array list_edges();                   // graafi kõigi seoste loend
        array list_edges(int type);           // kõigi antud tüüpi seoste loend
        node add_node(name);                  // uue tipu lisamine ja selle tagastamine
        edge add_edge(node from, node to);    // uue seose lisamine alates (from) kuni (to) ja selle tagastamine
        array overlay_edges(int overlayID);   // kõigi seoste loend määratud ülekattes
        edge add_overlay_edge(node from,
                              node to,
                              int overlayID); // määratud viidatüübiga seose lisamine määratud ülekattesse

##### Graafi tipud

Kui andmestruktuuriobjekti tüüp on "graaf", saab lisaks omadustele, mida pakuvad andmeelemendid, graafi tippudel välja kutsuda järgmised liikmesfunktsioonid:

    array adj_nodes();                    // kõigi külgnevate tippude loend
        array adj_edges();                    // ühendatud seoste loend
        array input_edges();                  // sisendseoste loend
        array output_edges();                 // väljundseoste loend
        array loop_edges();                   // kõigi tipul silmuse tegevate seoste loend
        array connected_edges(node target);   // kõik seosed, mis ühenduvad selle tipu kui sihtmärgiga (target)

##### Graafi seosed

Kui andmestruktuuriobjekti tüüp on "graaf", on saadaval ainult baasandmestruktuuri omadused.

#### Graafi stuktuuri algoritmid

Graafi taustaprogramm pakub mõningaid erifunktsioone, mida saab kasutada skriptimootori vahendusel.

Lühima teekonna arvutamine

  Arvutab lühima tee tippude algus ja lõpp vahel. Mõlemad tipud peavad asuma ühel graafil. Arvutamine arvestab ka seda, kas graaf on orienteeritud või orienteerimata.

          array dijkstra_shortest_path node algus node lõpp

Lühima teekonna vahemaad

  Arvutab lühima tee vahemaad tipust algus kõigi graafi teiste tippudeni. Arvutamine arvestab ka seda, kas graaf on orienteeritud või orienteerimata.

          array distances node algus

### Lingitud loendi taustaprogramm

#### Lingitud loendi omadused ja funktsioonid

##### Lingitud loendi struktuur

Kui andmestruktuuriobjekti tüüp on "lingitud loend", saab välja kutsuda järgmisi liikmesfunktsioone:

    node begin();                           // lingitud loendi peasõlme määramine
        setBegin(node begin):                   // tipu määramine loendi alguseks ja loendi ümberkorraldamine
        createNode();                           // loendi uue tipu loomine

##### Lingitud loendi tipud

Kui andmestruktuuriobjekti tüüp on "lingitud loend", saab lisaks omadustele, mida pakuvad andmeelemendid, graafi tippudel välja kutsuda järgmised liikmesfunktsioonid:

    node front();                           // tipu eelkäija tagastamine

##### Lingitud loendi seosed

Kui andmestruktuuriobjekti tüüp on "lingitud loend", on saadaval ainult baasandmestruktuuri omadused.

### Juurega puu taustaprogramm

#### Juurega puu omadused ja funktsioonid

##### Juurega puu taustaprogramm

Andmestruktuuri omaduste dialoog võimaldab kasutada graafi taustaprogrammile eripäraseid seadistusi. Omaduse Kõigi viitade näitamine märkimisel näidatakse kõiki viitu puu tippude vahel. Kui see on märkimata, koondatakse mitu viita samade tippude vahel üheks.

##### Juurega puu struktuur

Kui andmestruktuuriobjekti tüüp on "juurega puu", saab lugeda või kirjutada järgmisi omadusi:

    ShowAllPointers     // tõene (true), kui näidatakse kõiki seoseid, väär (false), kui mitu seost tuleb ühendada

Kui andmestruktuuriobjekti tüüp on "juurega puu", saab välja kutsuda järgmisi liikmesfunktsioone:

    node add_data(string name);         // määratud nimega tipu lisamine puule
        void set_root_node(node root);      // puu juurtipu määramine
        node root_node();                   // puu juurtipu tagastamine

##### Juurega puu tipud

Kui tipuobjekti tüüp on "juurega puu", saab lugeda või kirjutada järgmisi omadusi:

    int numberOfChilds                  // määratud tipu (lubatud) järglaste arvu määramine
        node left_child                     // ainult loetav: vasakpoolsest järglasest tipp
        node right_child                    // ainult loetav: parempoolsest järglasest tipp
        node node_parent                    // ainult loetav: eellasest tipp

Kui tipuobjekti tüüp on "juurega puu", saab välja kutsuda järgmisi liikmesfunktsioone:

    node add_left_child(node child);    // vasaku järglase lisamine
        node add_right_child(node child);   // parema järglase lisamine
        node add_child(node child, int i);  // järglase lisamine tipu i-nda järglasena
        node add_node_parent(node child);   // eellase lisamine (õnnestub ainult siis, kui eellast pole veel määratud)
        node left_child();                  // parema järglase tagastamine
        node right_child();                 // vasaku järglase tagastamine
        node child_at(int i);               // tipu i-nda järglase tagastamine
        node node_parent();                 // tipu eellase tagastamine

##### Juurega puu seosed

Kui andmestruktuuriobjekti tüüp on "juurega puu", on saadaval ainult baasandmestruktuuri omadused.

### Skripti täitmise juhtimine

#### Päisefailid

Skriptidokument võib kaasata ka teisi skripte. See võib olla abiks skriptidokumendi mahu vähendamisel ja loetavuse parandamisel. Menüükäsuga Skriptidokument Võimalikud päised saab teada skriptifailide nimekirja, mis on &rocs;iga juba kaasas ja mida on võimalik sel moel kaasta. Skriptifaili saab kaasata järgmise käsuga:

    include_script(string path);            // skriptifaili suhteline või absoluutne asukoht

#### Skripti väljund

Algoritmi täitmise ajal näeb programmi- ja silumisväljundit alas Silumis- ja skriptiväljund. Kui skriptimootor tuvastab skriptis süntaksivigu, näeb seda ka silumisteatena. Pane tähele, et silumisväljundis näeb ka kõiki programmi sõnumeid (neid näidatakse rasvases kirjas).

Teksti, mida näidatakse skriptiväljundis, saab juhtida järgmiste funktsioonidega:

    output(string message);            // sõnumi näitamine skriptiväljundina
        debug(string message);             // sõnumi näitamine silumisväljundina

#### Skripti täitmise juhtimine

Skripte saab täita eri moel.

Teksti, mida näidatakse skriptiväljundis, saab juhtida järgmiste funktsioonidega:

- Käivita: skripti täitmine algusest lõpuni.

- Peata: skripti täitmise peatamine (saab kasutada ainult siis, kui skripti täidetakse).

- Üks samm: skripti täitmine kuni ühe sammu lõpuni. Samm lõpeb, kui skript kutsub välja funktsiooni `interrupt()`:

      interrupt();    // sammu lõpetamine

- Silu: skripti täitmine silumisrežiimis. See avab QtScripti silumisdialoogi.

## Import ja eksport

### &rocs;i projektide vahetamine

&rocs;i projekte saab importida ja eksportida arhiveeritud `.tar.gz`-failidena. Nende arhiivide abil saab projekte teistega vahetada. Importida ja eksportida saab vastavalt menüükäskudega Fail Impordi projekt ja Fail Ekspordi projekt.

### Graafidokumentide import ja eksport

&rocs; toetab praegu importimisel ja eksportimisel järgmisi failivorminguid:

- DOT-failid, tuntud ka kui Graphviz-failid

- GML-failid

- TGF (Trivial Graph Format) failid

#### Trivial Graph failivorming

Trivial Graph Format (TGF) on lihtne graafe kirjeldav tekstipõhine failivorming. TGF-fail koosneb tipudefinitsioonide loendist, mis seovad tippude ID-d pealdistega ja millele järgneb seoste loend. Selles vormingus saab igal tipul olla ainult üks pealdis ja igal seosel ainult üks väärtus. &rocs; tõlgendab imporditud graafe orienteerimata graafidena. Eksporditud graafid sisaldavad ühenduse kohta kaks seost, kui ühendused on kahesuunalised.

##### Vormingu spetsifikatsioon

- FAil algab tippude loendiga (üks tipp rea kohta), millele järgneb rida, millel on ainult märk "#". Sellele järgneb seoste loend (üks seos igal real).

- Tipp koosneb täisarvust (identifikaator), millele järgneb tühik, millele järgneb suvaline string.

- Seos koosneb kahest tühikuga eraldatud täisarvust (identifikaatoritest), millele järgneb tühik, millele järgneb suvaline string. Eeldatakse, et suunaga seos kulgeb esimeselt identifikaatorilt teisele.

##### Näide

    1 algustipp
    2 saatja
    3 neel
    #
    1 2 sinine
    2 1 punane
    2 3 roheline

#### DOT-keele / Graphcizi graafi failivorming

DOT-keel on lihttekstis graafi kirjeldamise keel, mis võimaldab nii graafide inimsilmale kergesti haaratavat esitamist kui ka tõhusat töötlemist graafipaigutusprogrammide polt. DOT on Graphvizi graafide visualiseerimise komplekti vaikimisi failivorming, aga seda kasutavad ka paljud muud graafitööriistad. DOT-faili tavaline lõpp on .gv või .dot.

##### Toetamata võimalused

&rocs; suudab parsida kõiki graafifaile, mis sisaldavad graafi, mis on loodud DOT-keele spetsifikatsiooni alusel http://www.graphviz.org/content/dot-language. Keele omadused on täielikult toetatud, ehkki kehtivad järgmised erandid:

- alamgraafik (subgraph): et &rocs; ei kasuta alamgraafiku kontseptsiooni, imporditakse alamgraafikud lihtsalt andmeelementide ja ühenduste kogumina. Eriti tuleb tähele panna, et ei impordita ühendusi alamgraafikust või alamgraafikusse.

- &HTML;-i ja &XML;-i atribuudid: atribuudid (näiteks pealdised), mis sisaldavad &HTML;-i või &XML;-i süntaksit, loetakse sisse muutmata kujul. Eriti tuleb tähele panna, et neist atribuutidest ei loeta välja fontide ja stiilide kohandamist.

##### Näide

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

## Autorid ja litsents

&rocs;

Rakenduse autoriõigus:

- Autoriõigus 2008: Ugo Sangiori (ugorox AT gmail.com)

- Autoriõigus 2008-2012: Tomaz Canabrava (tcanabrava AT kde.org)

- Autoriõigus 2008-2012: Wagner Reck (wagner.reck AT gmail.com)

- Autoriõigus 2011-2012: Andreas Cord-Landwehr (cordlandwehr AT googlemail.com)

Dokumentatsiooni autoriõigus:

- Dokumentatsiooni autoriõigus 2009: &Anne-Marie.Mahfouf; &Anne-Marie.Mahfouf.mail;

- Dokumentatsiooni autoriõigus 2009: Tomaz Canabrava (tcanabrava AT kde.org)

- Dokumentatsiooni autoriõigus 2011-2012: Andreas Cord-Landwehr (cordlandwehr AT googlemail.com)

Tõlge eesti keelde: Marek Laane bald@smail.ee

&underFDL; &underGPL;

## Paigaldamine

### &rocs;i hankimine

&install.intro.documentation;

### Kompileerimine ja paigaldamine

&install.compile.documentation;

&documentation.index;