Моделирование сетей связи. Визуализация несвязных графов

Гойхман В. Ю., Есалов К. Э., Ермаков А. В., Яковлев В. В.

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

  Моделирование сетей связи. Визуализация несвязных графов (1,72 MB)

Аннотация

В статье представлен анализ использования алгоритма Камада и Каваи для визуализации нескольких сегментов сети как общего несвязного графа, рассмотрены формальные критерии, определяющие применения данного алгоритма на небольших и средних сетях. Далее рассмотрены методы визуализации несвязного графа посредством выделения связных компонент, описана библиотека Boost Graph Library, представлена методика визуализации сети как общего несвязного графа. 

Ключевые слова:

силовые алгоритмы визуализации- force-based drawing algorithms; алгоритм Камада и Каваи - Kamada-Kawai algorithm; визуализация несвязных графов - visualization of disconnected graphs; задача раскроя материала - problem of materials cutting; алгоритмы упаковки - mapping algorithms; жадные алгоритмы - greedy algorithms; библиотеки визуализации графов - graphs visualization libraries; Boost Graph Library.

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

1. Handbook of graph drawing and visualization / ed. by R. Tamassia [et al.]. — Boca Raton: CRC Press, 2013. — 862 p.

2. Касьянов, В. Н. Графы в программировании: обра- ботка, визуализация и применение / В.Н. Касьянов, В.А. Евстигнеев. — СПб.: БХВ Петербург, 2003. — 1104 с.

3. Graph drawing: .algorithms for visualization of graph / G. Di Battista [et al.]. — New Jersey: Prentice Hall, 1999. — 397 p.

4. Kamada, T. An algorithm for drawing general undirected graphs / T. Kamada, S. Kawai / / Information Processing Letters. — 1989. — Vol. 31. — P. 7 — 15.

5. Харари, Ф. Теория графов / Ф. Харари. — М.: Эдито- риал УРСС, 2003. — 302 с. 

6. Оре, О. Графы и их применение / О. Оре. — М.: КомКнига, 2006. — 172 с.

7. Кормен, Т.Х. Алгоритмы: построение и анализ / Т.Х. Кормен. — М.: Вильямс, 2013. — 1328 с.

8. Сик, Дж. C++ Boost Graph Library / Дж. Сик, Э. Ламсдэйн. — СПб.: Питер. 2006. — 304 с.

9. Виноградов, И. М. Математическая энциклопедия / И.М. Виноградов. — М.: Советская энциклопедия, 1977 — 1985. — 1105 с.

10. Канторович, Л. В. Рациональный раскрой промыш- ленных материалов / Л.В. Канторович, Э.А. Мухачева. — СПб.: Невский диалект, 2012. — 303 с.

11. Мэйерс, С. Эффективное использование C+ + : 55 верных советов чтобы улучшить структуру и код ваших программ / С. Мэйерс. — М.: ДМК Пресс, 2006. — 300 с.

12. Лоскутова, А. А. QNET. Система администриро- вания и мониторинга сети / А.А. Лоскутова, А.С. Белов / / T-Comm: Телекоммуникации и транспорт. — 2016. — Т. 10, № 2. — С. 48—52.

13. Vareldzhyan, K. Babel routing protocol research using quagga software router / K. Vareldzhyan, V. Fitsov / / Internet of Things and its Enablers (INTHITEN) Proceecing / Boris Goldstein, Andrey Koucheryavy; Saint-Petersburg State University of Telecommunications, 2013. — P. 118—123