45 #include <boost/graph/adjacency_list.hpp> 46 #include <boost/graph/adjacency_list_io.hpp> 52 using namespace boost;
53 int main(
int argc,
char* argv[])
55 using Graph1 = adjacency_list<vecS, vecS, undirectedS>;
56 using vertex_descriptor = graph_traits<Graph1>::vertex_descriptor;
57 using vertices_size_type = graph_traits<Graph1>::vertices_size_type;
58 using vertex_index_map = property_map<Graph1, vertex_index_t>::const_type;
59 std::vector<vertex_descriptor> verts;
62 printf(
"Provide data file in command.\n");
67 const int EDGE_FIELDS = 2;
68 const int P_FIELDS = 3;
69 const char* PROBLEM_TYPE =
"edge";
106 static const char* err_message[] = {
"more than one problem line.",
107 "wrong number of parameters in the problem line.",
108 "it is not a Max Flow problem line.",
109 "bad value of a parameter in the problem line.",
110 "can't obtain enough memory to solve this problem.",
111 "more than one line with the problem name.",
112 "can't read problem name.",
113 "problem description must be before node description.",
114 "this parser doesn't support multiply sources and sinks.",
115 "wrong number of parameters in the node line.",
116 "wrong value of parameters in the node line.",
118 "source and sink descriptions must be before arc descriptions.",
119 "too many arcs in the input.",
120 "wrong number of parameters in the arc line.",
121 "wrong value of parameters in the arc line.",
122 "unknown line type in the input.",
124 "not enough arcs in the input.",
125 "source or sink doesn't have incident arcs.",
126 "can't read anything from the input file."};
136 std::ifstream in(argv[1]);
138 while(std::getline(in, in_line))
161 sscanf(in_line.c_str(),
"%*c %4s %ld %ld", pr_type, &VERTICES, &number_of_edges) != P_FIELDS)
168 if(strcmp(pr_type, PROBLEM_TYPE))
175 if(VERTICES <= 0 || number_of_edges <= 0)
183 for(
long vi = 0; vi < VERTICES; ++vi)
185 verts.push_back(add_vertex(g1));
202 sscanf(in_line.c_str(),
"%*c %ld %ld", &tail, &head) != EDGE_FIELDS)
210 if(tail < 0 || tail > VERTICES || head < 0 || head > VERTICES)
216 graph_traits<Graph1>::edge_descriptor e1;
218 tie(e1, in1) = add_edge(verts[tail], verts[head], g1);
221 std::cerr <<
"unable to add edge (" << head <<
"," << tail <<
")" << std::endl;
252 if(no_elines < number_of_edges)
261 std::vector<vertices_size_type> color_vec(num_vertices(g1));
262 iterator_property_map<vertices_size_type*, vertex_index_map, vertices_size_type, vertices_size_type&> color(
263 &color_vec.front(),
get(vertex_index, g1));
265 std::cout <<
"Boost colors are: " << num_colors << std::endl;
271 printf(
"\nline %ld of input - %s\n", no_lines, err_message[err_no]);
This algorithm is to find coloring of a graph Algorithm: Let G = (V,E) be a graph with vertices v_1...
property_traits< ColorMap >::value_type dsatur2_coloring(const VertexListGraph &G, ColorMap color)
coloring of a graph following the DSATUR heuristic (version2)
Boost-based implementation of a heuristic sequential coloring algorithm based on the work of Daniel B...
int main(int argc, char *argv[])