PaStiX Handbook  6.2.1
graph.c
Go to the documentation of this file.
1 /**
2  *
3  * @file graph.c
4  *
5  * PaStiX graph structure routines
6  *
7  * @copyright 2004-2021 Bordeaux INP, CNRS (LaBRI UMR 5800), Inria,
8  * Univ. Bordeaux. All rights reserved.
9  *
10  * @version 6.2.0
11  * @author Xavier Lacoste
12  * @author Pierre Ramet
13  * @author Mathieu Faverge
14  * @author Tony Delarue
15  * @date 2021-01-25
16  *
17  * @addtogroup pastix_graph
18  * @{
19  *
20  **/
21 #include "common.h"
22 #include "graph/graph.h"
23 
24 #define assert_graph( _graph_ ) \
25  do { \
26  assert( (_graph_)->fmttype == SpmCSC ); \
27  assert( (_graph_)->flttype == SpmPattern ); \
28  assert( (_graph_)->values == NULL ); \
29  } while (0)
30 
31 /**
32  *******************************************************************************
33  *
34  * @brief Initialize an empty graph
35  *
36  *******************************************************************************
37  *
38  * @param[inout] graph
39  * The empty graph to init.
40  *
41  * @param[in] comm
42  * The MPI communicator used for the graph.
43  *
44  *******************************************************************************/
45 void
46 graphInitEmpty( pastix_graph_t *graph,
47  PASTIX_Comm comm )
48 {
49  spmInitDist( graph, comm );
50 
51  graph->flttype = SpmPattern;
52 
53  graph->colptr = malloc( sizeof( pastix_int_t ) );
54  graph->colptr[0] = 0;
55 
57 }
58 
59 /**
60  *******************************************************************************
61  *
62  * @brief Free the content of the graph structure.
63  *
64  *******************************************************************************
65  *
66  * @param[inout] graph
67  * The pointer graph structure to free.
68  *
69  *******************************************************************************/
70 void
71 graphExit( pastix_graph_t *graph )
72 {
73  /* Parameter checks */
74  if ( graph == NULL ) {
75  pastix_print_error( "graphExit: graph pointer is NULL" );
76  return;
77  }
78  assert_graph( graph );
79 
80  spmExit( graph );
81 
82  return;
83 }
84 
85 /**
86  *******************************************************************************
87  *
88  * @brief Rebase the graph to the given value.
89  *
90  *******************************************************************************
91  *
92  * @param[inout] graph
93  * The graph to rebase.
94  *
95  * @param[in] baseval
96  * The base value to use in the graph (0 or 1).
97  *
98  *******************************************************************************/
99 void
100 graphBase( pastix_graph_t *graph,
101  pastix_int_t baseval )
102 {
103  /* Parameter checks */
104  if ( graph == NULL ) {
105  pastix_print_error( "graphBase: graph pointer is NULL" );
106  return;
107  }
108  if ( (baseval != 0) &&
109  (baseval != 1) )
110  {
111  pastix_print_error( "graphBase: baseval is incorrect, must be 0 or 1" );
112  return;
113  }
114 
115  assert_graph( graph );
116 
117  spmBase( graph, baseval );
118 
119  return;
120 }
121 
122 /**
123  *******************************************************************************
124  *
125  * @ingroup pastix_graph
126  *
127  * @brief This routine copy a given ordering in a new one.
128  *
129  * This function copies a graph structure into another one. If all subpointers
130  * are NULL, then they are all allocated and contains the original graphsrc
131  * values on exit. If one or more array pointers are not NULL, then, only those
132  * are copied to the graphdst structure.
133  *
134  *******************************************************************************
135  *
136  * @param[output] graphdst
137  * The destination graph. Must be allocated on entry.
138  *
139  * @param[in] graphsrc
140  * The source graph
141  *
142  *******************************************************************************
143  *
144  * @retval PASTIX_SUCCESS on successful exit
145  * @retval PASTIX_ERR_BADPARAMETER if one parameter is incorrect.
146  *
147  *******************************************************************************/
148 int
149 graphCopy( pastix_graph_t *graphdst,
150  const pastix_graph_t *graphsrc )
151 {
152  /* Parameter checks */
153  if ( graphdst == NULL ) {
155  }
156  if ( graphsrc == NULL ) {
158  }
159  if ( graphsrc == graphdst ) {
161  }
162  assert_graph( graphsrc );
163 
164  /* Copy the source graph */
165  spmCopy( graphsrc, graphdst );
166 
167  return PASTIX_SUCCESS;
168 }
169 
170 /**
171  *******************************************************************************
172  *
173  * @ingroup pastix_graph
174  *
175  * @brief This routine scatter a graph from node root to the other nodes
176  *
177  *******************************************************************************
178  *
179  * @param[inout] graph
180  * On entry, the graph to scatter.
181  * On exit, the scattered graph
182  *
183  * @param[in] comm
184  * MPI communicator.
185  *
186  *******************************************************************************
187  *
188  * @retval 1 if the graph has been scattered, 0 if untouched
189  *
190  *******************************************************************************/
191 int
192 graphScatterInPlace( pastix_graph_t *graph,
193  PASTIX_Comm comm )
194 {
195  pastix_graph_t newgraph;
196  int rc;
197 
198  assert_graph( graph );
199  if ( graph->loc2glob != NULL ) {
200  return 0;
201  }
202 
203  /* Scatter the graph */
204  rc = spmScatter( &newgraph, -1, graph, -1, NULL, 1, comm );
205 
206  if ( rc == SPM_SUCCESS ) {
207  graphExit( graph );
208  memcpy( graph, &newgraph, sizeof( pastix_graph_t ) );
209 
210  assert_graph( graph );
211  return 1;
212  }
213  else {
214  return 0;
215  }
216 }
217 
218 /**
219  *******************************************************************************
220  *
221  * @ingroup pastix_graph
222  *
223  * @brief This routine gather a distributed graph on each note in place.
224  *
225  *******************************************************************************
226  *
227  * @param[in] graph
228  * On entry, the distributed graph.
229  * On exit, the gathered graph
230  *
231  * @param[in] root
232  * The root where we want to gather the graph
233  *
234  *******************************************************************************
235  *
236  * @retval 1 if the graph has been gathered, 0 if untouched
237  *
238  ********************************************************************************/
239 int
240 graphGatherInPlace( pastix_graph_t *graph )
241 {
242  pastix_graph_t newgraph;
243  int rc;
244 
245  assert_graph( graph );
246  if ( graph->loc2glob == NULL ) {
247  return 0;
248  }
249 
250  rc = spmGather( graph, -1, &newgraph );
251 
252  if ( rc == SPM_SUCCESS ) {
253  graphExit( graph );
254  memcpy( graph, &newgraph, sizeof( pastix_graph_t ) );
255 
256  assert_graph( graph );
257  return 1;
258  }
259  else {
260  return 0;
261  }
262 }
263 
264 /**
265  *******************************************************************************
266  *
267  * @ingroup pastix_graph
268  *
269  * @brief This routine sortes the subarray of edges of each vertex.
270  *
271  * WARNING: The sort is always performed, do not call this routine
272  * when it is not required.
273  *
274  *******************************************************************************
275  *
276  * @param[inout] graph
277  * On entry, the pointer to the graph structure.
278  * On exit, the same graph with subarrays of edges sorted by ascending
279  * order.
280  *
281  *******************************************************************************/
282 void
283 graphSort( pastix_graph_t *graph )
284 {
285  assert_graph( graph );
286  spmSort( graph );
287 }
288 
289 /**
290  *******************************************************************************
291  *
292  * @ingroup pastix_graph
293  *
294  * @brief Symmetrize a given graph
295  *
296  *******************************************************************************
297  *
298  * @param[inout] graph
299  * The initialized graph structure that will be symmetrized.
300  *
301  *******************************************************************************
302  *
303  * @retval PASTIX_SUCCESS on success,
304  * @retval PASTIX_ERR_BADPARAMETER if incorrect parameters are given.
305  *
306  *******************************************************************************/
307 int
308 graphSymmetrize( pastix_graph_t *graph )
309 {
310  /* Parameter checks */
311  if ( graph == NULL ) {
313  }
314  assert_graph( graph );
315 
316  spmSymmetrize( graph );
317  return PASTIX_SUCCESS;
318 }
319 
320 /**
321  *******************************************************************************
322  *
323  * @ingroup pastix_graph
324  *
325  * @brief Update dofs, nnz, nnzexp, gnnz, n, nexp, gN of a given graph
326  *
327  *******************************************************************************
328  *
329  * @param[inout] graph
330  * The initialized graph structure that will be updated.
331  *
332  *******************************************************************************
333  *
334  * @retval PASTIX_SUCCESS on success,
335  * @retval PASTIX_ERR_BADPARAMETER if incorrect parameters are given.
336  *
337  *******************************************************************************/
338 int
339 graphUpdateComputedFields( pastix_graph_t *graph )
340 {
341  /* Parameter checks */
342  if ( graph == NULL ) {
344  }
345  assert_graph( graph );
346 
347  spmUpdateComputedFields( graph );
348  return PASTIX_SUCCESS;
349 }
350 
351 /**
352  *******************************************************************************
353  *
354  * @ingroup pastix_graph
355  *
356  * @brief This routine build a graph thanks to an spm;
357  *
358  * This function copies an spm structure into a graph one. If all subpointers
359  * are NULL, then they are all allocated and contains the original spm
360  * values on exit. If one or more array pointers are not NULL, then, only those
361  * are copied to the graphdst structure.
362  * We will take care that our graph does not contain coefficients, therefore has
363  * SpmPattern floating type and is a SpmCSC format type.
364  *
365  *******************************************************************************
366  *
367  * @param[inout] graph
368  * The destination graph.
369  *
370  * @param[in] graphsrc
371  * The source Sparse Matrix.
372  *
373  *******************************************************************************
374  *
375  * @retval PASTIX_SUCCESS on successful exit
376  * @retval PASTIX_ERR_BADPARAMETER if one parameter is incorrect.
377  *
378  *******************************************************************************/
379 int
380 graphSpm2Graph( pastix_graph_t *graph,
381  const spmatrix_t *spm )
382 {
383  /* Parameter checks */
384  if ( graph == NULL ) {
386  }
387  if ( spm == NULL ) {
389  }
390 
391  /*
392  * Clear the prexisting graph
393  * Might be uninitialized, so we call spmExit instead of graphExit.
394  */
395  spmExit( graph );
396 
397  /* Copy existing datas */
398  spmCopy( spm, graph );
399 
400  /* Enforce Pattern type to the graph */
401  graph->flttype = SpmPattern;
402  if ( graph->values ) {
403  free( graph->values );
404  graph->values = NULL;
405  }
406 
407  /* Make sure the graph is in CSC format */
408  spmConvert( SpmCSC, graph );
409 
410  return PASTIX_SUCCESS;
411 }
412 
413 
414 /**
415  *******************************************************************************
416  *
417  * @ingroup pastix_graph
418  *
419  * @brief Build the vertex weight array out of the dof array.
420  *
421  *******************************************************************************
422  *
423  * @param[in] graph
424  * Pointer to the graph structure.
425  *
426  *******************************************************************************
427  *
428  * @retval The vertex weight array if graph->dof != 1, NULL otherwise.
429  *
430  *******************************************************************************/
431 pastix_int_t *
432 graphGetWeights( const pastix_graph_t *graph )
433 {
434  pastix_int_t i, n;
435  pastix_int_t *weights, *wptr;
436 
437  if ( graph->dof == 1 ) {
438  return NULL;
439  }
440 
441  n = graph->n;
442  MALLOC_INTERN( weights, n, pastix_int_t );
443 
444  wptr = weights;
445  /* Constant dof */
446  if ( graph->dof > 1 ) {
447  for ( i=0; i<n; i++, wptr++ ) {
448  *wptr = graph->dof;
449  }
450  }
451  /* Variadic dof */
452  else {
453  pastix_int_t *dofptr = graph->dofs;
454  if ( graph->loc2glob == NULL ) {
455  for ( i=0; i<n; i++, wptr++, dofptr++ ) {
456  *wptr = dofptr[1] - dofptr[0];
457  }
458  }
459  else {
460  pastix_int_t *dofptr = graph->dofs - graph->baseval;
461  pastix_int_t *loc2glob = graph->loc2glob;
462 
463  for ( i=0; i<n; i++, wptr++, loc2glob++ ) {
464  *wptr = dofptr[ *loc2glob + 1 ] - dofptr[ *loc2glob ];
465  }
466  }
467  }
468 
469  return weights;
470 }
471 
472 /**
473  * @}
474  */
graphBase
void graphBase(pastix_graph_t *graph, pastix_int_t baseval)
Rebase the graph to the given value.
Definition: graph.c:100
graphSort
void graphSort(pastix_graph_t *graph)
This routine sortes the subarray of edges of each vertex.
Definition: graph.c:283
graphCopy
int graphCopy(pastix_graph_t *graphdst, const pastix_graph_t *graphsrc)
This routine copy a given ordering in a new one.
Definition: graph.c:149
graphSpm2Graph
int graphSpm2Graph(pastix_graph_t *graph, const spmatrix_t *spm)
This routine build a graph thanks to an spm;.
Definition: graph.c:380
graphUpdateComputedFields
int graphUpdateComputedFields(pastix_graph_t *graph)
Update dofs, nnz, nnzexp, gnnz, n, nexp, gN of a given graph.
Definition: graph.c:339
PASTIX_SUCCESS
@ PASTIX_SUCCESS
Definition: api.h:346
graphGatherInPlace
int graphGatherInPlace(pastix_graph_t *graph)
This routine gather a distributed graph on each note in place.
Definition: graph.c:240
graphSymmetrize
int graphSymmetrize(pastix_graph_t *graph)
Symmetrize a given graph.
Definition: graph.c:308
graph.h
graphInitEmpty
void graphInitEmpty(pastix_graph_t *graph, PASTIX_Comm comm)
Initialize an empty graph.
Definition: graph.c:46
graphScatterInPlace
int graphScatterInPlace(pastix_graph_t *graph, PASTIX_Comm comm)
This routine scatter a graph from node root to the other nodes.
Definition: graph.c:192
graphExit
void graphExit(pastix_graph_t *graph)
Free the content of the graph structure.
Definition: graph.c:71
PASTIX_ERR_BADPARAMETER
@ PASTIX_ERR_BADPARAMETER
Definition: api.h:353
graphGetWeights
pastix_int_t * graphGetWeights(const pastix_graph_t *graph)
Build the vertex weight array out of the dof array.
Definition: graph.c:432