Введение Описание Функции Цены Библиотека для обработки графов Объектно-ориентированная C ++ классы Аннотация Особенности. - презентация

1 Введение Описание Функции Цены Библиотека для обработки графов Объектно-ориентированная C ++ классы Аннотация Особенности

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

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

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

5 Краткое описание модулей библиотеки Модуль G : описание абстрактного типа графа Модуль GImages : описание типов реализующих четыре основных представления графа Модуль GLance : описание типов реализующих вспомогательные классы Модуль GraphL: граф список ребер или дуг Модуль GraphB: граф битовая матрица смежности Модуль GraphD: граф числовая матрица смежности Модуль GraphI: граф список инцидентности вершин входящих дуг Модуль GraphO: граф список инцидентности вершин выходящих дуг Модуль GraphMG: граф подграфов Модуль SupplyG : описание функций реализующих вспомогательные алгоритмы Модуль BitField : описание объекта, позволяющего обрабатывать битовое поле Модуль BitMatrix : объекты битовых матриц Модуль Strings : описание функций обработки строк Модуль ErrorDia : описание функций диалога с пользователем при обработке исключительных ситуациях

6 Функциональность модулей

7 Относительные цены: Цена библиотеки Цена модуля Цена функции 0.73 Цена строки 0.030