Re: connected?

I think I get it (thanks for sending the code).  You're starting at an
element and finding the connected set (the set of elements to which it is
connected) then starting at another element (or in your case a subset of
elements) and seeing if it's connected set is equal.  And having your
subsets cover all elements of the set.

My solution was sort of different:

start at some arbitrary element in S.
find it's connected set and "color" (mark as visited) each.
iterate through all elements in S verifying that they are present in the
connected set ("colored").

Couldn't both our approaches benefit just by finding the connected set C
of any element and seeing if this set is the same as the original set S.
This could be done by comparing the sizeof(S) == sizeof(C).

/a

On Tue, 17 Feb 2004, dvanhorn wrote:

> So Aaron and I were discussing algorithms to determine if a given set is
> connected.  Here is my algorithm, which is a generic algorithm for finite
> sets, parameterized by some predicate touching? which returns true when two
> elements are touching and false otherwise.  It's not very efficient, but
> fairly elegant IMHO.  I'd like to see other approaches...
>
> David
>
>
> This code uses the list set functions specified in Olin Shivers' SRFI-1,
> available at http://srfi.schemers.org/srfi-1/.  From MzScheme it can be loaded
> with (require (lib "list.ss" "srfi" "1")).
>
> ;; A set s is connected iff it contains 1 or fewer elements or...
>
> ;; We choose a singleton subset of s, c_0, which by definition is
> ;; connected.  Let c_n be the union of c_n-1 and all elements in s that
> ;; touch an element in c_n-1.  When c_n = c_n-1 we know that c_n does not
> ;; touch any more elements in s.  If c_n = s, then s is connected,
> ;; otherwise s is not connected.
>
> ;; 'a set -> bool
>
> (define (connected? s)
>    (if (<= (length s) 1) #t
>        (let ((touching-s?
>               (lambda (x) (filter (lambda (y) (touching? x y)) s))))
>          (let loop ((c (list (car s))))
>            (let ((c+1 (apply lset-union equal? c (map touching-s? c))))
>              (if (lset= equal? c c+1)
>                  (lset= equal? c s)
>                  (loop c+1)))))))