PaStiX Handbook  6.3.2
graph_prepare.c
Go to the documentation of this file.
1 /**
2  *
3  * @file graph_prepare.c
4  *
5  * PaStiX graph construction routines
6  *
7  * @copyright 2004-2023 Bordeaux INP, CNRS (LaBRI UMR 5800), Inria,
8  * Univ. Bordeaux. All rights reserved.
9  *
10  * @version 6.3.2
11  * @author Xavier Lacoste
12  * @author Pierre Ramet
13  * @author Mathieu Faverge
14  * @author Tony Delarue
15  * @date 2023-07-21
16  *
17  **/
18 #include "common.h"
19 #include "graph/graph.h"
20
21 /**
22  *******************************************************************************
23  *
24  * @ingroup pastix_graph
25  *
26  * @brief This routine removes the diagonal edges from a centralized graph.
27  *
28  *******************************************************************************
29  *
30  * @param[inout] graph
31  * On entry, the pointer to the graph structure with possible diagonal
32  * edges (i,i).
33  * On exit, all entries of type (i,i) are removed from the graph.
34  *
35  *******************************************************************************/
36 void
37 graphNoDiag( pastix_graph_t *graph )
38 {
39  pastix_int_t n = graph->n;
40  pastix_int_t *colptr = graph->colptr;
41  pastix_int_t *rowptr = graph->rowptr;
42  pastix_int_t *newrow = graph->rowptr;
43  pastix_int_t *loc2glob = graph->loc2glob;
44  pastix_int_t baseval = colptr[0];
45  pastix_int_t i, j, ig, jg, indj;
46
47  indj = colptr[0];
48  for( i = 0; i < n ; i++, colptr++, loc2glob++ )
49  {
50  ig = (graph->loc2glob == NULL) ? i : *loc2glob - baseval;
51  for (j = colptr[0]; j < colptr[1]; j++, rowptr++ )
52  {
53  jg = *rowptr - baseval;
54  /* If diagonal element, we skip it */
55  if ( jg == ig ) {
56  continue;
57  }
58  /* Otherwise we save it */
59  else {
60  *newrow = *rowptr;
61  newrow++;
62  }
63  }
64  /* Save the new colptr[i] */
65  *colptr = indj;
66
67  /* Store the new colptr[i+1] */
68  indj = (newrow - graph->rowptr) + baseval;
69  }
70  *colptr = indj;
71
72  graph->nnz = *colptr - *(graph->colptr);
73
74  graph->rowptr =
75  (pastix_int_t *) memRealloc ( graph->rowptr, graph->nnz * sizeof (pastix_int_t) );
76
78 }
79
80 /**
81  *******************************************************************************
82  *
83  * @ingroup pastix_graph
84  *
85  * @brief This routine initializes the graph.
86  *
87  * This routine will also symmetrize the graph, remove duplicates,
88  * remove the diagonal elements, and keep only the lower part.
89  *
90  *******************************************************************************
91  *
92  * @param[inout] pastix_data
93  * The pointer to the solver instance. On exit, the fields n, cols,
94  * rows and loc2glob are initialized for future steps of the solver.
95  *
96  * @param[in] spm
97  * The initial user spm that needs to be transformed in a
98  * correct graph for future call in ordering and symbolic factorization
99  * routines.
100  *
101  * @param[out] graph
102  * On exit, the pointer to the allocated graph structure is returned.
103  * The graph can then be used with ordering and symbol factorization
104  * tools.
105  * The graph is symmetrized without diagonal elements and rows array is
106  * sorted.
107  *
108  *******************************************************************************
109  *
110  * @retval PASTIX_SUCCESS on success,
111  * @retval !0 on failure.
112  *
113  *******************************************************************************/
114 int
116  const spmatrix_t *spm,
117  pastix_graph_t **graph )
118 {
119  pastix_graph_t *tmpgraph = NULL;
120  pastix_int_t *iparm = pastix_data->iparm;
121
122  int io_strategy = iparm[IPARM_IO_STRATEGY];
123
124  MALLOC_INTERN( tmpgraph, 1, pastix_graph_t );
125  memset( tmpgraph, 0, sizeof(pastix_graph_t) );
126
127  if ( iparm[IPARM_VERBOSE] > PastixVerboseNo ) {
128  pastix_print( spm->clustnum, 0, "%s", OUT_SUBSTEP_GRAPH );
129  }
130
131  if (io_strategy & PastixIOLoadGraph)
132  {
133  graphLoad( pastix_data, tmpgraph );
134  }
135  else
136  {
137  graphSpm2Graph( tmpgraph, spm );
138
139  /*
140  * If the spm is symmetric, it only contains half of its datas.
141  * We need to have all the datas for the graph.
142  * An SpmGeneral has already a symmetrized pattern.
143  */
144  if( (spm->mtxtype == SpmSymmetric) ||
145  (spm->mtxtype == SpmHermitian) ) {
146
147  if (iparm[IPARM_VERBOSE] > PastixVerboseNo) {
148  pastix_print(spm->clustnum, 0, "%s", OUT_ORDER_SYMGRAPH);
149  }
150  graphSymmetrize( tmpgraph );
151  }
152
153  if (iparm[IPARM_VERBOSE] > PastixVerboseNo) {
154  pastix_print(spm->clustnum, 0, "%s", OUT_ORDER_SORT);
155  }
156  graphSort( tmpgraph );
157
158  if (iparm[IPARM_VERBOSE] > PastixVerboseNo) {
159  pastix_print(spm->clustnum, 0, "%s", OUT_ORDER_NODIAG);
160  }
161  graphNoDiag( tmpgraph );
162  }
163
164  assert( tmpgraph->fmttype == SpmCSC );
165  assert( tmpgraph->flttype == SpmPattern );
166  assert( tmpgraph->values == NULL );
167
168  *graph = tmpgraph;
169  return PASTIX_SUCCESS;
170 }
BEGIN_C_DECLS typedef int pastix_int_t
Definition: datatypes.h:51
@ PastixIOLoadGraph
Definition: api.h:232
@ IPARM_VERBOSE
Definition: api.h:36
@ IPARM_IO_STRATEGY
Definition: api.h:37
@ PastixVerboseNo
Definition: api.h:221
@ PASTIX_SUCCESS
Definition: api.h:367
int graphUpdateComputedFields(pastix_graph_t *graph)
Update dofs, nnz, nnzexp, gnnz, n, nexp, gN of a given graph.
Definition: graph.c:338
void graphLoad(const pastix_data_t *pastix_data, pastix_graph_t *graph)
Load a graph from a file.
Definition: graph_io.c:45
int graphSpm2Graph(pastix_graph_t *graph, const spmatrix_t *spm)
This routine build a graph thanks to an spm;.
Definition: graph.c:379
int graphSymmetrize(pastix_graph_t *graph)
Symmetrize a given graph.
Definition: graph.c:307
void graphNoDiag(pastix_graph_t *graph)
This routine removes the diagonal edges from a centralized graph.
Definition: graph_prepare.c:37
int graphPrepare(pastix_data_t *pastix_data, const spmatrix_t *spm, pastix_graph_t **graph)
This routine initializes the graph.
void graphSort(pastix_graph_t *graph)
This routine sortes the subarray of edges of each vertex.
Definition: graph.c:282
pastix_int_t * iparm
Definition: pastixdata.h:69
Main PaStiX data structure.
Definition: pastixdata.h:67