abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
part.c
Go to the documentation of this file.
1 /*
2  * Revision Control Information
3  *
4  * $Source$
5  * $Author$
6  * $Revision$
7  * $Date$
8  *
9  */
10 #include "mincov_int.h"
11 
13 
14 
15 static int visit_col();
16 
17 static void
18 copy_row(A, prow)
19 register sm_matrix *A;
20 register sm_row *prow;
21 {
22  register sm_element *p;
23 
24  for(p = prow->first_col; p != 0; p = p->next_col) {
25  (void) sm_insert(A, p->row_num, p->col_num);
26  }
27 }
28 
29 
30 static int
31 visit_row(A, prow, rows_visited, cols_visited)
32 sm_matrix *A;
33 sm_row *prow;
34 int *rows_visited;
35 int *cols_visited;
36 {
37  sm_element *p;
38  sm_col *pcol;
39 
40  if (! prow->flag) {
41  prow->flag = 1;
42  (*rows_visited)++;
43  if (*rows_visited == A->nrows) {
44  return 1;
45  }
46  for(p = prow->first_col; p != 0; p = p->next_col) {
47  pcol = sm_get_col(A, p->col_num);
48  if (! pcol->flag) {
49  if (visit_col(A, pcol, rows_visited, cols_visited)) {
50  return 1;
51  }
52  }
53  }
54  }
55  return 0;
56 }
57 
58 
59 static int
60 visit_col(A, pcol, rows_visited, cols_visited)
61 sm_matrix *A;
62 sm_col *pcol;
63 int *rows_visited;
64 int *cols_visited;
65 {
66  sm_element *p;
67  sm_row *prow;
68 
69  if (! pcol->flag) {
70  pcol->flag = 1;
71  (*cols_visited)++;
72  if (*cols_visited == A->ncols) {
73  return 1;
74  }
75  for(p = pcol->first_row; p != 0; p = p->next_row) {
76  prow = sm_get_row(A, p->row_num);
77  if (! prow->flag) {
78  if (visit_row(A, prow, rows_visited, cols_visited)) {
79  return 1;
80  }
81  }
82  }
83  }
84  return 0;
85 }
86 
87 int
89 sm_matrix *A;
90 sm_matrix **L, **R;
91 {
92  int cols_visited, rows_visited;
93  register sm_row *prow;
94  register sm_col *pcol;
95 
96  /* Avoid the trivial case */
97  if (A->nrows == 0) {
98  return 0;
99  }
100 
101  /* Reset the visited flags for each row and column */
102  for(prow = A->first_row; prow != 0; prow = prow->next_row) {
103  prow->flag = 0;
104  }
105  for(pcol = A->first_col; pcol != 0; pcol = pcol->next_col) {
106  pcol->flag = 0;
107  }
108 
109  cols_visited = rows_visited = 0;
110  if (visit_row(A, A->first_row, &rows_visited, &cols_visited)) {
111  /* we found all of the rows */
112  return 0;
113  } else {
114  *L = sm_alloc();
115  *R = sm_alloc();
116  for(prow = A->first_row; prow != 0; prow = prow->next_row) {
117  if (prow->flag) {
118  copy_row(*L, prow);
119  } else {
120  copy_row(*R, prow);
121  }
122  }
123  return 1;
124  }
125 }
127 
int sm_block_partition(sm_matrix *A, sm_matrix **L, sm_matrix **R)
Definition: part.c:88
sm_row * next_row
Definition: sparse.h:50
static void copy_row(sm_matrix *A, sm_row *prow)
Definition: part.c:18
static Llb_Mgr_t * p
Definition: llb3Image.c:950
sm_col * next_col
Definition: sparse.h:65
#define sm_get_row(A, rownum)
Definition: sparse.h:93
int flag
Definition: sparse.h:47
sm_element * first_row
Definition: sparse.h:63
int flag
Definition: sparse.h:62
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
#define sm_get_col(A, colnum)
Definition: sparse.h:89
static ABC_NAMESPACE_IMPL_START int visit_col()
sm_element * sm_insert(sm_matrix *A, int row, int col)
Definition: matrix.c:155
ABC_NAMESPACE_IMPL_START sm_matrix * sm_alloc()
Definition: matrix.c:31
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
static int visit_row(sm_matrix *A, sm_row *prow, int *rows_visited, int *cols_visited)
Definition: part.c:31
typedefABC_NAMESPACE_HEADER_START struct sm_element_struct sm_element
Definition: sparse.h:21
sm_element * first_col
Definition: sparse.h:48