Re: perldb weirdness

[Michael Styer <michael@styer.net>]

Jeff Abrahamson wrote:

> On Sun, Dec 12, 2004 at 10:27:11PM -0500, Michael Styer wrote:
>>   [85 lines, 432 words, 2550 characters]  Top characters: etsnoarh
>> 
>> I've been looking at this code wondering what the heck is going on,
>> and I can't make any sense of it, so I'll ask.
> 
> Yes, it's a bit odd looking, I admit, and it's doing something you
> might not think about very often.
> 
> Here's the algorithm in pseudo-code.  It finds the connected
> components of an undirected graph.  Cf. Cormen et al., ch 22 (first
> edition) or ch 21 (second edition).

<snip helpful quote from Cormen et al>

> The algorithm for connected components is then
> 
>     for each vertex v in V(G)
>         make-set(v)
>     for each edge (u,v) in E(G)
>         if find-set(u) != find_set(v)
>             union(u,v)
> 
> Quoting from Cormen again, the procedure initially places each vertex
> v in its own set. Then, for each edge (u, v), it unites the sets
> containing u and v.  After all the edges are processed, two vertices
> are in the same connected component if and only if the corresponding
> objects are in the same set.
> 
> 
> So the thing I need is to say "which set is x in?"

Aha. OK, I see what the issue is, and what you were doing. Thank you for
the explanation and references.
 
> Thus, I have a hash that has elements as keys and references to (I was
> hoping pointers to) hashes as values.  A union is thus just a matter
> of adding one element's hash's keys to the other's, then setting the
> two hash pointers to the same hash reference.

> It would have worked in C. ;-)

My C is, um, not very good, so I've taken a stab your Perl code
instead... ;)

What about this? (+ to add a line, - to delete, hope that's obvious) Does
this do what you want? (Warning: this is not tested)

    my %sets = ();
    for my $v (keys %V) {
-       $sets{$v} = [$v];
+       $sets{$v} = {$v => 1}
    }
    for my $v_begin (keys %E) {
        my $adj = $E{$v_begin};
        for my $v_end (keys %{$adj}) {
            if($sets{$v_begin} != $sets{$v_end}) {
                # union of sets
                my %s1 = %{$sets{$v_begin}};
                my %s2 = %{$sets{$v_end}};
+               my $union = {};
-               for my $key (keys %s1) {
+               for my $key (keys %s1, keys %s2) {
-                   $s2{$key} = 1;
+                   $union->{$key} = 1;
+                   $sets{$key} = $union;
                }
-    		    $sets{$v_begin} = $sets{$v_end};   # set pointers equal
            }
        }
    }
    my %unique_sets;
    for my $s (keys %sets) {
        print $sets{$s}, "\n";
        $unique_sets{$sets{$s}} = $sets{$s};
        print $sets{$s}, "\n";
    }

Or see the attachment for a version with subroutines and what have you. I
wrote that first to figure out what you were trying to do, then realized
that what I had was almost exactly what you started with and you just
need the changes above. I think. :) I've never used the stringification
of a reference like this, but it seems like it should work for what
you're doing...

Mike

Attachment: connected_components.pl
Description: Binary data