<?xml version="1.0" ?>
<!DOCTYPE book PUBLIC "-//KDE//DTD DocBook XML V4.2-Based Variant V1.1//EN" "dtd/kdex.dtd" [
<!ENTITY kappname "&rocs;">
<!ENTITY package "kdeedu">
<!ENTITY % addindex "IGNORE">
<!ENTITY % Portuguese "INCLUDE">
]>
<book id="rocs" lang="&language;">
<bookinfo>
<title
>O Manual do &rocs;</title>
<authorgroup>
<author
><personname
> <firstname
>Tomaz</firstname
> <surname
>Canabrava</surname
> </personname
> <email
>tomaz.canabrava@gmail.com</email
> </author>
<author
><personname
> <firstname
>Andreas</firstname
> <surname
>Cord-Landwehr</surname
> </personname
> <email
>cordlandwehr@googlemail.com</email
> </author>
<othercredit role="translator"
><firstname
>José</firstname
><surname
>Pires</surname
><affiliation
><address
><email
>zepires@gmail.com</email
></address
></affiliation
><contrib
>Tradução</contrib
></othercredit
>
</authorgroup>
<copyright
><year
>2009</year
><holder
>Tomaz Canabrava</holder
></copyright>
<copyright
><year
>2011-2012</year
><holder
>Andreas Cord-Landwehr</holder
></copyright>
<date
>2012-08-23</date>
<releaseinfo
>1.7.70 &kde; 4.10</releaseinfo>
<legalnotice
>&FDLNotice;</legalnotice>
<abstract>
<para
>O &rocs; é uma ferramenta da teoria dos grafos para o KDE. </para>
</abstract>
<keywordset>
<keyword
>KDE</keyword>
<keyword
>kdeedu</keyword>
<keyword
>matemática</keyword>
<keyword
>matemática</keyword>
<keyword
>grafos</keyword>
<keyword
>nó</keyword>
<keyword
>aresta</keyword>
</keywordset>
</bookinfo>
<chapter id="introduction">
<title
>Introdução</title>
<para
>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 <xref linkend="introduction-nutshell"/> e, enquanto escreve programas, use o <xref linkend="scripting"/> como referência. </para>
<sect1 id="introduction-goals">
<title
>Objectivos, Público-Alvo e Funcionamento</title>
<para
>O &rocs; é um IDE da Teoria dos Grafos para todos os interessados no desenho e análise de algoritmos de grafos. Isto inclui explicitamente</para>
<itemizedlist>
<listitem
><para
>os professores que poderão querer demonstrar algoritmos aos seus alunos,</para
></listitem>
<listitem
><para
>os alunos que queiram compreender e ver como é que funcionam os seus algoritmos,</para
></listitem>
<listitem
><para
>e todos os que estejam interessados em algoritmos e estruturas de dados.</para
></listitem>
</itemizedlist>
<para
>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. </para>
<para
>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 <guimenu
>Ferramentas</guimenu
> <guimenuitem
>Gerar o Grafo</guimenuitem
>. Eventualmente, poderá também querer usar as ferramentas auxiliares em <guimenu
>Ferramentas</guimenu
> <guimenuitem
>Atribuir Valores</guimenuitem
> 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. </para>
<screenshot>
<screeninfo
>Uma imagem do &rocs;.</screeninfo>
<mediaobject>
<imageobject>
<imagedata fileref="rocs-screenshot.png" format="PNG"/>
</imageobject>
<textobject>
<phrase
>Uma imagem do &rocs;.</phrase>
</textobject>
</mediaobject>
</screenshot>
</sect1>
<sect1 id="introduction-nutshell">
<title
>O &rocs; em Resumo</title>
<para
>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;. </para>
<para
>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 <emphasis
>documentos de grafos</emphasis
> e nos <emphasis
>programas</emphasis
>. </para>
<sect2>
<title
>Documentos de Grafos e 'Plugins' de Estruturas de Dados</title>
<para
>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). </para>
<para
>Os documentos de grafos formam também a base para definir os tipos de arestas e tipos de dados. </para>
</sect2>
<sect2>
<title
>Estruturas de Dados</title>
<para
>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. </para>
</sect2>
<sect2>
<title
>Tipos de Arestas</title>
<para
>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. </para>
</sect2>
<sect2>
<title
>Tipos de Dados</title>
<para
>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. </para>
</sect2>
<sect2>
<title
>Propriedades Dinâmicas</title>
<para
>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 <emphasis
>propriedades dinâmicas</emphasis
> 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>
<para
>Para adicionar propriedades dinâmicas, use as janelas <guilabel
>Propriedades dos Dados</guilabel
> e <guilabel
>Propriedades da Aresta</guilabel
>, nos menus de contexto dos respectivos elementos ou as funções dos programas explicadas em <xref linkend="scripting-data-structure"/>. </para>
<para
>Também poderá usar os programas. Apenas precisa de usar o <literal
>add_property</literal
> com o nome e o valor da sua propriedade. Depois disso, poderá usar a expressão nó/aresta.nomePropriedade para alterar/ler os valores. </para>
<para
>Aqui está um exemplo de utilização das propriedades dinâmicas com o 'plugin' do grafo. <programlisting
>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
</programlisting>
</para>
</sect2>
</sect1>
<sect1 id="introduction-tutorial">
<title
>Tutorial</title>
<para
>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 <emphasis
>cobertura mínima de vértices</emphasis
>. 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). </para>
<para
>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. </para>
<sect2>
<title
>Gerar um Grafo</title>
<para
>Para o 'plugin' do grafo, o &rocs; oferece um utilitário que poderá gerar grafos. Poderemos ir ao menu <menuchoice
><guimenu
>Documento do Grafo</guimenu
><guisubmenu
>Ferramentas</guisubmenu
><guimenuitem
>Gerar o Grafo</guimenuitem
></menuchoice
>. 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 <literal
>grafoteste</literal
>. </para>
</sect2>
<sect2>
<title
>Criar Tipos</title>
<para
>Iremos usar o botão de <guibutton
>Propriedades do Documento</guibutton
> 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 <literal
>1</literal
>. 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 <literal
>1</literal
> e iremos mudar a cor para azul. </para>
</sect2>
<sect2>
<title
>O Algoritmo</title>
<para
>Por último, temos de implementar o algoritmo de aproximação. Para tal, iremos usar a seguinte implementação: </para>
<programlisting
>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.");
</programlisting>
</sect2>
<sect2>
<title
>Executar o Algoritmo</title>
<para
>Finalmente, queremos executar o algoritmo. Para tal, iniciamos a execução com o <guibutton
>Botão de Execução</guibutton
> no painel de controlo do programa. </para>
</sect2>
</sect1>
</chapter>
<chapter id="user-interface">
<title
>A Interface de Utilizador do &rocs;</title>
<sect1 id="user-interface-all">
<title
>Elementos Gerais da Interface do Utilizador</title>
<para
>A interface do utilizador está dividida em várias partes lógicas, como aparece na imagem abaixo. </para>
<screenshot>
<screeninfo
>Elementos gráficos da interface do &rocs;.</screeninfo>
<mediaobject>
<imageobject>
<imagedata fileref="rocs-interfaces.png" format="PNG"/>
</imageobject>
<textobject>
<phrase
>Elementos gráficos da interface do &rocs;.</phrase>
</textobject>
</mediaobject>
</screenshot>
<variablelist>
<varlistentry>
<term
>Editor de Grafos Visual</term>
<listitem
><para
>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 <emphasis
>Barra de Edição Visual do Grafo</emphasis
> para modificar os elementos no quadro visual do grafo.</para
></listitem>
</varlistentry>
<varlistentry>
<term
>Barra do Editor de Grafos Visual</term>
<listitem
><para
>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 <guibutton
>Adicionar os Dados</guibutton
> ou <guibutton
>Adicionar uma Ligação</guibutton
>, poderá criar novos elementos de dados ou então arestas, respectivamente, à estrutura de dados seleccionada de momento no item de <emphasis
>Propriedades do Grafo</emphasis
>. Lembre-se que as opções <guibutton
>Adicionar Dados</guibutton
> e <guibutton
>Adicionar uma Ligação</guibutton
> 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 <xref linkend="user-interface-toolbars"/>. </para
></listitem>
</varlistentry>
<varlistentry>
<term
>Propriedades do Grafo</term>
<listitem
><para
>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 <xref linkend="user-interface-graph-properties"/>. </para
></listitem>
</varlistentry>
<varlistentry>
<term
>Editor de Programas</term>
<listitem
><para
>Neste editor de texto, poderá criar os algoritmos da forma descrita em <xref linkend="scripting"/>. 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. </para
></listitem>
</varlistentry>
<varlistentry>
<term
>Resultado de Depuração & Programas</term>
<listitem
><para
>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. </para
></listitem>
</varlistentry>
<varlistentry>
<term
>Controlos</term>
<listitem
><para
>Este menu controla a execução dos algoritmos. Poderá executar o programa que está aberto de momento no editor do programa se carregar em <guiicon
>Executar</guiicon
>. Enquanto o programa estiver em execução, é possível interrompê-lo se carregar no botão <guiicon
>Parar</guiicon
>. Lembre-se que a execução <guibutton
>Um Passo</guibutton
> só termina com palavras-chave específicas (veja em <xref linkend="scripting"/>). </para
></listitem>
</varlistentry>
</variablelist>
</sect1>
<sect1 id="user-interface-toolbars">
<title
>Barras de Ferramentas</title>
<para
>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:</para>
<itemizedlist>
<listitem
><para
>Barra Principal</para
></listitem>
<listitem
><para
>Barra de Alinhamento</para
></listitem>
</itemizedlist>
<!-- -->
<sect2 id="user-interface-toolbars-main">
<title
>Barra Principal</title>
<para
>A <emphasis
>Barra Principal</emphasis
> 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:</para>
<itemizedlist>
<listitem
><para
><guilabel
>Mover</guilabel
>: 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.</para
></listitem>
<listitem
><para
><guilabel
>Adicionar Dados</guilabel
>: 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).</para
></listitem>
<listitem
><para
><guilabel
>Adicionar uma Aresta</guilabel
>: 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 (⪚, 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).</para
></listitem>
<listitem
><para
><guilabel
>Apagar</guilabel
>: Carregue num elemento para o apagar. Se apagar um nó, todas as arestas adjacentes serão também apagadas.</para
></listitem>
<listitem
><para
><guilabel
>Ampliar</guilabel
>: 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.</para
></listitem>
</itemizedlist>
<screenshot>
<screeninfo
>A Barra Principal</screeninfo>
<mediaobject>
<imageobject>
<imagedata fileref="rocs-toolbar-main.png" format="PNG"/>
</imageobject>
<textobject>
<phrase
>A Barra Principal</phrase>
</textobject>
</mediaobject>
</screenshot>
</sect2>
<sect2 id="user-interface-toolbars-alignment">
<title
>Barra de Alinhamento</title>
<para
>Poderá adicionar a <emphasis
>Barra de Alinhamento</emphasis
> opcional. Se carregar numa acção desta barra de ferramentas, fará um efeito directo sobre os nós seleccionados de momento:</para>
<itemizedlist>
<listitem
><para>
<inlinemediaobject
><imageobject>
<imagedata fileref="hi22-action-rocsaligntop.png" format="PNG"/></imageobject>
</inlinemediaobject
> <guilabel
>Topo</guilabel
>: Alinha os elementos de dados na vertical para a posição do elemento superior. Isto só afecta as posições verticais.</para
></listitem>
<listitem
><para>
<inlinemediaobject
><imageobject>
<imagedata fileref="hi22-action-rocsalignvmiddle.png" format="PNG"/></imageobject>
</inlinemediaobject
> <guilabel
>Centro</guilabel
>: 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.</para
></listitem>
<listitem
><para>
<inlinemediaobject
><imageobject>
<imagedata fileref="hi22-action-rocsalignbottom.png" format="PNG"/></imageobject>
</inlinemediaobject
> <guilabel
>Base</guilabel
>: Alinha os elementos de dados na vertical para a posição do elemento inferior. Isto só afecta as posições verticais.</para
></listitem>
<listitem
><para>
<inlinemediaobject
><imageobject>
<imagedata fileref="hi22-action-rocsalignleft.png" format="PNG"/></imageobject>
</inlinemediaobject
> <guilabel
>Esquerda</guilabel
>: Alinha os elementos de dados na horizontal para a posição horizontal do elemento mais à esquerda. Isto só afecta as posições horizontais.</para
></listitem>
<listitem
><para>
<inlinemediaobject
><imageobject>
<imagedata fileref="hi22-action-rocsalignhmiddle.png" format="PNG"/></imageobject>
</inlinemediaobject
> <guilabel
>Centro</guilabel
>: Alinha os elementos de dados na horizontal para a posição central do elemento do tipo. Isto só afecta as posições horizontais.</para
></listitem>
<listitem
><para>
<inlinemediaobject
><imageobject>
<imagedata fileref="hi22-action-rocsalignright.png" format="PNG"/></imageobject>
</inlinemediaobject
> <guilabel
>Direita</guilabel
>: Alinha os elementos de dados na horizontal para a posição horizontal do elemento mais à direita. Isto só afecta as posições horizontais.</para
></listitem>
<listitem
><para>
<inlinemediaobject
><imageobject>
<imagedata fileref="hi22-action-rocsaligncircle.png" format="PNG"/></imageobject>
</inlinemediaobject
> <guilabel
>Círculo</guilabel
>: 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.</para
></listitem>
<listitem
><para>
<inlinemediaobject
><imageobject>
<imagedata fileref="hi22-action-rocsaligntree.png" format="PNG"/></imageobject>
</inlinemediaobject
> <guilabel
>Minimizar as Arestas Cruzadas</guilabel
>: Reorganiza os elementos de dados seleccionados para minimizar o número de arestas cruzadas (aplicando o algoritmo de Fruchterman-Reingold).</para
></listitem>
</itemizedlist>
<screenshot>
<screeninfo
>A Barra de Alinhamento</screeninfo>
<mediaobject>
<imageobject>
<imagedata fileref="rocs-toolbar-alignment.png" format="PNG"/>
</imageobject>
<textobject>
<phrase
>A Barra de Alinhamento</phrase>
</textobject>
</mediaobject>
</screenshot>
</sect2>
</sect1>
<sect1 id="user-interface-graph-properties">
<title
>O Painel de Propriedades do Grafo</title>
<para
>No topo do painel, poderá seleccionar o documento do grafo actual. Por baixo deste, poderá criar estruturas novas ou configurar as existentes. </para>
<sect2 id="user-interface-graph-properties-document">
<title
>Selecção do Documento e Propriedades</title>
<para
>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 <menuchoice
><guimenu
>Projecto</guimenu
> <guimenuitem
>Novo Documento de Grafo</guimenuitem
></menuchoice
> ou <menuchoice
><guimenu
>Projecto</guimenu
> <guimenuitem
>Importar um Grafo do &rocs;</guimenuitem
></menuchoice
>. Poderá também importar documentos de grafos a partir de aplicações de terceiros (para tal, consulte <xref linkend="import-export"/>). Ao carregar em <guibutton
>Propriedades</guibutton
>, poderá aceder às propriedades do documento do grafo. </para>
</sect2>
<sect2 id="user-interface-graph-properties-datastructure-create">
<title
>Criar uma Nova Estrutura de Dados</title>
<para
>Poderá criar uma nova estrutura de dados se introduzir um identificador (sem espaços nem caracteres especiais) e depois carregando em <guibutton
>Adicionar</guibutton
>. O identificador é usado para aceder à estrutura de dados dos algoritmos. </para>
</sect2>
<sect2 id="user-interface-graph-properties-datastructure-config">
<title
>Configurar a Estrutura de Dados</title>
<para
>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: </para>
<itemizedlist>
<listitem
><para
><guibutton
>Apagar</guibutton
>: Apaga esta estrutura de dados. </para
></listitem>
<listitem
><para
><guilabel
>Nome:</guilabel
> Este é o identificador da estrutura de dados. É o que o seu algoritmo deverá usar para aceder à estrutura de dados. </para
></listitem>
<listitem
><para
><guilabel
>Opções de Visualização</guilabel
> 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. </para
></listitem>
</itemizedlist>
</sect2>
<sect2 id="user-interface-graph-properties-datastructure-individual">
<title
>Configurar as Opções do 'Plugin' da Estrutura de Dados</title>
<para
>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: </para>
<sect3>
<title
>'Plugin' do Grafo</title>
<para
>Use o <guilabel
>Tipo de Grafo</guilabel
> para seleccionar o tipo do grafo. O significado destes tipos é o seguinte: </para>
<itemizedlist>
<listitem
><para
><guilabel
>Grafo Direccionado</guilabel
>: Um grafo com arestas direccionadas, nos quais são proibidas arestas com a mesma orientação e os mesmos nós. </para
></listitem>
<listitem
><para
><guilabel
>Grafo Não-Direccionado</guilabel
>: Um grafo com arestas não direccionadas, nos quais são proibidas várias arestas entre os mesmos nós. </para
></listitem>
<listitem
><para
><guilabel
>Multi-Grafo Direccionado</guilabel
>: Um grafo com arestas direccionadas, no qual são permitidas várias arestas orientadas entre os mesmos nós. </para
></listitem>
<listitem
><para
><guilabel
>Multi-Grafo Não-Direccionado</guilabel
>: Um grafo com arestas não-direccionadas, no qual são permitidas várias arestas entre os mesmos nós. </para
></listitem>
</itemizedlist>
</sect3>
<sect3>
<title
>'Plugin' da Árvore</title>
<para
>Ao assinalar a propriedade <guilabel
>Mostrar todas as arestas</guilabel
>, 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ó. </para>
</sect3>
</sect2>
</sect1>
</chapter>
<chapter id="scripting">
<title
>Criar e Executar os Algoritmos no &rocs;</title>
<para
>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.) </para>
<para
>É 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. </para>
<sect1 id="scripting-data-structure">
<title
>Os Elementos de Base da Estrutura de Dados</title>
<para
>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. </para>
<sect2
><title
>Propriedades da Estrutura de Dados de Base</title>
<para
>As estruturas de dados são identificadas pelo seu nome. Assumindo que criou uma estrutura de dados chamada <literal
>grafoteste</literal
>, 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 <literal
>grafoteste.list_nodes();</literal
> no programa. </para>
<sect3>
<title
>Propriedades e Funções da Estrutura de Dados de Base</title>
<para
>Cada estrutura de dados <literal
>grafoteste</literal
> tem as seguintes propriedades que podem ser lidas ou escritas com <literal
>grafoteste.propriedade</literal
>: </para>
<programlisting
>string name // identificação da estrutura de dados
</programlisting>
</sect3>
</sect2>
<sect2>
<title
>Propriedades e Funções de Base do Elemento de Dados</title>
<para
>Cada elemento de dados tem as seguintes propriedades que podem ser lidas ou escritas: </para>
<programlisting
>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
</programlisting>
<para
>Para além disso, todas as propriedades dinâmicas de um elemento de dados poderão ser acedidas pelo seu nome. </para>
<para
>Cada elemento de dados oferece os seguintes métodos: </para>
<programlisting
> 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
</programlisting>
</sect2>
<sect2>
<title
>Propriedades e Funções de Base das Arestas</title>
<para
>Cada aresta tem as seguintes propriedades que podem ser lidas ou escritas: </para>
<programlisting
> 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
</programlisting>
<para
>Para além disso, todas as propriedades dinâmicas de uma aresta podem ser acedidas pelo seu nome. </para>
<para
>Cada objecto de aresta oferece os seguintes métodos: </para>
<programlisting
>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
</programlisting>
</sect2>
</sect1>
<sect1 id="scripting-plugin-graph">
<title
>O 'Plugin' do Grafo</title>
<sect2>
<title
>Propriedades e Funções do Grafo</title>
<sect3>
<title
>A Estrutura do Grafo</title>
<para
>Dado um objecto de estrutura de dados do tipo grafo, poderá invocar as seguintes funções-membro: </para>
<programlisting
>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
</programlisting>
</sect3>
<sect3>
<title
>Nós do Grafo</title>
<para
>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: </para>
<programlisting
>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'
</programlisting>
</sect3>
<sect3>
<title
>Arestas do Grafo</title>
<para
>Dadas as arestas de uma estrutura de dados do tipo "Grafo", só estão disponíveis as propriedades da estrutura de dados de base. </para>
</sect3>
</sect2>
<sect2>
<title
>Algoritmos da Estrutura do Grafo</title>
<para
>O 'plugin' do grafo oferece algumas funções especiais que podem ser usadas a partir do motor de programação.</para>
<variablelist>
<varlistentry>
<term
>Cálculo do Caminho Mais Curto</term>
<listitem>
<para
>Calcula o caminho mais curto entre os nós <emphasis
>inicio</emphasis
> e <emphasis
>fim</emphasis
>. Ambos os nós deverão pertencer ao mesmo grafo. Este cálculo respeita o facto de o grafo ser direccionado ou não.</para>
<funcsynopsis>
<funcprototype
><funcdef
>array <function
>dijkstra_shortest_path</function
></funcdef
> <paramdef
>node <parameter
><replaceable
>inicio</replaceable
></parameter
></paramdef
> <paramdef
>node <parameter
><replaceable
>fim</replaceable
></parameter
></paramdef
> </funcprototype>
</funcsynopsis>
</listitem>
</varlistentry>
<varlistentry>
<term
>Distâncias Mais Curtas</term>
<listitem>
<para
>Calcula o caminho mais curto entre os nós <emphasis
>inicio</emphasis
> 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.</para>
<funcsynopsis>
<funcprototype
><funcdef
>array <function
>dijkstra_shortest_path</function
></funcdef
> <paramdef
>node <parameter
><replaceable
>inicio</replaceable
></parameter
></paramdef
> <paramdef
>node <parameter
><replaceable
>fim</replaceable
></parameter
></paramdef
> </funcprototype>
</funcsynopsis>
</listitem>
</varlistentry>
</variablelist>
</sect2>
</sect1>
<sect1 id="scripting-plugin-linkedlist">
<title
>O 'Plugin' da Lista Ligada</title>
<sect2>
<title
>Propriedades e Funções da Lista Ligada</title>
<sect3>
<title
>A Estrutura da Lista Ligada</title>
<para
>Dada uma estrutura de dados do tipo "Lista Ligada", poderá invocar as seguintes funções-membro: </para>
<programlisting
>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
</programlisting>
</sect3>
<sect3>
<title
>Nós da Lista Ligada</title>
<para
>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: </para>
<programlisting
>node front(); // devolve o antecessor do nó
</programlisting>
</sect3>
<sect3>
<title
>Arestas da Lista Ligada</title>
<para
>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. </para>
</sect3>
</sect2>
</sect1>
<sect1 id="scripting-plugin-rootedtree">
<title
>O 'Plugin' da Árvore</title>
<sect2>
<title
>Propriedades e Funções da Árvore</title>
<sect3>
<title
>A Estrutura em Árvore</title>
<para
>Dada uma estrutura de dados do tipo "Árvore", as seguintes propriedades podem ser lidas ou escritas: </para>
<programlisting
>ShowAllPointers // mude para 'true' (verdadeiro) para mostrar todas as arestas ou para 'false' se as várias arestas devem ser comprimidas
</programlisting>
<para
>Dado um objecto do tipo "Árvore", poderá invocar as seguintes funções-membro: </para>
<programlisting
>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
</programlisting>
</sect3>
<sect3>
<title
>Nós da Árvore</title>
<para
>Dado um objecto do tipo "Árvore", as seguintes propriedades podem ser lidas ou escritas: </para>
<programlisting
>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
</programlisting>
<para
>Dado um objecto do tipo "Árvore", poderá invocar as seguintes funções-membro: </para>
<programlisting
>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ó
</programlisting>
</sect3>
<sect3>
<title
>Arestas da Árvore</title>
<para
>Dadas as arestas de uma estrutura do tipo "Árvore", só estão disponíveis as propriedades da estrutura de base. </para>
</sect3>
</sect2>
</sect1>
<sect1 id="scripting-controls">
<title
>Controlar a Execução dos Programas</title>
<sect2>
<title
>Ficheiros de Inclusão</title>
<para
>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 <menuchoice
><guimenu
>Documento do Programa</guimenu
> <guimenuitem
>Inclusões Possíveis</guimenuitem
></menuchoice
>, 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: </para>
<programlisting
>include_script(string local); // localização relativa ou absoluta do ficheiro do programa
</programlisting>
</sect2>
<sect2 id="scripting-output">
<title
>Resultado do Programa</title>
<para
>Durante a execução de um algoritmo, o resultado de depuração e do programa aparece no <emphasis
>Resultado de Depuração ∧ Programa</emphasis
>. 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). </para>
<para
>Pode controlar o texto que é apresentado no resultado do programa, usando as seguintes funções: </para>
<programlisting
>output(string mensagem); // mostra a mensagem como resultado do programa
debug(string mensagem); // mostra a mensagem como resultado de depuração
</programlisting>
</sect2>
<sect2 id="scripting-controlling">
<title
>Controlar a Execução do Programa</title>
<para
>Existem diferentes modos de execução para os seus programas. </para>
<para
>Pode controlar o texto que é apresentado no resultado do programa, usando as seguintes funções: </para>
<itemizedlist>
<listitem
><para>
<inlinemediaobject
><imageobject>
<imagedata fileref="rocs-control-engine-run.png" format="PNG"/></imageobject>
</inlinemediaobject
> <guilabel
>Iniciar</guilabel
>: Executa o programa até este terminar.</para
></listitem>
<listitem
><para>
<inlinemediaobject
><imageobject>
<imagedata fileref="rocs-control-engine-stop.png" format="PNG"/></imageobject>
</inlinemediaobject
> <guilabel
>Parar</guilabel
>: Interrompe a execução do programa (só disponível se tiver um programa em execução).</para
></listitem>
<listitem
><para>
<inlinemediaobject
><imageobject>
<imagedata fileref="rocs-control-engine-step.png" format="PNG"/></imageobject>
</inlinemediaobject
> <guilabel
>Um Passo</guilabel
>: Executa o programa até que um passo termine. Um passo termina quando o programa invocar a função <literal
>interrupt()</literal
>:</para>
<programlisting
>interrupt(); // interrompe um passo
</programlisting>
</listitem>
<listitem
><para>
<inlinemediaobject
><imageobject>
<imagedata fileref="rocs-control-engine-debug.png" format="PNG"/></imageobject>
</inlinemediaobject
> <guilabel
>Depurar</guilabel
>: Executa o programa no modo de depuração. Isto abre a janela de depuração do QtScript.</para
></listitem>
</itemizedlist>
</sect2>
</sect1>
</chapter>
<chapter id="import-export">
<title
>Importar e Exportar</title>
<sect1 id="import-export-projects">
<title
>Trocar Projectos do &rocs;</title>
<para
>Poderá importar e exportar os projectos do &rocs; como pacotes <literal
>.tar.gz</literal
>. 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 <menuchoice
><guimenu
>Ficheiro</guimenu
> <guimenuitem
>Importar um Projecto</guimenuitem
></menuchoice
> e <menuchoice
><guimenu
>Ficheiro</guimenu
> <guimenuitem
>Exportar o Projecto</guimenuitem
></menuchoice
>, respectivamente. </para>
</sect1>
<sect1 id="import-export-graphs">
<title
>Importação e Exportação dos Documentos do Grafo</title>
<para
>O &rocs; suporta de momento a importação e exportação para os seguintes formatos de ficheiros:</para>
<itemizedlist>
<listitem
><para
>Ficheiros do DOT, também conhecidos pelo Graphviz</para
></listitem>
<listitem
><para
>Ficheiros GML</para
></listitem>
<listitem
><para
>Ficheiros no formato Trivial Graph Format</para
></listitem>
</itemizedlist>
<sect2 id="format-specification-tgf">
<title
>Trivial Graph Format</title>
<para
>O formato <emphasis
>Trivial Graph Format</emphasis
> (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. </para>
<sect3>
<title
>Especificação do Formato</title>
<itemizedlist>
<listitem
><para
>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).</para
></listitem>
<listitem
><para
>Um nó consiste num número inteiro (identificador), seguido de um espaço e de um texto arbitrário.</para
></listitem>
<listitem
><para
>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.</para
></listitem>
</itemizedlist>
</sect3>
<sect3>
<title
>Exemplo</title>
<programlisting
>1 nó inicial
2 transmissor
3 receptor
#
1 2 azul
2 1 vermelho
2 3 verde
</programlisting>
</sect3>
</sect2>
</sect1>
</chapter>
<chapter id="credits">
<title
>Créditos e Licença</title>
<para
>&rocs; </para>
<para
>Copyright do Programa:</para>
<itemizedlist>
<listitem
><para
>'Copyright' 2008 de Ugo Sangiori (ugorox AT gmail.com)</para
></listitem>
<listitem
><para
>'Copyright' 2008-2012 de Tomaz Canabrava (tcanabrava AT kde.org)</para
></listitem>
<listitem
><para
>'Copyright' 2008-2012 de Wagner Reck (wagner.reck AT gmail.com)</para
></listitem>
<listitem
><para
>'Copyright' 2011-2012 de Andreas Cord-Landwehr (cordlandwehr AT googlemail.com)</para
></listitem>
</itemizedlist>
<para
>'Copyright' da Documentação:</para>
<itemizedlist>
<listitem
><para
>Documentação com 'copyright' 2009 de &Anne-Marie.Mahfouf; &Anne-Marie.Mahfouf.mail;</para
></listitem>
<listitem
><para
>Documentação com 'copyright' 2009 de Tomaz Canabrava (tcanabrava at kde dot org)</para
></listitem>
<listitem
><para
>Documentação com 'copyright' 2011-2012 de Andreas Cord-Landwehr (cordlandwehr AT googlemail.com)</para
></listitem>
</itemizedlist>
<para
>Tradução de José Nuno Pires <email
>zepires@gmail.com</email
></para
>
&underFDL; &underGPL; </chapter>
<appendix id="installation">
<title
>Instalação</title>
<sect1 id="getting-rocs">
<title
>Como obter o &rocs;</title>
&install.intro.documentation; </sect1>
<sect1 id="compilation">
<title
>Compilação e instalação</title>
&install.compile.documentation; </sect1>
</appendix>
&documentation.index;
</book>
<!--
Local Variables:
mode: sgml
sgml-minimize-attributes: nil
sgml-general-insert-case: lower
sgml-indent-step:0
sgml-indent-data:nil
End:
-->
distrib
>
Mageia
>
5
>
x86_64
>
media
>
core-release
>
by-pkgid
>
88f57d599940e0bbc20cd457b1c23e9b
>
files
>
1169
