ти до ефективного використання обчислювальних ресурсів). Поряд з "Промисловим" програмування, універсальні бібліотеки для роботи з графами можуть застосовуватися у навчальних цілях, а також для підтримки теоретичних досліджень, пов'язаних з алгоритмами і програмами вирішення завдань теорії графів. В обох випадках універсальність проблемної орієнтації бібліотеки більш важлива, ніж максимальна ефективність реалізованих у ній алгоритмів. p>
В§ 2. Об'єктно-орієнтовані бібліотеки для роботи з графами 1. Переваги ООП при створенні бібліотек для роботи з графами
При створенні "першого покоління" бібліотек для роботи з графами використовувалися мови програмування Fortran, Algol, PL1, потім С [1]. Для вирішення теоретико-графових завдань використовувалися і непроцедурні мови, такі, як мова функціонального програмування LISP і логічного програмування PROLOG, однак через недостатню ефективність і технологічних труднощів розробки великих програмних систем на цих мовах ці мови не підходять для створення універсальних бібліотек. p> З розвитком об'єктно-орієнтованого програмування (ООП) почалася розробка об'єктно-орієнтованих бібліотек для роботи з графами. Використання коштів ООП при вирішенні теоретико-графових завдань дає суттєві переваги порівняно з традиційним структурним підходом, оскільки сам граф, його вершини і ребра є "готовими" об'єктами, даними самою природою завдання. До достоїнств ООП, які найбільш яскраво проявляються при роботі з графами, можна віднести наступне:
програмний код стає більш компактним, поліпшується його читаність; при реалізації алгоритмів з'являється можливість абстрагуватися від деталей внутрішнього представлення графа; внутрішнє подання графа можна змінювати в широких межах без впливу на "високорівневі" складові бібліотеки; легко вирішується проблема "прив'язки" даних до вершин і ребрах графа.
2. Огляд існуючих ГО-бібліотек для роботи з графами
В даний час існує декілька об'єктно-орієнтованих бібліотек, що надають кошти для роботи з графами. Серед них можна відзначити:
LEDA (Library of Efficient Data types and Algorithms); GTL (Graph Template Library, University of Passau); GTL (Graph Template Library, Євген Ципнятов, Нижній Новгород), далі - GTL (Н-Новгород).
Всі ці бібліотеки написані на мові C + +. p> Бібліотека LEDA (остання версія - 3.8) [2] розробляється з 1988р. в Інституті Інформатики Макса Планка (Сарабрюккен, ФРН). Бібліотека пропонує різні абстрактні типи даних (стеки, черги, пріоритетні черзі, відображення, списки, множини, розбиття, словники, інтервальні безлічі тощо), спеціалізовані числові типи даних (раціональні числа, великі речові числа, алгебраїчні числа тощо), графи і допоміжні структури даних для роботи з графами. У LEDA реалізовані алгоритми вирішення ряду комбінаторних, алгебраїчних, геометричних і теоретико-графових завдань, засоби графічного введення і виведення. Інститут Інформатики Ма...
