AGraph: бібліотека класів для роботи з поміченими графами
В§ 1. Актуальність розробки бібліотек для роботи з графами
До теперішнього часу накопичений великий досвід вирішення теоретико-графових задач на ЕОМ. Програми для вирішення багатьох завдань можна знайти в глобальній мережі Інтернет. У той же час, використання незалежно розроблених програм пов'язане з великими труднощами. До їх числа відносяться як загальні, не залежні від предметної області, технічні проблеми (різні мови програмування, несумісність програмних і апаратних засобів), так і проблеми, пов'язані зі специфікою теоретико-графових завдань (використання різних внутрішніх уявлень графів). У зв'язку з цим актуальним завданням є розробка більш-менш універсальних бібліотек, які, з одного боку, надавали б користувачеві високорівневі засоби для роботи з графами, а з іншого, позбавляли його від необхідності ручного програмування рутинних операцій введення-виведення або перетворень між різними внутрішніми уявленнями графів. p> Розробка універсальної бібліотеки для роботи з графами є складним завданням. Однією з проблем є велика різноманітність задач теорії графів. Оскільки теоретичні дослідження та розробка нових алгоритмів безперервно тривають, очевидно, що ніяка бібліотека не зможе вирішувати всі існуючі завдання. Іншою проблемою є забезпечення ефективності. Нерідко існує кілька алгоритмів для вирішення однієї і тієї ж задачі, причому не завжди можна вказати алгоритм, оптимальний у всіх випадках: для одних графів більш ефективним може бути один алгоритм, для інших - інший. Дизайнер універсальної бібліотеки зазвичай не може дозволити собі реалізацію декількох алгоритмів для вирішення однієї задачі, тому йому доводиться йти на компроміси між ефективністю і універсальністю. При розробці бібліотек для роботи з графами виникають також численні технічні труднощі. Для прийнятною з точки зору ефективності реалізації багатьох алгоритмів програмісту необхідно мати у своєму розпорядженні такі структури даних, як динамічні масиви, списки, стеки, черги, пріоритетні черги, дерева пошуку. Реалізація всіх необхідних структур даних у рамках однієї бібліотеки навряд чи можлива і виправдана, тому універсальна бібліотека для роботи з графами вимагає серйозної програмної "інфраструктури" у вигляді інших бібліотек. p> Перераховані проблеми можуть викликати сумніви щодо доцільності створення універсальних бібліотек для роботи з графами, проте існують вагомі аргументи на користь їх створення. По-перше, реалізовані в подібній бібліотеці базові алгоритми можуть служити хорошою основою для створення більш спеціалізованих алгоритмів і програм, спрямованих на вирішення конкретних прикладних завдань. По-друге, міркування ефективності не завжди є визначальними - постійне зростання продуктивності ЕОМ все частіше виводить на перший план технологічність і швидкість розробки програмного забезпечення (Зрозуміло, це не означає, що програміст не повинен прагну...
