Введение

Графом называется пара множеств, первое из которых есть непустое конечное множество элементов произвольной природы или множество вершин, а второе является подмножеством декартового произведения множества вершин и называется множеством дуг. Дуги могут быть ориентированными и неориентированными. Графы и графовые модели имеют широкое применение, так как могут быть использованы для наглядного представления сложной информации. Графовыми моделями являются расширения графов, например, графы, снабжённые атрибутами для элементов [1, 2]. Построение визуальных образов применяется для наглядного представления графов и графовых моделей.  Визуализация графов сопряжена с графическим изображением элементов графа, отражающим связи между вершинами и удовлетворяющим эстетическим критериям. Примером эстетических критериев могут служить минимальность числа пересечения дуг или отсутствие пересечений дуг и вершин. Существует множество методов визуализации графов, на основе которых построены системы визуализации графовых моделей. Среди последних встречаются как узкоспециализированные [3], так и системы общего назначения [4, 5, 6, 7, 8, 9]. Однако одна лишь визуализация графовых моделей даёт представление только структуре отображаемой информации. Знание того, как можно оперировать информацией, представляемой графами, повышает понимание самой информации. Алгоритмы на графах отражают операции над информацией, которая может быть представлена с помощью графов. Визуализация графовых алгоритмов даёт представление о методах работы с графовой информацией. Другими словами, визуализация преобразования графовой модели с помощью действия некоторого алгоритма даёт более полное представление об изображаемой информации и, кроме того, описывает алгоритм преобразования графа. Например, если графовая модель представлена с помощью сети Петри в начальном состоянии, то примером визуализации алгоритма может служить демонстрация работы сети. В настоящее время развивается направление визуализации алгоритмов, и в частности, алгоритмов на графах.

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

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

Два основных подхода в визуализации алгоритмов

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

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

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

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

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

Событийно-ориентированный подход

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

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

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

Например, для создания визуализации алгоритмов с помощью системы Polka [11], необходимо добавить в исходный код программы вызовы специальных функций, запускающих события визуализации. Также требуется создать сцены, реализующие визуализацию событий алгоритма, и построить соответствие между запускающими функциями и сценами.

Подход, опирающийся на отображение данных

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

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

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

Leonardo

Система Leonardo представляет собой интегрированную среду для разработки, выполнения и визуализации С-программ, реализующую подход управления данными [12]. Система Leonardo поддерживает механизм расчета графической визуализации, как реализуется путем добавления в код специальных директив.

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

void main(int[] v) {
	for (j=v.Length; j>0; j--)
		for (i=1; i<j; i++)
			if (v[i-1]>v[i]) {
				int temp=v[i]; v[i]=v[i-1]; v[i-1]=temp;
			}
}

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

void main(int[] v) {
	bsort.SendAlgoEvt("Input",v.Length,v);
	for (j=v.Length; j>0; j--)
		for (i=1; i<j; i++)
		if (v[i] > v[i+1]) {
			int temp = v[i]; v[i] = v[i-1]; v[i-1] = temp;
			bsort.SendAlgoEvt("Exchange",i,i-1);
	}
}

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

 

Рис. 1. Примеры визуализации алгоритма сортировки системами Polka и Leonardo, высота прямоугольников пропорциональна их значениям. На рисунке показана визуализация не отсортированного массива

 

С помощью Leonardo и Polka можно создать визуализации более понятные для восприятия. Например, в алгоритме сортировки методом пузырька, можно перемещать прямоугольники одновременно. В системе Polka можно записать инструкции так, чтобы движение графических примитивов начиналось одновременно. В системе Leonardo механизм таких действий выглядит проще за счёт использования директивы ScreenUpdateOn. Эта директива позволяет запускать все изменения одновременно. Если ScreenUpdateOn отключена, то система визуализации бездействует, и события визуализации не возникают. Чтобы визуализировать каждую перестановку в примере как атомарное действие, можно временно приостановить обновление экрана перед запуском перестановки и включить его снова после.

/** Not ScreenUpdateOn; **/
int temp=v[i]; v[i]=v[i-1]; v[i-1]=temp;
/** ScreenUpdateOn; **/

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

Например, чтобы визуализировать событие сравнения двух элементов в системе Polka, достаточно добавить один вызов функции, запускающей визуализацию. При этом событие визуализации "Compare" происходит незадолго до фактического сравнения значений.

void main(int[] v) {
	bsort.SendAlgoEvt("Input",n,v);
	for (j=v.Length; j>0; j--)
		for (i=1; i<j; i++) {
			bsort.SendAlgoEvt("Compare",i,i-1);
			if (v[i-1] > v[i]) {
				int temp = v[i]; v[i] = v[i-1]; v[i-1] = temp;
				bsort.SendAlgoEvt("Exchange",i,i-1);
			}
		}
}

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

 

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

void main(int[] v) {
	bsort.SendAlgoEvt("Input",n,v);
	for (j=v.Length; j>0; j--) {
		for (i=1; i<j; i++) {
			bsort.SendAlgoEvt("Compare",i,i-1);
			if (v[i-1] > v[i]) {
				int temp = v[i]; v[i] = v[i-1]; v[i-1] = temp;
				bsort.SendAlgoEvt("Exchange",i,i-1);
			}
		}
		bsort.SendAlgoEvt("InPlace",j-1);
	}
	bsort.SendAlgoEvt("InPlace",0);
}

Запуск события “InPlace” помечает графические объекты, соответствующие элементам массива, которые находятся на своей конечной позиции. Для системы Leonardo ситуация аналогична предыдущей. События “In Place” нужно симулировать с помощью вызова дополнительных функций.

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

Data Structure and Algorithm Visualization

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

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

Добавить новые алгоритмы нельзя, как уже было указано, алгоритмы добавляются в виде самостоятельных модулей. На Рис. 2 изображены два состояния графовой модели, обрабатываемой алгоритмом поиска в глубину.

 

Рис. 2. Алгоритм поиска в глубину

Белым цветом помечены вершины находящиеся, в начальном состоянии. Светло-Серые вершины с горизонтальной штриховкой находятся в очереди обработки. Серые вершины с вертикальной штриховкой являются необработанными соседями текущей обрабатываемой вершины. Серым цветом с наклонной штриховкой помечена текущая обрабатываемая вершина.  Серым цветом без штриховки помечены посещённые вершины.

JHAVE (Java-Hosted Algorithm Visualization Environment)

Система визуализации JHAVE [13] представляет собой самостоятельный виртуальный каталог визуализаций алгоритмов, изготовленный на языке java в виде загружаемого на локальный компьютер java-приложения. Пользователь сначала должен выбрать сервер, на котором хранятся визуализации алгоритмов. На момент написания статьи был доступен всего один сервер. Далее пользователю предоставляется возможность выбрать один алгоритм из фиксированного списка и запустить визуализацию. Каждая демонстрация загружается несколько минут. Набор демонстраций алгоритмов стандартный, и расширить его невозможно. Этот проект входит в состав каталога Data Structure and Algorithm Visualization, упомянутого выше.

Окно демонстрации разделено на две области: левая содержит изображение состояния графической модели, правая содержит описание алгоритма в текстовом виде, реализованное с использованием псевдокода и языка java. JHAVE позиционируется как образовательная система, предназначенная для обучения студентов. Целью данной системы является повышение понимания алгоритмов обработки графов.

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

Система визуализации не позволяет задать граф в качестве параметра.

 

Рис. 3. Визуализация алгоритма топологической сортировки

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

 

Рис. 4. Алгоритм Крускала для нахождения минимального остовного дерева неориентированного связного графа с взвешенными рёбрами

На данном рисунке демонстрируется четвёртый шаг алгоритма, когда для компоненты связности, состоящей из вершин A, E, D, C с дугами, имеющими вес 2, 2, 3, выбирается вершина и инцидентная ей дуга минимального веса, добавление которой не вызовет образования цикла. В данном случае показано, что есть дуга с весом 3, однако она не подходит, так как ей добавление создаст цикл из вершин A, E, D. Добавление дуги с весом 4, инцидентной вершинам A и H удовлетворяет условиям алгоритма. При этом на рисунке видно, что дополнительно отображаются текущие компоненты связности.

 

Рис. 5. Алгоритм Прима для нахождения минимального остовного дерева неориентированного связного графа с взвешенными рёбрами

На данном рисунке демонстрируется два шага, – второй и третий, алгоритма, который начал работу с вершины I. Серым цветом с наклонной штриховкой обозначаются вершины, которые принадлежат результирующему дереву. Серым цветом с горизонтальной штриховкой помечается вершина, которая была добавлена в результирующее дерево последней. Дуга, добавленная к дереву последней, выделяется жирной линией. Дуги, уже принадлежащие дереву, выделяются поперечной штриховкой. При переходе от состояния, изображённого в левой части рисунка, к состоянию, изображённому в правой части, была присоединена дуга с весом 5, так как она имеет минимальный вес среди всех дуг, инцидентных вершинам текущего остовного дерева. Серым цветом без штриховки цветом как раз помечены вершины из множества вершин, инцидентных вершинам из текущего остовного дерева

TRAKLA2

Система визуализации алгоритмов на графах TRAKLA2 [14] позиционируется как среда для обучения работе со структурами данных и алгоритмами. Процесс обучения представляет собой выполнение упражнений. Сама демонстрация представляет собой окно с псевдокодом и визуальным представлением графовой модели; в левой части окна располагается текстовое представление алгоритма в виде псевдокода, в правой части присутствует изображение состояния графовой модели. Система реализована на java-платформе. В окне системы выделено место для текстового представления графа-параметра в виде списка смежности. Далее на рисунках представлен пример алгоритма поиска в глубину в ориентированном связном графе. Вершины графа изображены кругами разного цвета, различные цвета также обозначают различные состояние вершин графа. Дуги графа представлены направленными отрезками. Вершины имеют текстовые подписи, соответствующие обозначениям вершин в списке смежности. В рассмотренном примере метки являются будками латинского алфавита. Упражнение представляет собой моделирование работы алгоритма на сгенерированном системой графе. Моделирование  заключается в последовательном изменении цветов вершин. Пользователь помечает определённую вершину некоторым цветом, соответствующим тому или иному состоянию вершины. Ход выполнения упражнения запоминается системой. После окончания выполнения упражнения система сравнивает предложенный пользователем вариант решения с эталонным решением. На основании этого сравнения пользователю выставляется оценка. В случае неверного решения пользователь может просмотреть историю выполнения и сравнить своё решение с правильным решением. Во время сравнения можно отследить, где предложенное решение отклоняется от правильного решения. К сожалению, строчки текстового представления алгоритма не подсвечиваются при демонстрации эталонного решения. Демонстрация имеет только пошаговый режим.

 

Рис. 6. Алгоритм поиска в глубину

 

В данном примере выполнение алгоритма поиска в глубину был начат с вершины A. В списке смежности вершины B дуги (B,A), (B,C), (B,E), (B,E) были заданы в указанном порядке. Поэтому сначала были посещены вершины C и E, а только после этого вершина D. Белым цветом помечаются вершины, которые ещё не участвовали в обходе. Чёрным цветом обозначаются вершины, которые участвовали в обходе и больше будут посещены. Серым цветом, соответственно, помечаются посещенные вершины, обработка которые ещё не закончена. На этом рисунке изображён результат следующих действий: вершина A помечается серым, вершина B помечается серым, вершина C помечается серым, вершина E помечается серым, вершина E помечается чёрным, так как все её соседи помечены как посещённые, вершина С помечается чёрным, так как все её соседи помечены как посещённые, вершина D помечается серым, вершина F помечается серым. Как видно из рисунка, данная последовательность действий совпадает с эталонным решением.

Рис. 7. Алгоритм поиска в глубину

Данный рисунок является продолжением рисунка 5. Здесь серым цветом помечается следующая белая вершина, инцидентная вершине F.

JAWAA

JAWAA [15] – это интерпретируемый язык для построения анимации с помощью специальной библиотеки. Библиотека разработана с использованием языка java. Авторы утверждают, что на этом языке можно быстро генерировать анимации таких структур данных, как очередь, стек, граф или дерево. Рассмотрим пример алгоритма поиска в глубину, сгенерированный с помощью упомянутой библиотеки. Как видно из рисунка 8, анимация содержит изображение графа, по которому ведётся поиск, и стека, который при этом используется. Поиск начинается в вершины 1. Зелёным цветом помечаются вершины, находящиеся в стеке или, другими словами, вершины, которые были посещены. Синим цветом помечены вершины, которые были посещены, и больше посещаться не будут. Серым цветом помечены вершины, которые ещё не посещались. Отличительной особенностью данной визуализации является наличие красного маркера, помечающего текущую вершину, либо текущий переход по дуге. Маркер движется непрерывно по дугам от вершины к вершине.

Рис. 8. Визуализация алгоритма поиска в глубину с помощью средств JAWAA

Также во время анимации дополнительно отображается содержимое стека. Вообще говоря, показывать его необязательно, так как зелёные вершины являются содержимым стека.

Animal

Система визуализации Animal позиционируется как инструмент, созданный для визуализации алгоритмов, причём не только алгоритмов на графах [16]. Инструмент разработан с использованием языка java. Каждая анимация может храниться в виде файла в специальном формате; такие файлы имеют расширение aml. Это означает, что созданные анимации можно сохранять для повторного использования. Для генерации aml-файлов используется специально созданный инструмент, так называемый генератор анимаций.

Рабочий генератор найти не удалось, но на рисунке 9 представлен пример анимации алгоритма, сгенерированного из сохранённого ранее aml-файла.

 

Рис. 9. Алгоритм последовательного поиска в массиве

 

На данном рисунке показаны три кадра из анимации, которая демонстрирует переборный алгоритм поиска в массиве. Массив a представлен однострочной таблицей. Как видно из текста алгоритма, используется цикл с индексом. Позиция стрелки, расположенной над ячейками таблицы, соответствует текущему значению индекса. Текущая выполняемая строка алгоритма подсвечивается синим цветом, а текущая выполняемая инструкция дополнительно подсвечивается красным цветом. Более сложных примеров обнаружить не удалось.

Evega (Educational Visualization Environment for Graph Algorithms)

Пользовательский интерфейс инструмента Evega [17] представляет собой окно графического редактора. Он может использоваться для построения графов и анимации алгоритмов. Граф может быть задан с помощью редактора либо загружен из файла. Во время анимации алгоритма также возможна анимация дополнительных структур данных, таких как стек или очередь. На рисунке 10 показано окно редактора графов. Утверждается, что при реализации алгоритма допускаются различные операции с элементами графа, такие как удаление или добавление вершин, изменение меток элементов. Инструмент Evega реализован как автономное java-приложение. Утверждается, что инструмент может быть использован для генерации пользовательских анимаций алгоритмов с использованием языка java и библиотек, поставляемых в комплекте инструмента Evega. Визуализация алгоритма представляет собой последовательное изменение цвета у вершин и текстовых меток у дуг.

 

Рис. 10. инструмент визуализации алгоритмов Evega. Окно графического редактора

 

В [18] для следующего примера не указано, с помощью какой системы была получена данная визуализация. На рисунке 11 показаны несколько кадров из визуализации алгоритма поиска в бинарном дереве.

 

Рис. 11. Визуализация алгоритма поиска в бинарных деревьях

 

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

Следующий пример визуализации алгоритмов представляет собой нетрадиционный подход, в том смысле, что визуализация динамического процесса представляет собой статическое изображение. В данном примере [19] показывается, как можно представить алгоритм сортировки массива в виде статического изображения. В данном примере нужно считать, что белый цвет обозначает минимальный элемент массива, а чёрный – максимальный элемент. Данную визуализацию удобно понимать следующим образом. Индексы элементов массива следует рассматривать как координаты элементов массива на числовой прямой. Тогда во время работы алгоритма эти координаты будут изменяться, а именно, в момент операции перестановки элементов. Если зафиксировать моменты времени, когда происходят перестановки элементов массива, то для каждого элемента массива можно построить соответствие между этим моментами времени и соответствующими этим моментам индексами. Так для каждого элемента массива можно получить дискретную зависимость индекса от времени. Если после этого соединить точки, соответствующие одному элементу массива, то для каждого элемента получится кусочно-линеный график зависимости “координаты” от времени. Если теперь совместить все графики на одном рисунке, обозначив графики разными цветами, то получившаяся картина будет выглядеть как рисунок 12.

 

Рис. 12. Визуализация пирамидальной сортировки массива с помощью статичного изображения

 

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

 

Рис. 13. Визуализация сортировки массива методом пузырька

 

Однако такие визуализации можно применять к алгоритмам сортировки. Для визуализации алгоритмов, оперирующих более сложными объектами, такие методы не подходят.

Данный пример найден на информационном портале колледжа Franklin & Marshall, посвящённом визуализации алгоритмов в компьютерной геометрии [20]. Визуализация алгоритмов на графах не является специализацией этого портала. Однако на нём есть полезные идеи, такие как, использование видео файлов для изображения работы алгоритмов, а сам процесс работы алгоритма описывается отображением последовательности состояний. Однако работа только демонстрационная, для заранее фиксированных решённых задач. На рисунке 14 изображена визуализация к задаче, которую можно сформулировать следующим образом. Для заданного множества точек на плоскости построить выпуклый многоугольник, содержащий все заданные точки, вершины которого также принадлежат заданному множеству точек.

 

Рис. 14. Визуализация алгоритма поиска выпуклой оболочки для множества заданных точек плоскости

 

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

Jeliot

Система Jeliot [21] предоставляет возможность визуализации процесса исполнения программ, написанных на языке java. Каждый шаг программы, например, вызов метода или переменной, отображается на экране в процессе выполнения, позволяя пошагово прослеживать ход исполнения программы. Программу можно ввести в окне программы или загрузить сохранённый пример. java программа может быть тут же визуализирована. Система Jeliot способна обработать большую часть синтаксических конструкций языка java. Особым достижением отмечается то, что приложение способно отображать объектно-ориентированные возможности объектов программы, как например, наследование классов.

 

Рис. 15. Визуализация инструкции вычисления разности двух операндов

 

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

 

Рис. 16. Визуализация инструкции вычисления разности двух операндов

Система визуализации доказательства корректности алгоритмов

Система разрабатывалась в Wellesley College. Далее будет представлен пример визуализации, построенный для алгоритма Прима.

Модель системы доказательства корректности алгоритмов состоит из нескольких частей:

1. Абстрактные графовые объекты (графы, подграфы, пути).
2. Элементарные графовые объекты, такие как вершины и дуги.
3. Описания доказываемых теорем и инвариантов, которые проверяются в процессе доказательства.
4. Динамическая помощь, описывающая объекты, появляющиеся на экране.
5. Описание диалога доказательства.

 

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

Разработчик, который использует данную систему, обязан предоставить следующие сущности:

1. Вступительную часть, в которой обозначается проблема, её значение и дополнительная информация.
2. Анимацию алгоритма, решающего проблему. Данный прототип системы был реализован с использованием HyperCard.
3. Диалог доказательства в терминах текстового файла в специальном формате.
4. Анимация базовых и вступительных шагов доказательства.
5. Файл справки, содержащий информацию об объектах.

 

Рис. 17. Первый шаг анимации алгоритма Прима в системе доказательства корректности алгоритмов на графах. На первом шаге приводится пример графа, на котором будет проводиться доказательство, и текстовое представление алгоритма

 

Рис. 18. Второй шаг анимации алгоритма в системе доказательства корректности. На втором шаге формулируется теорема в терминах инвариантов, сохранение которых будет показываться в процессе работы алгоритма

 

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

 

Рис. 20. Четвёртый шаг анимации алгоритма в системе доказательства корректности. Формулировка индукционного перехода метода математической индукции в терминах заданной задачи. В данном случае используется метод доказательства от противного

 

Рис. 21. Пятый шаг анимации алгоритма в системе доказательства корректности. Здесь приведены рассуждения индукционного перехода. Для подграфа меньшего размера построено остовное дерево, и есть два случая того, как оставшиеся вершины могут быть связаны с вершинами подграфа

 

Рис. 22. Шестой шаг анимации алгоритма в системе доказательства корректности. Доказательство противоречивости первого варианта связи оставшихся вершин с вершинами подграфа

 

Рис. 23. Седьмой шаг анимации алгоритма в системе доказательства корректности. Доказательство противоречивости второго варианта связи оставшихся вершин с вершинами подграфа

 

Рис. 24. Доказательство противоречивости второго варианта связи оставшихся вершин с вершинами подграфа (продолжение)

 

Рис. 25. Заключительный шаг анимации алгоритма в системе доказательства корректности. Так как предположение, сделанное на шаге индукционного перехода, привело к противоречию, то оно ложно

 

На рисунках 17–25 демонстрируется пример работы системы доказательства корректности алгоритмов на графах. Из рисунков видно, что элементы графа изображаются простыми кругами и прямыми отрезками, а выделение элементов производится с помощью различных цветов и толщины линий. Как нетрудно заметить, вся реализация процесса визуализации алгоритма лежит полностью на разработчике. Для реализации новой демонстрации нужно процесс разработки начинать заново.

GDR: инструмент визуализации алгоритмов на графах

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

 

Поиск в глубину для случая ориентированных графов

Необработанные вершины изображаются белыми кругами, вершины в стеке – серыми, вершины, которые посещены и полностью обработаны – чёрными. Метки вершин показывают два числа – моменты времени начала обработки вершины и конца обработки вершины (соответственно, для прямого порядка обхода и обратного). Дуги дерева подсвечены и дуги помечены буквой C, если они пересекаются, буквой F, если направлены вперёд, либо буквой B, если направлены назад.

Пользователь может выбирать стартовую вершину для поиска и также может выбирать различные последовательности дуг в списках смежности, чтобы получить различные поисковые деревья для заданного графа. Внешний цикл алгоритма побуждает пользователя выбирать стартовую вершину каждый раз в начале каждой итерации как показано на Рис. 26. Вершины 4 и 5 недоступны (не были достигнуты) для поиска, если стартовая вершина есть 0. Порядок необработанных дуг в списке смежности может быть изменён в любое время, когда включен режим паузы для анимации. Дуги могут быть вставлены в нужный список или удалены из него.

 

Рис. 26. GDR. Анимация поиска в глубину в ориентированном графе

 

Визуализация алгоритма минимизация числа состояний в конечном автомате

Это пример более сложной анимации (сложной только потому, что алгоритм нетривиален). Авторы системы утверждают, что алгоритм можно реализовывать за 12 часов с использованием GDR в качестве средства отладки. Анимации DFA минимизации сначала требует от пользователя или нарисовать DFA, или загрузить DFA из файла. Метки дуг обозначают переходы. В следующей фазе от пользователя требуется установить конечные состояния с помощью операции подсвечивания (или снять выделение с подсвеченных состояний). Алгоритм работает, успешно разделяя множество состояний на классы эквивалентности (основываясь на теореме Майхила–Нероуда). На протяжении всей анимации метки вершин показывают классы эквивалентности, которым они принадлежат. В конце алгоритм выбирает состояние-представитель из каждого класса и перерисовывает анимацию только с такими состояниями. На рис. 27 класс 0 разделён на два класса. Помеченные звёздочками состояния станут частью нового класса 2. Конечный результат показан на Рис. 28.

 

Рис. 27.  DFA-минимизация в процессе выполнения алгоритма

 

Рис. 28. DFA-минимизация завершена

 

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

Higres

Система Higres [4, 5]  создавалась  в 1996—1999 гг. Данная система предназначена для создания и визуализации иерархических графовых моделей, представляющих собой иерархические графы с заданной семантикой.

Иерархический граф состоит из вершин, дуг и фрагментов. Вершины и дуги представляют собой обычный граф, который может быть ориентированным или неориентированным. Также на графе задано дерево фрагментов, где фрагменты есть некоторые подграфы, а дерево задаёт отношение вложенности на множестве фрагментов. Фрагменты могут быть либо вложенными, либо не иметь общих вершин. Набор всех вершин определяет главный фрагмент иерархического графа. Строгое определение иерархических графов и других понятий, связанных с ними, можно найти в [1, 23]. Пример иерархического графа, созданного в системе Higres, приведен на Рис. 29.

 

Рис. 29. Иерархический граф в системе Higres

 

Возможности визуализации включают:

-  различные формы и стили вершин;

-  дуги в виде ломаных линий и гладких кривых;

-  различные стили линий и стрелок дуг;

-  выбор цвета для всех элементов графа;

-  возможность задавать произвольный масштаб изображения;

-  возможность перемещать текст дуги вдоль ее линии;

-  позиционирование внешнего текста вершины в любом месте около ее границы;

-  выбор шрифта для всех элементов графа;

-  два формата графического вывода;

-  широкий набор опций визуализации.

Система Higres содержит три встроенных алгоритма  размещения  графов  на  плоскости.  Первый — известный метод сил, второй — улучшенная версия  первого, третий — алгоритм размещения деревьев с помощью уровней. Все  алгоритмы реализованы во внешних модулях, прилагаемых к системе.  Одним из достоинств системы является удобный интуитивный пользовательский интерфейс. Главное окно системы содержит меню, несколько  панелей инструментов и панель состояния. Внутри главного окна можно открывать  произвольное  количество  окон  фрагментов,  используя  интерфейс MDI.

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

 

Рис. 30. Выполнение алгоритма, реализованного в виде внешнего модуля к системе Higres

 

Для запуска алгоритма в системе пользователь должен выбрать соответствующий внешний модуль. Результат работы модуля можно наблюдать непосредственно во время его работы. Кроме того, в системе предусмотрена возможность прокрутки в обратном направлении и пошагового выполнения. В отдельном окне показывается протокол исполнения алгоритма и его текстовый вывод. На рис. 30 показан пример исполнения внешнего модуля. В данном случае граф представляет собой схему программы быстрого возведения в степень. К системе прилагается специальная библиотека на языке C++, предназначенная для написания внешних модулей и включающая функции для модификации графа, а также для взаимодействия с системой. Для написания внешних модулей с помощью данной библиотеки необязательно знать детали внутреннего представления графа, что облегчает работу с ней.

VisuAlgo

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

 

Рис. 31. Анимация алгоритма DFS с помощью инструмента VisuAlgo.

 

В отображении тексте выделяется активная строка алгоритма, которая приводит к изображаемым эффектам над элементами графа. В данном случае выделение производится с помощью чёрного цвета для фона текущей строки текста. При визуализации имеется возможность прокрутить визуализацию в пошаговом режиме, а также в обратном направлении. Кроме того, есть возможность увеличить или уменьшить скорость воспроизведения. Проект разрабатывает при поддержке гранта для поддержки и развития методов обучения. При визуализации вершин и дуг не учитываются точки входа дуг в вершины в том смысле, что нет видимых отдельных объектов изображения для рисования портов вершин. При визуализации явно используются эффекты, протяжённые во времени. Так как при перемотке назад происходит визуализация последнего эффекта до конца. Для визуализации нельзя полностью вручную построить входной граф на момент написания статьи. При визуализации алгоритма обхода в глубину не используется отображение структур данных, стека в данном случае. Как видно из Рис. 31 на изображающем текст алгоритма фрагменте картинки используется рекурсивная версия алгоритма. Однако факт использования рекурсии на изображении не отражается. Если рассмотреть другой пример визуализации с помощью VisuAlgo на Рис. 32, использующий очередь и не использующий рекурсию, то также видно, что дополнительные структуры данных отображаются при визуализации алгоритма. В данном примере со содержимое очереди изображается с помощью цветового выделения вершин, находящихся в очереди. Синим цветом выделены вершины, находящиеся в очереди в данный момент. Отображению смены инструкций алгоритма не хватает плавности. Удаляемые вершины помечаются серым цветом.

 

Рис. 32. Анимация алгоритма топологической сортировки с помощью инструмента VisuAlgo.

Заключение

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

И если в существующих системах визуализации алгоритмов часто поддерживается возможность редактирования графов-параметров (хотя чаще используются автоматически сгенерированные графы), то ввод алгоритмов-параметров обычно не реализован никаким образом. Большинство систем визуализации представляют собой каталоги, где для каждого фиксированного алгоритма визуализации строятся для различных графов с помощью некоторых библиотек визуализации. При этом, если потребуется ввести новый алгоритм в такую систему, то будет необходимо разработать всю визуализацию заново.

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

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

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

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

1. Касьянов, В. Н., Евстигнеев, В. А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ-Петербург, 2003. – 1104 c. – 3000 экз. – ISBN 5-94157-184-4.
2. Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей // Научная визуализация. - 2014.- Том. 6, N 1. - С. 31 - 50.
3. Система визуализации графов Walrus. – http://www.caida.org/tools/visualization/walrus/
4. 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.
5. Система визуализации иерархических Higres. – http://pcosrv.iis.nsk.su/higres/
6. Система визуализации графов Graphviz. – http://www.graphviz.org/
7. Система визуализации графов aiSee. –  http://www.aisee.com/
8. Касьянов В.Н., Золотухин Т.А. Visual Graph - система для визуализации сложно структурированной информации большого объема на основе графовых моделей // Научная визуализация. - 2015. - Том. 7, N 4.- С. 44 – 59.
9. Kasyanov V.N., Kasyanova E.V. Graph- and cloud-based tools for computer science education // Lecture Notes of Computer Science. - Springer, 2015. - Vol. 9395. - pp. 41-54.  
10. 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.
11. Система анимации алгоритмов Polka. –  http://cc.gatech.edu/gvu/softviz/parviz/.
12. Система анимации алгоритмов Leonardo. – http://www.dis.uniroma1.it/~demetres/Leonardo/.
13. Система визуализации алгоритмов JHAVE. – http://jhave.org/
14. Система анимации алгоритмов TRAKLA2. – http://www.cs.hut.fi/Research/TRAKLA2/
15. Система анимации алгоритмов JAWAA. – http://www.cs.duke.edu/csed/jawaa2/
16. Система анимации алгоритмов Animal. – http://www.algoanim.info/Animal2/
17. Система анимации алгоритмов EVEGA. – http://www14.in.tum.de/EVEGA/
18. Пример визуализации алгоритмов. – http://www.cs.nyu.edu/algvis/java/Examples.html
19. Пример визуализации алгоритмов. – http://corte.si/posts/code/visualisingsorting/.
20. Пример визуализации алгоритмов. – http://www.fandm.edu/computer-science/professors-emeriti/anderson/jay-martin-anderson/research-and-development/portal-algorithm-visualization-in-computational-geometry.
21. Система анимации алгоритмов Jeliot. – http://cs.joensuu.fi/~jeliot/.
22. Stallmann M., Cleaveland R., Hebbar P.  GDR: A Visualization Tool for Graph Algorithms // In Proc. Computational Support for Discrete Mathematics, American Mathematical Society, – 1994. – P. 17-28.
23. Kasyanov V.N. Kasyanova E. V. Information visualization based on graph models // Enterprise Information Systems.- 2013.- Vol. 7, N 2.- pp. 187-197.
24. Halim S. VisuAlgo-Visualising Data Structures and Algorithms Through Animation // OLYMPIADS IN INFORMATICS. - 2015. - С. 243.
25. Scalable Vector Graphics. https://www.w3.org/TR/SVG11.
            

---

A survey of visualization techniques of algorithms on graphs

Author: D. S. Gordeev

A. P. Ershov Institute of Informatics Systems,

Novosibirsk, Russia

ORCID: 0000-0003-1623-9553, gds@iis.nsk.su

 

Abstract

The paper describes methods of visual representation of graph algorithm behavior. Several points of interests are an ability to configure input graph by user, an ability to configure input algorithm by user and an ability to configure visual effects for algorithm visualization visualization.

Existing visualization systems often use automatically generated graphs as input parameters and at the same time input algorithms are fixed by design of a system. Often visualization system are presented as catalogs where some fixed algorithms can be visualized for different input graphs. Usually if there is need to append a system with new algorithms then it is necessary to develop whole visualization from the beginning. Also continuous animation looks interesting addition to visualization technique in order to create smooth image transitions on output devices and to attract attention of user.

Also this paper considers widely used algorithms visualization techniques such as event-driven approach and data-driven approach. Also interesting characteristic is configuration of drawing of graphic primitives for graph visualization process in order to prepare user to following images.

 

Keywords: tree-like graphs, data visualization, pipeline systems, water hammer, Godunov type scheme.

This paper was carried out with the partial financial support of the Russian Foundation for Basic Research (grant of RFBR No. 18-07-00024).

References

1. Kasyanov V.N., Evstigneev V. A. Grafy v programmirovanii: obrabotka, vizualizatsiya i primenenie. [Graphs in programming: processing, Visualization and application.] – 2003. – 1104 pp.  – ISBN 5-94157-184-4. [In Russian]
2. Kasyanov V.N., Kasyanova E.V. Vizualizatsiya informatsii na osnove grafovyh modeley [Information visualization on the base of graph models]  // Scientific Visualization. - 2014.- Vol. 6, N 1. - pp. 31 - 50. [In Russian]
3. Walrus: Graph Visualization Tool. – URL: http://www.caida.org/tools/visualization/walrus
4. 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.
5. Higres: graph drawing system for hierarchically clustered graphs. – URL: http://pcosrv.iis.nsk.su/higres
6. Graphviz: graph visualization software. – URL: http://www.graphviz.org
7. aiSee: graph visualization software. –  URL: http://www.aisee.com
8. Kasyanov V.N., Zolotuhin T.A. Visual Graph - a system for visualization of big size complex structural information on the base of graph models // Scientific visualization. - 2015. - Vol. 7, N 4.- pp. 44 — 59. [In Russian]
9. Kasyanov V.N., Kasyanova E.V. Graph- and cloud-based tools for computer science education // Lecture Notes of Computer Science. - Springer, 2015. - Vol. 9395. - pp. 41-54.
10. 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.
11. Polka: Algorithm animation system. –  URL: http://cc.gatech.edu/gvu/softviz/parviz
12. Leonardo: Algorithm animation system. –  URL: http://www.dis.uniroma1.it/~demetres/Leonardo
13. JHAVE: Algorithm visualization system. – URL: http://jhave.org
14. TRAKLA2: Algorithm animation system. – URL: http://www.cs.hut.fi/Research/TRAKLA2
15. JAWAA: Algorithm animation system. – URL: http://www.cs.duke.edu/csed/jawaa2
16. Animal Algorithm animation system. – URL: http://www.algoanim.info/Animal2
17. EVEGA Algorithm animation system. – URL: http://www14.in.tum.de/EVEGA
18. Algorithm visualization example. – URL: http://www.cs.nyu.edu/algvis/java/Examples.html
19. Static sorting algorithm visualization example. – URL: https://corte.si/posts/code/visualisingsorting/index.html
20. Computational geometry algorithm visualization example. – URL: http://www.profdrjmanderson.com/quickhull-algorithm.html
21. Jeliot: algorithm animation system – URL: http://cs.joensuu.fi/~jeliot
22. Stallmann M., Cleaveland R., Hebbar P.  GDR: A Visualization Tool for Graph Algorithms // In Proc. Computational Support for Discrete Mathematics, American Mathematical Society, – 1994. – P. 17-28.
23. Kasyanov V.N. Kasyanova E.V. Information visualization based on graph models // Enterprise Information Systems.- 2013.- Vol. 7, N 2.- pp. 187-197.
24. Halim S. VisuAlgo-Visualising Data Structures and Algorithms Through Animation //OLYMPIADS IN INFORMATICS. - 2015. - С. 243.
25. Scalable Vector Graphics. URL: https://www.w3.org/TR/SVG11