MOTD

I've had this recurring theme in my life where I try to get my brother into some technical topic or other. Typically I'm trying to get him into programming of some sort. I never know how much of it is me being a pestering brute and how much is him actually enjoying and understanding the lesson.

So my latest push was accepted rather warmly. I mentioned that graph algorithms are usually big list manipulations, and the sort of thing that has all sorts of rich algorithm analysis behind it. Lots of good science code out there.

So he sent me this way to determine if a sequence of the degrees of unique vertices is graphical. That is, can we say that in a reasonable universe, all of these vertices are connected in a single structure.

(1 2 2 1) is a valid graph, since it is just four nodes strung together in a line. (7 2 2 1) is invalid, since there's simply not enough nodes for any one of them to have 7 connections.

I'm not sure he followed my explanations, or really spent much time reading my long mails on the subject. I encouraged him to trace the various functions to see how they work. The trace function is simply fantastic for learning how a system is behaving without going into the debugger. It's much like the strace and ltrace tools, but it's easier to be selective.

I'm not a great schemer, so likely this is done in a stupid or redundant way. I do think it's done in a portable way, and is straightforwardly implemented so that a new schemer can understand it.

So here's the code, all commented and supafly. The latest version lives at http://zork.net/~nick/scheme/degree_seq.scm

; Functions for analyzing degree sequences in an undirected graph


; list-satisfies? is a list analyzer function.  It accepts a predicate
; function and a list.  If any element of the list should fail the
; predicate, then list-satisfies? fails as a whole.  Put another way, it
; succeeds *only* when all elements of the list satisfy the predicate.
(define list-satisfies?
  (lambda (predicate l)
    (cond ((null? l) #t)
          ((predicate (car l)) (list-satisfies? predicate (cdr l)))
          (else #f))))

; decrement-n-elements accepts an integer n and a list of numbers.  It
; subtracts 1 from the first n elements of the list.  No data validation
; is done, so all atoms must be numbers.  In the event that there aren't
; enough elements in the list to decrement n elements, the function will
; simply return a list with all elements decremented.
(define decrement-n-elements
  (lambda (n l)
    (cond ((null? l) '())
          ((zero? n) l)
          (else (cons (- (car l) 1)
                      (decrement-n-elements (- n 1) (cdr l)))))))

; valid-degree-sequence? is a predicate that analyzes a list of integers
; representing the degree of connectedness of unique nodes in an
; undirected graph.  It returns true if the sequence is all zeroes or
; reduces to same, and false if it contains a negative degree or reduces
; to a sequence with a negative degree.
(define valid-degree-sequence?
  (lambda (sequence)
    (cond ((list-satisfies? zero? sequence) #t)
          ((list-satisfies? (lambda (x) (not (negative? x))) sequence)
           (valid-degree-sequence? (reduce-sequence sequence)))
          (else #f))))

; reduce-sequence does the actual work of reducing the degree sequence.
; If the sequence d1,d2...dn has enough elements such that n >= d1, then
; it will decrement the first d1 elements of d2...dn.  If there are not
; enough elements for this to be performed, the list reduces to the bogus
; sequence (-1), which will fail any valid-degree-sequence? test.
(define reduce-sequence
  (lambda (sequence)
    (cond ((> (length (cdr sequence)) (car (sort sequence >)))
           (decrement-n-elements (car (sort sequence >))
                                 (cdr (sort sequence >))))
          (else '(-1)))))