# The &rocs; Handbook

Tomaz
Canabrava
tomaz.canabrava@gmail.com
Andreas
Cord-Landwehr
cordlandwehr@googlemail.com
2009
Tomaz Canabrava
2011-2012
Andreas Cord-Landwehr
2012-12-02
1.8.0 &kde; 4.10
&FDLNotice;

&rocs; is a graph theory tool for KDE.

KDE
kdeedu
mathematics
math
graphs
node
edge

## Introduction

In this chapter we provide an overview of the core features and the workflow of &rocs;. For the eager reader, who wants to start using &rocs; immediately, we suggest to read at least and using as a reference when writing algorithms.

### Goals, Target Audience and Workflow

&rocs; is a Graph Theory IDE for everybody interested in designing and analyzing graph algorithms. This explicitly includes

- lecturers, who want to demonstrate algorithms to their students,

- students, who want to understand and see how their algorithm perform,

- and everybody, who is interested in data structures and algorithms.

For all these users, &rocs; provides an easy to use data structure editor for creating the data structures, a powerful scripting engine to execute algorithms, and several helper tools for your simulations and experiments.

The typical workflow when using &rocs; is to start by creating a graph with the visual graph editor. You can do this either by hand, this is adding data elements and connect them, or by using one of the data structure generators (if available for the currently selected data structure backend). Data structure generators can be found at Graph Document Tools Generate Graph. Further, you can assign values to the data structure elements, either by hand or using Graph Document Tools Assign Values. Finally, you can write your algorithm in JavaScript and execute it with the just created data structure. All changes that your algorithm perform at the data structure will be directly visible at the visual graph editor.

A Screenshot of &rocs;.
A Screenshot of &rocs;.

### &rocs; in a Nutshell

In this section we provide a compact overview of the core elements of &rocs;. We explain the important notions of data structures, data structure backends, and element types. Understanding of these concepts is useful to understand how data structures can be created and modified in &rocs;.

In general &rocs; works with projects: when opening &rocs; an empty project is created and you can replace it by loading or importing another project. Hereby, a project itself consists of graph documents and scripts.

#### Graph Documents and Data Structure Backends

A graph document represents the content of a whiteboard in the visual graph editor. Hereby, a graph document can contain several data structures at once, but only one data structure backends. Data structure backends are present for several graph types (general graphs, linked lists, rooted trees) and provide for their specific graph types additional functionality. That can be automatic positioning of the elements, special icon sets, or an extended set of script functions for use in your algorithms. (for details look at the corresponding handbook section). It is possible to change the data structure backend of a graph document, though information can be lost (e.g., edges of a circle in a general graph won't be added to a tree, if you switch to the rooted tree backend).

Graph documents form also the base for defining pointer types and data types.

#### Data Structures

Data structures are the base of all work in &rocs;. You can add one or several of them to a graph document, add data elements (nodes, datums) and pointers to them, and modify them by scripts. For this, each data structure has its unique name by which it can be accessed from your scripts. Due to your choice of the current data structure backend it can happen that you cannot modify the data structures arbitrarily (e.g., a tree should never contain a cycle). The data structure backend is determined by the data structure backend associated with the corresponding graph document that contains the data structure.

#### Pointer Types

By pointer types you can define different types of pointers to be used in your data structures. This is, a pointer type can get an individual layout (essentially a color) and it is easy to access only pointers of a specific type from your scripts. Typical use cases for pointers can be to implement meta-edges at your data structures that visualize relationships between data elements (e.g., visualize communication interests). But also, if your scripts shall identify specific kinds of edges (e.g., tree and cross edges at the depth first search algorithm), pointer types can be an elegant way to implement that.

#### Data Types

In several data structure problems, a set of data elements should be parted into groups of different types (e.g., clustering problems or covering problems). Or it is useful for the execution of an algorithm to specify a data element type to express a specific type (e.g., breath first search). For such use cases you can define data types. Each data type has its own icon and data types of some type can easily be accessed from your scripts.

#### Dynamic Properties

Every data element and pointer can have many properties. Some of these properties are default from data structure backend. See the documentation of the data structure backend for more details. To add further properties to the data elements and pointers, you can add dynamic properties to them. Each dynamic property is identified by its name and can contain any value associated with it. The name must start with a letter (a-z or A-Z) and can contain only letters, numbers and '_'. If you try to use any invalid character in the property name, the property will not be changed.

To add dynamic properties, use the Data Properties and Pointer Properties dialogs from the context menus of the respective elements or the script functions as explained in .

You can also use the scripts. You just need to use the `add_property` with the name and value of your property. After that, you can use node/pointer.propertyName to set/get the values.

Here is an example of how to use dynamic properties with data structure backend "Graph".

    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

In this section we want to create an example project to explore some of the most important functions of &rocs;. The goal is to create a graph and a script that illustrates a simple 2-approximate algorithm for the minimum vertex cover problem. The minimum vertex cover problem is the problem to find a subset of graph nodes C of minimal size such that each graph edge is connected to at least one node in C. This problem is known to be NP-hard and we want to illustrate how to find an approximation of factor 2 by finding a matching in the given graph (in the following we use the common terms for graph algorithms: graph is the data structure, nodes are the data elements, edges are the pointers).

Our goal is to visualize the correspondence of the matching and the minimum vertex cover. For this, we want to specify two pointer types, one to display matching edges and one type to display ordinary edges, as well as two data types that we use to distinguish nodes contained in C and those not contained in C.

#### Generate a Graph

For the data structure backend "Graph", &rocs; ships a helper tool that can generate graphs. We go to Graph Document Tools Generate Graph. There we generate a "Random Graph" with 30 nodes, 90 edges, and with seed 1 (the seed is the starting seed for the random graph generator; using the same seed multiple times results in same and reproducible graphs). Finally, we modify the graph name at the data structure panel and call the graph `testgraph`.

#### Create Types

We use the Document Properties Button at the data structure panel to open the properties dialog for data and pointer types of the current graph document. For the data types we add a new type called "C", which automatically gets ID `1`. For this type we select the server picture as icon. Furthermore, we switch to the pointer type page and add a new pointer type called "matching". This gets automatically ID `1` and we set the color to blue.

#### The Algorithm

At last we have to implement the approximation algorithm. For this we use the following implementation:

    var E = testgraph.list_edges(); // set of unprocessed edges
    var C = new Array();            // matching edges
    while (E.length > 0) {
        var e = E[0];        // we take first edge e={u,v}
        var u = e.start();
        var v = e.end();
        e.set_type(1);        // set edge to be a matching edge
        E.shift();            // remove e (i.e., E[0]) from edge list
        C.push(u);            // add u to C
        C.push(v);            // add v to C

        // mark u,v as nodes in C
        u.set_type(1);
        v.set_type(1);

        // remove from E all edges incident to u or v
        var adjacent = u.adj_edges();
        for (var i=0; i < adjacent.length; i++) {
            var index = E.indexOf(adjacent[i]); // find the index
            if (index!=-1) {
                E.splice(index, 1); // remove it if really found
            }
        }
        var adjacent = v.adj_edges();
        for (var i=0; i < adjacent.length; i++) {
            var index = E.indexOf(adjacent[i]); // find the index
            if (index!=-1) {
                E.splice(index, 1); // remove it if really found
            }
        }
    }
    output("Vertex Cover contains " + C.length + " nodes.");

#### Execute the Algorithm

Finally we want to execute the algorithm. For this we can start the execution by the Run Button at the script control panel.

## The &rocs; User Interface

### General Elements of the User Interface

The user interface is divided into several logical parts as presented at the screenshot below.

GUI elements of the &rocs; interface.
GUI elements of the &rocs; interface.

Document Selector

  At this top menu bar you must select the current document and data structure. Creating and deleting of data structures as well as access to data structure properties is also possible there.

Visual Graph Editor

  This is the whiteboard at which data structures can be created and modified. Right click at the whiteboard, at data elements, or at pointers to open context menus. You can use the tools from the Visual Graph Editor Toolbar to modify the elements at the visual graph editor whiteboard.

Visual Graph Editor Toolbar

  This toolbar provides all tools for the visual graph editor. Use the Add Data or Add Connection tool to create new elements or to connect elements, respectively. New data elements are added to the data structure that is currently selected at the Document Selector. Note that Add Data and Add Connection both have context menus to select the type of which the created elements shall be. For details see .

Side Bar

  At the right, you can find the side bar that provides several tools for your workflow:

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

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

  - Documentation: To get direct access to the handbook and by this to the script documentation, you can open this widget.

Script Editor

  In this text editor you can write algorithms as explained in detail in . You can work on several script documents simultaneously by using several tabs. The disk symbol at a tab appears if the script contains unsaved changes.

Script Output

  This text area either shows debug information or the script output of your algorithm, depending on the toggled setting at the top of this widget. If the script throws an error, automatically the debug output is presented.

Controls

  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. Note that the One Step execution only stops at specific keywords (see ).

### Toolbars

There are different toolbars for the visual graph editor that allow you to access features by only one click. Per default, the following toolbars are shown:

- Main Toolbar

- Alignment Toolbar

#### Main Toolbar

The Main Toolbar consists of the following actions. Clicking at an action means that your mouse pointer applies this action at the visual graph editor whiteboard:

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

- Add Data: Click at an arbitrary position at the visual 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 context menu shows up at which the data type of the new created data elements can be selected (only if different data types exist).

- Add Connection: Click at one data element, keep the mouse pressed and draw a line to another data element to which the pointer/edge shall point. This action is only successful if the current graph allows to add this edge (&eg;, 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 context menu shows up at which the pointer type of the new created pointers can be selected (only if different pointer types exist).

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

- Zoom: Click at the whiteboard, keep the &LMB; pressed, and by this draw a rectangle. The whiteboard will be zoomed to the selected area. Using the mousewheel to zoom in or out as well. A double click with the &LMB; restores the original zoom.

#### Alignment Toolbar

You can add the optional Alignment Toolbar. Pressing an action at this toolbar has direct effect to the currently selected nodes:

- Top: Align the data elements at the vertical position of the top-most data element. This only affects the vertical positions.

- Center: Align the data elements at the vertical position given by the center of all selected data elements vertical positions. This only affects the vertical positions.

- Base: Align the data elements at the vertical position of the bottom-most data element. This only affects the vertical positions.

- Left: Align the data elements at the horizontal position of the left-most data element. This only affects the horizontal positions.

- Center: Align the data elements at the horizontal position of the top-most data element. This only affects the horizontal positions.

- Right: Align the data elements at the horizontal position of the right-most data element. This only affects the horizontal positions.

- Circle: Aligns the data elements at a circle of diameter equals to the maximal distance of the data elements. The data elements are positioned in the same sequence as given by view from the center of gravity of these data elements.

- Minimize Crossing Edges: Rearrange the selected data elements to minimize the number of crossing connections (application of the Fruchterman-Reingold algorithm).

### Working with Graph Documents

A &rocs; project contains one or multiple graph documents that can be edited with the visual graph editor. Further, each document can contain an arbitrary number of data structures. Here, data structures of a document all use the same data structure backend. This section will explain how to switch between documents and how to create new ones.

#### The Document Selector Bar

The document selector bar is used to select the current graph document and further the current data structure. Using the visual graph editor tools to create data structures elements will automatically add those newly created elements to the current data structure. Also, this bar gives direct access to delete existing or create new data structures within the current document.

- New: This action creates a new data structure using an automatic naming pattern given by the data structure backend. The created data structure is added to the currently selected graph document.

- Delete: This action deletes the data structure that is currently selected in the data structure selector for the current document.

- Data Structure Properties: Open a dialog that gives access to the data structure properties.

- Document Properties: Open a dialog that gives access to the document properties as well as the data and pointer types of the document.

The Main Toolbar.
The Document Selector Bar.

#### Create and Import Graph Documents

To create a new graph document or to add an existing one to the project, use Project New Graph Document or Project Import &rocs; Graph. You can also import graph documents from third party applications (for this, see ).

## Writing and Executing Algorithms in &rocs;

&rocs; internally uses the QtScript scripting engine, which is a specific JavaScript engine. This means, all algorithms that you implement must use JavaScript. How JavaScript works and how to write JavaScript code is not covered in this handbook, though we explain how to access data structures, data elements and pointers of your data structures from the scripting engine. Since you never use the basic data structure object but one that is provided by the currently used data structure backend, the functionality of the data structure is extended by the corresponding backend and you should have a look at the specialized functionality. Especially, data structure backends use the common terms from their domain (nodes and edges in graphs, leafs and roots in trees, etc.)

It is important to know that changes done by the scripting engine are directly reflected at the properties at the visual graph editor whiteboard. Hence, the scripts actually modify the data structures.

### The Base Data Structure Elements

Every backend provides a special set of functions and properties for its data structures and their elements. But also every backend provides the properties and functions that are defined for the base data structure. Hence, everything explained in this sections is available for every data structure backend.

#### Base Data Structures Properties

Data structures are identified by their names. Assuming you created a data structure with name `testgraph`, then you can access the data structure simply by writing this identifier. For example, to get an array with all data elements in the given data structure, you can write `testgraph.list_nodes();` in the script.

##### Base Data Structure Properties and Functions

Each data structure `testgraph` has the following properties that can be read or written by `testgraph.property`:

         string name  // identification of the data structure

#### Base Data Element Properties and Functions

Each data element has the following properties that can be read or written:

        double x      // x coordinate of current position
        double y      // y coordinate of current position
        double width  // size
        string value  // value
        int id        // unique identifier for data element
        string name   // name
        string color  // color in HEXA

Further, every dynamic property of a data element can be accessed by its name.

Each data element object provides the following methods:

        int type();                         // data type of data element
        int set_type(int);                  // set data type of the data element
        void add_property(string name,      // add dynamic property to data element with specified name and value
                          string value);
        array adj_data();                   // list of adjacent data
        array adj_pointers();               // list of adjacent pointers
        array input_pointers();             // list of input pointers
        array output_pointers();            // list of output pointers
        array loop_pointers();              // list of pointers forming a self-loop
        array connected_pointers(target);   // list of pointers pointing to 'target'
        void  remove();                     // remove this data element

#### Base Pointer Properties and Functions

Each pointer has the following properties that can be read or written:

        string color  // color in HEXA
        string value  // value
        string name   // name
        double width  // width
        string style  // value out of: dot, dash, dash dot, solid

Further, every dynamic property of a pointer can be accessed by its name.

Each pointer object provides the following methods:

        int type();                         // pointer type of pointer
        int set_type(int);                  // set pointer type of the pointer
        void add_property(string name,      // add dynamic property to data element with specified name and value
                          string value);
        node start();                       // start node of the pointer
        node end();                         // target node of the pointer
        void remove();                      // remove this pointer

### The Graph Backend

#### Graph Properties and Functions

##### Graph Backend Specific Properties

The data structure properties dialog allows access to configure settings specific to the Graph backend. There, with Graph Type you can select the type of the graph. The meaning of these types is as follows:

- Graph: Graph at which same edges (with respect to start and end points) may not exist multiple times.

- Multigraph: Graph at which same edges (with respect to start and end points) may exist multiple times.

##### The Graph Structure

Given a data structure object of type "Graph", you can call the following member functions:

        array list_nodes();                   // list of all nodes of the graph
        array list_nodes(int type);           // list of all nodes of given type
        array list_edges();                   // list of all edges of the graph
        array list_edges(int type);           // list of all edges of given type
        node add_node(name);                  // add new node and returns it
        edge add_edge(node from, node to);    // add new edge from 'from' to 'to' and returns it
        array overlay_edges(int overlayID);   // list of all edges in given overlay
        edge add_overlay_edge(node from,
                              node to,
                              int overlayID); // add edge of given pointer type/in specified overlay

##### Graph Nodes

Given a data structure object of type "Graph", you can call the following member functions on the graph nodes additionally to the properties provided by the Data elements:

        array adj_nodes();                    // list of all adjacent nodes
        array adj_edges();                    // list of connected edges
        array input_edges();                  // list of input edges
        array output_edges();                 // list of all output edges
        array loop_edges();                   // list of all edges looping to the node
        array connected_edges(node target);   // all edges that connect this to to node 'target'

##### Graph Edges

Given edges of a data structure of type "Graph", only the properties of the base data structure are available.

#### Graph Structure Algorithms

The graph backend provides some special functions that can be used from the scripting engine.

Shortest Path Computation

  Compute the shortest path between the nodes start and end. Both nodes must be of the same graph. This computation respects if the graph is directed or undirected.

          array dijkstra_shortest_path
          node start
          node end

Shortest Path Distances

  Compute the shortest path distances from node start to all other nodes of the graph. This computation respects if the graph is directed or undirected.

          array distances
          node start

### The Linked List Backend

#### Linked List Properties and Functions

##### The Linked List Structure

Given a data structure object of type "Linked List", you can call the following member functions:

        node begin();                           // gives the head node of the linked list
        setBegin(node begin):                   // set node begin as begin of list and rearrange list
        createNode();                           // create a new list node

##### Linked List Nodes

Given a data structure object of type "Linked List", you can call the following member functions on the graph nodes additionally to the properties provided by the Data elements:

        node front();                           // returns the node's predecessor

##### Linked List Edges

Given edges of a data structure of type "Linked List", only the properties of the base data structure are available.

### The Rooted Tree Backend

#### Rooted Tree Properties and Functions

##### Rooted Tree Backend

The data structure properties dialog allows access to configure settings specific to the Graph backend. There, by checking the Show all pointers property, all pointers between the tree nodes are shown. If unchecked, multiple pointers between same nodes are collapsed to one.

##### The Rooted Tree Structure

Given a data structure object of type "Rooted Tree", the following properties can be read or written:

        ShowAllPointers     // set to true if show all edges, set to false if multiple edges shall be compressed

Given a data structure object of type "Rooted Tree", you can call the following member functions:

        node add_data(string name);         // add a node to tree with given name
        void set_root_node(node root);      // set root as root node of the tree
        node root_node();                   // return root node of the tree

##### Rooted Tree Nodes

Given a node object of type "Rooted Tree", the following properties can be read or written:

        int numberOfChilds                  // set the number of (allowed) children for this node
        node left_child                     // read only: node that is the left child
        node right_child                    // read only: node that is the right child
        node node_parent                    // read only: node that is the parent

Given a node object of type "Rooted Tree", you can call the following member functions:

        node add_left_child(node child);    // add left child
        node add_right_child(node child);   // add right child
        node add_child(node child, int i);  // add a child as the i-th child of the node
        node add_node_parent(node child);   // add parent (only successful if no parent set, yet)
        node left_child();                  // return right child
        node right_child();                 // return left child
        node child_at(int i);               // return the i-th child of the node
        node node_parent();                 // return the node's parent

##### Rooted Tree Edges

Given edges of a data structure of type "Rooted Tree", only the properties of the base data structure are available.

### Controlling the Script Execution

#### Include Files

Your script documents can include other scripts. This can be useful to reduce the size of script documents and improve readability. Using Script Document Possible Includes you get a list of script files already shipped with &rocs; that could be included. You can include a script file with the following command:

        include_script(string path);            // relative or absolute path to script file

#### Script Output

During the execution of an algorithm, debug and program output is displayed in the Debug & Script Output. If the scripting engine detects a syntax error in your script, the error is also displayed as debug message. Note that all program messages are also displayed at the debug output (displayed as bold text).

You can control the text that is displayed at the script output by the following functions:

        output(string message);            // displays the message as script output
        debug(string message);             // displays the message as debug output

#### Control Script Execution

There are different execution modes for your scripts.

You can control the text that is displayed at the script output by the following functions:

- Start: Execute the script until it finishes.

- Stop: Stop script execution (only available if a script is executing).

- One Step: Execute script until one step ends. A step ends when the script calls the function `interrupt()`:

              interrupt();    // ends a step

- Debug: Execute script in debug mode. This opens the QtScript debug dialog.

## Import and Export

### Exchange &rocs; Projects

&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 File Import Project and File Export Project, respectively.

### Import and Export of Graph Documents

&rocs; currently supports import and export of the following file formats:

- DOT files, also known as Graphviz files

- GML files

- Trivial Graph Format files

#### Trivial Graph File Format

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.

##### Format Specification

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

- A node consists of an integer (identifier), followed by a space, followed by an arbitrary string.

- An edge consists of two integers (identifiers) separated by a space, followed by a space, followed by an arbitrary string. It is assumed that the directed edge points from the first identifier to the second identifier.

##### Example

    1 starting node
    2 transmitter
    3 sink
    #
    1 2 blue
    2 1 red
    2 3 green

#### 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 endings for DOT are .gv and .dot.

##### Unsupported Features

&rocs; can parse every graph file that contains a graph specified according to the DOT language specification http://www.graphviz.org/content/dot-language. The support of language features is complete, despite of the following exceptions:

- subgraph: Due to the lack of a subgraph concept in &rocs;, subgraphs are only imported as a set of date elements and connections. Especially, connections to or from subgraphs are not imported.

- &HTML; and &XML; attributes: Attributes (like labels) that contain &HTML; or &XML; syntax are read unchanged. Especially, not adjustment of fonts and styles are read from those attributes.

##### Example

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

## Credits and License

&rocs;

Program Copyright:

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

Documentation Copyright:

- Documentation copyright 2009 &Anne-Marie.Mahfouf; &Anne-Marie.Mahfouf.mail;

- Documentation copyright 2009 Tomaz Canabrava (tcanabrava AT kde.org)

- Documentation copyright 2011-2012 Andreas Cord-Landwehr (cordlandwehr AT googlemail.com)

&underFDL; &underGPL;

## Installation

### How to obtain &rocs;

&install.intro.documentation;

### Compilation and installation

&install.compile.documentation;

&documentation.index;