Алгоритм раскраски графа с перекраской двуцветных компонент
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?
.Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры данных: учебник. - Нижний Новгород: Изд-во ННГУ, 2005. 307 с.
.Гэри М., Джонсон Д.: Вычислительные машины и трудно решаемые задачи, М.: Мир, 1982. - 416 с.
.Евстигнеев В.А. Применение теории графов в программировании./Под ред. А.П.Ершова. - М.: Наука. Главная редакция физико-математической литературы, 1985. - 352с.
.Кристофидес Н. Теория графов. Алгоритмическийподход. - М.: Мир, 1978. - 432с.
.Лекции по теории графов/Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. - М.: Наука. Гл. ред. физ.-мат. лит., 1990. - 384 с.
.Свами М., Тхуласираман К., Графы, сети и алгоритмы: Пер. с англ. - М.: Мир, 1984, - 455 с.
.Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. - 207 с.
.ШилдтГ., Полный справочник по Си++, 4-е издание.: Пер. с англ. - М.: Издательский дом Вильямс, 2008. - 800 с.
9.Brooks R.L., On coloring the nodes of a Network, Proc. Cambridge Phil. Soc., 1941, Vol., 37, p. 194 - 197.
.Lovasz L., Three short proofs in graph theory, J. Combinatorial Theory B, 1975, Vol., 19, p. 111 - 113.
.Melnikov L.S. and Vizing V.G., New proof of Brooks Theorem, J. Combinatorial Theory, 1969, Vol., 7, p. 289 - 290.
.Meynial H. On the perfect graph conjecture// DM - 1976. - V6 - p.339-342.
.DOT language - URL:://secure.wikimedia.org/wikipedia/en/wiki/DOT_language
.DOT language - URL:://www.graphviz.org/doc/info/lang.html
Приложение
Кодпрограммы.
#include
#include
#include
#include
#include
#include
#include
#include
#include
">#include
">#include
">#include
">#include
">#include
">#include
_vertex_info_t">#include_vertex_info_t
{id;color;
};_edge_info_t
{id;
};_info_t
{id;
};boost::adjacency_list::adjacency_iteratorgraph_adj_vertex_iter_t;_clock(clock_t start, clock_t end, int factor)
{= end - start;(diffticks*factor)/CLOCKS_PER_SEC;
}_clock_ms(clock_t start, clock_t end)
{_clock(start, end, 1000);
}_clock_sec(clock_t start, clock_t end)
{_clock(start, end, 1);
}_missing_incident_color(constVertexT&vert, constGraphT&graph)
adj_vert=boost::adjacent_vertices(vert,graph);::vectorpresent_colors;(autoi = adj_vert.first; i != adj_vert.second; ++i)
{color = graph[*i].color;(color > 0)
{_colors.push_back(color);
}
}(present_colors.size() == 0)
{1;
}::sort(present_colors.begin(), present_colors.end());(present_colors[0] != 1)1;(autoi = present_colors.begin(); i != present_colors.end(); ++i)
{j = i;(++j == present_colors.end())
{*i+1;
}(*j - *i > 1)
{*i+1;
}
}0;
}_if_all(InputIteratorT first, InputIteratorT last, OutputIteratorT out, PredicateTpred)
{= first;((i = find_if(i, last, pred)) != last)
*out++ = *i++;
}::iterator last, OutputIteratorT out, PredicateTpred)
{::map::iteratori = first;((i = find_if(i, last, pred)) != last)
*out++ = (*i++).first;
}_usage_pred_t
{:_usage_pred_t(size_tusage_cnt)
:m_usage_cnt(usage_cnt)
{}()(constColorUsagePairT&p) const
{(p.second == m_usage_cnt);
}:_tm_usage_cnt;
};_once_used_color_incident_vertices(constGraphT&graph, constVertexT&vert, VertexOutputIteratorT out)
{::pair vertex(autoi = adj_vert.first; i != adj_vert.second; ++i)
{(graph[*i].color != 0)
{
++color_usage[graph[*i].color];_vertex[graph[*i].color] = *i;
}
once_used_colors;_if_all(color_usage.begin(),color_usage.end(),std::back_inserter(once_used_colors),color_usage_pred_t(1));(autoi = once_used_colors.begin(); i != once_used_colors.end(); ++i)
{
*out++ = colored_vertex[*i];
}
}_paths_dfs_visitor : public boost::default_dfs_visitor
{:_paths_dfs_visitor(constVertexT&source_vertex, constVertexT&target_vertex,&out_iter)
:source(source_vertex), target(target_vertex), out(out_iter)
{}_vertex(VertexT&v, GraphT&g)
{(!current_chain.empty())
{_chain.push_back(v);
}(v == source)
{_chain.push_back(v);
}
if (v == target)
{
// сохранить в списке цепей
*out++ = current_chain;
}
}_vertex(VertexT&v, GraphT&g)
{(current_chain.empty())
{;
}(current_chain.back() == v)
{_chain.pop_back();
}
}:::listcurrent_chain;source;target;out;_vertex_ttarget_vertex;
};&ncp,&once_colored_vertices,&vert,&graph)
{(autoi = once_colored_vertices.begin(); i != once_colored_vertices.end(); ++i)
{(graph[*i].color == 0)
{;
}j = i;(++j != once_colored_vertices.end())
{(graph[*j].color == 0)
{;
}
// найти все пути между *iи *j
std::list(boost::num_vertices(graph)), *i);
// проверяем, естьлиунасдвуцветныепути(цепи)между*iи *j
for (auto k = paths.begin(); k != paths.end(); ++k)
{::mapend(); ++m)
{(path_colors.find(graph[*m].color) != path_colors.end())
{
++path_colors[graph[*m].color];
}
{_colors[graph[*m].color] = 1;
}
}
// все вершины в пути должны быть окрашены (0 не является цветом)
if (path_colors.find(0) != path_colors.end())
{;
}(path_colors.size() != 2)
{.first = *i;.second = *j;;
}
}
}
}
;
}_two_colored_component_dfs_visitor
{::list colors; //colors
};_two_colored_component(constVertexT&v, GraphT&graph)
{
}main(intargc, char **argv)
{::string input_filename("in.dot");::string output_filename("out.dot");::string report_filename("../../data/report.csv");
// аргументыкоманднойстроки
{::CmdLinecmd("Sub-optimal graph coloring", , "0.0");::ValueArginput_filename_arg("i", "input-filename",