PaStiX Handbook  6.4.0
graph_connected_components.c
Go to the documentation of this file.
1 /**
2  *
3  * @file graph_connected_components.c
4  *
5  * PaStiX routines to isolate disconnected subgraphs
6  *
7  * @copyright 2004-2024 Bordeaux INP, CNRS (LaBRI UMR 5800), Inria,
8  * Univ. Bordeaux. All rights reserved.
9  *
10  * @version 6.4.0
11  * @author Gregoire Pichon
12  * @author Mathieu Faverge
13  * @author Tony Delarue
14  * @date 2024-07-05
15  *
16  **/
17 #include "common.h"
18 #include <spm.h>
19 #include "graph/graph.h"
20 #include "pastix/order.h"
21 
22 #ifndef DOXYGEN_SHOULD_SKIP_THIS
23 typedef struct _Queue {
24  pastix_int_t *tab;
25  pastix_int_t size;
26  pastix_int_t start;
27  pastix_int_t end;
28 } Queue;
29 
30 static void queue_init (Queue *self, pastix_int_t size) {
31  self->size = size+1;
32  self->tab = malloc (self->size * sizeof (pastix_int_t));
33  self->start = -1;
34  self->end = -1;
35 }
36 
37 static void queue_push_back (Queue *self, pastix_int_t v) {
38  self->end++;
39  assert( self->end < self->size );
40  self->tab[ self->end ] = v;
41 }
42 
43 static pastix_int_t queue_pop_front (Queue* self) {
44  pastix_int_t v;
45 
46  self->start++;
47  assert( self->start <= self->end );
48  v = self->tab[self->start];
49  return v;
50 }
51 
52 static pastix_int_t queue_is_empty (const Queue *self) {
53  return self->start == self->end;
54 }
55 
56 static void queue_free (Queue *self) {
57  free (self->tab);
58 }
59 
60 /**
61  * @brief Invert partition p1 and p2 in buffer A of size (p1+p2), using workspace W of size p1
62  */
63 void
64 move_to_end( pastix_int_t p1,
65  pastix_int_t p2,
66  pastix_int_t *A,
67  pastix_int_t *W )
68 {
69  pastix_int_t size, from, to, move;
70 
71  memcpy( W, A, p1 * sizeof(pastix_int_t) );
72 
73  size = p2;
74  from = p1;
75  to = 0;
76  while( size > 0 ) {
77  move = pastix_imin( p1, size );
78  memcpy( A + to, A + from, move * sizeof(pastix_int_t) );
79  size -= move;
80  from += move;
81  to += move;
82  }
83  assert( p2 - to == 0 );
84  memcpy( A + to, W, p1 * sizeof(pastix_int_t) );
85 }
86 #endif
87 
88 /**
89  *******************************************************************************
90  *
91  * @ingroup pastix_graph
92  *
93  * @brief Isolate the connected components from the original graph
94  *
95  *******************************************************************************
96  *
97  * @param[in] graph
98  * The original graph associated from which vertices and edges must be
99  * extracted.
100  *
101  * @param[inout] comp_vtx
102  * Array of size n that hold the index of the component for each vertex
103  * of the graph.
104  *
105  * @param[inout] comp_sze
106  * The size of each components in the graph.
107  *
108  *******************************************************************************
109  *
110  * @retval The amount of connected components in the graph
111  *
112  *******************************************************************************/
114 graphIsolateConnectedComponents( const pastix_graph_t *graph,
115  pastix_int_t *comp_vtx,
116  pastix_int_t *comp_sze )
117 {
118  const pastix_int_t *colptr;
119  const pastix_int_t *rowptr;
120  pastix_int_t baseval = graph->baseval;
121  pastix_int_t n = graph->n;
122  pastix_int_t cur = 0;
123  pastix_int_t i, u, v, total;
124  Queue q;
125 
126  /* Set the comp_vtx to -1 */
127  memset(comp_vtx, 0xff, n*sizeof(pastix_int_t));
128 
129  /* Make sure the graph is 0 based. */
130  assert(baseval == 0);
131 
132  queue_init (&q, n);
133 
134  total = n;
135  colptr = graph->colptr;
136  rowptr = graph->rowptr - baseval;
137  while ( total > 0 ) {
138  i = 0;
139 
140  while ((i < n) && (comp_vtx[i] != -1) ) {
141  i++;
142  }
143  assert( i < n );
144 
145  queue_push_back( &q, i );
146  comp_vtx[i] = cur;
147  comp_sze[cur] = 1;
148  total--;
149 
150  while ( !queue_is_empty( &q ) )
151  {
152  v = queue_pop_front( &q );
153 
154  for (i = colptr[v]; i < colptr[v+1]; i++) {
155  u = rowptr[i] - baseval;
156 
157  if ( comp_vtx[u] != -1 ) {
158  assert( comp_vtx[u] == comp_vtx[v] );
159  continue;
160  }
161 
162  queue_push_back( &q, u );
163  comp_vtx[u] = cur;
164  comp_sze[cur]++;
165  total--;
166  }
167  }
168  /* End of this component */
169  cur++;
170  }
171 
172 #ifndef NDEBUG
173  for (i=0; i<n; i++){
174  assert( comp_vtx[i] != -1);
175  }
176 #endif
177 
178  queue_free (&q);
179  return cur;
180 }
BEGIN_C_DECLS typedef int pastix_int_t
Definition: datatypes.h:51
pastix_int_t graphIsolateConnectedComponents(const pastix_graph_t *graph, pastix_int_t *comp_vtx, pastix_int_t *comp_sze)
Isolate the connected components from the original graph.