Алгоритм раскраски графа с перекраской двуцветных компонент
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
"Input filename",,_filename,
"string",);::ValueArgoutput_filename_arg("o", "output-filename",
"Output filename",,_filename,
"string",);::ValueArgreport_filename_arg("r", "report-filename",
"CSV report filename",,_filename,
"string",);
// разборкоманднойстроки.parse(argc, argv);_filename = input_filename_arg.getValue();_filename = output_filename_arg.getValue();_filename = report_filename_arg.getValue();
}(TCLAP::ArgException&excp)
{::cerr<<"TCLAP Error: "<<excp.error();1;
}::ifstream input(input_filename);(!input.is_open())
{::cerr<<"Cant open input file \""<<input_filename<<"\""<<std::endl;2;
}_t graph;::dynamic_propertiesdp;.property("id", boost::get(&graph_vertex_info_t::id, graph));.property("color", boost::get(&graph_vertex_info_t::color, graph));
// чтениеграфаизфайла::read_graphviz(input, graph, dp, "id");.close();
// раскраскаграфа::clog <<"Coloring graph \""<<input_filename<<"\":"<<std::endl;_tstart_time = clock();
sl_ordered_vertices = boost::smallest_last_vertex_ordering(graph);::clog sl_ordered_vertices = boost::smallest_last_vertex_ordering(graph);::clog <<"Smallest-last vertex ordering: ";::for_each(sl_ordered_vertices.rbegin(), sl_ordered_vertices.rend(), [&graph](graph_vertex_t&v){std::clog << graph[v].id <<" ";});::clog <<std::endl;j = 1;(autocurrent_vertex = sl_ordered_vertices.rbegin(); current_vertex != sl_ordered_vertices.rend(); ++current_vertex)
{::clog <<"Coloring vertex "<< graph[*current_vertex].id <<"..."<<std::endl;
// минимальныйотсутствующийцветнасмежнойвершинеm = minimal_missing_incident_color(*current_vertex, graph);(m > 0);(m <= j)
{[*current_vertex].color = m;
}
else
{
// цвета, используемые один раз на смежных вершинах
std::vectorncp;(pair_non_connected_by_two_colored_chain(ncp, once_colored_vertices, *current_vertex, graph))// парасуществует
{_two_colored_component(*current_vertex, graph);// перекраскакомпонентграфа[*current_vertex].color = graph[ncp.first].color;
}
{
++j;[*current_vertex].color = j;
}
}
#ifdef _DEBUG
{::ofstream output("latest_coloring.dot");(!output.is_open())
{::cerr<<"Cant open output file \""<<"latest_coloring.dot"<<"\""<<std::endl;4;
}::write_graphviz_dp(output, graph, dp, "id");.close();
}
#endif
}_tend_time = clock();_time = diff_clock_sec(start_time, end_time);::mapcolor_usage;::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;::cout<<std::endl;::cout<<"Input graph filename: "<<input_filename<<std::endl
<<"Output graph filename: "<<output_filename<<std::endl
<<"Used colors: "<<color_usage.size() <<std::endl
&color_usage){::cout&color_usage){::cout<<"("<<color_usage.first<<" - "<<color_usage.second<<") ";});::cout<<std::endl
<<"Time (sec): "<<model_time<<std::endl;
// csv file::ofstream results(report_filename, std::fstream::app);(!results.is_open())
{::cerr<<"Cant open report file \""<<report_filename<<"\""<<std::endl;3;
}.precision(3);<<std::fixed;<<input_filename
<<","<<output_filename
<<","<<color_usage.size()
<<","<<start_time
<<","<<model_time
<<std::endl;.close();
// выводраскрашенногографа::ofstream output(output_filename);(!output.is_open())
{::cerr<<"Cant open output file \""<<output_filename<<"\""<<std::endl;4;
}::write_graphviz_dp(output, graph, dp, "id");.close();0;
}