Лучший способ хранения графика в памяти

Проблема в том, что у меня 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

Вот где разреженная матрица приходит на свои места. Он сохраняет только ненулевые значения. Кстати, ответ Дэнстагра лучше учитывает использование пространства. – 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. Если вам нужно сохранить края отдельно, то также сделать это по идентификатору, а не по указателю.

источник

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 смежные вершины с идентификаторами 3, 4, 5 и т. д.

источник

2013-11-25 16:07:12 Danstahr

Большое спасибо за ваш ответ) – tema

Лучший способ хранения графика в памяти

ответ

Смежные вопросы