O estudo foi feito através da leitura dos artigos correspondentes e através da leitura de algumas das referências neles indicadas.
Os dois algoritmos de força apresentam descrições detalhadas e claras de como implementá-los. O algoritmo de Rao e Deekshit, no entanto, está descrito de forma confusa, de forma que foi necessário um estudo mais cuidadoso antes da implementação.
A implentação dos algoritmos é
apoiada sobre a Boost
Graph Library (BGL). Boost é uma conjunto de
bibliotecas que, em geral, usa extensivamente os recursos da linguagem
C++, como templates e a STL (Standard
Template Library),
sendo assim basicamente um conjunto de headers (com poucas
excessões). O estudo da BGL foi feito principalmente pela
sua
documentação (disponível no site
oficial) e
às vezes também pela
inspeção dos headers
utilizados. Com esta biblioteca, a criação das
estruturas
dos grafos torna-se bastante simplificada e assim pode-se usufruir de
todos os recursos disponíveis na BGL, como os algoritmos
mais
comuns de grafos.
Utilizando o conceito de bundled properties da BGL, associou-se uma estrutura com informações
adicionais ao grafo, de modo que ele possa representar um diagrama. A
implementação dos dois algoritmos é bem parecida.
São algoritmos iterativos e cada iteração consiste
de 3 laços principais: cálculo das forças devido
aos nós, cálculo das forças devido às
arestas e finalmente atualização das
posições.
Foram necessárias mais algumas estruturas auxiliares para este algoritmo. Após verificar a profundidade da árvore, são criados dois vetores de posição livre (um para esquerda, outra para direita) que são consultados e atualizados ao posicionar um item. O algoritmo utiliza DFS (depth-first search), mas a implementação genérica disponível na BGL não foi utilizada. Ao invés disso, foi elaborada uma versão que visa principalmente evitar problemas ao aplicar o algoritmo de Rao e Deekshit a dados de sistemas cíclicos. A implementação foi satisfatória: os resultados para sistemas em árvore são os mesmos que do algoritmo original e a aplicação a sistemas com ciclos foi possível, apesar de não apresentar resultados satisfatórios.
Os estudos se basearam na aplicação dos algoritmos a vários grafos diferentes. Inicialmente e durante a implementação, foram utilizados grafos gerados aleatoriamente. Em seguida implementou-se alguns procedimentos de leitura, para os arquivos IEEE CDF, arquivos de listagem de ramos e arquivos PWF do ANAREDE, além da criação de um formato próprio, permitindo salvar diagramas completos e carregá-los futuramente.
Utilizando estes novos formatos de arquivo, foi possível estudar o comportamento dos algoritmos para um grande número de redes e grafos. Alguns exemplos podem ser vistos em Imagens dos Resultados.