Re: connected?

Aaron S. Hawley wrote:
> 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.

Hmmm.  I'm not sure.  What I do is start with a connected subset of s.  Then I
grow that set keeping the property of connectedness invariant.  I keep growing
until a fixed point is reached; there is no more to be grown.  If that set is
equal to s (or of the same size, as you mention), then s is connected, since s
is equal to a connected 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").

This sounds right too.  You visit each element and accumulate the set of
elements it immediately touches.  If s is connected, you'll generate the same
set s by visiting all elements in s.

I think the only difference between our two algorithms is that the set I
accumulate is connected throughout the process, whereas yours may not be.

(define (connected? s)
  (if (<= (length s) 1) #t
      (lset= equal? s
             (append-map
              (lambda (x) (filter (lambda (y) (touching? x y)) s))
              s))))

This is probably much more effecient than mine.  You do only one lset=
operation, I do one on each iteration.

Maybe you could post your gawk version for comparison to that. ;)

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

Yes, but for me, using lists as a set datastructure, the sizeof operation is
not trivial (not that lset= is either) (nor is sizeof actually part of the
library).  It's not just the list length operation, which is linear in the
size of the list.  List length doesn't work since (= (length '(1 1)) (length
'(1))) is false, but the sets are of the same size.

The simple case in my algorithm isn't quite right because of that.  Really a
predicate should be defined:

(define (singleton-or-empty? s)
  (match s
    [() #t]
    [(x . _) (lset= equal? (list x) s)]))

And then do:

(define (connected? s)
  (if (singleton-or-empty? s) #t
      (lset= equal? s
             (append-map
              (lambda (x) (filter (lambda (y) (touching? x y)) s))
              s))))

David