; G R A P H S

; A graph is a pair of sets 

; A set V of vertices

(define V (list 1 2 3 4))

; and a set E of edges connecting vertices 

(define edge (lambda (x y) (cons x y)))

(define e1 (edge 1 1))

; So an edge e is a cons cell 
; e1 = (1 . 1)

(define from car)
(define to   cdr)

; We can define E by hand 
; (define E (list (edge 1 1) (edge 1 2) .... )) 

; but we like computers
(define build-complete-graph (lambda (V) (build-complete-graph-aux V V)))
(define build-complete-graph-aux 
  (lambda (vertex-set V) 
    (if (null? vertex-set) '() 
	(append 
	 (map (lambda (x) (edge (car vertex-set) x)) V)
	 (build-complete-graph-aux (cdr vertex-set) V)))))

; (map f list) 
; map returns a list of the same size with each element in the 
; list replaced by the result of applying f to that element. 
; So if list = (1 2 3 4) and f(x) = 2 * x -- define f (lambda (x) (* 2 x))
; then map returns (f(1) f(2) f(3) f(4)) -- (2 4 6 8)

; So a (map (lambda (x) (edge 1 x)) V)
; will create an edge between 1 and every element in V 
; (map (lambda (x) (edge 1 x)) (1 2 3 4))
; ==> ((1 . 1) (1 . 2) (1 . 3) (1 . 4))
; This will be done for each element in the vertex-set 

; Therefore, the lambda will generate all possible pairs of vertices 

(define E (build-complete-graph V))

; so we have a set of edges which represent every possible connection 
; between two nodes
E
; ((1 . 1) (1 . 2) (1 . 3) (1 . 4) (2 . 1) (2 . 2) (2 . 3) (2 . 4) 
;  (3 . 1) (3 . 2) (3 . 3) (3 . 4) (4 . 1) (4 . 2) (4 . 3) (4 . 4))

; And we have our complete graph

(define G (cons V E))

(define vertices (lambda (G) (car G)))
(define edges (lambda (G) (cdr G)))

; I am going to create the other types of graphs by removing edges that 
; fit some criteria.  

; remove all edges that make the function f true
(define remove  
  (lambda (f edges)
    (cond
     ((null? edges) '())
     ((f (car edges)) (remove f (cdr edges)))
     (else (cons (car edges) (remove f (cdr edges)))))))



; S i m p l e   G r a p h
; A simple graph Gs is defined as a graph where for all edges 
; e \in E  , e = {(x . y) | x \neq y} 
; Or  (x . y) \in E --> x \neq y 
; Or   x = y  --> (x . y) \notin E

; an edge t does not connect distinct vertices 
; if it starts from and connects to the same value 
(define not-connect-distinct-vertices
  (lambda (e) (eq? (from e) (to e))))

; remove all edges from the complete graph G that do not connect distinct vertices
(define Gs (cons V (remove not-connect-distinct-vertices (edges G))))

Gs
; V = (1 2 3 4)
; E = ((1 . 2) (1 . 3) (1 . 4) (2 . 1) (2 . 3) (2 . 4) (3 . 1) (3 . 2) (3 . 4) (4 . 1) (4 . 2) (4 . 3))


; Undirected vs. directed simple graph

; The graphs previously built have directed edges 

; If we assume that the edges (1 . 2) or (2 . 1) are each equivalent 
; to (1 . 2) AND (2 . 1).  That is, there is no difference between 
; the two vertices so there is no need to list it twice in E. 
; We can enforce this with a non-symmetric relation applied on the pairs

(define to-not-greater-than-from (lambda (E) (> (from E) (to E))))

(define Gu (cons V (remove to-not-greater-than-from (edges Gs))))

Gu
; V = (1 2 3 4)
; E = ((1 . 2) (1 . 3) (1 . 4) (2 . 3) (2 . 4) (3 . 4))