ргр по алгоритмам и структурам данных. АиСД РГР, ключников. Разработка атд Простой граф
 Скачать 135.4 Kb.
|
1.6. АТД «итератор исходящих ребер вершины»Интерфейс АТД «Итератор исходящих ребер вершины» включает операции: Конструктор (v) - создает итератор исходящих ребер графа для вершины, заданной дескриптором v; beg( ) - возвращает итератор, установленный на первое исходящее ребро вершины; end( ) - возвращает итератор, соответствующий окончанию переходов итератора; operator ++ - переход к следующему исходящему ребру; operator * - возвращает дескриптор исходящего ребра вершины, на которое указывает итератор. 1.7. АТД «итератор входящих ребер вершины»Интерфейс АТД «Итератор входящих ребер вершины» включает операции: Конструктор (v) - создает итератор входящих ребер графа для вершины, заданной дескриптором v; beg( ) - возвращает итератор, установленный на первое входящее ребро вершины; end( ) - возвращает итератор, соответствующий окончанию переходов итератора; operator ++ - переход к следующему входящему ребру; operator * - возвращает дескриптор входящего ребра вершины, на которое указывает итератор. 1.8. АТД «задача 2»Спроектировать и реализовать шаблонный класс для АТД «Задача 1» в соответствии с вариантом и использовать для решения задачи на неориентированном графе. Интерфейс АТД «Задача 2» включает операции: Конструктор (g) - создает объект задачи 1, ассоциированный с графом g, и выполняет решение задачи для графа g; Конструктор (T) - конструктор копирования создает копию объекта – задачи T; Деструктор () - уничтожает внутренние структуры объекта задачи; Set (g) – связывает объект задачи с графом g и выполняет решение задачи 1 для графа g; Restart ( ) – повторно выполняет решение задачи 1 для графа g; Result( ) – возвращает результат решения задачи 1. 2. Вариант заданияВариант задачи 2: 14) Формирование двусвязного неориентированного графа. 3. АТД «простой граф3.1. Формат АТД «простой граф»Простой статический граф представляет собой совокупность множества вершин и множества ребер, соединяющих вершины. Каждая вершина графа имеет номер. Ребра графа могут быть направленными (ориентированный граф), и ненаправленными (неориентированный граф). Каждое ребро хранит вес и данные указанных типов TWeight и TData. Граф может иметь две формы представления: L-тип или M-тип. В графе запрещены петли и параллельные рёбра из одной вершины. При создании экземпляра графа можно задать количество вершин и ребер, которые создадутся случайным образом. После создания, структуру графа можно изменять с помощью соответствующих операций вставки и удаления вершин и ребер. Коэффициент насыщенности графа изменяется в интервале [0,1]. ДАННЫЕ: Параметры: Type, Oriented, Weighted – переменные хранящие тип, тип ориентации, взвешенность графа Структура хранения коллекции реализована в двух вариантах: L-граф – граф представлен с помощью списков смежности: с каждой вершиной графа, связывается список исходящих из нее ребер. M-граф – граф представлен в виде матрицы смежности: на пересечении j-ого столбца и i-ой строки находится указатель на дескриптор ребра или 0, если ребра нет, соединяющего i и j вершины. ОПЕРАЦИИ: Конструктор Вход: нет Предусловия: нет Процесс: создание внутреннего пустого объекта L-граф, установка свойства неориентированности Выход: нет Постусловия: создание пустого неориентированного L-графа Конструктор Вход: nVert – число вершин, type – тип графа (орграф/неорграф), form – форма графа Предусловия: нет Процесс: создание внутреннего объекта графа заданного типа и вставка заданного числа вершин Выход: нет Постусловия: создание графа заданного типа и ориентированности, с количеством вершин count Конструктор Вход: nVert – число вершин, nEdge – число ребер графа, type – тип графа (орграф/неорграф), form – форма графа Предусловия: nEdge не превышает максимально допустимого количества рёбер для графа с количеством вершин nVert, в противном случае количество вершин будет равно максимально допустимому Процесс: создание внутреннего объекта графа заданного типа и вставка заданного числа вершин и рёбер Выход: нет Постусловия: создание графа заданного типа и ориентированности, с количеством вершин nVert и количеством ребер nEdge. Конструктор копирования Вход: объект типа “Простой, статический граф” Graph Предусловия: объект SG не пуст Процесс: создание нового графа и копирование в него всех свойств SG, а также вершин и рёбер Выход: нет Постусловие: создана копия переданного графа Деструктор Вход: нет Предусловия: нет Процесс: удаление внутренних структур Выход: нет Постусловие: нет Опрос числа вершин в графе Вход: нет Предусловия: нет Процесс: чтение значения количества вершин Выход: количество вершин в графе Постусловия: нет Опрос числа рёбер в графе Вход: нет Предусловия: нет Процесс: чтение значения количества рёбер Выход: количество рёбер в графе Постусловия: нет Опрос типа графа Вход: нет Предусловия: нет Процесс: чтение значения типа графа Выход: тип графа (ориентированный/неориентированный) Постусловия: нет Опрос формы представления графа Вход: нет Предусловия: нет Процесс: чтение значения формы представления графа Выход: форма представления графа (L-граф/M-граф) Постусловия: нет Опрос коэффициента насыщенности графа Вход: нет Предусловия: нет Процесс: расчёт коэффициента насыщенности графа Выход: значение коэффициента насыщенности графа Постусловия: нет Преобразование графа к L-графу Вход: нет Предусловия: граф не является L-графом Процесс: создание нового внутреннего объекта L-графа, в который добавляются все вершины и рёбра из текущего графа Выход: true – в случае удачного преобразования, иначе false Постусловия: внутреннее представление графа - L Преобразование графа к M-графу Вход: нет Предусловия: граф не является M-графом Процесс: создание нового внутреннего объекта M-графа, в который добавляются все вершины и рёбра из текущего графа Выход: true – в случае удачного преобразования, иначе false Постусловия: внутреннее представление графа - М Добавление ребра Вход: адрес дескриптора исходящей вершины OutVDescriptor, и входящей InVDescriptor Предусловия: OutVDescriptor не равно InVDescriptor ребро OutVDescriptor - InVDescriptor не существует Процесс: вставка ребра соединяющего вершины pOutVDescriptor и InVDescriptor Выход: адрес дескриптора ребра – ребро добавлено, иначе NULL Постусловия: ребро OutVDescriptor - InVDescriptor добавлено в граф Удаление ребра Вход: адрес дескриптора исходящей вершины OutVDescriptor, и входящей pInVDescriptor Предусловия: ребро OutVDescriptor - InVDescriptor существует Процесс: удаление ребра соединяющего вершины OutVDescriptor и InVDescriptor Выход: true – ребро удалено, иначе false Постусловия: ребро OutVDescriptor - InVDescriptor удалено из графа Добавление вершины Вход: нет Предусловия: нет Процесс: создание и вставка новой вершины Выход: адрес дескриптора вершины – вершина добавлена, иначе NULL Постусловия: вершина добавлена в граф Добавление вершины Вход: адрес дескриптора вершины VDescriptor Предусловия: нет Процесс: вставка новой вершины Выход: нет Постусловия: нет Удаление вершины Вход: адрес дескриптора вершины VDescriptor Предусловия: вершина VDescriptor существует Процесс: удаление вершины VDescriptor и всех рёбер, связанных с ней Выход: true – вершина удалена, иначе false Постусловия: вершина и все связанные с ней ребра удалены из графа Опрос ребра Вход: адрес дескриптора исходящей вершины OutVDescriptor и входящей InVDescriptor Предусловия: ребро OutVDescriptor - InVDescriptor существует Процесс: получение ребра, соединяющего вершины OutVDescriptor и InVDescriptor Выход: дескриптор ребра – ребро существует, иначе NULL Постусловия: нет КОНЕЦ АТД |