Вместе с тем, для реализации потребуется хранение множеств синих и ультрафиолетовых множеств. Так, как множество синих вершин пополняется итеративно, по одной вершине за раз, и больше эти вершины не используются, то для них подойдет одно-связанный список.
Множество ультрафиолетовых вершин так же можно реализовать при помощи одно-связанного списка — причиной тому служит желание выполнить не деструктивную операцию слияния множеств ультрафиолетовых вершин и множества вершин, смежных с данной.
Программа состоит из трех компонентов — операции над объектом «граф» (graph), операции над объектом «множество вершин» (vertex-set) и функция поиска компонент связанности заданного графа.
Все функции программы, оперирующие с объектами, имеют в имени две компоненты, разделенные символом двоеточие (:). <имя класса>:<имя метода>. Каждый такой метод, исключая конструкторы объектов, принимает в качестве первого параметра ссылку на объект соответствующего типа.
Программа включает простейший контроль типов, выполняемый при каждом вызове метода классов «Граф» и «Множество вершин», реализация контроля основана на макроподстановке check раскрывающая предикат, переданный ей в качестве параметра P в выражение (or P (error …)).
В программе реализованы только необходимые операции над графами. Выбранный набор операций позволяет легко модифицировать внутреннюю структуру и реализацию объекта, оставляя при этом неизменным внешний интерфейс класса[2].
Объекты типа «граф» представляются в виде пары («Идентификатор типа», хеш-таблица). Идентификатор типа для графов определяется значением переменной *graph-id*. Значение идентификатора проверяется предикатом проверки типа. Второй элемент пары хранит ссылку на хеш-таблицу, являющуюся описателем графа. Таблица индексирована по именам вершин, а в качестве значений хранится одно-связанный список смежных вершин.
Создание и инициализация неориентированного графа.
graph:new (&optional links hashsize)
Функция создает и инициализирует объект «граф». Параметр links является списком вершин и ребер графа. Каждый элемент списка представлен как одна вершина (атом) или как список, содержащий два элемента, описывающие ребро графа. Функция конструирует граф на основании данного определения. Вершины графа не требуют предварительного определения, а дополняются динамически, по мере появления в описателе ребра.
Собственно граф представлен как хеш-таблица, в качестве ключа которой используется имя вершины, а в качестве значения — список вершин, смежных с данной вершиной. Размер хеш-таблицы выбирается при помощи необязательного параметра hashsize, имеющего значение по умолчанию равным значению переменной graph:*hashsize*. В данной реализации выбрано значение 101, из тех соображений, что графы, используемые в программе не велики. Но, если количество вершин в графе превосходит 75, предпочтительно явно специфицировать параметр hashsize (или изменить значение переменной graph:*hashsize*).
Проверка типа
graph? (var)
Предикат проверяет тип объекта, и возвращает не nil в случае успеха.
Доступ к хеш-таблице вершин графа
graph:vertexes (graph)
Функция предполагается служебной. Возвращает хеш-таблицу вершин графа.
Наличие данной функции позволяет легко ввести дополнительные поля в структуру, описывающие граф, и, таким образом, служит для дальнейшего развития программы.
Получение списка вершин, смежных с данной
graph:vertex-links (graph vertex)
Функция возвращает список вершин, смежных с данной.
Добавление вершины к графу
graph:add-vertex (graph vertex)
Функция добавляет новую вершину в граф, если она там не существовала. Повторное добавление вершины не приводит к потере связей, и не выполняет, таким образом, никаких действий.
Добавление ребра к графу
graph:add-link (graph source dest)
Функция добавляет новое ребро в граф, если такого ребра еще не было, повторное добавление ребра является пустой операцией.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.