Читать учебное пособие по информатике, вычислительной технике, телекоммуникациям: "AGraph: библиотека классов для работы с помеченными графами" Страница 17
(Назад)
(Cкачать работу)размера, и возможность решения этих задач на доступных вычислительных средствах напрямую зависит от эффективности реализации тех или иных алгоритмов.
Для оценки эффективности средств библиотеки 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.
Литература
Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях. - Новосибирск, Наука (сибирское отделение), 1990.Mehlhorn K., Naher St. The LEDA Platform of Combinatorial and Geometric Computing. - Cambridge University Press, 1999.Цыпнятов Е. Библиотека классов для программирования задач теории графов, дипломная работа. - Нижний Новгород, 1998.Object Pascal Language Guide. Borland Delphi 3 for Windows 95 and Windows NT - Borland International Inc., 1997.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.Mehrotra A., Trick M.A. A Column Generation Approach for Exact Graph Coloring / INFORMS Journal on Computing, 8:4, 1996.Himsolt M. GML: A Portable Graph File Format / Technical Report, Universitat Passau, 1997, cf.; см. также краткое описание GML.
Похожие работы
Интересная статья: Быстрое написание курсовой работы