PandA-2024.02
test_degree_coloring.cpp
Go to the documentation of this file.
1 /*
2  *
3  * _/_/_/ _/_/ _/ _/ _/_/_/ _/_/
4  * _/ _/ _/ _/ _/_/ _/ _/ _/ _/ _/
5  * _/_/_/ _/_/_/_/ _/ _/_/ _/ _/ _/_/_/_/
6  * _/ _/ _/ _/ _/ _/ _/ _/ _/
7  * _/ _/ _/ _/ _/ _/_/_/ _/ _/
8  *
9  * ***********************************************
10  * PandA Project
11  * URL: http://panda.dei.polimi.it
12  * Politecnico di Milano - DEIB
13  * System Architectures Group
14  * ***********************************************
15  * Copyright (C) 2004-2024 Politecnico di Milano
16  *
17  * This file is part of the PandA framework.
18  *
19  * The PandA framework is free software; you can redistribute it and/or modify
20  * it under the terms of the GNU General Public License as published by
21  * the Free Software Foundation; either version 3 of the License, or
22  * (at your option) any later version.
23  *
24  * This program is distributed in the hope that it will be useful,
25  * but WITHOUT ANY WARRANTY; without even the implied warranty of
26  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27  * GNU General Public License for more details.
28  *
29  * You should have received a copy of the GNU General Public License
30  * along with this program. If not, see <http://www.gnu.org/licenses/>.
31  *
32  */
43 #include "degree_coloring.hpp"
44 #include <boost/graph/adjacency_list.hpp>
45 #include <boost/graph/adjacency_list_io.hpp>
46 #include <cstring>
47 #include <fstream>
48 #include <iosfwd>
49 #include <utility>
50 
51 using namespace boost;
52 int main(int argc, char* argv[])
53 {
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;
59  if(argc < 2)
60  {
61  printf("Provide data file in command.\n");
62  exit(1);
63  }
64  // read Graph1
65  Graph1 g1;
66  const int EDGE_FIELDS = 2; /* no of fields in edge line */
67  const int P_FIELDS = 3; /* no of fields in problem line */
68  const char* PROBLEM_TYPE = "edge"; /* name of problem type*/
69  long VERTICES, /*number of vertices*/
70  number_of_edges, /* number of edges and nodes */
71  head, tail;
72 
73  long no_lines = 0, /* no of current input line */
74  no_plines = 0, /* no of problem-lines */
75  no_elines = 0; /* no of edge-lines */
76 
77  std::string in_line; /* for reading input line */
78  char pr_type[5]; /* for reading type of the problem */
79 
80  int err_no; /* no of detected error */
81 
82  /* -------------- error numbers & error messages ---------------- */
83  const int EN1 = 0;
84  const int EN2 = 1;
85  const int EN3 = 2;
86  const int EN4 = 3;
87  // const int EN6 = 4;
88  // const int EN10 = 5;
89  // const int EN7 = 6;
90  const int EN8 = 7;
91  // const int EN9 = 8;
92  // const int EN11 = 9;
93  // const int EN12 = 10;
94  // const int EN13 = 11;
95  // const int EN14 = 12;
96  // const int EN16 = 13;
97  const int EN15 = 14;
98  const int EN17 = 15;
99  const int EN18 = 16;
100  const int EN21 = 17;
101  const int EN19 = 18;
102  // const int EN20 = 19;
103  const int EN22 = 20;
104 
105  static const char* err_message[] = {/* 0*/ "more than one problem line.",
106  /* 1*/ "wrong number of parameters in the problem line.",
107  /* 2*/ "it is not a Max Flow problem line.",
108  /* 3*/ "bad value of a parameter in the problem line.",
109  /* 4*/ "can't obtain enough memory to solve this problem.",
110  /* 5*/ "more than one line with the problem name.",
111  /* 6*/ "can't read problem name.",
112  /* 7*/ "problem description must be before node description.",
113  /* 8*/ "this parser doesn't support multiply sources and sinks.",
114  /* 9*/ "wrong number of parameters in the node line.",
115  /*10*/ "wrong value of parameters in the node line.",
116  /*11*/ " ",
117  /*12*/ "source and sink descriptions must be before arc descriptions.",
118  /*13*/ "too many arcs in the input.",
119  /*14*/ "wrong number of parameters in the arc line.",
120  /*15*/ "wrong value of parameters in the arc line.",
121  /*16*/ "unknown line type in the input.",
122  /*17*/ "reading error.",
123  /*18*/ "not enough arcs in the input.",
124  /*19*/ "source or sink doesn't have incident arcs.",
125  /*20*/ "can't read anything from the input file."};
126  /* --------------------------------------------------------------- */
127 
128  /* The main loop:
129  - reads the line of the input,
130  - analyses its type,
131  - checks correctness of parameters,
132  - puts data to the arrays,
133  - does service functions
134  */
135  std::ifstream in(argv[1]);
136 
137  while(std::getline(in, in_line))
138  {
139  ++no_lines;
140 
141  switch(in_line[0])
142  {
143  case 'c': /* skip lines with comments */
144  case '\n': /* skip empty lines */
145  case '\0': /* skip empty lines at the end of file */
146  break;
147 
148  case 'p': /* problem description */
149  {
150  if(no_plines > 0)
151  /* more than one problem line */
152  {
153  err_no = EN1;
154  goto error;
155  }
156 
157  no_plines = 1;
158  if(
159  /* reading problem line: type of problem, no of nodes, no of arcs */
160  sscanf(in_line.c_str(), "%*c %4s %ld %ld", pr_type, &VERTICES, &number_of_edges) != P_FIELDS)
161  /*wrong number of parameters in the problem line*/
162  {
163  err_no = EN2;
164  goto error;
165  }
166 
167  if(strcmp(pr_type, PROBLEM_TYPE))
168  /*wrong problem type*/
169  {
170  err_no = EN3;
171  goto error;
172  }
173 
174  if(VERTICES <= 0 || number_of_edges <= 0)
175  /*wrong value of no of edges or nodes*/
176  {
177  err_no = EN4;
178  goto error;
179  }
180 
181  {
182  for(long vi = 0; vi < VERTICES; ++vi)
183  {
184  verts.push_back(add_vertex(g1));
185  }
186  }
187  break;
188  }
189 
190  case 'e': /* edge description */
191  {
192  if(no_plines == 0)
193  /* there was not problem line above */
194  {
195  err_no = EN8;
196  goto error;
197  }
198 
199  if(
200  /* reading an edge description */
201  sscanf(in_line.c_str(), "%*c %ld %ld", &tail, &head) != EDGE_FIELDS)
202  /* arc description is not correct */
203  {
204  err_no = EN15;
205  goto error;
206  }
207  --tail; // index from 0, not 1
208  --head;
209  if(tail < 0 || tail > VERTICES || head < 0 || head > VERTICES)
210  /* wrong value of nodes */
211  {
212  err_no = EN17;
213  goto error;
214  }
215  graph_traits<Graph1>::edge_descriptor e1;
216  bool in1;
217  tie(e1, in1) = add_edge(verts[tail], verts[head], g1);
218  if(!in1)
219  {
220  std::cerr << "unable to add edge (" << head << "," << tail << ")" << std::endl;
221  exit(1);
222  }
223 
224  ++no_elines;
225  break;
226  }
227  default:
228  {
229  /* unknown type of line */
230  err_no = EN18;
231  goto error;
232  }
233 
234  } /* end of switch */
235  } /* end of input loop */
236 
237  /* ----- all is read or error while reading ----- */
238 
239  if(!in.eof()) /* reading error */
240  {
241  err_no = EN21;
242  goto error;
243  }
244 
245  if(no_lines == 0) /* empty input */
246  {
247  err_no = EN22;
248  goto error;
249  }
250 
251  if(no_elines < number_of_edges) /* not enough arcs */
252  {
253  err_no = EN19;
254  goto error;
255  }
256 
257  /* Thanks God! all is done */
258 
259  {
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));
263  vertices_size_type num_colors = degree_coloring(g1, color);
264  std::cout << "Boost colors are: " << num_colors << std::endl;
265  }
266  return (0);
267  /* ---------------------------------- */
268 error: /* error found reading input */
269 
270  printf("\nline %ld of input - %s\n", no_lines, err_message[err_no]);
271 
272  exit(1);
273  return (1); /* to avoid warning */
274 }
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

Generated on Mon Feb 12 2024 13:02:50 for PandA-2024.02 by doxygen 1.8.13