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

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.

# 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