c++ - 将图形存储到内存中的最佳方式

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
}

由于您在数据库和 C 之间移动，我强烈建议不要使用指针，因为它们不会转换。使用 ID 并按 ID 查找您的节点。如果您需要单独存储边缘，那么也可以通过 ID 而不是指针来执行此操作。