Wednesday, February 22, 2012

Longest Path in a directed graph (Scheme Program)


;Function that returns list of all edges of a given vertex...
;Eg when the graph G given below is passed and v=1 it will return (2 5)
(define (edges v G)
 (if (null? G)
  '()
  (if (= (caaar G) v)
   (cadar G)
   (edges v (cdr G))
  )
  
 )
)

;To compare a list of vertices and then to retun the longest path among them...
(define (longer-one v-L G long-path)
      (if (null? v-L)
   long-path
   (if (< (length long-path) (length (cons (car v-L) (longest-path (car v-L) G))))
    (longer-one (cdr v-L) G (cons (car v-L) (longest-path (car v-L) G)))
    (longer-one (cdr v-L) G long-path)
   )
      )
)


;Function to find the longest path...
(define (longest-path v G)
 (if (null? (edges v G))
       '()
       (if (null? (cdr (edges v G)) )
  (cons (car (edges v G)) (longest-path (car (edges v G)) G))
  (longer-one (edges v G) G (cons (car (edges v G)) (longest-path (car (edges v G)) G)))
       )
 )
)

(define (find_path v G)
 (cons v (longest-path v G))
)

(define G
  (list
    (list (list 1) (list 2 5))
    (list (list 2) (list 3))
    (list (list 3) (list 4))
    (list (list 4) (list 9))
    (list (list 5) (list 6))
    (list (list 6) (list 7))
    (list (list 7) (list 8))
    (list (list 8) '() )
    (list (list 9) '() )

  )
)  

(define G2
  (list
    (list (list 1) (list 3))
    (list (list 3) (list 5 8))
    (list (list 5) (list 9))
    (list (list 8) (list 4))
    (list (list 4) (list 7 10))
    (list (list 7) (list 6))
    (list (list 6) (list 9))
    (list (list 9) '() )
    (list (list 10) '() )

  )
)

No comments:

Post a Comment