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

Аннотация

Выпускная квалификационная работа посвящена алгоритмическим проблемам задачи о правильной раскраске вершин графа, которая относится к классу NP-полных задач. В работе изучается эвристический алгоритм раскраски вершин графа с перекраской двуцветных компонент. Алгоритм запрограммирован на языке Си++ в среде программирования MicrosoftVisualStudio 2010, получены численные результаты.



Введение

произвольный граф алгоритм

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

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

Хроматическое число графа нельзя найти, зная только числа вершин и ребер графа. Недостаточно также знать степень каждой вершины, чтобы вычислить хроматическое число графа. В этом можно убедиться, рассматривая графы, приведенные на рис. 1(a) и 1(6). Эти графы имеют по вершин, ребер и одинаковые распределения степеней вершин . Однако хроматические числа данных графов равны 4 и 2 соответственно. При известных величинах n (число вершин), m (число ребер) и (степени вершин графа) можно получить верхнюю и нижнюю оценки для хроматического числа графа. Некоторые оценки хроматического числа мы рассмотрим ниже.

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

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

1) нахождение точных полиномиальных алгоритмов для ограниченных классов графов;

Рисунок1. Два графа с одинаковыми n,m и распределениями степеней вершин, но с различными хроматическими числами, (а) ч(G)=4, (б) ч(G)=2

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

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



Задача раскраски вершин графа. Некоторые примеры раскраски графа

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

Но задача раскраски в том «чистом» виде, в каком она рассматривается в теории, редко встречается на практике. Однако ее обобщения и разновидности (незначительно отличающиеся от нее) находят широкое применение в большом числе различных прикладных задач. Ниже приведены некоторые примеры раскраски, часто встречающиеся на практике. Естественно, что данный список этими примерами не ограничивается.

Составление графиков осмотра (проверки)

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

Распределение ресурсов

Пусть для выполнения каких-то n работ надо распределить m имеющихся в наличии ресурсов. Считаем, что каждая из работ выполняется за некоторый (одинаковый для всех работ) промежуток времени и что для выполнения i-й работы требуется подмножество ресурсов S_i.

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

Задача составления расписаний

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

Задача распределения оборудования

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

Построим граф G, положив VG= Vи объявив вершины v_iи v_jсмежными тогда и только тогда, когда для выполнения работ v_iи v_j требуется хотя бы один общий механизм. При правильной раскраске графа Gработы, соответствующие вершинам одного цвета, можно выполнять одновременно, а наименьшее время выполнения всех работ достигается при минимальной раскраске.

Оценки хроматического числа

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

Обозначим через множество всех порожденных подграфовПорождённый подграф -- подграф, порождённый множеством вершин исходного графа. графа G, а через д(G) - минимальную из степеней вершин графа G.

Теорема 1.Для любого графаG верно неравенство

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

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

Обозначим черезнаибольшую из степеней вершин графа .

Теорема 2.ПростойПростой граф -- граф, в котором нет кратных рёбер и петель. граф- - раскрашиваемый.

.

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

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

Очевидно, что для полных графов и циклов нечетной длины. Очень интересно то, что для всех остальных графов . Этот результат получен Бруксом[9] и доказывается ниже. Приводимое здесь доказательство предложили Мельников и Визинг[11]. Другое доказательство можно найти в работе [10].

Теорема 3(Брукс). Пусть G - связный простой граф. Если он не цикл нечетной длины и не полный граф, то есть когда G не содержит в качестве компонент граф или и цикл нечетной длины является компонентой G, то

Доказательство. Теорема очевидна для

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

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

Свойство 1. В любой ?-раскраске графа вершины, смежные с вершиной , раскрашиваются по-разному.

Пусть - вершины, смежные с вершиной . Пусть получают в раскраске графа цвета 1, 2,…,?соответственно. Обозначим черезпорожденный подграф на вершинах, которым присвоены цвета и .

Свойство 2. Вершины и находятся в одной компоненте связности.

В противном случае, заменяя цвета и в компоненте, содержащей , мы получим новую ?-раскраску графа , в которой и присвоен одинаковый цвет, что противоречит свойству 1.

Пусть - компонента, содержащая вершины и .

Свойство 3. - путь от вершины к вершине .

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



Аналогично можно показать, что степень в равна 1.

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

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

Свойство 4. и не имеют общих вершин, за исключением .

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

Продолжим доказательство теоремы. Установим теперь противоречие со свойством4.

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

Это завершает доказательство теоремы.

Алгоритм с перекраской двуцветных компонент

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

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

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

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

Вход: Граф G с ПН - упорядоченными вершинами.

Выход: Субоптимальная раскраска вершин.

начало

1. ;

2. для от до шаг 1 цикл

3. начало

4. m:= наименьший номер цвета, отсутствующего на вершинах, смежных с вершиной;

5. если m<=j то

6. окрасить вершину в цвет ;

7. иначе начало

8. К:= множество цветов, представленных ровно один раз на вершинах, смежных с вершиной ;

9. Если найдется пара , такая, что вершины и , смежные с, и окрашенные в цвета , не соединены двуцветной цепью то

10. начало

11. перекрасить ту компоненту двуцветного графа , которая содержит вершину ;

12. окрасить вершину в цвет ;

13. конец

14. иначеначало

15. ;

16. окрасить вершину в цвет ;

17. конец

18. конец

19. конец цикла;

конец

Поясним некоторые термины, которые встречаются в алгоритме:

Двуцветная цепь - это цепь графаG, которая окрашена только в два цвета. Двуцветная компонента - это подграф графа G, который окрашен только в два цвета.

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

Основные обозначения:

Вершины -

Цвета -

m - наименьший номер цвета, отсутствующего на вершинах, смежных с вершиной

Рисунок 2



1 шаг:

j = 1;

i = 1;

m=1;

Проверяем условие . Оно выполняется, поэтому мы окрашиваем вершину в цвет .

Переходим на следующую вершину.

2 шаг:

j = 1;

i = 2;

m=1;

Проверяем условие . Оно выполняется, поэтому мы окрашиваем вершину в цвет .

Переходим на 3-ю вершину.

3 шаг:

j = 1;

i = 3;

m=2;

Проверяем условие :. Оно не выполняется. Запишем множество цветовK={}. Это множество состоит из одного цвета, то есть, у нас нет пары .Поэтому мы данную вершину окрашиваем в минимальный свободный цвет, отсутствующий на соседних вершинах,:



Рисунок 3

4 шаг:

j = 2;

i = 4;

m=3;

Проверяем условие :. Оно не выполняется. Запишем множество K={}. Ищем пару , такую, что вершины и смежные и окрашенные в цвета , не соединены двуцветной цепью. Берем вершины и и рассмотрим эту пару. Она не соединена двуцветной цепью. По алгоритму, вершину окрашиваем в цвет вершины , то есть в . А вершину перекрашиваем в цвет .

Рисунок 4



5 шаг:

j = 2;

i = 5;

m=3;

Проверяем условие :. Оно не выполняется. Запишем множество . Ищем пару , такую, что вершины и смежные с и окрашенные в цвета , не соединены двуцветной цепью.Берем вершины и , которые окрашены в цвета и соответственно. Они соединены двуцветной цепью {}. Следовательно, и вершину окашиваем в цвет .

Рисунок 5

Граф окрашен.

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

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

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

Гэри, Джонсон и Стокмейер [2]доказали, что при даже проверка на 3-раскрашиваемоеть плоского графа является NP -полной задачей.

Рассмотрим теперь случай, когда алгоритм раскраски вершин графа с перекраской двухцветных компонент может быть отнесен к классу точных полиномиальных алгоритмов. В [12] описан класс графов, для которого исследуемый алгоритм всегда находит минимальную раскраску. Эти графы получили название графов Мейниеля: у всех таких графов каждый нечетный цикл содержит, по крайней мере, две хордыХорда - простая цепь или ребро, связывающая две не соседние вершины простого цикла.. Доказано, что всякий граф Мейниеля является совершенным графомГраф называется совершенным, еслидля любого его порожденного подграфа (где - хроматическое число графа G, - плотность графа G)..

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

Программа. Описание разработанной программы

На основании изученного материала была разработана и реализована программа, раскрашивающая вершины заданного графа. Программа разработана в среде VisualStudio2010 С++ с использованием библиотеки с графами BoostGraphLibrary.

Данная программа работает с файлами. Входные файлы должны содержать граф, описанный на языке DOT [13, 14] (см. рис.6) - специальный язык для описания графов. Это довольно простой способ описания графов, как люди, так и компьютерные программы могут легко его использовать.Принято файлы делать с расширением «.dot».

Рисунок 6. Входной файл

Выходной файл имеет такой же формат (см. рис.7).

Рисунок 7. Выходной файл

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

Опишем, как необходимо работать с программой.

Чтобы запустить программу, необходимо открыть командную строку, где лежит папка с программой (см. рис. 8):

Рисунок 8. Внешний вид программы

Далее необходимо прописать адрес, где лежит suboptimal_coloring.exe и затем, с помощью обозначений:

--input-filename- это откуда берётся выбранный файл;

--output-filename - это соответственно наоборот, куда он кладется;

написать полностью строку вызова файла. Она должна выглядеть следующим образом: D:\XXX\graph_coloring-r181\trunk>out\Debug-Win32\suboptimal_coloring.exe --input-filename data/exp1.1.dot --output-filename data/exp1.1.colored.dot --report-filename data/report.csv (см. рис. 9)

Рисунок 9. Строка вызова программы



Далее нажимаем enterи получаем результат программы (см. рис. 10)

Рисунок 10. Демонстрации работы программы

Так же, как было сказано выше, результат так же выводится еще и в файл (см. рис 7). Там видно, какими цветами окрашена каждая из вершин.

Результат работы программы (файл) сохраняется в папке data, которая находится по адресу Имя_папки_с_программой\trunk\data, с названием ХХХ.colored.dot, ХХХ - название изначального файла.

По необходимости, если граф нужно нарисовать, можно воспользоваться программой Graphviz[15].

Graphviz -- разработанный специалистами лаборатории AT&T пакет утилит по автоматической визуализации графов, заданных в виде описания на языке «dot». Пакет распространяется с открытыми исходными файлами по лицензии CPL (CommonPublicLicense) и работает на многих операционных системах, включая Linux, Mac OS, Unix-подобные, MicrosoftWindows.

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

В пакет утилит входит программа «dot», автоматический визуализатор ориентированных графов, который принимает на вход текстовый файл с представлением графа в виде смежных списков, а на выходе формирует граф в виде графического, векторного или текстового файла.

Входной файл для программы «dot» является обычным текстовым файлом на специальном языке описания. Структура файла очень простая(см. рис.6).

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

Приведем пример работы программы Graphviz на нашем примере, который показан на рис. 6. На рис.11 видно как программа нарисовала 5-ти вершинный неориентированный граф.

Рисунок 11. Graphviz

Проведенный эксперимент

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

Рисунок 12. Графы Мейниеля



То есть у всех таких графов каждый нечетный цикл содержит, по крайней мере, две хорды.

Для рассмотрения были выбраны графы (см. рис. 13), которые удовлетворяют условию графов Мейниеля:

Рисунок 13. Графы, удовлетворяющие структуре графов Мейниеля

Эти графы представляет собой некоторый подкласс класса графов Мейниеля.

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

Ниже приведен график работы программы (см. рис.14):

Рисунок 14. График работы программы



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



Заключение

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



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

1.Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры данных: учебник. - Нижний Новгород: Изд-во ННГУ, 2005. 307 с.

2.Гэри М., Джонсон Д.: Вычислительные машины и трудно решаемые задачи, М.: Мир, 1982. - 416 с.

3.Евстигнеев В.А. Применение теории графов в программировании./Под ред. А.П.Ершова. - М.: Наука. Главная редакция физико-математической литературы, 1985. - 352с.

4.Кристофидес Н. Теория графов. Алгоритмическийподход. - М.: Мир, 1978. - 432с.

5.Лекции по теории графов/Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. - М.: Наука. Гл. ред. физ.-мат. лит., 1990. - 384 с.

6.Свами М., Тхуласираман К., Графы, сети и алгоритмы: Пер. с англ. - М.: Мир, 1984, - 455 с.

7.Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. - 207 с.

8.ШилдтГ., Полный справочник по Си++, 4-е издание.: Пер. с англ. - М.: Издательский дом «Вильямс», 2008. - 800 с.

9.Brooks R.L., On coloring the nodes of a Network, Proc. Cambridge Phil. Soc., 1941, Vol., 37, p. 194 - 197.

10.Lovasz L., Three short proofs in graph theory, J. Combinatorial Theory B, 1975, Vol., 19, p. 111 - 113.

11.Melnikov L.S. and Vizing V.G., New proof of Brooks' Theorem, J. Combinatorial Theory, 1969, Vol., 7, p. 289 - 290.

12.Meynial H. On the perfect graph conjecture// DM - 1976. - V6 - p.339-342.

13.DOT language - URL:

https://secure.wikimedia.org/wikipedia/en/wiki/DOT_language

14.DOT language - URL:

http://www.graphviz.org/doc/info/lang.html

Приложение

Кодпрограммы.

#include<iostream>

#include<fstream>

#include<string>

#include<algorithm>

#include<map>

#include<stdexcept>

#include<iterator>

#include<cassert>

#include<tclap/CmdLine.h>

#include<boost/graph/adjacency_list.hpp>

#include<boost/graph/graphviz.hpp>

#include<boost/graph/smallest_last_ordering.hpp>

#include<boost/property_map/shared_array_property_map.hpp>

#include<boost/graph/depth_first_search.hpp>

#include<boost/graph/undirected_dfs.hpp>

#include<boost/graph/st_connected.hpp>

structgraph_vertex_info_t

{

int id;

int color;

};

structgraph_edge_info_t

{

int id;

};

structgraph_info_t

{

int id;

};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,

graph_vertex_info_t, graph_edge_info_t,

graph_info_t, boost::listS>

graph_t;

typedef boost::graph_traits<graph_t>::vertex_descriptorgraph_vertex_t;

typedef boost::graph_traits<graph_t>::edge_descriptorgraph_edge_t;

typedef boost::graph_traits<graph_t>::vertex_iteratorgraph_vertex_iter_t;

typedef boost::graph_traits<graph_t>::in_edge_iteratorgraph_in_edge_iter_t;

typedef boost::graph_traits<graph_t>::out_edge_iteratorgraph_out_edge_iter_t;

typedef boost::graph_traits<graph_t>::adjacency_iteratorgraph_adj_vertex_iter_t;

doublediff_clock(clock_t start, clock_t end, int factor)

{

doublediffticks = end - start;

return (diffticks*factor)/CLOCKS_PER_SEC;

}

doublediff_clock_ms(clock_t start, clock_t end)

{

returndiff_clock(start, end, 1000);

}

doublediff_clock_sec(clock_t start, clock_t end)

{

returndiff_clock(start, end, 1);

}

template<classVertexT, classGraphT>

intminimal_missing_incident_color(constVertexT&vert, constGraphT&graph)

{

std::pair<graph_adj_vertex_iter_t, graph_adj_vertex_iter_t>adj_vert = boost::adjacent_vertices(vert, graph);

std::vector<int>present_colors;

for (autoi = adj_vert.first; i != adj_vert.second; ++i)

{

int color = graph[*i].color;

if (color > 0)

{

present_colors.push_back(color);

}

}

if (present_colors.size() == 0)

{

return 1;

}

std::sort(present_colors.begin(), present_colors.end());

if (present_colors[0] != 1)

return 1;

for (autoi = present_colors.begin(); i != present_colors.end(); ++i)

{

auto j = i;

if (++j == present_colors.end())

{

return *i+1;

}

elseif (*j - *i > 1)

{

return *i+1;

}

}

return 0;

}

template<classInputIteratorT, classOutputIteratorT, classPredicateT>

voidfind_if_all(InputIteratorT first, InputIteratorT last, OutputIteratorT out, PredicateTpred)

{

InputIteratorTi = first;

while ((i = find_if(i, last, pred)) != last)

*out++ = *i++;

}

template<classOutputIteratorT, classPredicateT>

voidfind_if_all(std::map<int, size_t>::iterator first, std::map<int, size_t>::iterator last, OutputIteratorT out, PredicateTpred)

{

std::map<int, size_t>::iteratori = first;

while ((i = find_if(i, last, pred)) != last)

*out++ = (*i++).first;

}

template<classColorMapT>

classcolor_usage_pred_t

{

public:

color_usage_pred_t(size_tusage_cnt)

:m_usage_cnt(usage_cnt)

{}

template<classColorUsagePairT>

booloperator()(constColorUsagePairT&p) const

{

return (p.second == m_usage_cnt);

}

private:

constsize_tm_usage_cnt;

};

template<classGraphT, classVertexT, classVertexOutputIteratorT>

voidexactly_once_used_color_incident_vertices(constGraphT&graph, constVertexT&vert, VertexOutputIteratorT out)

{

std::pair<graph_adj_vertex_iter_t, graph_adj_vertex_iter_t>adj_vert = boost::adjacent_vertices(vert, graph);

std::map<int, size_t>color_usage; // color -> usage count

std::map<int, VertexT>colored_vertex; // color -> vertex

for (autoi = adj_vert.first; i != adj_vert.second; ++i)

{

if (graph[*i].color != 0)

{

++color_usage[graph[*i].color];

colored_vertex[graph[*i].color] = *i;

}

}

std::vector<int>once_used_colors;

find_if_all(color_usage.begin(), color_usage.end(), std::back_inserter(once_used_colors), color_usage_pred_t<std::map<int, size_t>>(1));

for (autoi = once_used_colors.begin(); i != once_used_colors.end(); ++i)

{

*out++ = colored_vertex[*i];

}

}

template<classVertexT, classPathsOutputIterator>

classvertex_paths_dfs_visitor : public boost::default_dfs_visitor

{

public:

vertex_paths_dfs_visitor(constVertexT&source_vertex, constVertexT&target_vertex,

PathsOutputIterator&out_iter)

:source(source_vertex), target(target_vertex), out(out_iter)

{}

template<classGraphT>

voiddiscover_vertex(VertexT&v, GraphT&g)

{

if (!current_chain.empty())

{

current_chain.push_back(v);

}

elseif (v == source)

{

current_chain.push_back(v);

}

if (v == target)

{

// сохранить в списке цепей

*out++ = current_chain;

}

}

template<classGraphT>

voidfinish_vertex(VertexT&v, GraphT&g)

{

if (current_chain.empty())

{

return;

}

if (current_chain.back() == v)

{

current_chain.pop_back();

}

}

private:

std::list<VertexT>current_chain;

VertexT source;

VertexT target;

PathsOutputIterator out;

graph_vertex_ttarget_vertex;

};

template<classVertexSetT, classVertexT, classGraphT>

bool pair_non_connected_by_two_colored_chain(std::pair<VertexT,VertexT>&ncp,

constVertexSetT&once_colored_vertices,

constVertexT&vert,

constGraphT&graph)

{

for (autoi = once_colored_vertices.begin(); i != once_colored_vertices.end(); ++i)

{

if (graph[*i].color == 0)

{

continue;

}

auto j = i;

while (++j != once_colored_vertices.end())

{

if (graph[*j].color == 0)

{

continue;

}

// найти все пути между *iи *j

std::list<std::list<VertexT>> paths;

boost::depth_first_search(graph,

vertex_paths_dfs_visitor<VertexT,std::back_insert_iterator<std::list<std::list<VertexT>>>>(*i,*j,std::back_inserter(paths)),

boost::vector_property_map<boost::default_color_type>(boost::num_vertices(graph)), *i);

// проверяем, естьлиунасдвуцветныепути(цепи)между*iи *j

for (auto k = paths.begin(); k != paths.end(); ++k)

{

std::map<int,size_t>path_colors; // color -> usage

for (auto m = k->begin(); m != k->end(); ++m)

{

if (path_colors.find(graph[*m].color) != path_colors.end())

{

++path_colors[graph[*m].color];

}

else

{

path_colors[graph[*m].color] = 1;

}

}

// все вершины в пути должны быть окрашены (0 не является цветом)

if (path_colors.find(0) != path_colors.end())

{

break;

}

if (path_colors.size() != 2)

{

ncp.first = *i;

ncp.second = *j;

returntrue;

}

}

}

}

returnfalse;

}

structrecolor_two_colored_component_dfs_visitor

{

std::list<int> colors; //colors

};

template<classVertexT, classGraphT>

voidrecolor_two_colored_component(constVertexT&v, GraphT&graph)

{

}

int main(intargc, char **argv)

{

std::string input_filename("in.dot");

std::string output_filename("out.dot");

std::string report_filename("../../data/report.csv");

// аргументыкоманднойстроки

try

{

TCLAP::CmdLinecmd("Sub-optimal graph coloring", ' ', "0.0");

TCLAP::ValueArg<std::string>input_filename_arg("i", "input-filename",

"Input filename",

true,

input_filename,

"string",

cmd);

TCLAP::ValueArg<std::string>output_filename_arg("o", "output-filename",

"Output filename",

false,

output_filename,

"string",

cmd);

TCLAP::ValueArg<std::string>report_filename_arg("r", "report-filename",

"CSV report filename",

false,

report_filename,

"string",

cmd);

// разборкоманднойстроки

cmd.parse(argc, argv);

input_filename = input_filename_arg.getValue();

output_filename = output_filename_arg.getValue();

report_filename = report_filename_arg.getValue();

}

catch (TCLAP::ArgException&excp)

{

std::cerr<<"TCLAP Error: "<<excp.error();

return 1;

}

std::ifstream input(input_filename);

if (!input.is_open())

{

std::cerr<<"Can't open input file \""<<input_filename<<"\""<<std::endl;

return 2;

}

graph_t graph;

boost::dynamic_propertiesdp;

dp.property("id", boost::get(&graph_vertex_info_t::id, graph));

dp.property("color", boost::get(&graph_vertex_info_t::color, graph));

// чтениеграфаизфайла

boost::read_graphviz(input, graph, dp, "id");

input.close();

// раскраскаграфа

std::clog <<"Coloring graph \""<<input_filename<<"\":"<<std::endl;

clock_tstart_time = clock();

// ПН - упорядочивание (Smallest-last order of graph vertices)

std::vector<graph_vertex_t>sl_ordered_vertices = boost::smallest_last_vertex_ordering(graph);

std::clog <<"Smallest-last vertex ordering: ";

std::for_each(sl_ordered_vertices.rbegin(), sl_ordered_vertices.rend(), [&graph](graph_vertex_t&v){std::clog << graph[v].id <<" ";});

std::clog <<std::endl;

int j = 1;

for (autocurrent_vertex = sl_ordered_vertices.rbegin(); current_vertex != sl_ordered_vertices.rend(); ++current_vertex)

{

std::clog <<"Coloring vertex "<< graph[*current_vertex].id <<"..."<<std::endl;

// минимальныйотсутствующийцветнасмежнойвершине

int m = minimal_missing_incident_color(*current_vertex, graph);

assert(m > 0);

if (m <= j)

{

graph[*current_vertex].color = m;

}

else

{

// цвета, используемые один раз на смежных вершинах

std::vector<graph_vertex_t>once_colored_vertices;

exactly_once_used_color_incident_vertices(graph, *current_vertex, std::back_inserter(once_colored_vertices));

std::pair<graph_vertex_t, graph_vertex_t>ncp;

if (pair_non_connected_by_two_colored_chain(ncp, once_colored_vertices, *current_vertex, graph)) // парасуществует

{

recolor_two_colored_component(*current_vertex, graph); // перекраскакомпонентграфа

graph[*current_vertex].color = graph[ncp.first].color;

}

else

{

++j;

graph[*current_vertex].color = j;

}

}

#ifdef _DEBUG

{

std::ofstream output("latest_coloring.dot");

if (!output.is_open())

{

std::cerr<<"Can't open output file \""<<"latest_coloring.dot"<<"\""<<std::endl;

return 4;

}

boost::write_graphviz_dp(output, graph, dp, "id");

output.close();

}

#endif

}

clock_tend_time = clock();

doublemodel_time = diff_clock_sec(start_time, end_time);

std::map<int,size_t>color_usage;

std::for_each(boost::vertices(graph).first, boost::vertices(graph).second, [&color_usage,&graph](constgraph_vertex_t&v){++color_usage[graph[v].color];});

// Вывестирезультат

// Выводвконсоль

std::cout.precision(3);

std::cout<<std::fixed;

std::cout<<std::endl;

std::cout<<"Input graph filename: "<<input_filename<<std::endl

<<"Output graph filename: "<<output_filename<<std::endl

<<"Used colors: "<<color_usage.size() <<std::endl

<<"Colors usage: ";

std::for_each(color_usage.begin(), color_usage.end(), [](conststd::pair<int,size_t>&color_usage){

std::cout<<"("<<color_usage.first<<" - "<<color_usage.second<<") ";});

std::cout<<std::endl

<<"Time (sec): "<<model_time<<std::endl;

// csv file

std::ofstream results(report_filename, std::fstream::app);

if (!results.is_open())

{

std::cerr<<"Can't open report file \""<<report_filename<<"\""<<std::endl;

return 3;

}

results.precision(3);

results<<std::fixed;

results<<input_filename

<<","<<output_filename

<<","<<color_usage.size()

<<","<<start_time

<<","<<model_time

<<std::endl;

results.close();

// выводраскрашенногографа

std::ofstream output(output_filename);

if (!output.is_open())

{

std::cerr<<"Can't open output file \""<<output_filename<<"\""<<std::endl;

return 4;

}

boost::write_graphviz_dp(output, graph, dp, "id");

output.close();

return 0;

}

Размещено на Allbest.ru