Lecture 24 : Counting in cycles

Let's make a simple data definition for web pages.  A web page will
consist of a URL and links to other web pages (we're leaving out the
actual text on the pages for now).  What would this look like?

;; A webpage is (make-webpage string list-of-webpage)
(define-struct webpage (url links))

;; A list-of-webpage is either
;; empty, or
;; (cons webpage list-of-webpage)

Reminder:  we get
           set-webpage-url! :  webpage string -> void
           set-webpage-links!: webpage list-of-webpage -> void

(define Ghome (make-webpage "www.cs.wpi.edu/~ghamel/" empty))
(define 1101home (make-webpage "www.cs.wpi.edu/~cs1101/c05/" empty))
(define CSdept (make-webpage "www.cs.wpi.edu" empty))

[Do as a class]
;; add-link : webpage webpage -> void
;; adds link to second page from first page
;; EFFECT: change the links of the first page
(define (add-link frompage topage)
  (set-webpage-links! frompage (cons topage (webpage-links frompage))))
                      --------  -----------------------------------
                      webpage                  |
                                         list-of-webpage

(add-link Ghome 1101home)
(add-link 1101home Ghome)
(add-link CSdept Ghome)

[Draw picture]

Now, we want to know how many pages are accessible from our page.
(counting from Ghome, should get 2)
Following the techniques we've used until now, we would write this as: 


;; count-pages : webpage -> number
;; consumes web page and produces number of pages accessible from it 
;; through links
(define (count-pages apage)
  (+ 1 (count-links (webpage-links apage))))

;; count-links : list-of-webpage -> number
;; consumes list of webpages and produce total number of pages accessible from 
;; pages in the list
(define (count-links alol)
  (cond [(empty? alol) 0]
        [(cons? alol) (+ (count-pages (first alol)) 
                         (count-links (rest alol)))]))

If we try to run this though, the program never stops.  Why?  Because
the data has a cycle -- counting Ghome forces us to count 1101home,
which forces us to count Ghome, ...

How do we avoid this problem?  We need to remember which pages we've
already counted and make sure we don't count them again.

[Declare a variable]

;; visited : list-of-string
;; stores urls that have already been counted
(define visited empty)

So, count-pages is where you need to check visited.

[give students in-list]

;; in-list?:  string list-of-string -> boolean
;; determines whether string is in list
(define (in-list? astring alos)
  (cond [(empty? alos) false]
        [(cons? alos) (or (string=? astring (first alos))
                          (in-list? astring (rest alos)))]))
                

[Have students do this...]

;; count-pages : webpage -> number
;; consumes web page and produces number of pages accessible from it 
;; through links
(define (count-pages apage)
  (cond [(in-list? (webpage-url apage) visited) 0]    ---> if it's already
                                                           visited, don't
                                                           count it

        [else (begin (set! visited (cons (webpage-url apage) visited))
                     (+ 1 (count-links (webpage-links apage))))]))


[Show that this works (once) but gives wrong answer after that...]

(count-pages Ghome)
>2
(count-pages 1101home)
>0

Now, if we run count-pages twice on the same page, we get 0 the second
time.  To make this program useful, we need to remember to reset the
visited list before each time we use this to count from the
interactions window.  Best way to do this is with a helper function
that we'll use to start the computation:

;; count-accessible : webpage -> number
;; consumes page and produces number of pages accessible from it through links
;; Effect : resets visited to empty
(define (count-accessible apage)
  (begin (set! visited empty)
         (count-pages apage)))