Visualization of algorithms on graphs with a large number of vertices: The features of applications design

Abstract

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

Alternate abstract:

Завдання візуалізації великих графів як спеціальної структури даних та алгоритмів на них розглядається вченими і практиками як складна і нетривіальна проблема. Аналіз наукових робіт та існуючих програмних додатків, що реалізують подібні функції предметної області, засвідчує актуальність розширення розвідок у напрямках виявлення особливостей розробки додатків для візуалізації великих графів та алгоритмів на них. Формулювання особливостей і рекомендацій щодо розробки такого програмного забезпечення та представлення спроєктованого авторами програмного модуля є метою статті. У ході роботи за допомогою методів аналізу та теорії графів виявлено та сформульовано основні особливості розробки програми для візуалізації графів з великою кількістю вершин. Надано окремі рекомендації щодо сутності кожного з етапів розробки таких додатків та виявлено ті кроки, які є найбільш важливими для розробників у термінах складності обробки та візуалізації великих графів, метрик їх розташування на екрані додатку тощо. Також представлено розроблений авторами модуль, який забезпечує уніфікований інтерфейс програмування додатків для візуалізації будь-якого алгоритму на графах, що дозволяє заощадити час на роботі над службовим програмним забезпеченням і більше зосередитися на розв’язанні алгоритмічних задач. Представлений модуль розроблено авторами з урахуванням виявлених особливостей та рекомендацій. Проведено порівняльний аналіз розробленого програмного модуля та аналогів, який засвідчив розширену функціональність модуля щодо візуалізації графів з великою кількістю вершин. Модуль є практично значущим інструментом для дослідників у галузі структур даних та інших експертів, які працюють над алгоритмами на графах, оскільки дає змогу візуалізувати дані при налагодженні програмного забезпечення та спрощує аналіз великих структур даних