47 #ifndef EIGEN_COLAMD_H 48 #define EIGEN_COLAMD_H 65 const int NKnobs = 20;
68 const int NStats = 20;
71 enum KnobsStatsIndex {
94 ErrorANotPresent = -1,
95 ErrorPNotPresent = -2,
96 ErrorNrowNegative = -3,
97 ErrorNcolNegative = -4,
98 ErrorNnzNegative = -5,
101 ErrorColLengthNegative = -8,
102 ErrorRowIndexOutOfBounds = -9,
103 ErrorOutOfMemory = -10,
104 ErrorInternalError = -999
110 template <
typename IndexType>
111 IndexType ones_complement(
const IndexType r) {
116 const int Empty = -1;
119 enum RowColumnStatus {
127 DeadNonPrincipal = -2
135 template <
typename IndexType>
143 IndexType thickness ;
163 IndexType degree_next ;
164 IndexType hash_next ;
167 inline bool is_dead()
const {
return start < Alive; }
169 inline bool is_alive()
const {
return start >= Alive; }
171 inline bool is_dead_principal()
const {
return start == DeadPrincipal; }
173 inline void kill_principal() { start = DeadPrincipal; }
175 inline void kill_non_principal() { start = DeadNonPrincipal; }
179 template <
typename IndexType>
192 IndexType first_column ;
195 inline bool is_dead()
const {
return shared2.mark < Alive; }
197 inline bool is_alive()
const {
return shared2.mark >= Alive; }
199 inline void kill() { shared2.mark = Dead; }
221 template <
typename IndexType>
222 inline IndexType colamd_c(IndexType n_col)
223 {
return IndexType( ((n_col) + 1) *
sizeof (ColStructure<IndexType>) /
sizeof (IndexType) ) ; }
225 template <
typename IndexType>
226 inline IndexType colamd_r(IndexType n_row)
227 {
return IndexType(((n_row) + 1) *
sizeof (RowStructure<IndexType>) /
sizeof (IndexType)); }
230 template <
typename IndexType>
231 static IndexType init_rows_cols (IndexType n_row, IndexType n_col, RowStructure<IndexType> Row [], ColStructure<IndexType> col [], IndexType A [], IndexType p [], IndexType stats[NStats] );
233 template <
typename IndexType>
234 static void init_scoring (IndexType n_row, IndexType n_col, RowStructure<IndexType> Row [], ColStructure<IndexType> Col [], IndexType A [], IndexType head [],
double knobs[NKnobs], IndexType *p_n_row2, IndexType *p_n_col2, IndexType *p_max_deg);
236 template <
typename IndexType>
237 static IndexType find_ordering (IndexType n_row, IndexType n_col, IndexType Alen, RowStructure<IndexType> Row [], ColStructure<IndexType> Col [], IndexType A [], IndexType head [], IndexType n_col2, IndexType max_deg, IndexType pfree);
239 template <
typename IndexType>
240 static void order_children (IndexType n_col, ColStructure<IndexType> Col [], IndexType p []);
242 template <
typename IndexType>
243 static void detect_super_cols (ColStructure<IndexType> Col [], IndexType A [], IndexType head [], IndexType row_start, IndexType row_length ) ;
245 template <
typename IndexType>
246 static IndexType garbage_collection (IndexType n_row, IndexType n_col, RowStructure<IndexType> Row [], ColStructure<IndexType> Col [], IndexType A [], IndexType *pfree) ;
248 template <
typename IndexType>
249 static inline IndexType clear_mark (IndexType n_row, RowStructure<IndexType> Row [] ) ;
253 #define COLAMD_DEBUG0(params) ; 254 #define COLAMD_DEBUG1(params) ; 255 #define COLAMD_DEBUG2(params) ; 256 #define COLAMD_DEBUG3(params) ; 257 #define COLAMD_DEBUG4(params) ; 259 #define COLAMD_ASSERT(expression) ((void) 0) 276 template <
typename IndexType>
277 inline IndexType recommended ( IndexType nnz, IndexType n_row, IndexType n_col)
279 if ((nnz) < 0 || (n_row) < 0 || (n_col) < 0)
282 return (2 * (nnz) + colamd_c (n_col) + colamd_r (n_row) + (n_col) + ((nnz) / 5));
306 static inline void set_defaults(
double knobs[NKnobs])
316 for (i = 0 ; i < NKnobs ; i++)
320 knobs [Colamd::DenseRow] = 0.5 ;
321 knobs [Colamd::DenseCol] = 0.5 ;
341 template <
typename IndexType>
342 static bool compute_ordering(IndexType n_row, IndexType n_col, IndexType Alen, IndexType *A, IndexType *p,
double knobs[NKnobs], IndexType stats[NStats])
351 Colamd::RowStructure<IndexType> *Row ;
352 Colamd::ColStructure<IndexType> *Col ;
357 double default_knobs [NKnobs] ;
364 COLAMD_DEBUG0 ((
"colamd: stats not present\n")) ;
367 for (i = 0 ; i < NStats ; i++)
371 stats [Colamd::Status] = Colamd::Ok ;
372 stats [Colamd::Info1] = -1 ;
373 stats [Colamd::Info2] = -1 ;
377 stats [Colamd::Status] = Colamd::ErrorANotPresent ;
378 COLAMD_DEBUG0 ((
"colamd: A not present\n")) ;
384 stats [Colamd::Status] = Colamd::ErrorPNotPresent ;
385 COLAMD_DEBUG0 ((
"colamd: p not present\n")) ;
391 stats [Colamd::Status] = Colamd::ErrorNrowNegative ;
392 stats [Colamd::Info1] = n_row ;
393 COLAMD_DEBUG0 ((
"colamd: nrow negative %d\n", n_row)) ;
399 stats [Colamd::Status] = Colamd::ErrorNcolNegative ;
400 stats [Colamd::Info1] = n_col ;
401 COLAMD_DEBUG0 ((
"colamd: ncol negative %d\n", n_col)) ;
408 stats [Colamd::Status] = Colamd::ErrorNnzNegative ;
409 stats [Colamd::Info1] = nnz ;
410 COLAMD_DEBUG0 ((
"colamd: number of entries negative %d\n", nnz)) ;
416 stats [Colamd::Status] = Colamd::ErrorP0Nonzero ;
417 stats [Colamd::Info1] = p [0] ;
418 COLAMD_DEBUG0 ((
"colamd: p[0] not zero %d\n", p [0])) ;
426 set_defaults (default_knobs) ;
427 knobs = default_knobs ;
432 Col_size = colamd_c (n_col) ;
433 Row_size = colamd_r (n_row) ;
434 need = 2*nnz + n_col + Col_size + Row_size ;
439 stats [Colamd::Status] = Colamd::ErrorATooSmall ;
440 stats [Colamd::Info1] = need ;
441 stats [Colamd::Info2] = Alen ;
442 COLAMD_DEBUG0 ((
"colamd: Need Alen >= %d, given only Alen = %d\n", need,Alen));
446 Alen -= Col_size + Row_size ;
447 Col = (ColStructure<IndexType> *) &A [Alen] ;
448 Row = (RowStructure<IndexType> *) &A [Alen + Col_size] ;
452 if (!Colamd::init_rows_cols (n_row, n_col, Row, Col, A, p, stats))
455 COLAMD_DEBUG0 ((
"colamd: Matrix invalid\n")) ;
461 Colamd::init_scoring (n_row, n_col, Row, Col, A, p, knobs,
462 &n_row2, &n_col2, &max_deg) ;
466 ngarbage = Colamd::find_ordering (n_row, n_col, Alen, Row, Col, A, p,
467 n_col2, max_deg, 2*nnz) ;
471 Colamd::order_children (n_col, Col, p) ;
475 stats [Colamd::DenseRow] = n_row - n_row2 ;
476 stats [Colamd::DenseCol] = n_col - n_col2 ;
477 stats [Colamd::DefragCount] = ngarbage ;
478 COLAMD_DEBUG0 ((
"colamd: done.\n")) ;
500 template <
typename IndexType>
501 static IndexType init_rows_cols
507 RowStructure<IndexType> Row [],
508 ColStructure<IndexType> Col [],
511 IndexType stats [NStats]
526 for (col = 0 ; col < n_col ; col++)
528 Col [col].start = p [col] ;
529 Col [col].length = p [col+1] - p [col] ;
531 if ((Col [col].length) < 0)
534 stats [Colamd::Status] = Colamd::ErrorColLengthNegative ;
535 stats [Colamd::Info1] = col ;
536 stats [Colamd::Info2] = Col [col].length ;
537 COLAMD_DEBUG0 ((
"colamd: col %d length %d < 0\n", col, Col [col].length)) ;
541 Col [col].shared1.thickness = 1 ;
542 Col [col].shared2.score = 0 ;
543 Col [col].shared3.prev = Empty ;
544 Col [col].shared4.degree_next = Empty ;
553 for (row = 0 ; row < n_row ; row++)
555 Row [row].length = 0 ;
556 Row [row].shared2.mark = -1 ;
559 for (col = 0 ; col < n_col ; col++)
564 cp_end = &A [p [col+1]] ;
571 if (row < 0 || row >= n_row)
573 stats [Colamd::Status] = Colamd::ErrorRowIndexOutOfBounds ;
574 stats [Colamd::Info1] = col ;
575 stats [Colamd::Info2] = row ;
576 stats [Colamd::Info3] = n_row ;
577 COLAMD_DEBUG0 ((
"colamd: row %d col %d out of bounds\n", row, col)) ;
581 if (row <= last_row || Row [row].shared2.mark == col)
585 stats [Colamd::Status] = Colamd::OkButJumbled ;
586 stats [Colamd::Info1] = col ;
587 stats [Colamd::Info2] = row ;
588 (stats [Colamd::Info3]) ++ ;
589 COLAMD_DEBUG1 ((
"colamd: row %d col %d unsorted/duplicate\n",row,col));
592 if (Row [row].shared2.mark != col)
604 Row [row].shared2.mark = col ;
614 Row [0].start = p [n_col] ;
615 Row [0].shared1.p = Row [0].start ;
616 Row [0].shared2.mark = -1 ;
617 for (row = 1 ; row < n_row ; row++)
619 Row [row].start = Row [row-1].start + Row [row-1].length ;
620 Row [row].shared1.p = Row [row].start ;
621 Row [row].shared2.mark = -1 ;
626 if (stats [Status] == OkButJumbled)
629 for (col = 0 ; col < n_col ; col++)
632 cp_end = &A [p [col+1]] ;
636 if (Row [row].shared2.mark != col)
638 A [(Row [row].shared1.p)++] = col ;
639 Row [row].shared2.mark = col ;
647 for (col = 0 ; col < n_col ; col++)
650 cp_end = &A [p [col+1]] ;
653 A [(Row [*cp++].shared1.p)++] = col ;
660 for (row = 0 ; row < n_row ; row++)
662 Row [row].shared2.mark = 0 ;
663 Row [row].shared1.degree = Row [row].length ;
668 if (stats [Status] == OkButJumbled)
670 COLAMD_DEBUG0 ((
"colamd: reconstructing column form, matrix jumbled\n")) ;
680 p [0] = Col [0].start ;
681 for (col = 1 ; col < n_col ; col++)
685 Col [col].start = Col [col-1].start + Col [col-1].length ;
686 p [col] = Col [col].start ;
691 for (row = 0 ; row < n_row ; row++)
693 rp = &A [Row [row].start] ;
694 rp_end = rp + Row [row].length ;
697 A [(p [*rp++])++] = row ;
716 template <
typename IndexType>
717 static void init_scoring
723 RowStructure<IndexType> Row [],
724 ColStructure<IndexType> Col [],
727 double knobs [NKnobs],
741 IndexType col_length ;
745 IndexType dense_row_count ;
746 IndexType dense_col_count ;
747 IndexType min_score ;
754 dense_row_count = numext::maxi(IndexType(0), numext::mini(IndexType(knobs [Colamd::DenseRow] * n_col), n_col)) ;
755 dense_col_count = numext::maxi(IndexType(0), numext::mini(IndexType(knobs [Colamd::DenseCol] * n_row), n_row)) ;
756 COLAMD_DEBUG1 ((
"colamd: densecount: %d %d\n", dense_row_count, dense_col_count)) ;
765 for (c = n_col-1 ; c >= 0 ; c--)
767 deg = Col [c].length ;
771 Col [c].shared2.order = --n_col2 ;
772 Col[c].kill_principal() ;
775 COLAMD_DEBUG1 ((
"colamd: null columns killed: %d\n", n_col - n_col2)) ;
780 for (c = n_col-1 ; c >= 0 ; c--)
783 if (Col[c].is_dead())
787 deg = Col [c].length ;
788 if (deg > dense_col_count)
791 Col [c].shared2.order = --n_col2 ;
793 cp = &A [Col [c].start] ;
794 cp_end = cp + Col [c].length ;
797 Row [*cp++].shared1.degree-- ;
799 Col[c].kill_principal() ;
802 COLAMD_DEBUG1 ((
"colamd: Dense and null columns killed: %d\n", n_col - n_col2)) ;
806 for (r = 0 ; r < n_row ; r++)
808 deg = Row [r].shared1.degree ;
809 COLAMD_ASSERT (deg >= 0 && deg <= n_col) ;
810 if (deg > dense_row_count || deg == 0)
819 max_deg = numext::maxi(max_deg, deg) ;
822 COLAMD_DEBUG1 ((
"colamd: Dense and null rows killed: %d\n", n_row - n_row2)) ;
832 for (c = n_col-1 ; c >= 0 ; c--)
835 if (Col[c].is_dead())
840 cp = &A [Col [c].start] ;
842 cp_end = cp + Col [c].length ;
848 if (Row[row].is_dead())
855 score += Row [row].shared1.degree - 1 ;
857 score = numext::mini(score, n_col) ;
860 col_length = (IndexType) (new_cp - &A [Col [c].start]) ;
865 COLAMD_DEBUG2 ((
"Newly null killed: %d\n", c)) ;
866 Col [c].shared2.order = --n_col2 ;
867 Col[c].kill_principal() ;
872 COLAMD_ASSERT (score >= 0) ;
873 COLAMD_ASSERT (score <= n_col) ;
874 Col [c].length = col_length ;
875 Col [c].shared2.score = score ;
878 COLAMD_DEBUG1 ((
"colamd: Dense, null, and newly-null columns killed: %d\n",
890 for (c = 0 ; c <= n_col ; c++)
897 for (c = n_col-1 ; c >= 0 ; c--)
900 if (Col[c].is_alive())
902 COLAMD_DEBUG4 ((
"place %d score %d minscore %d ncol %d\n",
903 c, Col [c].shared2.score, min_score, n_col)) ;
907 score = Col [c].shared2.score ;
909 COLAMD_ASSERT (min_score >= 0) ;
910 COLAMD_ASSERT (min_score <= n_col) ;
911 COLAMD_ASSERT (score >= 0) ;
912 COLAMD_ASSERT (score <= n_col) ;
913 COLAMD_ASSERT (head [score] >= Empty) ;
916 next_col = head [score] ;
917 Col [c].shared3.prev = Empty ;
918 Col [c].shared4.degree_next = next_col ;
922 if (next_col != Empty)
924 Col [next_col].shared3.prev = c ;
929 min_score = numext::mini(min_score, score) ;
940 *p_max_deg = max_deg ;
953 template <
typename IndexType>
954 static IndexType find_ordering
961 RowStructure<IndexType> Row [],
962 ColStructure<IndexType> Col [],
973 IndexType pivot_col ;
976 IndexType pivot_row ;
979 IndexType pivot_row_start ;
980 IndexType pivot_row_degree ;
981 IndexType pivot_row_length ;
982 IndexType pivot_col_score ;
983 IndexType needed_memory ;
988 IndexType max_score ;
989 IndexType cur_score ;
991 IndexType head_column ;
992 IndexType first_col ;
995 IndexType set_difference ;
996 IndexType min_score ;
997 IndexType col_thickness ;
999 IndexType pivot_col_thickness ;
1000 IndexType prev_col ;
1001 IndexType next_col ;
1002 IndexType ngarbage ;
1007 max_mark = INT_MAX - n_col ;
1008 tag_mark = Colamd::clear_mark (n_row, Row) ;
1011 COLAMD_DEBUG1 ((
"colamd: Ordering, n_col2=%d\n", n_col2)) ;
1015 for (k = 0 ; k < n_col2 ; )
1021 COLAMD_ASSERT (min_score >= 0) ;
1022 COLAMD_ASSERT (min_score <= n_col) ;
1023 COLAMD_ASSERT (head [min_score] >= Empty) ;
1026 while (min_score < n_col && head [min_score] == Empty)
1030 pivot_col = head [min_score] ;
1031 COLAMD_ASSERT (pivot_col >= 0 && pivot_col <= n_col) ;
1032 next_col = Col [pivot_col].shared4.degree_next ;
1033 head [min_score] = next_col ;
1034 if (next_col != Empty)
1036 Col [next_col].shared3.prev = Empty ;
1039 COLAMD_ASSERT (Col[pivot_col].is_alive()) ;
1040 COLAMD_DEBUG3 ((
"Pivot col: %d\n", pivot_col)) ;
1043 pivot_col_score = Col [pivot_col].shared2.score ;
1046 Col [pivot_col].shared2.order = k ;
1049 pivot_col_thickness = Col [pivot_col].shared1.thickness ;
1050 k += pivot_col_thickness ;
1051 COLAMD_ASSERT (pivot_col_thickness > 0) ;
1055 needed_memory = numext::mini(pivot_col_score, n_col - k) ;
1056 if (pfree + needed_memory >= Alen)
1058 pfree = Colamd::garbage_collection (n_row, n_col, Row, Col, A, &A [pfree]) ;
1061 COLAMD_ASSERT (pfree + needed_memory < Alen) ;
1063 tag_mark = Colamd::clear_mark (n_row, Row) ;
1070 pivot_row_start = pfree ;
1073 pivot_row_degree = 0 ;
1077 Col [pivot_col].shared1.thickness = -pivot_col_thickness ;
1080 cp = &A [Col [pivot_col].start] ;
1081 cp_end = cp + Col [pivot_col].length ;
1086 COLAMD_DEBUG4 ((
"Pivot col pattern %d %d\n", Row[row].is_alive(), row)) ;
1088 if (Row[row].is_dead())
1092 rp = &A [Row [row].start] ;
1093 rp_end = rp + Row [row].length ;
1099 col_thickness = Col [col].shared1.thickness ;
1100 if (col_thickness > 0 && Col[col].is_alive())
1103 Col [col].shared1.thickness = -col_thickness ;
1104 COLAMD_ASSERT (pfree < Alen) ;
1107 pivot_row_degree += col_thickness ;
1113 Col [pivot_col].shared1.thickness = pivot_col_thickness ;
1114 max_deg = numext::maxi(max_deg, pivot_row_degree) ;
1120 cp = &A [Col [pivot_col].start] ;
1121 cp_end = cp + Col [pivot_col].length ;
1126 COLAMD_DEBUG3 ((
"Kill row in pivot col: %d\n", row)) ;
1132 pivot_row_length = pfree - pivot_row_start ;
1133 if (pivot_row_length > 0)
1136 pivot_row = A [Col [pivot_col].start] ;
1137 COLAMD_DEBUG3 ((
"Pivotal row is %d\n", pivot_row)) ;
1143 COLAMD_ASSERT (pivot_row_length == 0) ;
1145 COLAMD_ASSERT (Col [pivot_col].length > 0 || pivot_row_length == 0) ;
1168 COLAMD_DEBUG3 ((
"** Computing set differences phase. **\n")) ;
1172 COLAMD_DEBUG3 ((
"Pivot row: ")) ;
1174 rp = &A [pivot_row_start] ;
1175 rp_end = rp + pivot_row_length ;
1179 COLAMD_ASSERT (Col[col].is_alive() && col != pivot_col) ;
1180 COLAMD_DEBUG3 ((
"Col: %d\n", col)) ;
1183 col_thickness = -Col [col].shared1.thickness ;
1184 COLAMD_ASSERT (col_thickness > 0) ;
1185 Col [col].shared1.thickness = col_thickness ;
1189 cur_score = Col [col].shared2.score ;
1190 prev_col = Col [col].shared3.prev ;
1191 next_col = Col [col].shared4.degree_next ;
1192 COLAMD_ASSERT (cur_score >= 0) ;
1193 COLAMD_ASSERT (cur_score <= n_col) ;
1194 COLAMD_ASSERT (cur_score >= Empty) ;
1195 if (prev_col == Empty)
1197 head [cur_score] = next_col ;
1201 Col [prev_col].shared4.degree_next = next_col ;
1203 if (next_col != Empty)
1205 Col [next_col].shared3.prev = prev_col ;
1210 cp = &A [Col [col].start] ;
1211 cp_end = cp + Col [col].length ;
1217 if (Row[row].is_dead())
1221 row_mark = Row [row].shared2.mark ;
1222 COLAMD_ASSERT (row != pivot_row) ;
1223 set_difference = row_mark - tag_mark ;
1225 if (set_difference < 0)
1227 COLAMD_ASSERT (Row [row].shared1.degree <= max_deg) ;
1228 set_difference = Row [row].shared1.degree ;
1231 set_difference -= col_thickness ;
1232 COLAMD_ASSERT (set_difference >= 0) ;
1234 if (set_difference == 0)
1236 COLAMD_DEBUG3 ((
"aggressive absorption. Row: %d\n", row)) ;
1242 Row [row].shared2.mark = set_difference + tag_mark ;
1250 COLAMD_DEBUG3 ((
"** Adding set differences phase. **\n")) ;
1253 rp = &A [pivot_row_start] ;
1254 rp_end = rp + pivot_row_length ;
1259 COLAMD_ASSERT (Col[col].is_alive() && col != pivot_col) ;
1262 cp = &A [Col [col].start] ;
1265 cp_end = cp + Col [col].length ;
1267 COLAMD_DEBUG4 ((
"Adding set diffs for Col: %d.\n", col)) ;
1273 COLAMD_ASSERT(row >= 0 && row < n_row) ;
1275 if (Row [row].is_dead())
1279 row_mark = Row [row].shared2.mark ;
1280 COLAMD_ASSERT (row_mark > tag_mark) ;
1286 cur_score += row_mark - tag_mark ;
1288 cur_score = numext::mini(cur_score, n_col) ;
1292 Col [col].length = (IndexType) (new_cp - &A [Col [col].start]) ;
1296 if (Col [col].length == 0)
1298 COLAMD_DEBUG4 ((
"further mass elimination. Col: %d\n", col)) ;
1300 Col[col].kill_principal() ;
1301 pivot_row_degree -= Col [col].shared1.thickness ;
1302 COLAMD_ASSERT (pivot_row_degree >= 0) ;
1304 Col [col].shared2.order = k ;
1306 k += Col [col].shared1.thickness ;
1312 COLAMD_DEBUG4 ((
"Preparing supercol detection for Col: %d.\n", col)) ;
1315 Col [col].shared2.score = cur_score ;
1320 COLAMD_DEBUG4 ((
" Hash = %d, n_col = %d.\n", hash, n_col)) ;
1321 COLAMD_ASSERT (hash <= n_col) ;
1323 head_column = head [hash] ;
1324 if (head_column > Empty)
1328 first_col = Col [head_column].shared3.headhash ;
1329 Col [head_column].shared3.headhash = col ;
1334 first_col = - (head_column + 2) ;
1335 head [hash] = - (col + 2) ;
1337 Col [col].shared4.hash_next = first_col ;
1340 Col [col].shared3.hash = (IndexType) hash ;
1341 COLAMD_ASSERT (Col[col].is_alive()) ;
1349 COLAMD_DEBUG3 ((
"** Supercolumn detection phase. **\n")) ;
1351 Colamd::detect_super_cols (Col, A, head, pivot_row_start, pivot_row_length) ;
1355 Col[pivot_col].kill_principal() ;
1359 tag_mark += (max_deg + 1) ;
1360 if (tag_mark >= max_mark)
1362 COLAMD_DEBUG2 ((
"clearing tag_mark\n")) ;
1363 tag_mark = Colamd::clear_mark (n_row, Row) ;
1368 COLAMD_DEBUG3 ((
"** Finalize scores phase. **\n")) ;
1371 rp = &A [pivot_row_start] ;
1374 rp_end = rp + pivot_row_length ;
1379 if (Col[col].is_dead())
1385 A [Col [col].start + (Col [col].length++)] = pivot_row ;
1390 cur_score = Col [col].shared2.score + pivot_row_degree ;
1395 max_score = n_col - k - Col [col].shared1.thickness ;
1398 cur_score -= Col [col].shared1.thickness ;
1401 cur_score = numext::mini(cur_score, max_score) ;
1402 COLAMD_ASSERT (cur_score >= 0) ;
1405 Col [col].shared2.score = cur_score ;
1409 COLAMD_ASSERT (min_score >= 0) ;
1410 COLAMD_ASSERT (min_score <= n_col) ;
1411 COLAMD_ASSERT (cur_score >= 0) ;
1412 COLAMD_ASSERT (cur_score <= n_col) ;
1413 COLAMD_ASSERT (head [cur_score] >= Empty) ;
1414 next_col = head [cur_score] ;
1415 Col [col].shared4.degree_next = next_col ;
1416 Col [col].shared3.prev = Empty ;
1417 if (next_col != Empty)
1419 Col [next_col].shared3.prev = col ;
1421 head [cur_score] = col ;
1424 min_score = numext::mini(min_score, cur_score) ;
1430 if (pivot_row_degree > 0)
1434 Row [pivot_row].start = pivot_row_start ;
1435 Row [pivot_row].length = (IndexType) (new_rp - &A[pivot_row_start]) ;
1436 Row [pivot_row].shared1.degree = pivot_row_degree ;
1437 Row [pivot_row].shared2.mark = 0 ;
1464 template <
typename IndexType>
1465 static inline void order_children
1470 ColStructure<IndexType> Col [],
1483 for (i = 0 ; i < n_col ; i++)
1486 COLAMD_ASSERT (col_is_dead(Col, i)) ;
1487 if (!Col[i].is_dead_principal() && Col [i].shared2.order == Empty)
1493 parent = Col [parent].shared1.parent ;
1494 }
while (!Col[parent].is_dead_principal()) ;
1500 order = Col [parent].shared2.order ;
1504 COLAMD_ASSERT (Col [c].shared2.order == Empty) ;
1507 Col [c].shared2.order = order++ ;
1509 Col [c].shared1.parent = parent ;
1512 c = Col [c].shared1.parent ;
1517 }
while (Col [c].shared2.order == Empty) ;
1520 Col [parent].shared2.order = order ;
1526 for (c = 0 ; c < n_col ; c++)
1528 p [Col [c].shared2.order] = c ;
1565 template <
typename IndexType>
1566 static void detect_super_cols
1570 ColStructure<IndexType> Col [],
1573 IndexType row_start,
1574 IndexType row_length
1590 IndexType head_column ;
1591 IndexType first_col ;
1595 rp = &A [row_start] ;
1596 rp_end = rp + row_length ;
1600 if (Col[col].is_dead())
1606 hash = Col [col].shared3.hash ;
1607 COLAMD_ASSERT (hash <= n_col) ;
1611 head_column = head [hash] ;
1612 if (head_column > Empty)
1614 first_col = Col [head_column].shared3.headhash ;
1618 first_col = - (head_column + 2) ;
1623 for (super_c = first_col ; super_c != Empty ;
1624 super_c = Col [super_c].shared4.hash_next)
1626 COLAMD_ASSERT (Col [super_c].is_alive()) ;
1627 COLAMD_ASSERT (Col [super_c].shared3.hash == hash) ;
1628 length = Col [super_c].length ;
1635 for (c = Col [super_c].shared4.hash_next ;
1636 c != Empty ; c = Col [c].shared4.hash_next)
1638 COLAMD_ASSERT (c != super_c) ;
1639 COLAMD_ASSERT (Col[c].is_alive()) ;
1640 COLAMD_ASSERT (Col [c].shared3.hash == hash) ;
1643 if (Col [c].length != length ||
1644 Col [c].shared2.score != Col [super_c].shared2.score)
1651 cp1 = &A [Col [super_c].start] ;
1652 cp2 = &A [Col [c].start] ;
1654 for (i = 0 ; i < length ; i++)
1657 COLAMD_ASSERT ( cp1->is_alive() );
1658 COLAMD_ASSERT ( cp2->is_alive() );
1661 if (*cp1++ != *cp2++)
1676 COLAMD_ASSERT (Col [c].shared2.score == Col [super_c].shared2.score) ;
1678 Col [super_c].shared1.thickness += Col [c].shared1.thickness ;
1679 Col [c].shared1.parent = super_c ;
1680 Col[c].kill_non_principal() ;
1682 Col [c].shared2.order = Empty ;
1684 Col [prev_c].shared4.hash_next = Col [c].shared4.hash_next ;
1690 if (head_column > Empty)
1693 Col [head_column].shared3.headhash = Empty ;
1698 head [hash] = Empty ;
1716 template <
typename IndexType>
1717 static IndexType garbage_collection
1723 RowStructure<IndexType> Row [],
1724 ColStructure<IndexType> Col [],
1741 for (c = 0 ; c < n_col ; c++)
1743 if (Col[c].is_alive())
1745 psrc = &A [Col [c].start] ;
1748 COLAMD_ASSERT (pdest <= psrc) ;
1749 Col [c].start = (IndexType) (pdest - &A [0]) ;
1750 length = Col [c].length ;
1751 for (j = 0 ; j < length ; j++)
1754 if (Row[r].is_alive())
1759 Col [c].length = (IndexType) (pdest - &A [Col [c].start]) ;
1765 for (r = 0 ; r < n_row ; r++)
1767 if (Row[r].is_alive())
1769 if (Row [r].length == 0)
1772 COLAMD_DEBUG3 ((
"Defrag row kill\n")) ;
1778 psrc = &A [Row [r].start] ;
1779 Row [r].shared2.first_column = *psrc ;
1780 COLAMD_ASSERT (Row[r].is_alive()) ;
1782 *psrc = ones_complement(r) ;
1791 while (psrc < pfree)
1798 r = ones_complement(*psrc) ;
1799 COLAMD_ASSERT (r >= 0 && r < n_row) ;
1801 *psrc = Row [r].shared2.first_column ;
1802 COLAMD_ASSERT (Row[r].is_alive()) ;
1805 COLAMD_ASSERT (pdest <= psrc) ;
1806 Row [r].start = (IndexType) (pdest - &A [0]) ;
1807 length = Row [r].length ;
1808 for (j = 0 ; j < length ; j++)
1811 if (Col[c].is_alive())
1816 Row [r].length = (IndexType) (pdest - &A [Row [r].start]) ;
1821 COLAMD_ASSERT (debug_rows == 0) ;
1825 return ((IndexType) (pdest - &A [0])) ;
1837 template <
typename IndexType>
1838 static inline IndexType clear_mark
1843 RowStructure<IndexType> Row []
1850 for (r = 0 ; r < n_row ; r++)
1852 if (Row[r].is_alive())
1854 Row [r].shared2.mark = 0 ;
Definition: Eigen_Colamd.h:50