My application needs to model of and perform operations on a network with 40 - 50 nodes and typically less than 6 edges per node. Both nodes and edges are objects with around 1K data each. During execution the mapping of the network is frequently changed - nodes added and deleted, edges added and deleted, in addition to the properties of individual nodes and edges being adjusted. The node objects and edge objects are allocated using 'new' with the resulting pointers stored in a std::list for each object type.I have experimented with two different approaches for mapping: Put a container in each node to hold IDs of edges, and 2 variables in each edge to store the IDs of the end nodes.Add a new top-level container, separate from the container of edges and container of nodes, to store the mapping information.Functions in the node and member classes will be easier to implement, if the mapping information is stored in those classes. Making changes to the network mapping would be much easier, if all the mapping data was stored separately. But if the mapping is not stored in the nodes and edges, then member functions in the nodes and edges need a way to get mapping information from the parent object.Is there a data structure or a conceptual technique that gives the best of both approaches, without duplicating data or breaking encapsulation? Performance is not major concern, since there are not any extremely expensive calculations involved. The more important concern is for safe, understandable, maintainable code.
What data structure could I use for modeling a network of nodes and edges?
c++;data structures
Graphs can be implemented in many ways, and the one you've outlined is certainly not wrong. For C++ I think you should take a gander into the Boost C++ libraries (BGL) that also has a library specifically for implementing graphs. If you use that then you can also use algorithms implemented in BGL (searches and traversals) or even use the _edge and _vertex visitors directly.