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

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

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