将图形存储到内存中的最佳方法

Question

问题是我有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;
}

我阅读了很多关于存储图形方法的文章,但没有找到真正好的解决方案.任何想法我都会很高兴.谢谢

Answer 1

你是在正确的道路上.

我建议的一些小改动:

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
}

由于您在数据库和CI之间移动,因此强烈建议不要使用指针,因为这些指针不会转换.使用ID并按ID查找节点.如果您需要单独存储边缘,那么也可以通过ID而不是指针来完成.