将图存储到内存中的最佳方式

问题是，我有150,000个以上的节点，其中200 000+以上（可能不超过1 000 000甚至更多），所有这些节点都被写入数据库。现在我想创建一个可以打开路由访问的正常图形。所以，我需要使用现有数据库中的数据进行撰写。这个想法是构建这个巨大的图形，将它分成小块并写入DB BLOBS进行存储。我试图递归构建它，但在我看来，堆栈不能存储太多的数据，并且所有的时间我的算法都会因分配错误而中断。所以，现在我有点困惑于一种可以让我构建这个图的方式。我在考虑某种迭代方法，但主要问题是架构，我的意思是我将用于存储节点和弧的结构。当我看到这个解决方案应该是史密斯这样的：将图存储到内存中的最佳方式

struct Graph 
{ 
    unsigned int nodesAmount; 
    unsigned int arcsAmount; 
    vector<Node*> NodeArr; //Some kind of container to store all existing Nodes 
} 

struct Node 
{ 
    unsigned int id; 
    int dimension; //how many arcs use this node 
    vector<Arcs*> ArcArr; 
} 

struct Arcs 
{ 
    unsigned int id; 
    double cost; 
    Node* Node_from; 
    Node* Node_to; 
}

我阅读了大量有关存储图形的方法的文章，但没有发现如此巨大的图形好的解决方案。我会很高兴的任何想法。谢谢

来源

2013-11-25 tema

食物的思考：而不是使用链表，可以使用（稀疏？）数组或矩阵。每个节点都有一个id（无符号整数），矩阵可以是一个''。该矩阵表示邻接矩阵：True表示存在从节点x到节点y的弧。 – ibizaman

@ibizaman其实我在想使用矩阵，但它看起来很庞大，有很多零。这就是为什么我正在寻找另一种方式 – tema

这就是稀疏矩阵到位的原因。它只存储非零值。顺便提一下Danstahr的回答是更好地考虑空间使用情况。 – ibizaman

你走在正确的道路上。

一些小的变化，我会建议：

struct Graph 
{ 
    unsigned int nodesAmount; 
    unsigned int arcsAmount; 
    vector<Node> NodeArr; // Store the nodes directly, not pointers 
} 

struct Node 
{ 
    unsigned int id; 
    int dimension; //how many arcs use this node 
    vector<int> Neighbours; // store neighbour IDs, saves memory 
}

由于您的数据库和C之间移动，我会强烈建议不要使用指针，因为那些没有翻译。使用ID并通过ID查找您的节点。如果你需要分别存储边缘，那么也可以通过ID来完成，而不是通过指针。

来源

2013-11-25 16:04:15

@ Segey-l听起来不错，但我会实现路由抛出这个图表，所以我需要以某种方式存储每个弧的成本。 – tema

@ tema.krukovets然后使它成为'struct {int neighbourID;双倍的成本;}' –

我知道这个解决方案与您的代码片段无关，但我想以另一种方式向您展示。

经常使用的选项是有两个数组 - 一个用于边，一个用于顶点。

顶点数组指向边数组，并指出相邻顶点的起点。边数组存储相邻的顶点本身。

例如：

V = 6, E = 7 

vertices = [0, 1, 1, 2, 5, 6] 
edges = [1, 2, 3, 4, 5, 6, 0]

考虑到索引，边缘阵列看起来像：

| [1] | [] | [2] | [3, 4, 5] | [6] | [0] |

所以第一顶点具有单一邻近的顶点（编号为1），第五顶点有3个相邻的顶点，ID为3,4,5等。

来源

2013-11-25 16:07:12 Danstahr

非常感谢您的回答） – tema

将图存储到内存中的最佳方式

回答

相关问题