Стандарт визуализации ГА: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 10: Строка 10:
 
=== Структурная схема визуализации ГА ===
 
=== Структурная схема визуализации ГА ===
  
* В качестве инструмента визуализации используется любой редактор векторной графики ( формат .svg ). Финальные версии построенных схем визуализации конвертируются в bitmap изображение любого формата.
+
* В качестве инструмента визуализации используется любой редактор векторной графики. Финальные версии построенных схем визуализации публикуются в виде изображений любого формата, поддерживаемого движком MediaWiki.
  
* Вершины графа обозначаются кругами , размер которых должен совпадать для всех однотипных операций. Требования к относительному размеру вершин для разных операций жестко не декларируются , но рекомендуется обозначать крупнее операции внешних циклов / процедур.
+
* Вершины графа обозначаются кругами , размер которых должен совпадать для всех операций одного вида. Требований к относительному размеру вершин, соответствующих разным операциям, нет , но рекомендуется обозначать крупнее вершины, соответствующие макроблокам либо вызовам процедур, а все базовые операции обозначать вершинами одного размера.
  
 
* Каждая вершина графа должна быть проиндексирована некоторым кодовым текстом , обозначающим конкретную операцию. В случае наличия дополнительных изображений с разъяснением структуры операций , кодовое слово должно присутствовать на этих изображениях.  
 
* Каждая вершина графа должна быть проиндексирована некоторым кодовым текстом , обозначающим конкретную операцию. В случае наличия дополнительных изображений с разъяснением структуры операций , кодовое слово должно присутствовать на этих изображениях.  

Версия 13:21, 4 июня 2015

1 Необходимый минимум изображений и описаний

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

2 Особенности схематичного изображения ГА

2.1 Структурная схема визуализации ГА

  • В качестве инструмента визуализации используется любой редактор векторной графики. Финальные версии построенных схем визуализации публикуются в виде изображений любого формата, поддерживаемого движком MediaWiki.
  • Вершины графа обозначаются кругами , размер которых должен совпадать для всех операций одного вида. Требований к относительному размеру вершин, соответствующих разным операциям, нет , но рекомендуется обозначать крупнее вершины, соответствующие макроблокам либо вызовам процедур, а все базовые операции обозначать вершинами одного размера.
  • Каждая вершина графа должна быть проиндексирована некоторым кодовым текстом , обозначающим конкретную операцию. В случае наличия дополнительных изображений с разъяснением структуры операций , кодовое слово должно присутствовать на этих изображениях.
  • Дуги графа обозначаются линиями со стрелками на концах , соответствующих "адресату" данных. Возможно использование одной линии с ответвлениями для изображения рассылки данных от одной вершины нескольким. В этом случае такая "магистраль" данных должна иметь на изображении большую толщину , нежели одиночные пересылки. Аналогично , допускается та же техника для изображения пересылки результатов нескольких операций для одной операции.
  • Рекомендуется использовать следующую общую схему визуализации ГА : ввести трёхмерную декартову систему координат, а также набор плоскостей, параллельных одной из координатных. На каждой такой плоскости вводится одна и та же равномерная сетка, после чего все вершины ГА располагаются на этих плоскостях в узлах сетки.

2.2 Цветовая схема визуализации ГА

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

2.3 Построение ярусно-параллельной формы ГА

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

2.4 Визуализация входных и выходных данных алгоритма

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

3 Методы визуализации сложных алгоритмов

3.1 Многомерные алгоритмы

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

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

  • Многомерные структуры удобно воспринимать в качестве некой иерархии , где любая n – k -мерная гиперплоскость в исходном n-мерном пространстве представляется как единый макроблок , то есть n-мерная структура сводится к k-мерной структуре из макроблоков , где k <= 3. Далее каждый макроблок , представляющий собой n-k мерное пространство , аналогично разбивается на гиперплоскости. Процесс продолжается , пока n-k > 3. k на каждом шаге выбирается равным 1-3 в зависимости от структуры собственно алгоритма.
  • В визуализации алгоритма не используется изображение графа алгоритма в полном виде. Вместо этого исходный граф алгоритма представляется в виде типовых макроблоков в качестве вершин графа алгоритма. Каждый макроблок опять же изображается в виде графа алгоритма в соответствии с построенной на предыдущем этапе иерархической структурой , пока не будет достигнут уровень базовых вычислительных операций. Таким образом , получается набор изображений. Кроме того , на каждом этапе решается проблема большого числа дуг в графе алгоритма по методу , описанному пунктом выше.

3.2 Алгоритмы с множественными связями

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

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

3.3 Алгоритмы с нетривиальными входными данными