How to save a directed acyclic graph to disk?

Question

So, I have created a directed acyclic graph in c++, now I want to save it to a text file, or maybe files. How do I do that?

P.S: sorry for confusion... I mean to ask how to format the file.

Thanks in advance!

Answer 1

A simple way is to save first all nodes assigning to each of them a node ID, then save all arcs using the node ID of starting and ending node.

This will handle all cases (including non-connected graphs, multiply connected graphs, loops... etc.)

Answer 2

Have a look at graphviz and the 'dot' language for an example of how someone else did it.

Basing your file format on an existing one is always a better idea than inventing your own - often they may have thought of stuff you haven't. And if you stick to the stabdard laguage, there's also lots of links to formats and tools on the graphviz website.

Answer 3

If each vertex in your graph has some kind of ID you can use following structure for your file:

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

Or you can use square matrix to save your graph.

Answer 4

You could create a matrix where the (i,j) entry in the matrix denotes that node i and node j are connected.

To write that to disk, I'd write out the the number of nodes there are, and then write out the matrix line by line. In this way you will be writing out n^2 + 1 numbers to the disk.

However, this approach is inefficient when the graph is sparse (meaning that the number of edges << number of nodes). But it does have a simple serialization structure.