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).
|
|
Copyright ®
Leandro T. C. Melo
|