What about the bgl

What about the BGL (Boost Graph Library)?

The BGL is a nice library that has been available for many years and has established itself as the de facto standard regarding graphs and generic programming. The GTAD is developed under the same construction principles of the BGL. However, I believe that there are still room for improvements and that a few design changes might make a difference.

Most concepts from the BGL (including Graphs and Property Maps) are entirelly followed by the GTAD. For operations or types that are not available in the BGL the GTAD provides its own concepts. Therefore, in many cases the GTAD is highly compatible with the BGL. There is not even a need for template specialization. (Check this out for an example.) There are, though, a couple of observations to be made. The first one relates to the tags directed_category, edge_parallel_category, and traversal_category from BGL's Graph concept.

There are no guarantees that graph representations from others libraries are not able to change their directionality at runtime. One example is the GRAPH type from LEDA (Library of Efficient Data Types and Algorithms). By default, it represents directed graphs. However, a call to the member function make_undirected makes the graph undirected. Conversely, a call to the member function make_directed has the opposite effect. A similar problem arises when allow_parallel_edges_tag is used for the category of parallel edges. By default, the GRAPH type does not prevents parallel edges. However, after a call to global function Make_Simple or in a graph generated by function random_graph with parameter no_parallel_edges set to true, parallel edges do not exist. A dispatching mechanism based on this tag could waste a lot of time looking for parallel edges in such a graph. I also wonder whether tag traversal_category is really necessary. The Graph concept of the GTAD does not require any of these tags.

Visitor's concepts from the GTAD are also a little bit different. Among all valid expressions of a visitor, there are several of them that take an edge descriptor as a parameter. One example is BGL's tree_edge callback (the GTAD's equivalent is called tree_link and there is a reason for that). The dijkstra_shortest_paths function, as many others in the BGL, is implemented in terms of a BFS visitor. The edge relaxation step of Dijkstra's algorithm is performed on a callback function of a visitor. Particularly in this case, there is an interesting use of tag directed_category (discussed in the previous paragraph) to determine whether the graph is directed or undirected. The problem is that the relaxation condition of a particular edge e must be performed in terms of the vertex v currently being processed by the algorithm and the vertex w, which is the other end of e. Since in undirected graphs, an edge (s, t) is the same of an edge (t, s), only through an edge descriptor, passed by the visitor's callback, it is not possible to determine if calls to source(e, g) and target(e, g) will actually return vertices v and w, respectively. The solution is then to verify the directed_category of the graph and if it is undirected_tag, a double check must be made in the edge relaxation condition. This is avoided in the GTAD because its visitors not only pass the edge descriptor as an argument, but they also pass the vertex descriptor which was used as the "origin" to retrieve a particular edge. So, there's no need to use such a tag.

Graph algorithms do not necessarily have well defined input and output like those in the STL (Standard Template Library). That is why they are implemented as classes in the GTAD, as opposed to the BGL where they are implemented as functions. Consider, for example, BGL's named parameter version of function biconnected_componets. The purpose of this function is to return the number of biconnected components of the graph. There is one overload that adds to the return an Output Iterator for the articulation points of the graph. In addition, there is an associated function that only computes the articulation points of the graph. What if one would also like to retrieve the bridges of the graph? Probably, more overloads or functions refactoring would be necessary.

Situations like the one just mentioned are easier to approach by adding a new member function to a class. There are other reasons that make me think that implementing classes for algorithms of rich combinatorial structures like graphs is a good idea: all required information for the algorithm is encapsulated within an object; pre-processing can be done only once for many executions; sometimes algorithms belong to a conceptual hierarchy and using inheritance is a natural way to implement them; functions with a large number of parameters require a documentation (or source code) to look at, while member functions of a class can have meaningful names specifying what they do.

A final observation regarding algorithms in the GTAD is that they are formalized as concepts. An examples is the Single Source Shortest Path Algorithm concept. Implementations of Dijkstra's or Bellman-Ford's algorithm can be switched very easily. All the benefits of the "programming with concepts" paradigm, which are extensively used in the STL and in the BGL, also apply to algorithms.

It is relatively common for graph algorithms to be described with a high level of abstraction. The augmenting-path method by Ford and Fulkerson for finding a maximum flow in a network is an elucidative example. There is not a specific rule for how such paths are chosen. Although the shortest augmenting-path strategy of Edmonds and Karp is widely accepted, a user might prefer an implementation that uses the longest-paths or even an implementation that takes other information into consideration. In the GTAD, policies, also formalized as concepts, come to the rescue when implementing such abstractions. All of the policy-based algorithms provide means for the user to set data that is passed to the policy whenever it is executed.

A few algorithms of the GTAD allow the user to decide which "items" should be stored during the execution. Instead of writing visitors like distance_recorder to accomplish this task, a parametrization is possible for the most usual items like the tree and back edges for a depth-first search or the cross edges and distances for a breadth-first search. Depending on the algorithm more items are available. Such parameterization is done through a class template that accepts named template parameters that correspond to the desired items.

In general, I tried to remove some template parameters in the algorithms of the BGL. For example, cases like distance_inf and distance_zero in BGL's implementation of Dijkstra's algorithm. Since the type of these parameters must be the same as the value type of the distance_map, I chose to provide two member functions in GTAD's implementation of Dijkstra's algorithm to set the infinity and zero values. Another case is of template parameters capacity_map and residual_capacity_map of BGL's flow algorithms. Both of these maps have an edge descriptor as the key type and some kind of flow unit as the value type. In the GTAD, I opted to provide only one template parameter, which is the flow_unit_map, that can be used as type for both the capacity and residual capacity maps. This way, the number of template parameters is reduced and there is no significant loss of flexibility.