;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) '() ) ) )
Wednesday, February 22, 2012
Longest Path in a directed graph (Scheme Program)
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment