# Constructing a Graph Class

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

## 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 on other sites
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.

##### Share on other sites
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 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 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 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 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.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 9
• 11
• 9
• 9
• ### Forum Statistics

• Total Topics
634136
• Total Posts
3015757
×