Graph Drawing Toolkit

Project philosophy

Focusing on the drawing, not on graphics.

• Many different types of graph representations are used in the industry, with a number of graphic peculiarities strictly related to their semantics. However, most of such representations have a common drawing type : organization charts, genealogy trees, object-oriented inheritance trees, for instance, have different graphics but a common hierarchical drawing type. Similarly, entity-relationship and data-flow-diagrams generally have both an orthogonal drawing type.


• As a consequence, libraries focused on graphics tend to be specific to some kind of applications (networking or software engineering or decision support), while GDT, being focused on the drawing conventions adopted, rather than on their graphics, has a wider range of applicability.


• Moreover, it is our belief and experience that the major problem for application developers, is not to draw nodes and edges with the proper icons, colors and line-styles (lots of libraries already exist for doing that), but to generate the best drawings for their graphs, minimizing the length of the edges, the number of crosses and bends along them, the total area of the drawing, etc. A challenge requiring relevant expertise in the graph-drawing theory, and man/years of effort for implementing efficient algorithms and data-structures.


• For the above-mentioned reasons, the GDT project is mainly focused on sophisticated topology-based layout algorithms supporting the developer in getting the best drawing for his graph. It is worth noting, however, that GDT still provides basic graphic capabilities (some different shapes for nodes, colors, line types, labels, etc.) which are generally enough for research and the average commercial application.
  

Delivering the right level of control and abstraction

• In order to effectively deliver graph-drawing functionality, it is essential to provide the customer with methods compatible with his expertise and needs, for controlling the graph and the layout process without getting overwhelmed by a counterproductive amount of details on algorithms and data-structures.


• However, what is a counterproductive detail for the student who just wants to draw a schema of its web-site, might be essential for the experienced application developer, who needs the maximum level of control to deliver perfect drawings with his new decision-support business tool. In one word, different users need a different level of control and abstraction with respect to the same graph-drawing functionality.


• With GDT, we deliver two different solutions globally addressing the needs of a wide range of users, including expert and novice application developers, system integrators, academic teachers and researchers, and people without any specific expertise. Each solution offers a different balance between control and abstraction:
  
  
  1. A programming interface for application developers.
     Expert application developers can take advantage of a fully object-oriented API (the GAPI) delivering them a very high level of control on the graph internal data-structures, and on the automatic layout process.
  
  
  
  2. A configurable layout generator for system integrators.
     Developers who need to integrate an existing (legacy) application with additional graph-drawing capabilities, can rely on a stand-alone batch layout generator (the BLAG) that can be simply interfaced by means of simple ASCII files. Despite its black-box concept, the BLAG can be configured with directives and constraints it read from a configuration file, and therefore still offers a level of control on the layout process which is compatible with most commercial and research applications. Researchers who need to test layout algorithms on a large set of graphs, can also launch the batch generator within a simple script looping across the whole graph set (by the way, this is one of the techniques we have used to test the GAPI itself)

Product key points

• A specific class for each graph type
  All the graph algorithms implemented in GDT are encapsulated as methods of the simplest class on which they are safely applicable. Derived classes inherit methods from the ancestor ones optionally refining or hiding them when unsafe. Inheritance and encapsulation effectively help the application developer in dealing with the intrinsic complexity of graph algorithms and data structures.


• Getting the right drawing by using the right algorithm
  Matching the aesthetic expectations of the end-user can be achieved by the developer by handling the graph with the proper GDT classes, and by properly combining their layout methods. Minimizing the overall area of a graph drawing while keeping edge-crossing to a minimum, making edges short and straight or minimizing the number of their bends, placing nodes and bends into an orthogonal grid... With GDT, years of research in graph-drawing are at the fingertips of any C++ developer.


• Additional flexibility by means of layout constraints
  The possibility to individually enforce layout constraints on nodes and edges makes GDT effectively applicable for drawing graphs with a standard graphic syntax (such as Entity-Relationship, Data-Flow, State Transition and many other diagram types widely used in the industry. Forcing nodes on the border of the drawing, avoiding crosses on a given edge, requiring an edge to contain only left or right bends (just to mention a few examples) means a valuable flexibility for the application developer, and nice drawings for the end-user


• High performance by means of efficient implementation
  GDT algorithms reflect the state-of-the art of the graph-drawing research area, and take advantage of sophisticated and efficient internal data-structures. Developers can tune the ratio between the performances of their applications and the quality of the generated drawings by individually choosing the available "steps" when composing their layout algorithm (for example, concerning orthogonal drawings, GDT provides three orthogonalizers, two compactors and an optional compaction-refinement heuristic, with different quality/performance ratios).


• Reliability proved on a large suite of test graphs
  Although GDT is developed within a research program, it is just as reliable as many industrial products. Automatic tests are performed on each released version, by applying all the drawing algorithms on a test suite of more than 20 thousands graphs ranging in both size (from 10 to 1000 nodes) and type (simply-connected, biconnected, directed, undirected, planar, non-planar, etc.). Since drawing algorithms are heavily based on the general-purpose graph-handling methods, each release of the library is proved to be reliable enough to let developers focusing on their graph-drawing application, rather than on the library itself.


• A qualified research team for a long-term product support
  GDT has been developed by the Algorithm Engineering Research Group of the Computer Science and Automation Department, at the "Roma Tre" University. The Research Group has a long tradition in graph-drawing, and inherits the experience gained by several other groups at the University of Rome "La Sapienza" since 1984. GDT is of primary importance to investigate the real potential of new graph-drawing algorithms, and is perceived by the Research Group as an essential link between the academic research and the industry. The relevant effort already spent by the Department on GDT is the first step of a long-term project with both research and application oriented goals to be achieved in the near future.