Курсовая: AGraph: библиотека классов для работы с помеченными графами - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

AGraph: библиотека классов для работы с помеченными графами

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 437 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной курсовой работы

Узнайте стоимость написания уникальной работы

AGraph: библиотека классов для работы с п омеченными графами § 1. Ак туальность разработки библиотек для работы с графами К настоящему вр емени накоплен большой опыт решения теоретико -графовых задач на ЭВМ . Программы для реше ния многих задач можно найти в глобальной сети Интернет . В то же время , использо вание независимо раз работанных программ с опряжено с большими трудностями . К их числ у относятся как общие , не зависящие от предметной области , технические проблемы (разли чные языки программирования , несовместимость прог раммных и аппаратных средств ), так и пробл емы , связанные с о спецификой теорети ко-графовых задач (использование различных внутрен них представлений графов ). В связи с этим актуальной задачей является разработка более или менее универсальных библиотек , которые , с одной стороны , предоставляли бы пользоват елю высокоу р овневые средства для работы с графами , а с другой , избавляли его от необходимости ручного программирования рутинных операций ввода-вывода или преобразо ваний между различными внутренними представления ми графов . Разработка универсальной библиотеки для р абот ы с графами является сложной зада чей . Одной из проблем является большое раз нообразие задач теории графов . Поскольку теор етические исследования и разработка новых алг оритмов непрерывно продолжаются , очевидно , что никакая библиотека не сможет решать все сущ е ствующие задачи . Другой проблем ой является обеспечение эффективности . Нередко существует несколько алгоритмов для решения одной и той же задачи , причем не вс егда можно указать алгоритм , оптимальный во всех случаях : для одних графов более эф фективным может быть один алгоритм , для других - другой . Разработчик универсальной библиотеки обычно не может позволить себе реализацию нескольких алгоритмов для решения одной задачи , поэтому ему приходится идти на компромиссы между эффективностью и ун иверсальностью . При разработке библиотек для работы с графами возникают также м ногочисленные технические трудности . Для приемлем ой с точки зрения эффективности реализации многих алгоритмов программисту необходимо имет ь в своем распоряжении такие структуры да нных , как динамич е ские массивы , сп иски , стеки , очереди , приоритетные очереди , дере вья поиска . Реализация всех необходимых струк тур данных в рамках одной библиотеки вряд ли возможна и оправдана , поэтому универса льная библиотека для работы с графами тре бует серьезной програм м ной "инфрастру ктуры " в виде других библиотек . Перечисленные проблемы могут вызвать сомн ения относительно целесообразности создания унив ерсальных библиотек для работы с графами , однако существуют весомые аргументы в пользу их создания . Во-первых , реализова нные в подобной библиотеке базовые алгоритмы могут служить хорошей основой для создания бол ее специализированных алгоритмов и программ , направленных на решение конкретных прикладных задач . Во-вторых , соображения эффективности не всегда являются определяющ и ми - пост оянный рост производительности ЭВМ все чаще выводит на первый план технологичность и скорость разработки программного обеспечения (разумеется , это не означает , что программис т не должен стремиться к эффективному исп ользованию вычислительных ресур с ов ). Н аряду с "промышленным " программирования , универсаль ные библиотеки для работы с графами могут применяться в учебных целях , а также для поддержки теоретических исследований , связанн ых с алгоритмами и программами решения за дач теории графов . В обоих сл у чаях универсальность проблемной ориентации библи отеки более важна , чем максимальная эффективн ость реализованных в ней алгоритмов . § 2. Объектно-ориентированные библиотек и для работы с графами 1. Преимущества ООП при создании библиоте к для работы с графами При создании "пе рвого поколения " библиотек для работы с гр афами использовались языки программирования Fortran, Algol, PL\ 1, затем С [ 1 ]. Для решения теоретико-графовых задач использовал ись и непроцедурные языки , такие , как язык функционального программирования LISP и логического программирования PROLOG, однако из-за недостаточной эффективности и технологических трудностей разработки больших программных систем на э тих языках эти языки не подходят для создания универсальных библиотек . С развитием объектно-ориентированного програм мирования (ООП ) началась разработка объектно-ориент ированных библиоте к для работы с граф ами . Использование средств ООП при решении теоретико-графовых задач дает существенные преи мущества по сравнению с традиционным структур ным подходом , поскольку сам граф , его верш ины и ребра являются "готовыми " объектами , данными самой пр и родой задачи . К достоинствам ООП , которые наиболее ярко п роявляются при работе с графами , можно отн ести следующее : 1. программный код становится более ко мпактным , улучшается его читаемость ; 2. при реализации алгоритмо в появляется возможность абстрагирова ться от деталей внутреннего представления графа ; 3. внутреннее представление графа можно менять в широких пределах без влияния на "высокоуровневые " составляющие библиотеки ; 4. легко решается проблема "привязки " данных к вершинам и ребрам графа. 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 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). Последний недостаток удалось частично преодолеть с помо щью "псевдошаблонов ". 2. Библиотека Vectors Создание серьезных программных систем в настоящее время практически невозможно без использования вспом огательных программных компонент , реализующих баз овые структуры данных и алгоритмы . Примером такой компоненты для C++ является стандартная библиотека шаблонов (С ++ STL). Рассмотренные ранее С + + -библиотеки для работы с гр афами демонстрируют различные подходы относитель но создания или использования подобных базовы х средств : в LEDA все необходимые структуры д анных были реализованы "с нуля ", библиотека GTL (University of Passau) базируется на C++ S T L, библиотека GTL (Н-Новгород ) основана на MFC 4.x. При разработке библиотеки AGraph также возникл а необходимость в базовых программных средств ах . Поскольку готовых средств такого рода для Object Pascal не существовало (библиотека визуальных компонент Del phi VCL ориентирована на решение других задач ), пришлось создавать их самостоят ельно . Реализованные в ходе этой работы ба зовые структуры данных и алгоритмы вошли в состав библиотеки Vectors. В библиотеке реализова ны векторы (динамические массивы ) на базе о сновных типов Object Pascal, в том числе на базе всех целых и вещественных типо в , логических переменных и строк . Векторы поддерживают большое количество операций ; некотор ые из которых являются общими для всех векторов , другие зависят от типа элементов дан н ого вектора . В состав биб лиотеки входит также ряд производных и вс помогательных классов : разреженные векторы , матриц ы , сбалансированные деревья поиска , приоритетные очереди , словари , потоки в памяти , файловые потоки и др . При написании библиотеки Vectors учитывались соображения эффективности , надежности и пере носимости . Многие векторные операции реализованы в нескольких вариантах : на Object Pascal и на в строенном ассемблере Object Pascal. Выбор между вариантами на Object Pascal и встроенном ассемблере осу щ ествляется с помощью директив условной компиляции . Если программа компилируется в режиме , разрешающем использование ассемблерных ва риантов , то при запуске программы средства времени исполнения автоматически определяют ра сширенные возможности процессора (в на стоящее время проверяется поддержка MMX-инструкций ) и выбирают наиболее эффективный вариант реализации той или иной операции с учетом возможностей процессора . Для более эффективного поиска ошибок в прикладных программах библиотека поддерживает отладочны й режим (также включаемый со ответствующей директивой компиляции ), в котором методы классов библиотеки осуществляют максима льно полную проверку выполнения предусловий и корректности передаваемых им параметров . Кро ме того , в отладочном режиме осуществляется контроль над операциями создания и уничтожения объектов , относящихся к классам библиотеки . Если при завершении программы какие-либо из этих объектов не уничтожаются , то пользователю выдается запрос на запис ь списка неуничтоженных объектов в файл . Серьезны м препятствием при написании библиотеки Vectors стало отсутствие в языке Object Pascal средств , аналогичных шаблонам C++. Очевидно , что независимая реализация векторов , отличающихся л ишь типом элементов , привела бы к дублиров анию программного кода , многоч и сленны м ошибкам и , в конечном счете , грозила бы потерей управляемости проектом . Решением д анной проблемы могло бы стать использование внешнего макропроцессора , однако это значите льно усложнило бы как разработку , так и использование библиотеки . Вместо этог о в библиотеке был применен механизм "псевдошаблонов ", основанный исключительно на сред ствах Object Pascal: директиве INCLUDE и переопределении типов . 3. Внутреннее пред ставление графов Существуют различны е способы внутреннего представления графов в опера тивной памяти ЭВМ , в том чис ле в виде списков (массивов ) вершин и р ебер , списков (массивов ) смежности , матриц смежн ости , а также в виде комбинаций этих с труктур хранения . Выбор внутреннего представления оказывает решающее влияние на эффективность выполнен и я различных операций на д графами и во многом определяет "технолог ию " использования той или иной библиотеки в прикладных программах . Ниже перечисленные структуры хранения гра фов будут рассмотрены более подробно , но п еред этим необходимо сделать следующее з амечание . В теории графов вершины и ребра графов , как правило , лишены индивидуал ьности : при таком подходе граф можно задат ь , например , булевской матрицей смежности , где логическая единица на пересечении i-ой ст роки и j-го столбца означает существование ре б ра (или дуги ) между i-ой и j-ой вершинами графа . В то же время , в о всех рассматриваемых библиотеках вершины и ребра графа считаются уникальными объектами (здесь термин "объект " употребляется в кон тексте объектно-ориентированного программирования ), ко торые различаются , по крайней мере , тем , что каждый из них занимает отдельный участок в оперативной памяти ЭВМ . Объект- вершина может содержать или не содержать какие-либо данные ; объект-ребро содержит , как ми нимум , указатели на инцидентные ему вершины . Если под х одить с технологической точки зрения , то наличие уникальных объекто в-вершин и объектов-ребер повышает удобство ре ализации и эффективность многих алгоритмов (х отя и неэкономично в смысле расхода опера тивной памяти ). Существует и более фундаментал ьная причи н а : при решении прикладн ых задач вершины графа , а иногда и его ребра , соответствуют реальным объектам предм етной области . Таким образом , структуры хранен ия графов в объектно-ориентированной библиотеке для работы с графами обеспечивают хранение не только "м а тематического " графа , но и объектов , представляющих вершины и ребра этого графа . Еще одно замечание необходимо сделать относительно использования списков и /или массивов : эти структуры данн ых будут считаться взаимозаменяемыми , пока из ложение не коснется ко н кретных би блиотек . Списки вершин и ребер Граф представляется в виде двух списков , один из которых содержит указатели на его вершины , второй - на ребра (как всегда , каждое ребро хр анит в себе указатели на инцидентные ему вершины ). Данная структура хранени я о беспечивает эффективное добавление в граф вер шин и ребер , а также итерацию по верши нам и ребрам . В то же время , это пр едставления неудобно , когда необходимо определить ребра , инцидентные заданной вершине графа . Списки смежности Граф представляется спи ском входящих в него вершин . В свою очередь , каждая вершина содержит спи сок инцидентных ей ребер (или списки входя щих и исходящих дуг в случае орграфов ). Данное представление обеспечивает эффективное добавление в граф вершин и ребер , итераци ю по вершинам г рафа и доступ к ребрам , инцидентным заданной вершине , но не поддерживает итерацию по ребрам графа . Матрицы смежности Граф задается к вадратной матрицей размерности NxN, где N - количество вершин в графе ; на пересечении i-го ст олбца и j-ой строки матрицы н аходится либо указатель на ребро , соединяющее верш ины i и j, если эти вершины инцидентны , либо nil, если они не инцидентны . Вершины могут либо храниться в отдельном списке , либо только в составе инцидентных им ребер ( в случае связных графов ). Это представ л ение удобно для реализации некоторых алгоритмов , но не обеспечивает эффективное добавление и удаление вершин . Кроме того , оно является самым неэкономичным по расходу памяти (за исключением графов , в которых количество ребер значительно превышает колич еств о вершин ). Из приведенного анализа видно , что каж дая из трех рассмотренных структур хранения графов обладает своими достоинствами и н едостатками . Внутреннее представление графов в универсальной библиотеке должно обеспечивать э ффективную реализацию большого числа разноо бразных алгоритмов , поэтому такие библиотеки используют комбинированные представления , либо , ка к это сделано в GTL (Н-Новгород ), позволяют явн о указать внутреннее представление при создан ии объекта-графа . Распространенным вариантом комбиниров анн ого внутреннего представления является объединен ие представлений в виде списков вершин /ре бер и списков смежности . Такая структура х ранения обеспечивает эффективное добавление и удаление вершин и ребер , итерацию по ве ршинам и ребрам и , в то же время , п о з воляет легко определить ребра , и нцидентные заданной вершине графа . Подобное п редставление используется в библиотеках LEDA и GTL (University of Passau). Библиотека AGraph также использует комбинированное представление , но вместо списков применяются динамич еские массивы указателей , реализо ванные в библиотеке Vectors (класс TPointerVector, он же TClassList). Сравнение списков и динамических массивов , реализованных в Vectors, с точки зрения эффктивно сти выполнения различных операций приведено в следующей табл и це (n обозначает ко личество вершин в графе , m - количество ребер ): Операция Эффективность Списки Мас сивы Добавление вершины | ребра O(1) O(n) | O(m) в худшем случае, O(1) в среднем Удаление вершины | ребра O(1) O(n) | O(m) Доступ к вершин е | ребру п о индексу O(n) | O(m) O(1) Списки позволяют эффективно добавлять и удалять вершины (реб ра ) графа , но не обеспечивают прямой досту п к ним по индексу (т.е . порядковому но меру ) вершины (ребра ) в соответствующем списке . Возможность получить ссылку на элемент графа по его индексу является весьма полезной при реализации многих алгоритмов , поэтому для решения данной проблемы приход ится использовать дополнительные структуры данны х . Достоинством динамических массивов является быстрый доступ к элементам по индексу. Наиболее "дорогой " операцией при использ овании динамических массивов является добавление элемента , поскольку в худшем случае для этого требуется выделить новый блок памя ти увеличенного размера , скопировать содержимое старого блока памяти в новый и освобо д ить старый блок , причем , по кр айней мере , этап копирования имеет сложность O(n). В то же время , в среднем операция добавления вершин (ребер ) в AGraph выполняется бо лее эффективно . Это достигается за счет то го , что при увеличении размера динамического масс и ва (вектора ) в библиотеке Vectors память выделяется сразу для нескольких э лементов , поэтому в большинстве случаев опера ция добавления элемента не требует фактическо го изменения размера вектора . Особенностью библиотеки AGraph является то , что каждая вершин а (ребро ) графа хранит собственный индекс в массиве вершин (ребер ) графа . Наличие такой "обратной " ссылки во многих случаях значительно упрощает работу с графом . Поддержание этой ссылки не ухудшает асимптотическую сложность операций доба вления и удаления в ершин (ребер ) графа . 4. Базовые средств а К базовым средс твам библиотеки для работы с графами отно сятся средства , обеспечивающие выполнение наиболе е общих операций над графом и его эле ментами , в том числе создание и уничтожени е объектов-графов , добавление в граф верш ин и ребер , удаление их из графа , итера цию по вершинам и ребрам и т.д . Базовые средства библиотеки AGraph в основном соответству ют аналогичным средствам других библиотек (см . пример 1). При создании программного интерфейс а приложений (API) биб л иотеки AGraph первоочер едное внимание уделялось обеспечению максимальны х функциональных возможностей библиотеки при сохранении простоты ее использования . Имена к лассов библиотеки , их полей , методов и сво йств (property) соответствуют распространенной англо я зычной терминологии теории графов и о бщепринятым соглашениям языка Object Pascal. // создани е графа G:=TGraph.Create; // добавление вершин и ребер V:=G.AddVertex; G.AddVertices(5); E:=G.AddEdge(G[0], G[1]); // ребро (v0, v1) G.AddEdgeI(0, 3); // ребро (v0 , v3) G.AddEdges([1, 2, 2, 4]); // ребра (v1, v2) и (v2, v4) // итерация по вершинам граф а for I:=0 to G.VertexCount - 1 do begin V:=G.Vertices[I]; // итерация по ребрам , инцидентным заданной вершине графа for J:=0 to V.Degree - 1 do With V.Inc identEdge[J] do ... ; end; // итерация по ребрам графа for I:=0 to G.EdgeCount - 1 do With G.Edges[I] do ... ; // удаление ребра (v0, v1) E.Free; // удаление ребра (v1, v2) G.GetEdgeI(1, 2).Free; // удаление вершины (с инциде нтными ребрами ) G.Vertice s[2].Free; // уничтожение графа G.Free; Пример 1. Базовые операции над графами в библиотеке AGraph. Если сравнивать библиотеки AGraph и LEDA, то можно отметить два существенных отличия . Первое из них связано с использованием динамических массивов для внут реннего представления графов в биб лиотеке AGraph. Массивы позволяют применять простой for-цикл для итерации по вершинам и ребра м графа . В библиотеке LEDA, использующей списки для хранения вершин и ребер , для той же цели необходимо использовать специальные макросы , а в библиотеке GTL (Passau), основа нной на STL, - итераторы STL [библиотека LEDA также подде рживает "STL-style" итераторы (пока в качестве экспери ментальной возможности )]. Второе отличие заключаетс я в том , что в AGraph для удаления вершин и ребер из графа используется с тандартный способ уничтожения объектов Object Pascal - вызов метода Free, в то время как в библиотеке LEDA для удаления вершин и ребер из граф а приходится использовать специальные методы классов-графов . Наиболее важным различием меж ду б иблиотеками AGraph и GTL (Н-Новгород ) является то , что в библиотеке GTL вершины и ребра существуют отдельно от графов и могут принадлежать сразу нескольким графам либо ни одному из графов . Для удаления неиспользуемых вершин (ребер ) из памяти в GTL исп о льзуе тся техника счетчиков ссылок (reference count): когда объек т (вершина или ребро ) присоединяется к гра фу или другой структуре (метод AddRef), счетчик увеличивается , когда удаляется из структуры (м етод Release) - уменьшается . При удалении ссылки на объ е кт из последней структуры , он должен удалить себя из памяти . Такое решение позволяет сэкономить память в тех случаях , когда графы конструируются из уж е существующих объектов . Одновременно снимается проблема отождествления объектов "родственных " графов : на п ример , в GTL порожденный п одграф графа содержит те же вершины , что и сам граф ( а не копии этих вершин !). В то же вр емя , такая интерпретация вершин и ребер мо жет затруднить использование библиотеки . Во-первых , проблемы могут возникнуть , когда с верши нами и ребрами графа связаны какие-либо атрибуты (см . ниже ) - изменение атрибута вер шины (ребра ) одного графа может вызвать не ожиданное для пользователя изменение атрибута вершины (ребра ) другого графа . Во-вторых , возможность существования "автономных " вершин и р ебер , на мо й взгляд , противоречит интуитивному пониманию графа . 5. Использование а трибутов Во многих случа ях необходимо связать с вершинами и ребра ми графа дополнительные данные - атрибуты (метк и ) вершин и ребер графа . Так , во взвеше нном графе каждое реб ро имеет целый или вещественный атрибут - вес ребра ; в м олекулярном графе с вершинами и ребрами м ожет быть связан целый ряд атрибутов (для вершин - номер атома , представляемого данной вершиной графа , в периодической таблице эле ментов Д.И.Менделеева , заряд атома и др ., для ребер - тип валентной связи , кото рой соответствует данное ребро ). Существует несколько способов привязки ат рибутов к вершинам и ребрам графа . Наиболе е простым из них является использование д ля хранения каждого атрибута вспомогательной стр уктуры данных , между элементами которо й , с одной стороны , и вершинами (ребрами ) графа , с другой стороны , существует взаимно- однозначное соответствие (см . пример 2). В данном примере используется особенность библиотеки AGraph, обеспечивающая эффективное по л учение для объекта-вершины (объекта-ребра ) его индекса в массиве вершин (ребер ). // создани е графа G:=TGraph.Create; V:=G.AddVertex; E:=G.AddEdge(V, G.AddVertex); // создание динамического массив а для хранения целого атрибута вершин графа (первый парам етр - количество элементов , второй - значение по умолчани ю ) AttrVector1:=TIntegerVector.Create(G.VertexCount, 0); // создание динамического массив а для хранения строкового атрибута ребер графа AttrVector2:=TStrLst.Create; AttrVector2.Count:=G.EdgeCou nt; // присваивание значений атрибут ам вершины V и ребра E графа AttrVector1[V.Index]:=1; AttrVector2[E.Index]:='AGraph'; Пример 2. Использова ние динамического массива для хранения атрибу тов вершин и ребер графа в библиотеке AGraph. В библиотеке LEDA д ля реализации аналогичного способа привязки атрибутов к вершинам и ребрам графа необходимо использовать специальные структуры да нных - классы node_array и edge_array (либо отличные от них по реализации , но эквивалентные в данном контексте классы node_map и e d ge_map). Это связано с тем , что в LEDA объекты-вершины и объекты-ребра хранятся в списках , а не в динамических массивах . // создани е графа graph G; node v = G.new_node(); edge e = G.new_edge(v, G.new_node()); // создание структуры node_arrray для хранения атрибута типа int для вершин графа G node_array attr1(G); // создание структуры edge_arrray для хранения атрибута типа string для ребер графа G edge_array attr2(G); // присваивание значений атрибут ам вершины v и ребра e графа G attr1[v]:=5; attr2[e]:="Saarbruecken"; Пример 3. Использова ние классов node_array и edge_array для хранения атрибутов вершин и ребер графа в библиотеке LEDA. Описанный способ хранения атрибутов подходит только для ста тических графов , т.к . при модификации графа соответ ствие между вершинами (ребрами ) г рафа и элементами вспомогательной структуры д анных теряется . Кроме того , определенные таким образом атрибуты не могут автоматически сохраняться при записи графа в поток или копироваться при копировании графов . Наиболе е ест е ственным способом "надежной " привязки атрибутов к вершинам (ребрам ) графа является хранение атрибутов (или ссылок н а атрибуты ) непосредственно в объектах-вершинах (объектах-ребрах ) графа . Библиотеки LEDA и GTL (University of Passay) пре длагают для этого п а раметризуемый класс графов , библиотека GTL (Н-Новгород ) - использов ание классов -"привкусов " (Flavor) и множественного на следования . Оба этих метода хорошо работают , когда набор атрибутов вершин (ребер ) графа известен во время компиляции программы . В библи о теке AGraph реализованы еще бол ее гибкие средства , позволяющие создавать и уничтожать атрибуты динамически , в процессе исполнения . Параметризуемый класс графов в LEDA позволяе т создавать графы , с каждой вершиной и каждым ребром которого связан атрибут зад анного типа (см . пример 4). Доступ к т аким атрибутам является в LEDA более эффективным , чем доступ к атрибутам , определенным с помощью node_array и edge_array. // создани е графа GRAPH H; node v = H.new_node(); edge e = H.new_edge(v, H.new_node()); // прис ваивание значений атрибутам вершины v и ребра e графа G H[v]:=5; H[e]:="Saarbruecken"; Пример 4. Использова ние параметризуемого класса графов LEDA. В библиотеке GTL (Н -Новгород ) для создания вершин и ребер с заданными свойствами используется механизм кла с сов -"привкусов " (Flavor). Данный механизм может использоваться для привязки атрибутов к вершинам и ребрам графа , хотя его возможно сти этим не ограничиваются . Flavor - это абстрактный (чисто виртуальный в терминологии С ++) клас с , который применяется в каче с тве "добавки " при порождении новых классов с использованием множественного наследования . Flavor тр ебует , чтобы объект обладал некоторыми свойст вами , но не привносит их в объект сам . Например , класс CWeightedEdge ("взвешенное ребро ") порожда ется от классов CEdge ("ребро ") и специ ального класса CWeightFlavor. В классе CWeightFlavor определены дв а абстрактных виртуальных метода - SetWeight и GetWeight, кото рые должны быть перекрыты в классе CWeightedEdge. GTL п редоставляет ряд "привкусов " для построения ра спр о страненных типов объектов (при необходимости пользователи могут расширить наб ор Flavor). Порожденные с помощью Flavor классы , в сво ю очередь , используются в качестве параметров шаблонных классов графов для создания кл ассов графов , вершины и ребра которых о бладают заданными свойствами (см . пример 5). // определ ение класса CWEdge (взвешенное ребро ) template class CWEdge:public CEdge,CWeightFlavor protected: double m_dWeight; public ... virtual void SetWeight(double dWeight) m_dWeight=dWeight; virtual double GetWeight() const return m_dWeight; ... ; // определение синонимов для вершин и ребер #define V CVertex #define E CWEdge ... // создание ориентированного гра фа с использованием представления в виде списков смежности CGraphAdjList xGraphAL(TRUE); // создание графа с использо ванием макросов VPOS xPos1,xPos2,xPos3; AL_ADDVERTEX(&xGraphAL,new V,xPos1); AL_ADDVERTEX(&xGraphAL,new V,xPos2); AL_ADDVERTEX(&xGraphAL,new V,xPos3); AL_ADDEDGE(&xGraphAL,xPos1,xPos2,new E(1.0)); A L_ADDEDGE(&xGraphAL,xPos1,xPos3,new E(3.0)); // доступ к весу ребра (м етоды GetWeight и SetWeight определены в классе CWeightFlavor) E* e = xGraphAL.GetIncidEdgeAt(xPos1, 0); double w = e->GetWeight; e->SetWeight(1.0); Пример 5. Использова ние классов -"п ривкусов " в GTL (Н-Новгород ). Смысл в использ овании Flavor проявляется , когда объект должен обла дать несколькими свойствами : например , требуется "взвешенное ребро с пропускной способностью ". Если использовать обычное наследование , то можно построить два р азлич ных класса , которые фактически п редставляют один и тот же вид ребра . Множественное наследовани е от классов "взвешенное ребро " и "ребро с пропускной способностью " также не помогае т , т.к . при этом класс "ребро " будет насл едоваться дважды . Проблема легко решается с помощью Flavors: достаточно определить Flavor "пропускная способность " и породить требуемый класс о т класса TEdge и двух Flavor. Методы привязки атрибутов к элементам графа с помощью параметризуемых классов гр афов , реализованные в библиотеке L EDA, или с помощью классов -"привкусов ", реализованные в GTL (Н-Новгород ), используют средства языка C++, кот орые отсутствуют в Object Pascal - шаблоны и множественно е наследование . Данное обстоятельство привело к реализации в библиотеке AGraph собственног о механизма поддержки атрибутов . С одной стороны , это решение является единственно возможным ; с другой стороны , данный механизм является более высокоуровневым и обладает большей гибкостью , чем средства других библ иотек . Атрибуты в AGraph фактически являютс я переменными , определенными на элементах графа . Каждый атрибут имеет уникальное имя и ти п , относящийся к одному из нескольких пред определенных типов . Типы атрибутов соответствуют основным типам языка программирования Object Pascal (Integer, Boolean, Char, Double, String и др .). Библиотека позволяет динамически создавать и уничтожа ть атрибуты вершин и ребер графа , причем можно создавать как общие дл я всех вершин (ребер ) графа атрибуты , так и локальные атрибуты , определенные только д ля отдельных вершин (ребе р ) графа (см . пример 6). Доступ к атрибутам осуществляется с помощью реализованного в Object Pascal механизма свой ств (property). Для каждого из поддерживаемых типов атрибутов определены свои методы доступа (AsBool, AsChar, AsInt8, AsInt16, AsInt32, AsFlo a t, AsString и т.д .), благодаря чем у на атрибуты распространяется контроль типов . Поскольку граф "владеет " всеми своими атр ибутами , их сохранение , восстановление и копир ование при выполнении соответствующих операций над графом осуществляется автоматически, полностью "прозрачно " для программиста - пол ьзователя библиотеки . // создани е графа G:=TGraph.Create; // создание общего атрибута вершин графа типа String с именем 'Name' G.CreateVertexAttr('Name', AttrString); // присваивание значений атрибут у 'Name' вер шин 0 и 1 графа G[0].AsString['Name']:='Moscow'; G[1].AsString['Name']:='Minsk'; // уничтожение общего атрибута вершин графа с именем 'Name' G.DropVertexAttr('Name'); // создание локального атрибута типа Integer с именем 'Color' для вершины 0 графа и пр исваива ние ему значения G[0].Local.Map.CreateAttr('Color', AttrInteger); G[0].Local.AsInteger['Color']:=1; Пример 6. Работа с атрибутами в библиотеке AGraph. Для поддержки а трибутов в библиотеке используется собственный механизм распределения памяти , кото рый обеспечивает высокую эффективность операций созд ания и уничтожения атрибутов и малый расх од памяти для хранения атрибутов . Единственны м недостатком данного подхода является относи тельно медленный доступ к атрибутам : основным способом идентификации атр и бута является его имя , поэтому при каждом обращ ении к атрибуту по имени осуществляется п оиск в таблице имен атрибутов . Библиотека AGraph предоставляет низкоуровневые средства , позволяющие значительно понизить "накладные расходы " на доступ к атрибутам (цен о й некот орого усложнения программирования и потенциально го снижения надежности ). Так , можно один ра з вычислить смещение некоторого атрибута в блоке памяти , отведенном для хранения атриб утов , для того , чтобы впоследствии обращаться к данному атрибуту по сме щ ен ию , а не по имени . Благодаря этому искл ючается относительно медленный этап поиска в таблице имен атрибутов , но снижается наде жность . Существует и другой способ повышения производительности , наиболее эффективный при интенсивном использовании атрибутов : п е ред началом работы некоторой процедуры следует скопировать атрибуты во временную структуру данных , которая поддерживает прямой доступ (например , динамический массив ), и в дальнейшем работать с этой структурой , т.е . использовать на "локальном уровне " спосо б привязки данных к графу , который уж е был рассмотрен . Разумеется , в этом случа е необходимо помнить о синхронизации графа и временной структуры данных . Атрибуты в библиотеке AGraph предназначены не только для привязки пользовательских данных , но и активно используются внутри с амой библиотеки . Например , для ребер графа (класс TEdge) определен метод RingEdge, который проверяет , является ли ребро кольцевым (т.е . при удале нии данного ребра количество связных компонен т графа не увеличивается ). Поскольку эта п ро в ерка является относительно дорогой операцией (время выполнения может достигать O(n+m)), нежелательно осуществлять ее при каждом обращении к методу RingEdge. В библиотеке использу ется следующий прием : при первом обращении к методу RingEdge библиотека выпол н яет соответствующий алгоритм , создает глобальный ат рибут ребер графа и запоминает в нем результат работы алгоритма . До тех пор , по ка граф не подвергнется изменениям , которые могут повлечь нарушение правильности запомненн ых значений , при последующих обраще н иях к методу RingEdge возвращается запомненное значение . Если граф подвергнется таким из менениям , то атрибут будет автоматически унич тожен . То же самое можно было бы сдела ть , добавив в класс TEdge дополнительное поле для запоминания результатов выполнения метода RingEdge, однако в таком случае при отсутствии обращений к методу RingEdge память , нео бходимая для хранения данного поля , расходова лась бы напрасно . 6. Поддержка разли чных видов графов Одна из проблем , которые возникают при разработке универсаль но й библиотеки для работы с графами - как реализовать поддержку различных видов графов : ориентированных и неориентированных графо в , взвешенных графов , деревьев и т.д . Вид графа , во-первых , задает набор атрибутов , кот орые определены для вершин и ребер данног о графа (например , вес ребра для взвешенного графа или указатель на родит ельскую вершину для дерева ), во-вторых , определя ет , какие методы можно применять к этому графу , и , в-третьих , может влиять на их выполнение (например , метод поиска кратчайшег о пути ме ж ду заданными вершинами графа выполняется по-разному для ориентирова нных и неориентированных графов ). Библиотеки LEDA явно поддерживает два вида графов - ориентированные и неориентированные гр афы : в библиотеке определены параметризуемые классы (GRAPH и UGR APH) для каждого из этих видов . Какие-либо средства для поддержки други х видов графов не предусмотрены . Если проц едура или функция являются специфичной для графа определенного вида (например , функция нахождения максимального потока в транспортной сети ), т о все необходимые параметр ы (в последнем примере - пропускные способности дуг сети ) непосредственно передаются в эт у процедуру или функцию (например , с помощ ью динамических массивов ). Библиотека GTL (Н-Новгород ) также непосредственно поддерживает ориентиро ванные и неориенти рованные графы - конструкторы классов-графов по умолчанию строят неориентированный граф , однако существуют варианты конструкторов с явным заданием "ориентированности " графа . В то же время , библиотека поддерживает и другие в иды графов с п о мощью классов -" привкусов ". Алгоритмы , специфичные для конкретных видов графов , реализованы как обычные фун кции-члены (методы ) параметризуемых классов графов , но в этих функциях неявно предполагается , что классы-вершины и классы-ребра , используемы е при кон к ретизации данного парам етризуемого класса графов , предоставляют необходи мые интерфейсные функции . Это , в свою очер едь достигается наследованием классов-вершин и классов-ребер от соответствующих классов -"привк усов ". Библиотека AGraph предлагает высокоуровн евый (хотя и не вполне универсальный ) подход к решению проблемы поддержки различных вид ов графов , использующий возможности библиотеки по динамическому созданию и уничтожению ат рибутов . В библиотеке определен набор "свойств " графа , которые соответствуют ко н кретным видам графов . Текущая версия библиоте ки поддерживает ориентированные графы , деревья , транспортные сети , взвешенные графы , геометриче ские графы . Не все "свойства " являются неза висимыми : так , транспортная сеть всегда являет ся ориентированным графом. Поддержка всех "свойств " реализована в одном и том же классе TGraph, который имеет свойство (в смысле property языка Object Pascal) Features типа "множ ество ". В процессе исполнения графу можно присвоить любую комбинацию предопределенных "свой ств " графов ( см . пример 7). При этом библ иотека автоматически создает необходимые атрибут ы и разрешает использование специфичных для данного "свойства " методов (в противном сл учае попытка их применения приводит к воз буждению исключительной ситуации ). Благодаря тому , ч т о библиотеке известно , к ка ким видам относится данный граф , операции записи графа в поток и чтения из пото ка , а также копирования графов отрабатываются корректно (с сохранением всей "видовой " ин формации ), причем это не требует дополнительно й работы со сто р оны программиста - пользователя библиотеки . Поддерживаемые нынешней версией библиотеки AGraph виды не исчерпывают всех возможных разновидностей графов , которые могут понадобиться при решении прикладных задач , однако даже этот набор способен значительно об л егчить работу прикладн ого программиста . // создани е взвешенного ориентированного дерева G:=TGraph.Create; G.Features:=[Directed, Tree, Weighted]; // добавление корня и двух листьев V:=G.AddVertex; // свойства (property) и методы , спец ифичные для деревьев G.Root:=V; V.AddChild; U:=V.AddChild; P:=U.Parent; // P = V // свойства (property), специфичные для взвешенных графов G.Edges[0].Weight:=5.1; G.Edges[1].Weight:=2.2; // метод FindMinWeightPath интерпретирует гра ф как ориентированный // или неориентированны й в зависимости от Features T:=G.FindMinWeightPath(V[0], V[1], nil); // T = 2.2 Пример 7. Использова ние "свойств " (Features) графа . Ниже все поддер живаемые библиотекой AGraph виды графов будут расс мотрены более подробно . Ориентированные гр афы Граф интер п ретируется как ориентированный , если во множе ство Features графа входит флаг Directed (Directed in Features = True). Поддержка орграфов не требует хранения каких-либо допол нительных данных : один из концов ребра TEdge.V1 считается началом дуги , а другой к о нец TEdge.V2 - концом дуги . Многие методы клас са TGraph учитывают свойство ориентированности графа ; в то же время , доступны методы , котор ые рассматривают граф как ориентированный или неориентированный независимо от значения Features. Деревья Граф являетс я деревом , если в его множество Features входит флаг Tree (Tree in Features = True). Указание на то , что гр аф является деревом (Directed in Features = True), позволяет упростить работу с древовидными структурами . Одна и з вершин дерева помечается как корен ь . Для того , чтобы сделать вершину кор нем , надо присвоить свойству IsRoot вершины значени е True или , что то же самое , присвоить сво йству Root графа указатель на эту вершину . Ка ждая вершина дерева , кроме корня , содержит ссылку на родительскую вершину (Paren t ). Для построения дерева следует использовать м етод TVertex.AddChild. Транспортные сети Транспортная сеть (Network in Features = True) - это ориентированный граф с двумя выделенными вершинами : истоком (TGraph.NetworkSource) и стоком (TGraph.NetworkSink). Исток обладает тем свойством , что в него не входит ни одна дуга ; из стока , напротив , не исходит ни одна ду га . Каждой дуге сети приписано неотрицательно е вещественное число - максимальный поток , кото рый может быть пропущен через эту дугу . Одной из наиболе е известных зада ч на сетях является задача нахождения мак симального потока в сети . В библиотеке реа лизовано решение этой задачи ; для этого не обходимо построить граф - транспортную сеть , ук азать с помощью свойств графа NetworkSource и NetworkSink ис ток и ст о к сети (то же сам ое можно сделать , присвоив значение True свойства м IsNetworkSource и IsNetworkSink соответствующих вершин сети ), задат ь максимальные потоки на дугах сети с помощью свойства TEdge.MaxFlow и вызвать метод TGraph.FindMaxFlowThroughNetwork. Е с ли построенная сеть коррек тна (IsNetworkCorrect = True), то этот метод возвращает значение максимального потока в сети и устанавлив ает свойства TEdge.Flow в значения потоков на дуг ах , при которых достигается максимальный пото к . Взвешенные графы Взвешенны й граф (Weighted in Features = True) - неориентированный или ориентированный граф , ребрам (дугам ) которого поставлено в соответствие вещественное число , называемое вес ом . Вес ребра доступен с помощью свойства TEdge.Weight. Классической задачей на взвешенн о м графе является задача нахождения кр атчайшего пути (пути с минимальной суммой весов входящих в этот путь ребер или дуг ) между заданными вершинами , либо между всеми парами вершин . Задача нахождения кратча йшего пути между заданными вершинами во в звешенном г рафе с неотрицательными весами решается в библиотеке методами TGraph.FindMinWeightPathCond / TGraph.FindMinWeightPath, в которых используется алгоритм Де йкстры . В библиотеке реализован также алгорит м Флойда (TGraph.CreateMinWeightPathsMatrix), позволяющий найти к ратчайшие пути между всеми парами вершин . Алгоритм Флойда применим к ографам с дуга ми отрицательного веса ; при наличии контуров отрицательной длины алгоритм их обнаруживает . Геометрические гра фы В геометрических графах для каждой вершины графа опр еделены вещественные координаты : двумерные (X, Y) или трехмерные (X, Y, Z) (соответственно , Geom2D или Geom3D). В настоящее время в библиотеке определен тол ько ряд вспомогательных методов для работы с такими графами , однако в будущем план ируется реализова т ь алгоритмы визуали зации графов . 7. Реализованные а лгоритмы В библиотеке AGraph реализованы алгоритмы решения многих теоретико-гр афовых задач , в том числе : · поиск путей с минимальным количеств ом промежуточных вершин между заданными верши нами графа ; · поиск путей минималь ной длины во взвешенном графе ; · определение связности графа ; · определение отношения ребра к кольцевым системам ; · нахождение компонент связности графа ; · нахождение сильных к омпонент ориентированного графа ; · построение матрицы с вязности и обобщенной матрицы связности графа ; · построение матрицы д остижимости графа ; · построение матрицы р асстояний графа ; · поиск максимальных н езависимых множеств вершин графа ; · поиск системы незави симых минимальных колец графа (исключая петли ), покрывающих все кольцевые ребра графа ; · построение графа , доп олнительного к заданному графу ; · построение реберного графа для заданного графа ; · построение кратчайшего остовного дерева для заданного взвешенного графа ; · поиск максимального потока в транспортной сети ; · поиск хроматического числа и оптимальной вершинной раскраски гр афа ; · поиск эйлерова цикла в графе ; · поиск гамильтоновых циклов в орграфе ; · решение задачи почта льона для взвешенного графа с неотрицательным и весами ребер ; · опре деление план арности графа ; · распознавание изоморфизм а графов с учетом атрибутов. В качестве исто чников алгоритмов использовались монографии и статьи по теории графов . При решении за дач , для которых известны алгоритмы полиномиа льной сложности , использовал ись , в основно м , алгоритмы , которые являются асимптотически оптимальными среди всех известных алгоритмов решения данной задачи , или близки к оптима льным . Для некоторых из задач , решаемых би блиотекой , алгоритмы полиномиальной сложности не существуют или не и звестны . В таком случае приходится использовать переборные алгоритмы , приближенные алгоритмы или алгори тмы , обеспечивающие эффективное решение для ч астных случаев задачи . Библиотека AGraph предоставляет ряд алгоритмов , которые относятся ко втор ой и третье й из этих категорий (например , приближенный алгоритм вершинной ра скраски графов ). В то же время , основное внимание в библиотеке уделялось реализации универсальных алгоритмов . Для некоторых "трудны х " задач переборные алгоритмы были реализован ы самостоятельн о ; для решения других в библиотеку были перенесены наиболее эф фективные программные реализации , которые удалось найти (разумеется , в том случае , когда авторы программ допускают такое использование ). Так , функция распознавания изоморфизма графов основана на программе , разработанной М.Венто [ 5 ]; функция нахождения хроматического числа и оп тимальной вершинной раскраски графа основан а на программе , разработанной М.Триком [ 6 ]. Важнейшей пробл емой при разработке программного обеспечения является обеспечение его корректности . Необходимой составляющей для достижения корректности является использование корректных алгоритмов , однако правильная и эффективная реализация алгоритмов также является нет р ивиальной задачей . При создан ии библиотеки AGraph принимались различные меры дл я обнаружения и исправления ошибок . Во-первых , в отладочном режиме методы классов библи отек AGraph и Vectors выполняют проверки предусловий и правильности передаваемых параметр о в ; в случае обнаружения ошибки возбуждается и сключительная ситуация (exception). Во-вторых , все изменения активно тестируются как в ручном , так и в автоматическом режиме , для чего был и созданы соответствующие программные тесты . Разумеется , все эти методы н е га рантируют отсутствие ошибок , однако их исполь зование позволило значительно повысить надежност ь библиотеки . С технологической точки зрения алгоритмы можно разделить на две категории : первые из них реализованы в виде методов кл асса TGraph (модуль graphs .pas), вторые - в отдельных модулях . Реализация алгоритмов в модуле graphs.pas поз воляет достичь максимальной эффективности за счет доступа к деталям внутреннего представле ния графа (т.е . к защищенным полям и ме тодам классов TVertex, TEdge и TGraph), поэт о му так им способом реализованы , в основном , "базовые " алгоритмы : поиск путей , определение компонент связности графа и т.д . 8. Ввод /вывод графов Одной из пробле м при создании средств работы с помеченны ми графами является выбор внешнего файлового формата дл я хранения графов . До н едавнего времени каждая программная система и спользовала свой собственный , уникальный формат , что приводило к сложностям при организации обмена данными . Относительно недавно разрабо тчики системы Graphlet предложили универсальный пер е носимый формат файла для предста вления помеченных графов - GML (Graph Modelling Language) [ 7 ]. В настоящее время GML-формат поддерживается мно гими прикладными программами и библиотека ми для работы с графами . GML-файл состоит из пар ключ-значение . Примерами ключей являются стандартные ключи graph , node и edge . Значениями могут быть целые и веще ственные числа , строки и списки ; в свою очередь , списки также содержат пары ключ-зна чение , в том числе вложенные списки . Важным достоинством формата GML является его отк рытость и расширяемость : любой разработчик им еет право определять свои ключи для хране ния необходимой информации . В настоящее время этот формат поддерживается многими прикладны ми п рограммами и библиотеками для работы с графами . Библиотека AGraph также поддер живает запись и чтение графов в GML-формате , но с некоторыми ограничениями (для хране ния строк не используется кодировка ISO 8859). Наряду с форматом GML, библиотека поддержива е т запись графов в поток и чтение их из потока с использованием двоичного формата (методы TGraph.WriteToStream и TGraph.ReadFromStream). Данный способ обеспечивает более высокую скорость записи /чтения графов и приводит к созданию фа йлов меньшего размера , о д нако не является переносимым . 9. Создание специа лизированных классов графов Библиотека AGraph предос тавляет гибкие средства (механизм поддержки д инамических атрибутов и различных видов графо в ), позволяющие использовать ее для решения самых разных приклад ных задач . Во м ногих случаях пользователю хватит возможностей , предоставляемых основным классом библиотеки TGraph. В то же время , создание специализированных классов графов оправдано , если это позволяе т облегчить работу с библиотекой и /или повысить эффект и вность прикладных программ . Примером специализированного класса графов является класс TChemGraph, предназначенный для работы с молекулярными графами . Данный класс являе тся непосредственным потомком класса TGraph и подд ерживает работу с молекулярными графа ми на уровне атомов и связей (см . пример 8). Для хранения необходимых данных используютс я атрибуты , но в целях ускорения доступа к ним вместо методов используется доступ по смещениям . TChemGraph обеспечивает также запись и чтение молекулярных графов с исп о льзованием распространенных MOL- и SDF-форматов . // создани е молекулярного графа G:=TChemGraph.Create; // добавление атомов и связе й A:=G.AddAtom(CarbonAtom); // добавить 'C' G.AddAtom(AtomTbl.SearchName('N')); // добавить 'N' G.AddAtom(AtomTbl.SearchName('Cl')); // добавить 'Cl' G.AddBond(A, G[1], DoubleBond); G.AddBond(A, G[2], SingleBond); // свойства и методы , специфи чные для молекулярных графов G.Atom[1]:=CarbonAtom; // заменить 'N' на 'C' S1:=G.AtomName[1]; // S1 = 'C' S2: =G.BruttoFormula; // S2 = 'С 2С l1' Пример 8. Использова ние класса TChemGraph. 10. Эффективность При создании би блиотеки AGraph в качестве основных целей были поставлены обеспечение универсальности и прост оты использования библиотеки . Соображения эффекти вн ости учитывались в той мере , в к акой это не противоречило достижению данных целей . В то же время , решение многих прикладных задач требует обработки графов большого размера , и возможность решения эти х задач на доступных вычислительных средствах напрямую за в исит от эффективност и реализации тех или иных алгоритмов . Для оценки эффективности средств библиоте ки AGraph было осуществлено решение ряда тестовых задач ; те же задачи решались с помощь ю библиотеки LEDA. Поскольку данные библиотеки ис пользуют разные внут ренние представления графов , различные методы привязки атрибутов к вершинам и ребрам графа , а также спос обы передачи параметров и возвращения результ атов , прямое сравнение результатов этих испыт аний не совсем корректно . Тем не менее , результаты показывают, что скоростные хар актеристики библиотек AGraph и LEDA являются , по крайн ей мере , сопоставимыми (см . таблицу 1). При тестировании использовались следующие программные и аппаратные средства . · ЭВМ : персональный ко мпьютер на процессоре AMD K6-2 400 (частот а системн ой шины 100 MHz), кэш второго уровня 512 Kb, ОЗУ 64 Mb. · ОС : Windows 95 OSR 2.1. · Версии библиотек : AGraph v.990915, LEDA 3.8. · Компиляторы : для AGraph - Delphi 3.0, для LEDA - MS Visual C++ 5.0 (в обоих случаях отладочные проверки были выкл ючены , исп ользовалась максимальная оптимизация ). AGraph LEDA количество вершин |V|=100000, количество ребер |E|=200000 * нахождение пути минимальной длин ы 0.4 с 0.6 с нахождение пути минимального суммарного веса (граф интерпретиро вался как неориентированный ) 1.5 с (вещ ественные веса ) 1.9 с (целые веса ); 3.2 с (вещественные веса ) нахождение пути минимального суммарного веса (граф интерпретиро вался как ориентированный ) 1.3 с (вещественные веса ) 1.1 с (целые веса ); 1.9 с (вещественные веса ) нахождение связны х компонент 0.6 с 0.4 с нахождение сильны х компонент (граф интерпретировался как ориен тированный ) 0.7 с ошибка времен и исполнения (переполнение стека ) построение минима льного остовного дерева 5.8 с 4.8 с * В библиотеке AGraph хранение графа такого размера потребов ало около 26 Мб оперативной памяти и 21 Мб на диске в формате GML. Литература 1. Нечепуренко М.И ., Попков В.К ., Майнагаше в С.М . и др . Алгоритмы и программы реше ния задач на графах и сетях . - Новосибирск , Наука (сибирское отделение ), 1990. 2. Mehlhorn K., Naher St. The LEDA Platform of Combinatorial and Geometric Computin g. - Cambridge University Press, 1999. 3. Цыпнятов Е . Библиотека классов для программирования задач теории графов , дипломная работа . - Нижний Новгород , 1998. 4. Object Pascal Language Guide. Borland Delphi 3 for Windows 95 and Windows NT - Borland Int ernational Inc., 1997. 5. Cordella L.P., Foggia P., Sansone C., Vento M. An Efficient Algorithm for the Inexact Matching of ARG Using a Contextual Transformational Model. / Proc. of the 13th ICPR, IEEE Computer Society Press, 1996, vol.III, pp.180-184. 6. Mehrotra A., Trick M.A. A Column Generation Approach for Exact Graph Coloring / INFORMS Journal on Computing, 8:4, 1996. 7. Himsolt M. GML: A Portable Graph File Format / Technical Report, Universitat Passau, 1997, cf. ; с м . также краткое описание GML .
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Попросить у курящего на улице сигарету - это нормально. А если кто-то шоколадку ест и ты попросишь кусочек - смотрят как на психа.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, курсовая по программированию "AGraph: библиотека классов для работы с помеченными графами", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru