Manual de Rocs

# 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
Traducción: Eloy Cuadra
revisión Rocs 2.1.50 (Applications 16.04) (2016-04-10)

Aviso Legal

Rocs is a graph theory tool by 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.

For all them, Rocs provides an easy to use graphical editor for creating graphs, a powerful scripting engine to execute algorithms, and several helper tools for simulations, experiments, and graph exports. The typical way of using Rocs is to create a graph, either by hand (i.e., dragging nodes and edges to the whiteboard), or by using one of the graph generators. Graph algorithms then can be implemented and executed on the created graph and all changes, which the algorithm performs, are visible immediately in the graph editor.

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

In some scenarios, graphs consist of different types of edges (e.g., an undirected graph plus the tree edges computed by a breadh-first-search algorithm) that shall be handled and displayed differently. For this, besides a default edge type, you can define arbitrary other edge types. Each edge type has its individual visual representation, dynamic properties, and can be set to be either undirected or directed. The scripting interface provides convenience methods to specifically access only edges of specific types.

### Tipos de nodos

Analog to edge types, you can define different types of nodes of a graph (e.g., to give some nodes special roles). Each node type has its own visual representation and dynamic properties.

### Propiedades

Every (node or edge) element can have properties. Those properties must be setup at the corresponding node or edge type. Properties are identified and accessed by their names and can contain any value. To create new or change existing properties, use the Element Types sidebar and use the Properties button to open the property dialog.

You can also use the scripting engine to access registered properties and change their values. In the following example we assume that the property "weight" is registered for the default edge type.

    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.

Our goal is to visualize the relationship of the matching and the minimum vertex cover. For this, we want to specify two edge types, one to display matching edges and one type to display "ordinary" edges, as well as two node types that we use to distinguish nodes contained in C and those not contained in 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

We use the Element Types and create a second node type as well as a second edge type. For both new types we open the properties dialog by using the respective Properties buttons and set the IDs to `2`. Furthermore, we change the colors of elements of these two new types (to distinguish them from the default types). Finally, we set all edge types to be bidirectional, and the IDs of the default types to `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

The algorithm can be executed by the Run button at the script control panel.

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

  The editor provides a whiteboard at that nodes and edges can be placed. Double-clicking at any of its elements opens a corresponding property menu. You can use the tools from the Graph Editor Toolbar to create and modify graphs.

Graph Editor Toolbar

  The toolbar provides the Create Node or Create Edge tools, for creating new elements on the whiteboard. Note the extra-toolbar for selecting the respective node or edge type that becomes visible of one of these tools is selected. Also tools for selecting and moving as well as deleting elements are available here. For details see “Graph Editor Toolbar”.

Barra lateral

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

  - Element Types: This widget gives you direct access to the available edge and node types.

  - Journal: Each project has its own journal that can be used to, por ejemplo note tasks, results, or observations.

  - Scripting API: To get direct access to the script documentation, you can open this widget.

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.

Script Output

  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

  Here you can find the controls for executing scripts. You can execute the script that is currently open at the script editor by pressing Run. While the script is executed, it is possible to stop execution by pressing the Stop button.

Graph Editor Toolbar
Graph Editor Toolbar

## Graph Editor Toolbar

This toolbar consists of the following actions. Clicking at an action means that your mouse pointer applies this action at the graph editor whiteboard:

- Select and Move: To select elements, either click at unused space at the whiteboard, keep the mouse pressed and draw a rectangle that contains some data elements and/or edges to select these elements or otherwise directly click at an unselected element to select this element. If you click at a selected element or a set of selected elements, respectively, by keeping the mouse pressed and moving around you can move these elements. Moving selected elements is also possible with the arrow keys.

- Create Node: Click at an arbitrary position at the graph editor whiteboard to create a new data element that belongs to the currently selected data structure. By keeping the mouse pointer pressed at the button, a menu shows up at which the data type of the new created data elements can be selected (only if different data types exist).

- Create Edge: Click at one data element, keep the mouse pressed and draw a line to another data element to which the edge shall point. This action is only successful if the current graph allows to add this edge (por ejemplo, in an undirected graph you are not allowed to add multiple edges between two data elements). By keeping the mouse pointer pressed at the button, a menu shows up at which the edge type of the new created edges can be selected (only if different edge types exist).

- Delete: Click at an element to delete it. If you delete a node, all adjacent edges are also deleted.

Capítulo 3. Guiones
Guiones

# Capítulo 3. Guiones

## Ejecución de algoritmos en Rocs

Rocs internally uses the QtScript Java Script engine. This means, all algorithms that you implement must use Java Script. In the following, we explain how to access and change elements of a graph document from the scripting engine. It is important to note that changes done by the scripting engine are directly reflected at the properties at the graph editor elements.

### Control de la ejecución del guion

Existen diferentes modos para ejecutar los algoritmos:

- Run: Execute the script until it finishes.

- Stop: Stop script execution (only available while a script is executed).

### Script Output

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

Rocs projects can be imported and exported as archived `.tar.gz` files. These archives can be used to exchange projects. Import and Export can be done with Graph Document → Import Graph and Graph Document → Export Graph as, respectively.

### Importar y exportar documentos de grafos

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

- DOT files, also known as Graphviz files

- GML files

- Archivos en formato de grafos Trivial

- El formato del lenguaje de marcas Keyhole

#### El formato de archivo de grafos Trivial

The Trivial Graph Format (TGF) is a simple text-based file format for describing graphs. A TGF file consists of a list of node definitions, that map the node IDs to labels, followed by a list of the edges. In this format it is only possible to have one label per node and one value per edge. Rocs interprets imported graphs as undirected graphs. Exported graphs will contain two edges per connection if connections are bidirectional.

##### Especificación del formato

- The file starts with a list of nodes (one node per line), followed by a line with the only character "#", followed by a list of edges (one edge per line).

- 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

#### DOT Language / Graphviz Graph File Format

The DOT language is a plain text graph description language that allows both,a good human readable representation of graphs as well as an efficient processing by graph layout programs. DOT is the default file format for the Graphviz graph visualization suite, but is also widely used by other graph tools. The usual file extensions for DOT are .gv and .dot.

##### Funcionalidades no permitidas

Rocs can parse every graph file that contains a graph specified according to the DOT language specification[1]. The support of language features is complete, despite of the following exceptions:

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