1 /* This software was developed by Bruce Hendrickson and Robert Leland *
2 * at Sandia National Laboratories under US Department of Energy *
3 * contract DE-AC04-76DP00789 and is copyrighted by Sandia Corporation. */
4
5 #include <stdio.h>
6 #include <string.h>
7 #include "defs.h"
8
9
input_graph(fin,inname,start,adjacency,nvtxs,vweights,eweights)10 int input_graph(fin, inname, start, adjacency, nvtxs, vweights, eweights)
11 FILE *fin; /* input file */
12 char *inname; /* name of input file */
13 int **start; /* start of edge list for each vertex */
14 int **adjacency; /* edge list data */
15 int *nvtxs; /* number of vertices in graph */
16 int **vweights; /* vertex weight list data */
17 float **eweights; /* edge weight list data */
18 {
19 extern FILE *Output_File; /* output file or null */
20 extern int CHECK_INPUT; /* print warnings or not? */
21 extern int DEBUG_INPUT; /* echo that input file read successful? */
22 extern int DEBUG_TRACE; /* trace main execution path */
23 int *adjptr; /* loops through adjacency data */
24 float *ewptr; /* loops through edge weight data */
25 int narcs; /* number of edges expected in graph */
26 int nedges; /* twice number of edges really in graph */
27 int nedge; /* loops through edges for each vertex */
28 int flag; /* condition indicator */
29 int found_flag; /* is vertex found in adjacency list? */
30 int skip_flag; /* should this edge be ignored? */
31 int end_flag; /* indicates end of line or file */
32 int vtx; /* vertex in graph */
33 int line_num; /* line number in input file */
34 int sum_edges; /* total number of edges read so far */
35 int option; /* input option */
36 int using_ewgts; /* are edge weights in input file? */
37 int using_vwgts; /* are vertex weights in input file? */
38 int vtxnums; /* are vertex numbers in input file? */
39 int vertex; /* current vertex being read */
40 int new_vertex; /* new vertex being read */
41 int weight; /* weight being read */
42 float eweight; /* edge weight being read */
43 int neighbor; /* neighbor of current vertex */
44 int self_edge; /* is a self edge encountered? */
45 int ignore_me; /* is this edge being ignored? */
46 int ignored; /* how many edges are ignored? */
47 int error_flag; /* error reading input? */
48 int j; /* loop counters */
49 int sfree(), read_int();
50 double *smalloc(), read_val();
51
52 if (DEBUG_TRACE > 0) {
53 printf("<Entering input_graph>\n");
54 }
55
56 /* Read first line of input (= nvtxs, narcs, option). */
57 /* The (decimal) digits of the option variable mean: 1's digit not zero => input
58 edge weights 10's digit not zero => input vertex weights 100's digit not zero
59 => include vertex numbers */
60
61 *start = NULL;
62 *adjacency = NULL;
63 *vweights = NULL;
64 *eweights = NULL;
65
66 error_flag = 0;
67 line_num = 0;
68
69 /* Read any leading comment lines */
70 end_flag = 1;
71 while (end_flag == 1) {
72 *nvtxs = read_int(fin, &end_flag);
73 ++line_num;
74 }
75 if (*nvtxs <= 0) {
76 printf("ERROR in graph file `%s':", inname);
77 printf(" Invalid number of vertices (%d).\n", *nvtxs);
78 if (Output_File != NULL) {
79 fprintf(Output_File, "ERROR in graph file `%s':", inname);
80 fprintf(Output_File, " Invalid number of vertices (%d).\n", *nvtxs);
81 }
82 fclose(fin);
83 return(1);
84 }
85
86 narcs = read_int(fin, &end_flag);
87 if (narcs < 0) {
88 printf("ERROR in graph file `%s':", inname);
89 printf(" Invalid number of expected edges (%d).\n", narcs);
90 if (Output_File != NULL) {
91 fprintf(Output_File, "ERROR in graph file `%s':", inname);
92 fprintf(Output_File, " Invalid number of expected edges (%d).\n", narcs);
93 }
94 fclose(fin);
95 return(1);
96 }
97
98 if (!end_flag) {
99 option = read_int(fin, &end_flag);
100 }
101 while (!end_flag)
102 j = read_int(fin, &end_flag);
103
104 using_ewgts = option - 10 * (option / 10);
105 option /= 10;
106 using_vwgts = option - 10 * (option / 10);
107 option /= 10;
108 vtxnums = option - 10 * (option / 10);
109
110 using_ewgts = TRUE;
111 using_vwgts = FALSE;
112 vtxnums = TRUE;
113
114 /* Allocate space for rows and columns. */
115 *start = (int *) smalloc((unsigned) (*nvtxs + 1) * sizeof(int));
116 if (narcs != 0)
117 *adjacency = (int *) smalloc((unsigned) (2 * narcs + 1) * sizeof(int));
118 else
119 *adjacency = NULL;
120
121 if (using_vwgts)
122 *vweights = (int *) smalloc((unsigned) (*nvtxs) * sizeof(int));
123 else
124 *vweights = NULL;
125
126 if (using_ewgts && narcs != 0)
127 *eweights = (float *) smalloc((unsigned) (2 * narcs + 1) * sizeof(float));
128 else
129 *eweights = NULL;
130
131 adjptr = *adjacency;
132 ewptr = *eweights;
133 self_edge = 0;
134 ignored = 0;
135
136 sum_edges = 0;
137 nedges = 0;
138 (*start)[0] = 0;
139 vertex = 0;
140 vtx = 0;
141 new_vertex = TRUE;
142 while ((narcs || using_vwgts || vtxnums) && end_flag != -1) {
143 ++line_num;
144
145 /* If multiple input lines per vertex, read vertex number. */
146 if (vtxnums) {
147 j = read_int(fin, &end_flag) + 1;
148 if (end_flag) {
149 if (vertex == *nvtxs)
150 break;
151 printf("ERROR in graph file `%s':", inname);
152 printf(" no vertex number in line %d.\n", line_num);
153 if (Output_File != NULL) {
154 fprintf(Output_File, "ERROR in graph file `%s':", inname);
155 fprintf(Output_File, " no vertex number in line %d.\n", line_num);
156 }
157 fclose(fin);
158 return (1);
159 }
160 if (j != vertex && j != vertex + 1) {
161 printf("ERROR in graph file `%s':", inname);
162 printf(" out-of-order vertex number in line %d.\n", line_num);
163 if (Output_File != NULL) {
164 fprintf(Output_File, "ERROR in graph file `%s':", inname);
165 fprintf(Output_File,
166 " out-of-order vertex number in line %d.\n", line_num);
167 }
168 fclose(fin);
169 return (1);
170 }
171 if (j != vertex) {
172 new_vertex = TRUE;
173 vertex = j;
174 }
175 else
176 new_vertex = FALSE;
177 }
178 else
179 vertex = ++vtx;
180
181 if (vertex > *nvtxs)
182 break;
183
184 /* If vertices are weighted, read vertex weight. */
185 if (using_vwgts && new_vertex) {
186 weight = read_int(fin, &end_flag);
187 if (end_flag) {
188 printf("ERROR in graph file `%s':", inname);
189 printf(" no weight for vertex %d.\n", vertex);
190 if (Output_File != NULL) {
191 fprintf(Output_File, "ERROR in graph file `%s':", inname);
192 fprintf(Output_File, " no weight for vertex %d.\n", vertex);
193 }
194 fclose(fin);
195 return (1);
196 }
197 if (weight <= 0) {
198 printf("ERROR in graph file `%s':", inname);
199 printf(" zero or negative weight entered for vertex %d.\n", vertex);
200 if (Output_File != NULL) {
201 fprintf(Output_File, "ERROR in graph file `%s':", inname);
202 fprintf(Output_File,
203 " zero or negative weight entered for vertex %d.\n", vertex);
204 }
205 fclose(fin);
206 return (1);
207 }
208 (*vweights)[vertex-1] = weight;
209 }
210
211 nedge = 0;
212
213 /* Read number of adjacent vertex. */
214 neighbor = read_int(fin, &end_flag) + 1;
215
216 while (!end_flag) {
217 skip_flag = FALSE;
218 ignore_me = FALSE;
219
220 if (neighbor > *nvtxs) {
221 printf("ERROR in graph file `%s':", inname);
222 printf(" nvtxs=%d, but edge (%d,%d) was input.\n",
223 *nvtxs, vertex, neighbor);
224 if (Output_File != NULL) {
225 fprintf(Output_File, "ERROR in graph file `%s':", inname);
226 fprintf(Output_File,
227 " nvtxs=%d, but edge (%d,%d) was input.\n",
228 *nvtxs, vertex, neighbor);
229 }
230 fclose(fin);
231 return (1);
232 }
233 if (neighbor <= 0) {
234 printf("ERROR in graph file `%s':", inname);
235 printf(" zero or negative vertex in edge (%d,%d).\n",
236 vertex, neighbor);
237 if (Output_File != NULL) {
238 fprintf(Output_File, "ERROR in graph file `%s':", inname);
239 fprintf(Output_File,
240 " zero or negative vertex in edge (%d,%d).\n",
241 vertex, neighbor);
242 }
243 fclose(fin);
244 return (1);
245 }
246
247 if (neighbor == vertex) {
248 if (!self_edge && CHECK_INPUT) {
249 printf("WARNING: Self edge (%d, %d) being ignored.\n",
250 vertex, vertex);
251 if (Output_File != NULL) {
252 fprintf(Output_File,
253 "WARNING: Self edge (%d, %d) being ignored.\n", vertex, vertex);
254 }
255 }
256 skip_flag = TRUE;
257 ++self_edge;
258 }
259
260 /* Check if adjacency is repeated. */
261 if (!skip_flag) {
262 found_flag = FALSE;
263 for (j = (*start)[vertex - 1]; !found_flag && j < sum_edges + nedge; j++) {
264 if ((*adjacency)[j] == neighbor)
265 found_flag = TRUE;
266 }
267 if (found_flag) {
268 printf("WARNING: Multiple occurences of edge (%d,%d) ignored\n",
269 vertex, neighbor);
270 if (Output_File != NULL) {
271 fprintf(Output_File,
272 "WARNING: Multiple occurences of edge (%d,%d) ignored\n",
273 vertex, neighbor);
274 }
275 skip_flag = TRUE;
276 if (!ignore_me) {
277 ignore_me = TRUE;
278 ++ignored;
279 }
280 }
281 }
282
283 if (using_ewgts) { /* Read edge weight if it's being input. */
284 eweight = read_val(fin, &end_flag);
285
286 if (end_flag) {
287 printf("ERROR in graph file `%s':", inname);
288 printf(" no weight for edge (%d,%d).\n", vertex, neighbor);
289 if (Output_File != NULL) {
290 fprintf(Output_File, "ERROR in graph file `%s':", inname);
291 fprintf(Output_File,
292 " no weight for edge (%d,%d).\n", vertex, neighbor);
293 }
294 fclose(fin);
295 return (1);
296 }
297
298 if (eweight <= 0 && CHECK_INPUT) {
299 printf("WARNING: Bad weight entered for edge (%d,%d). Edge ignored.\n",
300 vertex, neighbor);
301 if (Output_File != NULL) {
302 fprintf(Output_File,
303 "WARNING: Bad weight entered for edge (%d,%d). Edge ignored.\n",
304 vertex, neighbor);
305 }
306 skip_flag = TRUE;
307 if (!ignore_me) {
308 ignore_me = TRUE;
309 ++ignored;
310 }
311 }
312 else {
313 *ewptr++ = eweight;
314 }
315 }
316
317 /* Check for edge only entered once. */
318 if (neighbor < vertex && !skip_flag) {
319 found_flag = FALSE;
320 for (j = (*start)[neighbor - 1]; !found_flag && j < (*start)[neighbor]; j++) {
321 if ((*adjacency)[j] == vertex)
322 found_flag = TRUE;
323 }
324 if (!found_flag) {
325 printf("ERROR in graph file `%s':", inname);
326 printf(" Edge (%d, %d) entered but not (%d, %d)\n",
327 vertex, neighbor, neighbor, vertex);
328 if (Output_File != NULL) {
329 fprintf(Output_File, "ERROR in graph file `%s':", inname);
330 fprintf(Output_File,
331 " Edge (%d, %d) entered but not (%d, %d)\n",
332 vertex, neighbor, neighbor, vertex);
333 }
334 error_flag = 1;
335 }
336 }
337
338 /* Add edge to data structure. */
339 if (!skip_flag) {
340 if (++nedges > 2*narcs) {
341 printf("ERROR in graph file `%s':", inname);
342 printf(" at least %d adjacencies entered, but nedges = %d\n",
343 nedges, narcs);
344 if (Output_File != NULL) {
345 fprintf(Output_File, "ERROR in graph file `%s':", inname);
346 fprintf(Output_File,
347 " at least %d adjacencies entered, but nedges = %d\n",
348 nedges, narcs);
349 }
350 fclose(fin);
351 return (1);
352 }
353 *adjptr++ = neighbor;
354 nedge++;
355 }
356
357 /* Read number of next adjacent vertex. */
358 neighbor = read_int(fin, &end_flag) + 1;
359 }
360
361 sum_edges += nedge;
362 (*start)[vertex] = sum_edges;
363 }
364
365 /* Make sure there's nothing else in file. */
366 flag = FALSE;
367 while (!flag && end_flag != -1) {
368 read_int(fin, &end_flag);
369 if (!end_flag)
370 flag = TRUE;
371 }
372 if (flag && CHECK_INPUT) {
373 printf("WARNING: Possible error in graph file `%s'\n", inname);
374 printf(" Data found after expected end of file\n");
375 if (Output_File != NULL) {
376 fprintf(Output_File,
377 "WARNING: Possible error in graph file `%s'\n", inname);
378 fprintf(Output_File,
379 " Data found after expected end of file\n");
380 }
381 }
382
383 (*start)[*nvtxs] = sum_edges;
384
385 if (self_edge > 1 && CHECK_INPUT) {
386 printf("WARNING: %d self edges were read and ignored.\n", self_edge);
387 if (Output_File != NULL) {
388 fprintf(Output_File,
389 "WARNING: %d self edges were read and ignored.\n", self_edge);
390 }
391 }
392
393 if (vertex != 0) { /* Normal file was read. */
394 /* Make sure narcs was reasonable. */
395 if (nedges + 2 * self_edge != 2 * narcs &&
396 nedges + 2 * self_edge + ignored != 2 * narcs &&
397 nedges + self_edge != 2 * narcs &&
398 nedges + self_edge + ignored != 2 * narcs &&
399 nedges != 2 * narcs &&
400 nedges + ignored != 2 * narcs &&
401 CHECK_INPUT) {
402 printf("WARNING: I expected %d edges entered twice, but I only count %d.\n",
403 narcs, nedges);
404 if (Output_File != NULL) {
405 fprintf(Output_File,
406 "WARNING: I expected %d edges entered twice, but I only count %d.\n",
407 narcs, nedges);
408 }
409 }
410 }
411
412 else {
413 /* Graph was empty => must be using inertial method. */
414 sfree((char *) *start);
415 if (*adjacency != NULL)
416 sfree((char *) *adjacency);
417 if (*eweights != NULL)
418 sfree((char *) *eweights);
419 *start = NULL;
420 *adjacency = NULL;
421 }
422
423 fclose(fin);
424
425 if (DEBUG_INPUT > 0) {
426 printf("Done reading graph file `%s'.\n", inname);
427 }
428 return (error_flag);
429 }
430