Архитектура системы визуализации алгоритмов на графах

Гордеев Дмитрий Станиславович

Институт систем информатики им. Ершова А.П.,

Аспирант, e-mail: [email protected]

Аннотация

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

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

 

Graph algorithm visualization system architecture

Gordeev Dmitry Stanislavovich

P. Ershov Institute of Informatics Systems,

Post-graduate, e-mail: [email protected]

Abstract

This article describes the architecture of graph algorithm visualization system. The main feature of the architecture is that the algorithm also is considered as input parameter during visualization build process just like graph.

Key words: algorithm visualization, graph algorithms.

Введение

Рост требований для интерактивных визуализаций графов, которые могут быть эффективно использованы при обучении студентов и исследованиях, а также отсутствие универсальных систем визуализации алгоритмов побуждают к созданию новой архитектуры для универсальной системы визуализации. Определение новой архитектуры требует интенсивного анализа существующих систем визуализации и описания ключевых требований, которым должна удовлетворять архитектура. Применение этой архитектуры упрощает процесс создания визуализаций произвольных алгоритмов, оперирующих графовыми объектами. Такие визуализации можно эффективно использовать в образовательных целях, так как есть возможность внести изменения в граф и в алгоритм и незамедлительно увидеть эффекты, к которым приводят изменения.

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

Анализ требований

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

У некоторых существующих систем есть другое серьёзное ограничение. Если система поддерживает только специфичные наборы алгоритмов или структур данных, и таким образом не может быть использована для обучения широкому классу задач связанных с алгоритмами и структурами данных. Часто это серьёзное ограничение закладывается во время построения системы, и не может быть устранено без серьёзной переработки системы. Таким образом, можно сформулировать ещё одно существенное требование к эффективной системе обучения. Система визуализации должна быть применима к широкому кругу задач, не только из области информатики, а также, например, биоинформатики, химии. Системы, построенные быстро и для специальной задачи используют очень маленькую область применения или не реализуют динамическую визуализацию. Другие системы, при реализации которых были осуществлены попытки расширить заложенные рамки, требуют много дополнительных усилий, чтобы их можно было эффективно использовать.

Чрезвычайно важным требованием, предъявляемым к системам визуализации, является быстрое добавление новых симуляций. Система также должна обладать возможностью быстрого разворачивания. Исследование показывает, что существующие системы визуализации не удовлетворяют всем трём требованиям одновременно. Если система представляет собой модульную систему, состоящую из независимых модулей, то такая архитектура позволяет легче обновлять и поддерживать систему. Также модульная архитектура приводит к уменьшению усилий, необходимых для разработки и добавления новых анимаций. Также архитектура системы должна позволять студентам или исследователям запрограммировать собственный алгоритм, чтобы получить, максимум эффективности от анимации алгоритма.

Архитектура

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

Так как пользователь должен иметь возможность ввести в качестве параметра граф, то система должна содержать модель редактирования графов. При его реализации можно использовать существующие графические редакторы, либо реализовать новый редактор. В последнем случае дополнительные усилия обеспечат более простую интеграцию с другими модулями системы. Этот модуль также должен обеспечивать функциональность преобразования абстрактного графа в текстовое представление. Конкретный формат зависит от модели представления графа и может быть выбран в самом обобщённом виде. Текст алгоритма можно использовать в качестве параметра без дополнительного преобразования, так как наиболее естественный способ ввода алгоритма с точки зрения пользовательского интерфейса, это ввод инструкций алгоритма.

Также следует выделить модуль исполнения алгоритма. При его реализации потребуется построить интерпретатор инструкций алгоритма, переданного в текстовом виде. Реализация интерпретатора зависит от синтаксиса алгоритмических инструкций, однако это довольно слабая зависимость между модулями ввода параметров и исполнения алгоритма, так как ничто не мешает при необходимости реализовать его с использованием другой технологии. Во время работы интерпретатор инструкций генерирует журнал операций. Каждая запись журнала содержит информацию о преобразовании внутреннего состояния графовой модели, соответствующую исполненной инструкции алгоритма. Чтобы передать эту информацию следующему модулю, её также нужно представить в текстовом виде.

Самым важным, с точки зрения пользователя, модулем является визуализатор. Этот модуль получает в качестве параметров, текстовые представления графа, закодированного алгоритма, а также закодированное в текстовом виде представление журнала операций обработки графа-параметра заданным алгоритмом. Этот модуль связан с устройством вывода и пользовательского взаимодействия. Визуализатор перекодирует текстовое представление графа в графические примитивы, которые будут использоваться для построения визуализации. Текстовое представление будет использоваться без изменения. Суть его использования в том, что каждая инструкция алгоритма отражает некоторое преобразование внутреннего состояния графовой модели. И при изменении состояние следует визуально выделять инструкцию алгоритма, которая вызвала это преобразование. Каждая запись из журнала операций будет использоваться для изменения визуальных свойств графических примитивов. Также этот модуль должен содержать настройки, которые задают соответствие между данными из записи журнала операций и характером изменения визуального состояния графовой модели.

Заключение

Принципы описанной архитектуры были применены при реализации прототипа системы визуализации алгоритмов. На момент написания статьи были реализованы модули исполнения алгоритма и модуль визуализации с базовыми настройками. Реализованные настройки соответствуют изменению цвета и формы вершин графа. Результатом работы модуля визуализации является набор файлов изображений в любом заданном графическом формате. В данный момент рассматривается возможность интеграции с существующими графическими редакторами, чтобы обеспечить возможность ввод графа-параметра. Задача ввода алгоритма-параметра является сравнительно простой из-за текстового входного представления. Также рассматриваются существующие методы генерации управляемых пользователем визуализаций, построенных с помощью последовательности изображений. Следует отметить, что выбор последовательности файлов изображений в качестве выходных значений модуля визуализации продиктован исключительно тем, что текущая версия является прототипом. После решения указанных вопросов, направлением дальнейших исследований является задача создания настраиваемого соответствия между записями журнала операций и визуальными эффектами, соответствующими инструкциям алгоритма.

References

1. Lisitsyn I.A., Kasyanov V.N. Higres – Visualization system for clustered graphs and graph algorithms // Proc. of Graph Drawing 99. – Lect. Notes in Comput. Sci. – 1999. – Vol. 1731. – P. 82–89.

2. Demetrescu C., Finocchi I., Stasko J. T., Specifying Algorithm Visualizations: Interesting Events or State Mapping? // In Proc. of Dagstuhl Seminar on Software Visualization – Lect. Notes in Comput. Sci. – 2001. – P. 16–30.

3. Stallmann M., Cleaveland R., Hebbar P. GDR: A Visualization Tool for GraphAlgorithms // In Proc. Computational Support for Discrete Mathematics, American Mathematical Society, – 1994. – P. 17-28.