New Graph Classes

I am currently considering alternative approaches to the implementation of the undirected_graph and directed_graph classes. One thing is clear - i intend to leverage as much existing code in Boost.Graph as possible, so it's probable that these classes will be implemented in terms of the adjacency_list<> class. The irony to this approach is that I am not introducing new classes so much as additional abstractions around an existing class. On the other hand, it does make implementation a breeze.

Since I'm planning on reusing the adjacency_list<> for this project, I should point out that its template parameters are in a somewhat strange order. I don't fully understand why the out edge list selector would be first and the edge list selector would be last (even after the vertex, edge and graph properties). I suspect that the edge list was templated as an afterthought and to preserve source code compatibility, it was added to the end of the template parameter list. Still, it's just a little ugly if you actually plan to specialize the class beyond its default types.

(Jeremy: Yes, the edge list selector was added much later, in response to a user request, and had to go at the end to preserve backwards compatibility, the blessing and curse that it is!)

Question: Should the [un]directed graph classes really allow the override of the underlying collections? If the intent of these classes is to get the users up and running, then perhaps those options could be seen as optimizations rather than algorithm design choices. Since these classes can act as drop-in replacements (and are in fact, implemented in terms of an adjacency list), it should be relatively easy to "upgrade" if the user really needs to change those options. Of course, changing the storage options actually affects properties like iterator and descriptor stability, but that's going to be a gotcha anyways.

(Jeremy: I don't think it is a good idea to allow the override... user's can go directly to adjacency_list if they want that level of customization. The iterator stability is an important issue and I'd recommend specifying that the user-friendly graph classes have to preserve stability.)

Question: Should the [un]directed classes implement or provide checks to ensure that graphs are simple or contain no self-loops? How can this be managed? My gut feeling is that a good answer to this question might be a complete redesign of the graph concept structure. For exmaple, graph properties might be encapsulated in a struct of tags containing items like allow directedness, parallel edge support, self-loop support, etc. This is probably something to think about in the long-term.

(Jeremy: I would not prohibit self-loops unless you found a very good motivation. Otherwise you're just getting in the user's way.)

I'm going to use the following abbreviations for template parameters quite frequently:

• VL - The type of the vertex list. The vertex list stores all of the vertices of the graph.
• EL - The type of the edge list. Like the vertex list, this stores all the edges in the graph.
• OEL - The type of the out edge list. Each vertex has a corresponding out edge list (hence the name adjacency list) that stores its outgoing edges.
• VP - The type of the vertex property (either internal or bundled). Each vertex is associated with an instance of this type.
• EP - The type of the edge property (also internal or bundled). Each edge is associated with an instance of this type.
• GP - The type of the graph property. These are "global" to the entire graph.

Rather than embed all of the design iterations into a single page, I've decided to give each their own page so they can be cleanly separated from the rest of the work here.

• First Design
• Second Design
• Third Design