BFS in ruby from a hash

I want to do a breadth first search on a hash like below:

http://pastie.org/319366

can anyone give me some idea where to start as I’ve never done bfs
(breadth first search) on hash before.

On 20.11.2008 04:54, equinox wrote:

I want to do a breadth first search on a hash like below:

http://pastie.org/319366

can anyone give me some idea where to start as I’ve never done bfs
(breadth first search) on hash before.

http://en.wikipedia.org/wiki/Breadth-first_search#Algorithm_.28informal.29

If you just want to visit all nodes (i.e. not a search) then you need to
remember all visited nodes and not put new nodes into the queue which
you have seen already.

Kind regards

robert

On Nov 20, 12:34 am, Robert K. [email protected] wrote:

If you just want to visit all nodes (i.e. not a search) then you need to
remember all visited nodes and not put new nodes into the queue which
you have seen already.

Kind regards

    robert

Yes I know the algorithm of doing BFS, however I can’t see where a
hash is a graph structure…
How do I visit the child here? Which ones are trees in the same level?

2008/11/20 Hugh S. [email protected]:

On Thu, 20 Nov 2008, equinox wrote:

Yes I know the algorithm of doing BFS, however I can’t see where a
hash is a graph structure…

Well, isn’t this (i.e. analyzing the problem) part of your assignment?
This really looks like a homework assignment…

How do I visit the child here? Which ones are trees in the same level?

In the Pastie the keys point at arrays of strings. But in that example
all the strings correspond to keys, except for lonelygirl13 which looks
like a typo for the key lonelygirls13. Normally to make a tree with
hashes you’d use hashes of hashes [of hashes […]]. It seems to me
you can’t do Breadth first until you’ve got some Depth to not do first!

Hugh, not necessarily. You just need to look at the Hash as a vertex
collection. I’m not going to say more… :slight_smile:

Kind regards

robert

On Thu, Nov 20, 2008 at 8:27 AM, Robert K.
[email protected] wrote:

Kind regards

robert

Definitely agree with robert here. But the $database seems contrived.

I would guess the powers that be want you to come up with a clever way
to check your nodes. To be honest my first solution (that I thought
was clever) turned out to walk each node from left to right, but just
wasn’t even close to bfs. Your parent node, with this type of hash,
is probably supposed to be the first one, and then stack them from
there.

Todd

On Nov 20, 8:52 am, Todd B. [email protected] wrote:

hash is a graph structure…
you can’t do Breadth first until you’ve got some Depth to not do first!
I would guess the powers that be want you to come up with a clever way
to check your nodes. To be honest my first solution (that I thought
was clever) turned out to walk each node from left to right, but just
wasn’t even close to bfs. Your parent node, with this type of hash,
is probably supposed to be the first one, and then stack them from
there.

Todd

so I’ll need a queue to do this? How do you create a queue in ruby?

On Thu, 20 Nov 2008, equinox wrote:

http://en.wikipedia.org/wiki/Breadth-first_search#Algorithm_.28inform
hash is a graph structure…
How do I visit the child here? Which ones are trees in the same level?

In the Pastie the keys point at arrays of strings. But in that example
all the strings correspond to keys, except for lonelygirl13 which looks
like a typo for the key lonelygirls13. Normally to make a tree with
hashes you’d use hashes of hashes [of hashes […]]. It seems to me
you can’t do Breadth first until you’ve got some Depth to not do first!

    Hugh

2008/11/20 equinox [email protected]:

so I’ll need a queue to do this? How do you create a queue in ruby?

Go to the upper right corner of your web browser window. Enter “ruby
queue” in the field you find there and press ENTER. See what happens.

Frankly, IMHO you could demonstrate a bite more commitment.

Cheers

robert

On Nov 20, 10:18 am, Robert K. [email protected] wrote:

robert


remember.guy do |as, often| as.you_can - without end

Is there another common way to do it without using queue?
If the data structure is a hash then those in the same level
Are those represented by the same key to hash right?

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs