GTAD
SourceForge.net Logo Support This Project  


Documentation Discussion Download Author

The GTAD (Graph Toolkit for Algorithms and Drawings) is an attempt to construct a set of flexible, reusable, and efficient C++ implementations of graph representations and algorithms (including drawing/layout). It is developed with the generic programming paradigm and under the same principles of the BGL (Boost Graph Library).

Although the GTAD is intended to be highly compatible with the BGL there are a few design decisions that were taken differently. In the GTAD algorithms are implemented as classes, policy-based mechanisms are available, and they are all formalized as concepts.

Graph concepts from the BGL are modeled by GTAD's advanced adjacency list. The property map interface is also followed. In most cases interoperability between them is straightforward - there are a few differences regarding visitor's concepts. (Check this out for an example.) Therefore, it is possible to use just "parts" of the GTAD (the graph type or the algorithms) in conjunction with the BGL (or other compliant library) or to use it as a self-contained library.


Participate!
I develop the GTAD on my "spare" time. It's kind of a hobby. Still, any kind of feedback is welcome!

News!
GTAD 1.0.0 (a3) released.
    + Content:
           - Advanced adjacency list;
           - Generalized search;
           - Depth-first search (DFS);
           - Breadth-first search (BFS);
           - Dijkstra shortest-path;
           - Bellman-Ford shortest-path;
           - Augmenting-path maxflow [policy-based];
           - Preflow-push maxflow [policy-based];
           - Minflow [policy-based];
           - Cycle-cancelling mincost flow [policy-based];
           - Biconnectivity;
           - St-numbering;
           - Hopcroft-Tarjan planarity test [policy-based];
           - DFS-based biconnectivity augmentation.
    + Compilers:
           - MSVS 2005;
           - GCC 4.2.3 (Ubuntu).   

Graph Related Software!
C++ Liraries and Frameworks:
      BGL (Boost Graph Library)
      OGDF (Open Graph Drawing Framework) [Note: The old AGD.]
      LEDA (Library of Efficient Data types and Algorithms)
      GTL (Graph Template Library)
      GOBLIN Graph Library
      GDToolkit (Graph Drawing Toolkit) [Note: Now, a LEDA independent version.]
      CGAL (Computational Geometry Algorithms Library)


Copyright ® Leandro T. C. Melo

Valid HTML 4.01 Transitional