Public Group

# algorithmicly connecting a graph

This topic is 758 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
Rutin
26
3. 3
4. 4
JoeJ
18
5. 5
gaxio
11

• 14
• 22
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631763
• Total Posts
3002196
×