# El manual de &rocs;

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

&traductor.Antoni.Bella;
2009
Tomaz Canabrava
2011-2012
Andreas Cord-Landwehr
02-12-2012
1.8.0 &kde; 4.10
&FDLNotice;

&rocs; és una eina de teoria de grafs per al KDE.

KDE
kdeedu
matemàtiques
matemàtica
grafs
node
aresta

## Introducció

En aquest capítol oferim una visió general de les principals característiques i el flux de treball de &rocs;. Per al lector impacient, que vol començar a utilitzar immediatament &rocs;, li suggerim que almenys llegeixi i que utilitzi com a referència a l'hora d'escriure algorismes.

### Objectius, destinataris i flux de treball

&rocs; és un IDE per a la teoria de grafs per a tothom interessat en el disseny i anàlisi d'algorismes de graf. Això inclou explícitament

- professors, que volen demostrar algorismes als seus estudiants,

- estudiants, que volen entendre i veure com es realitza el seu algorisme,

- i tothom, que està interessat en les estructures de dades i algorismes.

Per a tots aquests usuaris, &rocs; ofereix una manera fàcil d'utilitzar l'editor d'estructura de dades per a crear estructures de dades, un motor per crear scripts de gran abast per executar algorismes i diverses eines d'ajuda per a les vostres simulacions i experiments.

El flux de treball típic quan s'utilitza &rocs; és començar creant un graf amb l'editor visual de grafs. Ho podeu fer ja sigui a mà, afegint elements de dades i la seva connexió, o utilitzant un dels generadors d'estructura de dades (si estan disponibles per al dorsal d'estructura de dades actualment seleccionat). Els generadors d'estructura de dades es poden trobar a Document de graf Eines Genera el graf. A més, podeu assignar valors als elements de l'estructura de dades, ja sigui a mà o utilitzant Document de graf Eines Assigna valors. Finalment, podeu escriure el vostre algorisme en JavaScript i executar-lo amb l'estructura de dades que acabeu de crear. Tots els canvis que realitzi el vostre l'algorisme a l'estructura de dades seran directament visibles en l'editor visual de grafs.

Una captura de pantalla de &rocs;.
Una captura de pantalla de &rocs;

### &rocs; en poques paraules

En aquesta secció proporcionem una visió general compacta dels elements centrals de &rocs;. Expliquem els conceptes importants de les estructures de dades, dorsals de les estructures de dades i tipus d'elements. La comprensió d'aquests conceptes és útil per entendre com es creen i es modifiquen les estructures de dades en &rocs;.

En general &rocs; treballa amb projectes: En obrir &rocs; es crea un projecte buit i el podeu substituir carregant o important un altre projecte. En sí, un projecte consisteix en documents de graf i scripts.

#### Documents de graf i dorsals d'estructura de dades

Un document de graf representa el contingut d'una pissarra en blanc a l'editor visual de grafs. En sí, un document de graf pot contenir diverses estructures de dades alhora, però només un dorsal d'estructura de dades. Els dorsals d'estructura de dades estan presents en diversos tipus de graf (grafs en general, llistes enllaçades, arbres arrelats) i proporcionen característiques addicionals als seus tipus de graf específic. Això pot posicionar automàticament els elements, jocs d'icones especials o un conjunt ampliat de funcions d'script per utilitzar en els vostres algorismes. (Per a més detalls veure la secció corresponent del manual). És possible canviar el dorsal de l'estructura de dades d'un document de graf, tot i que es pot perdre la informació (&pex;, les arestes d'un cercle en un graf general no seran afegides a un d'arbre, si canvieu al dorsal d'arbre arrelat).

Els documents de graf també formen la base per a definir tipus de punter i tipus de dades.

#### Estructures de dades

Les estructures de dades són la base de tot el treball en &rocs;. Podeu afegir una o diverses a un document de graf, afegir elements de dades (nodes, dades) i punters a elles i modificar-los mitjançant scripts. Per això, cada estructura de dades té el seu nom únic pel qual es pot accedir des dels scripts. Segons el dorsal de l'estructura de dades triat, pot passar que no es puguin modificar arbitràriament les estructures de dades (&pex;, un arbre mai podrà contenir un cicle). El dorsal de l'estructura de dades està determinat pel dorsal d'estructura de dades associat amb el document de graf corresponent que conté l'estructura de dades.

#### Tipus de punters

Amb els tipus de punter podeu definir diferents tipus de punters que s'utilitzaran en les vostres estructures de dades. És a dir, un tipus de punter pot obtenir un disseny individual (essencialment un color), de manera que serà fàcil accedir als punters només d'un tipus específic des dels vostres scripts. Els casos típics d'ús de punters poden ser la implementació dels meta-arestes a les vostres estructures de dades que visualitzen les relacions entre els elements de dades (&pex;, visualitzar els interessos de comunicació). Però, a més, si els vostres scripts han d'identificar tipus específics d'arestes (&pex;, les arestes dels arbres i la creu en l'algorisme de cerca de primera profunditat), els tipus de punter poden ser una manera elegant d'implementar-ho.

#### Tipus de dades

En diversos problemes d'estructura de dades, un conjunt d'elements de dades s'han de separar en grups de diferents tipus (&pex;, problemes d'agrupament o de cobertura). O és útil per a l'execució d'un algorisme per especificar un tipus d'element de dades per expressar un tipus específic (&pex;, per a la cerca primer en amplada). Per als casos d'ús d'aquest tipus podeu definir tipus de dades. Cada tipus de dades té la seva pròpia icona i podeu accedir als tipus de dades d'algun tipus fàcilment des dels vostres scripts.

#### Propietats dinàmiques

Cada element de dades i el punter pot tenir moltes propietats. Algunes d'aquestes propietats són per omissió del dorsal d'estructura de dades. Per a més detalls consulteu la documentació del dorsal d'estructura de dades. Per afegir propietats addicionals als elements de dades i punters, hi podeu afegir propietats dinàmiques. Cada propietat dinàmica s'identifica pel seu nom i pot contenir qualsevol valor associat amb ella. El nom ha de començar amb una lletra (a-z o A-Z) i només pot contenir lletres, nombres i «_». Si intenteu utilitzar qualsevol caràcter no vàlid en el nom de la propietat, la propietat no serà canviada.

Per afegir propietats dinàmiques, utilitzeu els diàlegs Propietats de les dades i Propietats del punter des dels menús contextuals dels respectius elements o les funcions de l'script, com s'explica a .

També podeu utilitzar els scripts. Només necessitareu utilitzar la `add_property` amb el nom i el valor de la vostra propietat. Després d'això, podreu utilitzar el node/pointer.propertyName per establir/obtenir els valors.

Heus aquí un exemple de com utilitzar les propietats dinàmiques amb el dorsal d'estructura de dades «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

### Guia d'aprenentatge

En aquesta secció volem crear un projecte d'exemple per explorar algunes de les característiques més importants de &rocs;. L'objectiu és crear un graf i un script que il·lustri un algorisme d'aproximació a 2 simple per al problema cobertura de vèrtexs mínima. En aquest problema s'han de trobar un subconjunt de nodes del graf C de mida mínima, de manera que cada aresta del graf estarà connectada a almenys un node de C. Se sap que aquest problema és NP-complex i volem il·lustrar com trobar una aproximació de factor 2 cercant una coincidència en el graf donat (en el que segueix utilitzarem la terminologia comuna per als algorismes de graf: un graf és l'estructura de dades, els nodes són els elements de dades i les arestes són els punters).

El nostre objectiu és visualitzar la correspondència de les coincidències i la cobertura de vèrtexs mínima. Per això, volem especificar dos tipus de punters, un per mostrar les arestes coincidents i un per mostrar arestes comunes, així com dos tipus de dades que utilitzarem per distingir els nodes continguts en C i els que no estan continguts en C.

#### Generar un graf

Per al dorsal d'estructura de dades «Graf», &rocs; ofereix una eina d'ajuda que pot generar grafs. Anem a Document de graf Eines Genera el graf. Cal que generem un «Graf aleatori» amb 30 nodes, 90 arestes i amb 1 llavor (la llavor és la llavor inicial per al generador de grafs aleatoris; si s'utilitza la mateixa llavor diverses vegades es tornaran a reproduir els mateixos grafs). Finalment, modificarem el nom del graf en el plafó de l'estructura de dades i cridarem al graf `testgraph`.

#### Crear els tipus

Utilitzarem el botó Propietats del document en el plafó de l'estructura de dades per obrir el diàleg de propietats per als tipus de dades i de punter del document de graf actual. Per al tipus de dades afegirem un nou tipus anomenat «C», el qual obtindrà automàticament l'ID `1`. Per aquest tipus seleccionarem la imatge del servidor com a icona. A més, canviarem a la pàgina tipus de punter i afegirem un nou tipus de punter anomenat «coincident». Això ens durà automàticament a l'ID `1` i establirem el color a blau.

#### L'algorisme

Per acabar, hem d'implementar l'algorisme d'aproximació. Per això utilitzarem la següent implementació:

    var E = testgraph.list_edges(); // conjunt d'arestes sense processar
    var C = new Array();            // arestes coincidents
    while (E.length
    > 0) {
        var e = E[0];        // prenem la primera aresta e={u,v}
        var u = e.start();
        var v = e.end();
        e.set_type(1);       // establim l'aresta com a coincident
        E.shift();           // eliminem «e» (és a dir, E[0]) des de la llista d'arestes
        C.push(u);           // afegim «u» a «C»
        C.push(v);           // afegim «v» a «C»

        // marquem «u,v» com a nodes en «C»
        u.set_type(1);
        v.set_type(1);

        // eliminem de «E» totes les arestes adjacents a «u» o «v»
        var adjacent = u.adj_edges();
        for (var i=0; i < adjacent.length; i++) {
            var index = E.indexOf(adjacent[i]); // troba l'índex
            if (index!=-1) {
                E.splice(index, 1); // l'elimina si ja s'ha trobat
            }
        }
        var adjacent = v.adj_edges();
        for (var i=0; i < adjacent.length; i++) {
            var index = E.indexOf(adjacent[i]); // troba l'índex
            if (index!=-1) {
                E.splice(index, 1); // l'elimina si ja s'ha trobat
            }
        }
    }
    output("Vertex Cover conté " + C.length + " nodes.");

#### Executar l'algorisme

Finalment volem executar l'algorisme. Per això podem iniciar l'execució amb el botó Executa al plafó de control de l'script.

## La interfície d'usuari de &rocs;

### Elements generals de la interfície d'usuari

La interfície d'usuari es divideix en diverses parts lògiques que es presenten en la següent captura de pantalla.

Elements de la &IGU; de la interfície de &rocs;.
Elements de la &IGU; de la interfície de &rocs;.

Selector de documents

  En aquesta barra de menú superior haureu de seleccionar el document actual i l'estructura de dades. Des d'on també és possible crear i eliminar estructures de dades així com accedir a les propietats de l'estructura de dades.

Editor visual de grafs

  Aquesta és la pissarra en blanc on es poden crear i modificar les estructures de dades. Feu clic dret a la pissarra, en els elements de dades, o en els punters per obrir els menús contextuals. Podeu utilitzar les eines de la barra d'eines Editor visual de grafs per modificar els elements a la pissarra de l'editor visual de grafs.

La barra d'eines Editor visual de grafs

  Aquesta barra d'eines proporciona totes les eines per a l'editor visual de grafs. Utilitzeu l'eina Afegeix dades o Afegeix connexió per crear nous elements o per connectar elements, respectivament. S'afegeixen nous elements de dades a l'estructura de dades que es troba seleccionada al Selector de documents. Recordeu que tant Afegeix dades i Afegeix connexió tenen menús contextuals per seleccionar el tipus dels elements que seran creats. Per a més detalls, veure .

Barra lateral

  A la dreta, trobareu la barra lateral que proporciona diverses eines per al vostre flux de treball:

  - Tipus d'element: Aquest estri us permet accedir directament al punter i tipus de dades disponibles.

  - Diari: Cada projecte disposa del seu propi diari que es pot utilitzar per, &pex;, anotar tasques, resultats o observacions.

  - Documentació: Podeu obrir aquest estri per obtenir accés directe al manual i a través seu a la documentació dels scripts.

Editor d'scripts

  En aquest editor de text podeu escriure algorismes com s'explica en detall en . Podeu treballar sobre diversos documents d'script simultàniament utilitzant diverses pestanyes. Si l'script conté canvis sense desar a la pestanya apareixerà el símbol d'un disc.

Sortida de l'script

  Aquesta àrea de text bé mostra informació de depuració o la sortida de l'script del vostre algorisme, depenent de la preferència indicada a la part superior d'aquest estri. Si l'script retorna un error, automàticament es presentarà la sortida de depuració.

Controls

  Aquí trobareu els controls per a l'execució d'scripts. Podeu executar l'script que està obert a l'editor d'scripts prement Executa. Mentre s'executa l'script, és possible aturar l'execució prement el botó Atura. Tingueu en compte que l'execució amb Un pas sols s'aturarà a les paraules clau específiques (veure ).

### Barres d'eines

Hi ha diferents barres d'eines per a l'editor visual de grafs que us permeten accedir a les funcions amb un sol clic. Per omissió, es mostren les següents barres d'eines:

- Barra d'eines principal

- Barra d'eines d'alineació

#### Barra d'eines principal

La barra d'eines principal es compon de les següents accions. El fer clic sobre una acció significa que el punter del ratolí aplica aquesta acció a la pissarra de l'editor visual de grafs:

- Moure: Per a seleccionar elements, o bé feu clic sobre l'espai sense utilitzar a la pissarra, manteniu premut el ratolí i dibuixeu un rectangle que contingui alguns elements de dades i/o punters per a seleccionar aquests elements o en cas contrari feu clic directament sobre un element sense seleccionar per seleccionar-lo. Si feu clic sobre un element o conjunt d'elements seleccionats, respectivament, els podreu moure mantenint premut el ratolí i movent-lo. També és possible moure els elements seleccionats amb les tecles del cursor.

- Afegeix dades: Feu clic sobre una posició arbitrària a la pissarra de l'editor visual de grafs per crear un nou element de dades que pertanyi a l'estructura de dades actualment seleccionada. Si manteniu premut el punter del ratolí sobre el botó, es mostrarà un menú contextual des d'on es podran seleccionar (només si hi ha diferents tipus de dades) els tipus de dades dels nous elements de dades creats.

- Afegeix connexió: Feu clic sobre un element de dades, manteniu premut el ratolí i dibuixeu una línia cap a un altre element de dades al qual assenyali el punter/aresta. Aquesta acció només té èxit si el graf actual permet afegir aquesta aresta (&pex;, en un graf no dirigit no podreu afegir múltiples arestes entre dos elements de dades). Si manteniu premut el punter del ratolí sobre el botó, es mostrarà un menú contextual des d'on es podran seleccionar (només si hi ha diferents tipus de punter) els tipus de punter dels nous elements de dades creats.

- Elimina: Feu clic sobre un element per eliminar-lo. Si elimineu un node, totes les arestes adjacents també s'eliminaran.

- Zoom: Feu clic sobre la pissarra, manteniu premut el &BER; i dibuixeu un rectangle. La pissarra s'ampliarà a la zona seleccionada. Utilitzant també la roda del ratolí per apropar o allunyar. Un doble clic amb el &BER; restaura el zoom original.

#### Barra d'eines d'alineació

Podeu afegir l'opcional barra d'eines d'alineació. En prémer sobre una acció en aquesta barra d'eines tindrà un efecte directe en els nodes seleccionats:

- Dalt: Alinea els elements de dades a la posició vertical de l'element de dades més superior. Això només afecta a les posicions verticals.

- Centre: Alinea els elements de dades a la posició vertical donada pel centre de totes les posicions verticals dels elements de dades seleccionats. Això només afecta a les posicions verticals.

- Base: Alinea els elements de dades a la posició vertical de l'element de dades més inferior. Això només afecta a les posicions verticals.

- Esquerre: Alinea els elements de dades a la posició horitzontal de l'element de dades més a l'esquerra. Això només afecta a les posicions horitzontals.

- Centre: Alinea els elements de dades a la posició horitzontal de l'element de dades més superior. Això només afecta a les posicions horitzontals.

- Dreta: Alinea els elements de dades a la posició horitzontal de l'element de dades més a la dreta. Això només afecta a les posicions horitzontals.

- Cercle: Alinea els elements de dades en un cercle de diàmetre igual que la distància màxima entre els elements de dades. Els elements de dades estan col·locats en la mateixa seqüència que la proposta per vista des del centre de gravetat d'aquests elements de dades.

- Minimitza els creuaments d'arestes: Torna a organitzar els elements de dades seleccionats per a minimitzar el nombre de connexions creuades (aplicació de l'algorisme Fruchterman-Reingold).

### Treballar amb documents de graf

Un projecte de &rocs; conté un o múltiples documents de graf que es poden editar amb l'editor visual de grafs. A més, cada document pot contenir un nombre arbitrari d'estructures de dades. En aquest cas, totes les estructures de dades d'un document utilitzen el mateix dorsal per a l'estructura de dades. En aquesta secció explicarem com canviar entre els documents i la manera de crear-ne de nous.

#### La barra selector de documents

La barra selector de documents s'utilitza per seleccionar el document de graf i també l'estructura de dades. Quan utilitzeu les eines de l'editor visual de grafs per crear elements d'estructures de dades, els nous elements creats s'afegiran automàticament a l'estructura de dades actual. A més, aquesta barra ofereix accés directe a eliminar els ja existents o crear noves estructures de dades dins del document actual.

- Nou: Aquesta acció crea una nova estructura de dades utilitzant un patró de nomenclatura automàtica proposta pel dorsal de l'estructura de dades. L'estructura de dades creada s'afegirà al document de graf seleccionat.

- Elimina: Aquesta acció elimina l'estructura de dades que es troba seleccionada en el selector d'estructura de dades per al document actual.

- Propietats de l'estructura de dades: Obre un diàleg que permet accedir a les propietats de l'estructura de dades.

- Propietats del document: Obre un diàleg que permet accedir a les propietats del document, així com als tipus de dades i punter del document.

La barra d'eines principal
La barra selector de documents.

#### Crear i importar documents de graf

Per crear un document nou gràfic o afegir un d'existent per al projecte, utilitzi Projecte → Nou document de gràfic o Projecte Nou document de graf o Projecte Importa un graf del &rocs;. També podreu importar documents de graf des d'aplicacions de tercers (per a això, veure ).

## Escriure i executar algorismes en &rocs;

&rocs; utilitza internament el motor per a la creació d'scripts QtScript, el qual és un motor específic de JavaScript. Això significa que tots els algorismes que implementeu hauran d'utilitzar JavaScript. Com funciona JavaScript i com escriure codi no està cobert per aquest manual, encara que s'explica com accedir a les estructures de dades, elements de dades i punters de les estructures de dades del motor per crear scripts. Atès que mai utilitzareu l'objecte d'estructura de dades bàsica, sinó el proporcionat pel dorsal d'estructura de dades utilitzat actualment, la funcionalitat de l'estructura de dades s'estén pel dorsal corresponent i haureu de fer una ullada a la funcionalitat especialitzada. Sobretot, els dorsals d'estructura de dades utilitzant la terminologia comuna del vostre domini (nodes i arestes en els grafs, les fulles i les arrels en els arbres, &etc;)

És important saber que els canvis fets pel motor per a la creació d'scripts es reflecteixen directament en les propietats a la pissarra de l'editor visual de grafs. Per tant, els scripts en realitat modifiquen les estructures de dades.

### Els elements de l'estructura de dades base

Cada dorsal proporciona un conjunt especial de funcions i propietats de les seves estructures de dades i els seus elements. Però cada dorsal també proporciona les propietats i funcions definides per l'estructura de dades base. Per tant, tot el que s'explica en aquesta secció està disponible per a cada dorsal d'estructura de dades.

#### Propietats de l'estructura de dades base

Les estructures de dades s'identifiquen pel seu nom. Assumint que heu creat una estructura de dades amb el nom `testgraph`, llavors podreu accedir a l'estructura de dades simplement escrivint aquest identificador. Per exemple, per obtenir una matriu amb tots els elements de dades en l'estructura de dades donada, podeu escriure `testgraph.list_nodes();` a l'script.

##### Propietats i funcions de l'estructura de dades base

Cada estructura de dades `testgraph` té les següents propietats que es poden llegir o escriure per `testgraph.property`:

    string name  // identificació de l'estructura de dades

#### Propietats i funcions dels elements de les dades base

Cada element de dades té les següents propietats que es poden llegir o escriure:

    double x      // coordenada «x» de la posició actual
        double y      // coordenada «y» de la posició actual
        double width  // mida
        string value  // valor
        int id        // identificador únic de l'element de dades
        string name   // nom
        string color  // color en hexadecimal

A més, es pot accedir a cada propietat dinàmica d'un element de dades pel seu nom.

Cada objecte d'element de dades proporciona els següents mètodes:

    int type();                         // tipus de dades de l'element de dades
        int set_type(int);                  // assigna el tipus de dades de l'element de dades
        void add_property(string name,      // afegeix la propietat dinàmica a l'element de dades amb el nom i valor especificats
                          string value);
        array adj_data();                   // llista de dades adjacents
        array adj_pointers();               // llista de punters adjacents
        array input_pointers();             // llista de punters d'entrada
        array output_pointers();            // llista de punters de sortida
        array loop_pointers();              // llista de punters que formen un bucle automàtic
        array connected_pointers(target);   // llista de punters que apunten a l'«objectiu»
        void  remove();                     // elimina aquest element de dades

#### Propietats i funcions de l'apuntador base

Cada punter té les següents propietats que es poden llegir o escriure:

    string color  // color en hexadecimal
        string value  // valor
        string name   // nom
        double width  // amplada
        string style  // un dels valors: «dot», «dash», «dash dot», «solid»

A més, es pot accedir a cada propietat dinàmica d'un punter pel seu nom.

Cada objecte punter proporciona els següents mètodes:

    int type();                         // tipus de punter
        int set_type(int);                  // assigna el tipus del punter
        void add_property(string name,      // afegeix propietat dinàmica a l'element de dades amb el nom i valor especificats
                          string value);
        node start();                       // node d'inici del punter
        node end();                         // node objectiu del punter
        void remove();                      // elimina aquest punter

### El dorsal del graf

#### Propietats i funcions del graf

##### Propietats específiques del dorsal del graf

El diàleg de propietats de l'estructura de dades permet accedir als ajustaments de configuració específics per al dorsal del graf. Allà, amb Tipus de graf podreu seleccionar el tipus del graf. El significat d'aquests tipus és el següent:

- Graf: Graf en el que és possible que no existeixin varies vegades les mateixes arestes (pel que fa als punts d'inici i final).

- Multigraf: Graf en el que és possible que existeixin varies vegades les mateixes arestes (pel que fa als punts d'inici i final).

##### L'estructura del graf

Tenint en compte un objecte d'estructura de dades del tipus «Graf», podeu cridar a les següents funcions membre:

    array list_nodes();                   // llista de tots els nodes del graf
        array list_nodes(int type);           // llista de tots els nodes del tipus indicat
        array list_edges();                   // llista de totes las arestes del graf
        array list_edges(int type);           // llista de totes les arestes del tipus indicat
        node add_node(name);                  // afegeix un nou node i el retorna
        edge add_edge(node from, node to);    // afegeix nova aresta de «from» a «to» i la retorna
        array overlay_edges(int overlayID);   // llista de totes les arestes de la capa indicada
        edge add_overlay_edge(node from,
                              node to,
                              int overlayID); // afegeix aresta del tipus de punter indicat a la capa especificada

##### Nodes del graf

Tenint en compte un objecte d'estructura de dades del tipus «Graf», podeu cridar a les següents funcions membre en els nodes del graf, a més de les propietats proporcionades pels elements de dades:

    array adj_nodes();                    // llista de tots els nodes adjacents
        array adj_edges();                    // llista de les arestes connectades
        array input_edges();                  // llista de les arestes d'entrada
        array output_edges();                 // llista de totes les arestes de sortida
        array loop_edges();                   // llista de totes les arestes que retornen al node
        array connected_edges(node target);   // totes les arestes que connecten aquest node amb el node «objectiu»

##### Arestes del graf

Tenint en compte les arestes d'una estructura de dades del tipus «Graf», només estaran disponibles les propietats de l'estructura de dades base.

#### Algorismes de l'estructura del graf

El dorsal de grafs proporciona algunes funcions especials que es poden utilitzar des del motor per a crear scripts.

Calcular el camí més curt

  Calcula el camí més curt entre els nodes inici i final. Ambos nodes han de ser del mateix graf. Aquest càlcul respecta si el graf és dirigit o no dirigit.

          array dijkstra_shortest_path node inici node final

Distàncies del camí més curt

  Calcula les distàncies del camí més curt entre el node inici i tots els altres nodes del graf. Aquest càlcul respecta si el graf és dirigit o no dirigit.

          array distances node inici

### El dorsal de llista enllaçada

#### Propietats i funcions de la llista enllaçada

##### L'estructura de la llista enllaçada

Tenint en compte un objecte d'estructura de dades del tipus «Llista enllaçada», podeu cridar a les següents funcions membre:

    node begin();                           // proporciona el node de capçalera per a la llista enllaçada
        setBegin(node begin):               // assigna el node inici com a inici de la llista i torna a ordenar la llista
        createNode();                       // crea un nou node de llista

##### Nodes de la llista enllaçada

Tenint en compte un objecte d'estructura de dades del tipus «Llista enllaçada», podeu cridar a les següents funcions membre en els nodes del graf, a més de les propietats proporcionades pels elements de dades:

    node front();                           // retorna predecessor del node

##### Arestes de la llista enllaçada

Tenint en compte les arestes d'una estructura de dades del tipus «Llista enllaçada», només estaran disponibles les propietats de l'estructura de dades base.

### El dorsal de l'arbre arrelat

#### Propietats i funcions de l'arbre arrelat

##### Dorsal de l'arbre arrelat

El diàleg de propietats de l'estructura de dades permet accedir als ajustaments de configuració específics per al dorsal del graf. Allà, marcant la propietat Mostra tots els punters, es mostraran els punters entre els nodes de l'arbre. Si no es marca, els múltiples punters entre els mateixos nodes es plegaran en un.

##### L'estructura de l'arbre arrelat

Tenint en compte un objecte d'estructura de dades del tipus «Arbre arrelat», es poden llegir o escriure les següents propietats:

    ShowAllPointers     // estableix a «true» per a mostrar totes les arestes; a «false» si s'han de plegar múltiples arestes

Tenint en compte un objecte d'estructura de dades del tipus «Arbre arrelat», podeu cridar a les següents funcions membre:

    node add_data(string name);         // afegeix un node a l'arbre amb el nom indicat
        void set_root_node(node root);  // estableix l'arrel com node arrel de l'arbre
        node root_node();               // retorna el node arrel de l'arbre

##### Nodes de l'arbre arrelat

Tenint en compte un objecte de node del tipus «Arbre arrelat», es poden llegir o escriure les següents propietats:

    int numberOfChilds                  // estableix el nombre (permès) de fills per aquest node
        node left_child                 // sols lectura: el node que és el fill de l'esquerra
        node right_child                // sols lectura: el node que és el fill de la dreta
        node node_parent                // sols lectura: el node que és el pare

Tenint en compte un objecte de node del tipus «Arbre arrelat», podeu cridar a les següents funcions membre:

    node add_left_child(node child);    // afegeix fill a l'esquerra
        node add_right_child(node child);   // afegeix fill a la dreta
        node add_child(node child, int i);  // afegeix un fill com a enèsim fill del node
        node add_node_parent(node child);   // afegeix pare (sols tindrà èxit si encara no s'ha assignat un pare)
        node left_child();                  // retorna el fill de la dreta
        node right_child();                 // retorna el fill de l'esquerra
        node child_at(int i);               // retorna l'enèsim fill del node
        node node_parent();                 // retorna el pare del node

##### Arestes de l'arbre arrelat

Tenint en compte les arestes d'una estructura de dades del tipus «Arbre arrelat», només estaran disponibles les propietats de l'estructura de dades base.

### Controlar l'execució de l'script

#### Incloure fitxers

Els vostres documents d'script poden incloure altres scripts. Això pot ser útil per reduir la mida dels documents d'script i millorar la llegibilitat. Utilitzant Document d'script Inclusions possibles obtindreu una llista de fitxers d'script que ja vénen amb &rocs; i que podeu incloure. Podeu incloure un fitxer d'script amb la següent ordre:

    include_script(string path);            // camí relatiu o absolut a un fitxer d'script

#### Sortida de l'script

Durant l'execució d'un algorisme, la sortida de depuració i del programa es mostren a la depuració i sortida de l'script. Si el motor per a la creació d'scripts detecta un error de sintaxi, l'error també es mostrarà com a missatge de depuració. Tingueu en compte que tots els missatges del programa també es mostraran a la sortida de depuració (com a text en negreta).

Podeu controlar el text que es mostrarà a la sortida de l'script mitjançant les següents funcions:

    output(string message);            // mostra el missatge com a sortida de l'script
        debug(string message);         // mostra el missatge com a sortida de depuració

#### Controlar l'execució de l'script

Hi ha diferents modes d'execució per als vostres scripts.

Podeu controlar el text que es mostrarà a la sortida de l'script mitjançant les següents funcions:

- Inicia: Executa l'script fins finalitzar.

- Atura: Atura l'execució de l'script (sols disponible si s'executa un script).

- Un pas: Executa l'script fins que finalitza un pas. Un pas finalitza quan l'script crida la funció `interrupt()`:

      interrupt();    // finalitza un pas

- Depura: Executa l'script en mode de depuració. Això obre el diàleg de depuració de QtScript.

## Importar i exportar

### Intercanviar projectes del &rocs;

Els projectes del &rocs; es poden importar i exportar com fitxers d'arxiu `.tar.gz`. Aquests arxius es poden utilitzar per a intercanviar projectes. Podeu importar i exportar amb Fitxer Importa un projecte i Fitxer Exporta el projecte, respectivament.

### Importar i exportar documents de graf

&rocs; actualment suporta la importació i exportació dels següents formats de fitxer:

- Fitxers DOT, també coneguts com fitxers Graphviz

- Fitxers GML

- Fitxers en el format de grafs trivial

#### Format de grafs trivial

El format de grafs trivial (TGF) és un format de fitxer basat en text simple per a la descripció dels grafs. Un fitxer TGF consta d'una llista de definicions de node, que assignen els identificadors dels nodes a les etiquetes, seguits per una llista de les arestes. En aquest format, és possible tenir més d'una etiqueta per node i un valor per a cada aresta. &rocs; interpreta grafs importats com a grafs no dirigits. Els grafs exportats contindran dues arestes per connexió si les connexions són bidireccionals.

##### Especificació del format

- El fitxer comença amb una llista de nodes (un node per línia), seguit per una línia amb el caràcter únic «#», seguit per una llista d'arestes (una aresta per línia).

- Un node consisteix d'un nombre enter (identificador), seguit d'un espai, seguit per una cadena arbitrària.

- Un aresta es compon de dos nombres enters (identificadors) separats per un espai, seguit per un espai, seguit per una cadena arbitrària. Se suposa que l'aresta dirigida apunta des del primer identificador fins al segon.

##### Exemple

    1 node inicial
    2 transmissor
    3 pila
    #
    1 2 blau
    2 1 vermell
    2 3 verd

#### Llenguatge DOT / Format de fitxer de grafs Graphviz

El llenguatge DOT és un llenguatge de descripció de grafs de text pla, que permet, tant una representació de grafs llegible, així com un processament eficient pels programes de disseny de grafs. DOT és el format de fitxer predeterminat per a la suite de visualització de grafs Graphviz, però també és àmpliament utilitzat per altres eines de graf. Les extensions de fitxer habituals per a DOT són .gv i .dot.

##### Característiques no implementades

&rocs; pot analitzar cada fitxer de grafs que contingui un graf especificat d'acord amb l'especificació del llenguatge DOT http://www.graphviz.org/content/dot-language. La implementació de les característiques del llenguatge és completa, tot i les següents excepcions:

- subgraf: A causa de la manca d'un concepte de subgraf en &rocs;, els subgrafs només s'importen com un conjunt d'elements de dades i connexions. En especial, no s'importaran les connexions cap o des dels subgrafs.

- Els atributs &HTML; i &XML;: Els atributs (com les etiquetes) que contenen la sintaxi &HTML; o &XML; es llegeixen sense canvis. En especial, no es llegeix cap atribut com el tipus de lletra i estil.

##### Exemple

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

## Crèdits i llicència

&rocs;

Copyright del programa:

- 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)

Copyright de la documentació:

- Copyright de la documentació 2009 &Anne-Marie.Mahfouf; &Anne-Marie.Mahfouf.mail;

- Copyright de la documentació 2009 Tomaz Canabrava (tcanabrava AT kde.org)

- Copyright de la documentació 2011-2012 Andreas Cord-Landwehr (cordlandwehr AT googlemail.com)

Traductor de la documentació: &credits.Antoni.Bella;

&underFDL; &underGPL;

## Instal·lació

### Com obtenir el &rocs;

&install.intro.documentation;

### Compilació i instal·lació

&install.compile.documentation;

&documentation.index;