Разработка абстрактного типа данных «Простой, статический граф», страница 2

5.1 Формат АТД «Простой граф»

АТД “Простой статический граф”:

            ОБЩАЯ ХАРАКТЕРИСТИКА:

Простой статический граф представляет собой совокупность множества вершин и множества ребер, соединяющих вершины. Каждая вершина графа имеет номер. Ребра графа могут быть направленными (ориентированный граф), и ненаправленными (неориентированный граф). Каждое ребро хранит вес и данные указанных типов TypeWeight и TypeData. Граф может иметь две формы представления: L-тип или M-тип. В графе запрещены петли и параллельные рёбра из одной вершины. При создании экземпляра графа можно задать количество вершин и ребер, которые создадутся случайным образом. После создания, структуру графа можно изменять с помощью соответствующих операций вставки и удаления вершин и ребер. Коэффициент насыщенности графа изменяется в интервале [0,1].

            ДАННЫЕ:

Параметры:

m_graph – переменна хранящая объект L или M графа

           Структура хранения коллекции:

  Реализована в двух вариантах:

·  L-граф – граф представлен с помощью списков смежности: с каждой вершиной графа, связывается список исходящих из нее ребер.

·  M-граф – граф представлен в виде матрицы смежности: на пересечении j-ого столбца и i-ой строки находится указатель на дескриптор ребра или 0, если ребра не нет, соединяющего i и j вершины.

ОПЕРАЦИИ:

Конструктор

Вход:   нет

Предусловия: нет

Процесс: создание внутреннего пустого объекта L-граф, установка свойства не ориентированности

Выход: нет

Постусловия: создание пустого неориентированного L-графа

Конструктор

Вход:   v– число вершин,  e-число рёбер,  GO – признак ориентированности графа, TG – тип графа

Предусловия: e не превышает максимально допустимого количества рёбер для графа с количеством вершин countVertex, в противном случае количество вершин будет равно максимально допустимому

Процесс: создание внутреннего объекта графа заданного типа и вставка заданного числа вершин и рёбер

Выход: нет

Постусловия: создание графа заданного типа и ориентированности, с количеством вершин countVertex и количеством ребер countEdge

Опрос числа вершин в графе

Вход: нет

              Предусловия: нет

              Процесс: чтение значения количества вершин

              Выход: количество вершин в графе

              Постусловия: нет

Опрос числа рёбер в графе

Вход: нет

              Предусловия: нет

              Процесс: чтение значения количества рёбер

              Выход: количество рёбер в графе

              Постусловия: нет

Опрос типа графа

              Вход: нет

              Предусловия: нет

              Процесс: чтение значения типа графа

              Выход: тип графа (ориентированный/неориентированный)

              Постусловия: нет

Опрос формы представления графа

              Вход: нет

              Предусловия: нет

              Процесс: чтение значения формы представления графа

Выход: форма представления графа (L-граф/M-граф)

Постусловия: нет

                            Коэффициент насыщенности графа

Вход: нет

Предусловия: нет

Процесс: расчёт коэффициента насыщенности графа

Выход: значение коэффициента насыщенности графа

Постусловия: нет

                            Преобразования графа к L-графу

Вход: нет

                            Предусловия: граф не является L-графом

Процесс: создание нового внутреннего объекта L-графа, в который добавляются все вершины и рёбра из текущего графа

Выход: true – в случае удачного преобразования, иначе false

Постусловия: внутреннее представление графа - L

                            Преобразования графа к M-графу

Вход: нет

                            Предусловия: граф не является M-графом

Процесс: создание нового внутреннего объекта M-графа, в который добавляются все вершины и рёбра из текущего графа

Выход: true – в случае удачного преобразования, иначе false

Постусловия: внутреннее представление графа - М

                            Добавление ребра

Вход: номер исходящей вершины v1, и входящей v2