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 (n). У той же час, в середньому операція додавання вершин (ребер) в AGraph виконується більш ефективно. Це досягається за рахунок того, що при збільшенні розміру динамічного масиву (вектора) в бібліотеці Vectors пам'ять виділяється відразу для декількох елементів, тому в більшості випадків операція додавання елемента не вимагає фактичної зміни розміру вектора.

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

4. Базові засоби

До базових засобам бібліотеки для роботи з графами відносяться засоби, що забезпечують виконання найбільш загальних операцій над графом і його елементами, в тому числі створення і знищення об'єктів-графів, додавання в граф вершин і ребер, видалення їх з графа, ітерацію по вершинах і ребрах і т.д. Базові засоби бібліотеки AGraph в основному відповідають аналогічним засобах інших бібліотек (див. приклад 1). При створенні програмного інтерфейсу додатків (API) бібліотеки AGraph першочергова увага приділялася забезпеченню максимальних функціональних можливостей бібліотеки при збереженні простоти її використання. Імена класів бібліотеки, їх полів, методів і властивостей (property) відповідають поширеною англомовної термінології теорії графів і загальноприйнятим угодами мови Object Pascal.

Приклад 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, що забезпечує ефективне отримання для об'єкта-вершини (об'єкта-ребра) його індексу в масиві вершин (ребер).

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

У бібліотеці LEDA для реалізації аналогічного способу прив'язки атрибутів до вершин і ребер графа необхідно використовувати спеціальні структури даних - класи node_array і edge_array (або відмінні від них по реалізації, але еквівалентні в даному контексті класи node_map і edge_map). Це пов'язано з тим, що в LEDA об'єкти-вершини і об'єкти-ребра зберігаються в списках, а не в динамічних масивах.

Приклад 3. Використання класів node_array і edge_array для зберігання атрибутів вершин і ребер графа в бібліотеці LEDA.

Описаний спосіб зберігання атрибутів підходить тільки для статичних графів, тому що при модифікації графа відповідність між вершинами (ребрами) графа і елементами допоміжної структури даних втрачається. Крім того, визначені таким чином атрибути не можуть автоматично зберігатися при записі графа в потік або копіюватися при копіюванні графів. Найбільш природним способом "надійною" прив'язки атрибутів до вершин (ребрах) графа є зберігання атрибутів (або посилань на атрибути) безпосередньо в об'єктах-вершинах (об'єктах-ребрах) графа. Бібліотеки LEDA і GTL (University of Passay) пропонують для цього параметрізуемий клас графів, бібліотека GTL (Н-Новгород) - використання класів-"присмаків" (Flavor) і множинного успадкування. Обидва цих методу добре працюють, коли набір атрибутів вершин (ребер) графа відомий під час компіляції програми. У бібліотеці AGraph реалізовані ще більш гнучкі засоби, що дозволяють створювати і знищувати атрибути динамічно, в процесі виконання.

Параметрізуемий клас графів у LEDA дозволяє створювати графи, з кожною вершиною і кожним ребром якого пов'язаний атрибут заданого типу (див. приклад 4). Доступ до таких атрибутів є в LEDA більш ефективним, ніж доступ до атрибутів, певним за допомогою node_array і edge_array.

Приклад 4. Використання параметрізуемого класу графів LEDA.

У бібліотеці GTL (Н-Новгород) для створення вершин і ребер із заданими властивостями використовується механізм класів-"присмаків" (Flavor). Цей механізм може використовуватися для прив'язки атрибутів до вершин і ребер графа, хоча його можливості цим не обмежуються. Flavor - це абстрактний (чисто віртуальний в термінології С + +) клас, який застосовується в якості "добавки" при породженні нових класів з використанням множинного успадкування. Flavor вимагає, щоб об'єкт мав деякими властивостями, але не привносить їх в об'єкт сам. Наприклад, клас CWeightedEdge ("зважене ребро") породжується від класів CEdge ("ребро") та спеціального класу CWeightFlavor. У класі CWeightFlavor визначені два абстрактні віртуальних методу - SetWeight і GetWeight, які повинні бути перекриті в класі CWeightedEdge. GTL надає ряд "присмаків" для побудови поширених типів об'єктів (при необхідності користувачі можуть розширити набір Flavor). Породжені за допомогою Flavor класи, у свою чергу, використовуються в якості параметрів шаблонних класів графів для створення класів графів, вершини і ребра яких володіють заданими властивостями (див. приклад 5).

Приклад 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 і т.д.), завдяки чому на атрибути поширюється контроль типів. Оскільки граф "володіє" всіма своїми атрибутами, їх збереження, відновлення і копіювання при виконанні відповідних операцій над графом здійснюється автоматично, повністю "прозоро" для програміста - користувача бібліотеки.

Приклад 6. Робота з атрибутами в бібліотеці AGraph.

Для підтримки атрибутів у бібліотеці використовується власний механізм розподілу пам'яті, який забезпечує високу ефективність операцій створення і знищення атрибутів і мала витрата пам'яті для зберігання атрибутів. Єдиним недоліком даного підходу є відносно повільний доступ до атрибутів: основним способом ідентифікації атрибуту є його ім'я, тому при кожному зверненні до атрибуту по імені здійснюється пошук в таблиці імен атрибутів. Бібліотека AGraph надає низькорівневі засоби, що дозволяють значно понизити "накладні витрати" на доступ до атрибутів (ціною деякого ускладнення програмування і потенційного зниження надійності). Так, можна один раз обчислити зміщення деякого атрибута в блоці пам'яті, відведеному для зберігання атрибутів, для того, щоб згодом звертатися до даного атрибуту по зсуві, а не по імені. Завдяки цьому виключається відносно повільний етап пошуку в таблиці імен атрибутів, але знижується надійність. Існує й інший спосіб підвищення продуктивності, найбільш ефективний при інтенсивному використанні атрибутів: перед початком роботи деякої процедури слід скопіювати атрибути в тимчасову структуру даних, яка підтримує прямий доступ (наприклад, динамічний масив), і надалі працювати з цією структурою, тобто використовувати на "локальному рівні" спосіб прив'язки даних до графа, який вже був розглянутий. Зрозуміло, в цьому випадку необхідно пам'ятати про синхронізацію графа і тимчасової структури даних.

Атрибути в бібліотеці AGraph призначені не тільки для прив'язки даних користувача, але і активно використовуються всередині самої бібліотеки. Наприклад, для ребер графа (клас TEdge) визначено метод RingEdge, який перевіряє, чи є ребро кільцевим (тобто при видаленні даного ребра кількість зв'язкових компонент графа не збільшується). Оскільки ця перевірка є відносно дорогою операцією (час виконання може досягати O (n + m)), небажано здійснювати її при кожному зверненні до методу RingEdge. У бібліотеці використовується наступний прийом: при першому зверненні до методу RingEdge бібліотека виконує відповідний алгоритм, створює глобальний атрибут ребер графа і запам'ятовує в ньому результат роботи алгоритму. До тих пір, поки граф не зазнає змін, які можуть спричинити порушення правильності запомненних значень, при наступних зверненнях до методу RingEdge повертається запам'ятоване значення. Якщо граф піддасться таких змін, то атрибут буде автоматично знищений. Те ж саме можна було б зробити, додавши в клас TEdge додаткове поле для запам'ятовування результатів виконання методу RingEdge, однак у такому разі за відсутності звернень до методу RingEdge пам'ять, необхідна для зберігання даного поля, витрачалася б даремно.

6. Підтримка різних видів графів

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

Бібліотеки LEDA явно підтримує два види графів - орієнтовані та неорієнтовані графи: в бібліотеці визначені параметрізуемие класи (GRAPH і UGRAPH) для кожного з цих видів. Будь-які засоби для підтримки інших видів графів не передбачені. Якщо процедура або функція є специфічною для графа певного виду (наприклад, функція знаходження максимального потоку в транспортній мережі), то всі необхідні параметри (в останньому прикладі - пропускні спроможності дуг мережі) безпосередньо передаються в цю процедуру або функцію (наприклад, за допомогою динамічних масивів ).

Бібліотека GTL (Н-Новгород) також безпосередньо підтримує орієнтовані та неорієнтовані графи - конструктори класів-графів за замовчуванням будують неорієнтований граф, проте існують варіанти конструкторів з явним завданням "орієнтованості" графа. У той же час, бібліотека підтримує і інші види графів за допомогою класів-"присмаків". Алгоритми, специфічні для конкретних видів графів, реалізовані як звичайні функції-члени (методи) параметрізуемих класів графів, але в цих функціях неявно передбачається, що класи-вершини і класи-ребра, використовувані при конкретизації даного параметрізуемого класу графів, надають необхідні інтерфейсні функції. Це, у свою чергу досягається спадкуванням класів-вершин і класів-ребер від відповідних класів-"присмаків".

Бібліотека AGraph пропонує високорівнева (хоча і не цілком універсальний) підхід до вирішення проблеми підтримки різних видів графів, що використовує можливості бібліотеки по динамічному створенню і знищенню атрибутів. У бібліотеці визначений набір "властивостей" графа, які відповідають конкретним видам графів. Поточна версія бібліотеки підтримує орієнтовані графи, дерева, транспортні мережі, зважені графи, геометричні графи. Не всі "властивості" є незалежними: так, транспортна мережа завжди є орієнтованим графом.

Підтримка всіх "властивостей" реалізована в одному і тому ж класі TGraph, який має властивість (в сенсі property мови Object Pascal) Features типу "безліч". У процесі виконання графу можна привласнити будь-яку комбінацію зумовлених "властивостей" графів (див. приклад 7). При цьому бібліотека автоматично створює необхідні атрибути і дозволяє використання специфічних для даного "властивості" методів (інакше спроба їх застосування призводить до порушення виняткової ситуації). Завдяки тому, що бібліотеці відомо, до яких видів відноситься даний граф, операції запису графа в потік і читання з потоку, а також копіювання графів відпрацьовуються коректно (зі збереженням всієї "видовий" інформації), причому це не вимагає додаткової роботи з боку програміста - користувача бібліотеки. Підтримувані нинішньою версією бібліотеки AGraph види не вичерпують всіх можливих різновидів графів, які можуть знадобитися при вирішенні прикладних завдань, проте навіть цей набір здатний значно полегшити роботу прикладного програміста.

Приклад 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 графа покажчик на цю вершину. Кожна вершина дерева, крім кореня, містить посилання на батьківську вершину (Parent). Для побудови дерева слід використовувати метод 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-форматів.

Приклад 8. Використання класу TChemGraph.

10. Ефективність

При створенні бібліотеки AGraph в якості основних цілей було поставлено забезпечення універсальності і простоти використання бібліотеки. Міркування ефективності враховувалися в тій мірі, в якій це не суперечило досягненню цих цілей. У той же час, рішення багатьох прикладних задач вимагає обробки графів великого розміру, та можливість вирішення цих завдань на доступних обчислювальних засобах безпосередньо залежить від ефективності реалізації тих чи інших алгоритмів.

Для оцінки ефективності засобів бібліотеки AGraph було здійснено рішення ряду тестових завдань; ті ж завдання вирішувалися за допомогою бібліотеки LEDA. Оскільки дані бібліотеки використовують різні внутрішні представлення графів, різні методи прив'язки атрибутів до вершин і ребер графа, а також способи передачі параметрів і повернення результатів, пряме порівняння результатів цих випробувань не зовсім коректно. Тим не менш, результати показують, що швидкісні характеристики бібліотек AGraph і LEDA є, принаймні, порівнянними (див. таблицю 1).

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

* У бібліотеці AGraph зберігання графа такого розміру зажадало близько 26 Мб оперативної пам'яті і 21 Мб на диску в форматі GML.

Література