An extensible graph class.
- Nodes are identified by positive integers – each node is assigned a unique integer starting at 1.
- Nodes know about both their upper and their lower edges. Iterators can range over all edges, just the upper edges or just the lower edges.
- Nodes store their incident edge information in edge lists; they provide const and non-const iterators which return const and non-const pointers to Edge objects.
- The Graph object provides iterators for all of the edges in the graph; this list is unordered.
- This graph is instantiatable (ie not a pure virtual class). It was also built with extension in mind. See core/scoring/EnergyGraph for an example on how to create an extension of the Node, Edge and Graph classes
- Derived graph classes must define two factory methods: create_node and create_edge which are called by the base class when adding graph elements.
- Edges offer constant-time deletion – edges remove themselves from the edge-lists that their nodes maintain, and from the edge-list that the Graph maintains without having to iterate over those lists.
- Memory is carefully managed to make edge addition and deletion exceedingly fast. The management is through a class "unodered_object_pool" which is very much like boost::object_pool. The base class ueses these unordered object pools for base class edges (when used) and for the edge lists elements. Derived classes may take advantage of this by defining their own unordered_object_pool objects.
- Graphs own the vertices and edges they create. Graphs cannot share or give away edges.
- To delete an edge pointed to by Edge* e in a graph g, call the virtual function "g->delete_edge( &e );"
- Derived classes must invoke the "destroy_everything" method in their virtual destructors so that they are empty by the time the base class destructor is called. The destroy_everything method invokes the virtual delete_edge() method – remember, virtual methods do not work in base class constructors or destructors. If a derived class does not call destroy_everything in its destructor, ~Graph() will call Graph::destroy_everything which will call (surprisingly) Graph::delete_edge and not Derived::delete_edge.
- Derived classes should not invoke the base class copy constructors for the same reason. The base class copy constructor will call the base class create_node and create_edge methods and not the desired derived class versions.
- The virtual functions Derived graph classes must override: Node: copy_from, print, count_static_memory, count_dynamic_memory Edge: copy_from, count_static_mmory, count_dynamic_memory Graph: create_node, create_edge, delete_edge, count_static_memory, count_dynamic_memoryCustom written edge list element class. Little more than a struct. Defined so that edge list memory management could rely on boost::pool like object
1.8.7