Как хранить графики, чтобы максимизировать локальность для алгоритмов сокращения графов?

Question

Я реализую алгоритм, основанный на правилах сокращения графов. This video объясняет алгоритм лучше, чем мог бы слов, но, ради ЗАВЕРШЕНИЕ, вот быстрое резюме:

Алгоритм работает в графике, где каждый узел имеет 3 ребра, один из которых является «основной» один. Когда основные ребра пересекаются, узел считается активным и применяется правило сокращения. Стоит также отметить, что при взаимодействии двух узлов очень вероятно, что другой узел, очень близкий к ним, станет активным.

В настоящее время я храню этот граф без ощущения локальности: я просто добавляю новые узлы в буфер. Это код для наивных стратегии распределения я использую, в JavaScript прототип:

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; 
}; 

Что превосходный способ организовать этот граф в памяти, чтобы максимизировать локальность и кэш-эффективность для такого графа алгоритм?

Answer 1

Я знаю только два способа «сохранить» график. Под «хранением» я подразумеваю реализацию.

Либо края хранятся в связанном списке для каждого узла, при этом все выгоды от него: добавление и удаление края происходит быстро, но поиск одного длинный.

Либо края хранятся в матрице узлов, а значение массива [node1] [node2] - это вес ребра. Добавление и удаление узла длинное, но поиск узла или ребра происходит быстро.

С помощью метода связанных списков вы храните только то, что существует, с помощью метода матрицы, вы сохраняете каждое ребро, даже если оно не существует, вы должны указать для него значение.