999
правок
Поуровневые изображения графов: различия между версиями
Перейти к навигации
Перейти к поиску
Поуровневые изображения графов (посмотреть исходный код)
Версия от 20:26, 21 октября 2024
, 21 октябрьнет описания правки
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
Широко используемыми алгоритмами для наглядного изображения графов являются алгоритмы, относящиеся к классу, предложенных Сугиямой. Они производят ''поуровневые'' (или ''иерархические'') ''изображения'' (layered drawings) [[Ациклический граф|ациклических орграфов]] ([[Дэг|дэгов]]), пытаясь также минимизировать количество пересечений или размер области размещения. Выбор этого подкласса для рисования можно объяснить двумя причинами. Во-первых, преимущественное большинство реальных графов, встречающихся в программировании, являются ациклическими, а, во-вторых, любой ориентированный (и тем более неориентированный) граф может быть преобразован к ациклическому орграфу путем смены или задания ориентации у части его ребер. | |||
Методы, основанные на поуровневом размещении (иерархический подход), хотя и не являются лидерами по всем эстетическим критериям, однако значительно опережают конкурентов на больших графах, возникших в реальных приложениях. | Методы, основанные на поуровневом размещении (иерархический подход), хотя и не являются лидерами по всем эстетическим критериям, однако значительно опережают конкурентов на больших графах, возникших в реальных приложениях. | ||
Данный подход является крайне интуитивным и позволяет для произвольного ациклического орграфа построить монотонное поуровневое представление с ребрами в виде ломаных или сплайнов в процессе последовательного решения следующих трех задач: [[распределение вершин по уровням]] так, чтобы все дуги следовали одному направлению; [[выбор порядка вершин на уровне]] с целью минимизации пересечений ребер; определение координат вершин на уровне с целью минимизации общей длины ребер и количества изломов. Таким образом, данный подход позволяет разбить задачу нахождения расположения ациклического графа на три достаточно независимых шага, реализация которых опирается на свои методы и использует различные эстетические критерии. В свою очередь каждый из этих трех шагов распадается на ряд малопересекающихся задач, с которыми связаны свои наборы решений. Поэтому любая конкретная реализация поуровневого подхода — это всегда конструктор, т. е. набор методов, решающих задачи разных этапов. Собирая такой конструктор, исследователь должен выбрать сбалансированный набор методов. Такой набор должен быть непротиворечивым по целям и эквивалентным в терминах временной сложности. Если в набор входит алгоритм, имеющий квадратичную сложность, то нет смысла «экономить» на решении задач других этапов, применяя к ним линейные, но «плохие» эвристики. | Данный подход к построению [[Сугиямо-подобные изображения графов|Сугиямо-подобных изображений]] (Sugiyama-style drawings) является крайне интуитивным и позволяет для произвольного ациклического орграфа построить монотонное поуровневое представление с ребрами в виде ломаных или сплайнов в процессе последовательного решения следующих трех задач: [[распределение вершин по уровням]] так, чтобы все дуги следовали одному направлению; [[выбор порядка вершин на уровне]] с целью минимизации пересечений ребер; определение координат вершин на уровне с целью минимизации общей длины ребер и количества изломов. Таким образом, данный подход позволяет разбить задачу нахождения расположения ациклического графа на три достаточно независимых шага, реализация которых опирается на свои методы и использует различные эстетические критерии. В свою очередь каждый из этих трех шагов распадается на ряд малопересекающихся задач, с которыми связаны свои наборы решений. Поэтому любая конкретная реализация поуровневого подхода — это всегда конструктор, т. е. набор методов, решающих задачи разных этапов. Собирая такой конструктор, исследователь должен выбрать сбалансированный набор методов. Такой набор должен быть непротиворечивым по целям и эквивалентным в терминах временной сложности. Если в набор входит алгоритм, имеющий квадратичную сложность, то нет смысла «экономить» на решении задач других этапов, применяя к ним линейные, но «плохие» эвристики. | ||
Как уже было сказано, данная методология может быть применена не только к [[Ациклический граф|ациклическим орграфам]] ([[Дэг|дэгам]]), но также к графам, близким к ациклическим, и даже просто к неориентированным графам. В этих случаях, когда структура графа не соответствует нашему изначальному предположению об ацикличности, требуется произвести некоторые предварительные преобразования над графом. Суть и цель этих преобразований заключается в обратимом преобразовании структуры, чтобы после размещения ациклического графа возможно было безболезненно для качества получаемого изображения восстановить структуру изначального графа и тем самым построить его изображение. Например, для построения изображения неориентированного графа можно сначала превратить его в дэг, задав ориентацию его рёбер. | Как уже было сказано, данная методология может быть применена не только к [[Ациклический граф|ациклическим орграфам]] ([[Дэг|дэгам]]), но также к графам, близким к ациклическим, и даже просто к неориентированным графам. В этих случаях, когда структура графа не соответствует нашему изначальному предположению об ацикличности, требуется произвести некоторые предварительные преобразования над графом. Суть и цель этих преобразований заключается в обратимом преобразовании структуры, чтобы после размещения ациклического графа возможно было безболезненно для качества получаемого изображения восстановить структуру изначального графа и тем самым построить его изображение. Например, для построения изображения неориентированного графа можно сначала превратить его в дэг, задав ориентацию его рёбер. | ||