Digs - Персональная территория

Авторский проект Артема Глазкова
? 
        Версия для печати (цвет)  

Алгоритмы
» Раскраска текста
» Радиальная раскладка графа
» Генерация случайных графов
» Сбалансированное дерево

Использование материалов
Заметка #22
25 октября 2006

Радиальная раскладка графа


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

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

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

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

    2. Если граф не связный, его нужно разбить на связные части и делать построение для каждой части отдельно.

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

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

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

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

    Основная структура, с которой придется работать, это список секторов. Секторы в этом списке будут упорядочены по углу. Т.е. они будут располагаться в той последовательности, в которой они представлены на круге при его обходе в каком-либо направлении. При этом два рядом стоящие сектора будут всегда иметь один общий луч-границу, никакие сектора не будут пересекаться между собой, а общая сумма всех секторов равна 360°. Если для центрального узла нет цикла, то изначально сектор будет один, и будет занимать пространство от 0 до 360°.

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

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

  R := Sqrt(0.5/(1-cos(2*pi/N)));

    где N количество ребер в цикле.

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

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

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

    При увеличении сектора нужно помнить об ограничении угла сверху. Если из текущего узла, будет развернут «веер» ребер, с общим углом секторов более 180°, то есть вероятность, что будут пересечены ребра подходящие к узлам на этой же окружности. 180° это касательная к текущей окружности. Точка пересечения касательной со следующей окружностью (радиус на единицу больше) соединенная с общим центром образуют гипотенузу прямоугольного треугольника. Следовательно, максимальный угол для сектора будет равен 2*arccos(R/(R+1)), где R это текущий радиус.

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

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

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

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

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

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

    Вот интерфейс процедуры вычисляющей внешние связи:

procedure UpdateRLDist(Childs, Neigh: TList; IsLeft: boolean);

    Здесь Childs список исходящих узлов, для которых нужно посчитать длину связей, Neigh список соседних узлов либо справа, либо слева, IsLeft указывает, список каких именно соседей задали. Каждый узел имеет два поля, которые содержат длину минимальных связей для правых и левых соседей. Таким образом, чтобы найти все связи нужно создать списки правых и левых соседей и дважды вызвать UpdateRLDist.

    После сортировки исходящих, они выстроятся в три группы. Сначала (справа налево) будут исходящие, имеющие более значительные внешние связи с правыми соседями, затем не имеющие внешних связей, и в конце, имеющие более значительные внешние связи с левыми соседями. Что значит более значительные? Для каждого узла вычисляется минимальная длина связи с правыми и левыми соседями. К каким соседям узел оказывается ближе, в ту группу его и заносим. Но другую связь (более длинное расстояние) также не следует игнорировать. Если, к примеру, у двух узлов будет одинаковая правая связь, но один из них будет иметь более лучшую левую связь, то такой узел лучше поставить левее, так как в будущем он даст соединение, которое вероятнее даст меньше пересечений, чем если бы его поставили правее.

     Каждая группа также является не беспорядочной: здесь тоже есть свои приоритеты расположения. Для групп с внешними связями важна длина связей. Связь, имеющая меньшую длину, является более привилегированной: чем меньше длина, тем быстрее произойдет соединение, и тем меньше вероятность пересечения других ребер. На рисунке слева приведен именно такой случай. Для родительских узлов у.36 и у.24 короткие внешние связи будут для узлов у.2 и у.6. На следующем же этапе они соединятся, и поэтому соединение у.12 и у.52 ничего не пересекает. Если бы мы определили дальние связи как более важные, тогда порядок следования узлов был бы другим, и мы получили бы сразу два пересечения.

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

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

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

function SortValue(L,R : Integer) : Double;
begin
  //значение -1 означает отсутствие связи
  if L=-1 then L := MaxValue;
  if R=-1 then R := MaxValue;
  if L=R then Result := 0
  else
  if L<R then Result := -((MaxValue + 1 - L) + (MaxValue - R)/MaxValue)
  else Result := (MaxValue + 1 - R ) + (MaxValue - L)/MaxValue;
end;

    Здесь L и R, соответственно, минимальные левая и правая связи, MaxValue это максимально возможное значение связи, в качестве которого можно взять максимальный радиус построения.

    Внутренние связи и без связей
    Теперь поговорим о группе исходящих, не имеющих внешних связей.

    Первым шагом нужно выделить из этой группы те исходящие, которые имеют внутреннюю связь с уже расставленными узлами. Мы можем воспользоваться процедурой UpdateRLDist для нахождения этих связей. Для этого уже сформированный список (назовем его GlobalKnots) разобьем на две части по знаку значения SortValue. Те узлы, которые имеют отрицательный SortValue, будем считать левыми, оставшиеся – правыми. Как и в случае с внешними связями делаем два вызова (для каждого списка) и тем самым, получаем для каждого нового узла длины левой и правой связи. Собрав все узлы, у которых присутствует хотя бы одна связь, мы помещаем их в новый список (LocalKnots), заранее отсортировав по SortValue. Так как для новых найденных узлов могут существовать связи с другими, не посчитанными узлами, нужно повторить эти действия, дополнив списки правых и левых узлов узлами из нового списка. И так до тех пор, пока будут находиться узлы с ненулевыми связями.

    После того, как список сформирован, перемещаем его в GlobalKnots как одно целое со значением SortValue = 0. Тут важным моментом будет запомнить, куда легла середина этого участка. В смысле, где пролегает граница между отрицательными и положительными SortValue. В дальнейшем в эту точку мы переместим все оставшиеся узлы.

    Теперь будем действовать следующим образом. Заведем пустой список, и будем перемещать в него узлы. Алгоритм перемещения следующий:
    1. Добавляем в новый список любой узел и запоминаем его позицию.
    2. Для каждого узла исходного списка ищем связь с каким-либо узлом нового списка. Если связь есть, то такой узел так же перемещаем, если такой узел не найден, то переходим к п.1.
    3. Перемещение происходит не в конец списка, а к узлу, с которым найдена связь. При этом учитываем связи последнего в другими в этом же списке. Если связь только с одним узлом, то просто добавляем после этого узла. Если же есть еще связь и с соседним узлом, то вставляем исходя из оценки расстояний между всеми узлами. Это проще продемонстрировать кодом.

procedure Insp(List : TKnots;p1,p2 : Integer;Item: TKnot);
begin
  if KDist(List[p1],List[p2])>KDist(List[p1],Item) then List.Insert(p2,Item)
    else if KDist(List[p1],Item)<KDist(List[p2],Item) then List.Insert(p1,Item)
      else List.Insert(p2+1,Item);
end;

    Здесь:
    KDist – функция вычисление расстояния между узлами
    List – список, куда помещаем узел
    p1,p2 – индексы двух подряд идущих узлов списка List, с которыми есть связь у добавляемого
    Item – добавляемый узел

    Вот собственно и все.

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

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


© 2005-16, Powered By Digs (Написать письмо, vk)