Поуровневые изображения графов: различия между версиями

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

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

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