BFS in ruby from a hash

[equinox]

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.

 

[Robert Klemme]

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

 

[equinox]

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

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?

 

[Robert Klemme]

On Thu, 20 Nov 2008, equinox wrote:

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...

Kind regards

robert

 

[Todd Benson]

On Thu, 20 Nov 2008, equinox wrote:

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...

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

 

[equinox]

2008/11/20 Hugh Sasse <[email protected]>:

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...

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

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

 

[Robert Klemme]

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

 

[equinox]

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

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?