Анализ алгоритмов автоматической расстановки сущностей и построения связей

Авторы: Киряков Е.А., Левинский А.Т.
Опубликовано в выпуске: #4(33)/2019
DOI: 10.18698/2541-8009-2019-4-469
Раздел: Информатика, вычислительная техника и управление | Рубрика: Системный анализ, управление и обработка информации, статистика
Ключевые слова: алгоритм, автоматизация, связи, построения, генетический алгоритм, модель, генетический, аналитический, мутация, расстановки сущностей, построения связей
Опубликовано: 30.04.2019

Большие системы часто удобно изучать с помощью концептуальных диаграмм (например, диаграмм сущность-связь или UML). Для автоматического построения таких диаграмм требуются алгоритмы автоматической расстановки сущностей и автоматического построения связей. В связи с этим был выполнен анализ существующих алгоритмов автоматической расстановки сущностей и автоматического построения связей. Приведены три основные группы алгоритмов: алгоритмы на основе физической модели, аналитические алгоритмы и генетические алгоритмы. По каждой группе алгоритмов передана основная информация, перечислены плюсы и минусы каждой группы алгоритмов. Помимо этого для каждой группы алгоритмов разобрано несколько конкретных алгоритмов. Изучение материалов данной статьи даст читателям базовые знания об основных группах алгоритмов и поможет понять принцип их работы.

Литература

[1] Соколов Г.В. Анализ алгоритмов автоматической укладки графов на плоскости в рамках задачи визуализации моделей на графах. Вестник Пермского Государственного Технического Университета. Прикладная математика и механика, 2008, № 15, с. 162–171.

[2] Dickerson M., Eppstein D., Goodrich M.T., et al. Confluent drawings: visualizing non-planar diagrams in a planar way. JGAA, 2005, vol. 9, no. 1, pp. 31–52. DOI: 10.7155/jgaa.00099 URL: http://jgaa.info/getPaper?id=99

[3] Гладков Л.А. Решение задачи планаризации графов на основе бионических технологий. Вестник южного научного центра РАН, 2005, т. 1, № 2, с. 51–57.

[4] Davis L.D. Handbook of genetic algorithms. Van Nostrand Reinold, 1991.

[5] Nikolov N.S., Tarassov A. Graph layering by promotion of nodes. Discrete Appl. Math., 2006, vol. 154, no. 5, pp. 848–860. DOI: 10.1016/j.dam.2005.05.023 URL: https://www.sciencedirect.com/science/article/pii/S0166218X05003100

[6] Siirtola H., Makinen E. The Barycenter heuristic and the reorderable matrix. Informatica, 2005, vol. 29, no. 3, p. 357–364.

[7] Carstens J.J. Node and label placement in a layered layout algorithm. Master Thesis. University of Kiel, 2012.

[8] Patarasuk P., Whalley D. Crossing reduction for layered hierarchical graph drawing. Master Thesis. Florida State University, 2004.

[9] Genc B., Dogrusoz U. An algorithm for automated layout of process description maps drawn in SBGN. Bioinformatics, 2016, vol. 32, no. 1, pp. 77–84. DOI: 10.1093/bioinformatics/btv516 URL: https://academic.oup.com/bioinformatics/article/32/1/77/1742665

[10] Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М., Вильямс, 2000.