44 #include <boost/graph/adjacency_list.hpp> 45 #include <boost/graph/adjacency_list_io.hpp> 51 using namespace boost;
52 int main(
int argc,
char* argv[])
54 using Graph1 = adjacency_list<vecS, vecS, undirectedS>;
55 using vertex_descriptor = graph_traits<Graph1>::vertex_descriptor;
56 using vertices_size_type = graph_traits<Graph1>::vertices_size_type;
57 using vertex_index_map = property_map<Graph1, vertex_index_t>::const_type;
58 std::vector<vertex_descriptor> verts;
61 printf(
"Provide data file in command.\n");
66 const int EDGE_FIELDS = 2;
67 const int P_FIELDS = 3;
68 const char* PROBLEM_TYPE =
"edge";
105 static const char* err_message[] = {
"more than one problem line.",
106 "wrong number of parameters in the problem line.",
107 "it is not a Max Flow problem line.",
108 "bad value of a parameter in the problem line.",
109 "can't obtain enough memory to solve this problem.",
110 "more than one line with the problem name.",
111 "can't read problem name.",
112 "problem description must be before node description.",
113 "this parser doesn't support multiply sources and sinks.",
114 "wrong number of parameters in the node line.",
115 "wrong value of parameters in the node line.",
117 "source and sink descriptions must be before arc descriptions.",
118 "too many arcs in the input.",
119 "wrong number of parameters in the arc line.",
120 "wrong value of parameters in the arc line.",
121 "unknown line type in the input.",
123 "not enough arcs in the input.",
124 "source or sink doesn't have incident arcs.",
125 "can't read anything from the input file."};
135 std::ifstream in(argv[1]);
137 while(std::getline(in, in_line))
160 sscanf(in_line.c_str(),
"%*c %4s %ld %ld", pr_type, &VERTICES, &number_of_edges) != P_FIELDS)
167 if(strcmp(pr_type, PROBLEM_TYPE))
174 if(VERTICES <= 0 || number_of_edges <= 0)
182 for(
long vi = 0; vi < VERTICES; ++vi)
184 verts.push_back(add_vertex(g1));
201 sscanf(in_line.c_str(),
"%*c %ld %ld", &tail, &head) != EDGE_FIELDS)
209 if(tail < 0 || tail > VERTICES || head < 0 || head > VERTICES)
215 graph_traits<Graph1>::edge_descriptor e1;
217 tie(e1, in1) = add_edge(verts[tail], verts[head], g1);
220 std::cerr <<
"unable to add edge (" << head <<
"," << tail <<
")" << std::endl;
251 if(no_elines < number_of_edges)
260 std::vector<vertices_size_type> color_vec(num_vertices(g1));
261 iterator_property_map<vertices_size_type*, vertex_index_map, vertices_size_type, vertices_size_type&> color(
262 &color_vec.front(),
get(vertex_index, g1));
264 std::cout <<
"Boost colors are: " << num_colors << std::endl;
270 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...
Boost-based implementation of a heuristic sequential coloring algorithm based on the descandant degre...
int main(int argc, char *argv[])
property_traits< ColorMap >::value_type degree_coloring(const VertexListGraph &G, ColorMap color)
coloring of a graph following the descandant degree of vertices