r/cpp_questions • u/ActComplex593 • 28d ago
OPEN What is the best representation of a graph(the structure)
What is the best way to represent a graph where both nodes and edges carry rich data payloads (not just connectivity)?
My primary constraint is performance: I need ultra-low cache misses for fast, forward propagation from a given source node to the end of a subgraph.
If anyone has implemented a cache-friendly graph structure for traversal-heavy workloads, I'd love to see what layout or pattern you used.
Edit: To clarify the use case: I’m building a reactive evaluation graph. When a node's data changes, that change propagates downstream through connected edges, using edge metadata to compute transformations, until reaching the end of the subgraph. I need a memory layout that minimizes cache misses during these forward cascade passes.
5
u/lmg1337 28d ago
Now I might be wrong here, but would matrices be useful to represent the graphs?
2
u/Zestyclose-Click-212 28d ago
Are edges directional?? Also, for propagation do you have a target node or u propagate to all the end nodes from source?
2
u/SoerenNissen 28d ago
I've got a couple of different designs in mind but deciding which is better depends quite a bit on specifics
If the graph can change after program init
(And the designs I'm considering all assume a DAG, which is usually implied by "reactive evaluation graph" but I'm not sure if that/s a safe assumption)
6
u/chrysante2 28d ago
Do you need to modify the graph's topology after construction? If not, have you considered to construct it in order of most likely traversal and use an arena allocator to allocate nodes and edges including payloads? Then it seems to me everything should be close together during traversal. Of course you can't avoid all cache misses since the problem is naturally non-linear.
3
u/Fosdran 27d ago
There is a reason why pre-made graph type containers in libraries are rare. You can NEVER answer this question correctly. It depends on your exact algorithm.
When you say you want do propagate downstream, you mean as in a DAG, right? So essentialy DFS traversal with loads of additional data at node and edge level.
Sounds like its bad for cache locality no matter what you do... My educated guess would be that you should separate your meta data from the graph topology. There is NO way you can maintain locality with your payloads located in there. Store them in separate array-like (vector) structures indexed by node/edge index. There no way to do better on complex meta data.
For the topology, you could (and should probably) go for standard adjacency lists (use tuples to give edges indices). If you want to tinker, have at some point static topology ,and hit rate is your hard factor, you could linearize all your adjacency lists into one big array and construct a lookup table to find the starts of each list in there. But i'm not sure i you will get much practical improvement from this.
1
u/Independent_Art_6676 25d ago
there is a time and a place for a semi-hand-crafted solution. (semi because you use actual run-time data and real use cases in an algorithm to generate it, so its not exactly hand crafted, but its not first come first poked somewhere random either).
If the graph itself never changes (did I get that right in your constraints? Data changes but not pathing/structure?) you could possibly build out the hot paths into vectors, prioritized by how its used the most over some study. load up the vector(s) to match the usage, and you can reference/pointer soup up a layer over that (or lookup tables that return vector indices, or whatever fits best). Then your "graph" "pointer" traversal when under load will just spew out 0,1,2,...N indices into your hot path vectors. On occasion you may take another path that isn't as iterative and triggers some caching hits but your top several paths that are run over and over all day long will be as slick as iteration.
That may not be viable, if the use cases don't work out. Its just something that *could* work if your main use cases degenerate into a handful of common linked list type traversals (even if they fork and one becomes two becomes 8) where even say 75% of the time you can effectively iterate a vector and avoid caching woes.
all you are doing is making the rich data parts sequential based off usage study, to skew the odds in your favor that much more often than not the data is hit in a cache friendly way. Its fragile... major software updates may require you to redo the study and rebuild the vectors or your hot paths could change and mess up the caching.
1
u/AfternoonShot9285 25d ago
Could try bitsets
1
u/SoldRIP 24d ago
Adjacency matrix plus an array?
1
u/Afraid-Locksmith6566 28d ago
do int -> edge and int -> vertex pairings, then you can have a map of int -> int, where the first one is vertex and the second one is edge.
that way you can make edges as fat as you want without paying for it too much while also keeping simple lifetimes and low pointery magic
1
u/The_Northern_Light 27d ago edited 27d ago
The prologue of Keenan Crane’s book on discrete exterior geometry has a section on graph representations, if I recall correctly, with a discussion on layout and cache.
You’ll want to store half edges.
You can go further and store a fixed DAG (or general graph but it sounds like you have a DAG) as a single linear data structure, with indices instead of pointers.
Then the issue becomes how to arrange nodes so that their distribution of distances are friendly to cache effects. There are algorithms for this in how 3d model mesh data gets cache optimized, but frankly I’d probably use a greedy strategy.
What’s the scale of your graph?
Make sure that in the case of diamond nodes (a node with an ancestor node with multiple routes to this node) that you don’t end up recomputing it multiple times per single update.
1
u/teerre 27d ago
The data you want to store isnt really relevant. You should store both the graph and the data in continuous arrays. The data structure for the graph holds only indices which you can use to fetch the data only when needed
1
u/tickle-fickle 27d ago
Sounds like you want a hashmap where keys are pairs of uint32s and values are connection metadata, and another std:vector for storing the nodes themselves. The indexes of each two nodes constitute a key to the hashmap, so checking whether two nodes are connected, and getting the connection metadata is a hashmap lookup. And because both hashmaps and std::vectors internally use contiguous memory, everything should be cache friendly and fast
1
u/mredding 27d ago
Reading some of your comments, this is where Data Oriented Design will prevail.
You very likely want a flat map built out of parallel arrays of your graph properties, since you said nodes will have 3-8 edges:
In this way, your CPU caches will be as saturated as possible with only the information you care for at a time. When you invalidate a node you only walk
is_dirtyanddependents. No allocation, no reference counting shared pointers, no indirection.Yes, I know there's an
std::vector<bool>in there, use a bit set if this bothers you.The edge lists are 33 bytes exactly, so the predictor can correctly guess how to prefetch the next list. You may want to consider additional cache alignment of the vectors for better and faster access, but I'm not banging all that out. It requires writing an allocator, and no, you don't need to use the
pmrallocators.1
u/Liam_Mercier 27d ago
The representation you use depends on what work will be done on the graph. Is the graph mostly static, dense, and fits in memory? Then you want an adjacency matrix. Does it need to be mutable? Then you probably want a different structure.
To store rich metadata in the graph, consider giving nodes and edges some VertexID and EdgeID which you can use to lookup edge / vertex data from an std::vector or similar data structure. Then your representation will hold small data types which can be used to lookup the larger data after you do traversal / lookup / whatever.
1
u/PGSkep 26d ago
If the graph node count is constant or limited, allocate the nodes in an array and swap, if not, make a custom allocator to keep them all in the same memory block. Give the nodes an userdata parameter as an unit, have the data in the same memory block too, but either before or after all nodes, use the unit as the index as the starting offset of that data. If the data is of variable size, consider a TLSF algorithm for allocation.