Sign in to follow this  
riruilo

How to store a DAG (scene graph structure) in a binary file (or lineal structure)?

Recommended Posts

Hi dudes. I'm just trying to store the nodes of a DAG (Direct Acicly Graph) in a binary file. How should I traverse my structure to save and load it? My render engine render this structure using a deph first traverse, but I cannot figure out how to store ( and load it after I save it) this structure using a deph first traverse. My question is, is next a good idea? SAVE: 1º store all nodes traversing them using deph first (or any other) but at the same time I store the level of the current node (root is level 0). LOAD: 1º To load nodes, read all them from the file. They are read in a list, so now they don't have their DAG structure. 2º To rebuild the DAG structure, I traverse the list several times using the level value to rebuild them. Is this correct? Do you have any other idea or suggestion? I'm not pretty sure this is the best way, because I cannot rebuild the structure in memory while I'm reading it from the file. (I chose a binary file cause I want performance and speed) Thanks a lot for your help. Ricardo.

Share this post


Link to post
Share on other sites
For each node either store an array of pointers to its children, or store each nodes parent and reconstruct it in reverse.

It's important to realise that the way a graph looks (ie root node at the top) is only like that for aesthetic simplicity, all you have to maintain is the relationships between the nodes in order to reconstruct it.

Share this post


Link to post
Share on other sites
Traverse the DAG depth-first, starting at the bottom. Ignore elements you've already treated. For each new element, associate to that element its index within the buffer and write it. Then, if that element had any chidren, write the index of these children to the buffer (which has already been computed).

When reading the DAG from the file, read all elements in order and store pointers to them in an array (in order of reading). Whenever you encounter an element with children, read the indices of these children and replace them with the corresponding pointers from the array.

Share this post


Link to post
Share on other sites
Quote:
Original post by Dave
For each node either store an array of pointers to its children, or store each nodes parent and reconstruct it in reverse.

It's important to realise that the way a graph looks (ie root node at the top) is only like that for aesthetic simplicity, all you have to maintain is the relationships between the nodes in order to reconstruct it.


Thanks for replies.

I cannot do that because it has no sense to write a pointer (a memory address) to a binary file. However, I guess I could give a name (or id or number) to every node, to do something similar.

What do you think?

Thanks.

Share this post


Link to post
Share on other sites
Or use something like boost::serialization, which handles all the messy pointer manipulation under the hood.

Quote:
Original post by riruilo
I cannot do that because it has no sense to write a pointer (a memory address) to a binary file. However, I guess I could give a name (or id or number) to every node, to do something similar.
Take a look here.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Traverse the DAG depth-first, starting at the bottom. Ignore elements you've already treated. For each new element, associate to that element its index within the buffer and write it. Then, if that element had any chidren, write the index of these children to the buffer (which has already been computed).

When reading the DAG from the file, read all elements in order and store pointers to them in an array (in order of reading). Whenever you encounter an element with children, read the indices of these children and replace them with the corresponding pointers from the array.


When you say index, do you mean the position of the written node?

Thanks.

Share this post


Link to post
Share on other sites
Quote:
Original post by riruilo
When you say index, do you mean the position of the written node?
The index is equal to the number of nodes that have already been written to the file so far.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this