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

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Введение

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

При создании понятных и доходчивых отображений всегда учитываются три ключевых момента: физические ограничения, присущие среде (например, экран компьютера), условные ограничения отображений и эстетика [1]. Условные ограничения существенно зависят от правил предметной области. В данной работе мы фокусируемся на иерархических графах, где вершины располагаются на вертикальных слоях, а ребра, соединяющие пары вершин, представлены ориентированными отрезками линий, которые идут в одном направлении. Из основополагающих работ [2] и [3], это представление было выбрано для выделения направленных парных отношений в многочисленных системах. Оптимизация эстетики направлена на улучшение читабельности и запоминания информации, содержащейся в графе. Недавние эксперименты, подтверждающие предыдущие результаты [4], указывают на то, что пересечения ребер- безусловно, самый важный эстетический критерий [5].

Минимизация числа пересечений в иерархической структуре может показаться интуитивно проще, чем общая проблема минимизации пересечений на плоскости, так как количество пересечений определяется порядком вершин вместо геометрических координат вершин. Тем не менее, она остается NP-полной, даже если есть только два слоя [6]. Многочисленные детерминированные эвристики следуют схеме поуровневого просмотра: вершины каждого слоя переупорядочиваются, чтобы уменьшить пересечения, сохраняя при этом порядок вершин в других слоях. При этом чаще всего используются методы сортировки и эвристика усреднения, которые включают эвристику барицентра [2], median эвристику и их варианты. Методы сортировки обменивают вершины, используя количества пересечений, аналогично классическим сортировкам [3]. Усредняющая эвристика основана на идее, что пересечения ребер, как правило, минимизируются, когда соединенные вершины располагаются лицом друг к другу. Следовательно, вершины располагаются в соответствии со средними положениями соседей, например, среднее арифметическое или медиана.

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

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

1. Основные определения

1.1 Понятия ориентированного ациклического графа, степени вершины, дерева

Граф G-пара (V, E), где V- конечное множество вершин, а E - конечное множество ребер. Каждое ребро состоит пары вершин . Если ребра не ориентированы(ребра считаются одинаковыми), то граф называется неориентированным, иначе- ориентированным.

Степень вершинынеориентированного графа -число попадающих в него ребер. Ели граф является ориентированным, то для вершин определены полустепень вершины -число ребер, исходящих в , и полустепень вершины - число ребер, входящих из . Вершина называется изолированной, если .

Граф без циклов называется ациклическим графом.

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

Граф G = (V, E) связный, если каждая пара вершин соединена путем.

Двудольный граф G = (V1, V2; E) -граф (V, E), множество вершин V которого разбито на два подмножества V1 и V2, так что каждое ребро соединяет вершину в V1 и вершину в V2.

Дерево- связный граф без циклов. Известно, что дерево с n вершинами имеет ровно n - 1 ребер. Корневое дерево - дерево, в котором одна из вершин является выделенной. Эту выделенную вершину называют корнем дерева.

Высота вершины u в дереве T-длина самого длинного пути из u к листу. Высота дерева-высота его корня. Глубина вершины u в дереве T - длина пути от корня до u.

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

1.2 Понятия планарного графа, иерархического графа, возможных отображений графа

Граф называется плоским, если он уложен на плоскость.

Граф G = (V, E) называется планарным, если он изоморфен плоскому графу.

Пусть G = (V, E) - ориентированный ациклический граф. Распределение вершин по уровням графа G -топологическая нумерация ц графа G, , отображающая множество вершин V графа G в целые числа, такие что для каждого направленного ребра и называется иерархическим (многоуровневым или уровневым) графом.

Иерархический граф называется правильным, если каждое ребро связывает только вершины, принадлежащие последовательным слоям. Если иерархический граф не является правильным, он должен иметь хотя бы одно ребро, такое, что и с, такое ребро называется длинным ребром, и говорят, что оно пересекает слои l с. Любой неправильный иерархический граф может быть преобразован в правильный иерархический граф путем замены каждого длинного ребра на путь коротких ребер, имеющих фиктивную вершину в каждом пройденном слое. Рисунок 1.1 показывает пример правильных и неправильных иерархических графов.



Рисунок 1.1 Пример правильного (a) и неправильного (b) иерархических графов. Корневые вершины показаны черным цветом

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

Планарный граф с фиксированным плоским отображением называется плоским графом.

Прямолинейное отображение - отображение графа, на котором все ребра графа изображены как отрезки прямых (Рисунок 1.2(а)).

Отображение с полилиниями- отображение графа, в котором каждое ребро графа представлено ломаной (Рисунок 1.2 (b)). Точка, в которой ребро меняет направление на чертеже полилинии, называется изгибом ребра. Визуализация полилиний обеспечивают большую гибкость, поскольку они могут приближаться к чертежам с изогнутыми краями. Тем не менее, края с более чем двумя изгибами уже могут быть сложны для визуального восприятия. Стоит отметить, что отображение прямой является частным случаем рисования ломаной линии, где края нарисованы без изгибов.



Рисунок 1.2. Пример прямолинейного отображения (a) и отображения с полилиниями (b)

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

Иерархическое отображение графа G называется планарным, если не пересекаются любые два ребра, кроме как в общих конечных точках. Иерархический граф называется иерархическим планарным графом, если он имеет иерархический плоский чертеж.



Рисунок 1.3. Пример иерархического отображения графа.

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

2.1 Постановка задачи

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

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

2. Критерии правильности: например, размещение работодателя над работниками на чертеже дерева организации, или вершина v должна быть справа от вершины u.

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

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

Для отображения графов берутся во внимание эстетические критерии, такие как:

· минимизация количества пересечений рёбер

· минимизация размеров областей изображения

· общая длина рёбер: минимизация суммарной длины всех рёбер или различий в длинах рёбер, ограничение количества длинных ребер

· общее число изгибов: минимизация общего числа изгибов, ограничение числа изгибов

· симметрия

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

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

2.2 Общий иерархический подход Sugiyama

Первые попытки построения ориентированных графов в иерархической форме представлены Warfield [3] и Carpano [4]. Тем не менее, наиболее распространенный и известный подход для иерархических отображений поуровневых графов и общих произвольных ориентированных графов представлен в 1981 году Sugiyama, K., S. Tagawa, andM. Toda[2] и назван подходом Sugiyama.

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

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

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

Шаг 1: Удаление циклов

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

Шаг 2: Распределение вершин по уровням

На этом этапе в качестве входных данных алгоритм получает ориентированный ациклический граф после этапа удаления цикла. Множество вершин из V разбиты на конечное множество слоев V1, V2, ..., Vk, такие, что если - ребро с и, то. Затем уровневый граф переносится в правильный уровневый граф, так что если (u, v) - ребро с и, то. Это делается с помощью подразбиения фиктивными вершинами ребер, которые охватывают более двух слоев, т.е. таких ребер , где и , что. На последнем уровнем ножество вершин Vi будет иметь ту же координату y, равную i. Результатом этого шага является многоуровневый иерархический граф .

Шаг 3: Определение порядка вершин

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

Шаг 4. Назначение координат вершин

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

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

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

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

Рисунок 2.1. Пример подхода Sugiyama. Отображение ориентированного графа в (а) и отображения, полученные после каждого шага подхода Sugiyama (b) - (e). В (f) представлено финальное отображение исходного графа после восстановления направления перевернутых ребер. Фиктивные вершины представлены в незаполненных маленьких кружках

2.3 Известные методы минимизации пересечений ребер

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

Предположим, что - два коротких ребра в иерархическом графетакое, что , тогда e1 и e2 пересекаются, если (р (u2) - р (u1)) · (р (v2) - р (v1)) <0, где р (v) - порядок вершины v в ее слое. Смотрите пример, приведенный на рисунке 2.2. Так, на рисунке 2.2 (a)р(1) = 1, р(2) = 2, р(3) = 1, р(4) = 2, а на рисунке 2.2 (b) р(1) = 1, р(2) = 2, р(3) = 2, р(4) = 1.

граф минимизация иерархический

Рисунок 2.2. Пример вычисления пересечения ребер по относительному порядку вершин в их слоях. На (а) нет пересечения между двумя ребрами (1,3) и (2,4), поскольку (р (2) - р (1)) · (р (4) - р (3)) = 1 · 1 = 1> 0. На (b) два ребра пересекаются, поскольку (р (2) - р (1)) · (р (4) - р (3)) = 1 · (?1) = ?1 <0

Важным наблюдением здесь является то, что количество пересечений ребер иерархического графа зависит не от точного положения (x-координат) вершин в их слоях, а только от упорядочения вершин в каждом слое. Следовательно, проблема минимизации пересечений ребер в иерархическом графе является комбинаторной задачей выбора подходящего порядка вершин для каждого слоя, а не геометрического выбора координаты x для каждой вершины. Хотя эта комбинаториализация упрощает проблему, она все еще трудна и имеет классификацию NP-hard даже с графом, имеющим только два слоя (то есть с двудольным графом) [6]. Кроме того, проблема минимизации пересечения по-прежнему остается NP-трудной, даже если один слой имеет фиксированный порядок вершин [8] и для разреженных графов со степенью вершин, равной 4 [9].

Упорядочение (или перестановка) рi множества вершин, принадлежащих уровню Vi, в иерархическом графе обеспечивает решение задачи минимизации пересечения, поскольку именно относительное упорядочение вдоль линии Li = i заставляет ребра, попадающие на этот слой, пересекать друг друга. Мы ищем множество перестановок, , которое минимизирует пересечение ребер.

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

Метод поуровневого рассмотрения работает при перестановках вниз следующим образом: во-первых, сначала выбирается порядок расположения уровней по вершинам, когда вершины получают свои позиции в порядке слева направо. На следующем шаге выбирается уровень с предварительно вычисленным порядком, например, слой V1, и для i = 2, 3, …, k порядок вершин уровня Vi ? 1 сохраняется фиксированным, в то время как вершины в уровне Vi переупорядочены для уменьшения пересечений между двумя уровнями Vi ? 1 и Vi. Мы можем перейти от слоя Vk к слою V1 и повторять эти два шага, пока не будет достигнуто дальнейшее уменьшение пересечений.

При использовании любого алгоритма минимизации одностороннего пересечения число пересечений между двумя уровнями Vi ? 1 и Vi уменьшается путем перестановки вершин в слое Vi, тогда как число пересечений между Vi и Vi + 1 может быть увеличено, переставляя Vi. Эти эвристики толкают пересечения вниз или вверх, в зависимости от направления потока, до тех пор, пока они не будут разрешены в слое k или 1 соответственно. Возможны другие способы, например, мы можем зафиксировать слой посередине и переставлять от него до нижнего и верхнего слоя. Таким образом, расширение - это центрированное 3-уровневое уменьшение пересечения, т.е. с учетом трех последовательных уровней Vi ? 1, Vi и Vi + 1 путем перестановки Vi, в то время как порядки Vi ? 1 и Vi + 1 фиксированы так, что пересечения между тремя слоями сокращены. Однако ключевая проблема поуровневой развертки заключается в уменьшении пересечений между двумя уровнями с фиксированной перестановкой одной стороны.

Основным недостатком поуровневого подхода является то, что он может застрять в локальном оптимуме, хотя одностороннее уменьшение пересечения двух уровней возвращает оптимальное расположение вершин в смысле минимального числа пересечений. Bastert и Matuszewski утверждали в [10], что результаты даже далеки от оптимальных. Увы, потенциально существующие коэффициенты аппроксимации односторонних алгоритмов двухслойного сокращения не могут быть фактически расширены для применения к иерархическим графам k-уровней.

Хотя двухуровневые алгоритмы уменьшают пересечения между Vi-1 и Vi, число пересечений между Vi и Vi + 1 (и, следовательно, даже общее количество пересечений) может увеличиваться при перестановке среднего слоя Vi. Эти эвристики толкают пересечения вниз или вверх, пока они не разрешатся на уровне k или 1 соответственно. Что еще хуже, могут остаться конфликты типа 2 (пересечение между двумя ребрами, которые соединяют только фиктивные вершины). Альтернативами являются упорядоченное просеивание k-слоя или аналогичное центрированное трехслойное уменьшение пересечения, описанное в разделе 2.3.4. Тем не менее, оба порождают много конфликтов типа 2 и предназначены для достижения глобального оптимума, оба ограничены локальным представлением. Таким образом, они также могут застрять в локальных оптимумах.

Бахмайер, Бранденбург, Бруннер и Хюбнер в [11] ввели глобальный алгоритм отсева (описанный в разделе2.3.4), в котором не используются развертки с двухуровневым односторонним фиксированным пересечением. Они рассматривают блок-граф - который совпадает с их графом уплотнения, заполненным одним проходом по всем уровням, - непосредственно для уменьшения пересечения. Затем весь граф обрабатывается. Экспериментально алгоритм глобального просеивания дал лучшие результаты, чем любой односторонний двухуровневый метод, он работает с более высокой сложностью и имеет время выполнения, ограниченное O (|E|2) для иерархического k-уровневого иерархического графа H = (V, E , ц).

Двудольный граф H = (V1, V2; E) является неориентированным графом G = (V, E), в котором V разбивается на два множества V1 и V2, так что (u, v) ? E подразумевает либо u ? V1, либо v ? V2 или v ? V1 и u ? V2. Упорядочение слоя Vi задается перестановкой рi из Vi. Итак, упорядочение двух уровней V1 и V2 - это перестановки р1 и р2 соответственно.

Пусть будет количеством пересечений ребер в отображении графа G, с заданными р1 и р2. Если перестановка р1 в V1 остается неизменной, минимальное количество пересечений ребер, которое может быть достигнуто путем переупорядочения вершин в V2, определяется с помощью ,где:

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

Дан двудольный граф G = (V1, V2, E) с перестановкой р1 из V1. Нужно найти порядок р2 в V2, который минимизирует пересечения ребер на отображении графа G, такой, что =.

Понятие числа пересечений, введенное P. Eades и D. Kelly [12], важно для многих эвристик. р1 является перестановкой слоя V1 и остается фиксированной, для каждой пары вершин u, v ? V2 cuv представляет количество пересечений между ребрами, которые падают на u, и ребрами, падающими на v, когда р2 (u) <р2 (v). Также для всех u ? V2 определим cuu = 0.

В задаче минимизации многоуровневого пересечения задан k-уровневый иерархический граф H, H = (V1, V2, ..., Vk; E), и цель состоит в том, чтобы найти перестановки р1, р2, ..., рk так, чтобы число пересечений ребер было минимальным. Для задачи минимизации пересечения с несколькими уровнями существует два решения. В первом подходе мы применяем поуровневую одностороннюю эвристику рекурсивно, чтобы получить порядок вершин в слое Vi, в то время как вершины в слое Vi ? 1 имеют фиксированный порядок, а затем переходим к следующему слою. Во втором подходе все уровни графа рассматриваются глобально одновременно в одно и то же время.

Эксперименты M. Jьnger и P. Mutzel [13] для задачи минимизации пересечения двух уровней показывают, что результаты поуровневых перестановок далеки от оптимальных. Можно ожидать лучших результатов при одновременном рассмотрении всех уровней, но минимизация многоуровневых пересечений является очень сложной проблемой [10]. Быстрая помощь состоит в том, чтобы запустить поуровневые перестановки несколько раз со случайно переставленными слоями. Этот подход может значительно улучшить результаты в [13]. Со стороны глобального подхода есть некоторые глобальные методы (такие как алгоритм глобального просеивания), представленные Бахмайером, Бранденбургом, Бруннером и Хюбнером [11]. Экспериментально было показано в [11], что метод глобального просмотра дает улучшение на 5-10% числа пересечений по сравнению с поуровневыми, однако он обычно имеет худшую временную сложность.

2.4 Собственный подход минимизации пересечений ребер

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

Шаг 1: Выбор корневой вершины.

Учитывая, что изначально граф G = (V, E) является неориентированным, мы можем выделить любую вершину, как начальную(т.е. как корень графа) и с помощью обхода в глубину, можно составить список смежности и преобразовать входные ребра, которые содержат информацию как source и target, подающиеся как номера начальной и конечной вершины, в ориентированные ребра. Так, мы сразу создаем ацикличный граф, в котором не требуется делать удаление циклов.

Шаг 2: Распределение вершин по уровням

На этом этапе наш алгоритм получает в качестве входных данных уже преобразованный в ориентированный ациклический граф G = (V, E) после выполнения шага 1. Тогда, нам удается разбить множество вершин на конечное множество уровней, таких, что если (u, v) ? ребро с u ? Vi и v ? Vj, то i <j. Затем уровневый граф переносим в правильный уровневый граф, путем вставки фиктивных вершин вдоль ребер, которые охватывают более двух уровней. Результатом этого шага является многоуровневый иерархический граф, где у каждой вершины теперь проставлена координата x, которая и является номером уровня (координата х варьируется от 0 до числа количества уровней).

Шаг 3: Определение порядка вершин на каждом уровне

Правильный многоуровневый иерархический ориентированный граф H = (V1, V2, ..., Vk; E), созданный на этапе назначения уровней, является входом для этого этапа. Поскольку порядки вершин на слоях определяют топологию окончательного отображения, эти порядки вычисляются таким образом, чтобы количество пересечений было как можно меньше. Результатом этого шага является новый правильный многоуровневый ориентированный граф, в котором порядок указан для вершин в каждом слое.

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

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

Реализация алгоритма выполнена на языке программирования JavaScriptc использованием библиотеки Sigma.js.

Пример 1

Теперь рассмотрим работу данного алгоритма на конкретном примере.

Возьмем, к примеру, неориентированный связный граф из 9 вершин, пронумерованных от 0 до 8,ребра которого соединены следующим образом (таблица 2.1):

Таблица 2.1. Информация о ребрах в исходном графе

Source	Target
4	3
3	6
4	2
2	3
4	0
0	2
4	5
5	2
5	7
7	1
1	0
4	8

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

Рисунок 2.3. Полный список смежности

Таблица 2.2. Степени, относящиеся к каждой вершине соответственно

id	0	1	2	3	4	5	6	7	8
d	3	2	4	3	5	3	1	2	1

Отсортированный список степеней вершин по убыванию.

Таблица 2.3. Степени, относящиеся к каждой вершине соответственно, по убыванию

id	4	2	0	3	5	1	7	6	8
d	5	4	3	3	3	2	2	1	1

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



Рисунок 2.4. Список смежности графа, где корневая вершина, у которой id 8

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

Таблица 2.4. Параметр х у каждой вершины

id	0	1	2	3	4	5	6	7	8
X	4	5	3	2	1	7	3	6	0

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

Таблица 2.5. Преобразованные в ориентированные ребра из исходных данных

Source	Target
8	4
4	3
3	6
3	2
2	0
0	1
1	7
7	5
2	5
4	2
4	0
4	5

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

Таблица 2.6. Список ребер с учетом добавленных фиктивных вершин

Source	Target
8	4
4	3
3	6
3	2
2	0
0	1
1	7
7	5
2	9
9	10
10	11
11	5
4	12
12	2
4	13
13	14
14	0
4	15
15	16
16	17
17	18
18	19
19	5

Таблица 2.7. Список вершин графа, с учетом добавленных фиктивных

id	x	y
0	4	0
1	5	0
2	3	1
3	2	0
4	1	0
5	7	0
6	3	0
7	6	0
8	0	0
9	4	1
10	5	1
11	6	1
12	2	1
13	2	2
14	3	2
15	2	3
16	3	3
17	4	2
18	5	2
19	6	2

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



Рисунок 2.5. Визуализация графа с корневой вершиной, у которой id=8, без применения метода минимизации пересечений ребер

Рисунок 2.6. Визуализация графа с корневой вершиной, у которой id=8, с применением метода минимизации пересечений ребер

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



Рисунок 2.7. Визуализация графа с корневой вершиной, у которой id=2, с применением метода минимизации пересечений ребер

Пример 2.

Теперь рассмотрим данный алгоритм на другом примере. Неориентированный связный граф из 9 вершин, пронумерованных от 0 до 8, ребра которого соединены следующим образом.

Таблица 2.8. Информация о ребрах в исходном графе

Source	Target
1	2
0	6
4	7
3	6
2	5
6	7
7	8
5	7

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



Рисунок 2.8. Полный список смежности

Таблица 2.9. Степени, относящиеся к каждой вершине соответственно

id	0	1	2	3	4	5	6	7	8
d	1	1	2	1	1	2	3	4	1

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

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



Рисунок 2.9. Визуализация графа с корневой вершиной, у которой id=8, с применением метода минимизации пересечений ребер

Рисунок 2.10. Визуализация графа с корневой вершиной, у которой id=7, с применением метода минимизации пересечений ребер

3. Описание вычислительных экспериментов

Реализованный алгоритм и дополнительные к нему методы для вычислительных экспериментов запускались наIntel® Core™ i3-4160 CPU @ 3.60GHz 3.60GHz.

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

Рассматривались сгенерированные графы с количеством вершин 8, 10, 15, 20 с плотностями n+5, 2n, n2/3, где n это число вершин, выполняя все действия алгоритма заданное число итераций. Причем, перебирая каждую вершину, как начальную, начиная с той, у которой степень наибольшая. Так, были собраны результаты, представленные в таблицах 3.1, 3.2 и 3.3.

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

Таблица 3.1. Результаты вычислительных экспериментов по построению генерированных графов с плотностью n+5, где n- число вершин

n=8
i=100
T	12.04
t	1.45	1.66	1.1	1.36	1.5	1.1	1.24	0.98
d	4.92	4.23	3.76	3.43	3.09	2.73	2.25	1.63
I	3.27	3.38	3.44	3.53	3.43	3.41	3.35	3.15
i=1000
T	8.81
t	0.98	0.95	0.97	1.07	0.97	0.95	0.9	0.85
d	4.95	4.26	3.81	3.42	3.05	2.67	2.19	1.59
I	3.18	3.25	3.28	3.27	3.18	3.26	3.13	3.04
i=10000
T	9.02
t	1.01	0.99	1.03	1.01	1.01	1.02	0.97	0.91
d	4.98	4.28	3.81	3.43	3.07	2.68	2.23	1.64
I	3.28	3.36	3.41	3.43	3.39	3.33	3.18	3.08
n=10
i=100
T	25.96
t	2.27	2.42	2.5	2.6	2.48	2.5	2.16	2.21	2.67	1.91
d	5.03	4.43	3.97	3.64	3.28	2.98	2.59	2.14	1.69	1.27
I	4.77	4.42	5.29	4.48	4.99	4.8	4.15	5.09	4.88	4.74
i=1000
T	20.64
t	2	2.14	1.91	1.95	1.81	1.89	1.88	1.89	1.89	1.65
d	5.11	4.34	3.89	3.50	3.14	2.83	2.51	2.18	1.76	1.28
I	4.31	4.28	4.42	4.41	4.35	4.12	4.25	4.22	4.04	4.046
i=10000
T	19.04
t	1.86	1.83	1.78	1.83	1.79	1.76	1.76	1.75	1.63	1.6
d	5.12	4.36	3.87	3.49	3.15	2.82	2.49	2.14	1.74	1.29
I	4.20	4.33	4.32	4.30	4.30	4.26	4.21	4.16	4.03	3.99
n=15
i=100
T	102.62
t	8.63	8.06	6.61	7.3	6.2	5.78	6.16	6.53	5.77	6.75	7.25	6.26	5.24	6.62
d	5.27	4.55	4.01	3.71	3.41	3.16	2.9	2.75	2.54	2.21	1.98	1.73	1.47	1.29
I	7.42	7.43	8.13	7.39	7.59	7.95	7.42	7.59	7.77	7.5	7.5	7.06	6.9	7.23
i=1000
T	71.68
t	5.15	4.79	4.72	5.16	5.04	4.68	4.49	4.51	4.99	4.39	4.43	4.22	4.08	4.21
d	5.34	4.53	4.08	3.71	3.39	3.11	2.85	2.60	2.37	2.13	1.88	1.61	1.36	1.17
I	6.37	6.38	6.50	6.37	6.52	6.47	6.24	6.40	6.36	6.43	6.14	6.06	5.91	5.56
n=20
i=100
T	191.73
t	10	9.3	9.5	8.7	10	8.9	9.3	8.8	8.8	10	10	9.4	9.1	8.6	10	9.1	9.4	8.2	9.2
d	5.5	4.6	4.2	3.8	3.6	3.4	3.1	2.9	2.7	2.5	2.4	2.2	2.1	1.8	1.6	1.4	1.2	1.1	1.1
I	9.3	9.2	9.5	9.6	9.6	10	8.8	9.8	9.6	9.4	9.5	9.1	9.2	9.4	9.4	8.7	8.1	9.1	9.5
i=1000
T	190.43
t	9.9	9.8	10.1	9.6	9.7	9.6	9.3	8.9	9.3	9.2	9.6	9.3	9.4	8.9	9.2	9.1	8.7	8.7	8.5
d	5.5	4.6	4.2	3.8	3.5	3.3	3.1	2.9	2.7	2.5	2.3	2.1	2.1	1.8	1.6	1.4	1.2	1.1	1.0
I	9.4	9.5	9.7	9.4	9.5	9.4	9.6	9.7	9.5	9.6	9.2	9.3	9.3	8.9	9.1	8.9	8.7	8.9	8.8
n=8
i=100
T	28.35
t	2.87	3.74	3.5	3.48	2.96	3.03	3.09	3.28
d	5.81	4.96	4.43	4.04	3.77	3.31	2.93	2.23
I	7.14	7.36	7.03	7.1	7.1	6.74	7.32	7.05
i=1000
T	28.43
t	3.57	3.27	3.36	3.45	3.48	3.16	3.44	3.02
d	5.68	5.06	4.59	4.20	3.84	3.47	3.01	2.30
I	7.34	7.99	7.97	7.77	7.70	7.73	7.53	7.18
i=10000
T	29.26
t	3.53	3.54	3.51	3.56	3.53	3.45	3.31	3.1
d	5.65	5.01	4.56	4.19	3.84	3.46	2.99	2.30
I	7.66	7.77	7.89	7.79	7.71	7.72	7.54	7.28
n=10
i=100
T	74.05
t	8.05	7.41	7.64	7.05	7.04	7.7	6.2	6.47	7.22	6.84
d	6.07	5.32	4.84	4.4	4.05	3.69	3.37	3.03	2.55	1.9
I	13.12	12.99	12.77	13.05	12.52	13.26	12.78	12.38	12.56	11.91
i=1000
T	83.87
t	8.6	8.84	8.66	8	8.4	8.16	7.8	8.11	7.56	7.56
d	6.17	5.39	4.88	4.51	4.16	3.81	3.46	3.06	2.59	1.94
I	14.19	14.02	14.11	14.21	14.08	14.13	14.01	13.97	13.29	13.03
i=10000
T	81.93
t	8.45	8.29	8.11	8.2	8.14	8.04	8.03	7.78	7.54	7.38
d	6.17	5.40	4.92	4.52	4.17	3.83	3.48	3.10	2.62	1.96
I	14.45	14.32	14.51	14.34	14.3	14.25	14.14	14.01	13.81	13.5
n=15
i=100
T	637.71
t	43.6	43.9	44.4	45.2	44	41.3	41.9	41.1	43.2	41.3	41.7	41.8	41.8	38.6	38.63
d	6.92	6.03	5.55	5.13	4.83	4.51	4.23	4.01	3.67	3.44	3.13	2.85	2.49	2.03	1.56
I	45.4	44.1	44.1	44.7	44.6	43.5	45.5	44	42.3	42.7	41.8	43.1	43.7	42.6	41.08
i=1000
T	601.15
t	42.9	41.3	40.3	41.1	39.9	40.5	39.6	40.3	39.4	39	38.1	38.5	38.3	38.7	38.1
d	6.89	6.03	5.53	5.14	4.79	4.5	4.23	3.95	3.68	3.41	3.11	2.8	2.46	2.06	1.5
I	43.9	43.7	43.4	43.6	43.1	43.1	43.2	42.9	42.7	42.5	42.1	41.4	41.4	41.2	40.5
n=20
i=100
T	2007.26
t	105	105	105	101	101	100	102	101	100	100	98	99	99	96	97	95	95	96	98	97
d	7.6	6.4	5.9	5.5	5.2	4.9	4.6	4.3	4.1	3.9	3.7	3.5	3.2	3.1	2.9	2.6	2.4	2.2	1.8	1.3
I	88	87	88	86	88	87	89	88	87	88	86	88	86	87	85	85	84	84	82	86

Таблица 3.2. Результаты вычислительных экспериментов по построению генерированных графов с плотностью 2•n, где n- число вершин

n=8
i=100
T	83.82
t	10.99	9.49	9.78	9.04	10.43	10.62	10.12	10.64
d	6.6	6.17	5.86	5.54	5.19	4.87	4.41	3.72
I	19.52	20.39	20.72	19.98	19.56	19.5	19.85	19
n=10
i=100
T	531.98
t	55.36	54.14	52.97	53.46	53.44	53.38	53.54	52.69	50.97	48.15
d	8.3	7.84	7.48	7.12	6.85	6.57	6.22	5.88	5.41	4.65
I	75.22	74.85	76.68	74.83	76.72	78.19	77.89	76.44	74.87	73.36
n=15
i=100
T	8306.1
t	556	553	562	564	566	556	549	549	556	543	546	551	544	540
d	12.4	11.9	11.5	11.1	10.9	10.6	10.3	10.0	9.8	9.5	9.2	8.8	8.3	7.8
I	619	616	618	608	627	611	613	611	604	604	601	600	598	599
n=20
i=100
T	62773.16
t	3153	3141	3121	3157	3150	3160	3254	3160	3163	3098	3129	3167	3136	3089	3107	3103	3098	3068	3023	3018
d	16.6	15.9	15.5	15.1	14.8	14.5	14.2	13.9	13.7	13.4	13.3	13	12.8	12.5	12.2	12.1	11.7	11.3	10.6	9.7
I	2306	2302	2313	2304	2302	2294	2290	2290	2283	2286	2290	2275	2275	2285	2261	2269	2263	2272	2249	2249

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

Заключение

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

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

Список литературы

1. Di-Battista, G., P. Eades, R. Tamassia, and I. Tollis: 1999, Graph drawing - Algorithms for the visualization of graphs. Prentice Hall.

2. Sugiyama, K., S. Tagawa, and M. Toda: 1981, Methods for visual understanding of hierarchical systems. IEEE Trans. Syst., Man, Cybern. 11(2), 109-125.

3. Warfield, J.: 1977, Crossing theory and hierarchy mapping. IEEE Trans. Syst., Man, Cybern. 7(7), 505-523.

4. Carpano, M.: 1980, Automatic display of hierarchized graphs for computer aided decision analysis. IEEE Trans. Syst., Man, Cybern. 10(11), 705-715.

5. Purchase, H.: 2000, Effective information visualisation: a study of graph drawing aesthetics and algorithms. Interacting with computers 13(2).

6. Garey, M. and D. Johnson: 1983, Crossing number is NP-complete. J. Algebraic Discrete Methods 4(3), 312-316.

7. H. C. Purchase, Which aesthetic has the greatest effect on human understanding?, Proc. 5th Int. Sym. on Graph Drawing (GD'97), LNCS, vol. 1353, Springer-Verlag, 1997, pp. 248-261.

8. P. Eades and S. Whitesides, Drawing graphs in two layers, Theoretical Computer Science 131 (1994), 361-374.

9. X. Munoz, W. Unger, and I. Vrt'o, One sided crossing minimization is np-hard for sparse graphs, Rev. Papers from 9th Int. Sym. on Graph Drawing (GD'01), LNCS, vol. 2265, Springer-Verlag, 2002, pp. 115-122.

10. Michael Kaufmann and Dorothea Wagner, Drawing graphs: Methods and models, LNCS, vol. 2025, Springer-Verlag, London, UK, 2001.

11. C. Bachmaier, F. J. Brandenburg, W. Brunner, and F. Hьbner, Global k-level crossing reduction, JGAA 15 (2011), no. 5, 631-659.

12. P. Eades and D. Kelly, Heuristics for reducing crossings in 2-layered networks, Ars Combinatorica 21 (1986), no. A, 89-98.

13. M. Jьnger and P. Mutzel, 2-layer straightline crossing minimization: performance of exact and heuristic algorithms, JGAA 1 (1997), 1-25.

14. Alaa A. K. Ismaeel: 2012, Dynamic Hierarchical Graph Drawing.

Приложение

Ниже представлено описаниекода в файле sigma.parser.json с добавленными функциями для минимизации пересечений ребер и генерирование графа.

;(function (undefined) {

'use strict';

if (typeof sigma === 'undefined')

throw 'sigma is not declared';

// Initialize package:

sigma.utils.pkg('sigma.parsers');

sigma.utils.pkg('sigma.utils');

/**

* Just an XmlHttpRequest polyfill for different IE versions.

*

* @return {*} The XHR like object.

*/

sigma.utils.xhr = function () {

if (window.XMLHttpRequest)

return new XMLHttpRequest();

var names, i;

if (window.ActiveXObject) {

names = [

'Msxml2.XMLHTTP.6.0',

'Msxml2.XMLHTTP.3.0',

'Msxml2.XMLHTTP',

'Microsoft.XMLHTTP'

];

for (i in names)

try {

return new ActiveXObject(names[i]);

} catch (e) {

}

}

return null;

};

/*** INIT VARIABLES ***/

var adjList = [],

fullAdjList = [],

numOfOutgoingRibs = [], //число выходящих ребер из каждой вершины

sortedNodeOnNumOfOutgoingRibs = [], //последовательность вершин от большего к меньшему числу выходящих ребер

lastLevel = 0; // for dfsSetX()

var rootNode,

needRemoveIdEdges = [],

fictNodes = [],

fictEdges = [],

isMergeFictNodes = false,

newIdE = 0,

newIdN = 0,

wasDoneFictEdgesFromTo = [];//for dfsWithAddedFictNode()

var edgesForRemove = [],

edgesOnEveryLevels = [],

intersectionsOnEveryLevels = [],

countIFromVertex = [];

varmapNodeById = newMap(),

resultsTimeAllMinimize = 0,//среднее число миллисекунд выполнения всего кода начиная от создания рандомного графа

resultsTimeMinimize = [],//среднее число микросекунд выполнения операции минимизации пересечений ребер

resultsNumOfOut = [],//среднее число выходящих ребер из каждой вершины, проходясь по отсортированному массиву

resultsMinCount = [],//среднее число пересечений начиная с каждой вершины, проходясь по отсортированному массиву

N = 20; //countNodes

function clearVariables() {

adjList = [];

lastLevel = 0;

needRemoveIdEdges = [];

fictNodes = [];

fictEdges = [];

isMergeFictNodes = false;

newIdE = 0;

newIdN = 0;

wasDoneFictEdgesFromTo = [];

edgesForRemove = [];

edgesOnEveryLevels = [];

intersectionsOnEveryLevels = [];

mapNodeById = new Map();

}

function addNewNode(id, newNodes) {

if (newNodes.filter(function(node){return node.id === id.toString()}).length === 0) {

let newN = {};

newN.label = id.toString();

newN.x = 0;

newN.y = 0;

newN.id = id.toString();

newN.color = "#422892";

newN.size = 8;

newNodes.push(newN);

}

return newNodes;

}

function setMapID(graph) {

for (let i = 0; i < graph.nodes.length; i++) {

mapNodeById.set(graph.nodes[i].id, i);

}

}

function getNodeIndexFromId(id) {

return mapNodeById.get(id) != undefined ? mapNodeById.get(id) : id;

}

function toSortNodes(graph) {

setMapID(graph);

let copyNodes = graph.nodes.slice();

for (let i = 0; i < graph.nodes.length; i++) {

graph.nodes[i] = copyNodes[getNodeIndexFromId(i.toString())];

}

}

function getRandomGraph() {

let newGraph = {},

newNodes = [],

newEdges = [],

n = N, //countNodes

maxEdges = n*(n-1)/2,

pToHaveEdge = (n+5)/maxEdges,

//pToHaveEdge = 2*n/maxEdges,

//pToHaveEdge = (n*n/3)/maxEdges,

newEId = 0,

countAddedE;

for (let i=0; i<n-1; i++) {

newNodes = addNewNode(i, newNodes);

countAddedE = 0;

for (let j=i+1; j<n; j++) {

let randProbability = Math.random();

if (randProbability < pToHaveEdge) {

let newE = {};

newE.source = i.toString();

newE.target = j.toString();

newE.id = newEId.toString();

newEId++;

countAddedE++;

newEdges.push(newE);

newNodes = addNewNode(j, newNodes);

}

}

if (countAddedE === 0) {

let wasAddedEdge = false;

for (let z=0; z<newEdges.length; z++) {

if (newEdges[z].source == i || newEdges[z].target == i) {

wasAddedEdge = true;

break;

}

}

if (!wasAddedEdge) {

let newE = {};

newE.source = i.toString();

if (i < n-2)

newE.target = (i+1).toString();

else

newE.target = (i-1).toString();

newE.id = newEId.toString();

newEId++;

newEdges.push(newE);

}

}

}

newGraph.edges = newEdges;

newGraph.nodes = newNodes;

return newGraph;

}

function setFullAdjacencyList(graph) {

for (let i in graph.nodes) {

fullAdjList.push([]);

}

graph.edges.forEach(function (edge) {

fullAdjList[parseInt(edge.source)].push(parseInt(edge.target));

fullAdjList[parseInt(edge.target)].push(parseInt(edge.source));

});

}

function setNumbersOfOutgoingRibs() {

fullAdjList.forEach(function (eachAdjList, i) {

numOfOutgoingRibs[i] = eachAdjList.length;

});

var fullAdjListForRemove = numOfOutgoingRibs.slice();//tmp array

for (let i=0; i<numOfOutgoingRibs.length; i++) {

let maxNum = fullAdjListForRemove[0];

let maxNumI = 0;

for (let j=0; j<fullAdjListForRemove.length; j++) {

if (fullAdjListForRemove[j] > maxNum) {

maxNum = fullAdjListForRemove[j];

maxNumI = j;

}

}

sortedNodeOnNumOfOutgoingRibs.push(maxNumI);

fullAdjListForRemove[maxNumI] = -1;

}

}

function setNewAdjacencyList(graph) {

adjList = [];

for (let i in graph.nodes) {

adjList.push([]);

wasDoneFictEdgesFromTo.push([]);

graph.nodes[i].was = 0;

}

graph.nodes[rootNode.id].was = 1;

dfsForNewAdjList(graph, rootNode.id);

}

function dfsForNewAdjList(graph, ind) {

fullAdjList[ind].forEach(function (adjIndNode) {

if (!adjList[ind].includes(adjIndNode)) {

if (graph.nodes[adjIndNode].was > 0) {

if (!adjList[adjIndNode].includes(ind))

adjList[adjIndNode].push(ind);

}

else {

adjList[ind].push(adjIndNode);

graph.nodes[adjIndNode].was = 1;

dfsForNewAdjList(graph, adjIndNode);

}

}

})

}

function setXYRandom(graph) {

graph.nodes.forEach(function (node, i, arr) {

node.x = Math.random();

node.y = -1;

node.was = 0;

});

}

function setX(graph) {

//rootNode.x = 0;

//graph.nodes[rootNode.id].x = 0;

graph.nodes[rootNode.id].x = 0;

graph.nodes[rootNode.id].was = 1;

if (graph.nodes[rootNode.id].was > 0) {

graph.edges = [];

dfsSetXandUpdateEdges(graph, rootNode.id, 0);

newIdE = 0;

}

else

dfsSetX(graph, rootNode.id);

}

function dfsSetX(graph, ind) {

adjList[ind].forEach(function (adjIndNode) {

if (graph.nodes[adjIndNode].x < graph.nodes[ind].x + 1) {

graph.nodes[adjIndNode].x = graph.nodes[ind].x + 1;

if (graph.nodes[adjIndNode].x > lastLevel)

lastLevel = graph.nodes[adjIndNode].x;

dfsSetX(graph, adjIndNode);

}

})

}

function dfsSetXandUpdateEdges(graph, ind) {

adjList[ind].forEach(function (adjIndNode) {

if (graph.nodes[adjIndNode].x < graph.nodes[ind].x + 1) {

graph.nodes[adjIndNode].x = graph.nodes[ind].x + 1;

if (graph.nodes[adjIndNode].x > lastLevel)

lastLevel = graph.nodes[adjIndNode].x;

let edge = {};

edge.source = ind.toString();

edge.target = adjIndNode.toString();

edge.id = newIdE.toString();

newIdE++;

graph.edges.push(edge);

dfsSetXandUpdateEdges(graph, adjIndNode);

}

else {

let edge = {};

edge.source = ind.toString();

edge.target = adjIndNode.toString();

edge.id = newIdE.toString();

newIdE++;

graph.edges.push(edge);

}

})

}

function getYLevels(graph) {

var YLevels = [];

var countLevels = 0;

for (let i = 0; i < graph.nodes.length; i++) {

if (countLevels < graph.nodes[i].x)

countLevels = graph.nodes[i].x;

}

for (let i = 0; i < countLevels + 1; i++) {

YLevels[i] = 0;

}

return YLevels;

}

function addFictitiousNodes(graph) {

var graphWithFictitiousNodes = {};

var tmpNodes = [];

for (let i = 0; i < graph.nodes.length; i++) {

tmpNodes.push(graph.nodes[i]);

}

var tmpEdges = [];

for (let i = 0; i < graph.edges.length; i++) {

tmpEdges.push(graph.edges[i]);

}

graphWithFictitiousNodes.nodes = tmpNodes;

graphWithFictitiousNodes.edges = tmpEdges;

var ind = rootNode.id;

newIdE = graph.edges.length;

newIdN = graph.nodes.length;

var YLevels = getYLevels(graph);

graph.nodes[rootNode.id].y = 0;//for root node set y=0

dfsWithAddedFictNode(graph, ind, graphWithFictitiousNodes, YLevels);

return graphWithFictitiousNodes;

}

function dfsWithAddedFictNode(graph, ind, graphWithFictitiousNodes, YLevels) {

adjList[ind].forEach(function (adjIndNode) {

if (graph.nodes[adjIndNode].x - graph.nodes[ind].x > 1 && !wasDoneFictEdgesFromTo[graph.nodes[ind].id].includes(parseInt(graph.nodes[adjIndNode].id))) {

wasDoneFictEdgesFromTo[graph.nodes[ind].id].push(parseInt(graph.nodes[adjIndNode].id));

var removeEdge = {};

removeEdge.source = ind.toString();

removeEdge.target = adjIndNode.toString();

needRemoveIdEdges.push(removeEdge);

var from = ind;

var to = newIdN;

var toAddNode = true;

for (var i = graph.nodes[ind].x; i < graph.nodes[adjIndNode].x; i++) {

if (i == (graph.nodes[adjIndNode].x - 1)) {

var newEdge = {};

newEdge.source = from.toString();

newEdge.target = graph.nodes[adjIndNode].id;

newEdge.id = newIdE.toString();

graphWithFictitiousNodes.edges.push(newEdge);

fictEdges.push(newEdge);

from = newIdN;

to = newIdN + 1;

newIdE++;

}

else {

var isYetFN = false;

var isYetFE = false;

var yetFictNode;

fictNodes.forEach((function (fictnode, ind) {

if (fictnode.x == i + 1) {

isYetFN = true;

yetFictNode = fictnode;

}

}));

if (isMergeFictNodes && isYetFN) {

fictEdges.forEach(function (fictedge, ind) {

if (fictedge.source == from && fictedge.target == yetFictNode.id) {

isYetFE = true;

}

});

if (isYetFE) {

from = yetFictNode.id;

to = newIdN;

}

else {

var newEdge = {};

newEdge.source = from.toString();

newEdge.target = yetFictNode.id;

newEdge.id = newIdE.toString();

graphWithFictitiousNodes.edges.push(newEdge);

fictEdges.push(newEdge);

from = yetFictNode.id;

to = newIdN;

newIdE++;

}

}

else {

var newNode = {};

//{"label":"0","x":0,"y":0,"id":"0","color":"#422892","size":8}

newNode.label = newIdN.toString();

newNode.x = i + 1;

newNode.y = YLevels[newNode.x];

YLevels[newNode.x]++;

newNode.id = newIdN.toString();

//newNode.color = "#00BCD4";

newNode.color = "#422892";

newNode.size = 4;

var newEdge = {};

//{"source":"4","target":"3","id":"1"},

newEdge.source = from.toString();