1 /*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * checkgraph.c
5 *
6 * This file contains routines related to I/O
7 *
8 * Started 8/28/94
9 * George
10 *
11 */
12
13 #include "metislib.h"
14
15
16
17 /*************************************************************************/
18 /*! This function checks if a graph is valid. A valid graph must satisfy
19 the following constraints:
20 - It should contain no self-edges.
21 - It should be undirected; i.e., (u,v) and (v,u) should be present.
22 - The adjacency list should not contain multiple edges to the same
23 other vertex.
24
25 \param graph is the graph to be checked, whose numbering starts from 0.
26 \param numflag is 0 if error reporting will be done using 0 as the
27 numbering, or 1 if the reporting should be done using 1.
28 \param verbose is 1 the identified errors will be displayed, or 0, if
29 it should run silently.
30 */
31 /*************************************************************************/
CheckGraph(graph_t * graph,int numflag,int verbose)32 int CheckGraph(graph_t *graph, int numflag, int verbose)
33 {
34 idx_t i, j, k, l;
35 idx_t nvtxs, err=0;
36 idx_t minedge, maxedge, minewgt, maxewgt;
37 idx_t *xadj, *adjncy, *adjwgt, *htable;
38
39 numflag = (numflag == 0 ? 0 : 1); /* make sure that numflag is 0 or 1 */
40
41 nvtxs = graph->nvtxs;
42 xadj = graph->xadj;
43 adjncy = graph->adjncy;
44 adjwgt = graph->adjwgt;
45
46 ASSERT(adjwgt != NULL);
47
48 htable = ismalloc(nvtxs, 0, "htable");
49
50 minedge = maxedge = adjncy[0];
51 minewgt = maxewgt = adjwgt[0];
52
53 for (i=0; i<nvtxs; i++) {
54 for (j=xadj[i]; j<xadj[i+1]; j++) {
55 k = adjncy[j];
56
57 minedge = (k < minedge) ? k : minedge;
58 maxedge = (k > maxedge) ? k : maxedge;
59 minewgt = (adjwgt[j] < minewgt) ? adjwgt[j] : minewgt;
60 maxewgt = (adjwgt[j] > maxewgt) ? adjwgt[j] : maxewgt;
61
62 if (i == k) {
63 if (verbose)
64 printf("Vertex %"PRIDX" contains a self-loop "
65 "(i.e., diagonal entry in the matrix)!\n", i+numflag);
66 err++;
67 }
68 else {
69 for (l=xadj[k]; l<xadj[k+1]; l++) {
70 if (adjncy[l] == i) {
71 if (adjwgt[l] != adjwgt[j]) {
72 if (verbose)
73 printf("Edges (u:%"PRIDX" v:%"PRIDX" wgt:%"PRIDX") and "
74 "(v:%"PRIDX" u:%"PRIDX" wgt:%"PRIDX") "
75 "do not have the same weight!\n",
76 i+numflag, k+numflag, adjwgt[j],
77 k+numflag, i+numflag, adjwgt[l]);
78 err++;
79 }
80 break;
81 }
82 }
83 if (l == xadj[k+1]) {
84 if (verbose)
85 printf("Missing edge: (%"PRIDX" %"PRIDX")!\n", k+numflag, i+numflag);
86 err++;
87 }
88 }
89
90 if (htable[k] == 0) {
91 htable[k]++;
92 }
93 else {
94 if (verbose)
95 printf("Edge %"PRIDX" from vertex %"PRIDX" is repeated %"PRIDX" times\n",
96 k+numflag, i+numflag, htable[k]++);
97 err++;
98 }
99 }
100
101 for (j=xadj[i]; j<xadj[i+1]; j++)
102 htable[adjncy[j]] = 0;
103 }
104
105
106 if (err > 0 && verbose) {
107 printf("A total of %"PRIDX" errors exist in the input file. "
108 "Correct them, and run again!\n", err);
109 }
110
111 gk_free((void **)&htable, LTERM);
112
113 return (err == 0 ? 1 : 0);
114 }
115
116
117 /*************************************************************************/
118 /*! This function performs a quick check of the weights of the graph */
119 /*************************************************************************/
CheckInputGraphWeights(idx_t nvtxs,idx_t ncon,idx_t * xadj,idx_t * adjncy,idx_t * vwgt,idx_t * vsize,idx_t * adjwgt)120 int CheckInputGraphWeights(idx_t nvtxs, idx_t ncon, idx_t *xadj, idx_t *adjncy,
121 idx_t *vwgt, idx_t *vsize, idx_t *adjwgt)
122 {
123 idx_t i;
124
125 if (ncon <= 0) {
126 printf("Input Error: ncon must be >= 1.\n");
127 return 0;
128 }
129
130 if (vwgt) {
131 for (i=ncon*nvtxs; i>=0; i--) {
132 if (vwgt[i] < 0) {
133 printf("Input Error: negative vertex weight(s).\n");
134 return 0;
135 }
136 }
137 }
138 if (vsize) {
139 for (i=nvtxs; i>=0; i--) {
140 if (vsize[i] < 0) {
141 printf("Input Error: negative vertex sizes(s).\n");
142 return 0;
143 }
144 }
145 }
146 if (adjwgt) {
147 for (i=xadj[nvtxs]-1; i>=0; i--) {
148 if (adjwgt[i] < 0) {
149 printf("Input Error: non-positive edge weight(s).\n");
150 return 0;
151 }
152 }
153 }
154
155 return 1;
156 }
157
158
159 /*************************************************************************/
160 /*! This function creates a graph whose topology is consistent with
161 Metis' requirements that:
162 - There are no self-edges.
163 - It is undirected; i.e., (u,v) and (v,u) should be present and of the
164 same weight.
165 - The adjacency list should not contain multiple edges to the same
166 other vertex.
167
168 Any of the above errors are fixed by performing the following operations:
169 - Self-edges are removed.
170 - The undirected graph is formed by the union of edges.
171 - One of the duplicate edges is selected.
172
173 The routine does not change the provided vertex weights.
174 */
175 /*************************************************************************/
FixGraph(graph_t * graph)176 graph_t *FixGraph(graph_t *graph)
177 {
178 idx_t i, j, k, l, nvtxs, nedges;
179 idx_t *xadj, *adjncy, *adjwgt;
180 idx_t *nxadj, *nadjncy, *nadjwgt;
181 graph_t *ngraph;
182 uvw_t *edges;
183
184
185 nvtxs = graph->nvtxs;
186 xadj = graph->xadj;
187 adjncy = graph->adjncy;
188 adjwgt = graph->adjwgt;
189 ASSERT(adjwgt != NULL);
190
191 ngraph = CreateGraph();
192
193 ngraph->nvtxs = nvtxs;
194
195 /* deal with vertex weights/sizes */
196 ngraph->ncon = graph->ncon;
197 ngraph->vwgt = icopy(nvtxs*graph->ncon, graph->vwgt,
198 imalloc(nvtxs*graph->ncon, "FixGraph: vwgt"));
199
200 ngraph->vsize = ismalloc(nvtxs, 1, "FixGraph: vsize");
201 if (graph->vsize)
202 icopy(nvtxs, graph->vsize, ngraph->vsize);
203
204 /* fix graph by sorting the "superset" of edges */
205 edges = (uvw_t *)gk_malloc(sizeof(uvw_t)*2*xadj[nvtxs], "FixGraph: edges");
206
207 for (nedges=0, i=0; i<nvtxs; i++) {
208 for (j=xadj[i]; j<xadj[i+1]; j++) {
209 /* keep only the upper-trianglular part of the adjacency matrix */
210 if (i < adjncy[j]) {
211 edges[nedges].u = i;
212 edges[nedges].v = adjncy[j];
213 edges[nedges].w = adjwgt[j];
214 nedges++;
215 }
216 else if (i > adjncy[j]) {
217 edges[nedges].u = adjncy[j];
218 edges[nedges].v = i;
219 edges[nedges].w = adjwgt[j];
220 nedges++;
221 }
222 }
223 }
224
225 uvwsorti(nedges, edges);
226
227
228 /* keep the unique subset */
229 for (k=0, i=1; i<nedges; i++) {
230 if (edges[k].v != edges[i].v || edges[k].u != edges[i].u) {
231 edges[++k] = edges[i];
232 }
233 }
234 nedges = k+1;
235
236 /* allocate memory for the fixed graph */
237 nxadj = ngraph->xadj = ismalloc(nvtxs+1, 0, "FixGraph: nxadj");
238 nadjncy = ngraph->adjncy = imalloc(2*nedges, "FixGraph: nadjncy");
239 nadjwgt = ngraph->adjwgt = imalloc(2*nedges, "FixGraph: nadjwgt");
240
241 /* create the adjacency list of the fixed graph from the upper-triangular
242 part of the adjacency matrix */
243 for (k=0; k<nedges; k++) {
244 nxadj[edges[k].u]++;
245 nxadj[edges[k].v]++;
246 }
247 MAKECSR(i, nvtxs, nxadj);
248
249 for (k=0; k<nedges; k++) {
250 nadjncy[nxadj[edges[k].u]] = edges[k].v;
251 nadjncy[nxadj[edges[k].v]] = edges[k].u;
252 nadjwgt[nxadj[edges[k].u]] = edges[k].w;
253 nadjwgt[nxadj[edges[k].v]] = edges[k].w;
254 nxadj[edges[k].u]++;
255 nxadj[edges[k].v]++;
256 }
257 SHIFTCSR(i, nvtxs, nxadj);
258
259 gk_free((void **)&edges, LTERM);
260
261 return ngraph;
262 }
263
264