Jump to content
  • Advertisement
Sign in to follow this  
Jemburula

BFS with C++: Question about storing a 'parent'

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi there! I'm writing a BFS algo and I am implementing Fringe and Expanded lists using STL vectors. Each Node in the problem I generate I want to be able to store the Parent node it was generated from in the Expanded list (I have moved the Parent node in to the Expanded list before generation of children). What is the best way to do this? Storing an index for the Parent seems slightly dodgey. I tried a pointer to the object which gives me access violations and so I read somewhere that is a terrible idea (will read up on later?). So what else can I do? I thought about having an iterator that points to the element in Expanded but then for the root Node I would have to create some sort of generic "EmptyNode" element to compare against. Is this a good idea? Any other suggestions? The point of it is when the Solution path is found, I can trace back the path. Cheers, much appreciated! Edit: I just had another thought, storing an iterator is a bad idea because aren't iterators invalidated everytime the vector is changed?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Jemburula
Hi there! I'm writing a BFS algo and I am implementing Fringe and Expanded lists using STL vectors.


You may not have chosen the best container for the purpose. For a breadth-first search algorithm, you do not need random access (i.e. indexing) to the data. You do, however, need to be able to efficiently move elements from one set to another. This hints that a std::list may be a better choice.

Quote:
Each Node in the problem I generate I want to be able to store the Parent node it was generated from in the Expanded list (I have moved the Parent node in to the Expanded list before generation of children). What is the best way to do this? Storing an index for the Parent seems slightly dodgey.


Do you have lists of nodes or lists of pointers to nodes. That is, do the node exist only within the list, or are the lists just a view of nodes which have an independent existence? This will affect your design.

Quote:
I tried a pointer to the object which gives me access violations and so I read somewhere that is a terrible idea (will read up on later?).

So what else can I do? I thought about having an iterator that points to the element in Expanded but then for the root Node I would have to create some sort of generic "EmptyNode" element to compare against. Is this a good idea? Any other suggestions?

Edit: I just had another thought, storing an iterator is a bad idea because aren't iterators invalidated everytime the vector is changed?


With a std::vector, iterators and pointers to the elements have exactly the same problem: when the vector grows, it may need to allocate a larger contiguous block of memory and move all its elements there. This leaves your pointers and iterators invalid.

Quote:
The point of it is when the Solution path is found, I can trace back the path.


std::list iterators do not have that problem, especially if you use std::list::splice() to move elements around. Another option is, as I mentioned above, to have the entire node list to exist independently of the Fringe and Expanded lists, and to have the latter two only contain pointers to the elements that unchanging list.


Finally, if all you care about is the result rather than the learning experience, you can pick up what you need from Boost.

Share this post


Link to post
Share on other sites
Awesome, thanks I'll look in to std::list.

I have a list of nodes.

So holding std::list::iterator's is a good way of getting what I want to achieve? I can see what you mean by having an independent list of nodes, but for now I think it would require a bit too much refactoring. I'm running a bit short of time as it's for an assignment =) .'. this is purely for learning purposes.

Thanks again for your help!

Share this post


Link to post
Share on other sites
Quote:
Original post by Jemburula
So holding std::list::iterator's is a good way of getting what I want to achieve?

List iterator do not get invalidated unless you actually remove the element from the list. list::splice transfers the list node itself from one list to another, which preserves the iterators. That, of course, assumes you are free to make 'destructive' operations on the source list.

You still need to be careful, obviously.

Whether you're better off using the iterator or an element pointer is up to you. You could use a series of splices at the end to neatly package the solution into a single list that you return from your algorithm.

It does in part depend on what you have to work with.

Quote:
I can see what you mean by having an independent list of nodes, but for now I think it would require a bit too much refactoring. I'm running a bit short of time as it's for an assignment =) .'. this is purely for learning purposes.


OK, fair enough. :)

Share this post


Link to post
Share on other sites
Hmm, I have changed to a list but I'm a bit confused now. The extent to which I've used iterators is roughly just called begin and end and using ++ & -- to traverse the collection. I'm reading something about "iterator_traits" which seems to be what I want with an "Iter::pointer". But I have no idea what to do :S

How do I create one of these and also is it possible to set these to 0 or something to indicate that this Node has no Parent (and hence is the Start node)?

Share this post


Link to post
Share on other sites
You don't need iterator traits or anything complex - you just need a copy of the iterator itself. When you use ++ or -- to traverse the collection, you just change the element that the iterator refers to. If you copy that iterator, you'll have stored a copy of an iterator referring to a specific element, which you can use later to get at that element.

Share this post


Link to post
Share on other sites
Quote:
Original post by Kylotan
You don't need iterator traits or anything complex - you just need a copy of the iterator itself. When you use ++ or -- to traverse the collection, you just change the element that the iterator refers to. If you copy that iterator, you'll have stored a copy of an iterator referring to a specific element, which you can use later to get at that element.


Sexy! Nice to meet you Kylotan, thanks for the help.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!