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

On Thursday 04 January 2007 05:08, Julien Quint (Pom) wrote:
> On Dec 30, 2006, at 4:41 , Shlomi Fish wrote:
> > Here's a quiz for the new year. My sister received this challenge
> > for her
> > college homework, and had to write some Standard ML code to solve
> > it, a task
> > which I helped her with. I hope you enjoy it too.
>
> Hi all,
>
> here is my answer for this quizz. Nothing fancy, not thoroughly
> tested but this is a well-known solution.
>

Hi Julien!

Thanks for your solution. It compiles under "use strict" and "use warnings" 
and passes all my tests. I also think it's much shorter than mine. :-).

I'm going to post my solution along with my tests later.

Regards,

	Shlomi Fish

> # Compute the connected components of the graph and return a list of
> list of
> # edges. Every list is a connected components. The edges are ordered
> in the
> # same way as in the original list of edges.
> # A simple algorithm for computing connected components is to build the
> # equivalence classes of vertices in the graph. Vertices belonging to
> the
> # same component are equivalent and belong in the same class. A
> simple way
> # to represent equivalence classes is a Union-Find tree. All elements
> in a
> # tree are equivalent, and the tree structure makes it easy to build the
> # union of two equivalence classes as we just need to attach the root
> of one
> # the trees to any node in the other.
> # The algorithm works in three steps:
> #   1. Make a new tree for every vertex in the graph with this vertex
> as the
> #   root (and only node so far.) Nodes point to their parent in a UF
> tree
> #   and the root points to itself.
> #   2. An edge between two vertices u and v means that u and v are in
> the
> #   same component, so u and v are equivalent, which means that all
> vertices
> #   equivalent to u are equivalent to all vertices equivalent to u.
> This is
> #   the union of their equivalent classes, which is implemented by
> attaching
> #   the root of v's tree to u. Once we have iterated over every edge
> in the
> #   graph, the resulting UF forest gives us the equivalence classes of
> #   vertices.
> #   3. We build the list of list of edges (each list being a
> component) by
> #   going through the original list of edges (to maintain the original
> #   order) and finding which component the edge belongs to. For every
> edge,
> #   looking up the root of the UF tree that one of its vertex belongs to
> #   gives us the index of the component in the list of list of edges,
> and we
> #   just push that vertex into the list.
> # Since we get the list of edges for the graph and not a list of
> vertices,
> # steps 1 and 2 can be merged.
> sub connected
> {
>    my $edges = shift;
>    # Step 1: initialize the UF forest for every vertex in the graph.
>    my $uf = { map { map { $_ => $_ } @$_ } @$edges };
>    # Step 2: make the union of the vertices of every edge.
>    $uf->{root($uf, $_->[1])} = $_->[0] for @$edges;
>    # Step 3: build the list of components. @components is the list
> itself,
>    # %components is the mapping between the root of an UF-tree and
> the index
>    # of the edge list in @components.
>    my @components = ();
>    my %components = ();
>    for (@$edges) {
>      my $root = root($uf, $_->[0]);
>      $components{$root} = @components if !exists $components{$root};
>      push @{$components[$components{$root}]}, $_;
>    }
>    return \@components;
> }
>
> # Find the root of an UF tree for a given node. We use a simple path
> # compression technique which also brings up nodes that we look-up
> closer to
> # the root.
> sub root
> {
>    my ($uf, $u) = @_;
>    while ($uf->{$u} != $u) {
>      my $next = $uf->{$u};
>      $uf->{$u} = $uf->{$next};
>      $u = $next;
>    }
>    return $u;
> }
>
> Julien

-- 

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