Jump to content
  • Advertisement
Sign in to follow this  
shaobohou

a sensible representation of directed graph?

This topic is 4408 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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. ]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!