PandA-2024.02
test_dsatur_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  */
49 #include "dsatur_coloring.hpp"
50 #include <boost/graph/adjacency_list.hpp>
51 #include <boost/graph/adjacency_list_io.hpp>
52 #include <cstring>
53 #include <fstream>
54 #include <iosfwd>
55 #include <utility>
56 
57 using namespace boost;
58 int main(int argc, char* argv[])
59 {
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;
65  if(argc < 2)
66  {
67  printf("Provide data file in command.\n");
68  exit(1);
69  }
70  // read Graph1
71  Graph1 g1;
72  const int EDGE_FIELDS = 2; /* no of fields in edge line */
73  const int P_FIELDS = 3; /* no of fields in problem line */
74  const char* PROBLEM_TYPE = "edge"; /* name of problem type*/
75  long VERTICES, /*number of vertices*/
76  number_of_edges, /* number of edges and nodes */
77  head, tail;
78 
79  long no_lines = 0, /* no of current input line */
80  no_plines = 0, /* no of problem-lines */
81  no_elines = 0; /* no of edge-lines */
82 
83  std::string in_line; /* for reading input line */
84  char pr_type[5]; /* for reading type of the problem */
85 
86  int err_no; /* no of detected error */
87 
88  /* -------------- error numbers & error messages ---------------- */
89  const int EN1 = 0;
90  const int EN2 = 1;
91  const int EN3 = 2;
92  const int EN4 = 3;
93  // const int EN6 = 4;
94  // const int EN10 = 5;
95  // const int EN7 = 6;
96  const int EN8 = 7;
97  // const int EN9 = 8;
98  // const int EN11 = 9;
99  // const int EN12 = 10;
100  // const int EN13 = 11;
101  // const int EN14 = 12;
102  // const int EN16 = 13;
103  const int EN15 = 14;
104  const int EN17 = 15;
105  const int EN18 = 16;
106  const int EN21 = 17;
107  const int EN19 = 18;
108  // const int EN20 = 19;
109  const int EN22 = 20;
110 
111  static const char* err_message[] = {/* 0*/ "more than one problem line.",
112  /* 1*/ "wrong number of parameters in the problem line.",
113  /* 2*/ "it is not a Max Flow problem line.",
114  /* 3*/ "bad value of a parameter in the problem line.",
115  /* 4*/ "can't obtain enough memory to solve this problem.",
116  /* 5*/ "more than one line with the problem name.",
117  /* 6*/ "can't read problem name.",
118  /* 7*/ "problem description must be before node description.",
119  /* 8*/ "this parser doesn't support multiply sources and sinks.",
120  /* 9*/ "wrong number of parameters in the node line.",
121  /*10*/ "wrong value of parameters in the node line.",
122  /*11*/ " ",
123  /*12*/ "source and sink descriptions must be before arc descriptions.",
124  /*13*/ "too many arcs in the input.",
125  /*14*/ "wrong number of parameters in the arc line.",
126  /*15*/ "wrong value of parameters in the arc line.",
127  /*16*/ "unknown line type in the input.",
128  /*17*/ "reading error.",
129  /*18*/ "not enough arcs in the input.",
130  /*19*/ "source or sink doesn't have incident arcs.",
131  /*20*/ "can't read anything from the input file."};
132  /* --------------------------------------------------------------- */
133 
134  /* The main loop:
135  - reads the line of the input,
136  - analyses its type,
137  - checks correctness of parameters,
138  - puts data to the arrays,
139  - does service functions
140  */
141  std::ifstream in(argv[1]);
142 
143  while(std::getline(in, in_line))
144  {
145  ++no_lines;
146 
147  switch(in_line[0])
148  {
149  case 'c': /* skip lines with comments */
150  case '\n': /* skip empty lines */
151  case '\0': /* skip empty lines at the end of file */
152  break;
153 
154  case 'p': /* problem description */
155  {
156  if(no_plines > 0)
157  /* more than one problem line */
158  {
159  err_no = EN1;
160  goto error;
161  }
162 
163  no_plines = 1;
164  if(
165  /* reading problem line: type of problem, no of nodes, no of arcs */
166  sscanf(in_line.c_str(), "%*c %4s %ld %ld", pr_type, &VERTICES, &number_of_edges) != P_FIELDS)
167  /*wrong number of parameters in the problem line*/
168  {
169  err_no = EN2;
170  goto error;
171  }
172 
173  if(strcmp(pr_type, PROBLEM_TYPE))
174  /*wrong problem type*/
175  {
176  err_no = EN3;
177  goto error;
178  }
179 
180  if(VERTICES <= 0 || number_of_edges <= 0)
181  /*wrong value of no of edges or nodes*/
182  {
183  err_no = EN4;
184  goto error;
185  }
186 
187  {
188  for(long vi = 0; vi < VERTICES; ++vi)
189  {
190  verts.push_back(add_vertex(g1));
191  }
192  }
193  break;
194  }
195 
196  case 'e': /* edge description */
197  {
198  if(no_plines == 0)
199  /* there was not problem line above */
200  {
201  err_no = EN8;
202  goto error;
203  }
204 
205  if(
206  /* reading an edge description */
207  sscanf(in_line.c_str(), "%*c %ld %ld", &tail, &head) != EDGE_FIELDS)
208  /* arc description is not correct */
209  {
210  err_no = EN15;
211  goto error;
212  }
213  --tail; // index from 0, not 1
214  --head;
215  if(tail < 0 || tail > VERTICES || head < 0 || head > VERTICES)
216  /* wrong value of nodes */
217  {
218  err_no = EN17;
219  goto error;
220  }
221  graph_traits<Graph1>::edge_descriptor e1;
222  bool in1;
223  tie(e1, in1) = add_edge(verts[tail], verts[head], g1);
224  if(!in1)
225  {
226  std::cerr << "unable to add edge (" << head << "," << tail << ")" << std::endl;
227  exit(1);
228  }
229 
230  ++no_elines;
231  break;
232  }
233  default:
234  {
235  /* unknown type of line */
236  err_no = EN18;
237  goto error;
238  }
239 
240  } /* end of switch */
241  } /* end of input loop */
242 
243  /* ----- all is read or error while reading ----- */
244 
245  if(!in.eof()) /* reading error */
246  {
247  err_no = EN21;
248  goto error;
249  }
250 
251  if(no_lines == 0) /* empty input */
252  {
253  err_no = EN22;
254  goto error;
255  }
256 
257  if(no_elines < number_of_edges) /* not enough arcs */
258  {
259  err_no = EN19;
260  goto error;
261  }
262 
263  /* Thanks God! all is done */
264 
265  {
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));
269  vertices_size_type num_colors = dsatur_coloring(g1, color);
270  std::cout << "Boost colors are: " << num_colors << std::endl;
271  }
272  return (0);
273  /* ---------------------------------- */
274 error: /* error found reading input */
275 
276  printf("\nline %ld of input - %s\n", no_lines, err_message[err_no]);
277 
278  exit(1);
279  return (1); /* to avoid warning */
280 }
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)

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