Функционално програмиране (И) 2016/2017

За целите на това упражнение ще представяме графите чрез списъци на съседство. Самият граф ще съдържа по един списък на съседите на всеки един връх, в който списък самият връх ще е глава, например:

(define G '((a b c d) ; от а има ребра към b,c,d
            (b e f)   ; може да бъде и ориентиран
            (c a d)
            (d b c g)
            (e)       ; връх без наследници
            (f b e)
            (g a)))

Зад.1. Да се напишат няколко основни функции за графи, а именно (vertices g), (successors v g), (has-edge? u v g), които връщат съответно списък с всички върхове в графа g, списък с всички наследници на даден връх в g и дали между два дадени върха има ребро:
(vertices G) -> '(a b c d e f g)
(successors 'c G) -> '(a d)
(has-edge? 'c 'e) -> #f

Зад.2. Да се напише функция (add-edge u v g), която добавя ориентирано ребро в графа g между върховете u и v, ако такова не съществува досега. Бонус: Да се напише функция, която съставя граф по списък от ребра.

Зад.3. Да се напише функция (contains-path? path g), която проверява дали последователността от върхове path е действителен път е графа g:
(contains-path? '(a b f e) G) -> #t
(contains-path? '(a c f e) G) -> #f

Зад.4. Да се напише функция (predecessors v g), която връща списък с всички предшественици на върха v в графа g:
(predecessors 'e G) -> '(b f)

Зад.5. Да се напише функция (extend-path path g), която връща всички възможни "разширения" на пътя path с едно ребро (искаме полученото да бъде прост път, т.е. да не съдържа повторения):
(extend-path '(a d b) G) -> '((a d b e) (a d b f))

Зад.6*. Да се напише функция (all-paths g), която намира всички прости пътища в графа g.
Упътване: използвайте предишната функция, евентуално с малко модификации. Използвайте и функция, която проверява дали всички елементи на списък се съдържат в друг.

Зад.7. Да се напише функция (edge-list g), която връща списък от всички ребра в графа g (без особена подредба):
(edge-list G) -> '((a . b) (a . c) (a . d) (b . e) (b . f) (c . a) (c . d) (d . b) (d . c) (f . b) (f . e) (g . a))

Зад.8. Да се напише функция (invert g), която обръща всички ребра в графа и връща новия граф.

Зад.9. Да се напише функция (bfs v g), която връща списък с върховете на графа g, получен при обхождане в ширина, започвайки от v.
(bfs 'a G) -> '(a b c d e f g) ; случайна подредба, очевидно не е единствената валидна

Зад.10. Да се напише функция (find-path u v g), която намира път между върховете u и v в графа g по избран от вас метод на обхождане (DFS или BFS).