# El manual de &rocs;

Tomaz
Canabrava
tomaz.canabrava@gmail.com
Andreas
Cord-Landwehr
cordlandwehr@googlemail.com
Leticia
Martín Hernández

    leticia.martin@gmail.com

Traducción
Rocío
Gallego

    traducciones@rociogallego.com

Traducción
2009
Tomaz Canabrava
2011-2012
Andreas Cord-Landwehr
2 de diciembre de 2012
1.8.0 &kde; 4.10
&FDLNotice;

&rocs; es una herramienta de teoría de grafos para KDE.

KDE
kdeedu
matemáticas
matemáticas
grafos
nodo
arista

## Introducción

En este capítulo le proporcionamos un resumen de las funcionalidades principales y del flujo de trabajo de &rocs;. Para el lector que impaciente que quiera comenzar a usar &rocs; inmediatamente, le sugerimos que lea al menos y use como referencia cuando escriba algoritmos.

### Objetivos, audiencia de destino y flujo de trabajo

&rocs; es un entorno de desarrollo integrado de teoría de grafos para todos aquellos interesados en el diseño y el análisis de algoritmos. Esto incluye explícitamente

- los profesores que quieran mostrar algoritmos a sus estudiantes,

- los estudiantes que quieran entender y ver como funciona un algoritmo,

- y cualquier persona interesada en las estructuras de datos y los algoritmos.

Para todos esos usuarios, &rocs; proporciona un editor de estructuras de datos fácil de utilizar para crear estructuras, un potente motor de guiones para ejecutar algoritmos y varias herramientas de ayuda para sus simulaciones y experimentos.

El flujo típico de trabajo cuando se usa &rocs; consiste en comenzar por crear un grafo con el editor visual. Puede hacer esto de manera manual, añadiendo elementos de datos y conectándolos, o bien utilizar uno de los generadores de estructuras de datos (si están disponibles para el motor de estructuras de datos que haya seleccionado). Puede encontrar generadores de estructuras de datos en Documento de grafo Herramientas Generar grafo. Además, puede asignar valores a los elementos de la estructura de datos, a mano o usando Documento de grafo Herramientas Asignar valores. Finalmente, puede escribir el algoritmo en JavaScript y ejecutarlo con la estructura de datos recién creada. Todos los cambios que realice el algoritmo en la estructura de datos serán directamente visibles en el editor visual del grafo.

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

### &rocs; en pocas palabras

En esta sección le proporcionamos un resumen compacto de los elementos principales de &rocs;. Le explicamos las importantes nociones de estructuras de datos, motores de estructuras de datos y tipos de elementos. La comprensión de estos conceptos resulta útil para entender cómo se pueden crear y modificar estructuras de datos en &rocs;.

En general, &rocs; trabaja con proyectos: cuando abra &rocs; se creará un proyecto vacío que podrá sustituir cargando o importando otro proyecto. En sí, un proyecto consta de documentos de grafos y de guiones.

#### Documentos de grafos y motores de estructuras de datos

Un documento de grafo representa el contenido de una pizarra en blanco en el editor visual de grafos. Un documento de grafo puede contener varias estructuras de datos a la vez, pero solo un motor de estructura de datos. Dispone de motores de estructuras de datos para varios tipos de grafos (grafos generales, listas enlazadas, árboles con raíz) que proporcionan funcionalidades adicionales para sus propios tipos de grafos, como posicionamiento de los elementos, juegos de iconos especiales o un juego extendido de funciones de guiones que puede usar en sus algoritmos (consulte la correspondiente sección del manual para más información). Se puede cambiar el motor de la estructura de datos de un documento de grafo, aunque puede acarrear pérdida de información (por ejemplo, las aristas de un círculo de un grafo general no se añadirán a un árbol si cambia al motor de árboles con raíz).

Los documentos de grafos también forman la base para definir tipos de punteros y de datos.

#### Estructuras de datos

Las estructuras de datos son la base de todo trabajo con &rocs;. Puede añadir una o varias de ellas a un documento de grafo, añadir elementos de datos (nodos, datos) y punteros a ellos, y modificarlos usando guiones. Para ello, cada estructura de datos tiene un nombre único por el que puede acceder a ella desde sus guiones. Según el motor de estructura de datos que elija, es posible que no pueda modificar las estructuras de datos a su antojo (por ejemplo, un árbol nunca podrá contener un ciclo). El motor de una estructura de datos se determina por el motor asociado con el correspondiente documento de grafo que contiene la estructura de datos.

#### Tipos de punteros

Con los tipos de punteros puede definir diferentes tipos de punteros para usar en sus estructuras de datos. Es decir, un tipo de puntero puede tener un esquema individual (esencialmente, un color), y resulta fácil acceder solo a punteros de un tipo específico desde un guion. Los punteros se usan típicamente para implementar metaaristas en las estructuras de datos que visualizan las relaciones entre elementos de datos (por ejemplo, mostrar los intereses de comunicación). Pero también, si sus guiones deben identificar tipos concretos de aristas (por ejemplo, aristas de árbol y de cruce en el algoritmo de la primera búsqueda de profundidad), los tipos de punteros pueden ser un modo elegante de implementarlo.

#### Tipos de datos

En diversos problemas de estructuras de datos, un juego de elementos de datos se debe dividir en grupos de diferentes tipos (por ejemplo, en problemas de agrupamiento o en problemas de cobertura). También puede resultar útil para la ejecución de un algoritmo que especifique un tipo de elemento de dato para un tipo concreto (por ejemplo, para la búsqueda en anchura). Para estos casos puede definir tipos de datos. Cada tipo de dato posee su propio icono y puede acceder a los tipos de datos fácilmente desde sus guiones.

#### Propiedades dinámicas

Cada elemento de dato y puntero puede tener muchas propiedades. Algunas de ellas se toman por omisión del motor de la estructura de datos. Consulte la documentación del motor de la estructura de datos para más detalles. Para añadir más propiedades a los elementos de datos y a los punteros, puede añadirles propiedades dinámicas. Cada propiedad dinámica se identifica por su nombre y puede contener cualquier valor asociado con ella. El nombre debe comenzar por una letra (de la «a» a la «z», o de la «A» a la «Z») y puede contener únicamente letras, números y «_». Si trata de usar cualquier carácter no válido en el nombre de la propiedad, la propiedad no se modificará.

Para añadir propiedades dinámicas, use los diálogos Propiedades de los datos y Propiedades del puntero desde los menús de contexto de sus respectivos elementos, o bien las funciones del guion como se explica en .

También puede usar los guiones. Solo necesita usar `add_property` con el nombre y el valor de la propiedad. Tras ello, puede usar node/pointer.propertyName para asignar u obtener los valores.

Aquí tiene un ejemplo de cómo usar las propiedades dinámicas con el motor de estructuras de datos «Grafo».

    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

### Tutorial

En esta sección queremos crear un proyecto de ejemplo para explorar algunas de las funciones más importantes de &rocs;. El objetivo es crear un grafo y un guion que ilustre un sencillo algoritmo de aproximación a 2 para el problema de la cobertura de vértices mínima. En este problema se debe encontrar un subconjunto de nodos del grafo C del mínimo tamaño, de modo que cada arista de grafo esté conectada a al menos un nodo de C. Este problema es NP-complejo y deseamos ilustrar cómo encontrar una aproximación de factor 2 buscando una coincidencia en el grafo propuesto (en lo que sigue vamos a usar la terminología de los algoritmos de grafos: un grafo es una estructura de datos, los nodos son los elementos de datos y las aristas son los punteros).

Nuestro objetivo es mostrar la correspondencia de las coincidencias y la cobertura de vértices mínima. Para ello, vamos a especificar dos tipos de punteros, uno para mostrar las aristas coincidentes y otro para mostrar las aristas ordinarias, así como dos tipos de datos que vamos a usar para distinguir los nodos contenidos en C y los que no están contenidos en C.

#### Generación de un grafo

Para el motor de estructura de datos «Grafo», &rocs; brinda una herramienta de ayuda que puede generar grafos. Está disponible en Documento de grafo Herramientas Generar grafo. Con ella generamos un «grafo aleatorio» con 30 nodos, 90 aristas y semilla 1 (la semilla es la inicial para el generador de grafos aleatorios; si usa la misma semilla varias veces se volverán a reproducir los mismos grafos). Finalmente, modificamos el nombre del grafo en el panel de la estructura de datos, dándole el nombre `testgraph`.

#### Creación de tipos

Usamos el botón Propiedades del documento del panel de la estructura de datos para abrir el diálogo de propiedades para los tipos de datos y de punteros del documento de grafo actual. Para los tipos de datos añadimos un nuevo tipo llamado «C», que obtiene automáticamente el ID `1`. Para dicho tipo, seleccionamos la imagen del servidor como icono. Luego cambiamos a la página del tipo de puntero y añadimos un nuevo tipo de puntero llamado «matching», que obtiene automáticamente el ID `1` y le asignamos el color azul.

#### El algoritmo

Por último, tenemos que implementar el algoritmo de aproximación. Para ello usaremos la siguiente implementación:

    var E = testgraph.list_edges(); // conjunto de aristas sin procesar
    var C = new Array();            // aristas coincidentes
    while (E.length
    > 0) {
        var e = E[0];        // tomamos la primera arista e={u,v}
        var u = e.start();
        var v = e.end();
        e.set_type(1);        // fijamos la arista como coincidente
        E.shift();            // eliminar e (es decir, E[0]) de la lista de aristas
        C.push(u);            // añadir u a C
        C.push(v);            // añadir v a C

        // marcar u,v como nodos en C
        u.set_type(1);
        v.set_type(1);

        // eliminar de E todas las aristas adyacentes con u o v
        var adjacent = u.adj_edges();
        for (var i=0; i < adjacent.length; i++) {
            var index = E.indexOf(adjacent[i]); // encontrar el índice
            if (index!=-1) {
                E.splice(index, 1); // eliminarlo si se ha encontrado
            }
        }
        var adjacent = v.adj_edges();
        for (var i=0; i < adjacent.length; i++) {
            var index = E.indexOf(adjacent[i]); // encontrar el índice
            if (index!=-1) {
                E.splice(index, 1); // eliminarlo si se ha encontrado
            }
        }
    }
    output("Vertex Cover contiene " + C.length + " nodos.");

#### Ejecución del algoritmo

Al final deseamos ejecutar el algoritmo. Podemos iniciar la ejecución usando el botón rojo que hay en el panel de control del guion.

## La interfaz de usuario de &rocs;

### Elementos generales de la interfaz de usuario

La interfaz de usuario se divide en varias partes lógicas tal como se presentan en la captura de pantalla de más abajo.

Elementos de la interfaz gráfica de usuario de &rocs;.
Elementos de la interfaz gráfica de usuario de &rocs;.

Selector de documentos

  En esta barra del menú superior debe seleccionar el documento actual y la estructura de datos. Desde aquí también puede crear y borrar estructuras de datos, así como acceder a las propiedades de la estructura de datos.

Editor visual de grafos

  Esta es la pizarra en blanco en la que se pueden crear y modificar estructuras de datos. Pulse en la pizarra con el botón derecho del ratón sobre los elementos de datos o sobre los punteros para abrir menús de contexto. Puede usar las herramientas de la barra de herramientas del editor visual de grafos para modificar los elementos en la pizarra del editor visual de grafos.

Barra de herramientas del editor visual de grafos

  Esta barra de herramientas proporciona todas las herramientas del editor visual de grafos. Use las herramientas Añadir datos o Añadir conexión para crear nuevos elementos o para conectarlos, respectivamente. Los nuevos elementos de datos se añaden a la estructura de datos actualmente seleccionada en el selector de documentos. Tenga en cuenta que tanto Añadir datos como Añadir conexión poseen menús de contexto para seleccionar el tipo al que pertenecen los elementos creados. Para más detalles consulte .

Barra lateral

  A la derecha puede encontrar la barra lateral que le proporciona diversas herramientas para su flujo de trabajo.

  - Tipos de elementos: este elemento le brinda acceso directo a los tipos de punteros y de datos disponibles.

  - Diario: cada proyecto dispone de su propio diario que se puede usar para, &eg;, anotar tareas, resultados u observaciones.

  - Documentación: abra este elemento gráfico para tener acceso directo al manual y, a través de él, a la documentación de los guiones.

Editor de guiones

  En este editor de texto puede escribir algoritmos como se explica con más detalle en . Puede trabajar en varios documentos de guiones al mismo tiempo usando varias pestañas. Si el guion contiene cambios sin guardar aparecerá en su pestaña un símbolo con un disco.

Salida del guion

  Este área de texto muestra información de depuración o la salida del guion del algoritmo, dependiendo de la preferencia indicada en la parte superior de este elemento gráfico. Si el guion produce un error, se muestra de forma automática la salida de depuración.

Controles

  Aquí puede encontrar los controles para la ejecución de guiones. Se puede ejecutar el guion que esté abierto actualmente en el editor de guiones pulsando Ejecutar. Mientras ejecuta el guion, puede detener su ejecución pulsando el botón Detener. Tenga en cuenta que la ejecución con Un paso se detiene únicamente en determinadas palabras clave (consulte ).

### Barras de herramientas

Hay diferentes barras de herramientas para el editor visual de grafos que permiten acceder a funcionalidades con solo un clic. Por omisión se muestran las siguientes barras de herramientas:

- Barra de herramientas principal

- Barra de herramientas principal

#### Barra de herramientas principal

La Barra de herramientas principal se compone de las siguientes acciones. Al hacer clic en una acción, el puntero del ratón aplica dicha acción a la pizarra del editor visual de grafos:

- Mover: para seleccionar elementos dispone de dos alternativas: puede pulsar en un espacio sin utilizar en la pizarra, mantener el ratón pulsado para dibujar un rectángulo que contenga elementos de datos y punteros para seleccionar dichos elementos, o bien hacer clic directamente en un elemento sin seleccionar para seleccionarlo. Si pulsa sobre un elemento seleccionado o un conjunto de elementos seleccionados, respectivamente, se pueden mover dichos elementos manteniendo el ratón pulsado y moviéndolo. También se pueden mover los elementos seleccionados mediante las teclas de las flechas.

- Añadir datos: haga clic en cualquier posición de la pizarra del editor visual de grafos para crear un nuevo elemento de datos que pertenezca a la estructura de datos seleccionada actualmente. Si mantiene pulsado el botón del ratón se mostrará un menú de contexto donde puede seleccionar el tipo de datos de los nuevos elementos de datos creados (solo si existen diferentes tipos de datos).

- Añadir conexión: haga clic en un elemento de dato, mantenga pulsado el ratón y dibuje una línea hacia otro elemento de dato al que debe apuntar la arista o el puntero. Esta acción solo se podrá realizar correctamente si el grafo actual permite añadir dicha arista (&eg;, en un grafo no dirigido, no se pueden añadir varias aristas entre dos elementos de datos). Si mantiene pulsado el botón del ratón se mostrará un menú de contexto en el que puede seleccionar el tipo de los punteros recién creados (solo si existen diferentes tipos de punteros).

- Borrar: haga clic en un elemento para borrarlo. Si borra un nodo, todas las aristas adyacentes también se borran.

- Escala: haga clic en la pizarra, mantenga pulsado el botón izquierdo del ratón y dibuje un rectángulo. La pizarra mostrará aumentada la zona seleccionada. Mediante la rueda del ratón también se podrá acercar o alejar la pizarra. Haciendo doble clic con el botón izquierdo del ratón se vuelve a la escala original.

#### Barra de herramientas de alineación

Se puede añadir la Barra de herramientas de alineación adicional. Pulsar una acción en dicha barra de herramientas tiene un efecto directo sobre los nodos seleccionados actualmente:

- Arriba: alinear los elementos de datos de forma vertical bajo el elemento de datos superior. Esto solo afecta a las posiciones verticales.

- Centro: alinea los elementos de datos de forma vertical bajo el centro de las posiciones verticales de todos los elementos de datos seleccionados. Solo afecta a las posiciones verticales.

- Base: alinea los elementos de datos de forma vertical bajo el elemento de datos inferior. Esto solo afecta a las posiciones verticales.

- Izquierda: alinea los elementos de datos de forma horizontal bajo el elemento de datos del extremo izquierdo. Esto solo afecta a las posiciones horizontales.

- Centro: alinea los elementos de datos de forma horizontal bajo el elemento de datos superior. Esto solo afecta a las posiciones horizontales.

- Derecha: alinear los elementos de datos de forma horizontal bajo el elemento de datos del extremo derecho. Esto solo afecta a las posiciones horizontales.

- Círculo: alinea los elementos de datos en un círculo cuyo diámetro es la máxima distancia entre los elementos de datos. Los elementos de datos se colocan en la misma secuencia en la que se verían desde el centro de gravedad de dichos elementos de datos.

- Minimizar aristas de cruce: reorganiza los elementos de datos seleccionados para minimizar el número de conexiones de cruce (aplicando el algoritmo de Fruchterman-Reingold).

### Trabajando con documentos de grafos

Un proyecto de &rocs; contiene uno o más documentos de grafos que se pueden modificar en el editor visual de grafos. Además, cada documento puede contener cualquier número de estructuras de datos. En este caso, todas las estructuras de datos del documento deben usar el mismo motor de estructura de datos. En esta sección explicaremos cómo crear documentos nuevos y cómo cambiar entre ellos.

#### La barra del selector de documentos

La barra del selector de documentos se usa para seleccionar el documento de grafo actual y también la estructura de datos actual. Cuando use las herramientas del editor visual de grafos para crear elementos de estructuras de datos, los nuevos elementos creados se añadirán automáticamente a la estructura de datos actual. Además, esta barra le proporciona accesos directos para borrar estructuras de datos existentes o crear otras nuevas dentro del documento actual.

- Nueva: esta acción crea una nueva estructura de datos usando un patrón de nombrado automático proporcionado por el motor de estructura de datos. La estructura de datos creada se añade al documento de grafos actualmente seleccionado.

- Borrar: esta acción borra la estructura de datos actualmente seleccionada en el selector de estructuras de datos del documento actual.

- Propiedades de la estructura de datos: abre un diálogo que proporciona acceso a las propiedades de la estructura de datos.

- Propiedades del documento: abre un diálogo que proporciona acceso a las propiedades del documento y a los tipos de datos y de puntero de dicho documento.

La barra de herramientas principal.
La barra del selector de documentos.

#### Crear e importar documentos de grafos

Para crear un nuevo documento de grafos o para añadir uno existente al proyecto, use Proyecto Nuevo documento de grafo o Proyecto Importar grafo de &rocs;. También puede importar documentos de grafos de otras aplicaciones (para ello, consulte ).

## Escritura y ejecución de algoritmos en &rocs;

&rocs; usa internamente el motor de guiones QtScript, que es un motor JavaScript específico. Esto significa que todos los algoritmos que implemente deben usar JavaScript. Este manual no cubre el funcionamiento de JavaScript ni cómo escribir código usando dicho lenguaje, aunque explicaremos cómo acceder a estructuras de datos, elementos de datos y punteros de las estructuras de datos desde el motor de guiones. Como nunca va a usar el objeto básico de estructura de datos, sino uno que proporciona el motor de la estructura de datos en uso y este motor extiende la funcionalidad de la estructura de datos, debería conocer dicha funcionalidad especializada. En especial, los motores de estructuras de datos usan términos comunes para sus dominios (nodos y aristas en grafos, hojas y raíces en árboles, etc.).

Es importante saber que los cambios realizados por el motor de guiones se reflejan directamente en las propiedades de la pizarra del editor visual de grafos. De ahí que los guiones modifiquen realmente las estructuras de datos

### Los elementos de la estructura de datos base

Cada motor proporciona un conjunto especial de funciones y propiedades para sus estructuras de datos y elementos. Pero también proporciona las propiedades y funciones que están definidas en la estructura de datos base. Por consiguiente, todo lo que se explica en estas secciones está disponible para cualquier motor de estructura de datos.

#### Propiedades de las estructuras de datos base

Las estructuras de datos se identifican por su nombre. Suponiendo que haya creado una estructura de datos con el nombre `testgraph`, podrá acceder a la estructura de datos simplemente escribiendo este identificador. Por ejemplo, para obtener una matriz con todos los elementos de datos de dicha estructura, puede escribir `testgraph.list_nodes();` en el guion.

##### Propiedades y funciones de la estructura de datos base

Cada estructura de datos `testgraph` tiene las siguiente propiedades que se pueden leer o escribir por `testgraph.property`:

    string name  // identificación de la estructura de datos

#### Propiedades y funciones del elemento de datos base

Cada elemento de datos tiene las siguientes propiedades que se pueden leer o escribir:

    double x      // coordenada x de la posición actual
        double y      // coordenada y de la posición actual
        double width  // tamaño
        string value  // valor
        int id        // identificador único del elemento de dato
        string name   // nombre
        string color  // color en hexadecimal

Además, es posible acceder a cada propiedad dinámica de un elemento de datos por su nombre.

Cada objeto de elemento de datos proporciona los siguientes métodos:

    int type();                         // tipo de dato del elemento de datos
        int set_type(int);                  // asignar el tipo de dato del elemento de datos
        void add_property(string name,      // añadir propiedad dinámica al elemento de datos con el nombre y valor especificados
                          string value);
        array adj_data();                   // lista de datos adyacentes
        array adj_pointers();               // lista de punteros adyacentes
        array input_pointers();             // lista de punteros de entrada
        array output_pointers();            // lista de punteros de salida
        array loop_pointers();              // lista de punteros que forman unbucle automático
        array connected_pointers(target);   // lista de punteros que apuntan al «objetivo»
        void  remove();                     // eliminar este elemento de datos

#### Propiedades y funciones del puntero base

Cada puntero tiene las siguientes propiedades, que se pueden leer o escribir:

    string color  // color en hexadecimal
        string value  // valor
        string name   // nombre
        double width  // anchura
        string style  // uno de los valores: «dot», «dash», «dash dot», «solid»

Además, es posible acceder a cada propiedad dinámica de un puntero por su nombre.

Cada objeto de puntero proporciona los siguientes métodos:

    int type();                         // tipo del puntero
        int set_type(int);                  // asignar el tipo del puntero
        void add_property(string name,      // añadir propiedad dinámica al elemento de datos con el nombre y valor especificados
                          string value);
        node start();                       // nodo de inicio del puntero
        node end();                         // nodo de destino del puntero
        void remove();                      // eliminar este puntero

### El motor de grafos

#### Propiedades y funciones del grafo

##### Propiedades específicas del motor de grafos

El diálogo de las propiedades de la estructura de datos permite el acceso a la configuración de las preferencias de un determinado motor de grafos. En él puede seleccionar el Tipo de grafo. El significado de estos tipos es el siguiente:

- Grafo: grafo en el que es posible que no existan varias veces las mismas aristas (con respecto a los puntos de inicio y fin).

- Multigrafo: grafo en el que pueden existir varias veces las mismas aristas (con respecto a los puntos de inicio y fin).

##### La estructura del grafo

Dado un objeto de estructura de datos del tipo «grafo», puede llamar a las siguientes funciones miembro:

    array list_nodes();                   // lista de todos los nodos del grafo
        array list_nodes(int type);           // lista de todos los nodos del tipo indicado
        array list_edges();                   // lista de todas las aristas del grafo
        array list_edges(int type);           // lista de todas las aristas del tipo indicado
        node add_node(name);                  // añadir un nuevo nodo y devolverlo
        edge add_edge(node from, node to);    // añadir nueva arista de «from» a «to» y devolverla
        array overlay_edges(int overlayID);   // lista de todas las aristas de la capa indicada
        edge add_overlay_edge(node from,
                              node to,
                              int overlayID); // añadir arista del tipo de puntero indicado en la capa especificada

##### Nodos de grafos

Dado un objeto de estructura de datos del tipo «grafo», puede llamar a las siguientes funciones miembro en los nodos del grafo, además de las propiedades que proporcionan los elementos de datos:

    array adj_nodes();                    // lista de todos los nodos adyacentes
        array adj_edges();                    // lista de las aristas conectadas
        array input_edges();                  // lista de la aristas de entrada
        array output_edges();                 // lista de todas las aristas de salida
        array loop_edges();                   // lista de todas las aristas que vuelven al nodo
        array connected_edges(node target);   // todas las aristas que conectan este nodo con el nodo «destino»

##### Aristas del grafo

Dadas las aristas de una estructura de datos de tipo «grafo», solo están disponibles las propiedades de la estructura de datos base.

#### Algoritmos de la estructura del grafo

El motor de grafos proporciona varias funciones especiales que se pueden usar desde el motor de guiones.

Cálculo del camino más corto

  Calcula el camino más corto entre los nodos inicio y fin. Ambos nodos deben pertenecer al mismo grafo. Este cálculo tiene en cuenta si el grafo es dirigido o no dirigido.

          array dijkstra_shortest_path node inicio node final

Distancias de la ruta más corta

  Calcula las distancias de los caminos más cortos entre el nodo inicio y el resto de nodos del grafo. Este cálculo tiene en cuenta si el grafo es dirigido o no dirigido.

          array distances node inicio

### El motor de listas enlazadas

#### Propiedades y funciones de las listas enlazadas

##### La estructura de lista enlazada

Dado un objeto de estructura de datos del tipo «lista enlazada», puede llamar a las siguientes funciones miembro:

    node begin();                           // proporciona el nodo de cabecera para la lista enlazada
        setBegin(node begin):                   // fijar el inicio del nodo como inicio de la lista y reordenar la lista
        createNode();                           // crear un nuevo nodo de lista

##### Nodos de la lista enlazada

Dado un objeto de estructura de datos del tipo «lista enlazada», puede llamar a las siguientes funciones miembro en los nodos del grafo, además de las propiedades que proporcionan los elementos de datos:

    node front();                           // devuelve el nodo precedente

##### Aristas de la lista enlazada

Dadas las aristas de una estructura de datos del tipo «lista enlazada», solo están disponibles las propiedades de la estructura de datos base.

### El motor de árbol con raíz

#### Propiedades y funciones del árbol con raíz

##### El motor de árbol con raíz

El diálogo de las propiedades de la estructura de datos permite el acceso a la configuración de las preferencias de un determinado motor de grafos. En él puede marcar la propiedad Mostrar todos los punteros para mostrar todos los punteros entre los nodos del árbol. Si no está marcada, los diferentes punteros entre los mismos nodos están comprimidos en uno solo.

##### La estructura de árbol con raíz

Dado un objeto de estructura de datos del tipo «árbol con raíz», se pueden leer y escribir las siguientes propiedades:

    ShowAllPointers     // fijar a «true» para mostrar todas las aristas; fijar a «false» si se deben comprimir varias aristas

Dado un objeto de estructura de datos del tipo «árbol con raíz», puede llamar a las siguientes funciones miembro:

    node add_data(string name);         // añadir un nodo al árbol con el nombre indicado
        void set_root_node(node root);      // fijar la raíz como raíz del nodo del árbol
        node root_node();                   // devolver el nodo raíz del árbol

##### Nodos de árbol con raíz

Dado un objeto de nodo del tipo «árbol con raíz», se pueden leer y escribir las siguientes propiedades:

    int numberOfChilds                  // fijar el número (permitido) de hijos de este nodo
        node left_child                     // solo lectura: el nodo que es el hijo de la izquierda
        node right_child                    // solo lectura: el nodo que es el hijo de la derecha
        node node_parent                    // solo lectura: el nodo que es el padre

Dado un objeto de nodo del tipo «árbol con raíz», puede llamar a las siguientes funciones miembro:

    node add_left_child(node child);    // añadir hijo a la izquierda
        node add_right_child(node child);   // añadir hijo a la derecha
        node add_child(node child, int i);  // añadir hijo como el enésimo hijo del nodo
        node add_node_parent(node child);   // añadir padre (solo tendrá éxito si aún no se ha asignado un padre)
        node left_child();                  // devolver el hijo de la izquierda
        node right_child();                 // devolver el hijo de la derecha
        node child_at(int i);               // devolver el enésimo hijo del nodo
        node node_parent();                 // devolver el padre del nodo

##### Aristas de árboles con raíz

Dadas las aristas de una estructura de datos del tipo «árbol con raíz», solo están disponibles las propiedades de la estructura de datos base.

### Control de la ejecución de guiones

#### Inclusión de archivos

Los documentos de guiones pueden incluir otros guiones. Esto puede ser útil para reducir el tamaño de los documentos de guiones y mejorar su legibilidad. Si usa Documento de guion Inclusiones posibles, obtendrá una lista de los archivos de guiones que vienen de serie con &rocs; y que puede incluir. Puede incluir un archivo de guion con la siguiente orden:

    include_script(string ruta);            // ruta relativa o absoluta al archivo de guion

#### Salida del guion

Durante la ejecución de un algoritmo, la salida de depuración y del programa se muestran en Depuración y Salida del guion. Si el motor de guiones detecta un error de sintaxis en el guion, también se muestra dicho error como un mensaje de depuración. Tenga en cuenta que todos los mensajes del programa también se muestran en la salida de depuración (como texto en negrita).

Puede controlar el texto que se muestra en la salida del guion mediante las siguientes funciones:

    output(string mensaje);            // muestra el mensaje como salida del guion
        debug(string mensaje);             // muestra el mensaje como salida de depuración

#### Control de la ejecución del guion

Puede ejecutar el guion de diferentes maneras.

Puede controlar el texto que se muestra en la salida del guion mediante las siguientes funciones:

- Iniciar: ejecuta el guion hasta su final.

- Detener: detener la ejecución del guion (solo está disponible cuando se ejecuta un guion).

- Un paso: ejecutar el guion hasta que finalice un paso. Un paso termina cuando el guion llama a la función `interrupt()`:

      interrupt();    // finaliza un paso

- Depurar: ejecutar el guion en modo de depuración. Esto abre el cuadro de diálogo de depuración de QtScript.

## Importar y exportar

### Intercambiar proyectos de &rocs;

Los proyectos de &rocs; se pueden importar y exportar como archivos comprimidos `.tar.gz`. Estos archivos comprimidos se pueden usar para intercambiar proyectos. Puede realizar importaciones y exportaciones usando Archivo Importar proyecto y Archivo Exportar proyecto, respectivamente.

### Importar y exportar documentos de grafos

Actualmente, &rocs; admite la importación y la exportación de los siguientes formatos de archivo:

- Archivos DOT, también conocidos como archivos Graphviz

- Archivos GML

- Archivos en formato de grafos Trivial

#### El formato de archivo de grafos Trivial

El Formato de grafo trivial (TGF) es un formato de archivo sencillo basado en texto para describir grafos. Un archivo TGF consiste en una lista de definiciones de nodos, que enlazan los ID de los nodos con etiquetas, seguida por una lista de las aristas. En este formato solamente se puede tener una etiqueta por nodo y un valor por arista. &rocs; interpreta los grafos importados como grafos no dirigidos. Los grafos exportados contendrán dos aristas por conexión si la conexiones son bidireccionales.

##### Especificación del formato

- El archivo comienza con una lista de nodos (un nodo por línea), seguida por una línea que contiene únicamente el carácter «#», seguida por una lista de aristas (una arista por línea).

- Un nodo consta de un entero (identificador), seguido por un espacio y por una cadena de texto.

- Una arista consta de dos enteros (identificadores) separados por un espacio, seguidos por un espacio y una cadena de texto. Se supone que la arista dirigida apunta desde el primer identificador hasta el segundo.

##### Ejemplo

    1 nodo inicial
    2 transmisor
    3 pila
    #
    1 2 azul
    2 1 rojo
    2 3 verde

#### Lenguaje DOT / Formato de archivo de grafos Graphviz

El lenguaje DOT es un lenguaje de descripción de grafos en texto sin formato que permite tanto una representación de grafos muy legible para humanos como de proceso eficiente para los programas de diseño de grafos. DOT es el formato de archivo predeterminado para la suite de visualización de grafos Graphviz, pero también se usa ampliamente por otras herramientas de grafos. Las extensiones de archivo típicas para DOT son .gv y .dot.

##### Funcionalidades no permitidas

&rocs; puede analizar cualquier archivo de grafos que contenga un grafo definido conforme a la especificación del lenguaje DOT http://www.graphviz.org/content/dot-language. La implementación de las funcionalidades de este lenguaje es completa, a pesar de las siguientes excepciones:

- subgrafo: debido a la falta del concepto de subgrafo en &rocs;, los subgrafos solo se importan como un conjunto de elementos de datos y conexiones. En especial, no se importan las conexiones hacia o desde subgrafos.

- Atributos &HTML; y &XML;: los atributos (como las etiquetas) que contienen sintaxis &HTML; o &XML; se leen sin cambios. En especial, no se lee de estos atributos ninguna información sobre ajustes de tipos de letra ni estilos.

##### Ejemplo

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

## Créditos y licencia

&rocs;

Copyright del programa:

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

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

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

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

Copyright de la documentación:

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

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

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

Traducido por Leticia Martín Hernández leticia.martin@gmail.com, Rocío Gallegotraducciones@rociogallego.com y Eloy Cuadra ecuadra@eloihr.net.

&underFDL; &underGPL;

## Instalación

### Cómo obtener &rocs;

&install.intro.documentation;

### Compilación e instalación

&install.compile.documentation;

&documentation.index;