Re: [QUIZ] Perl 'Medium' Quiz: Graph Connected Components (#2006-12-29)
Prem Kabir <premkabir_b-/[email protected]> Tue, 9 Jan 2007 17:51:50 +0000 (GMT)
| Newsgroups | gmane.comp.lang.perl.qotw.discuss |
|---|---|
| Message-ID | <[email protected]> |
--0-1059789904-1168365110=:5447
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
I think, with this approach of an array of edges, it may not be able to all graphs.
In the given example, if there were not edge, that would still be a valid graph with 3 connected components {{A, B, E, F}, {C}, {D}}, but this cannot be represented with the "edges" approach.
One could argue that we can imagine an edge from a vertex to itself, in which case, the original example has to be represented as:
[[$A,$A],[$A,$B],[$B,$B],[$B,$E],[$B,$F],[$C,$C],[$D,$D],[$D,$C],[$E,$E],[$F,$F],[$F,$E]]
Shlomi Fish <shlomif-ik1l9ssToec+JF/[email protected]> wrote:
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.
Send free SMS to your Friends on Mobile from your Yahoo! Messenger. Download Now! http://messenger.yahoo.com/download.php
--0-1059789904-1168365110=:5447
Content-Type: text/html; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
<div>I think, with this approach of an array of edges, it may not be able to all graphs.</div> <div> </div> <div>In the given example, if there were not edge, that would still be a valid graph with 3 connected components {{A, B, E, F}, {C}, {D}}, but this cannot be represented with the "edges" approach.</div> <div> </div> <div>One could argue that we can imagine an edge from a vertex to itself, in which case, the original example has to be represented as:</div> <div>[[$A,$A],[$A,$B],[$B,$B],[$B,$E],[$B,$F],[$C,$C],[$D,$D],[$D,$C],[$E,$E],[$F,$F],[$F,$E]]<BR></div> <div><B><I></I></B> </div> <div><B><I>Shlomi Fish <shlomif-ik1l9ssToec+JF/[email protected]></I></B> wrote: </div> <BLOCKQUOTE class=replbq style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #1010ff 2px solid">On Monday 01 January 2007 01:19, Michael C. Toren wrote:<BR>> On Fri, Dec 29, 2006 at 09:41:15PM +0200
, Shlomi Fish wrote:<BR>> > A--B--F D--C<BR>> ><BR>> > | /<BR>>
> |/<BR>> ><BR>> > E<BR>><BR>> [ ..]<BR>><BR>> > You should implement a function called "connected" that will receive<BR>> > such an input and return its connected components, where a connected<BR>> > component is such that for every two nodes in it, there's a path from<BR>> > one to the other. So for the graph above the function will return:<BR>> ><BR>> > [<BR>> > [[$A,$B],[$B,$E],[$B,$F],[$F,$E]],<BR>> > [[$D,$C]],<BR>> > ]<BR>><BR>> Would it perhaps make more sense for the "connected" function to return a<BR>> list of nodes, rather than links, for which there is some path connecting<BR>> them? For example:<BR>><BR>> [<BR>> [ $A, $B, $F, $E ],<BR>> [ $D, $C ]<BR>> ]<BR>><BR><BR>Well, that wasn't how the original problem was phrased. Besides, you may wish <BR>to know what are the
links in the connected components. And determining the <BR>correct order for the nodes
in this case would be more difficult. If for <BR>example you have:<BR><BR>[0,1],[0,2],[3,1]<BR><BR>Should it be:<BR><BR>[0,1,2,3]<BR><BR>Or:<BR><BR>[0,1,3,2]<BR><BR>So I suggest we stick with the original challenge.<BR><BR>Regards,<BR><BR>Shlomi Fish<BR><BR><BR>> Thanks,<BR>> -mct<BR><BR>-- <BR><BR>---------------------------------------------------------------------<BR>Shlomi Fish shlomif-ik1l9ssToec+JF/[email protected]<BR>Homepage: http://www.shlomifish.org/<BR><BR>Chuck Norris wrote a complete Perl 6 implementation in a day but then<BR>destroyed all evidence with his bare hands, so no one will know his secrets.<BR></BLOCKQUOTE><BR><p> Send free SMS to your Friends on Mobile from your Yahoo! Messenger. Download Now! http://messenger.yahoo.com/download.php
--0-1059789904-1168365110=:5447--