El manual del Rocs

# El manual del Rocs

Canabrava, Tomaz `<tomaz.canabrava@gmail.com>`

Cord-Landwehr, Andreas `<cordlandwehr@kde.org>`

Traductor: Antoni Bella
revisió Rocs 2.1.50 (Aplicacions 16.04) (10 d'abril de 2016)

Avís legal

El Rocs és una eina de teoria de grafs pel KDE.

Capítol 1. Introducció
Introducció

# Capítol 1. Introducció

En aquest capítol s'ofereix una visió general de les principals característiques i el flux de treball típic. Les parts més importants són «El Rocs en poques paraules» i Capítol 3, Crear scripts, que en el seu conjunt han de permetre que cada nou usuari comenci directament a emprar el Rocs.

## Objectius, destinataris i flux de treball

El Rocs és una eina per a la teoria de grafs per a tothom interessat en el disseny i anàlisi d'algorismes de graf. En particular, aquests són

- professors, que volen demostrar algorismes als seus estudiants,

- estudiants i investigadors, que volen entendre i veure com actua el seu algorisme,

- i tothom que estigui interessat en les estructures de dades i algorismes.

Per a tots ells, el Rocs proporciona un fàcil editor gràfic per a la creació de grafs, un poderós motor per a la creació de scripts per executar algorismes, i diverses eines d'ajuda per a les simulacions, experiments i exportacions dels grafs. La forma típica d'usar el Rocs és crear un graf, ja sigui a mà (és a dir, arrossegant els nodes i arestes a la pissarra) o emprant un dels generadors de grafs. Els algorismes de grafs després es poden implementar i executar en el graf creat, i tots els canvis que realitzi l'algorisme, seran visibles immediatament en l'editor de grafs.

El Rocs en poques paraules
El Rocs en poques paraules

## El Rocs en poques paraules

Cada sessió del Rocs és un projecte: en obrir el Rocs es crea un projecte buit, en carregar algun projecte es convertirà en el projecte actual. En si, un projecte consisteix en documents de graf, scripts/algorismes i scripts.

### Documents de graf

Un document de graf representa el contingut d'una pissarra en l'editor de grafs. Conté informació sobre els tipus de nodes i arestes definits per l'usuari, les seves propietats, i sobre els nodes i arestes ja creats. És a dir, el Rocs entén el conjunt de tots els nodes i arestes d'un document de graf per a formar un (no necessàriament connectat) graf. Tot el que pertany a un document de graf és accessible des del motor de scripts mitjançant l'objecte global `Document`.

### Tipus d'arestes

En alguns escenaris, els grafs consisteixen en diferents tipus d'arestes (p. ex., un graf no dirigit, a més de les tres arestes calculades per un algoritme de cerca en amplada) que s'han de manegar i mostrar de forma diferent. Per això, a més d'un tipus d'aresta per omissió, podeu definir altres tipus d'arestes arbitràries. Cada tipus d'aresta té la seva representació visual individual, propietats dinàmiques, i es pot canviar de no dirigit o dirigit. La interfície per a la creació de scripts proporciona mètodes convenients per a només accedir específicament als tipus específics d'arestes.

### Tipus de nodes

De la mateixa manera que per als tipus d'arestes, podeu definir diferents tipus de nodes d'un graf (p. ex., per a donar un paper especial a alguns nodes). Cada tipus de node posseeix la seva pròpia representació visual i propietats dinàmiques.

### Propietats

Cada element (node o aresta) pot tenir propietats. Aquestes propietats s'han de configurar en el corresponent tipus de node o aresta. Les propietats s'identifiquen i accedeix mitjançant els seus noms i poden contenir qualsevol valor. Per crear una propietat nova o per modificar una d'existent, empreu la barra lateral Tipus d'elements i empreu el botó Propietats per obrir el diàleg.

També podeu emprar el motor de crear scripts per accedir a les propietats registrades i canviar els seus valors. En el següent exemple se suposa que la propietat «weight» està registrada per al tipus d'aresta per omissió.

    var nodes = Document.nodes()
    for (var i = 0; i < nodes.length; ++i){
        nodes[i].weight = i;
    }
    for (var i = 0; i < nodes.length; ++i){
        Console.log("weight of node " + i + ": " + nodes[i].weight);
    }

Guia d'aprenentatge
Guia d'aprenentatge

## 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.

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

### Generar el graf

Per crear el graf, emprarem un generador de grafs predeterminat proporcionat per Rocs. El podeu trobar al menú principal a Document de graf → Eines → Genera el graf. Després, seleccionarem 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).

### Crear els tipus d'elements

Emprarem els Tipus d'elements per crear un segon tipus de node i un segon tipus d'aresta. Per a aquests dos tipus nous, obrirem el diàleg de propietats amb els respectius botons de Propietats i establirem els seus ID a `2`. A més, canviarem els colors dels elements d'aquests dos tipus nous (per a distingir els tipus per omissió). Finalment, establirem que tots els tipus d'arestes són bidireccionals i establirem els ID del tipus per omissió a `1`.

### L'algorisme

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

    for (var i=0; i < Document.nodes.length; i++) {
        Document.nodes[i].type = 1;
    }
    for (var i=0; i < Document.edges.length; i++) {
        Document.edges[i].type = 1;
    }

    var E = Document.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.from();
        var v = e.to();
        e.type = 2;           // 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.type = 2;
        v.type = 2;

        // eliminem de «E» totes les arestes adjacents a «u» o «v»
        var adjacent = u.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.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
            }
        }
    }
    Console.log("Vertex Cover contains " + C.length + " nodes.");

### Executar l'algorisme

L'algorisme es pot executar amb el botó Executa al plafó de control de l'script.

Capítol 2. La interfície d'usuari del Rocs
La interfície d'usuari del Rocs

# Capítol 2. La interfície d'usuari del Rocs

## Elements principals 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.

Editor de grafs

  L'editor proporciona una pissarra en blanc on es poden situar els nodes i les arestes. En fer doble clic a qualsevol dels seus elements obrirà un menú adequat. Podeu utilitzar les eines de la barra d'eines Editor de grafs per a crear i modificar els grafs.

La barra d'eines Editor de grafs

  La barra d'eines proporciona les eines Crea un node o Crea una aresta, per crear elements nous a la pissarra. Tingueu present la barra d'eines addicional per seleccionar el node respectiu o tipus d'aresta, visible quan se selecciona una d'aquestes eines. També hi ha disponibles eines per seleccionar i moure, així com suprimir elements. Per a més detalls, veure «La barra d'eines Editor de grafs».

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 a les arestes i tipus de node disponibles.

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

  - API per a crear scripts: Per obtenir accés directe a la documentació dels scripts, podeu obrir aquest estri.

Editor de scripts

  En aquest editor de text podeu escriure algorismes com s'explica en detall en Capítol 3, Crear scripts. Podeu treballar sobre diversos documents de script simultàniament utilitzant diverses pestanyes.

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ó de scripts. Podeu executar l'script que està obert a l'editor de scripts prement Executa. Mentre s'executa l'script, és possible aturar l'execució prement el botó Atura.

La barra d'eines Editor de grafs
La barra d'eines Editor de grafs

## La barra d'eines Editor de grafs

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

- Seleccionar i 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 arestes 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.

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

- Crea una aresta: 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 apunti l'aresta. Aquesta acció només té èxit si el graf actual permet afegir aquesta aresta (p. ex., 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ú des d'on es podran seleccionar (només si hi ha diferents tipus d'arestes) els tipus d'arestes 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.

Capítol 3. Crear scripts
Crear scripts

# Capítol 3. Crear scripts

## Executar algorismes en el Rocs

El Rocs empra internament el motor QtScript Java Script. Això vol dir, que tots els algorismes que implementeu empraran Java Script. A continuació, us expliquem com accedir i canviar els elements d'un document de graf des del motor per a la creació de scripts. És important tenir en compte que els canvis realitzats pel motor per a la creació de scripts es reflecteixen directament en les propietats dels elements a l'editor de grafs.

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

Hi ha diferents modes d'execució per als vostres algorismes:

- Executa: Executa l'script fins a finalitzar.

- Atura: Atura l'execució de l'script (només disponible quan s'executa un 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ó de 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:

    Console.log(string message);            // mostra el missatge com a sortida de l'script
        Console.debug(string message);      // mostra el missatge com a sortida de depuració
        Console.error(string message);          // mostra el missatge com a sortida d'error

### L'API per a la creació de scripts

Les diferents parts de Rocs proporcionen un element estàtic al qual es pot accedir des del motor per a la creació de scripts. Aquests són:

- `Document` per al document de grafs

- `Consola` per a la sortida de registre de la consola

Per a l'ús explícit de l'API i per un mètode de referència, si us plau, consulteu l'ajuda en línia a la barra lateral del Rocs.

Capítol 4. Importar i exportar
Importar i exportar

# Capítol 4. 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 Document de graf → Importa un graf i Document de graf → Exporta el graf com a, 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 a fitxers Graphviz

- Fitxers GML

- Fitxers en el format de grafs trivial

- Format de llenguatge de marcat Keyhole

#### 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 net, 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[1]. 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;
    }

[1] http://www.graphviz.org/content/dot-language

Capítol 5. Crèdits i llicència
Crèdits i llicència

# Capítol 5. 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-2015 Andreas Cord-Landwehr (cordlandwehr AT kde.org)

Copyright de la documentació:

- Copyright de la documentació 2009 Mahfouf, Anne-Marie `(annma AT kde.org)`

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

- Copyright de la documentació 2011-2015 Andreas Cord-Landwehr (cordlandwehr AT kde.org)

Traductor de la documentació: Antoni Bella `(antonibella5 AT yahoo.com)`

Aquesta documentació està llicenciada sota els termes de la Llicència de Documentació Lliure de GNU.

Aquest programa està llicenciat sota els termes de la Llicència Pública General de GNU.