Как сохранить ориентированный ациклический граф на диск?

Question

Итак, я создал ориентированный ациклический граф на С ++, теперь я хочу сохранить его в текстовом файле или, возможно, в файлах. Как мне это сделать?

P.S: извините за путаницу ... Я хочу спросить, как отформатировать файл.

Заранее спасибо!

Answer 1

Простой способ - сначала сохранить все узлы, присваивая каждому из них идентификатор узла, а затем сохранить все дуги, используя идентификатор узла начального и конечного узла.

Это будет обрабатывать все случаи (включая несвязанные графы, многосвязные графы, циклы и т. Д.)

Answer 2

Посмотрите на graphviz и язык 'точка', чтобы узнать, как это сделал кто-то другой.

Основывать формат файла на существующем - всегда лучшая идея, чем придумывать собственный - часто они могут подумать о том, чего у вас нет. И если вы будете придерживаться языковой нормы, на сайте Graphviz также есть много ссылок на форматы и инструменты.

Answer 3

Если каждая вершина в вашем графе имеет какой-то идентификатор, вы можете использовать следующую структуру для вашего файла:

<num vertexes>
1 <num neighbors> <neighbor ID> ... <neighbor ID>
...
N <num neighbors> <neighbor ID> ... <neighbor ID>

Или вы можете использовать квадратную матрицу для сохранения графика.

Answer 4

Вы можете создать матрицу, в которой запись (i, j) в матрице означает, что узел i и узел j соединены.

Чтобы записать это на диск, я бы записал количество имеющихся узлов, а затем вывел матрицу построчно. Таким образом, вы будете записывать на диск n ^ 2 + 1 цифр.

Однако этот подход неэффективен, когда граф разрежен (это означает, что число ребер << количество узлов). Но он имеет простую структуру сериализации. </p>