| | 6 | 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. |
| | 7 | |
| | 8 | I'm going to use the following abbreviations quite frequently: |
| | 9 | * VL - The type of the vertex list. The vertex list stores all of the vertices of the graph. |
| | 10 | * EL - The type of the edge list. Like the vertex list, this stores all the edges in the graph. |
| | 11 | * 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. |
| | 12 | * VP - The type of the vertex property (either internal or bundled). Each vertex is associated with an instance of this type. |
| | 13 | * EP - The type of the edge property (also internal or bundled). Each edge is associated with an instance of this type. |
| | 14 | * GP - The type of the graph property. These are "global" to the entire graph. |
| | 15 | |
| | 16 | An early prototype of the design proposed to simply (publicly) inherit the `adjacency_list` class like so: |
| | 17 | {{{ |
| | 18 | #!cpp |
| | 19 | namespace boost { |
| | 20 | template <class VL, class EL, class OEL, class VP, class EP, class GP> |
| | 21 | class undirected_graph : public adjacency_list<OEL, VL, undirectedS, VP, EP, GP, EL> |
| | 22 | { }; |
| | 23 | } |
| | 24 | }}} |
| | 25 | Obviously, this probably the simplest implementation possible with as much reuse as possible. In this strategy, I wouldn't even have to implement any of the requirement methods since graphs are always passed by reference, we can let the inheritance handle this for us. The problem with this approach is that if we ever decide to put members into this class, we can run the risk of ''object-slicing'' due to blind reuse of methods that I didn't write. While the alure of a one-line implementation is strong, we should probably defer to practical experience and good advice (in the form of ''C++ Coding Standards: 101 Rules Guidelines and Best Practices'' by Sutter and Alexandrescu). I'm not overloading virtual functions, accessing protected members, and I'm pretty sure `adjacency_list<>` wasn't intended for inheritance. |
| | 26 | |
| | 27 | A second design approach uses composition as a member rather than private inheritance - not for any particular reason, I'm just more familiar with composition. Now, the prototype looks like this: |
| | 28 | |
| | 29 | {{{ |
| | 30 | #!cpp |
| | 31 | namespace boost { |
| | 32 | template <class VL, class EL, class OEL, class VP, class EP, class GP> |
| | 33 | class undirected_graph |
| | 34 | { |
| | 35 | typedef adjacency_list<OEL, VL, undirectedS, VP, EP, GP, EL> graph_type; |
| | 36 | graph_type graph; |
| | 37 | |
| | 38 | public: |
| | 39 | graph_type& impl(); |
| | 40 | const graph_type& impl(); |
| | 41 | |
| | 42 | // other stuff so we comply with graph_traits<> |
| | 43 | }; |
| | 44 | |
| | 45 | // example add_vertex() function... |
| | 46 | template <class VL, class EL, class OEL, class VP, class EP, class GP> |
| | 47 | undirected_graph<VL, EL, OEL, VP, EP, GP>::vertex_descriptor |
| | 48 | add_vertex(undirected_graph<VL, EL, OEL, VP, EP, GP> &g) |
| | 49 | { |
| | 50 | return add_vertex(g.impl()); // calls add_vertex() for adjacency_list |
| | 51 | } |
| | 52 | } |
| | 53 | }}} |
| | 54 | Clearly a very different approach, but once complete it should preserve all of the concept requirements given in the documentation. Interestingly, this is somewhat similar to graph adapter classes except that we aren't really adapting the adjacency list to a different purpose - we're just reducing the "abstractness" of the class by requiring (in this case), that it is instantiated with the `undirectedS` parameter. This approach is also a little more flexible than the previous in that we can add to this class without fear of unexpected consequences in the details of the original implementation. Of course, with this I'll have to write more code. |
| | 55 | |
| | 56 | Other designs? I don't know... private inheritance is an option, but I'm not a big fan. Complete re-implementaiton is possible too, but I'm trying to steer clear of that - partly out of laziness, and partly out of sound engineering principles. |
| | 57 | |
