- Forum
- General C++ Programming
- What is the best strategy for implementi
What is the best strategy for implementing this "weird" kind of graph in C++?
Hi.
I'm wondering about this. I've got this problem: how can one implement this "weird" kind of graph in C++? Now, what do I mean by that, first? The answer is that a "weird" graph is like a normal node/edge graph except there's a third level of organization: node "strings". That is, we imagine the graph to be a bunch of long linear chains of nodes with cross-linkages between them. (What is this for? The answer is to represent a "web" of levels in a game: the nodes are levels and the edges represent connections between the levels, but I also want to have levels grouped together in linear "strings".) What is the best way to go about this? On one forum I heard that one could implement it on top of a conventional graph. What would be the best way to do that?
I'm wondering about this. I've got this problem: how can one implement this "weird" kind of graph in C++? Now, what do I mean by that, first? The answer is that a "weird" graph is like a normal node/edge graph except there's a third level of organization: node "strings". That is, we imagine the graph to be a bunch of long linear chains of nodes with cross-linkages between them. (What is this for? The answer is to represent a "web" of levels in a game: the nodes are levels and the edges represent connections between the levels, but I also want to have levels grouped together in linear "strings".) What is the best way to go about this? On one forum I heard that one could implement it on top of a conventional graph. What would be the best way to do that?
If you tried to explain the data structure more clearly, you may even come up with an answer yourself.
What would be a clearer explanation? There are 3 things in the structure:
1. Nodes
2. Edges
3. "Strings"
All nodes belong to strings. Each string is a linear sequence of nodes, such that any element is connected to the previous and next by an edge and can be referenced by an index (e.g. node 1, node 2, etc. of the string which correspond to their positions in the string's linear order.). Other edges can connect strings together. Does this help?
The node/edge part I know can be represented with a conventional graph. It's the overlaying of the string structure on top where I have the questions. It'd be nice to be able to build it on top of a conventional graph implementation somehow. That way, I could use something like Boost to provide the underlying graph stuff.
1. Nodes
2. Edges
3. "Strings"
All nodes belong to strings. Each string is a linear sequence of nodes, such that any element is connected to the previous and next by an edge and can be referenced by an index (e.g. node 1, node 2, etc. of the string which correspond to their positions in the string's linear order.). Other edges can connect strings together. Does this help?
The node/edge part I know can be represented with a conventional graph. It's the overlaying of the string structure on top where I have the questions. It'd be nice to be able to build it on top of a conventional graph implementation somehow. That way, I could use something like Boost to provide the underlying graph stuff.
Last edited on
I would just build a normal graph (each node has it's own data and pointers to other nodes as needed) and then just have several vectors containing whatever nodes you want for the "strings".
Well, I guess I'm on the right track with that part, then. In the current system, the "strings" are represented by a private class inside the "funny graph" class. But I've run into some troubles and have some questions about this approach (which was also suggested on the other forum mentioned):
1. first and foremost, there is a big problem with regards to iterator invalidation: the iterators kept in the "string" class's list, which point to the nodes comprising the string, are invalidated upon removing a node due to the way the graph implementation works. So what is the best way to keep track of the nodes so as to reset the iterators when needed (e.g. after removing a string)? Right now I use the string's user-specified ID code, which is also used to identify the string in the funny graph for accessing purposes. The funny graph keeps these user-specified IDs unique by keeping track of which ones have already been used. But what's the best way to do this?
2. related to the above, is it a good idea to have it so that each "string" object needs to be updated when nodes are removed from the graph, e.g. when deleting a "string" object? That is, all the rest need to be updated, which means we need to have access to all of them that are present at the time of delete. The way it's set up, this is possible (since the only ones we have are in an array), but it feels "iffy".
3. is it a good idea to remove nodes in the private string class's destructor, as that makes it bad to pass one of those string objects by value? Not that they need to be, but to me it feels "iffy".
1. first and foremost, there is a big problem with regards to iterator invalidation: the iterators kept in the "string" class's list, which point to the nodes comprising the string, are invalidated upon removing a node due to the way the graph implementation works. So what is the best way to keep track of the nodes so as to reset the iterators when needed (e.g. after removing a string)? Right now I use the string's user-specified ID code, which is also used to identify the string in the funny graph for accessing purposes. The funny graph keeps these user-specified IDs unique by keeping track of which ones have already been used. But what's the best way to do this?
2. related to the above, is it a good idea to have it so that each "string" object needs to be updated when nodes are removed from the graph, e.g. when deleting a "string" object? That is, all the rest need to be updated, which means we need to have access to all of them that are present at the time of delete. The way it's set up, this is possible (since the only ones we have are in an array), but it feels "iffy".
3. is it a good idea to remove nodes in the private string class's destructor, as that makes it bad to pass one of those string objects by value? Not that they need to be, but to me it feels "iffy".
I'd think you'd need some kind of callback to notify the strings that have nodes. So each node might maintain a list of strings that reference it and it notifies them of interesting changes like deletion.
I think it's a reasonable idea to keep the two things in sync as it's really one data structure. As long as you have a single interface into the whole thing, it should be ok.
I think it's a reasonable idea to keep the two things in sync as it's really one data structure. As long as you have a single interface into the whole thing, it should be ok.
But that would seem to require adding extra functionality to the graph. Also, that would seem to trigger an update on every delete of a single node, which would add a ton of cost to deleting a whole string. Though that last bit may not be so bad since strings, even nodes, aren't deleted so often.
Last edited on
For your problem 1, try using a list instead of a vector. The iterators for the levels will keep valid upon deletion of a level(except of course the ones pointing at the deleted level).
That would seem to be the best approach, however I was wondering whether there was a way to do it _with_ invalidating iterators that would address the concerns I mentioned. Is there? Or are these problems an inevitable result of using invalidating iterators?
Last edited on
@kbw: "I'd think you'd need some kind of callback to notify the strings that have nodes. So each node might maintain a list of strings that reference it and it notifies them of interesting changes like deletion."
Wouldn't that require modification to the graph class itself, though? (To do that "notification")
Wouldn't that require modification to the graph class itself, though? (To do that "notification")
Last edited on
| Wouldn't that require modification to the graph class itself, though? |
@kbw: But the way this is implemented is that there is a graph type, and the "funny graph" includes a field of that type.
Also, keeping a "list of strings that reference the node" wouldn't work, since a delete invalidates ALL strings' iterators.
How about putting the whole thing in one graph, strings and all.
You could follow a string by using edge labels.
One data structure, no synchronization problems?
You could follow a string by using edge labels.
One data structure, no synchronization problems?
So then, put a copy of the string data on every edge connecting the string's nodes? And have no separate "string" storage structure at all? But then how do you access a given string? Don't you need an expensive search of the graph's edges?
You would need to search edges emanating from a node to see which is the next node for the string iterator to visit.
You would need a graph representation that allows you do do that without searching all the graph edges.
Do you have 5 or 5,000 edges emanating from each node?
You would need a graph representation that allows you do do that without searching all the graph edges.
Do you have 5 or 5,000 edges emanating from each node?
More like 5 than 5,000. Actually, most nodes have 4. But all this searching sounds like a lot of expense, and it also looks like we need to search just to find the _starting_ node of a requested string. And using a different kind of graph class goes against the idea of just using a "standard" graph.
Topic archived. No new replies allowed.