50 #include <boost/graph/adjacency_list.hpp> 51 #include <boost/graph/adjacency_list_io.hpp> 57 using namespace boost;
58 int main(
int argc,
char* argv[])
60 using Graph1 = adjacency_list<vecS, vecS, undirectedS>;
61 using vertex_descriptor = graph_traits<Graph1>::vertex_descriptor;
62 using vertices_size_type = graph_traits<Graph1>::vertices_size_type;
63 using vertex_index_map = property_map<Graph1, vertex_index_t>::const_type;
64 std::vector<vertex_descriptor> verts;
67 printf(
"Provide data file in command.\n");
72 const int EDGE_FIELDS = 2;
73 const int P_FIELDS = 3;
74 const char* PROBLEM_TYPE =
"edge";
111 static const char* err_message[] = {
"more than one problem line.",
112 "wrong number of parameters in the problem line.",
113 "it is not a Max Flow problem line.",
114 "bad value of a parameter in the problem line.",
115 "can't obtain enough memory to solve this problem.",
116 "more than one line with the problem name.",
117 "can't read problem name.",
118 "problem description must be before node description.",
119 "this parser doesn't support multiply sources and sinks.",
120 "wrong number of parameters in the node line.",
121 "wrong value of parameters in the node line.",
123 "source and sink descriptions must be before arc descriptions.",
124 "too many arcs in the input.",
125 "wrong number of parameters in the arc line.",
126 "wrong value of parameters in the arc line.",
127 "unknown line type in the input.",
129 "not enough arcs in the input.",
130 "source or sink doesn't have incident arcs.",
131 "can't read anything from the input file."};
141 std::ifstream in(argv[1]);
143 while(std::getline(in, in_line))
166 sscanf(in_line.c_str(),
"%*c %4s %ld %ld", pr_type, &VERTICES, &number_of_edges) != P_FIELDS)
173 if(strcmp(pr_type, PROBLEM_TYPE))
180 if(VERTICES <= 0 || number_of_edges <= 0)
188 for(
long vi = 0; vi < VERTICES; ++vi)
190 verts.push_back(add_vertex(g1));
207 sscanf(in_line.c_str(),
"%*c %ld %ld", &tail, &head) != EDGE_FIELDS)
215 if(tail < 0 || tail > VERTICES || head < 0 || head > VERTICES)
221 graph_traits<Graph1>::edge_descriptor e1;
223 tie(e1, in1) = add_edge(verts[tail], verts[head], g1);
226 std::cerr <<
"unable to add edge (" << head <<
"," << tail <<
")" << std::endl;
257 if(no_elines < number_of_edges)
266 std::vector<vertices_size_type> color_vec(num_vertices(g1));
267 iterator_property_map<vertices_size_type*, vertex_index_map, vertices_size_type, vertices_size_type&> color(
268 &color_vec.front(),
get(vertex_index, g1));
270 std::cout <<
"Boost colors are: " << num_colors << std::endl;
276 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...
int main(int argc, char *argv[])
Boost-based implementation of a heuristic sequential coloring algorithm based on the work of Daniel B...
property_traits< ColorMap >::value_type dsatur_coloring(const VertexListGraph &G, ColorMap color)
coloring of a graph following the DSATUR heuristic (version1)