Implementation Detail for Graph Analysis Algorithms

Question

Let's say I have a graph with "heavy" nodes, that is each node is an object that is already carrying a lot of data. I want to do a graph transformation that requires me to calculate a special property for each node. This property only needs to be remembered temporarily to apply the transformation. How can I store this property efficiently?

Adding a special_property field to each node seems like a waste as I only need to remember it for a short time. Another possibility is to create a "shadow" graph, which is a graph that has the exact same connections as the original one and only storing the special_property though this seems unwieldy.

What is a generally acceptable way to tackle this problem?

Answer 1

The "heavy" objects should not be the actual nodes in the graph. Each node in the graph should have a pointer to the "heavy" object it represents and whatever other attributes you need when operating on the graph.

Answer 2

Each node should have a small integer identifier. Use it as an index to store the properties in a temporary array. Besides O(1) access time, an array also has great data locality for the processor cache.

Answer 3

Check out Boost library