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)?
Constructing a Graph Class
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:
If this is code for a general graph, not a tree, then you should look into the boost graph library. It may seem complicated at first, but it is quite powerful.
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.
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?
Are most graph data structures based on tree data structures?
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
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
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement