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

Abstract

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.