Forum: Ruby BFS in ruby from a hash

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
F1f64ada61619d15b958b1ad5164c601?d=identicon&s=25 equinox (Guest)
on 2008-11-20 04:55
(Received via mailing list)
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.
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2008-11-20 08:35
(Received via mailing list)
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#...

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
F1f64ada61619d15b958b1ad5164c601?d=identicon&s=25 equinox (Guest)
on 2008-11-20 14:55
(Received via mailing list)
On Nov 20, 12:34 am, Robert Klemme <shortcut...@googlemail.com> 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?
457cf540784a12ba2f30e06565a2c189?d=identicon&s=25 Hugh Sasse (Guest)
on 2008-11-20 15:23
(Received via mailing list)
On Thu, 20 Nov 2008, equinox wrote:

> > http://en.wikipedia.org/wiki/Breadth-first_search#......
> 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
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2008-11-20 15:31
(Received via mailing list)
2008/11/20 Hugh Sasse <hgs@dmu.ac.uk>:
>
> 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... :-)

Kind regards

robert
289cf19aa581c445915c072bf45c5e25?d=identicon&s=25 Todd Benson (Guest)
on 2008-11-20 16:57
(Received via mailing list)
On Thu, Nov 20, 2008 at 8:27 AM, Robert Klemme
<shortcutter@googlemail.com> 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
F1f64ada61619d15b958b1ad5164c601?d=identicon&s=25 equinox (Guest)
on 2008-11-20 17:51
(Received via mailing list)
On Nov 20, 8:52 am, Todd Benson <caduce...@gmail.com> 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?
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2008-11-20 19:00
(Received via mailing list)
2008/11/20 equinox <aditya15417@gmail.com>:
> 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
F1f64ada61619d15b958b1ad5164c601?d=identicon&s=25 equinox (Guest)
on 2008-11-20 21:01
(Received via mailing list)
On Nov 20, 10:18 am, Robert Klemme <shortcut...@googlemail.com> 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 topic is locked and can not be replied to.