Первая страница / Теория / Графы. Раскраски и укладки /

Построение изображений ациклических ориентированных графов

Голосование: 19, 6

В данной статье приведен обзор некоторых наиболее популярных методик для изображения ациклических ориентированных графов (в дальнейшем будем называть их также дэгами, от англ. directed acyclic graph, DAG).

Разделы, посвященные методам, основанным на сортировке, представляют собой реферативное изложение соответствующих разделов [1].

При создании иллюстраций использовался графовый редактор yEd Graph Editor.

Для иллюстрации работы алгоритмов, основанных на поуровневом подходе к рисованию ациклических ориентированных графов, к статье прилагается апплет. Левой кнопкой мыши добавьте вершины, протяните между ними ребра, для удаления элементов используйте клавишу Delete на клавиатуре. Нажмите правую кнопку мыши, чтобы получить готовое изображение. Введенный граф должен быть связным ациклическим и содержать не более 30 вершин. Для работы с апплетом необходимо наличие Java 5.

Можно выделить два подхода к рисованию дэгов: построение поуровневых (layering-based) и сеточных (grid-based) изображений.

1. Поуровневый подход

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

Методика поуровневого подхода была предложена К. Сугиямой (K. Sugiyama) и состоит из трех основных этапов:

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

Для решения задач каждого из указанных этапов существует ряд эвристик. Таким образом, конкретная реализация является «конструктором» из различных методов, решающих задачи разных этапов.

Благодаря интуитивной понятности и применимости к широкому классу графов, поуровневый подход весьма популярен среди разработчиков систем визуализации графов.

Теперь рассмотрим каждый из указанных этапов более подробно.

1.1. Распределение вершин по уровням

Поуровневым распределением (layering) графа G = (VE) называется разбиение множества вершин V на непересекающиеся подмножества L1, …, Lh, такие, что ∀(u,v)∈E, если uLi, vLj, то i>j. Такие подмножества называются уровнями (layers).

Высотой распределения называется количество уровней h, шириной — число вершин на самом большом уровне. Зазором (span) ребра (u,v), где uLi, vLj, называется разность ij. Распределение сжатое (proper), если нет ребер с зазором большим 1.

Распределение вершин по уровням естественным образом определяется как функция, отображающая множество номеров вершин в множество номеров уровней,

L: VZ

и удовлетворяющая следующим ограничениям:

L(u)≥1, ∀u∈V
L(u)−L(v)≥1, ∀(u,v)∈E.

Очевидно, что для любого ациклического орграфа существует поуровневое распределение, но не для всякого такого графа существует его сжатое распределение. Это может быть продемонстрировано уже для графа всего с тремя вершинами:

Рис. 1. Пример графа, не имеющего сжатого разбиения, и вставка фиктивной вершины

Рис. 1. Пример графа, не имеющего сжатого разбиения, и вставка фиктивной вершины

Необходимость же построения именно сжатого разбиения диктуется следующими причинами:

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

Для построения сжатых разбиений произвольных ациклических орграфов, вдоль ребер с зазором большим 1, добавляют фиктивные вершины (dummy nodes). Очевидно, что вдоль ребра (u,v)∈E, где uLi, vLj, будет добавлено L(u)−L(v)−1 = ij−1 фиктивных вершин.

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

1.1.1. Критерии построения разбиения

При построении поуровневого разбиения следует учитывать следующие критерии:

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

Далее рассмотрим несколько эффективных методов распределения вершин по уровням: распределение по длиннейшему пути (Longest Path algorithm) и применение методов линейного программирования (Linear Programming).

1.1.2. Распределение по длиннейшему пути

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

Следует отметить, что аналогичным образом можно построить разбиение от источников (source), т.е. вершин без входящих дуг. Очевидно, что высота обоих разбиений будет одинакова, но ширина может отличаться на сколь угодно большую величину (рис. 2). Поэтому представляется разумным построить оба разбиения и выбрать из них наименее широкое [1].

Рис. 2. Два способа распределения по методу длиннейшего пути: слева от источников, справа от стоков

Рис. 2. Два способа распределения по методу длиннейшего пути: слева от источников, справа от стоков

Основным недостатком метода распределения по длиннейшему пути является отсутствие оптимизации на ширину разбиения.

1.1.3. Применение симплекс-метода

Е. Гэнснер (E. Gansner) в [6] описал использование для построения поуровневого распределения симплекс-метода, который хотя и не полиномиален, но на практике является быстросходящимся.

Для перехода к задаче линейного программирования используется целевая функция, значение которой необходимо минимизировать:

min ∑(u,v)∈EL(u)−L(v),

где L(u) и L(v) номера уровней вершин u и v (см. выше), и ограничения

L(u)−L(v)≥1 ∀(u,v)∈E.

Разность L(u)−L(v) показывает, насколько длинным будет ребро (u,v), и, как было указано выше, на этом ребре разместятся L(u)−L(v)−1 фиктивных вершин.

Для более гибкого управления рисунком, Гэнснер ввел функции ω(u,v), вес (weight) ребра, по умолчанию равный 1, и δ(u,v), минимальную длину (minimum length) ребра. Увеличение веса ребра сделает его более коротким и вертикально ориентированным, а увеличение δ(u,v) приведет к тому, что оно будет иметь зазор не меньше этой величины.

С учетом ω и δ, целевая функция и ограничения принимают вид:

min ∑(u,v)∈Eω(u,v)(L(u)−L(v)),
L(u)−L(v)≥δ(u,v) ∀(u,v)∈E.

Матрица ограничений является абсолютно унимодулярной (total unimodularity), т.е. все ее миноры равны 0, 1 или −1, откуда и вытекает возможность применения симплекс-метода.

Введем некоторые необходимые определения. Разбиение является допустимым (feasible), если для любого ребра (u,v)∈E выполняется неравенство l(u,v)≥δ(u,v), где l(u,v) — длина соответствующего ребра. При заданном разбиении, не обязательно допустимом, провисанием (slack) ребра называется разность l(u,v)−δ(u,v). Отсюда следует, что разбиение является допустимым, если провисания всех ребер неотрицательны. Ребра с нулевым провисанием называются натянутыми (tight).

При описанном подходе, остовному дереву соответствует семейство эквивалентных поуровневых распределений. Для построения одного из этих распределений сначала выбирается начальная вершина, ей сопоставляется некоторый номер уровня, и она считается обработанной. Затем, на каждом следующем шаге, выбирается вершина, смежная в остовном дереве с уже обработанной вершиной, ей присваивается номер уровня этой смежной вершины, уменьшенный или увеличенный на минимально допустимую длину инцидентного им ребра (пример реализации см. в [6]). Будет ли выполнено уменьшение или увеличение, зависит от того, является ли текущая вершина началом или концом ребра. Этот процесс продолжается до тех пор, пока не будут обработаны все вершины. Остовное дерево, соответствующее допустимому разбиению, также называется допустимым (feasible tree). Ясно, что все ребра допустимого остовного дерева будут натянутыми, а ребра, ему не принадлежащие, могут иметь провисание, отличное от нуля.

После построения допустимого разбиения, всем ребрам, содержащимся в остовном дереве, можно сопоставить разделяющее значение (cut value). Делается это следующим образом. При удалении ребра остовное дерево распадается на две связные компоненты: одна из них содержит начало (головная компонента), а вторая — конец ребра (хвостовая компонента). Разделяющим значением будем называть разность суммы весов ребер, идущих из головной компоненты в хвостовую, включая данное ребро остовного дерева, и суммы весов ребер, идущих из хвостовой компоненты в головную. Пример вычисления разделяющих значений показан на рис. 3а.

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

Обобщая вышесказанное, получим следующий алгоритм:

Построить некоторое начальное допустимое остовное дерево.
Посчитать разделяющие значения.

Пока в дереве есть ребро e с отрицательным разделяющим значением:

    Удалить e из дерева, которое при этом распадется на головную и
        хвостовую компоненту.
    Выбрать одно из ребер, идущих из головной компоненты в хвостовую, и
        имеющих меньшее провисание. Добавить выбранное ребро в остовное
        дерево вместо ребра e.
    Пересчитать разделяющие значения.
    
Выполнить нормализацию разбиения: изменить номера уровней так, чтобы
    меньший из них стал равным 1.

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

Пример работы описанного алгоритма показан на рис. 3. Ребра, не принадлежащие остовному дереву, показаны пунктиром. Все ребра имеют вес 1. На рис. 3а изображено начальное допустимое разбиение и соответствующие разделяющие значения. Например, разделяющее значение ребра (7,8) равно -1 (ω(7,8)−ω(1,5)−ω(1,6) = 1−1−1 = −1). На рис. 3б ребро (7,8) в остовном дереве заменено ребром (1,5) и показаны пересчитанные разделяющие значения. Все они неотрицательны, а значит получено оптимальное разбиение, и выполнение алгоритма завершается.

Рис. 3. Поиск оптимального допустимого разбиения

Рис. 3. Поиск оптимального допустимого разбиения

1.1.4. Сведение к задаче линейного целочисленного программирования с решением за полиномиальное время

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

Определения

Неориентированный граф G = (V,E) представляет собой совокупность множества вершин (vertex) v и множества ребер (edge) E, состоящего из неупорядоченных пар различных вершин графа G. Циклом (cycle) будем называть последовательность ребер (eiE)

{e0, e1, …, en}

таких, что ei и ei+1(mod n) имеют общую вершину, каждая вершина инцидентна не более чем двум ребрам цикла и нет ребер, входящих в цикл более одного раза. Ориентацию графа G определим как функцию σ, определенную на множестве ребер графа G, и сопоставляющую каждому ребру число 1 или −1, так, что если (u,v)∈E, то σ(u,v) = −σ(v,u).

Ориентированный граф (directed graph) D = (V,A) — это совокупность множества вершин V и множества дуг (arc) A, где дуга, или ориентированное ребро (directed edge), это упорядоченная пара различных вершин из D. Ориентированным циклом (directed cycle) будем называть последовательность дуг (aiA)

{a0, a1, …, an}

таких, что если ai = (ui,vi), то vi = ui+1 (mod n) и нет дуг, входящих в цикл более одного раза. Ациклическим ориентированным графом (directed acyclic graph, DAG) называется ориентированный граф, не содержащий ориентированных циклов. Т. к. дэг не содержит симметричных пар дуг (иначе нарушилось бы свойство ацикличности), то он может быть задан посредством соответствующего неориентированного графа и функции ориентации (см. рис. 4).

Рис. 4. Дэг, соответствующий ему неориентированный граф и функция ориентации
Рис. 4. Дэг, соответствующий ему неориентированный граф и функция ориентации

Рис. 4. Дэг, соответствующий ему неориентированный граф и функция ориентации

Гиперграф H = (V,Ψ) — это совокупность множества вершин V и множества гиперребер (hyperedge) Ψ, где гиперребро — это непустое подмножество множества вершин V.

Базис циклов и фундаментальное множество циклов

Пусть D = (V,A) — некоторый дэг, которому соответствует неориентированный граф G = (V,E) и функция ориентации σ. D является ациклическим, а G, очевидно, может содержать циклы. Пусть C — множество всех циклов G. Вектор цикла (cycle vector) χc цикла cC (с координатами χc(e), eE) определяется как

χc(e) = 1, ecли ec,
χc(e) = 0, ecли ec

Векторное пространство циклов (cycle vector space) G — это векторное пространство над полем Галуа порядка 2 (GF(2)), натянутом на χc (∀cC). Множество циклов B = {b1, …, bn}⊆C является базисом циклов (cycle basis), если χb (∀bB) формирует базис для векторного пространства циклов G. Следовательно, ∀cC,

χc = ∑i=1,…,n αibi

хотя бы с одним ненулевым коэффициентом αi.

Пусть T — остовный лес G. Тогда множество фундаментальных циклов (set of fundamental cycles) F может быть сконструировано следующим образом: ∀e=(u,v)∉T существует единственный цикл в T∪{e} (рис. 5 и таблица 1). Эти циклы и образуют множество фундаментальных циклов графа. Любое такое ребро eхорда (chord) G относительно T. Множество фундаментальных циклов образует базис циклов. Обратное, вообще говоря, не верно. В соответствии с ориентацией хорд выбирается направление в фундаментальных циклах. Ребра циклов, чья ориентация совпадает с этим направлением, будем называть прямыми (forward), противоположно направленные — обратными (backward).

Рис. 5. Остовное дерево (сплошные линии) и хорды (пунктирные линии)

Рис. 5. Остовное дерево (сплошные линии) и хорды (пунктирные линии)

Таблица 1. Хорды и соответствующие фундаментальные циклы графа (рис. 5)
F Хорда Фундаментальный цикл
F0 (2,4) {(2,4),(4,3),(3,2)}
F1 (4,5) {(4,5),(5,10),(10,11),(11,7),(7,6),(6,1),(1,2),(2,3),(3,4)}
F2 (7,8) {(7,8),(8,5),(5,10),(10,11),(11,7)}
F3 (5,9) {(9,5),(5,10),(10,9)}
F4 (13,14) {(13,14),(14,12),(12,11),(11,10),(10,9),(9,13)}

Гиперграфом фундаментальных циклов (fundamental cycle hypergraph, FCH) графа G относительно F называется гиперграф FCH(G,F)(F,Ψ), множеством вершин в котором является F, а каждое гиперребро E∈Ψ — это максимальное непустое подмножество EF такое, что ∩FEF ≠ 0. Таким образом, каждое гиперребро ассоциировано с некоторым подмножеством ребер графа G (см. рис. 6 и таблицу 2).

Рис. 6. Гиперграф фундаментальных циклов

Рис. 6. Гиперграф фундаментальных циклов

Таблица 2. Множества ребер, ассоциированные с гиперребрами гиперграфа (рис. 6)
Гиперребро Соответствующее множество ребер (si = si+si)
s0 {(2,4)} Ø
s1 {(4,5),(1,2)} {(6,1),(7,6)}
s2 {(6,7),(7,5)} Ø
s3 {(9,5)} Ø
s4 {(13,14),(14,12),(9,13)} {(12,11)}
s5 {(2,3),(3,4)} Ø
s6 {(7,11)} Ø
s7 Ø {(10,9)}
s8 Ø {(5,10)}
s9 {(10,11)} Ø
Распределение вершин по уровням

Как уже упоминалось выше, поуровневое распределение можно ввести как функцию, сопоставляющую вершине номер ее уровня:

L: V → Z
L(u)≥1, ∀uV (1)
L(u)−L(v)≥1, ∀(u,v)∈A. (2)

L однозначно определяет местоположение фиктивных вершин: вдоль дуги (u,v)∈A добавляется L(v)−L(u)−1 фиктивных вершин.

Альтернативный способ ввести распределение по уровням — задать функцию, сопоставляющую каждому ребру количество фиктивных вершин на нем:

L′: EZ.

Выясним, каким ограничениям должна удовлетворять функция L′, чтобы задавать правильное сжатое разбиение. Для этого введем понятие сбалансированного (balanced) цикла в неориентированном графе. L′ балансирует цикл C в G, если

e=(u,v)∈E χc(e)σ(u,v)(1+L′(e)) = 0,

где ребра (u,v)∈E берутся в порядке обхода цикла в произвольном направлении.

Теорема. Если функция L′ балансирует любое множество фундаментальных циклов в G, то она балансирует все циклы в G.

Доказательство этой теоремы приводится в [6].

Ясно, что если L′ балансирует все циклы в G, то она задает правильное сжатое разбиение.

Построив некоторое фундаментальное множество циклов F, разобьем множество ребер графа на подмножества так, чтобы любое подмножество было максимальным множеством ребер, общим для некоторого подмножества из F. Это будут те же подмножества, которые ассоциированы с гиперребрами гиперграфа фундаментальных циклов FCH(G,F).

Пусть S = {s1, …, sn} — такое разбиение. Оно может быть получено за время O(|E|2):

    Исходные данные: граф G = (V,E) и множество фундаментальных
        циклов F = {F1, …, Fm}

    Результат: разбиение множества ребер S = {s1, …, sn}

    Заполнить матрицу инцидентности фундаментальных циклов и ребер:
    Отсортировать столбцы этой матрицы.

    Разбить множество ребер на подмножества так, чтобы ребра
        с одинаковыми соответствующими им столбцами в матрице
        инцидентности, попали в одно подмножество, S = {s1, …, sn}

Далее подмножества ребер siS можно разбить на две группы si+ и si, — ребра направленные в одну и в противоположную сторону. Будем снова называть их прямыми и обратными. Фиктивные вершины, ассоциированные с некоторым прямым (соответственно обратным) ребром могут быть перемещены на любое другое прямое (соответственно обратное) ребро того же подмножества, и сбалансированность фундаментальных циклов при этом не нарушится.

Заменим L′ двумя функциями,

L+: SZ
L: SZ,

заданными на подмножествах прямых и обратных ребер соответственно.

Эти функции подчиняются следующим ограничениям:

sS γ(F,s)(|s+|−|s|+L+(s)−L(s)) = 0, ∀FF, (3)
L+(s) = 0, ∀sS такого, что s+ = Ø, (4)
L(s) = 0, ∀sS такого, что s = Ø, (5)
L+(s) ≥ 0, L(s) ≥ 0, ∀sS, (6)

где γ(F,s) есть ориентация ребер подмножества s относительно фундаментального цикла F, определяемая следующим образом: γ(F,s) = 1, если sF и прямые (соответственно обратные) ребра в s являются прямыми (соответственно обратными) в F, γ(F,s) = −1 если sF и прямые (соответственно обратные) ребра в s являются обратными (соответственно прямыми) в F, γ(F,s) = 0, если sF. Функция γ(F,s) задает матрицу инцидентности фундаментальных циклов и подмножеств ребер (fundamental cycle-edge subset incidence matrix) графа D.

Формулировка задачи в терминах линейного целочисленного программирования

Гэнснер в [6] свел распределение вершин по уровням к задаче линейного целочисленного программирования, используя в качестве целевой функции выражение

(u,v)∈A L(u)−L(v),

значение которого необходимо минимизировать с учетом (1), (2) и необходимых ограничений на переменные.

Альтернативный способ перейти к линейному целочисленному программированию основан на использовании функций L+ и L и минимизации

sS L+(u)+L(v)

с учетом (3), (4), (5), (6) и необходимых ограничений на переменные.

В этой альтернативной формулировке, также как в методе, описанном Гэнснером [6], матрица ограничений обладает свойством абсолютной унимодулярности. Это гарантирует, что задача является полиномиально разрешимой и имеет целочисленные решения.

Достоинства описанного метода

Полученное решение описывает некоторое семейство распределений по уровням с одинаковым числом фиктивных вершин. Фиктивные вершины, размещенные на прямых или обратных ребрах одного подмножества, можно перемещать на другие прямые и обратные ребра соответственно, принадлежащие тому же подмножеству. Т.к. m неразличимых фиктивных вершин могут быть распределены между n различимыми ребрами Cm+n−1n−1 различными способами, то решение определяет

sS СL+(s)|s+|−1|s+|−1 × СL(s)|s|−1|s|−1

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

Одно из возможных разбиений для графа, изображенного на рис. 4, выглядит следующим образом:

Рис. 7. Разбиение с минимальным числом фиктивных вершин

Рис. 7. Разбиение с минимальным числом фиктивных вершин

1.2. Определение порядка вершин на уровне

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

Заметим, что количество пересечений ребер в поуровневом изображении зависит не от конечных координат вершин, а от их относительного положения внутри каждого уровня. Таким образом, задача данного этапа является не геометрической, а комбинаторной. Однако уже для графа с двумя уровнями (bipartite graph) она является NP-полной даже в том случае, если порядок вершин на одном из этих уровней фиксирован.

В большинстве работ проблема минимизации пересечений ребер в поуровневом орграфе решается не глобально для всего графа, а локально — для всех пар соседних уровней. Обычно это выглядит следующим образом. На первом уровне L1 выбирается некоторый начальный порядок. Затем для каждого i = 2, …, h порядок на уровне Li−1 считается фиксированным, а вершины на уровне Li переставляются так, чтобы минимизировать число пересечений ребер, соединяющих уровни Li−1 и Li. После достижения последнего уровня выполнение алгоритма продолжается в обратном направлении. Критерием окончания работы может служить либо выполнение фиксированного числа проходов, либо отсутствие уменьшения или существенного уменьшения общего числа пересечений.

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

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

Для «средних» случаев применяется ряд эвристик, позволяющих найти приближенное решение за приемлемое время и рассмотренных ниже.

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

1.2.1. Метод барицентров, медиан и их модификации

На практике широко применяются алгоритмы, основанные на методе барицентров (barycenter heuristic). Суть этого метода состоит в том, что координата вершины vLi определяется как среднее арифметическое координат ее соседей с уровня Li−1 (рис. 8а). Следует отметить, что на этом этапе под координатой вершины понимается ее порядковый номер на уровне. Если после перестановки координаты каких-либо двух вершин совпали, то они разносятся на минимальное расстояние, порядок при этом определяется произвольно.

Самая распространенная модификация метода барицентров — метод медиан (median heuristic), где вместо среднего арифметического используется координата среднего соседа с уровня Li−1. Если же число соседей на этом уровне четно, то может использоваться либо средний левый, либо средний правый сосед (рис. 8б).

Рис. 8. Применение метода барицентров и метода медиан для определения позиции вершины

Рис. 8. Применение метода барицентров и метода медиан для определения позиции вершины

Для описанных методов верны следующие два утверждения:

  • Если для данного графа возможно размещение без пересечений ребер, то и метод барицентров, и метод медиан его находят.
  • После применения метода медиан остается не более 3n пересечений ребер, где n — минимально возможное число пересечений ребер для данного графа.

Известны также следующие модификации метода медиан:

  • Полумедианы. Для вершин с четным числом соседей на предыдущем уровне, используется значение, полученное по методу барицентров.
  • Взвешенные медианы. Для вершин, имеющих четное число соседей на соседнем уровне, позиция выбирается между средним левым и средним правым соседом, ближе к той стороне, где вершины располагаются более плотно. См. [6].

1.2.2. Сведение к задаче о назначениях

Описанный в этом разделе метод, известный как assignment heuristic, основан на сведении задачи минимизации пересечений в поуровневом орграфе к задаче о назначениях.

Задача о назначениях (assignment problem) — это задача о наилучшем распределении некоторого числа заданий между испольнителями с учетом заданных значений cij — затрат на выполнение i-ым рабочим j-го задания. Для решения задачи о назначениях используется венгерский алгоритм (Hungarian method).

Вернемся к задаче минимизации пересечений ребер. Будем рассматривать два соседних уровня исходного графа, представляющие собой двудольный граф G=(L,R,E) и будем считать, что позиции вершин на уровне L фиксированы. Пусть B(m×n×m×n) — 4-мерная матрица, элемент Babcd которой равен 1 тогда и только тогда, когда выполняется условие (c>a и b<d) или (c<a и d>b), и равен 0 в противоположном случае.

Задача минимизации пересечений в двудольном графе G=(L,R,E) соответствует задачи о назначениях, заданной матрицей C(m×n), где m=|R|, cij=∑nh=1[ahi( ∑mc=1nd=1 Bjhcd)], j,c∈, h,dL. Элемент cij, как несложно заметить, представляет собой максимальное число пересечений ребер, возникающих при размещении вершины i на позиции j.

1.2.3. Методы, основанные на сортировке

Методы, описанные в этом разделе, основаны на идее сортировки вершин каждого уровня с целью уменьшения количества пересечений ребер. Для двух выбранных вершин vLi и uLi количество пересечений инцидентных им ребер зависит только от относительного положения этих двух вершин и не зависит от положения остальных вершин этого уровня. Поэтому между вершинами одного уровня можно установить отношение/порядок, которое задается количеством пересечений ребер, порождаемых различными расположениями вершин.

Такое отношение не образует отношение линейного или частичного порядка. В противном случае обычная сортировка решила бы нашу NP-полную задачу по крайней мере за квадратичное время. Пример, иллюстрирующий это замечание, см. в [1].

Однако закон трихотомии для нашего отношения выполняется. А это означает, что возможна устойчивая сортировка вершин, при которой выполняются свойства упорядоченности и устойчивости. Выполнение такого упорядочения лежит в основе методов, основанных на сортировке.

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

Другой метод, позволяющий упорядочить множество вершин, основан на идее быстрой сортировки. Сначала выбирается "средняя" вершина, а все остальные вершины разбиваются на два множества в зависимости от того, в каком отношении они находятся с выбранной вершиной. Затем подобная процедура рекурсивно применяется к каждому из получившихся множеств.

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

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

1.2.4. Переход к планарному графу

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

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

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

1.3. Определение горизонтальных координат вершин

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

  • Изображение должно быть компактным.
  • Ребра должны быть настолько вертикальными, насколько это возможно.

Гэнснер в [6] сформулировал задачу определения горизонтальных координат вершин в виде задачи оптимизации:

min ∑(v,u)∈Eω(v,u)·|x(v)−x(u)|
x(b)−x(a)≥δ(a,b),

где a — левый сосед вершины b на уровне Li, 1≤ih, ω(v,u) — весовая функция, описанная в разделе 1.1.3, δ(a,b) — минимальное расстояние между вершинами a и b. Т. к. ребра соединяющие реальные вершины всегда могут быть изображены отрезками прямых, то важнее уменьшить горизонтальное расстояние между фиктивными вершинами так, чтобы цепочки фиктивных вершин могли быть выравнены вертикально и таким образом выпрямлены соединяющие их ребра. Но при выпрямлении длинных ребер может возникнуть т. н. эффект спагетти (spaghetti effect): много разных сгибов на одном ребре. Чтобы этого избежать используют, например, следующую технику. Вес ω ребер, соединяющих две фиктивные вершины, должен быть больше веса ребер, соединяющих фиктивные вершины с реальными, который, в свою очередь, больше веса ребер, соединяющих две реальные вершины. Например, 8, 2 и 1 соответственно (согласно [6]).

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

Хорошие результаты также могут быть получены применением методов, основанных на упругосиловой физической модели. См. [1].

2. Сеточный подход

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

Такие методы также называются нумерующими (numbering-based), потому что в процессе работы вершины и грани (faces) графа нумеруются, а затем координаты вершин и сгибов ребер рассчитываются с использованием этой нумерации. В русскоязычной литературе также встречается термин мозаичный метод [1].

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

Литература

  1. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003.
  2. Catarci T. The Assignment Heuristic for Crossing Reduction. IEEE Transactions on Systems, Man, and Cybernetics, 25(3), 1995. http://citeseer.ist.psu.edu/catarci88assignment.html
  3. Cruz I. F., Tamassia R. Graph Drawing Tutorial. http://www.cs.brown.edu/people/rt/gd.html
  4. Di Battista G., Eades P., Tamassia R., Tollis I. G. Algorithms for Drawing Graphs: An Annotated Bibliography. Computational Geometry: Theory and Applications 4:235-282 (1994). http://www.cs.brown.edu/people/rt/gd.html
  5. Di Battista G., Garg A., Liotta G., Parise A., Tamassia R., Tassinari E., Vargiu F., Vismara L. Drawing Directed Acyclic Graphs: An Experimental Study. In Proc. Graph Drawig (GD'96'), Lectures Notes i Computer Sciece 1190, Spriger-Verlag, pages 76 91, 1996. http://citeseer.ist.psu.edu/dibattista96drawing.html
  6. Gansner E. R., Koutsofios E., North S. C., Vo K.-P. A Technique for Drawing Directed Graphs. IEEE Trans. Softw. Eng., 19(3):214—230, 1993. http://citeseer.ist.psu.edu/gansner93technique.html
  7. Harrigan M., Healy P. On Layering Directed Acyclic Graphs. Graph Drawing, 8.-13. May 2005. Dagstuhl Seminar Proceedings 05191 Internationales Begegnungs- und Forschungszentrum fur Informatik (IBFI), Schloss Dagstuhl, Germany 2006.
  8. Поуровневое рисование ациклических орграфов (Чеботарева Ю., 2007)

Юлия Чеботарева


Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий