Поуровневые изображения графов

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

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

Данный подход к построению Сугиямо-подобных изображений (Sugiyama-style drawings) является крайне интуитивным и позволяет для произвольного ациклического орграфа построить монотонное поуровневое представление с ребрами в виде ломаных или сплайнов в процессе последовательного решения следующих трех задач: распределение вершин по уровням так, чтобы все дуги следовали одному направлению; выбор порядка вершин на уровне с целью минимизации пересечений ребер; определение координат вершин на уровне с целью минимизации общей длины ребер и количества изломов. Таким образом, данный подход позволяет разбить задачу нахождения расположения ациклического графа на три достаточно независимых шага, реализация которых опирается на свои методы и использует различные эстетические критерии. В свою очередь каждый из этих трех шагов распадается на ряд малопересекающихся задач, с которыми связаны свои наборы решений. Поэтому любая конкретная реализация поуровневого подхода — это всегда конструктор, т. е. набор методов, решающих задачи разных этапов. Собирая такой конструктор, исследователь должен выбрать сбалансированный набор методов. Такой набор должен быть непротиворечивым по целям и эквивалентным в терминах временной сложности. Если в набор входит алгоритм, имеющий квадратичную сложность, то нет смысла «экономить» на решении задач других этапов, применяя к ним линейные, но «плохие» эвристики.

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

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

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

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

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

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

Литература

• Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ-Петербург, 2003. – 1104 c.
• Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей // Научная визуализация. – 2014. – Том. 6, N 1. – С. 31 – 50.
• Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей. – Новосибирск: НГУ, 2014. – 149 с.