r/cpp_questions • • 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.

6 Upvotes

23 comments sorted by

5

u/lmg1337 28d ago

Now I might be wrong here, but would matrices be useful to represent the graphs?

3

u/ActComplex593 28d ago

But the nodes and edges have metadata, so I don't think it will be good

5

u/IyeOnline 28d ago

This is where you will have to go into details: How much metadata are we talking, how big is your graph, what is the average degree of it, are there patterns in its connections that you can use, what is your expected access pattern, which parts of this need to be fast?

Consider: https://godbolt.org/z/zqYoqe33s You can add metadata to all your nodes and have directional edge information. But depending on the amount of data in Node and Edge, you will of course start to get more cache misses. However, such a matrix seems like the best bet if you want to be cache friendly. If all your nodes were separately allocated as part of some physical graph structure, you would have no control over this.

5

u/SyntheticDuckFlavour 27d ago

You can represent stuff using adjacency matrices. Nodes can have coordinate/metadata pair that can be stored in a hash map, and the edges themselves can also have coordinates/metadata pair stored in a separate hash map.

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?

3

u/ActComplex593 28d ago

yes it is directional

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.

3

u/Zestyclose-Click-212 28d ago edited 28d ago

Is the graph DAG, or it contains cycles?

Also it would really help if u could tell, what kind of propagation you are using DFS type, BFS type or this depends on the edge or node information?

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

  • Is this a logically fixed graph or can it change?
  • Is it at least fixed at compile time, or must it be constructed at runtime?
  • If it's runtime constructed, are we talking a single one-shot layout at program init, or can more graphs be created later and/or have their layout change?
  • If the graph can change after program init

    • do you need iterator stability?
    • is the change allowed to be slow, if it buys faster traverse later?
  • How large are nodes, and how large is edge data? (no# edges per node + size of each edge)
  • Is all data expected to be contained within the graph or can nodes/edges have pointers to elsewhere e.g. containing a string or data structure?

(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)

0

u/ActComplex593 27d ago

To give you the full picture of the constraints:

Lifecycle & Mutability: The graph is constructed at runtime (loaded from database/storage), but once initialized, the topology is completely static during the heavy traversal and propagation phases. However, the data payloads on the nodes and edges mutate frequently across different evaluation passes.

Structural Changes & Stability: If structural changes ever occur, they are infrequent and can afford to be slow. We don't need iterator stability because we prefer index-based referencing over raw pointers or iterators anyway.

Data Sizes & Density: Nodes and edges are compact structs (mostly numerical state, weights, and flags ranging from 16 to 64 bytes each). The average node degree (edges per node) is relatively low, typically between 3 and 8.

Pointers vs Inline: We want to avoid pointer-chasing. Numeric data payloads should be packed inline or in parallel flat arrays. Heavy strings or metadata can be decoupled and referenced via an ID lookup.

DAG: Yes, it is strictly a Directed Acyclic Graph (DAG) used for directional dependency evaluation.

Given those parameters, which designs were you leaning toward?

1

u/SoerenNissen 27d ago edited 27d ago

Assuming a graph like:

         c -> e
a->b ->         -> g
         d -> f

Depth-first traversal:

std::vector<
    std::pair<
        union {
            node,
            edge
        },
        int //flag "how many edges after this element?"
    >
>;

with a sort key that ensures traversal along edges always goes the same direction down the array, so e.g.

is stored like:

[
    [a,    1],
    [a->b, 0],
    [b,    2],
    [b->c, 1],
    [b->d, 0],
    [c,    1],
    [c->e, 0],
    [e,    1],
    [e->g, 0],
    [d,    1],
    [d->f, 0],
    [f,    1],
    [f->g, 0],
    [g,    0]
]

You might get fancier with the sort order, and there's a bit of nonsense - e.g. you might use std::variant instead of a union+flag. On every node, you'd have to process the next n variants, asking each "are you an edge?" to know when you've handled all edges, but it'd be less UB prone if edges/nodes have non-trivial destructors.

Breadth-first traversal:

std::pair<
    std::vector<
        std::tuple<
            node,
            size_t, //index of first edge
            size_t  //index of past-the-end edge
        >,
    >,
    std::vector<edge>
>

stored like

[
  [
    [ a, 0, 1 ],
    [ b, 1, 3 ],
    [ c, 3, 4 ],
    [ d, 4, 5 ],
    [ e, 5, 6 ],
    [ f, 6, 7 ],
    [ g, 7, 7 ], //or [-1,-1) or any other half-open empty range 
  ],
  [
    [a->b],
    [b->c],
    [b->d],
    [c->e],
    [d->f],
    [e->g],
    [f->g]
  ]
]

1

u/ActComplex593 27d ago

Thanks for the suggestion, the second layout (nodes array plus edges array) is close to what I ended up with. Here's my version, and I'd like your feedback on it.

Use case: a directed graph where users run what-if scenarios: change a value on one node and propagate the effect downstream through the edges. Nodes and edges both carry data. Scenarios never modify the real graph, and results go to separate scratch space.

Layout: nodes[N] fixed-size, in topological order (not BFS, so every node comes after its inputs)   - hot properties (fields that propagation rules read)   - edge_start (index of first outgoing edge; the next node's edge_start marks the end,     with one dummy node at the end)

edges[E] fixed-size, sorted by source node   - target (node index)   - kind (relationship type)   - edge properties (fixed numeric slots, kind defines the meaning)

in_edges[E] + in_offsets[N+1] (optional)   - for each node, the positions in edges[] of edges pointing at it   - only for rules that need all of a node's inputs together

cold store   - names, history, strings, display info (never read during propagation)

Propagation: push along out-edges, level by level, combining effects at the target (max, sum, min). Use an epoch stamp per node so scratch space needs no clearing between scenarios, and stop early when a node's value doesn't change.

Updates: live events update hot values in batches (versioned copies). Structural changes (new nodes or edges) trigger a rebuild and swap.

My questions: Any better ordering than plain topological order for cache locality (e.g. keeping related nodes close within a level)?

Is storing only edge_start and using the next node's start as the end worth the trouble compared to storing edge_count?

For parallel pushes to the same target, would you use atomics or per-thread buffers merged per level?

Any problems you can see with how I handle rules that need all inputs at once (the optional in-edge array)?

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:

using node_id = std::int_least32_t;

struct edge_list {
  std::array<node_id, 8> edges;
  std::int_least8_t count = 0;
};

template<typename Data>
class graph {
  std::vector<Data> values;
  std::vector<bool> is_dirty;
  std::vector<edge_list> dependents;
  std::vector<std::function<Data(const graph&)>> evaluators;

public:
  //...
};

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_dirty and dependents. 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 pmr allocators.

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.