МЕТОД ВИЗУАЛИЗАЦИИ МЕТАГРАФА

Штогрина Елена Сергеевна, Кривенко Александра Сергеевна

2014 , ТОМ 14, НОМЕР 3 ( МАЙ-ИЮНЬ )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

УДК 519.1

МЕТОД ВИЗУАЛИЗАЦИИ МЕТАГРАФА

Штогрина Е.С., Кривенко А.С.

Читать статью полностью

Аннотация

Проведен анализ методов визуализации разных типов графов. Сделан вывод об актуальности разработки метода визуализации метаграфов. Описываются проблемы размещения узлов, принадлежащих и не принадлежащих метавершинам, пересечения фигур метавершин, которые возникают при решении задачи визуализации метаграфа. Данные проблемы рассмотрены на примере. Определены критерии, по которым полученное изображение считается наглядным для пользователя и однозначно соответствует заданному метаграфу. Поставлена задача визуализации метаграфа. Для ее решения предложен метод визуализации, основанный на принципах силовых алгоритмов. В рамках данного метода определены правила действия сил между узлами. Эти силы зависят от типа узлов, между которыми действуют, и наличия ребер между ними. Применение предложенного метода позволяет строить графическое представление метаграфа, который соответствует заданной предметной области. Метод не предполагает участия человека при формировании изображения, что позволяет экономить время при частых изменениях, которые требуют перестройки изображения. Полученное изображение позволяет визуализировать сущности предметной области и связи между ними, применить методы графического анализа. Определены дальнейшие направления работы – минимизация количества пересечений ребер и площади, занимаемой результирующим изображением. Модификация метода визуализации метаграфа с учетом данных направлений позволит улучшить визуальное представление метаграфа.

Ключевые слова: метаграф, визуализация, граф, метавершина, графическое представление

Список литературы

1. Grossman O., Harel D. On the algorithmics of higraphs. Technical Report, Rehovot, Israel. 1997. 32 p.

2. Basu A., Blanning R.W. Metagraphs and their applications. Springer, 2006. 172 p.

3. Eades P., Lin X. Springalgorithms and symmetry // Theoretical Computer Science. 2000. V. 240. N 2. P. 379–405.

4. Eades P. A heuristic for graph drawing// Congressus Nutnerantiunt.1984.N 42. P. 149–160.

5. Fruchterman T.M.J., Reingold E.M. Graph drawing by force-directed placement // Software-Practice and Experience. 1991. V. 21. N 11. P. 1129–1164.

6. Barnes J., Hut P. A hierarchical O (N log N) force-calculation algorithm // Nature. 1986. V. 324. N 4. P. 446–449.

7. Kamada T., Kawai S. An algorithm for drawing general undirected graphs // Information Processing Letters. 1989. V. 31. N 1. P. 7–15.

8. Hachul S., Junger M. Drawing Drawing large graphs with a potential-field-based multilevel algorithm // Lecture Notes in Computer Science. 2004. V. 3383. P. 285–295.

9. Archambault D., Munzner T., Auber D. TopoLayout: Multilevel graph layout by topological features // IEEE Transactions on Visualization and Computer Graphics. 2007.V.13. N 2. P. 305–316.

10.Harel D., Koren Y. A fast multi-scale method for drawing large graphs // Journal of Graph Algorithms and Applications. 2002. V. 6. N 3. P. 177–202.

11.Jin R., Xiang Y., Fuhry D., Dragan F.F. Overlapping Matrix Pattern Visualization: A Hypergraph Approach // Proc. of IEEE International Conference on Data Mining, ICDM. Pisa, Italy, 2008. Art. N 4781126. P. 313–322.

12.Paquette J., Tokuyasu T. Hypergraph visualization and enrichment statistics: How the EGAN paradigm facilitates organic discovery from big data // Proc. SPIE - The International Society for Optical Engineering. 2011. V. 7865. Art. N 78650E.

13.Астанин С.В., Драгныш Н.В., Жуковская Н.К. Вложенные метаграфы как модели сложных объектов // Инженерный вестник Дона. 2012. Т. 23. № 4-2 (23). С. 76.

14.Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ. 2-eизд. М.: Вильямс, 2005. 1296c.

15.Роджерс Д., Адамс Дж. Математические основы машинной графики. М.: Мир, 2001. 604 с.

16.Holten D. Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data // IEEE Transactions on Visualization and Computer Graphics. 2006. V. 12. N 5. P. 741–748.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License