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 /* Allocate space for rows and columns. */
111 *start = (int *) smalloc((unsigned) (*nvtxs + 1) * sizeof(int));
112 if (narcs != 0)
113 *adjacency = (int *) smalloc((unsigned) (2 * narcs + 1) * sizeof(int));
114 else
115 *adjacency = NULL;
116
117 if (using_vwgts)
118 *vweights = (int *) smalloc((unsigned) (*nvtxs) * sizeof(int));
119 else
120 *vweights = NULL;
121
122 if (using_ewgts && narcs != 0)
123 *eweights = (float *) smalloc((unsigned) (2 * narcs + 1) * sizeof(float));
124 else
125 *eweights = NULL;
126
127 adjptr = *adjacency;
128 ewptr = *eweights;
129 self_edge = 0;
130 ignored = 0;
131
132 sum_edges = 0;
133 nedges = 0;
134 (*start)[0] = 0;
135 vertex = 0;
136 vtx = 0;
137 new_vertex = TRUE;
138 while ((narcs || using_vwgts || vtxnums) && end_flag != -1) {
139 ++line_num;
140
141 /* If multiple input lines per vertex, read vertex number. */
142 if (vtxnums) {
143 j = read_int(fin, &end_flag);
144 if (end_flag) {
145 if (vertex == *nvtxs)
146 break;
147 printf("ERROR in graph file `%s':", inname);
148 printf(" no vertex number in line %d.\n", line_num);
149 if (Output_File != NULL) {
150 fprintf(Output_File, "ERROR in graph file `%s':", inname);
151 fprintf(Output_File, " no vertex number in line %d.\n", line_num);
152 }
153 fclose(fin);
154 return (1);
155 }
156 if (j != vertex && j != vertex + 1) {
157 printf("ERROR in graph file `%s':", inname);
158 printf(" out-of-order vertex number in line %d.\n", line_num);
159 if (Output_File != NULL) {
160 fprintf(Output_File, "ERROR in graph file `%s':", inname);
161 fprintf(Output_File,
162 " out-of-order vertex number in line %d.\n", line_num);
163 }
164 fclose(fin);
165 return (1);
166 }
167 if (j != vertex) {
168 new_vertex = TRUE;
169 vertex = j;
170 }
171 else
172 new_vertex = FALSE;
173 }
174 else
175 vertex = ++vtx;
176
177 if (vertex > *nvtxs)
178 break;
179
180 /* If vertices are weighted, read vertex weight. */
181 if (using_vwgts && new_vertex) {
182 weight = read_int(fin, &end_flag);
183 if (end_flag) {
184 printf("ERROR in graph file `%s':", inname);
185 printf(" no weight for vertex %d.\n", vertex);
186 if (Output_File != NULL) {
187 fprintf(Output_File, "ERROR in graph file `%s':", inname);
188 fprintf(Output_File, " no weight for vertex %d.\n", vertex);
189 }
190 fclose(fin);
191 return (1);
192 }
193 if (weight <= 0) {
194 printf("ERROR in graph file `%s':", inname);
195 printf(" zero or negative weight entered for vertex %d.\n", vertex);
196 if (Output_File != NULL) {
197 fprintf(Output_File, "ERROR in graph file `%s':", inname);
198 fprintf(Output_File,
199 " zero or negative weight entered for vertex %d.\n", vertex);
200 }
201 fclose(fin);
202 return (1);
203 }
204 (*vweights)[vertex-1] = weight;
205 }
206
207 nedge = 0;
208
209 /* Read number of adjacent vertex. */
210 neighbor = read_int(fin, &end_flag);
211
212 while (!end_flag) {
213 skip_flag = FALSE;
214 ignore_me = FALSE;
215
216 if (neighbor > *nvtxs) {
217 printf("ERROR in graph file `%s':", inname);
218 printf(" nvtxs=%d, but edge (%d,%d) was input.\n",
219 *nvtxs, vertex, neighbor);
220 if (Output_File != NULL) {
221 fprintf(Output_File, "ERROR in graph file `%s':", inname);
222 fprintf(Output_File,
223 " nvtxs=%d, but edge (%d,%d) was input.\n",
224 *nvtxs, vertex, neighbor);
225 }
226 fclose(fin);
227 return (1);
228 }
229 if (neighbor <= 0) {
230 printf("ERROR in graph file `%s':", inname);
231 printf(" zero or negative vertex in edge (%d,%d).\n",
232 vertex, neighbor);
233 if (Output_File != NULL) {
234 fprintf(Output_File, "ERROR in graph file `%s':", inname);
235 fprintf(Output_File,
236 " zero or negative vertex in edge (%d,%d).\n",
237 vertex, neighbor);
238 }
239 fclose(fin);
240 return (1);
241 }
242
243 if (neighbor == vertex) {
244 if (!self_edge && CHECK_INPUT) {
245 printf("WARNING: Self edge (%d, %d) being ignored.\n",
246 vertex, vertex);
247 if (Output_File != NULL) {
248 fprintf(Output_File,
249 "WARNING: Self edge (%d, %d) being ignored.\n", vertex, vertex);
250 }
251 }
252 skip_flag = TRUE;
253 ++self_edge;
254 }
255
256 /* Check if adjacency is repeated. */
257 if (!skip_flag) {
258 found_flag = FALSE;
259 for (j = (*start)[vertex - 1]; !found_flag && j < sum_edges + nedge; j++) {
260 if ((*adjacency)[j] == neighbor)
261 found_flag = TRUE;
262 }
263 if (found_flag) {
264 printf("WARNING: Multiple occurences of edge (%d,%d) ignored\n",
265 vertex, neighbor);
266 if (Output_File != NULL) {
267 fprintf(Output_File,
268 "WARNING: Multiple occurences of edge (%d,%d) ignored\n",
269 vertex, neighbor);
270 }
271 skip_flag = TRUE;
272 if (!ignore_me) {
273 ignore_me = TRUE;
274 ++ignored;
275 }
276 }
277 }
278
279 if (using_ewgts) { /* Read edge weight if it's being input. */
280 eweight = read_val(fin, &end_flag);
281
282 if (end_flag) {
283 printf("ERROR in graph file `%s':", inname);
284 printf(" no weight for edge (%d,%d).\n", vertex, neighbor);
285 if (Output_File != NULL) {
286 fprintf(Output_File, "ERROR in graph file `%s':", inname);
287 fprintf(Output_File,
288 " no weight for edge (%d,%d).\n", vertex, neighbor);
289 }
290 fclose(fin);
291 return (1);
292 }
293
294 if (eweight <= 0 && CHECK_INPUT) {
295 printf("WARNING: Bad weight entered for edge (%d,%d). Edge ignored.\n",
296 vertex, neighbor);
297 if (Output_File != NULL) {
298 fprintf(Output_File,
299 "WARNING: Bad weight entered for edge (%d,%d). Edge ignored.\n",
300 vertex, neighbor);
301 }
302 skip_flag = TRUE;
303 if (!ignore_me) {
304 ignore_me = TRUE;
305 ++ignored;
306 }
307 }
308 else {
309 *ewptr++ = eweight;
310 }
311 }
312
313 /* Check for edge only entered once. */
314 if (neighbor < vertex && !skip_flag) {
315 found_flag = FALSE;
316 for (j = (*start)[neighbor - 1]; !found_flag && j < (*start)[neighbor]; j++) {
317 if ((*adjacency)[j] == vertex)
318 found_flag = TRUE;
319 }
320 if (!found_flag) {
321 printf("ERROR in graph file `%s':", inname);
322 printf(" Edge (%d, %d) entered but not (%d, %d)\n",
323 vertex, neighbor, neighbor, vertex);
324 if (Output_File != NULL) {
325 fprintf(Output_File, "ERROR in graph file `%s':", inname);
326 fprintf(Output_File,
327 " Edge (%d, %d) entered but not (%d, %d)\n",
328 vertex, neighbor, neighbor, vertex);
329 }
330 error_flag = 1;
331 }
332 }
333
334 /* Add edge to data structure. */
335 if (!skip_flag) {
336 if (++nedges > 2*narcs) {
337 printf("ERROR in graph file `%s':", inname);
338 printf(" at least %d adjacencies entered, but nedges = %d\n",
339 nedges, narcs);
340 if (Output_File != NULL) {
341 fprintf(Output_File, "ERROR in graph file `%s':", inname);
342 fprintf(Output_File,
343 " at least %d adjacencies entered, but nedges = %d\n",
344 nedges, narcs);
345 }
346 fclose(fin);
347 return (1);
348 }
349 *adjptr++ = neighbor;
350 nedge++;
351 }
352
353 /* Read number of next adjacent vertex. */
354 neighbor = read_int(fin, &end_flag);
355 }
356
357 sum_edges += nedge;
358 (*start)[vertex] = sum_edges;
359 }
360
361 /* Make sure there's nothing else in file. */
362 flag = FALSE;
363 while (!flag && end_flag != -1) {
364 read_int(fin, &end_flag);
365 if (!end_flag)
366 flag = TRUE;
367 }
368 if (flag && CHECK_INPUT) {
369 printf("WARNING: Possible error in graph file `%s'\n", inname);
370 printf(" Data found after expected end of file\n");
371 if (Output_File != NULL) {
372 fprintf(Output_File,
373 "WARNING: Possible error in graph file `%s'\n", inname);
374 fprintf(Output_File,
375 " Data found after expected end of file\n");
376 }
377 }
378
379 (*start)[*nvtxs] = sum_edges;
380
381 if (self_edge > 1 && CHECK_INPUT) {
382 printf("WARNING: %d self edges were read and ignored.\n", self_edge);
383 if (Output_File != NULL) {
384 fprintf(Output_File,
385 "WARNING: %d self edges were read and ignored.\n", self_edge);
386 }
387 }
388
389 if (vertex != 0) { /* Normal file was read. */
390 /* Make sure narcs was reasonable. */
391 if (nedges + 2 * self_edge != 2 * narcs &&
392 nedges + 2 * self_edge + ignored != 2 * narcs &&
393 nedges + self_edge != 2 * narcs &&
394 nedges + self_edge + ignored != 2 * narcs &&
395 nedges != 2 * narcs &&
396 nedges + ignored != 2 * narcs &&
397 CHECK_INPUT) {
398 printf("WARNING: I expected %d edges entered twice, but I only count %d.\n",
399 narcs, nedges);
400 if (Output_File != NULL) {
401 fprintf(Output_File,
402 "WARNING: I expected %d edges entered twice, but I only count %d.\n",
403 narcs, nedges);
404 }
405 }
406 }
407
408 else {
409 /* Graph was empty => must be using inertial method. */
410 sfree((char *) *start);
411 if (*adjacency != NULL)
412 sfree((char *) *adjacency);
413 if (*eweights != NULL)
414 sfree((char *) *eweights);
415 *start = NULL;
416 *adjacency = NULL;
417 }
418
419 fclose(fin);
420
421 if (DEBUG_INPUT > 0) {
422 printf("Done reading graph file `%s'.\n", inname);
423 }
424 return (error_flag);
425 }
426