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

На правах рукописи

Ворожцов Артём Викторович

Построение алгоритмов ортогонального представления графа с указанными портами рёбер

Специальность 05.13.18 -Математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

МОСКВА - 2005

Работа выполнена на кафедре информатики Московского физико-технического института (государственного университета)

Научный руководитель:

доктор физико-математических наук, профессор Малинецкий Георгий Геннадьевич

Официальные оппоненты:

член-корреспондент РАН,

доктор физико-математических наук, профессор Флёров Юрий Арсениевич

кандидат физико-математических наук, Подлипский Олег Константинович

Ведущая организация:

Институт Проблем Управления РАН им. В.А. Трапезникова

Защита состоится ЛкЗ__в__на

заседании диссертационного совета К 212.156.02 при Московском физико-техническом институте (государственном университете) по адресу: 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9.

С диссертацией можно ознакомиться в библиотеке МФТИ. Автореферат разослан

Ученый секретарь уг-

диссертационного совета,

кандидат физико-математических наук

Федько О. С.

^ /М6ГИ

iâ

Общая характеристика работы

Актуальность темы

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

управление Выход

Функциональный блок

Актуальной задачей является

автоматическое построение органи- Вход

зационных IDEF-диаграмм. IDEF _

(ICAM Definition) — это стандарт -

моделирования технологических

„ I I механизм

операций, компьютерных систем и

бизнес-процессов. В частности, стандарт IDEF0 касается моделирования Рис. 1 управляющих бизнес-процессов предприятия. Этот стандарт описывает правила представления схемы управления предприятия в виде набора функциональных блоков, соединённых ломанными линиями. Блоки изображаются прямоугольниками, стороны которых называются портами. В верхнюю часть функционального блока (северный порт) идут стрелки от функциональных блоков, которые им управляют, в западный порт поступает вход, из восточного порта идёт выход, в южный порт выходят стрелки от блоков, определяющих механизм работы данного блока (см. рис. 1).

Задача представления графов, для ребёр которых указаны порты, возникает при построении не только IDEF-диаграмм, но и ряда других схем: SADT-схем, UML-диаграмм, блок-схем и др.

Цели работы

Целью работы была разработка системы автоматического построения IDEF-диаграмм, то есть системы, решающей задачу оптимального ортогонального представления графов с указанными портами рёбер (Optimal Orthogonal Graph Layout with Ports, OOGLP), где оптимальность определяется функцией штрафа, зависящей от числа пересечений и изгибов представления рёбер, а также от площади представления.

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

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА С.Пст*»*рг 09

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

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

Методы исследования

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

Для проведения численных исследований, визуализации данных и сравнительного анализа методов были использованы системы graphviz и Mathematica.

При построении программного комплекса использовались языки программирования Си и Perl.

Научная новизна

Только некоторые этапы решения задачи OOGLP можно свести к ряду известных Л^Р-сложных оптимизационных задач, в частности, к задаче поиска оптимального линейного порядка вершин графа (Optimal Linear Arrangement, OLA) и задаче поиска максимального ацикличного подграфа ориентированного графа (задача MAXACYCL). Можно рассматривать задачу OOGLP как обобщение задачи OLA на двумерный случай. Задачи OLA и MAXACYCL подробно исследованы, но разработанные методы их решения не имеют хороших оценок качества работы. Задача OOGLP ранее в научных работах не рассматривалась1.

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

1 Поиск работ по темам связанным с задачей OOGLP осуществлялся по аннотированным библиографическим спискам 'Теория представления графов", в архиве препринтов http://arxiv.org/, статьях журнала "Journal of Graph Algorithms aijd Applications", и системе http://citeseer.ist.psu.edu.

не превосходят 4, для случая, когда порты рёбер не фиксированы, оказался не применимым к задаче OOGLP.

Поэтому, решение задачи OOGLP требовало разработки новых алгоритмов.

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

В работе исследованы базовые методы (метаэвристики) NV-программирования, которые можно использовать при конструировании приближённых алгоритмов решения jVP-сложных и плохо формализуемых алгоритмических задач.

В работе описан новый метод macro — метод введения макросущностей: макро-объектов, макро-действий и макро-языка. Описаны общие принципы осуществления метасистемных переходов на уровне конструирования алгоритма, в частности новый подход решения сложных задач, в котором задача выделения макросущностей решается алгоритмом, а не человеком.

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

Практическое значение работы

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

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

2Verba!l — инструмент построения информационных систем предприятий, http://orgvay.org.

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

Публикации

По теме диссертации опубликовано 9 работ, из них 4 препринта, 2 статьи в реферируемых журналах, 3 тезизов докладов.

Структура диссертации

Диссертация состоит из введения, семи глав и заключения, изложенных на 130 страницах и иллюстрирована 36 рисунками. Библиографический список включает 65 наименований.

Содержание работы Введение

В введении описана структура диссертации и сформулированы основные положения диссертации. Рассматриваемая в диссертации задача ортогонального представления графов с указанными портами рёбер (Optimal Orthogonal Graph Layout with Ports, OOGLP) описывается следующими условиями:

а) граф произвольный;

б) ребра представляются "ортогональными" ломанными, то есть ломанными, звенья которых параллельны осям координат;

в) вершины (узлы) представляются прямоугольниками заданных размеров;

г) для каждого ребра указана сторона узла, откуда оно должно выходить, и сторона узла, куда оно должно входить;

д) необходимо минимизировать следующую целевую функцию:

Cost = ai • (длина рёбер) +

<*2 • (число изгибов рёбер) +

аз • (число пересечений рёбер) +_

а4 • ^/(площадь ограничивающего прямоугольника).

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

Глава 1. Обзор задач и алгоритмов теории представления графов

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

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

Ключевые работы и библиографические списки работ по теме визуализации графов приведены в аннотированной библиографии Р. Тамассия и др.1

Ключевым моментом решения многих задач представления графов оказывается поиск оптимального линейного порядка вершин ориентированного графа с взвешенными рёбрами (Optimal Linear Arrangement, OLA). Это NV-сложная задача, на которой опробован практически весь "арсенал" эвристических алгоритмов ("жадные" алгоритмы, метод отжига, генетические алгоритмы и другие).

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

Глава 2. Общие методы ЛЛР-программирования

В этой главе разобраны методы Л^-программирования [9], которые использовались при построении алгоритмов решения задачи OOGLP.

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

Описаны следующие базовые методы:

model: Сведение задачи к моделированию физической системы divide: Деление на подзадачи ("разделяй и властвуй") scale: Огрубление (упрощение) задачи reduction: Сведение задачи к другой

1Battista G. D., Eades P., Tamassia R., Tollis I G.. Algorithms for Drawing Graphs: an Annotated Bibliography, 1994, ftp://ftp.es.brovn.edu/pub/papers/compgeo/.

local: Метод локальных улучшений parallel: Распараллеливание competition: Естественный отбор лучших

macro: Выделение макро-объектов и проецирование задачи на м акро-объекты

meta: Метасистемный переход на уровне алгоритма (различные мета-алгоритмы)

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

генетические алгоритмы = parallel + competition + local.

А в методе масштабирования присутствуют следующие компоненты:

метод масштабирования = scale + macro + local + meta. Методы scale и macro во многом схожи. Оба связаны с уменьшением уровня детализации рассматриваемых данных.

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

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

Глава 3. Задача OOGLP

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

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

Пример описания портов ребра: "ребро ei выходит из севера узла а\ и входит в восток узла 02".

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

East-East CZ^ |—^J,—^

East-North | | Д^ИЦ

East-West I Ы I —|

Рис. 1: Простые пути для рёбер типа восток-восток, восток-север и восток-запад.

Ключевой метод решения оптимизационных задач со сложной целевой функцией заключается в поиске альтернативной целевой функции Cost', которая близка настоящей целевой функции Cost и при этом допускает эффективный алгоритм поиска минимума. Понятие близость целевых функций можно грубо пояснить так: из неравенства Cost(a) > Cost{b) должно часто следовать неравенство Cost'(a) > Cost'(b).

Замены настоящей целевой функции на искусственную соответствует метаэвристике reduction — сведению исходной задаче к другой, более простой. Это практически единственный конструктивный подход к задаче OOGLP. Решение задачи разбивается на два этапа:

• поиск оптимального положения вершин на плоскости,

• оптимальное проведение рёбер для заданного положения вершин.

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

На рисунке 1 показаны примеры простых путей рёбер с заданными портами. Простыми мы называем пути, которые имеют минимальное число изломов при заданных положениях узлов. Так для ребра типа "восток-восток" есть только два возможных простых пути (с точностью до симметрии относительно горизонтали). Слева на рисунке указаны наиболее оптимальные варианты расположения узлов для каждого типа ребра.

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

Глава 4. Приближенные алгоритмы решения задачи OOGLP

В главе 4 показано, как методы ЛГР-программирования, описанные в главе 2, "работают" при решении задачи OOGLP. Разработано четыре различных эвристических алгоритма, решающих задачу оптимального положения вершин на плоскости — это алгоритмы model, mover, spectr и stem ранжирования вершин графа:

• model — метод, основанный на математическом моделировании физической системы взаимодействующих узлов графа, в которой взаимодействия определяются рёбрами графа.

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

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

• stem — метод, основанный на поиске подграфа, который может быть построен без решения сложной оптимизационной задачи. Достройка остальной части графа проводится жадным методом, исходя из минимизации штрафа на каждом шаге. Указанный подграф можно назвать каркасом, метод — мето-

» дом выделения каркаса.

Спектральные методы ранжирования и метод выделения каркаса подробно описаны в ряде работ по алгоритмам решения задачи OLA2. Рассмотрим подробнее алгоритмы mover и model.

Алгоритм mover

Алгоритм ранжирования mover основан на последовательных малых улучшениях (метод local). Он устроен следующим образом:

• Рассматриваются последовательно каждая вершина графа и рассматриваются все возможные перемещения этой вершины.

• Для каждого перемещения вычисляется ценность — мера уменьшения функции штрафа, к которому приводит данное перемещение. Самое «ценное» из перемещений для каждого узла запоминается.

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

ь На рисунке 2 показаны примеры простых улучшающих переме-

щений вершины с, соединённой с двумя другими вершинами.

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

2 Juvan M., Mohär В. "Optimal Linear Labelings and Eigenvalues of Graphs", Discrete Applied Math. 36 (1992), pp. 153-168.

Berger В., Shor P.W. Approximation algorithms acyclic subgraph problem. Proc. of the first annual ACM-SIAM Symp. on Discrete Algorithms, (1990) SIAM, Philadelphia, pp. 236-243

Lf d

В- ^

ш ш

a)

сtj cE

e)

[EHjl^

kzh

Ш—J

5)

г)

Рис. 2: Примеры простых улучшающих перемещений вершины с связанного с вершинами а и Ь

огрубляется, а именно не рассмариваются штрафы за пересечения рёбер. На первом этапе удобно считать, что все рёбра идут по простым путям, представленным на рисунке 1 и не учитывать штраф за пересечения, и то, что на пути ребра может возникнуть препятствие в виде вершины, которую нужно "обходить". Это связано с тем, что учёт описанных моментов требует вычислительно сложного алгоритма. Описанное огрубление функции штрафа на первом этапе последовательных локальных улучшений даже полезно, так как позволяет сгладить многие локальные минимумы функции штрафа и получить более оптимальные представления (метод масштабирования). После того, как ни для одного узла не найдется улучшающего перемещения, функция штрафа уточняется и делаются локальные улучшения с учётом препятствий на пути рёбер « и пересечений рёбер. Эксперименты показали, что такой двухэтап-ный метод локальных улучшений позволяет в среднем уменьшить значение штрафа на 5%.

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

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

локального улучшения пропорциональна е-^, где 5£ — величина изменения штрафа за представление, связанная с этим улучшением. Эта модификация алгоритма mover давала представления с штрафом в среднем больше на 4%, но при этом в 7% случаях давала представления лучше, нежели базовый алгоритм mover.

Метод model

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

задача —> мат. модель алгоритм —> программа

был добавлен ещё один шаг — сведение исходной задачи к аналоговой (физической) модели, и приближение функции штрафа потенциальной энергией взаимодействующих материальных точек: задача —> аналог, модель —v мат. модель —¥ алгоритм —> программа

Алгоритм model также ocho- fdJ ,] Нд] ван на идее последовательных

-й—

КГ]

локальных изменениях, но в от- ^ личие от алгоритма mover эти изменения происходят непре- а) б)

рывно и для всех вершин одно-

времейно. Рис. 3: Силы, действующие на вер-

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

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

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

а) б)

Рис. 4: Ситуации, в которых вершина о уменьшает "желание" вершины с к перемещению (а) или, наоборот, увеличивает (б).

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

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

Время работы алгоритма определяется числом взаимодействий и числом шагов эволюции. Число взаимодействий пропорционально числу рёбер графа, а число шагов зависит от активности динамики. Максимальное значение числа шагов определяется эвристической функцией, линейно зависящей от числа вершин графа. Процесс эволюции завершается раньше при условии, когда суммарное перемещение вершин графа становится меньше некоторого предельного значения. Всремя работы алгоритма model имеет асимптотику 0{\Е\ ■ |V|), где |V| - число вершин графа, - число рёбер графа.

Задача оптимального проведения рёбер

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

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

Алгоритм основан на "жадности" (методы greedy и local), и заключается последовательном проведении рёбер с минимизацией штрафа на каждом шаге.

Рассмотрим как осуществляется один такой шаг. Будем считать, что установлены штрафы за пересечения, изгибы и длину рёбер. Оптимальный путь ребра ищется как кратчайший путь в графе-решетке, который модифицируется по мере проведения рёбер. Граф решётки Gg = (Vg,Eg) мы будем называть решёткой, его вершины — узлами, а рёбра решётки — звеньями. Рёбрами мы будем называть рёбра исходного графа G = (V, Е), а также последовательность звеньев решетки, по которым они они проведены.

Для учёта штрафов за изгибы граф решётки был модифицирован, а именно, каждый узел v решетки был учетверён, то есть узел v заменён на четыре узла ve, vw, vs, vn, которые являются восточным, западным, южным и северным представителями узла v исходной решетки (см. рис. 5). Диагоналям получившегося квадрата с вершинами ve, vw, v„, vn назначается нулевой вес (длина), а сторонам квадрата назначается вес a-i, равный штрафу за поворот. Веса внешних звеньев устанавливаются равными величине ai штрафа за единицу длины ребра. Граф учетверённой решётки обозначим как 6?4. В те места решетки, куда помещены вершины исходного графа, вершины ve, vw, vs, vn не соединены звеньями.

Л ^ с,

Л Л V S

Рис. 5: Каждый узел целочисленной решетки имеет с каждой стороны своего представителя. Вес рёбер (ги,п), (п, е), (е,з), (з,ги) равен штрафу за поворот.

Схема алгоритма 1. вычисления представления рёбер

Даны целочисленные координаты вершин графа G = (У, Е).

1. Строим граф решётки G4 с взвешенными ребрами.

2. Для каждого ребра е графа G

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

Теорема 2.1. Алгоритм 1 находит представление рёбер, на котором достигается минимум функции штрафа Cost': Cost' = а\суммарная длина рёбер + а^число изгибов рёбер.

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

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

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

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

сортировка по длине простого пути.

Время работы алгоритма определяется размером графа решётки Gg = (Vg,Eg). Алгоритм сводится решению задачи поиска кратчайшего пути в графе решетки для каждого ребра исходного графа. Кратчайший путь ищется алгоритмом Дейкстры, оптимизированном для разреженных графов. Время работы этого алгоритма есть 0(Ед log \Ед\), где \Ед\ — число ребер в графе решетки. Изначально \Ед\ на 16 • X • Y, где X х Y — размер решетки. Каждое проведённое ребро исходного графа увеличивает число ребер решетки.

Важно отметить, что именно на этап проведения рёбер при типичных размерах графа (число вершин \V\ < 100) тратится большая часть времени поиска оптимального представления. Если предположить, что узлы расположены по площади представления равномерно, так что размер решетки X х У пропорционален числу узлов |V|, то можно получить следующую асимптотику времени работы алгоритма проведений рёбер: 0(\V\ log |V|).

Глава 5. Анализ приближённых алгоритмов

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

Пусть X = {xi,x2, ■ ■ ■ ,хп} — множество различных входных данных, а А = {Ai, Лг,..., Ат} — множество имеющихся эвристических алгоритмов решения оптимизационной задачи.

Обозначим величину значения целевой функции на результате работы алгоритма Ai для входных данных хкак £i(xj).

Турнирная таблица. Для каждой пары алгоритмов (A„Aj) подсчитаем долю £ij задач, на которых алгоритм Аг обыграл алгоритм Aj (в случае ничьи алгоритмы делят очко попалам):

Sij = (число задач х, для которых £i(x) > £j(x)) +0.5 • (число задач х, для которых £i{x) = £j{x)).

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

Введём меру полезности алгоритма Ai при решении задачи j:

Величина Т соответствует некоторой эталонной сложности задачи или фиксированной единице измерения штрафа.

Если проводить аналогию со статистической физикой, то задачи X играют роль физических систем, а алгоритмы отображаются в уровни энергии, запараметризованные задачами. Величина W^ полезности алгоритма Aj при решении задачи х3 равна вероятности пребывания на энергетическом уровне Si(xj) в физической системе, соответствующей задаче Xj. Введём агрегатную меру полезности алгоритма А{:

ui = YJw^T)- (2Л)

з

Это сумма вероятностей пребывания на+ уровне энергии, задаваемом алгоритмом Ai, по всем задачам (физическим системам) xj.

При Т —> О величина U% стремится к числу задач, в которых алгоритм Ai оказался лучше всех остальных алгоритмов (в случае, когда несколько алгоритмов получили конфигурации с одним и тем же значением функции штрафа, очко поровну делится между ними). При Т —> оо распределение по алгоритмам становится равномерным и величина Т(п • Wij — 1) стремится к разности среднего штрафа за задачу Xj по всем алгоритмам и штрафа алгоритма А,-: Т(П ■ w^ -1) (П=1 - Ыч))-

Таким образом, при маленьких значениях Т величина Ui отображает полезность алгоритма - то, насколько часто данный алгоритм оказался лучше других, а при больших значениях Т — надёжность — то, насколько хорошо данный алгоритм работает в среднем.

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

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

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

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

Предлагаемые методы во многом основаны на работах Ю.И. Журавлева по теме "Корректные алгебры над множествами некорректных (эвристических) алгоритмов".

Результаты сравнительного анализа

Для разреженных графов (40 вершин, средняя степень вершин равна 3) получается следующая турнирная таблица алгоритмов:

0 12 3 model( 0): 0.500 0.650 0.875 0.775 stem( 1): 0.350 0.500 0.500 0.675 spectr( 2): 0.125 0.500 0.500 0.625 mover( 3): 0.225 0.325 0.375 0.500

Для более плотных графов (40 вершин, средняя степень вершин равна 7) метод spectr обходит метод stem:

0 12 3 model( 0): 0.500 0.650 0.825 0.700 spectr( 1): 0.350 0.500 0.575 0.600 stem( 2): 0.175 0,425 0.500 0.575 mover( 3): 0.300 0.400 0.425 0.500

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

Как для плотных, так и для разрежённых графов метод model оказывается в среднем лучшим, то есть суммарная величина штрафа для него минимальна. Введём алгоритм best, соответствующий "сумме" этих четырёх алгоритмов: best = model + spectr + stem + mover. Он по определению означает алгоритм, который запускает все четыре алгоритма и из полученных

представлений графа выбирает наилучшее. Обозначим величину среднего штрафа алгоритма best за единицу.

Для тестовой базы графов типичных для IDEF диаграмм со средней степенью вершин 5 получается следующие относительные величины средних

штрафов:

штраф очки

best 1.000 86.000

model 1.053 29.105

spectr 1.060 28.565

local 1.090 13.029'

stem 1.096 15.301

MODEL

a

r><^<VsTEM

__-—BEST

■ относительный штраф

N. MOOEL

6

---^^^SPECTir^

9EST

----MOVER

0.2

• относительный штраф

Второй столбец (очки) отображает меру полезности алгоритма, которая вычислялась по формуле 2.1 при малых значениях параметра Т (1/10 от величины дисперсии штрафа). Рис. 7

На рисунке 7 приведена более подробная диаграмма сложения алгоритмов для двух различных наборов графов: (а) - разреженные графы (средняя степень вершины равна 3) и (б) - плотные графы (средняя степень вершины равна 6). Там показано, что каждый из алгоритмов model, spectr, stem и mover является в свою очередь "суммой" нескольких сходных алгоритмов, отличающихся лишь каким-то набором параметров. Все алгоритмы в сумме дают алгоритм best. Алгоритм spectr в случае (б) обгоняет алгоритм stem и оказывается по качеству очень близок к model. Интересно также отметить, что в случае (б) алгоритм stem оказался полезнее mover, хотя в среднем работает хуже. Видно, что добавление к методу model трёх других алгоритмов (приводящее к учетверению времени работы) приводит к уменьшению среднего штрафа лишь на 5%. Для тестовой базы графов, в которой есть как разреженные так и плотные графа, выигрыш от сложения достигает 10%.

Примеры ортогональных представлений

Разработанный программный комплекс ortho предоставляет возможность задавать параметры алгоритмов, комбинировать раз-

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

На рисунках 8, 9, 10, 11 приведены примеры представлений, построенных с помощью разработанной программы огг1ю.

Глава 6. Задача OLA и упорядочивание по вычислительной сложности

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

Рис. 8.

Рис. 9.

Рис. 10.

Рис. 11.

можно преодолеть, сведя её к проблеме ранжирования по матрице парных взаимодействий, то есть к задаче, решаемой в диссертации [1].

Основные результаты

1. Разработано четыре эвристических алгоритма, решающих задачу оптимального ортогонального представления графа на плоскости с указанными портами рёбер (задачу ОСЮЬР). В качестве основного метода использовался метод математического моделирования физической системы взаимодействующих вершин графа;

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

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

4. Исследованы базовые методы Л/^-программирования, позволяющие приближенно решать Л/'Р-сложные и трудно формализуемые задачи. Предложен новый метод конструирования алгоритмов, основанный на введении макро-сущностей (макро-объектов и макро-действий с ними). Указаны варианты использования базовых методов для построения приближённых алгоритмов решения задачи ОСЮЬР.

Список публикаций по теме диссертации

1. Ворожцов А. В. Алгебраические методы определения сложности: Препринт / ИПМ РАН. - М., 2001. - №17. - 23 с.

2. Ворожцов А. В. Прогнозирование и теория сложности: Препринт / ИПМ РАН. - М., 2001. - №18. - 17 с.

3. Ворожцов A.B. Индустрия знаний.// Информационные технологии и вычислительные системы. - 2003. - том. 1-2. -С. 145-148.

4. Ворожцов A.B. Задача о лидере и упорядочивание по вычислительной сложности.// Моделирование процессов управления. - М.:МФТИ, 2004. - С. 218-228.

5. Ворожцов A.B. Эвристические алгоритмы кластеризации для маломерных пространств.// Современные проблемы фундаментальных и прикладных наук: Труды XLV Научной Конференции МФТИ. Часть VIII. - Долгопрудный, 2003 - С. 54.

6. Ворожцов A.B., Винокуров H.A. Два приближенных алгоритма решения задачи коммивояжера.// Моделирование процессов управления. - М.:МФТИ, 2004. - С. 211-217.

7. Ворожцов A.B. Критерии интеллектуальности искусственных систем: Препринт / ИПМ РАН. - М., 2004. - №60. - 26 с.

8. Ворожцов A.B. Критерии интеллектуальности искусственных систем.// Рефлексивные процессы и управление. - 2004 - Том 4, №2. - С. 18-29.

9. Ворожцов A.B. Мета-методы ЛЛР-программирования: Препринт / ИПМ РАН. - М., 2005. - №43. - 18 с.

«24194

РНБ Русский фонд

2006-4 26639

Ворожцов Артём Викторович

Построение алгоритмов ортогонального представления графа с указанными портами рёбер

Подписано в печать 20.10.2005. Формат 60 х 84 1/16. Печать офсетная. Усл. печ.л. 1,0. Усл. изд.л 1,0. Тираж 70 экз. Заказ Л» ф 534.

Государственное образовательное учереждение

высшего профессионального образования /.

Московский физико-технический институт (государственный университет) Отдел автоматизированных издательских систем « ФИЗТЕХ-ПОЛИГРАФ »

141700, Московская обл., г. Долгопрудный, Институтский пер., 9

Введение

1 Обзор задач и алгоритмов теории представления графов

1.1 Ссылки на базовые алгоритмы и ключевые работы

1.2 Компьютерные системы.

Система Graphviz.

Библиотека алгоритмов LEDA и системы yEd, AGD.

1.3 Задача поиска оптимального линейного порядка.

Основные понятия и формулировка ключевых задач.

Обзор приближенных алгоритмов решения задач OLA

2 "Человеческие" методы решения сложных задач

2.1 Базовые составляющие алгоритмов решения сложных задач

Метод divide: "разделяй и властвуй".

Метод parallel: распараллеливание.

Метод competition: отбор лучших.

Метод local: локальные улучшения, "жадные" алгоритмы

Метод scale: огрубление.

Метод macro: введение макро-объектов.

Метод meta: метасистемные переходы в программировании

2.2 Инструментарий для Л/*'Р-программирования.

3 Задача ортогонального представления графа с портами

3.1 Общая задача плоского ортогонального представления графа

3.2 Задача представления графа с заданными портами рёбер

3.3 Сводимость OOGLP к OOGL.

4 Эвристические алгоритмы решения задачи OOGLP

4.1 Идеи решения.

4.2 Схема основного алгоритма.

4.3 Метод ранжирования последовательными улучшениями.

4.4 Метод ранжирования на основе физической модели.

4.5 Метод выделения каркаса графа.

4.6 Спектральные методы ранжирования.

4.7 Задача проведения рёбер.

4.8 Задача выпрямления рёбер.

4.9 Примеры работы алгоритма ortho

4.10 Реализация алгоритмов.

5 Методы анализа приближённых алгоритмов

5.1 Сила алгоритма и мера зависимости сил двух алгоритмов

5.2 Понятия надёжности и полезности алгоритмов.

5.3 Результаты сравнительного анализа.

6 Задача OLA и вычислительная сложность

6.1 Задача о лидере — два метода ранжирования.

6.2 Модель "Естественный отбор".

6.3 Модель "Обмен товаров".

6.4 Ранжирование по вычислительной сложности

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

Актуальной задачей является автоматическое построение организационных IDEF- Вх°Д диаграмм. IDEF (Integrated Computer-Aided

Manufacturing Definition) — это стандарт

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

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

Задача представления графов, для рёбер которых указаны порты, возникает при построении не только ГОЕР-диаграмм, но и ряда других схем: ЭАБТ-схем, иМЬ-диаграмм, блок-схем и др.

Целью работы была разработка программы для автоматического построения IDEF-диаграмм, то есть программы, решающей задачу поиска оптимального ортогонального представления графов с указанными портами рёбер (Optimal Orthogonal Graph Layout with Ports, OOGLP). Оптимальность представления графа определяется числом пересечений и изгибов представлений рёбер, площадью представления и суммарной длиной представлений рёбер.

Раздел теории алгоритмов, посвященный представлениям графов (Graph Drawing, GD), активно развивался начиная с 1980 года [7, 8] и сейчас содержит ряд интересных решений для специальных случаев представлений. Различные варианты задачи оптимального плоского представления графа порождаются множеством ограничений на входной граф (ограничения на степени вершин, планарный граф или нет, плотный или разреженный, ориентированный или неориентированный), типами представлений рёбер (прямые линии, ломанные, "ортогональные" ломанные, кривые Безье), различными ограничениями на представление в целом (решётчатые представления, многослойные представления, ограничения на пересечения и изгибы, ограничения на длины ребер, ограничения на расстояния между объектами, ограничения на площадь представления), а также различными целевыми функциями (число пересечений, площадь представления, число изгибов рёбер, суммарная длина рёбер, максимальная длина ребра, комбинации этих функций).

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

Cost = ai • (длина ребер) + a<i • (число изгибов ребер) + з • (число пересечений ребер) +

4 ■ л/(площадь ограничивающего прямоугольника).

Пункт (г) наиболее важен. Ранее представления с таким ограничением не рассматривались.

Задача OOGLP как и множество других задач поиска представления графа, на котором достигается минимум целевой функции (функции штрафа), является А/'Р-сложной [4]. В частности, задача поиска плоского представления с минимальным числом пересечений рёбер (cross number problem, CNP) является Л/'Р-сложной [21]. Рассматриваемую задачу OOGLP можно частично свести к задаче поиска максимального ацикличного подграфа ориентированного графа, которая тоже является Л/'Р-сложной [32]. Кроме того, задачу OOGLP можно рассматривать как обобщение Л/""Р-сложной задачи поиска оптимального линейного порядка вершин ориентированного графа с взвешенными рёбрами (Optimal Linear Arrangement, OLA) [39] на двумерный случай. На задаче OLA опробован практически весь "арсенал" эвристических алгоритмов ("жадные" алгоритмы, метод отжига, генетические алгоритмы и др.). И многие идеи алгоритмов решения задачи OLA могут быть перенесены на задачу OOGLP.

Опишем содержание следующих глав диссертации.

Заключение

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

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

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

Алгоритмы spectr и mover также могут быть доработаны — есть несколько способов применения метаэвристики macro для повышения качества результата и уменьшения времени работы.

Резюмируем основные результаты работы.

1. В работе разобраны базовые методы Л^Р-программирования, позволяющих эффективно приближенно решать Л/'Р-сложные и трудно формализуемые задачи: метод огрубления задачи, жадные алгоритмы, метод локальных улучшений, метод введения макро-сущностей, метод отбора лучших и общая идея метасистемного перехода при построении сложных систем и алгоритмов. Описан новый метод конструирования алгоритмов macro, основанный на введение макро-сущностей (макро-объектов и макро-действий с ними). Предложено несколько вариантов применения этих методов для построения приближённых алгоритмов решения задачи OOGLP.

2. Разработано несколько приближённых алгоритмов, решающих задачу оптимального ортогонального представления графа на плоскости с указанными портами рёбер (задачу OOGLP):

• model — алгоритм, основанный на моделировании физической системы с пружинами и различными типами взаимодействия вершин графа;

• mover — алгоритм, основанный на методе последовательных локальных улучшений;

• spectr — алгоритм, основанный на построении "матрицы взаимодействия" узлов графа и вычислении доминантного собственного вектора этой матрицы;

• stem — алгоритм, основанный на выделении максимального подграфа, который может быть нарисован без решения сложной оптимизационной задачи;

3. Проведён сравнительный анализ разработанных алгоритмов, указаны достоинства и недостатки каждого из них. Введены важные понятия надёжности и полезности эвристических алгоритмов и описаны методы экспериментальной оценки этих величин. Исследована эффективность комбинирования разработаных алгоритмов и показано, что метод model является наиболее гибким и надежным алгоритмом для широкого класса графов, а алгоритм stem часто оказывается лучшим для разрежённых графов, поэтому на практике полезно комбинировать ("складывать") алгоритмы model и stem. Построена диаграмма сложения алгоритмов на плоскости {полезность, надежность}.

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

1. ABACUS A framework for branch-and-cut algorithms, http: / / www .informatik.uni-koeln.de/abacus /

2. AGD — library of Algorithms for Graph Drawing, http://www.mpi-sb.mpg.de/AGD/

3. Angeline P. Evolutionary Algorithms and Emergent Intelligence. PhD thesis, Ohio State University, Computer Science Department, 1993.

4. A compendium of MV optimization problems, Editors: Pierluigi Crescenzi, and Viggo Kann,http://www.nada.kth.se/~viggo/wwwcompendium/

5. Atkins J. E., Boman E. G., Hendrickson В. A Spectral Algorithm for Seriation and the Consecutive Ones Problem, SIAM Journal on Computing 28 (1998), 297-310.

6. Adolphson D., Ни Т. С. "Optimal linear ordering", SIAM Journal on Applied Mathematics, 25(3):403-423, 1973.

7. Battista G. D., Eades P., Tamassia R., Tollis I. G., Algorithms for Drawing Graphs: an Annotated Bibliography, 1994,ftp://ftp.cs.brown.edu/pub/papers/compgeo/.

8. Battista G. D., Eades P., Tamassia R., Tollis I. G., "Graph Drawing Algorithms for the Visualization of Graphs", 1999.

9. Berger В., Shor P. W. Approximation algorithms acyclic subgraph problem. Proc. of the first annual ACM-SIAM Symp. on Discrete Algorithms, pp. 236243, SIAM, Philadelphia, 1990.

10. Doxygen documentation system,http: //www. stack. nl/^dimitri/doxygen/index. html.

11. Diaz J., Petit J., Serna M. A Survey on Graph Layout Problems, Technical report LSI-00-61-R, Universität Politécnica de Catalunya, Departament de Llenguatges i Sistemes Informatics, 2000. http://www.lsi.upe.es/dept/techreps/ps/R00-61.ps.gz

12. Eades P., Lin X. A new heuristic for the feedback arc set problem, Australian Journal of Combinatorics, 12:15-26, 1995.

13. Ellson J., TclDG A Tel Extension for Dynamic Graphs, 1996.

14. Emden R. Gansner, North S. C. "An open graph visualization system and its applications to software engineering", 1999,http://www.graphviz.org/Documentation.html.

15. Essays and Surveys in Metaheuristics Series: Operations Research/Computer Science Interfaces Series, Vol. 15 Ribeiro, Celso C.; Hansen, Pierre (Eds.) 2001, 664 p., Hardcover.

16. Even G., Naor J. S., Rao S., Scieber B. "Divide-and-Conquer approximation algorithms via spreading matrices", in Proc. 36th Annual IEEE Symposium on Foundation of Computer Science, IEEE Computer Society Press, pp. 62-71, 1995.

17. Even G., Naor J. S., Rao S., Scieber B. "Fast Approximate Graph Partition Algorithms", 8th Annual ACM-SIAM Symposium on Disc. Algo., pp. 639-648, 1997.

18. Even S., Shiloach Y. "./VP-Completeness of several arrangement problems", Technical Report 43, Isreal Institute of Technology, 1975.

19. Gansner E. R., Koutsofios E., North S. C., Vo K. P. "Graph Visualization in Software Analysis" Proc. Symposium on Assessment of Quality Software Development Tools, IEEE Computer Society Press, New Orleans LA, May 27-29, 1992.

20. Garg A., Tamassia R. "On the Computational Complexity of Upward and Rectilinear Planarity Testing," Technical Report CS-94-10, Dept. of Computer Science, Brown Univ., 1994.

21. Garey M. R., Johnson D. S. "Crossing Number is NP-Complete", SIAM J. Algebraic and Discrete Methods, Vol. 4, No. 3, pp. 312-316, 1983.

22. Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of AAP-Completeness, W. H. Freeman and Company, NY, 1979.

23. Garey M. R., Johnson D. S., Stockmeyer L. "Some simplified ./VP-complete graph problems". Theoretical Computer Science, 1: pp. 237-267, 1976.

24. GiST for PostgreSQL, http://www.sai.msu.su/ megera/postgres/gist/

25. GraphViz — Graph Drawing Tools, http://www.graphviz.org,

26. Grdtschel M., Jiinger M., Reinelt G. "On the acyclic subgraph polytope", Mathematical Programming, 33, pp. 28-42, 1985.

27. Harary F. Problem 16. In M. Fieldler (Ed.), "Theory of Graphs and its Applications", Czech. Academy of Sciences, Prague, 1967.

28. Harper L. H. "Optimal assignment of numbers to vertices", SIAM Journal, 12, pp. 131-135, 1964.

29. IDEF — A structured approach to enterprise modeling and analysis, http://www.idef.com

30. Johnson, D. S. A catalog of complexity classes, in Algorithms and Complexity, volume A of Handbook of Theoretical Computer Science, Handbook of Theoretical Computer Science, Elsevier science publishing company, Amsterdam, pp. 67-161, 1990.

31. Juvan M., Mohar B. "Optimal Linear Labelings and Eigenvalues of Graphs", Discrete Applied Math. 36 (1992), 153-168.

32. Karp R. M. "Reducibility among combinatorial problems", Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, Eds. Plenum, New York, pp. 85103, 1972.

33. Kamada T. On Visualization of Abstract Objects and Relations, Ph.D. dissertation, Dept. of Information Science, Univ. of Tokyo, 1988.

34. Koren Y., Harel D. Multi-Scale Algorithm for the Linear Arrangement Problem, Technical Report MCS02-04, Faculty of Mathematics and Computer Science, The Weizmann Institute of Science, 2004.

35. LEDA, LEDAGraphAlgo Library of Algorithms on Graphs, http://www.algorithmic-solutions.com/

36. Leighton F. T. Complexity issues in VLSI, MIT Press, 1983.

37. Lovasz L. On the Shannon capacity of the graph, IEEE Trans. Inform, Theory 25 (1979), 1-7.

38. Metaheuristics, Progress as Real Problem Solvers Series: Operations Research /Computer Science Interfaces Series, Vol. 32 Ibaraki, Toshihide; Nonobe, Koji; Yagiura, Mutsunori (Eds.) 2005, XII, 414 p. 106 illus., Hardcover.

39. Petit J. Experiments on the Minimum Linear Arrangement Problem, Technical report LSI-Ol-7-R, Universität Politècnica de Catalunya, Departament de Llenguatges i Sistemes Informatics, 2001.

40. Rudich A., Zernik D., Zodik G. "Visage — Visualization of Attribute Graphs: A foundation for a Parallel Programming Environment," Environments and Tools for Parallel Scientific Computing North Holland, Ed. J.J. Dongarra and B. Tourancheau, pp. 171-192.

41. Shiloach ^"Arrangements of Planar Graphs on the Planar Lattice", Ph.D. Thesis, Weizmann Institute of Science, Rehovot, Israel, 1976.

42. Smart J. C. and Vemuri V. A-Vu: A Visualization Tool for Complex Software Systems. Proc. Symposium on Assessment of Quality Software Development Tools, IEEE Computer Society Press, New Orleans LA, May 27-29, 1992.

43. Storer J. A., "On Minimal Node-Cost, Planar Embeddings," Networks, vol. 14, pp. 181-212, 1984.

44. Sugiyama K., Tagawa S., Toda M. "Methods for visual understanding of hierarchical systems structures", IEEE Transactions on Systems, Man and Cybernetics 11, pp. 109-125, 1981.

45. Sugiyama K., Misue K. Visualization of Structural Information: Automatic Drawing of Compound Digraphs, IEEE Transactions on Systems, Man and Cybernetics, vol. 21, no. 4, pp. 876-892, 1991.

46. Tamassia R. "On Embedding a Graph in the Grid with the Minimum Number of Bends", SIAM J. Computing, vol. 16, no. 3, pp. 421-444, 1987.

47. Tamassia R., Tollis I. G. "Efficient Embedding of Planar Graphs in Linear Time," Proc. IEEE Int. Symp. on Circuits and Systems, pp. 495-498, Philadelphia, 1987.

48. Tamassia R., Tollis I. G. "Planar Grid Embedding in Linear Time," IEEE Trans, on Circuits and Systems, vol. CAS-36, no. 9, pp. 1230-1234, 1989.

49. The GNU General Public License,http://www.gnu.org/licenses/licenses.html51. yEd — Java Graph Editor,http://www.yworks.com/en/productsyedabout.htm.

50. Берж К. Теория графов и её применения.// М.: Изд-во иностр. лит, 1962.

51. Вороэюцов А. В. Алгебраические методы определения сложности: Препринт / ИПМ РАН. М., 2001. - №17. - 23 с.

52. Вороэюцов А. В. Прогнозирование и теория сложности: Препринт / ИПМ РАН. М, 2001. - №18. - 17 с.

53. Вороэюцов А.В. Индустрия знаний.// Информационные технологии и вычислительные ситемы, 1-2, 2003, С. 20.

54. Вороэюцов А.В. Задача о лидере и упорядочивание по вычислительной сложности.// Моделирование процессов управления. М.МФТИ, 2004. С. 218-228.

55. Вороэюцов А.В. Эвристические алгоритмы кластеризации для маломерных пространств.// Современные проблемы фундаментальных и прикладных наук: Труды XLV Научной Конференции МФТИ. Часть VIII.-Долгопрудный, 2003 С. 54.

56. Вороэюцов А.В., Винокуров Н.А. Два приближенных алгоритма решения задачи коммивояжера.// Моделирование процессов управления. М., 2004. С. 211-217.

57. Вороэюцов А.В. Критерии интеллектуальности искусственных систем: Препринт / ИПМ РАН. М., 2004. - №60. - 26 с.

58. Вороэюцов А.В. Критерии интеллектуальности искусственных систем.// Рефлексивные процессы и управление. Том 4, №2, 2004. С.18-29.

59. Ворожцов A.B. Мета-методы ЛЛР-программирования: Препринт / ИПМ РАН. М., 2005. - №43. - 18 с.

60. Журавлев Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов I, II, III.// Кибернетика, 1977, Я® 4, с. 14 21, № 6, с. 21 - 27; 191., № 2, с. 35 - 43.

61. Прасолов В. В. Задачи и теоремы линейной алгебры.// М.:Наука. Физ-матлит. 1996. 304 с.

62. Тамасия Р., Ресурс материалов по представлению графов, http://www.es.brown.edu/people/rt/ .

63. Турчин В. Ф. Феномен науки: Кибернетический подход к эволюции, М.: Наука, 295 е., 1993, http://pespmcl.vub.ac.be/POSBOOK.html.