checkgraph.c
Go to the documentation of this file.
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 /*************************************************************************/
31 /*************************************************************************/
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 /*************************************************************************/
119 /*************************************************************************/
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 /*************************************************************************/
175 /*************************************************************************/
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 
FixGraph
graph_t * FixGraph(graph_t *graph)
Definition: checkgraph.c:176
numflag
idx_t idx_t idx_t idx_t idx_t * numflag
Definition: include/metis.h:208
adjwgt
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
Definition: include/metis.h:198
CreateGraph
#define CreateGraph
Definition: rename.h:95
graph_t::vwgt
idx_t * vwgt
Definition: libmetis/struct.h:86
gk_free
void gk_free(void **ptr1,...)
Definition: memory.c:202
vsize
idx_t idx_t idx_t idx_t idx_t * vsize
Definition: include/metis.h:198
edges
vector< MFAS::KeyPair > edges
Definition: testMFAS.cpp:25
graph_t::xadj
idx_t * xadj
Definition: libmetis/struct.h:85
adjncy
idx_t idx_t idx_t * adjncy
Definition: include/metis.h:198
imalloc
#define imalloc
Definition: gklib_rename.h:42
graph_t::adjwgt
idx_t * adjwgt
Definition: libmetis/struct.h:89
ismalloc
#define ismalloc
Definition: gklib_rename.h:68
CheckGraph
int CheckGraph(graph_t *graph, int numflag, int verbose)
Definition: checkgraph.c:32
ncon
idx_t * ncon
Definition: include/metis.h:197
j
std::ptrdiff_t j
Definition: tut_arithmetic_redux_minmax.cpp:2
l
static const Line3 l(Rot3(), 1, 1)
LTERM
#define LTERM
Definition: gk_defs.h:14
graph_t::vsize
idx_t * vsize
Definition: libmetis/struct.h:87
graph_t::nvtxs
idx_t nvtxs
Definition: libmetis/struct.h:83
vwgt
idx_t idx_t idx_t idx_t * vwgt
Definition: include/metis.h:198
ASSERT
#define ASSERT(expression)
Definition: ccolamd.c:872
xadj
idx_t idx_t * xadj
Definition: include/metis.h:197
SHIFTCSR
#define SHIFTCSR(i, n, a)
Definition: gk_macros.h:80
graph_t::ncon
idx_t ncon
Definition: libmetis/struct.h:84
uvwsorti
#define uvwsorti
Definition: gklib_rename.h:118
v
Array< int, Dynamic, 1 > v
Definition: Array_initializer_list_vector_cxx11.cpp:1
PRIDX
#define PRIDX
Definition: include/metis.h:107
graph_t::adjncy
idx_t * adjncy
Definition: libmetis/struct.h:88
uvw_t
Definition: gklib_defs.h:18
MAKECSR
#define MAKECSR(i, n, a)
Definition: gk_macros.h:73
NULL
#define NULL
Definition: ccolamd.c:609
metislib.h
icopy
#define icopy
Definition: gklib_rename.h:28
graph
NonlinearFactorGraph graph
Definition: doc/Code/OdometryExample.cpp:2
gk_malloc
void * gk_malloc(size_t nbytes, char *msg)
Definition: memory.c:140
i
int i
Definition: BiCGSTAB_step_by_step.cpp:9
CheckInputGraphWeights
int CheckInputGraphWeights(idx_t nvtxs, idx_t ncon, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *vsize, idx_t *adjwgt)
Definition: checkgraph.c:120
graph_t
Definition: libmetis/struct.h:82
idx_t
int32_t idx_t
Definition: include/metis.h:101


gtsam
Author(s):
autogenerated on Fri Nov 1 2024 03:32:05