# Manual do &rocs;

Tomaz
Canabrava
tomaz.canabrava@gmail.com
Andreas
Cord-Landwehr
cordlandwehr@googlemail.com
Marcus
Gama

    marcus.gama@gmail.com

Tradução
2009
Tomaz Canabrava
2011-2012
Andreas Cord-Landwehr
02/12/2012
1.8.0 &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 apresentar uma visão geral do &rocs;. Para o leitor que quiser começar a usar diretamente o &rocs;, sugerimos que leia o e, enquanto escreve programas, use o como referência.

### Objetivos, 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 demonstrar algoritmos aos seus alunos,

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

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

Para todos estes usuários, o &rocs; oferece um editor de estrutura de dados simples de usar para criar as estruturas de dados, um poderoso mecanismo de programação para executar os algoritmos, assim como diversos utilitários para suas simulações e experiências.

O fluxo de trabalho típico no &rocs; é começar criando um grafo com o editor visual do grafo. Você poderá fazer isto à mão, isto é, adicionando elementos de dados e conectando-os, ou então poderá usar um dos algoritmos auxiliares (se estiverem disponíveis para a infraestrutura de dados selecionada). Geradores de estruturas de dados podem ser em Documento Grafo Ferramentas Gerar o Grafo. Posteriormente, você poderá atribuir valores aos elementos da estrutura de dados seja manualmente seja usando Documento Grafo Ferramentas Atribuir valores. Finalmente, você poderá criar o seu algoritmo em JavaScript e executá-lo com a estrutura de dados recém criada. Todas as alterações que seu algoritmo realiza na estrutura de dados são visíveis imediatamente no quadro do editor visual do grafo.

Uma captura de tela do &rocs;.
Uma captura de tela do &rocs;.

### O &rocs; em resumo

Nesta seção, iremos dar uma visão geral resumida sobre os elementos básicos do &rocs;. Iremos explicar noções importantes das estruturas de dados, das infraestruturas e dos tipos de elementos. O conhecimento destes conceitos é útil para compreender como as estruturas de dados podem ser criadas e modificadas no &rocs;.

De um modo geral, o &rocs; funciona com projetos: ao abrir o &rocs;, é criado um projeto vazio e você poderá substituí-lo se carregar ou importar outro projeto. Assim, um projeto em si consiste dos documentos de grafos e dos programas.

#### Documentos de grafos e Infraestruturas 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 uma infraestrutura de estrutura de dados em especial. As infraestruturas de estrutura de dados estão presentes para diversos tipos de grafos (grafos gerais, listas ligadas, árvores com raiz) e fornece 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 estendido de funções do programa a usar nos seus algoritmos. (Para mais detalhes, veja a seção correspondente no manual). É possível alterar a infraestrutura 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 a infraestrutura de árvores com raiz).

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

#### Estruturas de dados

As estruturas de dados são a base de todo o trabalho no &rocs;. Você poderá adicionar uma ou várias a um documento de grafo, adicionar elementos de dados (nós, dados) e ponteiros para elas, e ainda modificá-las com programas. Para isso, cada estrutura de dados tem o seu nome único, com o qual poderá ser acessada pelos seus programas. Devido à sua escolha da infraestrutura de estruturas de dados atual, poderá acontecer que você não consiga modificar as estruturas de dados de forma arbitrária (p.ex., uma árvore nunca deverá conter um ciclo). A infraestrutura de estrutura de dados é determinada pela infraestrutura de estrutura de dados associado com o documento do grafo correspondente que contém a estrutura de dados.

#### Tipos de ponteiros

Você poderá definir diferentes tipos de ponteiros a usar nas suas estruturas de dados. Isto é, um tipo de ponteiro poderá obter uma disposição individual (basicamente uma cor) e é bastante simples acessar aos ponteiros de um determinado tipo a partir dos seus programas. Os casos de uso típicos dos ponteiros 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 ponteiros 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 represente um tipo específico (p.ex., pesquisa em largura primeiro). Para esses casos de uso, você 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 acessados a partir dos seus programas.

#### Propriedades dinâmicas

Os vários elementos de dados e ponteiros poderão ter várias propriedades. Algumas dessas propriedades são predefinidas para a infraestrutura da estrutura de dados. Veja a documentação sobre a infraestrutura da estrutura de dados para mais detalhes. Para adicionar mais propriedades aos elementos de dados e ponteiros, você pode 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 você tentar usar algum caractere inválido no nome da propriedade, a propriedade não será alterada.

Para adicionar propriedades dinâmicas, use as janelas Propriedades dos dados e Propriedades do ponteiro, nos menus de contexto dos respectivos elementos ou as funções dos scripts explicadas em .

Você também poderá usar os scripts. Apenas precisa usar o `add_property` com o nome e o valor da sua propriedade. Em seguida, você poderá usar a expressão nó/ponteiro.nomePropriedade para definir/obter os valores.

Aqui está um exemplo de utilização das propriedades dinâmicas com a infraestrutura da estrutura de dados do grafo.

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

### Tutorial

Nesta seção, iremos criar um projeto de exemplo para explorar algumas das funções mais importantes do &rocs;. O objetivo é 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 conectada 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 fator 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 objetivo é 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 a infraestrutura da estrutura de dados 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

Nós 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 ponteiros do documento de grafo atual. Para os tipos de dados, iremos adicionar um novo tipo chamado "C", que irá obter automaticamente o ID `1`. Para esse tipo, iremos selecionar a imagem do servidor como ícone. Além disso, iremos mudar para a página do tipo de ponteiro e adicionar um novo tipo de ponteiro 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 isso, 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 isso, iniciamos a execução com o Botão de Execução no painel de controle do programa.

## A interface do usuário do &rocs;

### Elementos gerais da interface do usuário

A interface do usuário 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;.

Seleção do documento

  Neste menu de topo, você deverá selecionar o documento e estrutura de dados atual. A criação e remoção de estruturas de dados, assim como o acesso às propriedades das estruturas de dados, também é possível aqui.

Editor de Grafos Visual

  Este é o quadro branco no qual estruturas de dados podem ser criadas e modificadas. Um clique-direito no quadro branco, elementos de dados ou ponteiros abre menus de contexto. Você pode usar as ferramentas da barra de ferramentas do editor de grafo visual para modificar elementos no quadro brando do editor de grafo visual.

Barra de ferramentas do Editor de Grafos Visual

  Esta barra fornece todas as ferramentas do editor de grafo visual. Use o Adicionar dados ou Adicionar conexão para criar novos elementos ou conectar elementos, respectivamente. Novos elementos de dados são adicionados à estrutura de dados que está selecionada no momento no Seletor de documento. Observe que tanto o Adicionar dados como o Adicionar conexão possuem menus de contexto para selecionar o tipo que os elementos criados deverão ter. Para mais detalhes veja .

Barra lateral

  À direita, você poderá encontrar a barra lateral que oferece diversas ferramentas para o seu fluxo de trabalho:

  - Tipos de elementos: Este elemento fornece acesso direto para os tipos de arestas e dados disponíveis.

  - Diário: Cada projeto tem o seu próprio diário que pode ser usado &eg; para: notas das tarefas, resultados ou observações.

  - Documentação: Para obter acesso direto ao manual e, deste modo, à documentação do programa, você poderá abrir este elemento.

Editor de script

  Neste editor de texto você pode criar os algoritmos como explicado em detalhes em . Você poderá trabalhar com vários documentos de script ao mesmo tempo usando diversas abas. O pequeno símbolo do disco aparece se existirem alterações a serem salvas no script.

Resultado do programa

  Esta área de texto poderá apresentar as informações de depuração ou o resultado do script para o seu algoritmo, dependendo da configuração no topo deste elemento. Se o script emitir um erro, o resultado de depuração é automaticamente apresentado.

Controles

  Aqui você pode encontrar controles para a execução do script. Você pode executar o script atualmente aberto no editor do script clicando em Executar. Enquanto o script estiver em execução, é possível interrompê-lo se clicar no botão Parar. Observe que a execução em Um passo somente interrompe em palavras-chave específicas (veja ).

### Barras de ferramentas

Existem diferentes barras de ferramentas para o editor do grafo que permitem-lhe acessar as funcionalidades apenas com um clique do mouse. Por padrão são mostradas as seguintes barras de ferramentas:

- Barra de ferramentas principal

- Barra de ferramentas de alinhamento

#### Barra de ferramentas principal

A Barra de ferramentas principal consiste nas seguintes ações. Clicar em uma ação significa que o ponteiro do seu mouse aplica esta ação ao quadro do editor do grafo:

- Mover: Para selecionar os elementos, você poderá clicar no espaço em branco do quadro, manter o mouse pressionado e desenhar um retângulo que contenha alguns elementos de dados e/ou ponteiros para selecionar estes elementos ou então clicar diretamente em um elemento não selecionado para escolher esse elemento. Se clicar em um elemento ou conjunto de elementos selecionados, você poderá mover estes elementos em conjunto. A movimentação dos elementos selecionados também é possível com as teclas direcionais.

- Adicionar dados: Clique em uma posição arbitrária no quadro do editor do grafo para criar um novo elemento de dados que pertença ao grafo selecionado na estrutura de dados. Mantendo o ponteiro do mouse pressionado no botão, um menu de contexto mostra a quais tipos de dados o novo elemento de dados criados pode pertencer (somente se existirem diferentes tipos de dados).

- Adicionar conexão: Clique em um elemento de dado, mantenha o mouse pressionado e desenhe uma linha para outro elemento de dado, apontando a aresta nessa direção. Esta ação só será bem-sucedida se o grafo atual permitir adicionar esta aresta (&eg;, em um grafo não-direcionado, você não poderá adicionar várias arestas entre dois elementos de dado). Mantendo o ponteiro do mouse pressionado no botão, um menu de contexto mostra a quais tipos de dados o novo elemento de dados criados pode pertencer (somente se existirem diferentes tipos de dados).

- Excluir: Clique em um elemento para excluí-lo. Se excluir um nó, todas as arestas adjacentes serão também excluídas.

- Ampliação: Clique no quadro, mantenha o &LMB; pressionado e com isto desenhe um retângulo. O quadro será ampliado para a área selecionada. É possível também usar a roda do mouse para ampliar ou reduzir. Se clicar duas vezes com o &LMB;, irá restaurar a ampliação original.

#### Barra de ferramentas de alinhamento

Você pode adicionar a Barra de ferramentas de alinhamento opcional. Se clicar em uma ação desta barra de ferramentas, fará um efeito direto sobre os nós selecionados:

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

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

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

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

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

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

- Círculo: Alinha os elementos de dado em um círculo com o diâmetro igual à distância máxima dos elementos de dado. Estes são posicionados na mesma ordem indicada pelo centro de gravidade destes elementos de dado.

- Minimizar os cantos cruzado: Reorganiza os elementos de dado selecionados para minimizar o número de conexões cruzadas (aplicação do algoritmo de Fruchterman-Reingold).

### Trabalhando com documentos de grafo

Um projeto do &rocs; contém um ou vários documentos de grafos que poderão ser editados com o editor visual de grafos. Além disso, cada documento poderá conter um número arbitrário de estruturas de dados. Aqui, as estruturas de dados de um documento usam todas a mesma infraestrutura de estruturas de dados. Esta seção irá explicar como mudar de documentos e como criar novos.

#### A barra de seleção do documento

A barra de seleção de documentos é usada para selecionar o documento de grafo atual e, além disso, a estrutura de dados atual. Usar as ferramentas de edição visuais do grafo para criar elementos de estruturas de dados irá adicionar esses elementos recém criados à estrutura de dados atual. Do mesmo modo, esta barra fornece acesso direto para apagar as estruturas de dados existentes ou criar novas dentro do documento atual.

- Nova: Esta ação cria uma nova estrutura de dados, usando um padrão de nomes indicado pela infraestrutura da estrutura de dados. Esta estrutura é adicionada ao documento do grafo selecionado no momento.

- Apagar Esta ação apaga a estrutura de dados selecionada no momento na lista de estruturas de dados do documento atual.

- Propriedades da estrutura de dados: Abre uma janela que fornece acesso às propriedades da estrutura de dados.

- Propriedades do documento: Abre uma janela que oferece o acesso às propriedades do documento, assim como aos tipos de arestas e dados do mesmo.

A barra de ferramentas principal.
A barra de seleção do documento.

#### Criar e importar documentos do grafo

Para criar um novo documento de grafo ou adicionar um existente ao projeto, use Projeto Novo documento de grafo ou Projeto Importar grafo do &rocs;. Você também pode importar documento de grafo de aplicativos de terceiros (para isto, veja ).

## 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 acessar às estruturas de dados, aos elementos de dados e aos ponteiros da sua estrutura de dados a partir do motor de programação. Uma vez que você nunca usa o objeto da estrutura de dados de base, mas sim um que é fornecido pela infraestrutura da estrutura de dados atualmente em uso, a funcionalidade da estrutura de dados é estendida pela infraestrutura correspondente, de modo que você deverá dar uma olhada na funcionalidade especializada. Especialmente, as infraestruturas de estruturas de dados usam os termos comuns do seu domínio (nós e arestas nos grafos, folhas e raízes nas árvores, etc.)

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

### Os elementos de base da estrutura de dados

Cada infraestrutura oferece um conjunto especial de funções e propriedades para as suas estruturas de dados e elementos. Do mesmo modo, cada infraestrutura oferece as propriedades e funções definidas para a estrutura de dados de base. Assim, tudo o que for explicado nestas seções está disponível para todas as infraestruturas de estruturas de dados.

#### Propriedades da estrutura de dados de base

As estruturas de dados são identificadas pelo seu nome. Considerando que você criou uma estrutura de dados chamada `grafoteste`, então poderá acessar a estrutura de dados simplesmente escrevendo 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 atual
        double y      // coordenada em Y da posição atual
        double width  // tamanho
        string value  // valor
        int id        // identificador único para o elemento de dados
        string name   // nome
        string color  // cor em HEXA

Além disso, todas as propriedades dinâmicas de um elemento de dados podem ser acessadas pelo seu nome.

Cada elemento de dados oferece os seguintes métodos:

        int type();                         // tipo de elemento de dados
        int set_type(int);                  // alterar o tipo de dados do elemento de dados
        void add_property(string name,      // adicionar as propriedades dinâmicas para o elemento de dados com o
                          nome indicado e o valor da string);
        array adj_data();                   // lista de dados adjacentes
        array adj_pointers();               // lista dos ponteiros adjacentes
        array input_pointers();             // lista dos ponteiros de entrada
        array output_pointers();            // lista dos ponteiros de saída
        array loop_pointers();              // lista dos ponteiros que foram ciclos para o próprio
        array connected_pointers(destino);  // lista dos ponteiros que apontam para o 'destino'
        void remove();                      // remove este elemento de dados

#### Propriedades e funções de base dos ponteiros

Cada ponteiro 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

Além disso, todas as propriedades dinâmicas de um ponteiro podem ser acessadas pelo seu nome.

Cada objeto de ponteiro oferece os seguintes métodos:

    int type();                         // tipo do ponteiro
        int set_type(int);                  // muda o tipo do ponteiro
        void add_property(string name,      // adicionar as propriedades dinâmicas para o elemento de dados com o
                          nome indicado e o valor da string);
        node start();                       // nó de origem do ponteiro
        node end();                         // nó de destino do ponteiro
        void remove();                      // remove este ponteiro

### A infraestrutura do grafo

#### Propriedades e funções do grafo

##### Propriedades específicas da infraestrutura do grafo

A janela de estrutura de dados permite o acesso de configuração das opções específicas da infraestrutura de Grafos. Use o Tipo de grafo para selecionar o tipo do grafo. O significado destes tipos é o seguinte:

- Grafo: Um grafo em que as mesmas arestas (relacionadas com os pontos de origem e destino) não podem existir várias vezes.

- Multigrafo: Um grafo no qual são permitidas várias arestas entre os mesmos nós (no que diz respeito aos pontos de origem e destino).

##### A Estrutura do Grafo

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

    array list_nodes();                   // lista de todos os nós do grafo
        array list_nodes(int type);           // lista de todos os nós do tipo indicado
        array list_edges();                   // lista de todas as arestas do grafo
        array list_edges(int type);           // lista de todas as arestas do tipo indicado
        node add_node(name);                  // 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 objeto do tipo "Grafo", você poderá invocar as seguintes funções sobre os nós do grafo, 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 conectadas
        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 conectam 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

A infraestrutura 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 início e fim. Ambos os nós deverão pertencer ao mesmo grafo. Este cálculo respeita o fato de o grafo ser direcionado ou não.

          array dijkstra_shortest_path node início node fim

Distância do caminho mais curto

  Calcula a distância do caminho mais curto entre o nó início e todos os outros nós do grafo. Este cálculo respeita o fato de o grafo ser direcionado ou não.

          array distances node início

### A infraestrutura da lista ligada

#### Propriedades e funções da lista ligada

##### A estrutura da lista ligada

Dada uma estrutura de dados do tipo "Lista Ligada", você 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 objeto do tipo "Lista Ligada", você poderá invocar as seguintes funções sobre os nós do grafo, 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.

### A infraestrutura da Árvore

#### Propriedades e funções da árvore

##### Infraestrutura da Árvore com raiz

A janela de propriedades da estrutura de dados permite o acesso para as configurações específicas da infraestrutura de Grafo. Aqui, selecionando a propriedade Mostrar todos os ponteiros, todos os ponteiros entre três nós são exibidos. Se não estiver selecionado, ponteiros múltiplos entre os mesmos nós são recolhidos em um.

##### 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 objeto do tipo "Árvore", você 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 objeto 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 objeto do tipo "Árvore", você 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.

### Controlando a execução dos scripts

#### Incluir arquivos

Seus documentos de script podem incluir outros scripts. Isto pode ser útil para reduzir o tamanho dos documentos de script e melhorar a legibilidade. Usando o Documento de script Inclusões possíveis você obtém uma lista de arquivos de script que já foram empacotados com o &rocs; e que podem ser incluídos. Você pode incluir um arquivo de script com o seguinte comando:

    include_script(string caminho);            // caminho relativo ou absoluto do arquivo de script

#### Resultado do programa

Durante a execução de um algoritmo, o resultado do programa e da depuração é exibido no Resultado do script & depuração. Se o motor de script detecta um erro de sintaxe em seu script, o erro é também exibido como uma mensagem de depuração. Observe que todas as mensagens do programa são também exibidas na saída de depuração (exibida em texto em negrito).

Você pode controlar o texto que é exibido no resultado do script com as seguintes funções:

    output(string mensagem);            // exibe a mensagem como resultado do script
        debug(string mensagem);             // exibe a mensagem como resultado da depuração

#### Controle da execução dos scripts

Existem diferentes modo de execução para seus scripts.

Você pode controlar o texto que é exibido no resultado do script com as seguintes funções:

- Iniciar: Executa o script até ele terminar.

- Parar: Interrompe a execução de script (somente disponível se um script estiver em execução).

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

      interrupt();    // termina um passo

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

## Importar e exportar

### Compartilhar projetos &rocs;

Os projetos do &rocs; podem ser importados e exportados como pacotes `.tar.gz`. Estes pacotes podem ser usados para compartilhar projetos. A importação e exportação pode ser feita com o Arquivo Importar projeto e Arquivo Exportar projeto, respectivamente.

### Importar e exportar documentos de grafo

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

- Arquivos DOT, também conhecidos como arquivos Graphviz

- Arquivos GML

- Arquivos no formato Trivial Graph

#### Formato de Arquivo Trivial Graph

O Formato Trivial Graph (TGF, sigla em inglês) é um formato de arquivo simples baseado em texto para descrever gráficos. O arquivo TGF consiste de uma lista de definições de nó, o mapa de IDs dos nós para rótulos, seguido de uma lista de arestas. Neste formato, somente é possível ter um rótulo por nó e um valor por aresta. O &rocs; interpreta os gráficos importados como gráficos não direcionados. Os gráficos exportados conterão duas arestas por conexão se as conexões forem bidirecionais.

##### Especificação do formato

- O arquivo inicia com uma lista de nós (um nó por linha), seguida de uma linha com somente o caractere "#", seguida pela lista de arestas (uma aresta por linha).

- Um nó consiste de um inteiro (identificador), seguido por um espaço, seguido por um string arbitrário.

- Uma aresta consiste de dois inteiros (identificadores) separados por um espaço, seguida por um espaço, seguida por um string arbitrário. É considerado que a aresta aponta do primeiro para o segundo identificador

##### Exemplo

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

#### Linguagem DOT / Formato do Arquivo de Grafos do Graphviz

A linguagem DOT é uma linguagem descritiva em texto simples que permite tanto uma representação legível para os usuários dos grafos, assim como um processamento eficiente pelos programas de formatação de grafos. O DOT é o formato de arquivo padrão do pacote de visualização de grafos Graphviz, mas também é largamente usado por outras ferramentas de grafos. As extensões dos nomes dos arquivos normais para o DOT são .gv e .dot.

##### Funcionalidades não suportadas

O &rocs; consegue processar todos os arquivos de grafos que tenham um grafo definido de acordo com a especificação da linguagem DOT http://www.graphviz.org/content/dot-language. O suporte das funcionalidades da linguagem é completo, apesar das seguintes exceções:

- sub-grafo: Devido à falta da funcionalidade do conceito de sub-grafos no &rocs;, os sub-grafos só são importados como um conjunto de elementos de dados e ligações. Especialmente, as ligações de e para sub-grafos não são importadas.

- Atributos em &HTML; e &XML;: Os atributos (como as legendas) que contenham uma sintaxe em &HTML; ou &XML; são lidos sem qualquer alteração. Especialmente, não são lidos os ajustes de estilos e tipos de letra destes atributos.

##### Exemplo

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

## Créditos e licença

&rocs;

Direitos autorais do programa:

- Direitos autorais 2008 Ugo Sangiori (ugorox AT gmail.com)

- Direitos autorais 2008-2012 Tomaz Canabrava (tcanabrava AT kde.org)

- Direitos autorais 2008-2012 Wagner Reck (wagner.reck AT gmail.com)

- Direitos autorais 2011-2012 Andreas Cord-Landwehr (cordlandwehr AT googlemail.com)

Direitos autorais da documentação:

- Direitos autorais da documentação 2009 &Anne-Marie.Mahfouf; &Anne-Marie.Mahfouf.mail;

- Direitos autorais da documentação 2009 Tomaz Canabrava (tcanabrava AT kde.org)

- Direitos autorais da documentação 2011-2012 Andreas Cord-Landwehr (cordlandwehr AT googlemail.com)

Tradução de Marcus Gama marcus.gama@gmail.com

&underFDL; &underGPL;

## Instalação

### Como obter o &rocs;

&install.intro.documentation;

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

&install.compile.documentation;

&documentation.index;