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

§ 1. Актуальність розробки бібліотек для роботи з графами

До теперішнього часу накопичений великий досвід вирішення теоретико-Графова задач на ЕОМ. Програми для вирішення багатьох задач можна знайти у глобальній мережі Інтернет. У той же час, використання незалежно розроблених програм пов'язане з великими труднощами. До їх числа відносяться як загальні, які не залежать від предметної області, технічні проблеми (різні мови програмування, несумісність програмних і апаратних засобів), так і проблеми, пов'язані зі специфікою теоретико-Графова завдань (використання різних внутрішніх уявлень графів). У зв'язку з цим актуальним завданням є розробка більш-менш універсальних бібліотек, які, з одного боку, надавали б користувачеві високорівневі засоби для роботи з графами, а з іншого, рятувала його від необхідності ручного програмування рутинних операцій вводу-виводу або перетворень між різними внутрішніми уявленнями графів.

Розробка універсальної бібліотеки для роботи з графами є складним завданням. Однією з проблем є велика різноманітність задач теорії графів. Оскільки теоретичні дослідження та розробка нових алгоритмів безперервно тривають, очевидно, що жодна бібліотека не зможе вирішувати всі існуючі завдання. Іншою проблемою є забезпечення ефективності. Нерідко існує кілька алгоритмів для вирішення однієї і тієї ж задачі, причому не завжди можна вказати алгоритм, оптимальний у всіх випадках: для одних графів більш ефективним може бути один алгоритм, для інших - інший. Розробник універсальної бібліотеки зазвичай не може дозволити собі реалізацію декількох алгоритмів для розв'язання однієї задачі, тому йому доводиться йти на компроміси між ефективністю та універсальністю. При розробці бібліотек для роботи з графами виникають також численні технічні труднощі. Для прийнятною з точки зору ефективності реалізації багатьох алгоритмів програмісту необхідно мати у своєму розпорядженні такі структури даних, як динамічні масиви, списки, стеки, черги, пріоритетні черги, дерева пошуку. Реалізація всіх необхідних структур даних в межах однієї бібліотеки навряд чи можлива і виправдана, тому універсальна бібліотека для роботи з графами вимагає серйозної програмної "інфраструктури" у вигляді інших бібліотек.

Перераховані проблеми можуть викликати сумнів у доцільності створення універсальних бібліотек для роботи з графами, проте існують вагомі аргументи на користь їх створення. По-перше, реалізовані в подібній бібліотеці базові алгоритми можуть служити хорошою основою для створення більш спеціалізованих алгоритмів і програм, спрямованих на вирішення конкретних прикладних задач. По-друге, міркування ефективності не завжди є визначальними - постійне зростання продуктивності ЕОМ все частіше виводить на перший план технологічність та швидкість розробки програмного забезпечення (зрозуміло, це не означає, що програміст не повинен прагнути до ефективного використання обчислювальних ресурсів). Поряд з "промисловим" програмування, універсальні бібліотеки для роботи з графами можуть застосовуватися у навчальних цілях, а також для підтримки теоретичних досліджень, пов'язаних з алгоритмами і програмами рішення задач теорії графів. В обох випадках універсальність проблемної орієнтації бібліотеки більш важлива, ніж максимальна ефективність реалізованих у ній алгоритмів.

§ 2. Об'єктно-орієнтовані бібліотеки для роботи з графами

1. Переваги ООП при створенні бібліотек для роботи з графами

При створенні "першого покоління" бібліотек для роботи з графами використовувалися мови програмування Fortran, Algol, PL1, потім З [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

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 + + STL, бібліотека GTL (Н-Новгород) заснована на MFC 4.x.

При розробці бібліотеки AGraph також виникла необхідність у базових програмних засобах. Оскільки готових засобів такого роду для Object Pascal не існувало (бібліотека візуальних компонент Delphi 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. IncidentEdge [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. Vertices [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. EdgeCount;// присвоювання значень атрибутів вершини V і ребра E графаAttrVector1 [V. Index]: = 1; AttrVector2 [E. Index]: = 'AGraph';

Приклад 2. Використання динамічного масиву для зберігання атрибутів вершин і ребер графа в бібліотеці AGraph.

У бібліотеці LEDA для реалізації аналогічного способу прив'язки атрибутів до вершин і ребер графа необхідно використовувати спеціальні структури даних -- класи node_array і edge_array (або відмінні від них по реалізації, але еквівалентні в даному контексті класи node_map і edge_map). Це пов'язано з тим, що в LEDA об'єкти-вершини і об'єкти-ребра зберігаються в списках, а не в динамічних масивах. //Створення графаgraph G; node v = G.new_node (); edge e = G.new_edge (v, G.new_node ());// створення структури node_arrray для зберігання атрибуту типу int для вершин графа Gnode_array attr1 (G);// створення структури edge_arrray для зберігання атрибуту типу string для ребер графа Gedge_array attr2 (G);// присвоювання значень атрибутів вершини v і ребра e графа Gattr1 [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 графа GH [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)); AL_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.

Методи прив'язки атрибутів до елементів графа за допомогою параметрізуемих класів графів, реалізовані в бібліотеці LEDA, або за допомогою класів-"присмаків", реалізовані в GTL (Н-Новгород), використовують засоби мови C + +, які відсутні в Object Pascal - шаблони і множинне успадкування. Дана обставина привела до реалізації в бібліотеці AGraph власного механізму підтримки атрибутів. З одного боку, це рішення є єдино можливим, з іншого боку, цей механізм є більш високорівневим і має більшу гнучкість, ніж кошти інших бібліотек.

Атрибути в AGraph фактично є змінними, визначеними на елементах графа. Кожен атрибут має унікальне ім'я і тип, що відноситься до одному з кількох визначених типів. Типи атрибутів відповідають основним типам мови програмування Object Pascal (Integer, Boolean, Char, Double, String та ін.) Бібліотека дозволяє динамічно створювати і знищувати атрибути вершин і ребер графа, причому можна створювати як загальні для всіх вершин (ребер) графа атрибути, так і локальні атрибути, визначені тільки для окремих вершин (ребер) графа (див. приклад 6). Доступ до атрибутів здійснюється за допомогою реалізованного в Object Pascal механізму властивостей (property). Для кожного з підтримуваних типів атрибутів визначені свої методи доступу (AsBool, AsChar, AsInt8, AsInt16, AsInt32, AsFloat, 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. У бібліотеці вико