Содержание к диссертации
Введение
Глава I, Многокритериальная постановка задачи размещения ациклических графов на плоскости 29
1.1, Описание задачи размещения ациклических графов на плоскости 29
12. Математическая модель задачи размещения ациклических графов на плоскости 42
Глава 2. Алгоритмы с оценками решения многокритериальной задачи размещения ациклического графа на плоскости 48
2.1, Алгоритм ах получения оптимального разбиения по критерию симметричного размещения графа 48
2.2, Алгоритм а2 получения оптимального разбиения по критерию совпадающего направления ребер 62
2.3, Алгоритм а, получения оптимального разбиения по критерию прямолинейности ребер 76
2.4, Алгоритмы размещения предфрактального графа, порожденного ациклической затравкой 87
Глава 3, Алгоритмы перемещения графических объектов графа на плоскости 93
Заключение 117
Список литературы
- Математическая модель задачи размещения ациклических графов на плоскости
- Алгоритм а2 получения оптимального разбиения по критерию совпадающего направления ребер
- Алгоритм а, получения оптимального разбиения по критерию прямолинейности ребер
- Алгоритмы размещения предфрактального графа, порожденного ациклической затравкой
Введение к работе
В настоящее время графовое представление информации все больше и больше используется в различных областях точных и естественных наук. В программировании графовые модели применяются при создании программного обеспечения (управляющие графы, иерархии классов, диаграммы потоков данных), дизайне баз данных (диаграммы сущностей-связей), разработке информационных систем и систем реального времени (модели компьютерных сетей, графы состояний, сети Петри), а также в системном программировании - при создании теории компиляции и преобразования программ. Вопрос визуализации подобных графовых структур является краеугольным камнем в процессе адекватного отображения информации [21].
Автоматическое размещение графов - это задача конструирования геометрического представления графа, удовлетворяющего набору эстетических критериев. В последние пятнадцать лет эта проблема подвергается интенсивному изучению. Было опубликовано большое количество работ по рисованию графов, а с 1993 года проводятся ежегодные конференции по данной тематике [21].
В диссертационной работе впервые сделана многокритериальная математическая постановка задачи о размещении ациклических графов на плоскости, а также разработаны и математически сформулированы алгоритмы с оценками величин получаемых оптимизационных критериев задач размещения ациклических графов на плоскости, чтобы в конечном итоге решить практическую задачу построения объектно-ориентированной модели программного комплекса, и разработан, а также зарегистрирован программный комплекс GraphDravvingAB [26].
В работе на примере многокритериальной задачи размещения ациклических графов на плоскости продемонстрирована связь и переход от математической модели к исследованию многокритериальной задачи, сформулированной при построении модели [26].
Цели работы
Построение и исследование математической модели реализации крупного научно-исследовательского проекта, состоящего в представлении объектно-ориентированной модели крупного программного комплекса, с последующим ее сведением к многокритериальной задаче размещения ациклических графов на плоскости.
Исследование свойств ациклических графов, возникающих в многокритериальной задаче их размещения на плоскости.
Построение алгоритмов нахождения решения поставленной задачи с оценкой их сложности и оценкой оптимизируемых критериев.
Программная реализация полученных алгоритмов, а также создание алгоритмов корректного перемещения графических объектов графа на плоскости с тем, чтобы вручную изменить величины оптимизируемых критериев. Создание алгоритмов изменения атрибутов графических объектов с тем, чтобы упростить процесс визуального восприятия изображения.
Методы исследования
Все исследования, проведенные в работе, используют методы и подходы дискретной математики и теории графов в частности. Аппарат теории графов наилучшим образом подходит для формального представления задач, связанных с изменением и преобразованием дискретных объектов, какими являются структуры систем [36].
Научная новизна
Построение многокритериальной задачи о размещении ациклических графов. Исследование этой задачи в применении к проблеме представления па плоскости объектно-ориентированной модели крупного программного комплекса.
Улучшение временной трудоемкости известных алгоритмов для нахождения решения классической задачи размещения ациклических графов на плоскости, построение новых алгоритмов.
Теоретическая значимость работы
Рассмотренные в работе математические модели, методы многокритериальной оптимизации, алгоритмы построения размещения ацикличесїаїх графов на плоскости с оценками расширяют и дополняют существующие разработки в дан-нон области, что подтверждает теоретическою значимость работы. Практическая ценность
Практическая ценность результатов работы определяется возможностью их применения при создании программных комплексов с применением объектно-ориентированного подхода, Построена математическая модель реализации научно-исследовательских проектов. Все исследованные алгоритмы в случае ре&іиза-ции способны повысить эффективность рассматриваемой системы. Положения, выносимые па защиту
К Математическая модель многокритериальной постановки размещения ациклических графов на плоскости.
2. Алгоритм #, получения оптимального разбиения по критерию симметричного размещения графа.
3. Алгоритм а, получения оптимального разбиения по критерию совпадающего направления ребер.
4. Алгоритм ЙЯ получения оптимального разбиения по критерию прямолинейности ребер.
5. Алгоритмы размещения предфрактального графа порожденного ациклической затравкой,
6. Алгоритмі»! перемещения графических объектов графа на плоскости. Апрпбацни работы
Основные результаты работы докладывались на следующих научно-технических конференциях: V Международной научно-практической конференции «Компьютерные технологии в науке, производстве, социальных и экономических процессах». Новочеркасск, 2004; I Международной научно-технической конференции «Инфотелекоммуиикационныс технологии в науке, производстве и образовании». Ставрополь, 2004; Международной научно-технической конференции «Информационно-вычислительные технологии и их применение». Пенза, 2005. III Международной научно-практической конференции «Теория, методы проектирования, программно-техническая платформа информационных систем». Новочеркасск, 2005, VII Международной научно-практической конференции «Информационная безопасность», Таганрог, 2005. II Международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности». Санкг Петербург, 2006.
Личный вклад автора
Обосновано применение ациклических графов для представления объектно-орнентированной модели программного комплекса.
Разработаны алгоритмы с оценками и программный комплекс Grapli Drawing АВ получения оптимального размещения ациклического графа по различным критериям оптимальности.
Разработаны алгоритмы и программный комплекс Graph Dra wing АВ корректного перемещения графических объектов графа по плоскости изображения.
В перішії главе диссертации описана многокритериальная постановка задачи размещения ациклических графов на плоскости. Приведены и математически формализованы эстетические критерии, которые принимаются при размещении ациклических графов. Описано, почему объектно-ориентированная модель крупного программного комплекса может быть представлена в виде ациклического графа, Первая глава состоит из пунктов:
• описание задачи размещения ациклических графой на плоскости;
• математическая модель задачи размещения ациклических графов на плоскости.
Во второй главе диссертации приведешь алгоритмы решения многокритериальной задачи размещения ациклических графов на плоскости:
• алгоритм а, получения оптимального разбиения по критерию симметричного размещения графа;
• алгоритм аг получения оптимального разбиения по критерию совпадающего направления ребер;
• алгоритм аъ получения оптимального разбиения по критерию прямолинейности ребер;
• алгоритмы размещения предфракталыюго графа порожденного ациклической затравкой.
В третьей главе диссертации описаны алгоритмы перемещения графических объектов графа на плоскости:
• обработка процедуры OnLBDown(CPoint point);
• обработка процедуры GnMouscMove(CPoint point);
• обработка процедуры OnLBlJp(CPoini point, inl &size).
Далее мы сконцентрируем свое внимание на изображении ациклических орграфов (дэгов). Выбор этого подкласса для рисования можно объяснить двумя причинами. Во-первых, преимущественное большинство реальных графов, встречающихся в программировании, являются ациклическими, а во-вторых, любой ориентированный (и тем более неориентированный) граф может быть преобразован в ациклический орграф путем смены или задания ориентации у части его ребер [29,35],
Наиболее известный подход к размещению ациклических орграфов является обобщением стандартного подхода, используемого для размещения деревьев. Для подчеркивания иерархичїіости структуры дога при его укладке строятся, как и в древесном случае, иоуровневые представления, у которых ьсе дуги графа имеют одно и то же направление- Такие представления называются монотонными поуровиевыми представлениями [36,16],
Отличительной чертой методологии поуровпепого представления является ее интуитивная понятность и масштабируемость. Под масштабируемостью мы здесь пониманием разделение методологии на ряд малопересскающихся задач. Любая конкретная реализация это всегда конструктор, то есть набор методов, решающих задачи разных этапов. Собирая такой конструктор, исследователь должен выбрать сбалансированный набор методов. Такой набор должен быть непротиворечивым по целям и эквивалентным в терминах временной сложности.
Если в набор входит алгоритм, имеющий квадратичную сложность, іо нет смысла экономить на решении задач других этапов, применяя к ним линейные, но плохие эвристики [14].
Методы, основанные на поуровневом размещении (иерархический подход), хотя и не являются лидерами по всем эстетическим критериям, однако значительно опережают конкурентов па больших графах, возникших в реальных приложениях [10,30].
В главе 1 описана задача многокритериальной оптимизации размещения ациклических графов. Но одновременная оптимизация всех перечисленных критериев является невозможной потому, что эти критерии зачастую оказываются противоречащими друг другу. Так, например, условие прямолинейности ребер нарушает равномерность распределения вершин и увеличивает общую площадь изображения [48,26].
Существуют несколько различных техник размещения ациклических графов, каждая из которых ставит во главу угла один или несколько из перечисленных эстетических критериев и старается в меру возможностей удовлетворить оставшиеся критерии [28.31].
Например, можно решать задачу размещения ациклических графов сведением их к пленарному графу и дальнейшему построению выпуклого изображения, используя особенности топологии пленарных графов, с последующим восстановлением изначальной структуры. Так, например, хорошо изучена задача построения выпуклого изображения для планарных ациклических st -графов, то есть графов, имеющих одну входную и одну выходную вершины, а также планарную укладку, в которой дуга, соединяющая эти нершины, лежит во внешней грани. Они допускают монотонное изображение с прямолинейными ребрами, внешняя грань которого есть заданный треугольник. Изображение в этом случае строится рекурсивно, путем выделения специальным образом st -подграфов с меньшим множеством вершин, чем у исходного, и применения алгоритма к ним. При таком подходе, когда фиксируется внешняя грань и дуги изображены прямыми линиями, с возрастанием степеней вершин углы между смежными ребрами быстро умень шаются, что сильно понижает читаемость изображения. Существует общий метод сведения произвольного планарного ациклического графа к si -графу с сохранением планарности, однако само требование планарности исходного графа является слишком жестким. С одной стороны, задача удаления минимального количества ребер произвольного ациклического графа так, чтобы сделать граф нлапариым, является Л / трудной, а с другой - не слишком подходит нашим целям, поскольку нарушает саму структуру исходного графа [21,29].
Задачу автоматического размещения ациклических графой можно также решать с помощью ортогональных техник, которые широко используются для графов произвольного вида и имеют хорошие временные показатели. Основным недостатком данного подхода является то, что теряется возможность отражения иерархичности графа, к тому же размещения, полученные с использованием ортогонального подхода, более разряжены, чем, например, плоские размещения, и соответственно имеют большую площадь, что понижает удобность изучения структуры ірафа. Следует отметить также, что при ортогональном подходе при изображении орграфов степени вершин более 4-х возникает проблема с появлением существенного разброса в размерах вершин. Дело в том, что у вершины для размещения инцидентных ей ребер, число которых превышает 4, требуется увеличить размер изображения, что может привести к одновременному наличию и слишком больших, и совсем маленьких вершин [21],
Для построения изображения дэгов наиболее широко применяется так называемый иерархический подход, который направлен на получение их поуровне-вого размещения. Данный подход является крайне интуитивным и позволяет для произвольного ациклического орграфа построить монотонное поуровневое представление с ребрами в виде ломаных или сплайнов в процессе последовательного решения следующих трех задач:
распределение вершин по уровням так, чтобы все дуги следовали одному направлению [21{;
выбор порядка вершин на уровне с целью минимизации пересечений ребер [21];
определение координат вершин на уровне с целью минимизации общей длины ребер и количества изломов [28].
Таким образом, данный подход позволяет разбить задачу нахождения расположения ациклического ірафа на три достаточно независимых шага, реализация которых опирается на свои методы и использует различные эстетические критерии [29],
Дія успешного применения иерархического подхода система изображения графов (исходные данные, визуализирующая компонента, область применения) должна удовлетворять следующим ограничениям:
исходный граф должен быть ациклическим мультиграфом или мультиграфом, близким к ациклическому. Близость здесь следует понимать в том смысле, что смена ориентации малого количества дуг должна превратить граф в ациклический 21];
семантика графовой информации должна предполагать возможность построения монотонного изображения, подчерки вакшеего направленность или наличие некоторого порядка на множестве вершин [21];
система визуализации не должна предполагать проведение только прямолинейных ребер между вершинами графа. Ребра должны быть изображены в виде ломаных или сплайнов [48,14].
Канонически метод поуровнеіюго изображения состоит из трех последовательно применяющихся шагов;
распределение вершин по уровням. Каждой вершине и присваивается число Л(ІГ), указывающее уровень этой вершины, так, чтобы все дуги, соединяющие вершины, следовали от меньшего номера к большему, при этом вершины одного уровня не должны быть связаны между собой. Подразумевается, что все вершины одного уровня будут расположены на одной прямой - вертикальной или горизонтальной, - в зависимости от того, какое мы предпочитаем общее направление размещения: сверху вниз или слева направо. После проведения распределения вершин по уровням просматриваются все дуги: если дуга с = (u,v) проходит через несколько уровней, то есть /.{;/)-Цг) 1, то она удаляется из графа и заменяется на цепочку фиктивных вершин rlv,JTvV3 каждая вершина у соединена дугой с гм1 и определение порядка вершин на уровне. Задача данного шага состоит в сортировке вершин на каждом из уровней. Порядок вершин определяет топологию конечного изображения и должен быть выбран с целью минимизации пересечений ребер графа [21 j;
определение координат вершин на урошю. На данном этапе каждой сер-шине присваивается вертикальная координата (при размещении в горизонтальном направлении) так, чтобы сохранить порядок вершин на уровне, который был вычислен на предыдущем шаге. Координата выбирается с целью минимизации общей длины ребер и количества изломов. Наконец, конечное изображение получается представлением каждого ребра в виде прямолинейного отрезка и удаления фиктивных вершин, В этом случае длинные ребра оказываются изображенными в виде ломанных [10,28].
Некоторые исследователи склонны выделять задачу проведения ребер в отдельный этап алгоритма. Это целесообразно делать, если ребра изображаются не каноническими ломаными а например сплайнами. Существуют эффективные методы проведения сплайнов, не пересекающих вершины графа и проходящих через заданные области плоскости [10,28].
Также задача проведения ребер выделяется в отдельный этап, если вершины графа имеют неточечное представление. При этом приходится следить за отсутствием пересечений ребер и вершин графа, а также определять точки на изображении вершины, в которые будут входить и выходить ребра, инцидентные этой вершине [30,35],
В случае, если исходный граф не является ациклическим, требуется отдельный шаг алгоритма, который отвечает за препроцессирование графа и преобразование его к ациклическому ориентированному графу- После построения изображения структура изначального графа восстанавливается [35].
Иерархический подход оказывается не очень удачным с точки зрения по-сгроения инкрементального размещения. Этот факт можно объяснить тем, что то пология получаемого изображения очень сильно зависит от выделенной на первом шаге алгоритма иерархии вершин. А даже при локальных изменениях графа, как-то: удаление или добавление вершин, групп вершин или ребер, - не удаеіся сохранись эту иерархию неизменной. Вопросы инкрементального размещения очень тесно переплетены с вопросами удовлетворения ограничений на получаемое изображение, В качестве ограничений, которые могут быть удовлетворены при таком подходе, можно назвать требование разместить две выделенные вершины с одного уровня иерархии как можно ближе друг к другу, а также выравнивание вертикальных координат вершин с разных уровней иерархии [10].
Математическая модель задачи размещения ациклических графов на плоскости
Пусть объектно-ориентированная модель некоторого программного комплекса Р представлена в виде ациклического графа (/ = (ї\) - В общем виде V \ -множество вершин графа G = (l\E)t \Е\ - множество ребер графа G = (V,E). Но в применении к практической задаче построения объектно-ориентированной модели программного комплекса /\ V \ - число классов v, с V программного комплекса /\ а \Е\ - число линий связей et є Л , которые характеризуют отношения простого наследования и множественного наследования в комплексе / . Если класс А наследует свои свойства от класса В, то ориентированное ребро ?, є Е проводится ог класса В по направлению к классу А, В данной задаче необходимо расположить ациклический граф программного комплекса Г на плоскости. Такое размещение обозначим х.
Пусть дан ациклический граф G = {t\E). Разделим множество V на элементы Л,,/,,,,,,,/ . Пусть u,veV, (м,г)є\ а также usLt и vsLn а также верно, что і j. Тогда элементы \LX} = {1 L,...,LA) будем называть уровнями разбиения множества Г. А само такое разбиение \1Х)будем называть поуровисвым разбиением множества Г, относящегося к некоторому размещению г. А множество таких размещений х назовем множеством допустимых решений X = X{G)-{x) (МДР). Применительно к задаче об объектно-ориентированном программировании, Лг (/ = 1, ,/,, eLx) есть подмножество множества V и представляет собой множество классов, находящиеся в подмножестве Ps.
Допустим, что при построении размещения х на графе G = (lrJC) выделена некоторая вершина г еГ, относительно которой производится размещение графи G на плоскости. Вершина v eV- зто один из классов, относящихся к проекту р. Проведем на плоскости через вершину у вертикальную линию а, которую назовем линией симметрии. Размещение х графа (J = (l\E) будем строить относительно линии симметрии а. Вершины v EF, = 1, будем располагать по обе стороны от линии а согласно уровням L L .J . При этом будем полагать, что размещение Л: будет симметричным, если число классов проекта / будет равным на уровнях Lf е LA, / = \,к слева и справа от линии и. Обозначим NXnj, NXti. - число вершин слева и справа отлипни симметрии а на уровне Л,.
При размещении вершин графа G = (VtE) необходимо оптимизировать критерий совпадающего направления ребер, отражающих отношения наследования между классами (вершинами графа). Для этого направление ребер может быть или восходящим, или нисходящим. Предположим, что иерархическая модель связей классов между собой в проекте Р должна быть восходящей. Для этого введем вектор /переменных Xkuf которые определяются по следующему правилу: и, а противном случае к = ]jtt9 где м- число ребер графа G формально выражает число и направление связей, отражающих отношение наследования в проекте Р; Ltl- номер уровня начала ребра ек, ct єА\ Lh є А,; /J)y- номер уровня конца ребра ct, е,. с/-;, Lh =Lx.
При представлении объектно-ориентированной модели проекта Ръ виде ациклического графа необходимо минимизировать площадь получаемого изобра 44 жепия Sx. Для этого необходимо минимизировать произведение \УХ-НХ Wr- ширина получаемого размещения л\ Wx определяется как максимальная величина из мощностей множеств ІЛУи,...уік, Wx =max{/J],t2v..,/ }. Hs- высота получаемого размещения х. Нх определяется по числу уровней в размещении х, Нх = /-.v Для повышения наглядности и простоты просмотра размещения л- необходимо, чтобы оно размещалось равномерно по площади изображения. Очевидно, что для этого необходимо, чтобы ширина получаемого размещения Wx была равна его высоте Нх.
При представлении крупного программного комплекса в виде объектно-ориентированной модели на плоскости графом велика вероятность получения не-планарного графа, то есть графа, который невозможно уложить на плоскости без пересечения линий связей. Поэтому речь идет о минимизации пересечений Пх линий связей на размещении х. Под пересечением ребер графа будем понимать случай, когда ребра имеют общую точку не в вершине графа. При представлении модели проекта Р в виде ациклического графа следует учитывать необходимость прямолинейности ребер. Если представить каждое ребро с. є Е графа О = (Г, Ат) в виде уравнения прямой, то очевидно, что все звенья этой прямой должны иметь один угловой коэффициент, или, иначе говоря, число сгибов прямой должно быть минимально. Рассмотрим ребро с, Е. Пусть это ребро состоит из / звеньев. Обозначим kls угловой коэффициент звена s ребра cs = Е\ -M.ir w- номера конечного и начального уровней звена s ребра ct є Л"; atKtJtatir номера конечной и начальной горизонтальной позиции звена л\ Пусіь ребро є Е состоит из к звеньев.
Алгоритм а2 получения оптимального разбиения по критерию совпадающего направления ребер
Рассмотрим ациклический граф G = (F,A )3 где К - число вершин, /;- число ребер. Примем, что критерий совпадающего направления ребер для получения оптимального разбиения является предпочтительным.
Будем предполагать, что исходный граф (7 = (Г,/:) является так называемым .st - .уюфолг7 то есть в нем имеется только одна начальная вершина, обозначаемая через $ и только одна конечная вершина, обозначаемая через /. Ясно, что любой дэг G = (1\К) может быть преобразован в s/ -граф добавлением фиктивных вершин s и , а также дуг (s,p) и (qj) для всех начальных вершин р и конечных вершин ц графа G. Изображение графа легко конструируется на основе его обзорного представления.
Обзорным представлением Г заданного st -графа G называется такое его изображение, в котором каждая вершина р представлена горизонтальным отрезком / (/ ), называемым вершинным отрезком, а каждая дуга {p,q)- вертикальным отрезком r(p,q)t называемым реберным отрезком, таким образом, что справедливы следующие три свойства: вершинные отрезки не накладываются друг на друга; реберные отрезки не накладываются друг на друга; реберный отрезок l\p,q) имеет нижнюю границу, лежащую на Г(р), и верхнюю границу, лежащую на Г(ц)9 и не пересекает ни один другой вершинный отрезок. Например, построим обзорное представление для ациклического графа Z (рис. 2,2),
Легко конструируется изображение А-/-графа G на основе его обзорного представления. Для этого каждая вершина графа G может быть представлена некоторой точкой соответствующего вершинного отрезка, а каждая дуга (/м/) графа С7- ломанной не более чем из трех звеньев, среднее звено которой образовано частью реберного отрезка, изображающего эту дугу (/v/) АЛГОРИТМ щ ВХОД: ациклический граф (J {V,E) ВЫХОД: оптимальное восходящее изображение С - {V,K) 1. Процедура MAXSUGRPAH, Выделить максимальный планарпый подграф G 1- (!",) графа G, rt V, Д с К, 2. Для каждой вершины v, veV цикле,. 3. Процедура ПОЛИЛИНЕЙНОЕ ИЗОБРАЖЕНИЕ. Получение изображения Д, /-1,г. 4. Анализ на оптиматьность изображения Д, / = Цу\. 5. Окончание цикла с}. 6. Окончание алгоритма а,. Процедура ПОЛИЛИНЕЙНОЕ ИЗОБРАЖЕНИЕ ВХОД: ациклический граф О = {У,К) ВЫХОД: изображение Д, і-і\У\ 1. Конструируется обзорное представление Г графа (7 с целочисленными координатами вершин, 2. Для каждой вершины v, VGV цикл с:. 3. Заменить вершинный отрезок Г(г) на произвольную точку /» = (л-(у), (г)) отрезка I\v), і. Окончание цикла с:. 5, Для каждого ребра (п,\ )єЕ цикл с3, 6, Если (v)-v(«) l т 7. % Короткое ребро %. Заменить реберный отрезок I (uyv) т отрезок с конечными вершинами Р(и) и (v), 8. Иначе % Длинное ребро %. Заменить реберный отрезок Г(и,у) на ломанную линию, соединяющую точку Р(п) с точкой P(v) через точки {xil\umv))ty{ii)+l) и (x(rOuv)ly(v)-\). 9. Окончание цикла сг Процедура MAXSUGRAPH ВХОД: ациклический граф G = (l\K). ВЫХОД: максимальный планарный подграф (? {У\ІЇ) графа G, 1п 1\ ]?я Е 1. Создастся начальный граф ; ={Г,0). Этот граф образуется из графа (} = (1-\К) путем представления всех смежных вершин в виде несмежных вершин. 2. Для каждого ребра G цикл с4. 3. Добавляется на каждом шаге по одному ребру из G\C/ без нарушения планарности до тех пор, пока не возникнет ситуация, когда нет ребра в G\G , добавление которого к С не нарушает свойство планарности G1. 4. Окончание цикла сА. Опишем подробнее алгоритм о,
Рассмотрим ациклический граф (7 (Г,)Ч где - число вершин, \Е\- число ребер. Будем предполагать, что исходный граф G = (Г,) является так называемым si-графом, то есть в нем имеется только одна начальная вершина, обозначаемая через л, и только одна конечная вершина, обозначаемая через t. Основная задача работы алгоритма а2 - получить восходящее изображение графа G,
Па первом этапе работы алгоритма а2 выделяется максимальный планарный подграф G ={V\K ) графа G, ГсГ, сА\ Известно множество алгоритмов выделения максимального планарного подграфа, и ранее уже установлено, что эта задача является NP-трудпой.
Мланарность графов не меняется при удалении петель и кратных ребер, при введении в разрыв ребра новых вершин с локальной степенью dcg(r,) = 2, при удалении этих вершин. Введение и удаление таких вершин называется соответственно операциями разбиения и стягивания ребер. Графы, которые получаются один из другого применением операций разбиения и стягивания, называются изоморфными с точностью до вершин степени 2.
Перед исследованием планарности графа для уменьшения размерности задачи целесообразно сначала выделить все компоненты связности и в каждой из них выполнить все перечисленные операции, которые па плапармость не влияют, но облегчают исследования. После этого задача сводится к исследованию на планарность каждого отдельного компонента связности.
Алгоритм а, получения оптимального разбиения по критерию прямолинейности ребер
Рассмотрим ациклический граф G = (V4E), где ]F - число вершин, /ь- число ребер. Примем, что критерий прямолинейности ребер для получения оптимального разбиения является предпочтительным.
Одним из очевидных вариантов укладки графа G на плоскость, в которой все ребра будут прямолинейны, без изломов, представляется размещение вершин графа G в вершины правильного м но гоу голы гика РТ. Число сторон этого многоугольника равно числу вершин графа (7. Задача сводится к упорядочиванию вершин G в вершинах РТ. Наиболее простой вариант - это расположение вершин о в вершинах РТ произвольно. Но данный подход не принесет желаемого оптимального размещения по критериям оптимальности, при такой укладке оптимальным будет только критерий ТЦх). Известно, что если располагать связанные вершины как можно ближе друг к другу, то можно косвенно решить проблему минимизации числа пересечений рсбср[10]. Фактически данную стратегию и использует алгоритм #3. Но известны некоторые методы укладки графов по данной стратегии. Например, существует алгоритм, который укладывает граф по принципу укладки «соседей» рядом друге другом строго за линейное время 0{н)[Ю. Данный алгоритм является эвристическим и дает удовлетворительные результаты по числу пересечений линий связей,
Другие алгоритмы, которые минимизируют суммарную длину линий связей (СДС) классифицируются как алгоритмы размещения.
Суть всех алгоритмов размещения сводится к следующему. При размещении элементы представляются точками. В большинстве случаев в таких алгоритмах основным критерием является СДС, который учитывает косвенно «число пересечений линий связей» и просте математической точки зрения.
Расстояние между позициями элементов (точками) где (л-і5уґ), (л-;,у,)-координаты і-ой и j-ой позиций коммутационного поли.
Задача сводится к тому, чтобы на множестве установочных вакантных мест К = {&}ч1с2ч..,чкр] разместить множество элементов схемы x=[xitx2f...,xtl)f добиваясь минимизации целевой функции по СДС где с„- число связей между элементами х, и гДчисло кратных ребер графа G = (Г,Л ), отображающего схему).
Часто элементы, наиболее связанные между собой, предварительно объединяются в группы. Группа при размещении рассматривается как один элемент, внутренние связи которого не учитываются.
Все известные алгоритмы являются приближенными, но этого достаточно, так как dtj - это расстояние между центрами элементов, а не истинные длины соединений.
Приведем классификацию алгоритмов размещения. Все эги алгоритмы делятся на группы,
1, Алгоритмы, которые используют силовые функции, в которых задача раз мещения сводится к задаче определения статического состояния модельной меха нической системы материальных точек. Элементы интерпретируются как матери альные точки, между которыми действуют силы притяжения и отталкивания. Си лы притяжения Ftj между точками / ( ,, ,) и 1)(хгу;) пропорциональны числу связей frjl, силы отталкивания Фч между точками РХхпу,) и Р {хгу ) возрастают с уменьшением dir Вводятся силы отталкивания от краев коммутационного поля, силы сопротивления среды. Эти алгоритмы сложны для реализации на ЭВМ.
2, Алгоритмы последовательного размещения предусматривают первона чальное размещение части элементов. На следующем шаге рассматривается упо рядоченное множество неразмещенных элементов, множество свободных пози 78 ций и матрица длин связей [c/ ]s где Jep- длина соединений между элементом е и другими ранее размещенными элементами, при условии размещения элемента е к позицию р. Для каждой позиции определяется СДС элементов, для которых эта позиция наиболее удобна (в смысле минимальной длины соединений с размещенными элементами). Иногда подсчитываетея не абсолютная длина соединений, а приращение длины соединений, то сеть вводится целевая функция, учитывающая связи данного элемента с размешенными элементами. После размещения очередного элемента (модуля) процесс повторяется для оставшихся элементов и вакантных установочных мест до тех пор, пока не будут размещены все элементы. Такие алгоритмы просты и быстродействующие.
3. Алгоритмы перестановки элементов (парные замены, соседние парные замены, частичный перебор) предполагают наличие начального размещения, полученного с помощью алгоритмов первой или второй группы или вручную, и используются для улучшения первоначального размещения. Например, в итерационном алгоритме парных замен каждый элемент меняется с каждым и при каждой пробе просматривается, сокращается ли СДС. Все возможные пробы (их число равно //(/ -1)/2, где //- число элементов) составляют одну итерацию. Выбирается замена с минимумом СДС. Время пропорционально и2 и при больших размерностях тго не целесообразный алгоритм. Алгоритм соседних парных замен отличается от предыдущего просмотром только соседних элементов (например, при расстоянии к = 4 or первичного элемента просматривается около lk{k -+-1) = 40 элементов)- Применяются методы упорядочения просмотра элементов при замене, групповые перестановки.
Алгоритмы размещения предфрактального графа, порожденного ациклической затравкой
Термином заіравка условимся называть какой-либо связный граф // = (И7,0 . Дли определения фрактального (предфрактального) графа [59] нам потребуется операция замены вершины затравкой (ЗВЗ). Суть операции ЗВЗ заключается в следующем. В данном графе (7 = (Г,Я) у намеченной для замещения вершины г є Г выделяется множество Г = {5 }сГ 7 = 1,2,...,1(7] смежных ей вершин. Далее из графа О удаляется вершина v и все инцидентные ей ребра. Затем каждая вершина v, є Г j -1,2,...,1 V 17 соединяется ребром с одной из вершин затравки
H={W,Q). Вершины соединяются произвольно (случайным образом) или по определенному правилу, при необходимости,
Прсдфрактальный граф будем обозначать через Olt=(Vj,KL) где VL -множество вершин графа, a KL- множество его ребер. Определим его рекуррент-но, поэтапно, заменяя каждый раз в построенном на предыдущем этапе / = 1Д,,,,А 1 графе G, =( ,К,)каждую его вершину затравкой н -ф\0). На этапе / = 1предфрактальному графу соответствует затравка = //.06 описанном процессе говорят, что прсдфрактальный граф GL - i}\J\) порожден затравкой H-(WtQ). Процесс порождения предфрактального графа GL, по существу, есть процесс построения последовательности предфрактальных графов G Gy..Jjt,...,GL , называемой траекторией. Фрагляльпыи граф G-(l\K)t порожденный затравкой Н={№\0)9 определяется бесконечной траекторией.
Предположим, что затравка // = {W,Q} является ациклическим графом. Допустим также, что порождение предфрактального графа GL соответствует построению траектории Gi4G2,...,G!4...,Gj.
Таким образом, если граф GL -(PL,,\) порожден ациклическими затравками Н ={ft\Q)9 то к нему можно применить любой из ранее предложенных алго ритмов укладки ациклических графов, В алгоритмах будем полагать, что пред-фрактальный граф G, =(VL9EL) был получен из графа G = Q\E) путем последовательности операций ЗВЗ.
Алгоритм а4 получения оптимального разбиения по критерию симметричного размещения графа в применении к предфрактальному ациклическому графу GL = {1\ KL) будет выглядеть следующим образом, ВХОД: прсдфрактальный граф GL = (VLtEL) и граф G = (IV-). ВЫХОД: оптимальное разбиение графа Gr = (l M/:t) 1 длину и в ширину. Шаг 1. Применение процедуры Алгоритм а, для графа G = (l\E). Шаг 2. Применение процедуры Алгоритм ах для затравки Н = (W90). Шаг 3, Учитывая связность вершин в предфрактальном графе GL = (l L,KL), получить размещение х. Окончание. Теорема 2Л1. Алгоритм аА строит укладку предфракталыюго графа GL = (VL,EL) оптимальную по критерию симмеїричного размещения его на плоскости,
ДОКАЗАТЕЛЬСТВО. Согласно следствию 2.1.1, получаемая укладка для каждой затравки // -{W.O) является оптимальной по критерию /]( ) симметричного размещения на плоскости. Кроме того, оптимальной укладкой по критерию !\(х) является укладка, получаемая для графа G = {l\R), из которого путем построения траектории получается предфрактальный граф G} -(VLj:L). Таким образом, общее результирующее размещение ХЕХ для графа GL-(VL,KL) будет оптимально по критерию !\(х).М
Теорема 2.12. Алгоритм ал строит размещение .v, = {V ,E") графа Gr =(l \tKL} оптимальное по первому критерию ,( ), по пятому критерию / (л ,). И оцениваемое по второму критерию 0 /":( ,) -1, по третьему критерию — HJVx Fi(xi) HsIVxt по четвертому критерию 0 F4(xl) Wx-Hx9 но шестому критерию 0 F&(x}) 2(I\ + Р2)9 где I]- число пар связанных вершин лежащих на одной горизонтальной линии (L = const), Рг- число пар связанных вершин, лежащих на одной вертикальной линии. ДОКАЗАТЕЛЬСТВО, Доказательство аналогично доказательству теоремы 2,3.«
Теорема 2.13. Вычислительная сложность алгоритма ах для предфракталь ного графа G\ = ( А) порожденного от графа G = (V,E) путем последовательности операций ЗВЗ с длиной маршрута П, равной и, для графа Gn с длиной маршрута Qjr раиной шП для затравки II =(№ ()) равна «{(1 + deev, +2( 8 -, l))-i.-] + (lH-degW H-StfeB -! -l» ) 3 1-І ДОКАЗАТЕЛЬСТВО. В алгоритме а4 два раза используется процедура Алгоритм aL; один раз для графа G = (VtE), второй раз для затравки Н -(WtO), Используя доказательство теоремы 2.4, мы можем утверждать, что вычислительная сложность алгоритма а4 равна: Л7-1 ЛТ —1 0((1 + degv, + (degv, ,-!)) + (1 + degи-, + 2])(degw( ,-l))-Gj), где r, є! и н1, є Ж- вершины, из которых берется начало при построении маршрутов О. и Qir соответственно.- Алгоритм cfs получения оптимального разбиения по критерию совпадающего направления ребер трафа в применении к предфрактальному ациклическому графу Gs -{VjJ7 ) будет выглядеть следующим образом. ВХОД; ациклический граф GL = {VL,K() ВЫХОД: оптимальное восходящее изображение Gr - ( ,/ )-Шаг 1. Применение процедуры Алгоритм а2 для графа (; = (yjc). Шаг2. Применение процедуры Алгоритм аг для затравки И =(WJJ). Шаг 3. Учитывая связность вершин в предфрактальном графе GL -(Гм/ ;л), получить размещение х.
