a sensible representation of directed graph?
Author
Hi,
I wanted to get rid of pointers in my representation of directed graph or tree structure to avoid any issues related to memory management and copying. Primarily, I will be using these structures to represent mesh connectivity information and structure of scene graph.
To this end, instead of storing pointers to children/parent nodes, each node stores indices into an array/vector/map of nodes stored in a top level class representing the graph/tree. I suspect this will make the code a bit slower but I not sure how much, perhaps someone else can point me to some benchmark results or tests.
Overall, is this a sensible representation?
Shaobo
What you're describing is unswizzled references. There's no problem with it as long as your data structure is random access (so std::map would be a bad idea). Speed should be comparable.
Author
Quote:Original post by Sneftel
What you're describing is unswizzled references. There's no problem with it as long as your data structure is random access (so std::map would be a bad idea). Speed should be comparable.
Ah, I suspect it had a name, I just didn't know what it was. I assume this is what you are referring to, http://en.wikipedia.org/wiki/Pointer_swizzling.
I only used std::map for a very specific case, I am not sure how it implements its accessor or find method (brute force search?), would a hash_map be more appropriate?
Shaobo
std::vector would be most appropriate. std::hash_map doesn't provide random access by index.
hmmm...as with every post on a forum take this with a grain of salt.
I usually have a manager class that keeps a dynamic list of all the objects in the graph. Each object is given a unique key (unsigned int) and the manager keeps its object list sorted from low key to high key, yeah...it's basically a map.
Instead of object pointers, handles (keys) are used. So when you create objectX the manager gives you handleX. When you want to do something with objectX you pass the manager handleX and it passes back a pointer to objectX. Right, right, so how is this not just a map minus the stl?
The handles are actually structures, they contain an unsigned int for the key value and an additional unsigned int for the purposes of caching the object index within the manager's list. So when you pass handleX to the manager it first checks if the index given with the handle yields an object with an equal key value, if it does then all is well and that object is returned; if it doesn't then the manager does your standard log(n) search on the sorted list of objects, changes the handle's index when the object is found and return a pointer to the object.
What's the point? Well you can build a lot of functionality into the object manager such as reference counting, memory management, and the like. I like this approach for a number of reasons the primary two being:
1) Say you have a chair mesh, and ten rooms that contain that chair. The
object manager can give a handle to the chair to all the rooms. Now, if the
chair in roomA gets destroyed then roomA tells the manager that it's done
using the chair but the manager won't delete the chair mesh until all of
chair handles that have been given out are given back.
2) Your resources are all centralized so you can record access patterns and
manage memory accordingly. Also, the dreaded device recreation problem
can be solved fairly easily (this applies to DirectX). When the device
goes into a lost state and is subsequently recreated you simply have the
manager tell all of its objects to rebuild their hardware interfaces, and
it's as simple as that. You don't need to reload the level or restart the
game or anything absurd like that.
And remember, your particular situation may be unsuited for such things
...always with a grain of salt.
[ Edit: I was the first kid out in every spelling bee I was ever in. ]
I usually have a manager class that keeps a dynamic list of all the objects in the graph. Each object is given a unique key (unsigned int) and the manager keeps its object list sorted from low key to high key, yeah...it's basically a map.
Instead of object pointers, handles (keys) are used. So when you create objectX the manager gives you handleX. When you want to do something with objectX you pass the manager handleX and it passes back a pointer to objectX. Right, right, so how is this not just a map minus the stl?
The handles are actually structures, they contain an unsigned int for the key value and an additional unsigned int for the purposes of caching the object index within the manager's list. So when you pass handleX to the manager it first checks if the index given with the handle yields an object with an equal key value, if it does then all is well and that object is returned; if it doesn't then the manager does your standard log(n) search on the sorted list of objects, changes the handle's index when the object is found and return a pointer to the object.
What's the point? Well you can build a lot of functionality into the object manager such as reference counting, memory management, and the like. I like this approach for a number of reasons the primary two being:
1) Say you have a chair mesh, and ten rooms that contain that chair. The
object manager can give a handle to the chair to all the rooms. Now, if the
chair in roomA gets destroyed then roomA tells the manager that it's done
using the chair but the manager won't delete the chair mesh until all of
chair handles that have been given out are given back.
2) Your resources are all centralized so you can record access patterns and
manage memory accordingly. Also, the dreaded device recreation problem
can be solved fairly easily (this applies to DirectX). When the device
goes into a lost state and is subsequently recreated you simply have the
manager tell all of its objects to rebuild their hardware interfaces, and
it's as simple as that. You don't need to reload the level or restart the
game or anything absurd like that.
And remember, your particular situation may be unsuited for such things
...always with a grain of salt.
[ Edit: I was the first kid out in every spelling bee I was ever in. ]
Author
that is probably a little more involved than what I was considering at the moment, but I never thought about the access pattern bit, that could be very useful.
Guess I should go find an stl book and look up how std::map and std::hash_map accessor are implemented. The reason I used std::map in a particular instance is to avoid updating internal indices when trees are merged with each other, maybe I should rewrite it if it proves to be computatinally costly.
Guess I should go find an stl book and look up how std::map and std::hash_map accessor are implemented. The reason I used std::map in a particular instance is to avoid updating internal indices when trees are merged with each other, maybe I should rewrite it if it proves to be computatinally costly.
maybe you stick with pointers, but use an array of nodes at the same time, for faster allocation/construction of new nodes, and memory managment?
Author
possibly, tho it does mean that each node will need to know its position in the array anyway, so deep copy can be easily performed
Just as an added tip: I am currently using boost to represent my directed graph: http://www.boost.org/libs/graph/doc/
As with everything, there was a learning curve, but it is very flexible for representing all kinds of graphs.
As with everything, there was a learning curve, but it is very flexible for representing all kinds of graphs.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
