What data structure could I use for modeling a network of nodes and edges?

Question

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:

1. 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.

2. 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.

• Patrick Hughes: Sounds like a fairly standard graph data structure. Boost has a graph along with algorithms to match, and there's a ton of academic and practical data on working with graphs out there.
• S.Lott: Node-Edge graph structures are notoriously hard to model well because either nodes or edges are sufficient. Having both is redundant. Yet. Some queries are better with nodes and some queries are better with edges. There is no pat answer. There is, however, "a ton of academic and practical data". But there can never be a pat answer.

Answer 1

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.

• Mark Taylor: Patrick Hughes also recommended Boost::Graph. I already use Boost for other things, but thought Graph was too much. After a second look I see that it is worth the effort, because after the initial time to implement my graph with Boost then all of the experimenting with different container types and algorithms becomes a matter of passing other type parameters into the Boost templates.

Answer 2

I've implemented network operations in Python. Here is my solution.

• a class Node which owns a list of Ports
• each Port object has attributes destination, proper_direction and back_port
• Node provides linking functions and ensures that for each Port object in its list has another back-port Port object is created at the destination node with the negative proper_direction and also this back-port is referenced by back_port

This way Nodes are linked by a pair of Ports in both directions with reverse proper_directions. Make C-pointers as appropriate - in Python we don't care about pointers ;-)

To store data in each Node I derive a subclass which adds a mapping. If I also want to store data in each Link, then I emulate Links by Node objects, and basically link Objects and Links (both Node) by Ports.

This data structure turned out to be really convenient for network search and operations.