§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 (Н-Новгород).
Похожий материал - Курсовая работа: UNIX System V
Все эти библиотеки написаны на языке 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
Очень интересно - Реферат: Классификация оперативной памяти
1. Общая характеристика
При разработке библиотеки AGraph были поставлены следующие цели:
- охват широкого круга теоретико-графовых задач;
- простота использования;
- эффективность.
Библиотека AGraph написана на языке Object Pascal [4], который используется в Delphi - среде быстрой разработки приложений (RAD) фирмы Inprise (бывшей Borland), и является, вероятно, единственной развитой библиотекой для работы с графами на Object Pascal. В то же время, используемый язык программирования - не главное отличие AGraph от других библиотек. При необходимости библиотека AGraph может быть переписана с использованием таких объектно-ориентированных языков программирования, как C++, Eiffel или Java. Перенос облегчается тем обстоятельством, что AGraph не использует стандартную библиотеки классов Delphi VCL (Visual Component Library), за исключением классов исключительных ситуаций (Exception).
В пользу выбора языка Object Pascal как средства создания библиотеки для работы с графами можно привести следующие соображения. К настоящему времени разработано немало объектно-ориентированных языков программирования (ООЯП): Smalltalk, C++, Java, Object Pascal, Eiffel, Oberon-2, Modula-3 и другие. Если исходить из достоинств и недостатков самих языков программирования, не принимая во внимание распространенность языка и качество его конкретных реализаций, то одним из лучших "кандидатов", на мой взгляд, является Eiffel. Однако, если учитывать конкретную платформу, которая имеется в распоряжении (персональный компьютер на процессоре семейства Intel 386, работающий под управлением операционных систем Windows или Linux), а также практически доступные системы программирования коммерческого качества, то выбор значительно сужается: остаются языки C++, Java и Object Pascal. Языки Smalltalk и Java не подходят по соображениям эффективности. Наиболее распространенный в настоящее ООЯП, C++, поддерживается на большинстве платформ и является мощным языком программирования. Важное значение имеет существование стандарта языка C++ (к сожалению, многие компиляторы C++ не вполне соответствуют этому стандарту). К недостаткам С++ можно отнести его значительно большую, по сравнению с Object Pascal, сложность. Учитывая цели, которые ставились при разработке библиотеки AGraph, в первую очередь - соображения простоты использования, выбор был сделан в пользу Object Pascal.
Язык Object Pascal в той его версии, которая реализована в Delphi, также является развитым объектно-ориентированным языком программирования. По сравнению с ранними версиями языка (Turbo Pascal и Borland Pascal), в Object Pascal некоторые изменения претерпела объектная модель, был реализован механизм свойств объектов (object property), добавлены средства обработки исключительных ситуаций (конструкции try...except и try...finally), появилась возможность передавать в процедуры и функции переменное количество параметров (open array параметры). В Delphi 4.0 появились динамические массивы, перегрузка (overloading) процедур и функций, а также возможность указывать для параметров процедур и функций значения, принимаемые по умолчанию. Среди важных языковых средств C++, которые не реализованы в Object Pascal, следует отметить множественное наследование и механизм шаблонов (templates). Последний недостаток удалось частично преодолеть с помощью "псевдошаблонов".
Вам будет интересно - Курсовая работа: Основы конфигурирования сетевых файловых систем (на примере NFS)
2. Библиотека Vectors
Создание серьезных программных систем в настоящее время практически невозможно без использования вспомогательных программных компонент, реализующих базовые структуры данных и алгоритмы. Примером такой компоненты для C++ является стандартная библиотека шаблонов (С++ STL). Рассмотренные ранее С++-библиотеки для работы с графами демонстрируют различные подходы относительно создания или использования подобных базовых средств: в LEDA все необходимые структуры данных были реализованы "с нуля", библиотека GTL (University of Passau) базируется на C++ STL, библиотека GTL (Н-Новгород) основана на MFC 4.x.
При разработке библиотеки AGraph также возникла необходимость в базовых программных средствах. Поскольку готовых средств такого рода для Object Pascal не существовало (библиотека визуальных компонент Delphi VCL ориентирована на решение других задач), пришлось создавать их самостоятельно. Реализованные в ходе этой работы базовые структуры данных и алгоритмы вошли в состав библиотеки Vectors. В библиотеке реализованы векторы (динамические массивы) на базе основных типов Object Pascal, в том числе на базе всех целых и вещественных типов, логических переменных и строк. Векторы поддерживают большое количество операций; некоторые из которых являются общими для всех векторов, другие зависят от типа элементов данного вектора. В состав библиотеки входит также ряд производных и вспомогательных классов: разреженные векторы, матрицы, сбалансированные деревья поиска, приоритетные очереди, словари, потоки в памяти, файловые потоки и др.
При написании библиотеки Vectors учитывались соображения эффективности, надежности и переносимости. Многие векторные операции реализованы в нескольких вариантах: на Object Pascal и на встроенном ассемблере Object Pascal. Выбор между вариантами на Object Pascal и встроенном ассемблере осуществляется с помощью директив условной компиляции. Если программа компилируется в режиме, разрешающем использование ассемблерных вариантов, то при запуске программы средства времени исполнения автоматически определяют расширенные возможности процессора (в настоящее время проверяется поддержка MMX-инструкций) и выбирают наиболее эффективный вариант реализации той или иной операции с учетом возможностей процессора.
Для более эффективного поиска ошибок в прикладных программах библиотека поддерживает отладочный режим (также включаемый соответствующей директивой компиляции), в котором методы классов библиотеки осуществляют максимально полную проверку выполнения предусловий и корректности передаваемых им параметров. Кроме того, в отладочном режиме осуществляется контроль над операциями создания и уничтожения объектов, относящихся к классам библиотеки. Если при завершении программы какие-либо из этих объектов не уничтожаются, то пользователю выдается запрос на запись списка неуничтоженных объектов в файл.
Похожий материал - Курсовая работа: Служба удаленного доступа (RAS) Windows NT
Серьезным препятствием при написании библиотеки Vectors стало отсутствие в языке Object Pascal средств, аналогичных шаблонам C++. Очевидно, что независимая реализация векторов, отличающихся лишь типом элементов, привела бы к дублированию программного кода, многочисленным ошибкам и, в конечном счете, грозила бы потерей управляемости проектом. Решением данной проблемы могло бы стать использование внешнего макропроцессора, однако это значительно усложнило бы как разработку, так и использование библиотеки. Вместо этого в библиотеке был применен механизм "псевдошаблонов", основанный исключительно на средствах Object Pascal: директиве INCLUDE и переопределении типов.
3. Внутреннее представление графов
Существуют различные способы внутреннего представления графов в оперативной памяти ЭВМ, в том числе в виде списков (массивов) вершин и ребер, списков (массивов) смежности, матриц смежности, а также в виде комбинаций этих структур хранения. Выбор внутреннего представления оказывает решающее влияние на эффективность выполнения различных операций над графами и во многом определяет "технологию" использования той или иной библиотеки в прикладных программах.
Ниже перечисленные структуры хранения графов будут рассмотрены более подробно, но перед этим необходимо сделать следующее замечание. В теории графов вершины и ребра графов, как правило, лишены индивидуальности: при таком подходе граф можно задать, например, булевской матрицей смежности, где логическая единица на пересечении i-ой строки и j-го столбца означает существование ребра (или дуги) между i-ой и j-ой вершинами графа. В то же время, во всех рассматриваемых библиотеках вершины и ребра графа считаются уникальными объектами (здесь термин "объект" употребляется в контексте объектно-ориентированного программирования), которые различаются, по крайней мере, тем, что каждый из них занимает отдельный участок в оперативной памяти ЭВМ. Объект-вершина может содержать или не содержать какие-либо данные; объект-ребро содержит, как минимум, указатели на инцидентные ему вершины. Если подходить с технологической точки зрения, то наличие уникальных объектов-вершин и объектов-ребер повышает удобство реализации и эффективность многих алгоритмов (хотя и неэкономично в смысле расхода оперативной памяти). Существует и более фундаментальная причина: при решении прикладных задач вершины графа, а иногда и его ребра, соответствуют реальным объектам предметной области. Таким образом, структуры хранения графов в объектно-ориентированной библиотеке для работы с графами обеспечивают хранение не только "математического" графа, но и объектов, представляющих вершины и ребра этого графа. Еще одно замечание необходимо сделать относительно использования списков и/или массивов: эти структуры данных будут считаться взаимозаменяемыми, пока изложение не коснется конкретных библиотек.