Библиотека "g-lib" представляет набор объектов для хранения и обработки графовых и сетевых структур дан-ных. Способ реализации алгоритмов обработки графов с помощью объектов библиотеки допускает инвариантность к способу задания графа



Скачать 62.13 Kb.
Дата11.10.2012
Размер62.13 Kb.
ТипДокументы


Аннотация
Библиотека "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, а также функции чтения, установки, пересчета, копирования, инвертации, сравнения битовых полей
Модуль BitMatrix :

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

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

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

Модуль Strings :

описание функций обработки строк

Модуль ErrorDia :

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

Похожие:

Библиотека \"g-lib\" представляет набор объектов для хранения и обработки графовых и сетевых структур дан-ных. Способ реализации алгоритмов обработки графов с помощью объектов библиотеки допускает инвариантность к способу задания графа iconИспользование цифровой фотограмметрии для моделирования биоценозов и объектов окружающей среды
В докладе приводятся особенности математических методов обработки стереоизображений для изучения различных биологических объектов,...
Библиотека \"g-lib\" представляет набор объектов для хранения и обработки графовых и сетевых структур дан-ных. Способ реализации алгоритмов обработки графов с помощью объектов библиотеки допускает инвариантность к способу задания графа icon2. Разновидности графовых моделей сложных объектов
Целью настоящей работы является изучение основных методов формального представления объектов проектирования разновидностями графовых...
Библиотека \"g-lib\" представляет набор объектов для хранения и обработки графовых и сетевых структур дан-ных. Способ реализации алгоритмов обработки графов с помощью объектов библиотеки допускает инвариантность к способу задания графа iconВопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры
Способы задания графов. Матричный способ задания. Свойства матриц смежности и инцидентности. Привести примеры
Библиотека \"g-lib\" представляет набор объектов для хранения и обработки графовых и сетевых структур дан-ных. Способ реализации алгоритмов обработки графов с помощью объектов библиотеки допускает инвариантность к способу задания графа iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
Библиотека \"g-lib\" представляет набор объектов для хранения и обработки графовых и сетевых структур дан-ных. Способ реализации алгоритмов обработки графов с помощью объектов библиотеки допускает инвариантность к способу задания графа iconИспользование многомерных деревьев для обработки многомерной информации
Рассмотрена проблема выбора и использования многомерных структур данных в качестве основы системы хранения многомерной информации....
Библиотека \"g-lib\" представляет набор объектов для хранения и обработки графовых и сетевых структур дан-ных. Способ реализации алгоритмов обработки графов с помощью объектов библиотеки допускает инвариантность к способу задания графа iconСложность алгоритмов. Уметь оценивать сложность всех алгоритмов и программ
Графы. Основные способы хранения графов, их преимущества и недостатки, количество необходимой памяти. Сложности алгоритмов над разными...
Библиотека \"g-lib\" представляет набор объектов для хранения и обработки графовых и сетевых структур дан-ных. Способ реализации алгоритмов обработки графов с помощью объектов библиотеки допускает инвариантность к способу задания графа iconРабочая программа лекционного курса «Информатика»
Задача курса состоит в выработке у студентов навыков использования структур данных и методов разработки алгоритмов на примере классических...
Библиотека \"g-lib\" представляет набор объектов для хранения и обработки графовых и сетевых структур дан-ных. Способ реализации алгоритмов обработки графов с помощью объектов библиотеки допускает инвариантность к способу задания графа iconМетодические указания по выполнению лабораторных работ по дисциплине «Компьютерная графика»
Особый акцент делается на практическое применение изучаемых алгоритмов. Также особое внимание уделяется современным алгоритмам обработки...
Библиотека \"g-lib\" представляет набор объектов для хранения и обработки графовых и сетевых структур дан-ных. Способ реализации алгоритмов обработки графов с помощью объектов библиотеки допускает инвариантность к способу задания графа icon«Архитектура пк»
Устройство ввода – предназначено для реализации алгоритмов обработки, накопления и передачи информации
Библиотека \"g-lib\" представляет набор объектов для хранения и обработки графовых и сетевых структур дан-ных. Способ реализации алгоритмов обработки графов с помощью объектов библиотеки допускает инвариантность к способу задания графа iconЭлектронная и туннельная микроскопия
...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org