English
Received 29.08.2022, Revised 24.11.2022, Accepted 20.12.2022
The task of visualization of large graphs as a special data structure and algorithms on them is considered by scientists and practitioners as a complex and non-trivial problem. The analysis of scientific works and existing software applications that implement similar functions of the subject domain testifies the relevance of expanding exploration in the lines of identifying the features of the development of applications for the visualization of large graphs and algorithms on them. The formulation of features and recommendations for the development of such software and presentation of the software module designed by the authors is the aim of the article. In the course of the work, the main features of the development of a program for the visualization of graphs with a large number of vertices were identified and formulated using methods of analysis and graph theory. Special recommendations on the essence of each of the stages of development of such applications were provided and those steps that are most important for developers in terms of the complexity of processing and visualization of large graphs, metrics of their layout in the application screen, etc. were identified. A software module developed by the authors, that provides a unified application programming interface for visualizing any algorithm on graphs, which allows to save time working on utility software and focus more on solving algorithmic problems is also presented. The presented module was developed by the authors taking into account the identified recommendations. A comparative analysis of the developed software module and analogues was carried out, which proved the extended functionality of the module for the visualization of graphs with a large number of vertices. The module is a practically valuable tool for data structures researchers and other experts working on graph algorithms, since it enables data visualization at debugging software and simplifies the analysis of large data structures
large graphs; problems of algorithms visualization; a module for visualization of algorithms on graphs; graph layout; unified Application Programming Interface
[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.
Українська