Построение алгоритмов ортогонального представления графа с указанными портами рёбер тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Ворожцов, Артём Викторович

• Ворожцов, Артём Викторович
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Ворожцов, Артём Викторович

Введение

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

1.1 Ссылки на базовые алгоритмы и ключевые работы

1.2 Компьютерные системы.

Система Graphviz.

Библиотека алгоритмов LEDA и системы yEd, AGD.

1.3 Задача поиска оптимального линейного порядка.

Основные понятия и формулировка ключевых задач.

Обзор приближенных алгоритмов решения задач OLA

2 "Человеческие" методы решения сложных задач

2.1 Базовые составляющие алгоритмов решения сложных задач

Метод divide: "разделяй и властвуй".

Метод parallel: распараллеливание.

Метод competition: отбор лучших.

Метод local: локальные улучшения, "жадные" алгоритмы

Метод scale: огрубление.

Метод macro: введение макро-объектов.

Метод meta: метасистемные переходы в программировании

2.2 Инструментарий для Л/*'Р-программирования.

3 Задача ортогонального представления графа с портами

3.1 Общая задача плоского ортогонального представления графа

3.2 Задача представления графа с заданными портами рёбер

3.3 Сводимость OOGLP к OOGL.

4 Эвристические алгоритмы решения задачи OOGLP

4.1 Идеи решения.

4.2 Схема основного алгоритма.

4.3 Метод ранжирования последовательными улучшениями.

4.4 Метод ранжирования на основе физической модели.

4.5 Метод выделения каркаса графа.

4.6 Спектральные методы ранжирования.

4.7 Задача проведения рёбер.

4.8 Задача выпрямления рёбер.

4.9 Примеры работы алгоритма ortho

4.10 Реализация алгоритмов.

5 Методы анализа приближённых алгоритмов

5.1 Сила алгоритма и мера зависимости сил двух алгоритмов

5.2 Понятия надёжности и полезности алгоритмов.

5.3 Результаты сравнительного анализа.

6 Задача OLA и вычислительная сложность

6.1 Задача о лидере — два метода ранжирования.

6.2 Модель "Естественный отбор".

6.3 Модель "Обмен товаров".

6.4 Ранжирование по вычислительной сложности

Введение диссертации (часть автореферата) на тему «Построение алгоритмов ортогонального представления графа с указанными портами рёбер»

Системы автоматической визуализации данных сегодня востребованы и активно развиваются. Это связано с увеличением объёмов информации и сложности структур, возникающих в практических задачах. Требуются инструменты для наглядного представления и анализа информации.

Актуальной задачей является автоматическое построение организационных IDEF- Вх°Д диаграмм. IDEF (Integrated Computer-Aided

Manufacturing Definition) — это стандарт

Функциональный блок управление Выход механизм моделирования технологических операций, компьютерных систем и бизнес-процессов. ^

В частности, стандарт ГОЕРО касается моделирования управляющих бизнес-процессов предприятия. Этот стандарт описывает правила представления схемы управления предприятия в виде набора функциональных блоков, соединённых ломанными линиями. Блоки изображаются прямоугольниками, стороны которых называются портами. В верхнюю часть функционального блока (северный порт) идут стрелки от функциональных блоков, которые им управляют, в западный порт поступает вход, из восточного порта идёт выход, в южный порт выходят стрелки от блоков, определяющих механизм работы данного блока (см. рис. 1).

Задача представления графов, для рёбер которых указаны порты, возникает при построении не только ГОЕР-диаграмм, но и ряда других схем: ЭАБТ-схем, иМЬ-диаграмм, блок-схем и др.

Целью работы была разработка программы для автоматического построения IDEF-диаграмм, то есть программы, решающей задачу поиска оптимального ортогонального представления графов с указанными портами рёбер (Optimal Orthogonal Graph Layout with Ports, OOGLP). Оптимальность представления графа определяется числом пересечений и изгибов представлений рёбер, площадью представления и суммарной длиной представлений рёбер.

Раздел теории алгоритмов, посвященный представлениям графов (Graph Drawing, GD), активно развивался начиная с 1980 года [7, 8] и сейчас содержит ряд интересных решений для специальных случаев представлений. Различные варианты задачи оптимального плоского представления графа порождаются множеством ограничений на входной граф (ограничения на степени вершин, планарный граф или нет, плотный или разреженный, ориентированный или неориентированный), типами представлений рёбер (прямые линии, ломанные, "ортогональные" ломанные, кривые Безье), различными ограничениями на представление в целом (решётчатые представления, многослойные представления, ограничения на пересечения и изгибы, ограничения на длины ребер, ограничения на расстояния между объектами, ограничения на площадь представления), а также различными целевыми функциями (число пересечений, площадь представления, число изгибов рёбер, суммарная длина рёбер, максимальная длина ребра, комбинации этих функций).

Специфика рассматриваемой здесь задачи OOGLP описывается следующими условиями: а) граф произвольный; б) ребра представляются ломанными, звенья которых параллельны осям координат; в) вершины (функциональные блоки) представляются прямоугольниками заданных размеров; г) для каждого ребра указана сторона узла, из которой оно должно выходить, и сторона узла, куда оно должно входить; д) необходимо минимизировать следующую целевую функцию:

Cost = ai • (длина ребер) + a<i • (число изгибов ребер) + з • (число пересечений ребер) +

4 ■ л/(площадь ограничивающего прямоугольника).

Пункт (г) наиболее важен. Ранее представления с таким ограничением не рассматривались.

Задача OOGLP как и множество других задач поиска представления графа, на котором достигается минимум целевой функции (функции штрафа), является А/'Р-сложной [4]. В частности, задача поиска плоского представления с минимальным числом пересечений рёбер (cross number problem, CNP) является Л/'Р-сложной [21]. Рассматриваемую задачу OOGLP можно частично свести к задаче поиска максимального ацикличного подграфа ориентированного графа, которая тоже является Л/'Р-сложной [32]. Кроме того, задачу OOGLP можно рассматривать как обобщение Л/""Р-сложной задачи поиска оптимального линейного порядка вершин ориентированного графа с взвешенными рёбрами (Optimal Linear Arrangement, OLA) [39] на двумерный случай. На задаче OLA опробован практически весь "арсенал" эвристических алгоритмов ("жадные" алгоритмы, метод отжига, генетические алгоритмы и др.). И многие идеи алгоритмов решения задачи OLA могут быть перенесены на задачу OOGLP.

Опишем содержание следующих глав диссертации.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Ворожцов, Артём Викторович

Заключение

Семейство задач на поиск оптимального ортогонального плоского представления графа является типичным примером плохо формализуемой сложной задачи. Попытки её формализовать приводят с ЛГР-сложным задачам. Такого сорта задачи всё чаще возникают на практике, и назрела необходимость разработки общих методов их решения.

Для разработки приближенного алгоритма решения этой задачи были использованы несколько известных метаэвристик (подходов к конструированию приближённых алгоритмов). Экспериментальное исследование качества алгоритмов показали, что лучше всего работает алгоритм, в котором удалось реализовать несколько метаэвристик. Подобная ситуация типична для сложных задач. Хороших результатов можно достичь лишь путём синтеза нескольких идей.

Дальнейшие развитие разработанных алгоритмов возможна в направлении метаэвристики масштабирования, а также доработке алгоритма stem, основанного на выделении максимального простого каркаса графа.

Алгоритмы spectr и mover также могут быть доработаны — есть несколько способов применения метаэвристики macro для повышения качества результата и уменьшения времени работы.

Резюмируем основные результаты работы.

1. В работе разобраны базовые методы Л^Р-программирования, позволяющих эффективно приближенно решать Л/'Р-сложные и трудно формализуемые задачи: метод огрубления задачи, жадные алгоритмы, метод локальных улучшений, метод введения макро-сущностей, метод отбора лучших и общая идея метасистемного перехода при построении сложных систем и алгоритмов. Описан новый метод конструирования алгоритмов macro, основанный на введение макро-сущностей (макро-объектов и макро-действий с ними). Предложено несколько вариантов применения этих методов для построения приближённых алгоритмов решения задачи OOGLP.

2. Разработано несколько приближённых алгоритмов, решающих задачу оптимального ортогонального представления графа на плоскости с указанными портами рёбер (задачу OOGLP):

• model — алгоритм, основанный на моделировании физической системы с пружинами и различными типами взаимодействия вершин графа;

• mover — алгоритм, основанный на методе последовательных локальных улучшений;

• spectr — алгоритм, основанный на построении "матрицы взаимодействия" узлов графа и вычислении доминантного собственного вектора этой матрицы;

• stem — алгоритм, основанный на выделении максимального подграфа, который может быть нарисован без решения сложной оптимизационной задачи;

3. Проведён сравнительный анализ разработанных алгоритмов, указаны достоинства и недостатки каждого из них. Введены важные понятия надёжности и полезности эвристических алгоритмов и описаны методы экспериментальной оценки этих величин. Исследована эффективность комбинирования разработаных алгоритмов и показано, что метод model является наиболее гибким и надежным алгоритмом для широкого класса графов, а алгоритм stem часто оказывается лучшим для разрежённых графов, поэтому на практике полезно комбинировать ("складывать") алгоритмы model и stem. Построена диаграмма сложения алгоритмов на плоскости {полезность, надежность}.

4. Разработана компьютерная система ort ho, в которой реализованы эти алгоритмы, и которая позволяет получать представления графов в различных графических форматах и различных стилях. Разработанная система предоставляет возможность задавать параметры алгоритмов, выбирать тип представления, а также балансировать между качеством результата и временем работы программы. Кроме того, есть возможность варьировать параметры целевой функции (функции штрафа), задавая штрафы за пересечения и изгибы рёбер, их ссуммарную длину, а также общую площадь представления.

Список литературы диссертационного исследования кандидат физико-математических наук Ворожцов, Артём Викторович, 2005 год

1. ABACUS A framework for branch-and-cut algorithms, http: / / www .informatik.uni-koeln.de/abacus /

2. AGD — library of Algorithms for Graph Drawing, http://www.mpi-sb.mpg.de/AGD/

3. Angeline P. Evolutionary Algorithms and Emergent Intelligence. PhD thesis, Ohio State University, Computer Science Department, 1993.

4. A compendium of MV optimization problems, Editors: Pierluigi Crescenzi, and Viggo Kann,http://www.nada.kth.se/~viggo/wwwcompendium/

5. Atkins J. E., Boman E. G., Hendrickson В. A Spectral Algorithm for Seriation and the Consecutive Ones Problem, SIAM Journal on Computing 28 (1998), 297-310.

6. Adolphson D., Ни Т. С. "Optimal linear ordering", SIAM Journal on Applied Mathematics, 25(3):403-423, 1973.

7. Battista G. D., Eades P., Tamassia R., Tollis I. G., Algorithms for Drawing Graphs: an Annotated Bibliography, 1994,ftp://ftp.cs.brown.edu/pub/papers/compgeo/.

8. Battista G. D., Eades P., Tamassia R., Tollis I. G., "Graph Drawing Algorithms for the Visualization of Graphs", 1999.

9. Berger В., Shor P. W. Approximation algorithms acyclic subgraph problem. Proc. of the first annual ACM-SIAM Symp. on Discrete Algorithms, pp. 236243, SIAM, Philadelphia, 1990.

10. Doxygen documentation system,http: //www. stack. nl/^dimitri/doxygen/index. html.

11. Diaz J., Petit J., Serna M. A Survey on Graph Layout Problems, Technical report LSI-00-61-R, Universität Politécnica de Catalunya, Departament de Llenguatges i Sistemes Informatics, 2000. http://www.lsi.upe.es/dept/techreps/ps/R00-61.ps.gz

12. Eades P., Lin X. A new heuristic for the feedback arc set problem, Australian Journal of Combinatorics, 12:15-26, 1995.

13. Ellson J., TclDG A Tel Extension for Dynamic Graphs, 1996.

14. Emden R. Gansner, North S. C. "An open graph visualization system and its applications to software engineering", 1999,http://www.graphviz.org/Documentation.html.

15. Essays and Surveys in Metaheuristics Series: Operations Research/Computer Science Interfaces Series, Vol. 15 Ribeiro, Celso C.; Hansen, Pierre (Eds.) 2001, 664 p., Hardcover.

16. Even G., Naor J. S., Rao S., Scieber B. "Divide-and-Conquer approximation algorithms via spreading matrices", in Proc. 36th Annual IEEE Symposium on Foundation of Computer Science, IEEE Computer Society Press, pp. 62-71, 1995.

17. Even G., Naor J. S., Rao S., Scieber B. "Fast Approximate Graph Partition Algorithms", 8th Annual ACM-SIAM Symposium on Disc. Algo., pp. 639-648, 1997.

18. Even S., Shiloach Y. "./VP-Completeness of several arrangement problems", Technical Report 43, Isreal Institute of Technology, 1975.

19. Gansner E. R., Koutsofios E., North S. C., Vo K. P. "Graph Visualization in Software Analysis" Proc. Symposium on Assessment of Quality Software Development Tools, IEEE Computer Society Press, New Orleans LA, May 27-29, 1992.

20. Garg A., Tamassia R. "On the Computational Complexity of Upward and Rectilinear Planarity Testing," Technical Report CS-94-10, Dept. of Computer Science, Brown Univ., 1994.

21. Garey M. R., Johnson D. S. "Crossing Number is NP-Complete", SIAM J. Algebraic and Discrete Methods, Vol. 4, No. 3, pp. 312-316, 1983.

22. Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of AAP-Completeness, W. H. Freeman and Company, NY, 1979.

23. Garey M. R., Johnson D. S., Stockmeyer L. "Some simplified ./VP-complete graph problems". Theoretical Computer Science, 1: pp. 237-267, 1976.

24. GiST for PostgreSQL, http://www.sai.msu.su/ megera/postgres/gist/

25. GraphViz — Graph Drawing Tools, http://www.graphviz.org,

26. Grdtschel M., Jiinger M., Reinelt G. "On the acyclic subgraph polytope", Mathematical Programming, 33, pp. 28-42, 1985.

27. Harary F. Problem 16. In M. Fieldler (Ed.), "Theory of Graphs and its Applications", Czech. Academy of Sciences, Prague, 1967.

28. Harper L. H. "Optimal assignment of numbers to vertices", SIAM Journal, 12, pp. 131-135, 1964.

29. IDEF — A structured approach to enterprise modeling and analysis, http://www.idef.com

30. Johnson, D. S. A catalog of complexity classes, in Algorithms and Complexity, volume A of Handbook of Theoretical Computer Science, Handbook of Theoretical Computer Science, Elsevier science publishing company, Amsterdam, pp. 67-161, 1990.

31. Juvan M., Mohar B. "Optimal Linear Labelings and Eigenvalues of Graphs", Discrete Applied Math. 36 (1992), 153-168.

32. Karp R. M. "Reducibility among combinatorial problems", Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, Eds. Plenum, New York, pp. 85103, 1972.

33. Kamada T. On Visualization of Abstract Objects and Relations, Ph.D. dissertation, Dept. of Information Science, Univ. of Tokyo, 1988.

34. Koren Y., Harel D. Multi-Scale Algorithm for the Linear Arrangement Problem, Technical Report MCS02-04, Faculty of Mathematics and Computer Science, The Weizmann Institute of Science, 2004.

35. LEDA, LEDAGraphAlgo Library of Algorithms on Graphs, http://www.algorithmic-solutions.com/

36. Leighton F. T. Complexity issues in VLSI, MIT Press, 1983.

37. Lovasz L. On the Shannon capacity of the graph, IEEE Trans. Inform, Theory 25 (1979), 1-7.

38. Metaheuristics, Progress as Real Problem Solvers Series: Operations Research /Computer Science Interfaces Series, Vol. 32 Ibaraki, Toshihide; Nonobe, Koji; Yagiura, Mutsunori (Eds.) 2005, XII, 414 p. 106 illus., Hardcover.

39. Petit J. Experiments on the Minimum Linear Arrangement Problem, Technical report LSI-Ol-7-R, Universität Politècnica de Catalunya, Departament de Llenguatges i Sistemes Informatics, 2001.

40. Rudich A., Zernik D., Zodik G. "Visage — Visualization of Attribute Graphs: A foundation for a Parallel Programming Environment," Environments and Tools for Parallel Scientific Computing North Holland, Ed. J.J. Dongarra and B. Tourancheau, pp. 171-192.

41. Shiloach ^"Arrangements of Planar Graphs on the Planar Lattice", Ph.D. Thesis, Weizmann Institute of Science, Rehovot, Israel, 1976.

42. Smart J. C. and Vemuri V. A-Vu: A Visualization Tool for Complex Software Systems. Proc. Symposium on Assessment of Quality Software Development Tools, IEEE Computer Society Press, New Orleans LA, May 27-29, 1992.

43. Storer J. A., "On Minimal Node-Cost, Planar Embeddings," Networks, vol. 14, pp. 181-212, 1984.

44. Sugiyama K., Tagawa S., Toda M. "Methods for visual understanding of hierarchical systems structures", IEEE Transactions on Systems, Man and Cybernetics 11, pp. 109-125, 1981.

45. Sugiyama K., Misue K. Visualization of Structural Information: Automatic Drawing of Compound Digraphs, IEEE Transactions on Systems, Man and Cybernetics, vol. 21, no. 4, pp. 876-892, 1991.

46. Tamassia R. "On Embedding a Graph in the Grid with the Minimum Number of Bends", SIAM J. Computing, vol. 16, no. 3, pp. 421-444, 1987.

47. Tamassia R., Tollis I. G. "Efficient Embedding of Planar Graphs in Linear Time," Proc. IEEE Int. Symp. on Circuits and Systems, pp. 495-498, Philadelphia, 1987.

48. Tamassia R., Tollis I. G. "Planar Grid Embedding in Linear Time," IEEE Trans, on Circuits and Systems, vol. CAS-36, no. 9, pp. 1230-1234, 1989.

49. The GNU General Public License,http://www.gnu.org/licenses/licenses.html51. yEd — Java Graph Editor,http://www.yworks.com/en/productsyedabout.htm.

50. Берж К. Теория графов и её применения.// М.: Изд-во иностр. лит, 1962.

51. Вороэюцов А. В. Алгебраические методы определения сложности: Препринт / ИПМ РАН. М., 2001. - №17. - 23 с.

52. Вороэюцов А. В. Прогнозирование и теория сложности: Препринт / ИПМ РАН. М, 2001. - №18. - 17 с.

53. Вороэюцов А.В. Индустрия знаний.// Информационные технологии и вычислительные ситемы, 1-2, 2003, С. 20.

54. Вороэюцов А.В. Задача о лидере и упорядочивание по вычислительной сложности.// Моделирование процессов управления. М.МФТИ, 2004. С. 218-228.

55. Вороэюцов А.В. Эвристические алгоритмы кластеризации для маломерных пространств.// Современные проблемы фундаментальных и прикладных наук: Труды XLV Научной Конференции МФТИ. Часть VIII.-Долгопрудный, 2003 С. 54.

56. Вороэюцов А.В., Винокуров Н.А. Два приближенных алгоритма решения задачи коммивояжера.// Моделирование процессов управления. М., 2004. С. 211-217.

57. Вороэюцов А.В. Критерии интеллектуальности искусственных систем: Препринт / ИПМ РАН. М., 2004. - №60. - 26 с.

58. Вороэюцов А.В. Критерии интеллектуальности искусственных систем.// Рефлексивные процессы и управление. Том 4, №2, 2004. С.18-29.

59. Ворожцов A.B. Мета-методы ЛЛР-программирования: Препринт / ИПМ РАН. М., 2005. - №43. - 18 с.

60. Журавлев Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов I, II, III.// Кибернетика, 1977, Я® 4, с. 14 21, № 6, с. 21 - 27; 191., № 2, с. 35 - 43.

61. Прасолов В. В. Задачи и теоремы линейной алгебры.// М.:Наука. Физ-матлит. 1996. 304 с.

62. Тамасия Р., Ресурс материалов по представлению графов, http://www.es.brown.edu/people/rt/ .

63. Турчин В. Ф. Феномен науки: Кибернетический подход к эволюции, М.: Наука, 295 е., 1993, http://pespmcl.vub.ac.be/POSBOOK.html.