Библиотека для обработки графов "G-Lib"

Аннотация

Библиотека "G-Lib" представляет набор объектов для хранения и обработки графовых и сетевых структур дан-ных. Способ реализации алгоритмов обработки графов с помощью объектов библиотеки допускает инвариантность к способу задания графа. В библиотеке реализованы четыре основных способа задания графа: список ребер, матрица смежности, список инцидентности вершин входящих дуг, список инцидентности вершин выходящих дуг.

Введенние

Граф - отображение множества вершин на само себя, можно задать например графически в виде кружков вершин и соединяющих их стрелок дуг. Используя более простые структуры данных - массивы и матрицы можно указать следующие четыре способа задания графа:

- список рёбер (или направленных дуг), то есть список пар инцидентных вершин

- матрица смежности - квадратная матрица, каждый элемент которой соответствует возможному в графе одному ребру между двумя любыми вершинами

- для каждой вершины указать список вершин исхода входящих в неё рёбер

- для каждой вершины указать список вершин входа выходящих из неё рёбер.

Компонентные функции классов графов позволяют :

- создавать граф с заданным количеством вершин и количеством подграфов

- выполнять над подграфами следующие действия :

добавлять, удалять, включать и исключать из обрабатываемого суграфа

- определить, включен ли в обрабатываемый суграф подграф и выбрать данные подграфа для обработки

- устанавливать и получать любые дополнительные параметры графа

- устанавливать количество вершин в графе

- менять местами номера двух заданных вершин

- вставлять в граф вершину с заданным номером

- удалять из графа вершину с заданным номером

- получать количество инцидентных вершине ребер

- удалять ребра заданной вершины

- устанавливать и получать любые дополнительные параметры вершин

- получать количество ребер в выбранных подграфах

- устанавливать ребро и удалять выбранное

- перемещать выбранное ребро в одном подграфе

- выбирать ребро : по номеру, по инцидентным вершинам, по инцидентным вершинам и номеру компоненты мультиребра, по номеру вершины исхода и номеру выходящего из нее ребра, по номеру вершины входа и номеру входящего в нее ребра.

- получать графовые параметры выбранного ребра :

порядковый номер ребра,

вершины инцидентности ребра,

номер компоненты в мультиребре,

номер ребра среди выходящих из вершины его исхода,

номер ребра среди входящих в вершину его входа,

количество ребер инцидентных обеим вершинам

выбранного ребра

- устанавливать и получать любые дополнительные

параметры выбранного ребра

- методы-итераторы для обработки ребер выбранного суграфа позволяют :

вызывать функцию итератора для каждого ребра

вызывать функцию итератора для каждой компоненты мультиребра

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

вызывать функцию итератора для каждого ребра выходящего из заданной вершины

вызывать функцию итератора для каждого ребра входящего в заданную вершину.

Алгоритмы обработки графов обычно состоят из перебора вершин и относящихся к ним ребер, что в библиотеке можно реализовать при помощи функций передаваемых как параметер методам итераторам. Это позволяет в большинстве случаев выполнять алгоритмы обработки графов инвариантно к способу задания графа. В реальных, не математических задачах, граф может быть нужно разбить на подграфы и обрабатывать суграф, состоящий из нескольких выбранных подграфов, что поддерживается библиотечными классами, как и концепции позволяющие при изменении графовой модели сохранять связь с данными реальной задачи.

Несколько десятков вспомогательных алгоритмов и классы списков ребер и вершин реализуют часто используемые при обработке графов операции, что позволяет быстро приступить к решению основной задачи.

Краткое описание модулей библиотеки

Модуль G :

описание типов из словаря предметной области, констант и абстрактного типа графа

Модуль GImages :

описание типов реализующих четыре основных представления графа:

TListG - список ребер или дуг

TAdjacencyMatrixG - матрица смежности

TIncomIncidenceG - список инцидентности вершин входящих дуг

TOutgoIncidenceG - список инцидентности вершин выходящих дуг

Модуль GLance :

описание типов реализующих вспомогательные классы :

TNodeList - список вершин

TLNodeList - список списков вершин

TEdgeList - список ребер

TLEdgeList - список списков ребер

TMultiEdgeList - список мультиребер

TLMultiEdgeList - список списков мультиребер

TEdgeNumList- список номеров ребер

TLEdgeNumList - список списков номеров ребер

TGraphList- список указателей на графы

Модуль GraphL:

TCListG - граф список ребер или дуг

TCCListG - граф список ребер или дуг с разделением на подграфы

Модуль GraphB:

TBitMatrixG - граф битовая матрица смежности

TСBitMatrixG - граф битовая матрица с смежности с разделением на подграфы

Модуль GraphD:

TDigitMatrixG - граф числовая матрица смежности

TСDigitMatrixG - граф числовая матрица смежности с разделением на подграфы

Модуль GraphI:

TCInIncG - граф список инцидентности вершин входящих дуг

TСCInIncG - граф список инцидентности вершин входящих дуг с разделением на подграфы

Модуль GraphO:

TСOutIncG - граф список инцидентности вершин выходящих дуг

TССOutIncG - граф список инцидентности вершин выходящих дуг с разделением на подграфы

Модуль GraphMG:

TMultiG - граф подграфов

Модуль SupplyG :

описание функций реализующих вспомогательные алгоритмы

Модуль BitField :

описание объекта, позволяющего обрабатывать битовое поле произвольной изменяемой длины TBitField, а также функции чтения, установки, пересчета, копирования, инвертации, сравнения битовых полей

Модуль Matrix :

TBitFieldList - список объектов TBitField

TBitMatrix - M x N битовая матрица

TBitMatrixRows - с выделением памяти отдельно для каждой строки