Public Group

algorithmicly connecting a graph

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

Recommended Posts

Hello everyone,

I can't quite wrap my head around this problem so I need a little help please.

Give a map represented by a std::vector<int> map that might look like this...

0 0 0 0 1 0

0 0 0 0 1 0

1 0 1 1 1 0

0 0 0 0 1 0

where '1' is an obstacle and '0' is a free moving space, and where the distances between the

values are arbitrary.

I would like the following,

one std::vector<Node> nodes;

two std::vector<Edge> edges;

I know potentially, that every 'node' in my graph (that being a 0) can have 8 possible edges.

What I don't know however, is how to iterate over my graph, and keep track of which edges have been already created.

For example, map[0] will have 3 edges to each of its neighbours. Now, when I move to map[1], and create the edges to its neighbours, how do I check, or keep track of, whether map[0] already has an edge to map[1].

Thanks,

Mike

Share on other sites
Just look into the container of edges while you're building it. If it already contains a matching edge, don't add a new copy.

Share on other sites

Is duplication that big of an issue?  Otherwise, I consider it a feature.  Take a node where the edge is actually the actor hopping down a cliff face, or entering a one-way teleporter, etc.  Or even going up vs. down a ladder.  Having separate edges for going from 0-->1 and 1-->0 means you can cost them out differently.

Share on other sites

My only concern with that is as the map gets bigger, the duplication checks are going to grow very quickly.

Share on other sites
You can store edges in an associative container instead of a vector to mitigate that. For example if you have:

std::multimap<EdgeID, std::pair<SourceNodeID, TargetNodeID>>
You can hold both one-way edges (as ferrous described) as well as having fast lookups for duplicates. Although if you do one-way edges then duplicates shouldn't ever appear if you're building the map correctly, i.e. one cell at a time with no backtracking. Edited by ApochPiQ
Corrected code snippet

Share on other sites

Thanks ferrous and ApochPiQ, I understand it now.

I am beginning to think that ferrous has a good point, duplicate edges are not a big deal and might come in handy. Since it's my first time considering this problem, it did not occur to me.

Thanks again,

Mike

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 9
• 9
• 11
• 11
• 23
• Forum Statistics

• Total Topics
633679
• Total Posts
3013295
×