# O Manual do &rocs;

Tomaz
Canabrava
tomaz.canabrava@gmail.com
Andreas
Cord-Landwehr
cordlandwehr@googlemail.com
José
Pires

    zepires@gmail.com

Tradução
2009
Tomaz Canabrava
2011-2012
Andreas Cord-Landwehr
2012-08-23
1.7.70 &kde; 4.10
&FDLNotice;

O &rocs; é uma ferramenta da teoria dos grafos para o KDE.

KDE
kdeedu
matemática
matemática
grafos
nó
aresta

## Introdução

Neste capítulo, iremos dar uma visão geral sobre o &rocs;. Para o leitor que quiser começar a usar directamente o &rocs;, sugerimos que leia o e, enquanto escreve programas, use o como referência.

### Objectivos, Público-Alvo e Funcionamento

O &rocs; é um IDE da Teoria dos Grafos para todos os interessados no desenho e análise de algoritmos de grafos. Isto inclui explicitamente

- os professores que poderão querer demonstrar algoritmos aos seus alunos,

- os alunos que queiram compreender e ver como é que funcionam os seus algoritmos,

- e todos os que estejam interessados em algoritmos e estruturas de dados.

Para todos estes utilizadores, o &rocs; oferece um editor de grafos simples de usar para definir os grafos, um motor de programação em Qt Script, para executar os algoritmos, assim como diversos utilitários para configurar os seus grafos e estruturas de dados para as suas experiências.

O fluxo de trabalho típico no &rocs; é começar por criar um grafo com o editor visual do grafo. Poderá fazê-lo à mão, isto é, adicionando nós e ligando-os, ou então poderá usar um dos algoritmos auxiliares que poderá encontrar em Ferramentas Gerar o Grafo. Eventualmente, poderá também querer usar as ferramentas auxiliares em Ferramentas Atribuir Valores para atribuir valores iniciais aos nós e arestas do grafo. Finalmente, poderá atribuir um nome ao seu grafo. Este nome será então o identificador que deverá usar no motor de programação. Finalmente, poderá criar o seu algoritmo em JavaScript e executá-lo sobre a estrutura de dados acabada de criar. As alterações feitas pelo seu algoritmo são visíveis imediatamente no quadro do editor visual do grafo.

Uma imagem do &rocs;.
Uma imagem do &rocs;.

### O &rocs; em Resumo

Nesta secção, iremos dar uma visão geral breve sobre os elementos de base do &rocs;. Iremos explicar as noções importantes das estruturas de dados, dos 'plugins' de estruturas de dados e dos tipos de elementos. O conhecimento destes elementos é útil para compreender como poderá criar e modificar as estruturas de dados no &rocs;.

De um modo geral, o &rocs; funciona com projectos: ao abrir o &rocs;, é criado um projecto vazio e podê-lo-á substituir se carregar ou importar outro projecto. Como tal, um projecto em si consiste nos documentos de grafos e nos programas.

#### Documentos de Grafos e 'Plugins' de Estruturas de Dados

Um documento de grafo representa o conteúdo de um quadro branco no editor visual do grafo. Como tal, um documento de grafo poderá conter várias estruturas de dados ao mesmo tempo, mas somente um 'plugin' de estruturas de dados em especial. Os 'plugins' de estruturas de dados estão presentes para diversos tipos de grafos (grafos gerais, listas ligadas, árvores com raiz) e atribuir funcionalidades adicionais aos seus tipos de grafos específicos. Isso poderá ser o posicionamento automático dos elementos, os conjuntos de ícones especiais ou um conjunto extendido de funções do programa a usar nos seus algoritmos. (Para mais detalhes, veja a secção correspondente no manual). É possível alterar o 'plugin' da estrutura de dados de um documento de grafo, ainda que se possa perder informação (p.ex., as arestas de um círculo num grafo geral não serão adicionadas a uma árvore, caso mude para o 'plugin' de árvores com raiz).

Os documentos de grafos formam também a base para definir os tipos de arestas e tipos de dados.

#### Estruturas de Dados

As estruturas de dados são a base de todo o trabalho no &rocs;. Poderá adicionar uma ou várias a um documento de grafo, adicionar elementos de dados (nós, dados) e arestas para elas, e ainda modificá-las com programas. Para tal, cada estrutura de dados tem o seu nome único, com o qual poderá ser acedida pelos seus programas. Devido à sua escolha do 'plugin' de estruturas de dados actual, poderá acontecer que não consiga modificar as estruturas de dados de forma arbitrária (p.ex., uma árvore nunca deverá conter um ciclo). O 'plugin' de estrutura de dados é determinado pelo 'plugin' de estruturas de dados associado com o documento do grafo correspondente que contém a estrutura de dados.

#### Tipos de Arestas

Poderá definir diferentes tipos de arestas a usar nas suas estruturas de dados. Isto é, um tipo de aresta poderá obter uma disposição individual (basicamente uma cor) e é bastante simples aceder às arestas de um determinado tipo a partir dos seus programas. Os casos de uso típicos das arestas poderão ser a implementação de meta-arestas nas suas estruturas de dados que visualizam as relações entre os elementos de dados (p.ex., visualizar os interesses de comunicação). Do mesmo modo, se os seus programas deverão identificar tipos específicos de arestas (p.ex., arestas em árvore e cruzadas no algoritmo de pesquisa em profundidade), os tipos de arestas poderão ser uma forma elegante de implementar isso.

#### Tipos de Dados

Em diversos problemas de estruturas de dados, um conjunto de elementos de dados poderá ser repartido em grupos de tipos diferentes (p.ex., problemas de 'clusters' ou de cobertura). Por outro lado, é útil para a execução de um algoritmo indicar um tipo de elemento de dados que exprima um tipo específico (p.ex., pesquisa em largura primeiro). Para esses casos de uso, poderá definir tipos de dados. Cada tipo de dados tem o seu próprio ícone e os tipos de dados de um determinado tipo poderão ser acedidos a partir dos seus programas.

#### Propriedades Dinâmicas

Os vários elementos de dados e arestas poderão ter várias propriedades. Algumas dessas propriedades são predefinidas para o 'plugin' da estrutura de dados. Veja a documentação sobre o 'plugin' da estrutura de dados para mais detalhes. Para adicionar mais propriedades aos elementos de dados e arestas, poderá adicionar propriedades dinâmicas a eles. Cada propriedade dinâmica é identificada pelo seu nome e poderá conter qualquer valor associado a ela. O nome deverá começar por uma letra (a-z ou A-Z) e poderá conter apenas letras, números e '_'. Se tentar usar algum carácter inválido ao nome da propriedade, a propriedade não será alterada.

Para adicionar propriedades dinâmicas, use as janelas Propriedades dos Dados e Propriedades da Aresta, nos menus de contexto dos respectivos elementos ou as funções dos programas explicadas em .

Também poderá usar os programas. Apenas precisa de usar o `add_property` com o nome e o valor da sua propriedade. Depois disso, poderá usar a expressão nó/aresta.nomePropriedade para alterar/ler os valores.

Aqui está um exemplo de utilização das propriedades dinâmicas com o 'plugin' do grafo.

    nos = meuGrafo.list_nodes()
    for (var i = 0; i < nos.length; ++i ){
        nos[i].add_property("MinhaPropriedade", 0)
    }
    nos[0].MinhaPropriedade = 2
    nos[1].MinhaPropriedade = nos[0].MinhaPropriedade + 2

### Tutorial

Nesta secção, iremos querer criar um projecto de exemplo para explorar algumas das funções mais importantes do &rocs;. O objectivo é criar um grafo e um programa que ilustre um algoritmo de 2 aproximações para o problema da cobertura mínima de vértices. Este problema consiste em encontrar um sub-conjunto de nós do grafo C com um tamanho mínimo, de modo que cada aresta do grafo esteja ligada a pelo menos um nó do C. Este problema é conhecido por ser NP-difícil e queremos ilustrar como encontrar uma aproximação com um factor 2, encontrando uma correspondência no grafo indicado (no seguinte, usamos os termos comuns dos algoritmos de grafos: o grafo é a estrutura de dados, os nós são os elementos de dados e as arestas são os ponteiros).

O nosso objectivo é visualizar a correspondência da ocorrência e da cobertura mínima de vértices. Para tal, queremos mostrar dois tipos de arestas, um para mostrar as arestas correspondentes e outro para mostrar as normais, assim como dois tipos de dados que usamos para distinguir os nós contidos em C e os não-contidos.

#### Gerar um Grafo

Para o 'plugin' do grafo, o &rocs; oferece um utilitário que poderá gerar grafos. Poderemos ir ao menu Documento do Grafo Ferramentas Gerar o Grafo. Aí, iremos gerar um "Grafo Aleatório" com 30 nós, 90 arestas e com uma raiz 1 (a raiz é o valor de referência inicial para o gerador de grafos aleatórios; a utilização da mesma raiz várias vezes origina grafos iguais). Finalmente, iremos modificar o nome do grafo no painel da estrutura de dados e chamar ao grafo `grafoteste`.

#### Criar Tipos

Iremos usar o botão de Propriedades do Documento no painel de estruturas de dados para abrir a janela de propriedades dos tipos de dados e arestas do documento de grafo actual. Para os tipos de dados, iremos adicionar um novo tipo chamado "C", que irá obter automaticamente o ID `1`. Para esse tipo, iremos seleccionar a imagem do servidor como ícone. Para além disso, iremos mudar para a página do tipo de aresta e adicionar um novo tipo de aresta chamado "correspondente". Este irá obter automaticamente o ID `1` e iremos mudar a cor para azul.

#### O Algoritmo

Por último, temos de implementar o algoritmo de aproximação. Para tal, iremos usar a seguinte implementação:

    var E = grafoteste.list_edges(); // conjunto de arestas não processadas
    var C = new Array();            // arestas correspondentes
    while (E.length
    > 0) {
        var e = E[0];        // iremos usar primeiro a aresta e={u,v}
        var u = e.start();
        var v = e.end();
        e.set_type(1);        // mudar a aresta para ser correspondente
        E.shift();            // remover o 'e' (i.e., E[0]) da lista de arestas
        C.push(u);            // adicionar o 'u' ao C
        C.push(v);            // adicionar o 'v' ao C

        // marcar o 'u,v' como nós no C
        u.set_type(1);
        v.set_type(1);

        // remover do E todas as arestas que incidem em 'u' ou 'v'
        var adjacente = u.adj_edges();
        for (var i=0; i < adjacente.length; i++) {
            var indice = E.indexOf(adjacente[i]); // descobrir o índice
            if (indice!=-1) {
                E.splice(indice, 1); // remove-o se tiver sido encontrado
            }
        }
        var adjacente = v.adj_edges();
        for (var i=0; i < adjacente.length; i++) {
            var indice = E.indexOf(adjacente[i]); // descobrir o índice
            if (index!=-1) {
                E.splice(index, 1); // remove-o se tiver sido encontrado
            }
        }
    }
    output("A cobertura de vértices contém " + C.length + " nós.");

#### Executar o Algoritmo

Finalmente, queremos executar o algoritmo. Para tal, iniciamos a execução com o Botão de Execução no painel de controlo do programa.

## A Interface de Utilizador do &rocs;

### Elementos Gerais da Interface do Utilizador

A interface do utilizador está dividida em várias partes lógicas, como aparece na imagem abaixo.

Elementos gráficos da interface do &rocs;.
Elementos gráficos da interface do &rocs;.

Editor de Grafos Visual

  Este é o quadro onde poderá criar e modificar as suas estruturas de dados. Carregue com o botão direito no quadro, nos elementos de dados ou nas arestas para abrir os menus de contexto. Poderá usar as ferramentas da Barra de Edição Visual do Grafo para modificar os elementos no quadro visual do grafo.

Barra do Editor de Grafos Visual

  Estas são as ferramentas a usar para modificar as estruturas de dados no quadro do editor visual do grafo. Ao usar os botões Adicionar os Dados ou Adicionar uma Ligação, poderá criar novos elementos de dados ou então arestas, respectivamente, à estrutura de dados seleccionada de momento no item de Propriedades do Grafo. Lembre-se que as opções Adicionar Dados e Adicionar uma Ligação têm ambos menus de contexto para seleccionar o tipo de dados ou de aresta com que deverão ser criados os novos elementos. Para mais detalhes, consulte a secção .

Propriedades do Grafo

  No topo, poderá seleccionar o documento do grafo actual, abrir a sua janela de configuração e adicionar novas estruturas de dados ao documento actual (&ie;, ao quadro actual). Por baixo, poderá seleccionar a estrutura de dados actual. Aí, poderá modificar as propriedades do elemento de dados ou aresta (nomes, valores, objectos) que estão visíveis, carregando para tal nos botões respectivos. Ao carregar nos nomes dos tipos de dados e arestas, poderá aceder às suas janelas de configuração. Para mais detalhes, veja em .

Editor de Programas

  Neste editor de texto, poderá criar os algoritmos da forma descrita em . Poderá trabalhar com vários algoritmos ao mesmo tempo, abrindo ou criando novas páginas de programas no menu principal. O pequeno símbolo do disco aparece se existirem alterações por gravar.

Resultado de Depuração & Programas

  Esta área de texto poderá apresentar a informação de depuração ou o resultado do programa para o seu algoritmo, dependendo da configuração do resultado. Se o programa emitir um erro, será seleccionado automaticamente o resultado da depuração. Para além disso, o resultado da depuração apresenta todas as mensagens de resultados do programa, do mesmo modo.

Controlos

  Este menu controla a execução dos algoritmos. Poderá executar o programa que está aberto de momento no editor do programa se carregar em Executar. Enquanto o programa estiver em execução, é possível interrompê-lo se carregar no botão Parar. Lembre-se que a execução Um Passo só termina com palavras-chave específicas (veja em ).

### Barras de Ferramentas

Existem diferentes barras de ferramentas possíveis para o editor do grafo que lhe permitem aceder às funcionalidades apenas com um botão do rato. Por omissão, são apresentadas as seguintes barras de ferramentas:

- Barra Principal

- Barra de Alinhamento

#### Barra Principal

A Barra Principal consiste nas seguintes acções. Se carregar no nome de uma acção, significa que o seu cursor do rato aplica esta acção ao quadro do editor do grafo:

- Mover: Para seleccionar os elementos, tanto poderá carregar no espaço em branco do quadro, mantenha carregado o rato e desenhe um rectângulo que contenha alguns nós e/ou arestas para seleccionar estes elementos ou poderá então carregar directamente num elemento não seleccionado para escolher esse elemento. Se carregar num elemento ou conjunto de elementos seleccionados, poderá mover estes elementos em conjunto. A movimentação dos elementos seleccionados também é possível com as teclas de cursores.

- Adicionar Dados: Carregue numa posição arbitrária no quadro do editor do grafo para criar um novo nó que pertença ao grafo seleccionado de momento. Mantendo o botão do rato pressionado, irá aparecer um menu de contexto onde poderá escolher o tipo de dados dos novos elementos (somente se existirem outros tipos de dados diferentes).

- Adicionar uma Aresta: Carregue num nó, mantenha o rato pressionado e desenhe uma linha para outro nó, apontando a aresta nessa direcção. Esta acção só será bem-sucedida se o grafo actual permitir adicionar esta aresta (&eg;, num grafo não-direccionado, não poderá adicionar várias arestas entre dois nós). Mantendo o botão do rato pressionado, irá aparecer um menu de contexto onde poderá escolher o tipo de aresta dos novos elementos (somente se existirem outros tipos de dados diferentes).

- Apagar: Carregue num elemento para o apagar. Se apagar um nó, todas as arestas adjacentes serão também apagadas.

- Ampliar: Carregue no quadro, mantenha o rato carregado e com isto desenhe um rectângulo. O quadro ampliar-se-á para a área seleccionada. Também pode usar a roda do rato para ampliar ou reduzir. Se fizer duplo-click com o &LMB;, irá repor a ampliação original.

A Barra Principal
A Barra Principal

#### Barra de Alinhamento

Poderá adicionar a Barra de Alinhamento opcional. Se carregar numa acção desta barra de ferramentas, fará um efeito directo sobre os nós seleccionados de momento:

- Topo: Alinha os elementos de dados na vertical para a posição do elemento superior. Isto só afecta as posições verticais.

- Centro: Alinha os elementos de dados na vertical, com base no centro das posições verticais de todos os elementos de dados seleccionados. Isto só afecta as posições verticais.

- Base: Alinha os elementos de dados na vertical para a posição do elemento inferior. Isto só afecta as posições verticais.

- Esquerda: Alinha os elementos de dados na horizontal para a posição horizontal do elemento mais à esquerda. Isto só afecta as posições horizontais.

- Centro: Alinha os elementos de dados na horizontal para a posição central do elemento do tipo. Isto só afecta as posições horizontais.

- Direita: Alinha os elementos de dados na horizontal para a posição horizontal do elemento mais à direita. Isto só afecta as posições horizontais.

- Círculo: Alinha os elementos de dados num círculo com o diâmetro igual á distância máxima destes elementos. Estes são posicionados na mesma ordem que foi indicada pelo centro de gravidade destes elementos de dados.

- Minimizar as Arestas Cruzadas: Reorganiza os elementos de dados seleccionados para minimizar o número de arestas cruzadas (aplicando o algoritmo de Fruchterman-Reingold).

A Barra de Alinhamento
A Barra de Alinhamento

### O Painel de Propriedades do Grafo

No topo do painel, poderá seleccionar o documento do grafo actual. Por baixo deste, poderá criar estruturas novas ou configurar as existentes.

#### Selecção do Documento e Propriedades

No topo do painel, poderá seleccionar o documento do grafo actual. O documento do grafo representa o quadro que é apresentado no editor visual do grafo. Para criar um novo documento de grafo ou para adicionar um existente ao projecto, use as opções Projecto Novo Documento de Grafo ou Projecto Importar um Grafo do &rocs;. Poderá também importar documentos de grafos a partir de aplicações de terceiros (para tal, consulte ). Ao carregar em Propriedades, poderá aceder às propriedades do documento do grafo.

#### Criar uma Nova Estrutura de Dados

Poderá criar uma nova estrutura de dados se introduzir um identificador (sem espaços nem caracteres especiais) e depois carregando em Adicionar. O identificador é usado para aceder à estrutura de dados dos algoritmos.

#### Configurar a Estrutura de Dados

Todas as estruturas de dados disponíveis do documento de grafo actual são apresentadas numa lista. Ao seleccionar uma, são mostradas as opções de configuração da estrutura de dados correspondente:

- Apagar: Apaga esta estrutura de dados.

- Nome: Este é o identificador da estrutura de dados. É o que o seu algoritmo deverá usar para aceder à estrutura de dados.

- Opções de Visualização Por baixo, todos os tipos de elementos de dados e arestas são apresentados. Ao carregar no nome, poderá abrir as opções de configuração dos tipos correspondentes. Para além disso, poderá controlar a visibilidade dos elementos e arestas, os seus nomes e valores para o tipo indicado, carregando para tal nos botões correspondentes.

#### Configurar as Opções do 'Plugin' da Estrutura de Dados

Cada 'plugin' de estrutura de dados poderá adicionar opções à janela de configuração da estrutura de dados. As opções normais dos 'plugins' são as seguintes:

##### 'Plugin' do Grafo

Use o Tipo de Grafo para seleccionar o tipo do grafo. O significado destes tipos é o seguinte:

- Grafo Direccionado: Um grafo com arestas direccionadas, nos quais são proibidas arestas com a mesma orientação e os mesmos nós.

- Grafo Não-Direccionado: Um grafo com arestas não direccionadas, nos quais são proibidas várias arestas entre os mesmos nós.

- Multi-Grafo Direccionado: Um grafo com arestas direccionadas, no qual são permitidas várias arestas orientadas entre os mesmos nós.

- Multi-Grafo Não-Direccionado: Um grafo com arestas não-direccionadas, no qual são permitidas várias arestas entre os mesmos nós.

##### 'Plugin' da Árvore

Ao assinalar a propriedade Mostrar todas as arestas, são mostradas todas as arestas entre os nós da árvore. Se não estiver assinalado, as várias arestas entre os mesmos nós são recolhidas numa só.

## Criar e Executar os Algoritmos no &rocs;

O &rocs; internamente usa o motor de programação QtScript, que é um motor específico de JavaScript. Isto significa que todos os algoritmos que implementar deverão usar JavaScript. A forma como funciona o JavaScript e como escrever código em JavaScript não está coberto por este manual, ainda que expliquemos como aceder às estruturas de dados, aos elementos de dados e às arestas da sua estrutura de dados a partir do motor de programação. Dado que nunca o objecto da estrutura de dados de base, mas sim um que é fornecido pelo 'plugin' da estrutura de dados actualmente em uso, a funcionalidade da estrutura de dados é extendida pelo 'plugin' correspondente, pelo que deverá dar uma vista de olhos na funcionalidade especializada. Especialmente, os 'plugins' de estruturas de dados usam os termos comuns do seu domínio (nós e arestas nos grafos, folhas e raizes nas árvores, etc.)

É importante saber que as alterações feitas pelo motor de programação são reflectidas directamente nas propriedades no quadro do editor visual do grafo. Assim, os programas modificam de facto as estruturas de dados.

### Os Elementos de Base da Estrutura de Dados

Cada 'plugin' oferece um conjunto especial de funções e propriedades para as suas estruturas de dados e elementos. Do mesmo modo, cada 'plugin' oferece as propriedades e funções definidas para a estrutura de dados de base. Assim, tudo o que for explicados nestas secções está disponível para todos os 'plugins' de estruturas de dados.

#### Propriedades da Estrutura de Dados de Base

As estruturas de dados são identificadas pelo seu nome. Assumindo que criou uma estrutura de dados chamada `grafoteste`, então poderá aceder à estrutura de dados se simplesmente escrever este identificador. Por exemplo, para obter uma lista com todos os elementos de dados na estrutura de dados indicada, poderá escrever `grafoteste.list_nodes();` no programa.

##### Propriedades e Funções da Estrutura de Dados de Base

Cada estrutura de dados `grafoteste` tem as seguintes propriedades que podem ser lidas ou escritas com `grafoteste.propriedade`:

    string name  // identificação da estrutura de dados

#### Propriedades e Funções de Base do Elemento de Dados

Cada elemento de dados tem as seguintes propriedades que podem ser lidas ou escritas:

    double x      // coordenada em X da posição actual
        double y      // coordenada em Y da posição actual
        double width  // tamanho
        string value  // valor
        int id        // identificador único do elemento de dados
        string name   // nome
        string color  // cor em HEXA

Para além disso, todas as propriedades dinâmicas de um elemento de dados poderão ser acedidas pelo seu nome.

Cada elemento de dados oferece os seguintes métodos:

        int type();                         // tipo de dados do elemento
        int set_type(int);                  // alterar o tipo de dados do elemento
        void add_property(string nome,      // adiciona uma propriedade dinâmica ao elemento
                          string valor);    // de dados com o nome e valor indicados
        array adj_data();                   // lista de dados adjacentes
        array adj_pointers();               // lista das arestas adjacentes
        array input_pointers();             // lista das arestas de entrada
        array output_pointers();            // lista das arestas de saída
        array loop_pointers();              // lista das arestas que foram ciclos para o próprio
        array connected_pointers(destino);  // lista das arestas que apontam para o 'destino'
        void  remove();                     // remove este elemento de dados

#### Propriedades e Funções de Base das Arestas

Cada aresta tem as seguintes propriedades que podem ser lidas ou escritas:

        string color  // cor em HEXA
        string value  // valor
        string name   // nome
        double width  // largura
        string style  // um dos seguintes valores: dot, dash, dash dot, solid

Para além disso, todas as propriedades dinâmicas de uma aresta podem ser acedidas pelo seu nome.

Cada objecto de aresta oferece os seguintes métodos:

    int type();                         // tipo da aresta
        int set_type(int);                  // muda o tipo da aresta para o indicado
        void add_property(string nome,      // adiciona uma propriedade dinâmica
                          string valor);    // com o nome e valor indicados
        node start();                       // nó de origem da aresta
        node end();                         // nó de destino da aresta
        void remove();                      // remove esta aresta

### O 'Plugin' do Grafo

#### Propriedades e Funções do Grafo

##### A Estrutura do Grafo

Dado um objecto de estrutura de dados do tipo grafo, poderá invocar as seguintes funções-membro:

    array list_nodes();                   // lista de todos os nós do grafo
        array list_edges();                   // lista de todas as arestas do grafo
        array list_edges(int tipo);           // lista de todas as arestas do tipo indicado
        node add_node(nome);                  // adiciona um novo nó e devolve-o
        edge add_edge(node origem,
                      node destino);          // adiciona uma nova aresta de 'origem' para 'destino' e devolve-a
        array overlay_edges(int idCamada);    // lista de todas as arestas na camada indicada
        edge add_overlay_edge(node origem,
                              node destino,
                              int idCamada);  // adiciona uma aresta do tipo indicado/na camada indicada

##### Nós do Grafo

Dado um objecto do tipo "Grafo", poderá invocar as seguintes funções sobre os nós do grafo, para além das propriedades fornecidas pelos elementos de Dados:

    array adj_nodes();                    // lista de todos os nós adjacentes
        array adj_edges();                    // lista das arestas ligadas
        array input_edges();                  // lista das arestas de entrada
        array output_edges();                 // lista de todas as arestas de saída
        array loop_edges();                   // lista de todas as arestas com ciclos para o nó
        array connected_edges(node destino);   // todas as arestas que ligam este nó ao nó 'destino'

##### Arestas do Grafo

Dadas as arestas de uma estrutura de dados do tipo "Grafo", só estão disponíveis as propriedades da estrutura de dados de base.

#### Algoritmos da Estrutura do Grafo

O 'plugin' do grafo oferece algumas funções especiais que podem ser usadas a partir do motor de programação.

Cálculo do Caminho Mais Curto

  Calcula o caminho mais curto entre os nós inicio e fim. Ambos os nós deverão pertencer ao mesmo grafo. Este cálculo respeita o facto de o grafo ser direccionado ou não.

          array dijkstra_shortest_path node inicio node fim

Distâncias Mais Curtas

  Calcula o caminho mais curto entre os nós inicio e todos os nós do grafo. Ambos os nós deverão pertencer ao mesmo grafo. Este cálculo respeita o facto de o grafo ser direccionado ou não.

          array dijkstra_shortest_path node inicio node fim

### O 'Plugin' da Lista Ligada

#### Propriedades e Funções da Lista Ligada

##### A Estrutura da Lista Ligada

Dada uma estrutura de dados do tipo "Lista Ligada", poderá invocar as seguintes funções-membro:

    node begin();                           // devolve o nó inicial da lista ligada
        setBegin(node inicio):                   // muda o nó 'inicio' para nó inicial da lista, reorganizando-a
        createNode();                           // cria um novo nó na lista

##### Nós da Lista Ligada

Dado um objecto do tipo "Lista Ligada", poderá invocar as seguintes funções sobre os nós do grafo, para além das propriedades indicadas pelos elementos de Dados:

    node front();                           // devolve o antecessor do nó

##### Arestas da Lista Ligada

Dadas as arestas de uma estrutura de dados do tipo "Lista Ligada", só estão disponíveis as propriedades da estrutura de dados de base.

### O 'Plugin' da Árvore

#### Propriedades e Funções da Árvore

##### A Estrutura em Árvore

Dada uma estrutura de dados do tipo "Árvore", as seguintes propriedades podem ser lidas ou escritas:

    ShowAllPointers     // mude para 'true' (verdadeiro) para mostrar todas as arestas ou para 'false' se as várias arestas devem ser comprimidas

Dado um objecto do tipo "Árvore", poderá invocar as seguintes funções-membro:

    node add_data(string nome);         // adiciona um nó à árvore com o nome indicado
        void set_root_node(node raiz);      // define 'raiz' como nó de topo da árvore
        node root_node();                   // devolve o nó de topo da árvore

##### Nós da Árvore

Dado um objecto do tipo "Árvore", as seguintes propriedades podem ser lidas ou escritas:

    int numberOfChilds                  // define o número (permitido) de filhos deste nó
        node left_child                     // apenas p/ leitura: o nó-filho à esquerda
        node right_child                    // apenas p/ leitura: o nó-filho à direita
        node node_parent                    // apenas p/ leitura: o nó-pai

Dado um objecto do tipo "Árvore", poderá invocar as seguintes funções-membro:

    node add_left_child(node filho);    // adiciona um filho à esquerda
        node add_right_child(node filho);   // adiciona um filho à direita
        node add_child(node filho, int i);  // adiciona um filho como 'i-ésimo' filho do nó
        node add_node_parent(node filho);   // adiciona um pai (só funciona se ainda não atribuído)
        node left_child();                  // devolve o filho à direita
        node right_child();                 // devolve o filho à esquerda
        node child_at(int i);               // devolve o 'i-ésimo' filho do nó
        node node_parent();                 // devolve o pai do nó

##### Arestas da Árvore

Dadas as arestas de uma estrutura do tipo "Árvore", só estão disponíveis as propriedades da estrutura de base.

### Controlar a Execução dos Programas

#### Ficheiros de Inclusão

Os seus documentos dos programas poderão incluir outros programas. Isto pode ser útil para reduzir o tamanho dos documentos e para melhorar a legibilidade. Ao usar a opção Documento do Programa Inclusões Possíveis, irá obter uma lista dos ficheiros de programas que poderá já incluir com o &rocs;. Poderá incluir um ficheiro de programa com o seguinte comando:

    include_script(string local);            // localização relativa ou absoluta do ficheiro do programa

#### Resultado do Programa

Durante a execução de um algoritmo, o resultado de depuração e do programa aparece no Resultado de Depuração ∧ Programa. Se o motor de programação detectar um erro de sintaxe no seu programa, o erro também aparece como uma mensagem de depuração. Repare que todas as mensagens do programa também são apresentadas no resultado de depuração (aparecendo a negrito).

Pode controlar o texto que é apresentado no resultado do programa, usando as seguintes funções:

    output(string mensagem);            // mostra a mensagem como resultado do programa
        debug(string mensagem);             // mostra a mensagem como resultado de depuração

#### Controlar a Execução do Programa

Existem diferentes modos de execução para os seus programas.

Pode controlar o texto que é apresentado no resultado do programa, usando as seguintes funções:

- Iniciar: Executa o programa até este terminar.

- Parar: Interrompe a execução do programa (só disponível se tiver um programa em execução).

- Um Passo: Executa o programa até que um passo termine. Um passo termina quando o programa invocar a função `interrupt()`:

      interrupt();    // interrompe um passo

- Depurar: Executa o programa no modo de depuração. Isto abre a janela de depuração do QtScript.

## Importar e Exportar

### Trocar Projectos do &rocs;

Poderá importar e exportar os projectos do &rocs; como pacotes `.tar.gz`. Estes pacotes podem ser usados para trocar projectos entre pessoas. A importação e exportação poderão ser feitas com as opções do menu Ficheiro Importar um Projecto e Ficheiro Exportar o Projecto, respectivamente.

### Importação e Exportação dos Documentos do Grafo

O &rocs; suporta de momento a importação e exportação para os seguintes formatos de ficheiros:

- Ficheiros do DOT, também conhecidos pelo Graphviz

- Ficheiros GML

- Ficheiros no formato Trivial Graph Format

#### Trivial Graph Format

O formato Trivial Graph Format (TGF) é um formato de ficheiros em texto simples para descrever grafos. Um ficheiro TGF consiste numa lista de definições de nós que associam os ID's dos nós às legendas, seguida por uma lista das arestas. Neste formato, só é possível ter uma legenda por nó e um valor por aresta. O &rocs; interpreta os grafos importados como grafos unidireccionais. Os grafos exportados irão conter duas arestas por ligação, se as ligações forem bidireccionais.

##### Especificação do Formato

- O ficheiro começa com uma lista de nós (um nó por linha), seguido de uma linha apenas com o carácter "#", seguida de uma lista de arestas (uma aresta por linha).

- Um nó consiste num número inteiro (identificador), seguido de um espaço e de um texto arbitrário.

- Uma aresta consiste em dois números inteiros (identificadores) separados por espaços, seguido de um espaço e um texto arbitrário. Assume-se que os pontos das arestas são direccionados do primeiro identificador para o segundo.

##### Exemplo

    1 nó inicial
    2 transmissor
    3 receptor
    #
    1 2 azul
    2 1 vermelho
    2 3 verde

## Créditos e Licença

&rocs;

Copyright do Programa:

- 'Copyright' 2008 de Ugo Sangiori (ugorox AT gmail.com)

- 'Copyright' 2008-2012 de Tomaz Canabrava (tcanabrava AT kde.org)

- 'Copyright' 2008-2012 de Wagner Reck (wagner.reck AT gmail.com)

- 'Copyright' 2011-2012 de Andreas Cord-Landwehr (cordlandwehr AT googlemail.com)

'Copyright' da Documentação:

- Documentação com 'copyright' 2009 de &Anne-Marie.Mahfouf; &Anne-Marie.Mahfouf.mail;

- Documentação com 'copyright' 2009 de Tomaz Canabrava (tcanabrava at kde dot org)

- Documentação com 'copyright' 2011-2012 de Andreas Cord-Landwehr (cordlandwehr AT googlemail.com)

Tradução de José Nuno Pires zepires@gmail.com

&underFDL; &underGPL;

## Instalação

### Como obter o &rocs;

&install.intro.documentation;

### Compilação e instalação

&install.compile.documentation;

&documentation.index;