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

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