首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >图约简算法如何以最大局部性的方式存储图?

问图约简算法如何以最大局部性的方式存储图?
EN

Stack Overflow用户
提问于 2015-08-12 03:33:01
回答 1查看 270关注 0票数 2

我正在实现一个基于图约简规则的算法。这段视频比文字更好地解释了算法,但是,为了完成任务,下面是一个简短的总结:

该算法工作在一个图中,每个节点都有三个边,其中一个是“主”边。当主边缘相交时,节点被认为是活动的,并且应用了约简规则。还值得注意的是,当两个节点交互时,非常接近它们的另一个节点很可能会成为活动节点。

我目前正在存储这个图,完全没有局部性:我只是在缓冲区中添加新的节点。这是我使用的朴素分配策略的代码,在JavaScript中是原型的:

代码语言: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;
};

为了最大限度地提高这种图形算法的局部性和缓存效率,在内存中组织这个图的最佳方法是什么?

EN

回答 1

Stack Overflow用户

发布于 2015-08-12 12:27:25

我只知道两种“存储”图形的方法。所谓“存储”,我指的是实现。

任何一个边都存储在每个节点的链接列表中,其中的所有优点是:添加和删除边是快速的,但是找到一个边是很长的。

或者边存储在节点矩阵中,而Arraynode1的值是边的权重。添加和删除一个节点是很长的,但是找到一个节点或边缘是快速的。

使用链接列表方法,您只存储存在的内容,使用矩阵方法,您存储每个边,即使它不存在,您必须为它提供一个值。

票数 -1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/31955567

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档