Стандарт визуализации ГА

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

• Визуализация алгоритма должна состоять как минимум из одного изображения , содержащего граф алгоритма.

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

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

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

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

• В качестве инструмента визуализации используется любой редактор векторной графики ( формат .svg ). Финальные версии построенных схем визуализации конвертируются в bitmap изображение любого формата.

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

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

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

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

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

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

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

• Цвет любой дуги графа должен быть идентичен цвету вершины , из которой выходит эта дуга.

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

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

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

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

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

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

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

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

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

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

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

• Изображается аналогичная проекция на плоскость Oyz.

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

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