Нахождение компонент связанности графа (Пояснительная записка к курсовой работе), страница 5

Функциональное программирование является мощным и элегантным средством написания программ, позволяющее сосредоточится на основной идее реализуемого алгоритма, а не частных особенностях конкретных императивных языков. Lisp, являющийся ярким представителем языков функционального программирования, породивший целое семейство языков (наиболее известным из которых является язык Scheme), представляет собой средство, позволяющее совместить в одной программе как императивный, так и функциональный стили программирования, что ведет к максимально эффективной реализации выбранного алгоритма.

Любопытной особенностью lisp подобных языков является регулярность их синтаксиса, позволяющая использовать современные методологии программирования (такие, как объектно-ориентированное программирование) не изменяя самого языка.

Список литературы

1.  Зюзьков В.М. Функциональное программирование. Учебное пособие. Т.: 2000.

2.  Сафьянова Е.Н. Дискретная математика. Учебное пособие. Т.: 2000.

3.  Дейкстра Э. Дисциплина прогаммирования. – М.: Мир, 1978.

4.  Белов В.В. Воробьев Е.М. Шаталов В.Е. Теория графов. – М.: Высшая школа, 1976.

5.  Кормен Т. Лейзерсон Ч. Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО. 2000

Приложение 1. Листинг программы

;; Макрос, предназначенный для выполнения проверок.

;; Если заданный предикат form вычисляется в nil, то макрос печатает

;; сообщение на экран.

(defmacro check (form)

`(progn

;; Преобразуем к виду (or form (error …))

(or ,form (error "assertion failed" (quote ,form)))

;; Возвращаемое значение nil

nil))

;; Вспомогательные переменные, содержимое которых используется для проверки

;; типов объектов “граф” и “множество вершин”.

(defconstant *graph-id* 'graph)

(defconstant *vertex-set-id* 'vector-set)

;; Размер хеша множества вершин графа

(defvar graph:*hashsize* 101)

;; Конструктор неориентированного графа.

;; Функция принимает список атомов и списков, состоящих из двух

;; элементов, обозначающих, соответственно, вершину и ребро графа.

(defun graph:new (&optional links hashsize)

;; g: создаваемый объект

(let ((g (cons *graph-id*

(make-hash-table :size (or hashsize graph:*hashsize*)))))

;; выполняем инициализацию графа списком вершин и ребер

(dolist (link links)

;; link — очередной элемент списка

(if (listp link)

;; если link является списком, то это ребро

(graph:add-link g (car link) (cadr link))

;; иначе link — вершина

(graph:add-vertex g link)))

;; возвращаем построенный граф

g))

;; предикат проверки принадлежности типа объекта классу “граф”

(defun graph? (var)

(and (consp var) (equal (car var) *graph-id*)))

;; Функция возвращает хеш-таблицу вершин АТД Граф

(defun graph:vertexes (graph)

(check (graph? graph))

(cdr graph))

;; Функция возвращает список вершин графа, смежных с данной

(defun graph:vertex-links (graph vertex)

(check (graph? graph))

(gethash vertex (graph:vertexes graph)))

;; Функция добавляет вершину в неориентированный граф

(defun graph:add-vertex (graph vertex)

(check (graph? graph))

(setf (gethash vertex (graph:vertexes graph))

(gethash vertex (graph:vertexes graph))))

;; Функция добавляет ребро (source, dest) в неориентированный граф

(defun graph:add-link (graph source dest)

(check (graph? graph))

;; Функция добавления ребра add вызывается дважды, поэтому она вынесена

(flet ((add (s d)

;; SL – список вершин, смежных с исходной

(let ((sl (gethash s (graph:vertexes graph))))

;; Если ребро не было определено, добавим его

(unless (member d sl)

(setf (gethash s (graph:vertexes graph)) (cons d sl))))))

;; Добавление ребра в неориентированный граф реализовано как добавление

;; двух ребер в ориентированный

(add source dest)

(add dest source)))

;; Функция вызывает функцию p для каждой вершины графа

(defun graph:for-each-vertex (graph p)

(check (graph? graph))

;; maphash вызывает функцию двух аргументов, передавая ей ключ и значение

;; в данном случае значение игнорируется

(maphash (lambda (x y) (funcall p x)) (graph:vertexes graph)))