libmetis/graph.c
Go to the documentation of this file.
1 
11 #include "metislib.h"
12 
13 
14 /*************************************************************************/
16 /*************************************************************************/
19 {
20  idx_t i, j, k, sum;
21  real_t *nvwgt;
22  graph_t *graph;
23 
24  /* allocate the graph and fill in the fields */
25  graph = CreateGraph();
26 
27  graph->nvtxs = nvtxs;
28  graph->nedges = xadj[nvtxs];
29  graph->ncon = ncon;
30 
31  graph->xadj = xadj;
32  graph->free_xadj = 0;
33 
34  graph->adjncy = adjncy;
35  graph->free_adjncy = 0;
36 
37 
38  /* setup the vertex weights */
39  if (vwgt) {
40  graph->vwgt = vwgt;
41  graph->free_vwgt = 0;
42  }
43  else {
44  vwgt = graph->vwgt = ismalloc(ncon*nvtxs, 1, "SetupGraph: vwgt");
45  }
46 
47  graph->tvwgt = imalloc(ncon, "SetupGraph: tvwgts");
48  graph->invtvwgt = rmalloc(ncon, "SetupGraph: invtvwgts");
49  for (i=0; i<ncon; i++) {
50  graph->tvwgt[i] = isum(nvtxs, vwgt+i, ncon);
51  graph->invtvwgt[i] = 1.0/(graph->tvwgt[i] > 0 ? graph->tvwgt[i] : 1);
52  }
53 
54 
55  if (ctrl->objtype == METIS_OBJTYPE_VOL) {
56  /* Setup the vsize */
57  if (vsize) {
58  graph->vsize = vsize;
59  graph->free_vsize = 0;
60  }
61  else {
62  vsize = graph->vsize = ismalloc(nvtxs, 1, "SetupGraph: vsize");
63  }
64 
65  /* Allocate memory for edge weights and initialize them to the sum of the vsize */
66  adjwgt = graph->adjwgt = imalloc(graph->nedges, "SetupGraph: adjwgt");
67  for (i=0; i<nvtxs; i++) {
68  for (j=xadj[i]; j<xadj[i+1]; j++)
69  adjwgt[j] = 1+vsize[i]+vsize[adjncy[j]];
70  }
71  }
72  else { /* For edgecut minimization */
73  /* setup the edge weights */
74  if (adjwgt) {
75  graph->adjwgt = adjwgt;
76  graph->free_adjwgt = 0;
77  }
78  else {
79  adjwgt = graph->adjwgt = ismalloc(graph->nedges, 1, "SetupGraph: adjwgt");
80  }
81  }
82 
83 
84  /* setup various derived info */
86 
87  if (ctrl->optype == METIS_OP_PMETIS || ctrl->optype == METIS_OP_OMETIS)
89 
90  ASSERT(CheckGraph(graph, ctrl->numflag, 1));
91 
92  return graph;
93 }
94 
95 
96 /*************************************************************************/
98 /*************************************************************************/
100 {
101  idx_t i;
102 
103  if (graph->tvwgt == NULL)
104  graph->tvwgt = imalloc(graph->ncon, "SetupGraph_tvwgt: tvwgt");
105  if (graph->invtvwgt == NULL)
106  graph->invtvwgt = rmalloc(graph->ncon, "SetupGraph_tvwgt: invtvwgt");
107 
108  for (i=0; i<graph->ncon; i++) {
109  graph->tvwgt[i] = isum(graph->nvtxs, graph->vwgt+i, graph->ncon);
110  graph->invtvwgt[i] = 1.0/(graph->tvwgt[i] > 0 ? graph->tvwgt[i] : 1);
111  }
112 }
113 
114 
115 /*************************************************************************/
117 /*************************************************************************/
119 {
120  idx_t i;
121 
122  if (graph->label == NULL)
123  graph->label = imalloc(graph->nvtxs, "SetupGraph_label: label");
124 
125  for (i=0; i<graph->nvtxs; i++)
126  graph->label[i] = i;
127 }
128 
129 
130 /*************************************************************************/
132 /*************************************************************************/
134 {
135  graph_t *sgraph;
136 
137  sgraph = CreateGraph();
138 
139  sgraph->nvtxs = snvtxs;
140  sgraph->nedges = snedges;
141  sgraph->ncon = graph->ncon;
142 
143  /* Allocate memory for the splitted graph */
144  sgraph->xadj = imalloc(snvtxs+1, "SetupSplitGraph: xadj");
145  sgraph->vwgt = imalloc(sgraph->ncon*snvtxs, "SetupSplitGraph: vwgt");
146  sgraph->adjncy = imalloc(snedges, "SetupSplitGraph: adjncy");
147  sgraph->adjwgt = imalloc(snedges, "SetupSplitGraph: adjwgt");
148  sgraph->label = imalloc(snvtxs, "SetupSplitGraph: label");
149  sgraph->tvwgt = imalloc(sgraph->ncon, "SetupSplitGraph: tvwgt");
150  sgraph->invtvwgt = rmalloc(sgraph->ncon, "SetupSplitGraph: invtvwgt");
151 
152  if (graph->vsize)
153  sgraph->vsize = imalloc(snvtxs, "SetupSplitGraph: vsize");
154 
155  return sgraph;
156 }
157 
158 
159 /*************************************************************************/
161 /*************************************************************************/
163 {
164  graph_t *graph;
165 
166  graph = (graph_t *)gk_malloc(sizeof(graph_t), "CreateGraph: graph");
167 
168  InitGraph(graph);
169 
170  return graph;
171 }
172 
173 
174 /*************************************************************************/
176 /*************************************************************************/
178 {
179  memset((void *)graph, 0, sizeof(graph_t));
180 
181  /* graph size constants */
182  graph->nvtxs = -1;
183  graph->nedges = -1;
184  graph->ncon = -1;
185  graph->mincut = -1;
186  graph->minvol = -1;
187  graph->nbnd = -1;
188 
189  /* memory for the graph structure */
190  graph->xadj = NULL;
191  graph->vwgt = NULL;
192  graph->vsize = NULL;
193  graph->adjncy = NULL;
194  graph->adjwgt = NULL;
195  graph->label = NULL;
196  graph->cmap = NULL;
197  graph->tvwgt = NULL;
198  graph->invtvwgt = NULL;
199 
200  /* by default these are set to true, but the can be explicitly changed afterwards */
201  graph->free_xadj = 1;
202  graph->free_vwgt = 1;
203  graph->free_vsize = 1;
204  graph->free_adjncy = 1;
205  graph->free_adjwgt = 1;
206 
207 
208  /* memory for the partition/refinement structure */
209  graph->where = NULL;
210  graph->pwgts = NULL;
211  graph->id = NULL;
212  graph->ed = NULL;
213  graph->bndptr = NULL;
214  graph->bndind = NULL;
215  graph->nrinfo = NULL;
216  graph->ckrinfo = NULL;
217  graph->vkrinfo = NULL;
218 
219  /* linked-list structure */
220  graph->coarser = NULL;
221  graph->finer = NULL;
222 }
223 
224 
225 /*************************************************************************/
227 /*************************************************************************/
229 {
230 
231  /* The following is for the -minconn and -contig to work properly in
232  the vol-refinement routines */
233  if ((void *)graph->ckrinfo == (void *)graph->vkrinfo)
234  graph->ckrinfo = NULL;
235 
236 
237  /* free partition/refinement structure */
238  gk_free((void **)&graph->where, &graph->pwgts, &graph->id, &graph->ed,
239  &graph->bndptr, &graph->bndind, &graph->nrinfo, &graph->ckrinfo,
240  &graph->vkrinfo, LTERM);
241 }
242 
243 
244 /*************************************************************************/
246 /*************************************************************************/
247 void FreeGraph(graph_t **r_graph)
248 {
249  graph_t *graph;
250 
251  graph = *r_graph;
252 
253  /* free graph structure */
254  if (graph->free_xadj)
255  gk_free((void **)&graph->xadj, LTERM);
256  if (graph->free_vwgt)
257  gk_free((void **)&graph->vwgt, LTERM);
258  if (graph->free_vsize)
259  gk_free((void **)&graph->vsize, LTERM);
260  if (graph->free_adjncy)
261  gk_free((void **)&graph->adjncy, LTERM);
262  if (graph->free_adjwgt)
263  gk_free((void **)&graph->adjwgt, LTERM);
264 
265  /* free partition/refinement structure */
266  FreeRData(graph);
267 
268  gk_free((void **)&graph->tvwgt, &graph->invtvwgt, &graph->label,
269  &graph->cmap, &graph, LTERM);
270 
271  *r_graph = NULL;
272 }
273 
274 
graph_t::tvwgt
idx_t * tvwgt
Definition: libmetis/struct.h:91
SetupGraph_label
void SetupGraph_label(graph_t *graph)
Definition: libmetis/graph.c:118
adjwgt
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
Definition: include/metis.h:198
graph_t::vwgt
idx_t * vwgt
Definition: libmetis/struct.h:86
gk_free
void gk_free(void **ptr1,...)
Definition: memory.c:202
graph_t::invtvwgt
real_t * invtvwgt
Definition: libmetis/struct.h:92
vsize
idx_t idx_t idx_t idx_t idx_t * vsize
Definition: include/metis.h:198
CheckGraph
#define CheckGraph
Definition: rename.h:30
ctrl_t
Definition: libmetis/struct.h:139
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
graph_t::nedges
idx_t nedges
Definition: libmetis/struct.h:83
SetupSplitGraph
graph_t * SetupSplitGraph(graph_t *graph, idx_t snvtxs, idx_t snedges)
Definition: libmetis/graph.c:133
ismalloc
#define ismalloc
Definition: gklib_rename.h:68
ncon
idx_t * ncon
Definition: include/metis.h:197
j
std::ptrdiff_t j
Definition: tut_arithmetic_redux_minmax.cpp:2
CreateGraph
graph_t * CreateGraph(void)
Definition: libmetis/graph.c:162
FreeRData
void FreeRData(graph_t *graph)
Definition: libmetis/graph.c:228
LTERM
#define LTERM
Definition: gk_defs.h:14
ctrl_t::objtype
mobjtype_et objtype
Definition: libmetis/struct.h:141
graph_t::vsize
idx_t * vsize
Definition: libmetis/struct.h:87
graph_t::nvtxs
idx_t nvtxs
Definition: libmetis/struct.h:83
graph_t::label
idx_t * label
Definition: libmetis/struct.h:99
METIS_OP_OMETIS
@ METIS_OP_OMETIS
Definition: include/metis.h:265
METIS_OP_PMETIS
@ METIS_OP_PMETIS
Definition: include/metis.h:263
vwgt
idx_t idx_t idx_t idx_t * vwgt
Definition: include/metis.h:198
FreeGraph
void FreeGraph(graph_t **r_graph)
Definition: libmetis/graph.c:247
SetupGraph
graph_t * SetupGraph(ctrl_t *ctrl, idx_t nvtxs, idx_t ncon, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *vsize, idx_t *adjwgt)
Definition: libmetis/graph.c:17
ASSERT
#define ASSERT(expression)
Definition: ccolamd.c:872
xadj
idx_t idx_t * xadj
Definition: include/metis.h:197
InitGraph
void InitGraph(graph_t *graph)
Definition: libmetis/graph.c:177
graph_t::ncon
idx_t ncon
Definition: libmetis/struct.h:84
isum
#define isum
Definition: gklib_rename.h:72
SetupGraph_tvwgt
void SetupGraph_tvwgt(graph_t *graph)
Definition: libmetis/graph.c:99
ctrl_t::optype
moptype_et optype
Definition: libmetis/struct.h:140
METIS_OBJTYPE_VOL
@ METIS_OBJTYPE_VOL
Definition: include/metis.h:356
graph_t::adjncy
idx_t * adjncy
Definition: libmetis/struct.h:88
real_t
float real_t
Definition: include/metis.h:132
NULL
#define NULL
Definition: ccolamd.c:609
metislib.h
graph
NonlinearFactorGraph graph
Definition: doc/Code/OdometryExample.cpp:2
ctrl_t::numflag
idx_t numflag
Definition: libmetis/struct.h:159
rmalloc
#define rmalloc
Definition: gklib_rename.h:93
gk_malloc
void * gk_malloc(size_t nbytes, char *msg)
Definition: memory.c:140
i
int i
Definition: BiCGSTAB_step_by_step.cpp:9
graph_t
Definition: libmetis/struct.h:82
idx_t
int32_t idx_t
Definition: include/metis.h:101


gtsam
Author(s):
autogenerated on Sun Dec 22 2024 04:11:38