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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример отображения графа алгоритма с использованием трёхмерной декартовой системы координат.

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

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

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

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

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

Пример изображения графа алгоритма выполнения некоторой операции из графа исходного алгоритма.

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

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

Пример части графа некоторого алгоритма, изображаемого на нескольких плоскостях.

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

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

• 

  Первый ярус

• 

  Второй ярус

• 

  Третий ярус

Пример отображения графа алгоритма в ярусно-параллельной форме с помощью набора изображений

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

Пример отображения графа алгоритма в ярусно-параллельной форме с использованием трёхмерной декартовой системы координат.

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

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

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

• 

  Отображены входные данные

• 

  Отображены выходные данные

Пример отображения надграфа алгоритма с входными и выходными данным

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

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

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

Пример отображения условных переходов в графе алгоритма.

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

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

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

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

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

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

• 

  Упрощенное отображение алгоритма - показаны входные-выходные данные и макроблоки

• 

  Отображение структуры каждого макроблока.

Пример отображения многомерного алгоритма с использованием макроблоков

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

Под множественными связями понимается большая величина E/V, где E - число дуг в графе алгоритма, а V - число вершин графа алгоритма. В рамках этого руководства граф алгоритма считается имеющим множественные связи, если E = O(V^2) и более. Основная возникающая при этом визуальная проблема — дуги перекрывают друг друга и определение того, каким вершинам инцидентна конкретная дуга, становится затруднительным. Для решения этой проблемы используется следующая методика, основанная на предположении о использовании для визуализации предложенной схемы с трёхмерной декартовой системой координат.

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

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

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

• Каждая вершина графа, проектируемого на плоскости oXY и oXZ, помечается индексом вида A(ijk), где ijk - координаты узла сетки в трёхмерной декартовой системе координат, в котором находится данная вершина. Эта индексация присутствует и на изображениях проекций графа, что облегчает понимание того, какие именно вершины графа алгоритма изображены на соответствующей проекции.

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

• 

  Пример проекции графа алгоритма на плоскость oXZ

• 

  Пример проекции графа алгоритма на плоскость oYZ

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

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

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