;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
;               Depth First Search (DFS) in a graph G.
;
; NOTE: that the graph may be directed or undirected.
; Two versions of depth first search are given below, one recursive
; the other iterative. They are functionally equivalent
;
; See demo at end of file
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (recursive-dfs s G)
  (let ((mark (make-vector (+ 1 (n G)) #f))                          ;(1)
	(visited '()))                                               ;(2)
  (define (dfs' w)                                                   ;(3)
    (cond ((not (vector-ref mark w))                                 ;(4)
	   (vector-set! mark w #t)                                   ;(5)
	   (set! visited (cons w visited))                           ;(6)
	   (do ((unvisited (adjacent-to w G) (cdr unvisited)))       ;(7)
	       ((null? unvisited))                                   ;(8)
	     (dfs' (first unvisited))))))                            ;(9)
  (dfs' s)                                                           ;(10)
  visited))                                                          ;(11)
;;;
;;; Depth first search from starting vertex s in graph G
;;;
;;; (1) Vector element (vector-ref mark w) is #t if vertex w has been visited
;;;     otherwise (vector-ref mark w) is #f
;;; (2) visited is a list of vertices, giving the vertices in reverse 
;;;     order as visited by a dfs from vertex s in G
;;; (3) Local recursive function dfs' ... this is for cosmetics
;;;     saving us having to pass in the vector mark every call
;;; (4) If we have not already visited the vertex w ...
;;; (5) ... then set w's mark ast true ...
;;; (6) ... push w onto the set of visited vertices ...
;;; (7-9) ... then make recursive calls to dfs' from the vertices 
;;;           adjacent to w in G
;;;
;;;


(define (iterative-dfs s G)
  (let ((mark (make-vector (+ 1 (n G)) #f))
	(unvisited (list s)) (visited '()))
    (do ()
	((null? unvisited) visited)
      (let ((w (first unvisited)))
	(set! unvisited (cdr unvisited))
	(cond ((not (vector-ref mark w))
	       (vector-set! mark w #t)
	       (set! visited (cons w visited))
	       (set! unvisited (append (adjacent-to w G) unvisited))))))))
;;;
;;; Iterative version of above function ... functionally equivalent
;;;


;;;
;;; demo deno demo demo demo deno demo demo demo deno demo demo demo deno demo
;;;

(define (demo-dfs n p)
  (define G (make-random-graph n p))
  (draw-graph G)
  (print (list 'i-dfs 1 (iterative-dfs 1 G)))
  (print (list 'r-dfs 1 (recursive-dfs 1 G)))
  (print (list 'r-dfs n (recursive-dfs n G)))
  (print "~~~~~~~~ Above undirected, below directed ~~~~~~~~")
  (define DG (make-random-digraph n p))
  (draw-graph DG)
  (print (list 'i-dfs 1 (iterative-dfs 1 DG)))
  (print (list 'r-dfs 1 (recursive-dfs 1 DG)))
  (print (list 'r-dfs n (recursive-dfs n DG))))
;;;
;;; Generate a undirected graph G with n vertices and edge probability p
;;; Then do a dfs (iteratively) starting at vertex 1, then repeat using
;;; the recursive dfs, then do dfs starting at vertex n
;;;
;;; Repeat the procedure, but do it with a directed graph DG
;;;