Українська
Отримано 29.08.2022, Доопрацьовано 24.11.2022, Прийнято 20.12.2022
Завдання візуалізації великих графів як спеціальної структури даних та алгоритмів на них розглядається вченими і практиками як складна і нетривіальна проблема. Аналіз наукових робіт та існуючих програмних додатків, що реалізують подібні функції предметної області, засвідчує актуальність розширення розвідок у напрямках виявлення особливостей розробки додатків для візуалізації великих графів та алгоритмів на них. Формулювання особливостей і рекомендацій щодо розробки такого програмного забезпечення та представлення спроєктованого авторами програмного модуля є метою статті. У ході роботи за допомогою методів аналізу та теорії графів виявлено та сформульовано основні особливості розробки програми для візуалізації графів з великою кількістю вершин. Надано окремі рекомендації щодо сутності кожного з етапів розробки таких додатків та виявлено ті кроки, які є найбільш важливими для розробників у термінах складності обробки та візуалізації великих графів, метрик їх розташування на екрані додатку тощо. Також представлено розроблений авторами модуль, який забезпечує уніфікований інтерфейс програмування додатків для візуалізації будь-якого алгоритму на графах, що дозволяє заощадити час на роботі над службовим програмним забезпеченням і більше зосередитися на розв’язанні алгоритмічних задач. Представлений модуль розроблено авторами з урахуванням виявлених особливостей та рекомендацій. Проведено порівняльний аналіз розробленого програмного модуля та аналогів, який засвідчив розширену функціональність модуля щодо візуалізації графів з великою кількістю вершин. Модуль є практично значущим інструментом для дослідників у галузі структур даних та інших експертів, які працюють над алгоритмами на графах, оскільки дає змогу візуалізувати дані при налагодженні програмного забезпечення та спрощує аналіз великих структур даних
великі графи; проблеми унаочнення алгоритмів; модуль візуалізації алгоритмів на графах; компонування графа; уніфікований програмний інтерфейс
[1] Lande, D., & Subach, I. (2021). Visualization and analysis of network structures. Kyiv: Igor Sikorsky Kyiv Polytechnic Institute, Politekhnika.
[2] Babkov, V., & Serik, M. (2011). Methods of visualization of data of complex structure based on tree-like maps. Scientific papers of Donetsk National Technical University. Series: Informatics, Cybernetics and Computer Science, 14(188), 163-170.
[3] Demianchuk, O. (2022). Principles of data visualization. Retrieved from https://dou.ua/forums/topic/39157/.
[4] Iguana, S. (2019). Large graph visualization tools and approaches. Retrieved from https://towardsdatascience.com/large-graph-visualization-tools-and-approaches-2b8758a1cd59.
[5] Beck, F., Burch, M., & Diehl, S. (2009). Towards an aesthetic dimensions framework for dynamic graph visualisations. In 2009 13th International Conference Information Visualisation (pp. 592-597). Barcelona: IEEE. doi: 10.1109/IV.2009.42.
[6] Noack, A. (2019). Energy models for graph clustering. Journal of Graph Algorithms and Applications, 11(2), 453-480. doi: 10.7155/jgaa.00154.
[7] Schwab, M., Strobelt, H., Tompkin, J., Fredericks, C., Huff, C., Higgins, D., Strezhnev, A., Komisarchik, M., King, G., & Pfister, H. (2017). An education system with hierarchical concept maps and dynamic nonlinear learning plans. IEEE Transactions on Visualization and Computer Graphics, 23(1), 571-580. doi: 10.1109/TVCG.2016.2598518.
[8] Wilke, C. (2019). Fundamentals of data visualization: A primer on making informative and compelling figures. Sebastopol: O’Reilly Media Inc.
[9] Jacomy, M., Venturini, T., Heymann, S., & Bastian, M. (2014). ForceAtlas2, a continuous graph layout algorithm for handy network visualization designed for the gephi software. PLoS ONE, 9(6): article number e98679. doi: 10.1371/journal.pone.0098679.
[10] Fruchterman, T.M.J., & Reingold, E.M. (2014). Graph drawing by force-directed placement. Journal of Software: Practise and Experience, 21(11), 1129-1164. doi: 10.1002/spe.4380211102.
[11] Cheong, S., & Si, Y. (2015). Accelerating Kamada-Kawai for boundary detection in mobile ad hoc network. ACM Transactions on Sensor Networks, 13(1), article number 3. doi: 10.1145/3005718.
[12] Shawn, M., Brown, W.M., Klavans, R., & Boyack, K.W. (2011). OpenOrd: An open-source toolbox for large graph layout. Visualization and Data Analysis 2011. Proceedings of the SPIE, 7868, article number 786806. doi: 10.1117/12.871402.
[13] Frick, A., Ludwig, A., & Mehldau, H. (1995). A fast adaptive layout algorithm for undirected graphs (extended abstract and system demonstration). In Tamassia, R., Tollis, I.G. (Eds.), Graph Drawing (pp. 388-403). Berlin: Springer. doi: 10.1007/3-540-58950-3_393.
[14] Sund, D. (2016). Comparison of visualization algorithms for graphs and implementation of visualization algorithm for multi-touch table using JavaFX. Linköping: Linköpings Universitet.
[15] Banerjee, A. (2020). Computational complexity of PCA. Retrieved from https://alekhyo.medium.com/computational-complexity-of-pca-4cb61143b7e5.
[16] Bauer, R., Delling, D., Sanders, P., Schieferdecker, D., Schultes, D., & Wagner, D. (2010). Combining hierarchical and goal-directed speed-up techniques for dijkstra’s algorithm. ACM Journal of Experimental Algorithmics, 15, article number 2.3. doi: 10.1145/1671970.1671976.
Holdsworth, J. (1999). The nature of breadth-first search. Townsville: James Cook University.
[17] Meyers, S. (2014). Effective modern C++. Newton: O’Reilly Media.
[18] SFML documentation. (n.d.). Retrieved from https://www.sfml-dev.org/documentation/2.5.1/.
[19] TGUI documentation. (n.d.). Retrieved from https://tgui.eu/documentation/.
[20] Shotts, W. (2019). The Linux command line: A complete introduction. (2nd ed.). San Francisco: No Starch Press.
[21] Kurant, M, Markopoulou, A., & Thiran, P. (2010). On the bias of BFS (Breadth First Search). In 2010 22nd International Teletraffic Congress (ITC 22) (pp. 1-8). Amsterdam: IEEE. doi: 10.1109/ITC.2010.5608727.
[22] Shynhalov, D. (2018). Investigation of the software for analysis and visualization of social graph structures. Control, Navigation and Communication Systems. Academic Journal, 5(51), 128-131. doi: 10.26906/SUNZ.2018.5.128.
English