The best way to store graph into the memory

architecture, c++, database, graph

Solution

You are on the right path.

Some small changes that I would suggest:

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
}

Since you are moving between database and C I would strongly suggest not to use pointers because those do not translate. Use IDs and look up your nodes by ID. If you need to store the edges separately then also do this by ID, not by pointer.

Problem

The problem is that I have 150 000+ nodes with 200 000+ (may vary up to 1 000 000 or even more) all of them are written to a DB. Now I'd like to create a normal graph which will open access to routing. So, I need to compose it using data from existing DB. The idea is to build this huge graph, divide it into small pieces and write to DB BLOBS for storing. I tried to build it recursively but it seems to me that stack could't store so much data and all the time my algorithm breaks with allocation error. So, now I'm a bit confused with a way which will allow me to build this graph. I'm thinking about some kind of iterative method, but the main problem is architecture, I mean structures which I'm going to use for storing nodes and arcs. As I see this solution it should be smith like that: ``` 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; } ``` I read lots of articles about method of storing graphs, but didn't find really good solution for such huge graphs. I would be very pleased for any ideas. Thank you

Original source