Uma biblioteca para desenho de grafos construída sob o paradigma de programação genérica

Exportado OPUSMade available in DSpace on 2019-08-10T00:11:11Z (GMT). No. of bitstreams: 1 leandro_terra_cunha_melo.pdf: 2027596 bytes, checksum: bdc2c75b20bf59449ba3300a42a3da6a (MD5) Previous issue date: 25Grafos são estruturas combinatoriais presentes em inúmeras aplicações. Seus vértices e arestas correspondem, respectivamente, às entidades e às relações de adjacência de determinado domínio. Apesar de um grafo ser um conceito puramente matemático, é fundamental que seu desenho seja inteligível e que transmita o máximo de informações possível. Em alguns casos, a clareza do desenho de um grafo não é apenas uma questão estética, mas um requisito essencial da aplicação. Este trabalho apresenta uma biblioteca para desenho de grafos chamada GTAD (Graph Toolkit for Algorithms and Drawings). Uma visão introdutória sobre a área de desenho de grafos, em conjunto com uma análise detalhada de três algoritmos de desenho ortogonal de grafos, também é apresentada. A GTAD é desenvolvida na linguagem de programação C++, sob o paradigma de programação genérica, que visa abstrair implementações das estruturas de dados sobre as quais elas operam. O mecanismo de templates da linguagem C++, ferramenta fundamental para a programação genérica, garante a resolução de tipos em tempo de compilação. Conseqüentemente, implementações baseadas nesta abordagem são comumente mais eficientes que aquelas que utilizam o paradigma de orientação a objetos em sua forma convencional. Resultados de desempenho de operações básicas de manipulação de grafos mostram que a GTAD é superior a outras bibliotecas, quando comparados os tempos de execução. Implementações de alguns algoritmos também foram submetidas a testes de desempenho e obtiveram resultados positivos. Finalmente, desenhos de grafos de categorias distintas, gerados sob diferentes estratégias, são discutidos e comparados entre si.Graphs are combinatorial structures used in a great variety of applications. Vertices and edges of a graph correspond, respectively, to entities and relationships of a specic domain. Although the concept of a graph is purely mathematical, it is very important that its drawing effectively convey all necessary information. There are cases in which the clarity of a graph drawing is not a simple aesthetical matter, but part of the application's requirement. This work presents the GTAD (Graph Toolkit for Algorithms and Drawings) graph drawing library. An introductory perspective of the graph drawing area, along with a detailed analysis of three orthogonal drawing algorithms, is also presented. The GTAD is developed with the C++ programming language, under the generic programming paradigm, which focus on abstracting implementations from the data structures in which they operate. C++ template is a fundamental tool to achieve generic programming. Since type resolution of templates is performed at compile time, generic libraries are usually more efficient than libraries developed under the object-oriented paradigm in its traditional form. Performance results of basic graph manipulation operations show that GTAD is faster than other libraries when execution times are compared. Implementations of a few algorithms were also submitted to performance tests and obtained positive results. Finally, drawings of graphs from different categories, generated by different strategies, are discussed and compared against each other