Re: [QUIZ] Perl 'Medium' Quiz: Graph Connected Components (#2006-12-29)

On Monday 01 January 2007 01:19, Michael C. Toren wrote:
> On Fri, Dec 29, 2006 at 09:41:15PM +0200, Shlomi Fish wrote:
> > A--B--F       D--C
> >
> >    | /
> >    |/
> >
> >    E
>
> [ ..]
>
> > You should implement a function called "connected" that will receive
> > such an input and return its connected components, where a connected
> > component is such that for every two nodes in it, there's a path from
> > one to the other. So for the graph above the function will return:
> >
> > [
> >     [[$A,$B],[$B,$E],[$B,$F],[$F,$E]],
> >     [[$D,$C]],
> > ]
>
> Would it perhaps make more sense for the "connected" function to return a
> list of nodes, rather than links, for which there is some path connecting
> them?  For example:
>
>         [
>           [ $A, $B, $F, $E ],
>           [ $D, $C ]
>         ]
>

Well, that wasn't how the original problem was phrased. Besides, you may wish 
to know what are the links in the connected components. And determining the 
correct order for the nodes in this case would be more difficult. If for 
example you have:

[0,1],[0,2],[3,1]

Should it be:

[0,1,2,3]

Or:

[0,1,3,2]

So I suggest we stick with the original challenge.

Regards,

	Shlomi Fish


> Thanks,
> -mct

-- 

---------------------------------------------------------------------
Shlomi Fish      shlomif-ik1l9ssToec+JF/[email protected]
Homepage:        http://www.shlomifish.org/

Chuck Norris wrote a complete Perl 6 implementation in a day but then
destroyed all evidence with his bare hands, so no one will know his secrets.