Jump to content
  • Advertisement
Sign in to follow this  
Alpha_ProgDes

Constructing a Graph Class

This topic is 4785 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

ok I've been reading Data Structures for Game Programmers. Now I've gotten to the chapter about Graphs. I disagree with the way he created the Arc and Node classes. They are too dependent on each other. One can't exist without the other. If the author in here, please feel free to make comments. Doing some thinking about it, I've come up with this:
template <typename Data>
class Node {

   Data x, y;  //coordinates of the Node
   bool visited;
};

template <typename Data>
class Arc {

   Node<Data>* node1;
   Node<Data>* node2; //will hold the actual address of the nodes, for traversal
   Data cost;  //I want Data to be either an int or float only... gotta look that up
};
That is what I have so far. The rest of my code is at home. But is this a bad start? What disadvantages would this have over what the author presented (Again, I know it would useful if I posted the code, but I don't have it with me)?

Share this post


Link to post
Share on other sites
Advertisement
Actually it's a learning experience. So it's nothing really game-related. I was using the book because I heard it was easy to read/understand (and it is). But thank you for the Boost suggestion.

Share this post


Link to post
Share on other sites
Has anyone read Data Structures for Game Programmers? Just wanted to see if anyone who read the book feels the same way I do.

Are most graph data structures based on tree data structures?

Share this post


Link to post
Share on other sites
I haven't read the book, but I talked to the author a few times. :-)

Anyway, the primary disadvantage I see with your graph structure is this:
If you're currently visiting a node, how do you get all the arcs that the node is connected to? You can go through the arc list, of course, but that's not very intuitive and can also increase your complexity for a search algorithm (for every node visited, you have to search through every arc to see if there's a connection).

That's just something I saw at a glance. It may not apply to your needs though.

Cheers,
--Brian

Share this post


Link to post
Share on other sites
Good point.
I guess I thought the Graph class would handle through a list of some sort.
I'll have to work on it more this weekend (and a little this week).

thanks.

Share this post


Link to post
Share on other sites
who cares if the arcs and the nodes are interconnected? Afterall, aren't they? In my game I have a graph that consists of nodes and in each node there is a vector of pointers to other nodes. I don't even bother with an arc class. However I am just doing simple stuff with it, no fancy algorithms.

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!