-
Notifications
You must be signed in to change notification settings - Fork 1
/
a2.rkt
114 lines (94 loc) · 3.5 KB
/
a2.rkt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
;-----------------------------
; Assignment Group <number>
; <name1>, <student ID1>
; <name2>, <student ID2>
; <name3>, <student ID3>
;-----------------------------
;-------------------------------------------------------------------------------------
; If "graph" is acyclic, "topsort" returns an ordered list of its vertices obtained by
; topologically sorting it; otherwise "topsort" returns the symbol "cyclic".
;-------------------------------------------------------------------------------------
(define (topsort graph)
(if (null? graph) '() ; If "graph" is empty, () is a total ordering.
(let ((small (noInEdges graph))) ; Otherwise, get the list of vertices with no
(if (null? small) ; inedges.
'cyclic ; If none, then "graph" is cyclic.
(let ((rest (topsort ; Otherwise, sort the graph that results
(delete small graph)))) ; from deleting these vertices.
(if (eq? rest 'cyclic) ; If the reduced graph is cyclic, then
'cyclic ; so is "graph".
(append small rest))))))) ; Otherwise, construct total ordering.
;-------------------------------------------------------------------------------------
; "noInEdges" returns a list of all vertices of a graph which have no incoming edges.
;-------------------------------------------------------------------------------------
;diff -- return a sub-list of list2 whose members are not in list1
(define (noInEdges graph)
(if (null? graph) '()
(findallvex graph (getvex graph))))
(define (getvex graph)
(cond ((null? (cdr graph)) (list (caar graph)))
(else
(let (( vexes (getvex (cdr graph))))
(cons (caar graph) vexes)))))
(define (findallvex graph vexList)
(cond ((null? vexList) '())
(else
(let ((vexes (findallvex graph (cdr vexList))))
(let ((avex (findAvex graph (car VexList))))
(if (not (boolean? avex))
(cons avex vexes)
vexes))))))
(define (findAvex graph vex)
(cond ((null? graph) vex)
((ismember vex (cdar graph)) )
(else
(findAvex (cdr graph) vex))))
(define (ismember x list)
(cond ((null? list) #f)
((eq? x (car list)) #t)
(else
(ismember x (cdr list)))))
;-------------------------------------------------------------------------------------
; "delete" returns the graph obtained by removing the vertices with no incoming edges
; from a graph
;-------------------------------------------------------------------------------------
(define (delete vertices graph)
(cond ((null? vertices) graph)
((eq? (car vertices) (caar graph)) (delete (cdr vertices) (cdr graph)))
(else
(delete vertices (append (cdr graph) (list (car graph)))))))
;-------------------------------------------------------------------------------------
; Some graphs to try.
;-------------------------------------------------------------------------------------
(define cyclic1
'((a b b e)
(b c)
(c)
(d a b)
(e d f)
(f d)))
(define cyclic2
'((a a)))
(define cyclic3
'((a b)
(b c)
(c d)
(d e)
(e f)
(f a)))
(define acyclic1
'((a b c e)
(b c)
(c f)
(d)
(e d f)
(f)))
(define acyclic2
'())
(define acyclic3
'((a b c d e f)
(b c d e f)
(c d e f)
(d e f)
(e f)
(f)))