AGraph: библиотека классов для работы с помеченными графами
AGraph: библиотека классов для работы с помеченными графами§1. Актуальность разработки библиотек для работы с графами К настоящему времени накоплен большой опыт решения теоретико-графовых задач на ЭВМ. Программы для решения многих задач можно найти в глобальной сети Интернет. В то же время, использование независимо разработанных программ сопряжено с большими трудностями. К их числу относятся как общие, не зависящие от предметной области, технические проблемы (различные языки программирования, несовместимость программных и аппаратных средств), так и проблемы, связанные со спецификой теоретико-графовых задач (использование различных внутренних представлений графов). В связи с этим актуальной задачей является разработка более или менее универсальных библиотек, которые, с одной стороны, предоставляли бы пользователю высокоуровневые средства для работы с графами, а с другой, избавляли его от необходимости ручного программирования рутинных операций ввода-вывода или преобразований между различными внутренними представлениями графов. Разработка универсальной библиотеки для работы с графами является сложной задачей. Одной из проблем является большое разнообразие задач теории графов. Поскольку теоретические исследования и разработка новых алгоритмов непрерывно продолжаются, очевидно, что никакая библиотека не сможет решать все существующие задачи. Другой проблемой является обеспечение эффективности. Нередко существует несколько алгоритмов для решения одной и той же задачи, причем не всегда можно указать алгоритм, оптимальный во всех случаях: для одних графов более эффективным может быть один алгоритм, для других - другой. Разработчик универсальной библиотеки обычно не может позволить себе реализацию нескольких алгоритмов для решения одной задачи, поэтому ему приходится идти на компромиссы между эффективностью и универсальностью. При разработке библиотек для работы с графами возникают также многочисленные технические трудности. Для приемлемой с точки зрения эффективности реализации многих алгоритмов программисту необходимо иметь в своем распоряжении такие структуры данных, как динамические массивы, списки, стеки, очереди, приоритетные очереди, деревья поиска. Реализация всех необходимых структур данных в рамках одной библиотеки вряд ли возможна и оправдана, поэтому универсальная библиотека для работы с графами требует серьезной программной "инфраструктуры" в виде других библиотек. Перечисленные проблемы могут вызвать сомнения относительно целесообразности создания универсальных библиотек для работы с графами, однако существуют весомые аргументы в пользу их создания. Во-первых, реализованные в подобной библиотеке базовые алгоритмы могут служить хорошей основой для создания более специализированных алгоритмов и программ, направленных на решение конкретных прикладных задач. Во-вторых, соображения эффективности не всегда являются определяющими - постоянный рост производительности ЭВМ все чаще выводит на первый план технологичность и скорость разработки программного обеспечения (разумеется, это не означает, что программист не должен стремиться к эффективному использованию вычислительных ресурсов). Наряду с "промышленным" программирования, универсальные библиотеки для работы с графами могут применяться в учебных целях, а также для поддержки теоретических исследований, связанных с алгоритмами и программами решения задач теории графов. В обоих случаях универсальность проблемной ориентации библиотеки более важна, чем максимальная эффективность реализованных в ней алгоритмов. §2. Объектно-ориентированные библиотеки для работы с графами 1. Преимущества ООП при создании библиотек для работы с графами При создании "первого поколения" библиотек для работы с графами использовались языки программирования Fortran, Algol, PL\1, затем С [1]. Для решения теоретико-графовых задач использовались и непроцедурные языки, такие, как язык функционального программирования LISP и логического программирования PROLOG, однако из-за недостаточной эффективности и технологических трудностей разработки больших программных систем на этих языках эти языки не подходят для создания универсальных библиотек. С развитием объектно-ориентированного программирования (ООП) началась разработка объектно-ориентированных библиотек для работы с графами. Использование средств ООП при решении теоретико-графовых задач дает существенные преимущества по сравнению с традиционным структурным подходом, поскольку сам граф, его вершины и ребра являются "готовыми" объектами, данными самой природой задачи. К достоинствам ООП, которые наиболее ярко проявляются при работе с графами, можно отнести следующее: программный код становится более компактным, улучшается его читаемость; при реализации алгоритмов появляется возможность абстрагироваться от деталей внутреннего представления графа; внутреннее представление графа можно менять в широких пределах без влияния на "высокоуровневые" составляющие библиотеки; легко решается проблема "привязки" данных к вершинам и ребрам графа. 2. Обзор существующих ОО-библиотек для работы с графами В настоящее время существует несколько объектно-ориентированных библиотек, предоставляющих средства для работы с графами. Среди них можно отметить: LEDA (Library of Efficient Data types and Algorithms); GTL (Graph Template Library, University of Passau); GTL (Graph Template Library, Евгений Цыпнятов, Нижний Новгород), далее - GTL (Н-Новгород). Все эти библиотеки написаны на языке C++. Библиотека LEDA (последняя версия - 3.8) [2] разрабатывается с 1988 г. в Институте Информатики Макса Планка (Сарабрюккен, ФРГ). Библиотека предлагает различные абстрактные типы данных (стеки, очереди, приоритетные очереди, отображения, списки, множества, разбиения, словари, интервальные множества и др.), специализированные числовые типы данных (рациональные числа, большие вещественные числа, алгебраические числа и др.), графы и вспомогательные структуры данных для работы с графами. В LEDA реализованы алгоритмы решения ряда комбинаторных, алгебраических, геометрических и теоретико-графовых задач, средства графического ввода и вывода. Институт Информатики Макса Планка бесплатно предоставляет библиотеку, включая исходные тексты, по лицензии, которая дает право использовать LEDA для академических исследований и/или обучения, но не допускает коммерческое использование. Программный интерфейс приложений (API) для работы с графами, реализованный в LEDA, послужил образцом для создания других библиотек, в том числе GTL (University of Passau) (последняя версия - 0.3.1). В отличие от LEDA, GTL базируется на STL (C++ Standard Template Library) - мощной библиотеке классов-контейнеров и стандартных алгоритмов. Существует GTL-Java интерфейс, позволяющий Java-программам использовать графовые структуры данных и алгоритмы, реализованные в GTL. По своим функциональным возможностям и надежности GTL в настоящее время значительно уступает LEDA. Библиотека GTL (Евгений Цыпнятов, последняя версия - 1.0R8) [3] существенно отличается от других библиотек по своей идеологии. Во-первых, библиотека поддерживает несколько внутренних представлений для графов - в виде массивов вершин и ребер, списков смежности, матрицы смежности. Существует также представление, которое объединяет все три перечисленные выше структуры хранения графов и обеспечивает их автоматическую синхронизацию. Представления реализованы в виде шаблонных классов; выбор нужного представления осуществляется при создании графа. Во-вторых, библиотека использует оригинальный способ придания необходимых "свойств" вершинам и ребрам графа (фактически, "свойства" - это атрибуты вершин и ребер) - механизм классов-"привкусов" (Flavor). Этот способ основан на использовании множественного наследования и параметризуемых (шаблонных) классов графов. Механизм "привкусов" будет рассмотрен при сравнении с аналогичными средствами библиотек LEDA и AGraph. В настоящее время GTL доступна только на платформе Win32, т.к. она существенно зависит от библиотеки MFC (Microsoft Foundation Classes). §3. Библиотека AGraph ...
Другие файлы:
Практикум по КОМПАС-3D V8: машиностроительные библиотеки
В книге излагаются основы работы с библиотеками KOMПAC-3D V8. их добавление и подключение.Подробно описывается работа с наиболее используемыми библиот...
Игры на графах
Книга ученого из ГДР, содержащая изложение теории одного из классов игр, в которых множества позиций с допустимыми в них ходами описываются ориентиров...
Педагогический потенциал школьной библиотеки и ее роль в воспитательной работе современной школы
Библиотека и педагогическая система школы. Библиотекарь как участник педагогического процесса, его функциональные особенности и специфика работы. Педа...
Библиотека Крокодила. Книжная серия в 4 книгах
Библиотека Крокодила - серия юмористических и сатирических брошюр, библиотека знаменитого журнала Крокодил.Брошюрки маленькие, но смешные и с веселыми...
Разработка архитектуры программной системы "Библиотека"
Обзор существующих объектных архитектур. Архитектура программного обеспечения. Создание веб-сервиса "Библиотека", предоставляющего механизмы работы с...
