title: How to store graphs in order to maximize locality for graph-reduction algorithms?
body: <p>I'm implementing an algorithm based on graph-reduction rules. <a href="https://www.youtube.com/watch?v=lhNtgbFTXFE&amp;feature=youtu.be" rel="nofollow">This video</a> explains the algorithm better than words could, but, for completion's sake, here's a quick summary: </p>
  
  <blockquote>
    <p>The algorithm operates in a graph where every node has 3 edges, one of which is the "main" one. When main edges intersect, a node is said to be active and a reduction rule is applied. It is also worth noting that, when two nodes interact, it is very likely that another node very close to them will become active. </p>
  </blockquote>
  
  <p>I'm currently storing this graph with no sense of locality whatsoever: I just append new nodes to a buffer. This is the code for the naive allocation strategy I'm using, prototyped in JavaScript:</p>
  
  <pre><code>function Node(type,tag){
      var idx = garbage.pop() || memory.length;
      memory[idx+0] = type;      // Node type (used on readback)
      memory[idx+1] = 0;         // Port 0 target port
      memory[idx+2] = 0;         // Port 1 target port
      memory[idx+3] = 0;         // Port 2 target port
      memory[idx+4] = 0;         // Port 0 target node
      memory[idx+5] = 0;         // Port 1 target node
      memory[idx+6] = 0;         // Port 2 target node
      memory[idx+7] = ++next_id; // Unique id
      memory[idx+8] = tag;       // Tag (used to decide which reduction rule apply)
      return idx;
  };
  </code></pre>
  
  <p>What is a superior way to organize this graph in memory in order to maximize locality and cache-efficiency for that kind of graph algorithm?</p>