El manual de Rocs

# El manual de Rocs

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

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

Traducción: Leticia Martín Hernández
Traducción: Rocío Gallego
revisión Rocs 2.1.50 (Aplicaciones 16.04) (2016-04-10)

Aviso Legal

Rocs es una herramienta de teoría de grafos para KDE.

Capítulo 1. Introducción
Introducción

# Capítulo 1. Introducción

En este capítulo le proporcionamos un resumen de las funcionalidades principales y de los flujos de trabajo típicos. Las partes más importantes son “Rocs en pocas palabras” y Capítulo 3, Guiones, que deberían bastar para que cualquier nuevo usuario comience a usar Rocs.

## Objetivos, audiencia de destino y flujo de trabajo

Rocs es una herramienta de teoría de grafos para todos aquellos interesados en el diseño y el análisis de algoritmos de grafos. Esto incluye:

- a profesores que quieran mostrar algoritmos a sus estudiantes,

- a estudiantes e investigadores que quieran ver como funciona un algoritmo,

- y a cualquier persona interesada en estructuras de datos y algoritmos.

Para todos ellos, Rocs proporciona un editor gráfico muy fácil de usar para crear grafos, un potente motor de guiones para ejecutar algoritmos y diversas herramientas auxiliares para realizar simulaciones, experimentos y exportar grafos. El modo usual de usar Rocs consiste en crear un grafo, bien a mano (es decir, arrastrando nodos y aristas por la pizarra), o bien usando cualquiera de los generadores de grafos. A continuación puede implementar algoritmos de grafos y ejecutarlos sobre el grafo creado, con lo que cualquier cambio que realice el algoritmo se hará visible de forma inmediata en el editor de grafos.

Rocs en pocas palabras
Rocs en pocas palabras

## Rocs en pocas palabras

Cada sesión de Rocs es un proyecto: cuando abra Rocs se creará un proyecto vacío; cuando cargue algún proyecto, se convertirá en proyecto activo. En sí, un proyecto consta de documentos de grafos, de guiones o algoritmos. y de un diario.

### Documentos de grafos

Un documento de grafos representa el contenido de una pizarra en el editor de grafos. Contiene información sobre los tipos de nodo y aristas definidos por el usuario y sus propiedades, así como sobre los nodos y aristas ya creados. Es decir, Rocs entiende el conjunto de todos los nodos y aristas de un documento de grafos (no necesariamente conectados) que componen un grafo. Todo lo que pertenezca a un documento de grafos permanece accesible para el motor de guiones usando el objeto global `Document`.

### Tipos de aristas

En algunos escenarios, los grafos consisten en distintos tipos de aristas (por ejemplo, un grafo no dirigido más las tres aristas calculadas por un algoritmo de búsqueda en anchura) que se deben manejar y mostrar de forma diferente. Para ello, además de un tipo de arista por omisión, puede definir otros tipos de aristas adicionales. Cada tipo de arista tiene su representación visual individual, sus propiedades dinámicas y se puede cambiar de dirigido a no dirigido. La interfaz de guiones proporciona los métodos necesarios para acceder de forma específica a las aristas de determinados tipos.

### Tipos de nodos

Del mismo modo que para los tipos de aristas, puede definir diferentes tipos de nodos de un grafo (por ejemplo, para proporcionar un papel especial a algunos nodos). Cada tipo de nodo posee su propia representación visual y propiedades dinámicas.

### Propiedades

Cada elemento (nodo o arista) puede tener propiedades. Estas propiedades se deben configurar en el correspondiente tipo de nodo o arista. Los nombres de las propiedades pueden contener cualquier valor y sirven para identificarlas y para acceder a ellas. Para crear una nueva propiedad o para modificar una existente, use la barra lateral Tipos de elementos. Para abrir el diálogo de una propiedad, use el botón Propiedades.

También puede usar el motor de guiones para acceder a las propiedades registradas y modificar su valor. En el ejemplo siguiente se supondrá que la propiedad «weight» está registrada para el tipo de arista por omisión.

    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("peso del nodo " + i + ": " + nodes[i].weight);
    }

Tutorial
Tutorial

## 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 al menos a 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.

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 aristas (uno para mostrar las aristas coincidentes y otro para mostrar las aristas «ordinarias»), así como dos tipos de nodos que vamos a usar para distinguir los nodos contenidos en C y los que no están contenidos en C.

### Generación del grafo

Para crear el grafo, usaremos el generador por omisión que proporciona Rocs. Está disponible en menú principal: Documento de grafo → Herramientas → Generar grafo. Allí seleccionamos 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).

### Creación de los tipos de elementos

Usaremos Tipos de elementos para crear un segundo tipo de nodo y un segundo tipo de arista. Para estos dos nuevos tipos, abriremos el diálogo de propiedades usando sus respectivos botones Propiedades y fijaremos sus ID a `2`. Además, cambiaremos los colores de los elementos de estos dos nuevos tipos (para distinguirlos de los tipos por omisión). Finalmente, indicaremos que todos los tipos de aristas sean bidireccionales y fijaremos el ID de los tipos por omisión a `1`.

### El algoritmo

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

    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(); // 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.from();
        var v = e.to();
        e.type = 2;           // indicamos que la arista es 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.type = 2;
        v.type = 2;

        // eliminar de E todas las aristas en común con u o v
        var adjacent = u.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); // eliminarla si se encuentra
            }
        }
        var adjacent = v.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); // eliminarla si se encuentra
            }
        }
    }
    Console.log("La cobertura de vértices contiene " + C.length + " nodos.");

### Ejecución del algoritmo

El algoritmo se puede ejecutar usando el botón Ejecutar que hay en el panel de control del guion.

Capítulo 2. La interfaz de usuario de Rocs
La interfaz de usuario de Rocs

# Capítulo 2. La interfaz de usuario de Rocs

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

Editor de grafos

  El editor proporciona una pizarra en blanco en la que se pueden situar nodos y aristas. Si hace doble clic en cualquiera de sus elementos, se abrirá el correspondiente menú de propiedades. Puede usar las herramientas de la barra de herramientas del editor de grafos para crear y modificar grafos.

Barra de herramientas del editor de grafos

  Esta barra de herramientas proporciona las herramientas Crear nodo y Crear arista para crear nuevos elementos en la pizarra. Advierta la barra de herramientas adicional para seleccionar el correspondiente tipo de nodo o de arista que se hace visible al seleccionar una de estas herramientas. Aquí también dispone de herramientas para seleccionar y mover, así como para borrar elementos. Para más detalles consulte “Barra de herramientas del editor de grafos”.

Barra lateral

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

  - Tipos de elementos: esta ventana le proporciona acceso directo a los tipos de aristas y de nodos disponibles.

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

  - API de guiones: abra este elemento gráfico para tener acceso directo a la documentación de guiones.

Editor de guiones

  En este editor de texto puede escribir algoritmos como se explica con más detalle en Capítulo 3, Guiones. Puede trabajar en varios documentos de guiones al mismo tiempo usando varias pestañas.

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.

Barra de herramientas del editor de grafos
Barra de herramientas del editor de grafos

## Barra de herramientas del editor de grafos

Esta barra de herramientas 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 de grafos):

- Seleccionar y 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 o aristas 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.

- Crear nodo: 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ú donde puede seleccionar el tipo de datos de los nuevos elementos de datos creados (solo si existen diferentes tipos de datos).

- Crear arista: 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. Esta acción solo se podrá realizar correctamente si el grafo actual permite añadir dicha arista (p. ej., 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ú en el que puede seleccionar el tipo de las aristas recién creadas (solo si existen diferentes tipos de aristas).

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

Capítulo 3. Guiones
Guiones

# Capítulo 3. Guiones

## Ejecución de algoritmos en Rocs

Rocs usa internamente el motor de Java Script de QtScript. Esto significa que todos los algoritmos que implemente deben usar Java Script. A continuación explicaremos cómo acceder y modificar los elementos de un documento de grafos desde el motor de guiones. Es importante que tenga en cuenta que los cambios realizados por el motor de guiones se reflejan directamente en las propiedades de los elementos del editor de grafos.

### Control de la ejecución del guion

Existen diferentes modos para ejecutar los algoritmos:

- Ejecutar: ejecuta el guion hasta su final.

- Detener: detener la ejecución del guion (solo está disponible cuando se ejecuta un 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:

    Console.log(string mensaje);            // muestra el mensaje como salida del guion
        Console.debug(string mensaje);             // muestra el mensaje como salida de depuración
        Console.error(string mensaje);          // muestra el mensaje comosalida de error

### API del motor de guiones

Las diferentes partes de Rocs proporcionan elementos estáticos a los que se puede acceder desde el motor de guiones. Son las siguientes:

- `Document` para el documento de grafos

- `Console` para la salida de registro de la consola

Para el uso de la API y para una guía sobre los métodos que contienen, consulte la ayuda en línea disponible en la barra lateral de Rocs.

Capítulo 4. Importar y exportar
Importar y exportar

# Capítulo 4. Importar y exportar

## Intercambiar proyectos de Rocs

Los proyectos de Rocs se pueden importar y exportar como archivos comprimidos `.tar.gz`. Estos archivos se puede usar para intercambiar proyectos. La importación y la exportación se pueden llevar a cabo con Documento de grafo → Importar grafo y Document de grafo → Exportar grafo como, respectivamente.

### Importar y exportar documentos de grafos

En la actualidad, Rocs permite importar y exportar en los siguientes formatos de archivos:

- Archivos DOT, también conocidos como archivos Graphviz

- Archivos GML

- Archivos en formato de grafos Trivial

- El formato del lenguaje de marcas Keyhole

#### 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 buena representación legible para humanos como un procesamiento eficiente para los programas de diseño de grafos. DOT es el formato de archivo por omisión para la suite de visualización de grafos Graphviz, aunque también se usa ampliamente en otras herramientas de grafos. Las extensiones 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[1]. 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;
    }

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

Capítulo 5. Créditos y licencia
Créditos y licencia

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

Copyright de la documentación:

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

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

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

Traducido por Leticia Martín Hernández `(leticia.martin AT gmail.com)`, Rocío Gallego`(traducciones AT rociogallego.com )` y Eloy Cuadra `(ecuadra AT eloihr.net)`.

Esta documentación está sujeta a los términos de la Licencia de Documentación Libre GNU.

Este programa está sujeto a los términos de la Licencia Pública General GNU.