This repository has been archived by the owner on Apr 16, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Eigen__Colamd_8h_source.html
1936 lines (1934 loc) · 253 KB
/
Eigen__Colamd_8h_source.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.9.7"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>Eigen: Eigen_Colamd.h Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(document).ready(function() { init_search(); });
/* @license-end */
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
extensions: ["tex2jax.js", "TeX/AMSmath.js", "TeX/AMSsymbols.js"],
jax: ["input/TeX","output/HTML-CSS"],
});
</script>
<script type="text/javascript" async="async" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
<link href="eigendoxy.css" rel="stylesheet" type="text/css">
<!-- -->
<script type="text/javascript" src="eigen_navtree_hacks.js"></script>
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td id="projectlogo"><img alt="Logo" src="Eigen_Silly_Professor_64x64.png"/></td>
<td id="projectalign" style="padding-left: 0.5em;">
<div id="projectname"><a href="http://eigen.tuxfamily.org">Eigen</a>
 <span id="projectnumber">3.4.90 (git rev 21cd3fe20990a5ac1d683806f605110962aac3f1)</span>
</div>
</td>
<td> <div id="MSearchBox" class="MSearchBoxInactive">
<span class="left">
<span id="MSearchSelect" onmouseover="return searchBox.OnSearchSelectShow()" onmouseout="return searchBox.OnSearchSelectHide()"> </span>
<input type="text" id="MSearchField" value="" placeholder="Search" accesskey="S"
onfocus="searchBox.OnSearchFieldFocus(true)"
onblur="searchBox.OnSearchFieldFocus(false)"
onkeyup="searchBox.OnSearchFieldChange(event)"/>
</span><span class="right">
<a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.svg" alt=""/></a>
</span>
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.9.7 -->
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
var searchBox = new SearchBox("searchBox", "search/",'.html');
/* @license-end */
</script>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
<div id="nav-tree">
<div id="nav-tree-contents">
<div id="nav-sync" class="sync"></div>
</div>
</div>
<div id="splitbar" style="-moz-user-select:none;"
class="ui-resizable-handle">
</div>
</div>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(document).ready(function(){initNavTree('Eigen__Colamd_8h_source.html',''); initResizable(); });
/* @license-end */
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>
<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<div id="MSearchResults">
<div class="SRPage">
<div id="SRIndex">
<div id="SRResults"></div>
<div class="SRStatus" id="Loading">Loading...</div>
<div class="SRStatus" id="Searching">Searching...</div>
<div class="SRStatus" id="NoMatches">No Matches</div>
</div>
</div>
</div>
</div>
<div class="header">
<div class="headertitle"><div class="title">Eigen_Colamd.h</div></div>
</div><!--header-->
<div class="contents">
<div class="fragment"><div class="line"><a id="l00001" name="l00001"></a><span class="lineno"> 1</span><span class="comment">// // This file is part of Eigen, a lightweight C++ template library</span></div>
<div class="line"><a id="l00002" name="l00002"></a><span class="lineno"> 2</span><span class="comment">// for linear algebra.</span></div>
<div class="line"><a id="l00003" name="l00003"></a><span class="lineno"> 3</span><span class="comment">//</span></div>
<div class="line"><a id="l00004" name="l00004"></a><span class="lineno"> 4</span><span class="comment">// Copyright (C) 2012 Desire Nuentsa Wakam <desire.nuentsa_wakam@inria.fr></span></div>
<div class="line"><a id="l00005" name="l00005"></a><span class="lineno"> 5</span><span class="comment">//</span></div>
<div class="line"><a id="l00006" name="l00006"></a><span class="lineno"> 6</span><span class="comment">// This Source Code Form is subject to the terms of the Mozilla</span></div>
<div class="line"><a id="l00007" name="l00007"></a><span class="lineno"> 7</span><span class="comment">// Public License v. 2.0. If a copy of the MPL was not distributed</span></div>
<div class="line"><a id="l00008" name="l00008"></a><span class="lineno"> 8</span><span class="comment">// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.</span></div>
<div class="line"><a id="l00009" name="l00009"></a><span class="lineno"> 9</span> </div>
<div class="line"><a id="l00010" name="l00010"></a><span class="lineno"> 10</span><span class="comment">// This file is modified from the colamd/symamd library. The copyright is below</span></div>
<div class="line"><a id="l00011" name="l00011"></a><span class="lineno"> 11</span> </div>
<div class="line"><a id="l00012" name="l00012"></a><span class="lineno"> 12</span><span class="comment">// The authors of the code itself are Stefan I. Larimore and Timothy A.</span></div>
<div class="line"><a id="l00013" name="l00013"></a><span class="lineno"> 13</span><span class="comment">// Davis (davis@cise.ufl.edu), University of Florida. The algorithm was</span></div>
<div class="line"><a id="l00014" name="l00014"></a><span class="lineno"> 14</span><span class="comment">// developed in collaboration with John Gilbert, Xerox PARC, and Esmond</span></div>
<div class="line"><a id="l00015" name="l00015"></a><span class="lineno"> 15</span><span class="comment">// Ng, Oak Ridge National Laboratory.</span></div>
<div class="line"><a id="l00016" name="l00016"></a><span class="lineno"> 16</span><span class="comment">//</span></div>
<div class="line"><a id="l00017" name="l00017"></a><span class="lineno"> 17</span><span class="comment">// Date:</span></div>
<div class="line"><a id="l00018" name="l00018"></a><span class="lineno"> 18</span><span class="comment">//</span></div>
<div class="line"><a id="l00019" name="l00019"></a><span class="lineno"> 19</span><span class="comment">// September 8, 2003. Version 2.3.</span></div>
<div class="line"><a id="l00020" name="l00020"></a><span class="lineno"> 20</span><span class="comment">//</span></div>
<div class="line"><a id="l00021" name="l00021"></a><span class="lineno"> 21</span><span class="comment">// Acknowledgements:</span></div>
<div class="line"><a id="l00022" name="l00022"></a><span class="lineno"> 22</span><span class="comment">//</span></div>
<div class="line"><a id="l00023" name="l00023"></a><span class="lineno"> 23</span><span class="comment">// This work was supported by the National Science Foundation, under</span></div>
<div class="line"><a id="l00024" name="l00024"></a><span class="lineno"> 24</span><span class="comment">// grants DMS-9504974 and DMS-9803599.</span></div>
<div class="line"><a id="l00025" name="l00025"></a><span class="lineno"> 25</span><span class="comment">//</span></div>
<div class="line"><a id="l00026" name="l00026"></a><span class="lineno"> 26</span><span class="comment">// Notice:</span></div>
<div class="line"><a id="l00027" name="l00027"></a><span class="lineno"> 27</span><span class="comment">//</span></div>
<div class="line"><a id="l00028" name="l00028"></a><span class="lineno"> 28</span><span class="comment">// Copyright (c) 1998-2003 by the University of Florida.</span></div>
<div class="line"><a id="l00029" name="l00029"></a><span class="lineno"> 29</span><span class="comment">// All Rights Reserved.</span></div>
<div class="line"><a id="l00030" name="l00030"></a><span class="lineno"> 30</span><span class="comment">//</span></div>
<div class="line"><a id="l00031" name="l00031"></a><span class="lineno"> 31</span><span class="comment">// THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY</span></div>
<div class="line"><a id="l00032" name="l00032"></a><span class="lineno"> 32</span><span class="comment">// EXPRESSED OR IMPLIED. ANY USE IS AT YOUR OWN RISK.</span></div>
<div class="line"><a id="l00033" name="l00033"></a><span class="lineno"> 33</span><span class="comment">//</span></div>
<div class="line"><a id="l00034" name="l00034"></a><span class="lineno"> 34</span><span class="comment">// Permission is hereby granted to use, copy, modify, and/or distribute</span></div>
<div class="line"><a id="l00035" name="l00035"></a><span class="lineno"> 35</span><span class="comment">// this program, provided that the Copyright, this License, and the</span></div>
<div class="line"><a id="l00036" name="l00036"></a><span class="lineno"> 36</span><span class="comment">// Availability of the original version is retained on all copies and made</span></div>
<div class="line"><a id="l00037" name="l00037"></a><span class="lineno"> 37</span><span class="comment">// accessible to the end-user of any code or package that includes COLAMD</span></div>
<div class="line"><a id="l00038" name="l00038"></a><span class="lineno"> 38</span><span class="comment">// or any modified version of COLAMD.</span></div>
<div class="line"><a id="l00039" name="l00039"></a><span class="lineno"> 39</span><span class="comment">//</span></div>
<div class="line"><a id="l00040" name="l00040"></a><span class="lineno"> 40</span><span class="comment">// Availability:</span></div>
<div class="line"><a id="l00041" name="l00041"></a><span class="lineno"> 41</span><span class="comment">//</span></div>
<div class="line"><a id="l00042" name="l00042"></a><span class="lineno"> 42</span><span class="comment">// The colamd/symamd library is available at</span></div>
<div class="line"><a id="l00043" name="l00043"></a><span class="lineno"> 43</span><span class="comment">//</span></div>
<div class="line"><a id="l00044" name="l00044"></a><span class="lineno"> 44</span><span class="comment">// http://www.suitesparse.com</span></div>
<div class="line"><a id="l00045" name="l00045"></a><span class="lineno"> 45</span> </div>
<div class="line"><a id="l00046" name="l00046"></a><span class="lineno"> 46</span> </div>
<div class="line"><a id="l00047" name="l00047"></a><span class="lineno"> 47</span><span class="preprocessor">#ifndef EIGEN_COLAMD_H</span></div>
<div class="line"><a id="l00048" name="l00048"></a><span class="lineno"> 48</span><span class="preprocessor">#define EIGEN_COLAMD_H</span></div>
<div class="line"><a id="l00049" name="l00049"></a><span class="lineno"> 49</span> </div>
<div class="line"><a id="l00050" name="l00050"></a><span class="lineno"> 50</span><span class="keyword">namespace </span>internal {</div>
<div class="line"><a id="l00051" name="l00051"></a><span class="lineno"> 51</span> </div>
<div class="line"><a id="l00052" name="l00052"></a><span class="lineno"> 52</span><span class="keyword">namespace </span>Colamd {</div>
<div class="line"><a id="l00053" name="l00053"></a><span class="lineno"> 53</span> </div>
<div class="line"><a id="l00054" name="l00054"></a><span class="lineno"> 54</span><span class="comment">/* Ensure that debugging is turned off: */</span></div>
<div class="line"><a id="l00055" name="l00055"></a><span class="lineno"> 55</span><span class="preprocessor">#ifndef COLAMD_NDEBUG</span></div>
<div class="line"><a id="l00056" name="l00056"></a><span class="lineno"> 56</span><span class="preprocessor">#define COLAMD_NDEBUG</span></div>
<div class="line"><a id="l00057" name="l00057"></a><span class="lineno"> 57</span><span class="preprocessor">#endif </span><span class="comment">/* NDEBUG */</span><span class="preprocessor"></span></div>
<div class="line"><a id="l00058" name="l00058"></a><span class="lineno"> 58</span> </div>
<div class="line"><a id="l00059" name="l00059"></a><span class="lineno"> 59</span> </div>
<div class="line"><a id="l00060" name="l00060"></a><span class="lineno"> 60</span><span class="comment">/* ========================================================================== */</span></div>
<div class="line"><a id="l00061" name="l00061"></a><span class="lineno"> 61</span><span class="comment">/* === Knob and statistics definitions ====================================== */</span></div>
<div class="line"><a id="l00062" name="l00062"></a><span class="lineno"> 62</span><span class="comment">/* ========================================================================== */</span></div>
<div class="line"><a id="l00063" name="l00063"></a><span class="lineno"> 63</span> </div>
<div class="line"><a id="l00064" name="l00064"></a><span class="lineno"> 64</span><span class="comment">/* size of the knobs [ ] array. Only knobs [0..1] are currently used. */</span></div>
<div class="line"><a id="l00065" name="l00065"></a><span class="lineno"> 65</span><span class="keyword">const</span> <span class="keywordtype">int</span> NKnobs = 20;</div>
<div class="line"><a id="l00066" name="l00066"></a><span class="lineno"> 66</span> </div>
<div class="line"><a id="l00067" name="l00067"></a><span class="lineno"> 67</span><span class="comment">/* number of output statistics. Only stats [0..6] are currently used. */</span></div>
<div class="line"><a id="l00068" name="l00068"></a><span class="lineno"> 68</span><span class="keyword">const</span> <span class="keywordtype">int</span> NStats = 20;</div>
<div class="line"><a id="l00069" name="l00069"></a><span class="lineno"> 69</span> </div>
<div class="line"><a id="l00070" name="l00070"></a><span class="lineno"> 70</span><span class="comment">/* Indices into knobs and stats array. */</span></div>
<div class="line"><a id="l00071" name="l00071"></a><span class="lineno"> 71</span><span class="keyword">enum</span> KnobsStatsIndex {</div>
<div class="line"><a id="l00072" name="l00072"></a><span class="lineno"> 72</span> <span class="comment">/* knobs [0] and stats [0]: dense row knob and output statistic. */</span></div>
<div class="line"><a id="l00073" name="l00073"></a><span class="lineno"> 73</span> DenseRow = 0,</div>
<div class="line"><a id="l00074" name="l00074"></a><span class="lineno"> 74</span> </div>
<div class="line"><a id="l00075" name="l00075"></a><span class="lineno"> 75</span> <span class="comment">/* knobs [1] and stats [1]: dense column knob and output statistic. */</span></div>
<div class="line"><a id="l00076" name="l00076"></a><span class="lineno"> 76</span> DenseCol = 1,</div>
<div class="line"><a id="l00077" name="l00077"></a><span class="lineno"> 77</span> </div>
<div class="line"><a id="l00078" name="l00078"></a><span class="lineno"> 78</span> <span class="comment">/* stats [2]: memory defragmentation count output statistic */</span></div>
<div class="line"><a id="l00079" name="l00079"></a><span class="lineno"> 79</span> DefragCount = 2,</div>
<div class="line"><a id="l00080" name="l00080"></a><span class="lineno"> 80</span> </div>
<div class="line"><a id="l00081" name="l00081"></a><span class="lineno"> 81</span> <span class="comment">/* stats [3]: colamd status: zero OK, > 0 warning or notice, < 0 error */</span></div>
<div class="line"><a id="l00082" name="l00082"></a><span class="lineno"> 82</span> Status = 3,</div>
<div class="line"><a id="l00083" name="l00083"></a><span class="lineno"> 83</span> </div>
<div class="line"><a id="l00084" name="l00084"></a><span class="lineno"> 84</span> <span class="comment">/* stats [4..6]: error info, or info on jumbled columns */</span></div>
<div class="line"><a id="l00085" name="l00085"></a><span class="lineno"> 85</span> Info1 = 4,</div>
<div class="line"><a id="l00086" name="l00086"></a><span class="lineno"> 86</span> Info2 = 5,</div>
<div class="line"><a id="l00087" name="l00087"></a><span class="lineno"> 87</span> Info3 = 6</div>
<div class="line"><a id="l00088" name="l00088"></a><span class="lineno"> 88</span>};</div>
<div class="line"><a id="l00089" name="l00089"></a><span class="lineno"> 89</span> </div>
<div class="line"><a id="l00090" name="l00090"></a><span class="lineno"> 90</span><span class="comment">/* error codes returned in stats [3]: */</span></div>
<div class="line"><a id="l00091" name="l00091"></a><span class="lineno"> 91</span><span class="keyword">enum</span> Status {</div>
<div class="line"><a id="l00092" name="l00092"></a><span class="lineno"> 92</span> Ok = 0,</div>
<div class="line"><a id="l00093" name="l00093"></a><span class="lineno"> 93</span> OkButJumbled = 1,</div>
<div class="line"><a id="l00094" name="l00094"></a><span class="lineno"> 94</span> ErrorANotPresent = -1,</div>
<div class="line"><a id="l00095" name="l00095"></a><span class="lineno"> 95</span> ErrorPNotPresent = -2,</div>
<div class="line"><a id="l00096" name="l00096"></a><span class="lineno"> 96</span> ErrorNrowNegative = -3,</div>
<div class="line"><a id="l00097" name="l00097"></a><span class="lineno"> 97</span> ErrorNcolNegative = -4,</div>
<div class="line"><a id="l00098" name="l00098"></a><span class="lineno"> 98</span> ErrorNnzNegative = -5,</div>
<div class="line"><a id="l00099" name="l00099"></a><span class="lineno"> 99</span> ErrorP0Nonzero = -6,</div>
<div class="line"><a id="l00100" name="l00100"></a><span class="lineno"> 100</span> ErrorATooSmall = -7,</div>
<div class="line"><a id="l00101" name="l00101"></a><span class="lineno"> 101</span> ErrorColLengthNegative = -8,</div>
<div class="line"><a id="l00102" name="l00102"></a><span class="lineno"> 102</span> ErrorRowIndexOutOfBounds = -9,</div>
<div class="line"><a id="l00103" name="l00103"></a><span class="lineno"> 103</span> ErrorOutOfMemory = -10,</div>
<div class="line"><a id="l00104" name="l00104"></a><span class="lineno"> 104</span> ErrorInternalError = -999</div>
<div class="line"><a id="l00105" name="l00105"></a><span class="lineno"> 105</span>};</div>
<div class="line"><a id="l00106" name="l00106"></a><span class="lineno"> 106</span><span class="comment">/* ========================================================================== */</span></div>
<div class="line"><a id="l00107" name="l00107"></a><span class="lineno"> 107</span><span class="comment">/* === Definitions ========================================================== */</span></div>
<div class="line"><a id="l00108" name="l00108"></a><span class="lineno"> 108</span><span class="comment">/* ========================================================================== */</span></div>
<div class="line"><a id="l00109" name="l00109"></a><span class="lineno"> 109</span> </div>
<div class="line"><a id="l00110" name="l00110"></a><span class="lineno"> 110</span><span class="keyword">template</span> <<span class="keyword">typename</span> IndexType></div>
<div class="line"><a id="l00111" name="l00111"></a><span class="lineno"> 111</span>IndexType ones_complement(<span class="keyword">const</span> IndexType r) {</div>
<div class="line"><a id="l00112" name="l00112"></a><span class="lineno"> 112</span> <span class="keywordflow">return</span> (-(r)-1);</div>
<div class="line"><a id="l00113" name="l00113"></a><span class="lineno"> 113</span>}</div>
<div class="line"><a id="l00114" name="l00114"></a><span class="lineno"> 114</span> </div>
<div class="line"><a id="l00115" name="l00115"></a><span class="lineno"> 115</span><span class="comment">/* -------------------------------------------------------------------------- */</span></div>
<div class="line"><a id="l00116" name="l00116"></a><span class="lineno"> 116</span><span class="keyword">const</span> <span class="keywordtype">int</span> Empty = -1;</div>
<div class="line"><a id="l00117" name="l00117"></a><span class="lineno"> 117</span> </div>
<div class="line"><a id="l00118" name="l00118"></a><span class="lineno"> 118</span><span class="comment">/* Row and column status */</span></div>
<div class="line"><a id="l00119" name="l00119"></a><span class="lineno"> 119</span><span class="keyword">enum</span> RowColumnStatus {</div>
<div class="line"><a id="l00120" name="l00120"></a><span class="lineno"> 120</span> Alive = 0,</div>
<div class="line"><a id="l00121" name="l00121"></a><span class="lineno"> 121</span> Dead = -1</div>
<div class="line"><a id="l00122" name="l00122"></a><span class="lineno"> 122</span>};</div>
<div class="line"><a id="l00123" name="l00123"></a><span class="lineno"> 123</span> </div>
<div class="line"><a id="l00124" name="l00124"></a><span class="lineno"> 124</span><span class="comment">/* Column status */</span></div>
<div class="line"><a id="l00125" name="l00125"></a><span class="lineno"> 125</span><span class="keyword">enum</span> ColumnStatus {</div>
<div class="line"><a id="l00126" name="l00126"></a><span class="lineno"> 126</span> DeadPrincipal = -1,</div>
<div class="line"><a id="l00127" name="l00127"></a><span class="lineno"> 127</span> DeadNonPrincipal = -2</div>
<div class="line"><a id="l00128" name="l00128"></a><span class="lineno"> 128</span>};</div>
<div class="line"><a id="l00129" name="l00129"></a><span class="lineno"> 129</span> </div>
<div class="line"><a id="l00130" name="l00130"></a><span class="lineno"> 130</span><span class="comment">/* ========================================================================== */</span></div>
<div class="line"><a id="l00131" name="l00131"></a><span class="lineno"> 131</span><span class="comment">/* === Colamd reporting mechanism =========================================== */</span></div>
<div class="line"><a id="l00132" name="l00132"></a><span class="lineno"> 132</span><span class="comment">/* ========================================================================== */</span></div>
<div class="line"><a id="l00133" name="l00133"></a><span class="lineno"> 133</span> </div>
<div class="line"><a id="l00134" name="l00134"></a><span class="lineno"> 134</span><span class="comment">// == Row and Column structures ==</span></div>
<div class="line"><a id="l00135" name="l00135"></a><span class="lineno"> 135</span><span class="keyword">template</span> <<span class="keyword">typename</span> IndexType></div>
<div class="line"><a id="l00136" name="l00136"></a><span class="lineno"> 136</span><span class="keyword">struct </span>ColStructure</div>
<div class="line"><a id="l00137" name="l00137"></a><span class="lineno"> 137</span>{</div>
<div class="line"><a id="l00138" name="l00138"></a><span class="lineno"> 138</span> IndexType start ; <span class="comment">/* index for A of first row in this column, or Dead */</span></div>
<div class="line"><a id="l00139" name="l00139"></a><span class="lineno"> 139</span> <span class="comment">/* if column is dead */</span></div>
<div class="line"><a id="l00140" name="l00140"></a><span class="lineno"> 140</span> IndexType length ; <span class="comment">/* number of rows in this column */</span></div>
<div class="line"><a id="l00141" name="l00141"></a><span class="lineno"> 141</span> <span class="keyword">union</span></div>
<div class="line"><a id="l00142" name="l00142"></a><span class="lineno"> 142</span> {</div>
<div class="line"><a id="l00143" name="l00143"></a><span class="lineno"> 143</span> IndexType thickness ; <span class="comment">/* number of original columns represented by this */</span></div>
<div class="line"><a id="l00144" name="l00144"></a><span class="lineno"> 144</span> <span class="comment">/* col, if the column is alive */</span></div>
<div class="line"><a id="l00145" name="l00145"></a><span class="lineno"> 145</span> IndexType parent ; <span class="comment">/* parent in parent tree super-column structure, if */</span></div>
<div class="line"><a id="l00146" name="l00146"></a><span class="lineno"> 146</span> <span class="comment">/* the column is dead */</span></div>
<div class="line"><a id="l00147" name="l00147"></a><span class="lineno"> 147</span> } shared1 ;</div>
<div class="line"><a id="l00148" name="l00148"></a><span class="lineno"> 148</span> <span class="keyword">union</span></div>
<div class="line"><a id="l00149" name="l00149"></a><span class="lineno"> 149</span> {</div>
<div class="line"><a id="l00150" name="l00150"></a><span class="lineno"> 150</span> IndexType score ; <span class="comment">/* the score used to maintain heap, if col is alive */</span></div>
<div class="line"><a id="l00151" name="l00151"></a><span class="lineno"> 151</span> IndexType order ; <span class="comment">/* pivot ordering of this column, if col is dead */</span></div>
<div class="line"><a id="l00152" name="l00152"></a><span class="lineno"> 152</span> } shared2 ;</div>
<div class="line"><a id="l00153" name="l00153"></a><span class="lineno"> 153</span> <span class="keyword">union</span></div>
<div class="line"><a id="l00154" name="l00154"></a><span class="lineno"> 154</span> {</div>
<div class="line"><a id="l00155" name="l00155"></a><span class="lineno"> 155</span> IndexType headhash ; <span class="comment">/* head of a hash bucket, if col is at the head of */</span></div>
<div class="line"><a id="l00156" name="l00156"></a><span class="lineno"> 156</span> <span class="comment">/* a degree list */</span></div>
<div class="line"><a id="l00157" name="l00157"></a><span class="lineno"> 157</span> IndexType hash ; <span class="comment">/* hash value, if col is not in a degree list */</span></div>
<div class="line"><a id="l00158" name="l00158"></a><span class="lineno"> 158</span> IndexType prev ; <span class="comment">/* previous column in degree list, if col is in a */</span></div>
<div class="line"><a id="l00159" name="l00159"></a><span class="lineno"> 159</span> <span class="comment">/* degree list (but not at the head of a degree list) */</span></div>
<div class="line"><a id="l00160" name="l00160"></a><span class="lineno"> 160</span> } shared3 ;</div>
<div class="line"><a id="l00161" name="l00161"></a><span class="lineno"> 161</span> <span class="keyword">union</span></div>
<div class="line"><a id="l00162" name="l00162"></a><span class="lineno"> 162</span> {</div>
<div class="line"><a id="l00163" name="l00163"></a><span class="lineno"> 163</span> IndexType degree_next ; <span class="comment">/* next column, if col is in a degree list */</span></div>
<div class="line"><a id="l00164" name="l00164"></a><span class="lineno"> 164</span> IndexType hash_next ; <span class="comment">/* next column, if col is in a hash list */</span></div>
<div class="line"><a id="l00165" name="l00165"></a><span class="lineno"> 165</span> } shared4 ;</div>
<div class="line"><a id="l00166" name="l00166"></a><span class="lineno"> 166</span> </div>
<div class="line"><a id="l00167" name="l00167"></a><span class="lineno"> 167</span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> is_dead()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> start < Alive; }</div>
<div class="line"><a id="l00168" name="l00168"></a><span class="lineno"> 168</span> </div>
<div class="line"><a id="l00169" name="l00169"></a><span class="lineno"> 169</span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> is_alive()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> start >= Alive; }</div>
<div class="line"><a id="l00170" name="l00170"></a><span class="lineno"> 170</span> </div>
<div class="line"><a id="l00171" name="l00171"></a><span class="lineno"> 171</span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> is_dead_principal()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> start == DeadPrincipal; }</div>
<div class="line"><a id="l00172" name="l00172"></a><span class="lineno"> 172</span> </div>
<div class="line"><a id="l00173" name="l00173"></a><span class="lineno"> 173</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> kill_principal() { start = DeadPrincipal; }</div>
<div class="line"><a id="l00174" name="l00174"></a><span class="lineno"> 174</span> </div>
<div class="line"><a id="l00175" name="l00175"></a><span class="lineno"> 175</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> kill_non_principal() { start = DeadNonPrincipal; }</div>
<div class="line"><a id="l00176" name="l00176"></a><span class="lineno"> 176</span> </div>
<div class="line"><a id="l00177" name="l00177"></a><span class="lineno"> 177</span>};</div>
<div class="line"><a id="l00178" name="l00178"></a><span class="lineno"> 178</span> </div>
<div class="line"><a id="l00179" name="l00179"></a><span class="lineno"> 179</span><span class="keyword">template</span> <<span class="keyword">typename</span> IndexType></div>
<div class="line"><a id="l00180" name="l00180"></a><span class="lineno"> 180</span><span class="keyword">struct </span>RowStructure</div>
<div class="line"><a id="l00181" name="l00181"></a><span class="lineno"> 181</span>{</div>
<div class="line"><a id="l00182" name="l00182"></a><span class="lineno"> 182</span> IndexType start ; <span class="comment">/* index for A of first col in this row */</span></div>
<div class="line"><a id="l00183" name="l00183"></a><span class="lineno"> 183</span> IndexType length ; <span class="comment">/* number of principal columns in this row */</span></div>
<div class="line"><a id="l00184" name="l00184"></a><span class="lineno"> 184</span> <span class="keyword">union</span></div>
<div class="line"><a id="l00185" name="l00185"></a><span class="lineno"> 185</span> {</div>
<div class="line"><a id="l00186" name="l00186"></a><span class="lineno"> 186</span> IndexType degree ; <span class="comment">/* number of principal & non-principal columns in row */</span></div>
<div class="line"><a id="l00187" name="l00187"></a><span class="lineno"> 187</span> IndexType p ; <span class="comment">/* used as a row pointer in init_rows_cols () */</span></div>
<div class="line"><a id="l00188" name="l00188"></a><span class="lineno"> 188</span> } shared1 ;</div>
<div class="line"><a id="l00189" name="l00189"></a><span class="lineno"> 189</span> <span class="keyword">union</span></div>
<div class="line"><a id="l00190" name="l00190"></a><span class="lineno"> 190</span> {</div>
<div class="line"><a id="l00191" name="l00191"></a><span class="lineno"> 191</span> IndexType mark ; <span class="comment">/* for computing set differences and marking dead rows*/</span></div>
<div class="line"><a id="l00192" name="l00192"></a><span class="lineno"> 192</span> IndexType first_column ;<span class="comment">/* first column in row (used in garbage collection) */</span></div>
<div class="line"><a id="l00193" name="l00193"></a><span class="lineno"> 193</span> } shared2 ;</div>
<div class="line"><a id="l00194" name="l00194"></a><span class="lineno"> 194</span> </div>
<div class="line"><a id="l00195" name="l00195"></a><span class="lineno"> 195</span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> is_dead()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> shared2.mark < Alive; }</div>
<div class="line"><a id="l00196" name="l00196"></a><span class="lineno"> 196</span> </div>
<div class="line"><a id="l00197" name="l00197"></a><span class="lineno"> 197</span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> is_alive()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> shared2.mark >= Alive; }</div>
<div class="line"><a id="l00198" name="l00198"></a><span class="lineno"> 198</span> </div>
<div class="line"><a id="l00199" name="l00199"></a><span class="lineno"> 199</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> kill() { shared2.mark = Dead; }</div>
<div class="line"><a id="l00200" name="l00200"></a><span class="lineno"> 200</span> </div>
<div class="line"><a id="l00201" name="l00201"></a><span class="lineno"> 201</span>};</div>
<div class="line"><a id="l00202" name="l00202"></a><span class="lineno"> 202</span> </div>
<div class="line"><a id="l00203" name="l00203"></a><span class="lineno"> 203</span><span class="comment">/* ========================================================================== */</span></div>
<div class="line"><a id="l00204" name="l00204"></a><span class="lineno"> 204</span><span class="comment">/* === Colamd recommended memory size ======================================= */</span></div>
<div class="line"><a id="l00205" name="l00205"></a><span class="lineno"> 205</span><span class="comment">/* ========================================================================== */</span></div>
<div class="line"><a id="l00206" name="l00206"></a><span class="lineno"> 206</span> </div>
<div class="line"><a id="l00207" name="l00207"></a><span class="lineno"> 207</span><span class="comment">/*</span></div>
<div class="line"><a id="l00208" name="l00208"></a><span class="lineno"> 208</span><span class="comment"> The recommended length Alen of the array A passed to colamd is given by</span></div>
<div class="line"><a id="l00209" name="l00209"></a><span class="lineno"> 209</span><span class="comment"> the COLAMD_RECOMMENDED (nnz, n_row, n_col) macro. It returns -1 if any</span></div>
<div class="line"><a id="l00210" name="l00210"></a><span class="lineno"> 210</span><span class="comment"> argument is negative. 2*nnz space is required for the row and column</span></div>
<div class="line"><a id="l00211" name="l00211"></a><span class="lineno"> 211</span><span class="comment"> indices of the matrix. colamd_c (n_col) + colamd_r (n_row) space is</span></div>
<div class="line"><a id="l00212" name="l00212"></a><span class="lineno"> 212</span><span class="comment"> required for the Col and Row arrays, respectively, which are internal to</span></div>
<div class="line"><a id="l00213" name="l00213"></a><span class="lineno"> 213</span><span class="comment"> colamd. An additional n_col space is the minimal amount of "elbow room",</span></div>
<div class="line"><a id="l00214" name="l00214"></a><span class="lineno"> 214</span><span class="comment"> and nnz/5 more space is recommended for run time efficiency.</span></div>
<div class="line"><a id="l00215" name="l00215"></a><span class="lineno"> 215</span><span class="comment"></span> </div>
<div class="line"><a id="l00216" name="l00216"></a><span class="lineno"> 216</span><span class="comment"> This macro is not needed when using symamd.</span></div>
<div class="line"><a id="l00217" name="l00217"></a><span class="lineno"> 217</span><span class="comment"></span> </div>
<div class="line"><a id="l00218" name="l00218"></a><span class="lineno"> 218</span><span class="comment"> Explicit typecast to IndexType added Sept. 23, 2002, COLAMD version 2.2, to avoid</span></div>
<div class="line"><a id="l00219" name="l00219"></a><span class="lineno"> 219</span><span class="comment"> gcc -pedantic warning messages.</span></div>
<div class="line"><a id="l00220" name="l00220"></a><span class="lineno"> 220</span><span class="comment">*/</span></div>
<div class="line"><a id="l00221" name="l00221"></a><span class="lineno"> 221</span><span class="keyword">template</span> <<span class="keyword">typename</span> IndexType></div>
<div class="line"><a id="l00222" name="l00222"></a><span class="lineno"> 222</span><span class="keyword">inline</span> IndexType colamd_c(IndexType n_col)</div>
<div class="line"><a id="l00223" name="l00223"></a><span class="lineno"> 223</span>{ <span class="keywordflow">return</span> IndexType( ((n_col) + 1) * <span class="keyword">sizeof</span> (ColStructure<IndexType>) / <span class="keyword">sizeof</span> (IndexType) ) ; }</div>
<div class="line"><a id="l00224" name="l00224"></a><span class="lineno"> 224</span> </div>
<div class="line"><a id="l00225" name="l00225"></a><span class="lineno"> 225</span><span class="keyword">template</span> <<span class="keyword">typename</span> IndexType></div>
<div class="line"><a id="l00226" name="l00226"></a><span class="lineno"> 226</span><span class="keyword">inline</span> IndexType colamd_r(IndexType n_row)</div>
<div class="line"><a id="l00227" name="l00227"></a><span class="lineno"> 227</span>{ <span class="keywordflow">return</span> IndexType(((n_row) + 1) * <span class="keyword">sizeof</span> (RowStructure<IndexType>) / <span class="keyword">sizeof</span> (IndexType)); }</div>
<div class="line"><a id="l00228" name="l00228"></a><span class="lineno"> 228</span> </div>
<div class="line"><a id="l00229" name="l00229"></a><span class="lineno"> 229</span><span class="comment">// Prototypes of non-user callable routines</span></div>
<div class="line"><a id="l00230" name="l00230"></a><span class="lineno"> 230</span><span class="keyword">template</span> <<span class="keyword">typename</span> IndexType></div>
<div class="line"><a id="l00231" name="l00231"></a><span class="lineno"> 231</span><span class="keyword">static</span> IndexType init_rows_cols (IndexType n_row, IndexType n_col, RowStructure<IndexType> Row [], ColStructure<IndexType> col [], IndexType A [], IndexType p [], IndexType stats[NStats] );</div>
<div class="line"><a id="l00232" name="l00232"></a><span class="lineno"> 232</span> </div>
<div class="line"><a id="l00233" name="l00233"></a><span class="lineno"> 233</span><span class="keyword">template</span> <<span class="keyword">typename</span> IndexType></div>
<div class="line"><a id="l00234" name="l00234"></a><span class="lineno"> 234</span><span class="keyword">static</span> <span class="keywordtype">void</span> init_scoring (IndexType n_row, IndexType n_col, RowStructure<IndexType> Row [], ColStructure<IndexType> Col [], IndexType A [], IndexType head [], <span class="keywordtype">double</span> knobs[NKnobs], IndexType *p_n_row2, IndexType *p_n_col2, IndexType *p_max_deg);</div>
<div class="line"><a id="l00235" name="l00235"></a><span class="lineno"> 235</span> </div>
<div class="line"><a id="l00236" name="l00236"></a><span class="lineno"> 236</span><span class="keyword">template</span> <<span class="keyword">typename</span> IndexType></div>
<div class="line"><a id="l00237" name="l00237"></a><span class="lineno"> 237</span><span class="keyword">static</span> 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);</div>
<div class="line"><a id="l00238" name="l00238"></a><span class="lineno"> 238</span> </div>
<div class="line"><a id="l00239" name="l00239"></a><span class="lineno"> 239</span><span class="keyword">template</span> <<span class="keyword">typename</span> IndexType></div>
<div class="line"><a id="l00240" name="l00240"></a><span class="lineno"> 240</span><span class="keyword">static</span> <span class="keywordtype">void</span> order_children (IndexType n_col, ColStructure<IndexType> Col [], IndexType p []);</div>
<div class="line"><a id="l00241" name="l00241"></a><span class="lineno"> 241</span> </div>
<div class="line"><a id="l00242" name="l00242"></a><span class="lineno"> 242</span><span class="keyword">template</span> <<span class="keyword">typename</span> IndexType></div>
<div class="line"><a id="l00243" name="l00243"></a><span class="lineno"> 243</span><span class="keyword">static</span> <span class="keywordtype">void</span> detect_super_cols (ColStructure<IndexType> Col [], IndexType A [], IndexType head [], IndexType row_start, IndexType row_length ) ;</div>
<div class="line"><a id="l00244" name="l00244"></a><span class="lineno"> 244</span> </div>
<div class="line"><a id="l00245" name="l00245"></a><span class="lineno"> 245</span><span class="keyword">template</span> <<span class="keyword">typename</span> IndexType></div>
<div class="line"><a id="l00246" name="l00246"></a><span class="lineno"> 246</span><span class="keyword">static</span> IndexType garbage_collection (IndexType n_row, IndexType n_col, RowStructure<IndexType> Row [], ColStructure<IndexType> Col [], IndexType A [], IndexType *pfree) ;</div>
<div class="line"><a id="l00247" name="l00247"></a><span class="lineno"> 247</span> </div>
<div class="line"><a id="l00248" name="l00248"></a><span class="lineno"> 248</span><span class="keyword">template</span> <<span class="keyword">typename</span> IndexType></div>
<div class="line"><a id="l00249" name="l00249"></a><span class="lineno"> 249</span><span class="keyword">static</span> <span class="keyword">inline</span> IndexType clear_mark (IndexType n_row, RowStructure<IndexType> Row [] ) ;</div>
<div class="line"><a id="l00250" name="l00250"></a><span class="lineno"> 250</span> </div>
<div class="line"><a id="l00251" name="l00251"></a><span class="lineno"> 251</span><span class="comment">/* === No debugging ========================================================= */</span></div>
<div class="line"><a id="l00252" name="l00252"></a><span class="lineno"> 252</span> </div>
<div class="line"><a id="l00253" name="l00253"></a><span class="lineno"> 253</span><span class="preprocessor">#define COLAMD_DEBUG0(params) ;</span></div>
<div class="line"><a id="l00254" name="l00254"></a><span class="lineno"> 254</span><span class="preprocessor">#define COLAMD_DEBUG1(params) ;</span></div>
<div class="line"><a id="l00255" name="l00255"></a><span class="lineno"> 255</span><span class="preprocessor">#define COLAMD_DEBUG2(params) ;</span></div>
<div class="line"><a id="l00256" name="l00256"></a><span class="lineno"> 256</span><span class="preprocessor">#define COLAMD_DEBUG3(params) ;</span></div>
<div class="line"><a id="l00257" name="l00257"></a><span class="lineno"> 257</span><span class="preprocessor">#define COLAMD_DEBUG4(params) ;</span></div>
<div class="line"><a id="l00258" name="l00258"></a><span class="lineno"> 258</span> </div>
<div class="line"><a id="l00259" name="l00259"></a><span class="lineno"> 259</span><span class="preprocessor">#define COLAMD_ASSERT(expression) ((void) 0)</span></div>
<div class="line"><a id="l00260" name="l00260"></a><span class="lineno"> 260</span> </div>
<div class="line"><a id="l00261" name="l00261"></a><span class="lineno"> 261</span> </div>
<div class="line"><a id="l00276" name="l00276"></a><span class="lineno"> 276</span><span class="keyword">template</span> <<span class="keyword">typename</span> IndexType></div>
<div class="line"><a id="l00277" name="l00277"></a><span class="lineno"> 277</span><span class="keyword">inline</span> IndexType recommended ( IndexType nnz, IndexType n_row, IndexType n_col)</div>
<div class="line"><a id="l00278" name="l00278"></a><span class="lineno"> 278</span>{</div>
<div class="line"><a id="l00279" name="l00279"></a><span class="lineno"> 279</span> <span class="keywordflow">if</span> ((nnz) < 0 || (n_row) < 0 || (n_col) < 0)</div>
<div class="line"><a id="l00280" name="l00280"></a><span class="lineno"> 280</span> <span class="keywordflow">return</span> (-1);</div>
<div class="line"><a id="l00281" name="l00281"></a><span class="lineno"> 281</span> <span class="keywordflow">else</span></div>
<div class="line"><a id="l00282" name="l00282"></a><span class="lineno"> 282</span> <span class="keywordflow">return</span> (2 * (nnz) + colamd_c (n_col) + colamd_r (n_row) + (n_col) + ((nnz) / 5));</div>
<div class="line"><a id="l00283" name="l00283"></a><span class="lineno"> 283</span>}</div>
<div class="line"><a id="l00284" name="l00284"></a><span class="lineno"> 284</span> </div>
<div class="line"><a id="l00306" name="l00306"></a><span class="lineno"> 306</span><span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> set_defaults(<span class="keywordtype">double</span> knobs[NKnobs])</div>
<div class="line"><a id="l00307" name="l00307"></a><span class="lineno"> 307</span>{</div>
<div class="line"><a id="l00308" name="l00308"></a><span class="lineno"> 308</span> <span class="comment">/* === Local variables ================================================== */</span></div>
<div class="line"><a id="l00309" name="l00309"></a><span class="lineno"> 309</span> </div>
<div class="line"><a id="l00310" name="l00310"></a><span class="lineno"> 310</span> <span class="keywordtype">int</span> i ;</div>
<div class="line"><a id="l00311" name="l00311"></a><span class="lineno"> 311</span> </div>
<div class="line"><a id="l00312" name="l00312"></a><span class="lineno"> 312</span> <span class="keywordflow">if</span> (!knobs)</div>
<div class="line"><a id="l00313" name="l00313"></a><span class="lineno"> 313</span> {</div>
<div class="line"><a id="l00314" name="l00314"></a><span class="lineno"> 314</span> return ; <span class="comment">/* no knobs to initialize */</span></div>
<div class="line"><a id="l00315" name="l00315"></a><span class="lineno"> 315</span> }</div>
<div class="line"><a id="l00316" name="l00316"></a><span class="lineno"> 316</span> <span class="keywordflow">for</span> (i = 0 ; i < NKnobs ; i++)</div>
<div class="line"><a id="l00317" name="l00317"></a><span class="lineno"> 317</span> {</div>
<div class="line"><a id="l00318" name="l00318"></a><span class="lineno"> 318</span> knobs [i] = 0 ;</div>
<div class="line"><a id="l00319" name="l00319"></a><span class="lineno"> 319</span> }</div>
<div class="line"><a id="l00320" name="l00320"></a><span class="lineno"> 320</span> knobs [Colamd::DenseRow] = 0.5 ; <span class="comment">/* ignore rows over 50% dense */</span></div>
<div class="line"><a id="l00321" name="l00321"></a><span class="lineno"> 321</span> knobs [Colamd::DenseCol] = 0.5 ; <span class="comment">/* ignore columns over 50% dense */</span></div>
<div class="line"><a id="l00322" name="l00322"></a><span class="lineno"> 322</span>}</div>
<div class="line"><a id="l00323" name="l00323"></a><span class="lineno"> 323</span> </div>
<div class="line"><a id="l00341" name="l00341"></a><span class="lineno"> 341</span><span class="keyword">template</span> <<span class="keyword">typename</span> IndexType></div>
<div class="line"><a id="l00342" name="l00342"></a><span class="lineno"> 342</span><span class="keyword">static</span> <span class="keywordtype">bool</span> compute_ordering(IndexType n_row, IndexType n_col, IndexType Alen, IndexType *A, IndexType *p, <span class="keywordtype">double</span> knobs[NKnobs], IndexType stats[NStats])</div>
<div class="line"><a id="l00343" name="l00343"></a><span class="lineno"> 343</span>{</div>
<div class="line"><a id="l00344" name="l00344"></a><span class="lineno"> 344</span> <span class="comment">/* === Local variables ================================================== */</span></div>
<div class="line"><a id="l00345" name="l00345"></a><span class="lineno"> 345</span> </div>
<div class="line"><a id="l00346" name="l00346"></a><span class="lineno"> 346</span> IndexType i ; <span class="comment">/* loop index */</span></div>
<div class="line"><a id="l00347" name="l00347"></a><span class="lineno"> 347</span> IndexType nnz ; <span class="comment">/* nonzeros in A */</span></div>
<div class="line"><a id="l00348" name="l00348"></a><span class="lineno"> 348</span> IndexType Row_size ; <span class="comment">/* size of Row [], in integers */</span></div>
<div class="line"><a id="l00349" name="l00349"></a><span class="lineno"> 349</span> IndexType Col_size ; <span class="comment">/* size of Col [], in integers */</span></div>
<div class="line"><a id="l00350" name="l00350"></a><span class="lineno"> 350</span> IndexType need ; <span class="comment">/* minimum required length of A */</span></div>
<div class="line"><a id="l00351" name="l00351"></a><span class="lineno"> 351</span> Colamd::RowStructure<IndexType> *Row ; <span class="comment">/* pointer into A of Row [0..n_row] array */</span></div>
<div class="line"><a id="l00352" name="l00352"></a><span class="lineno"> 352</span> Colamd::ColStructure<IndexType> *Col ; <span class="comment">/* pointer into A of Col [0..n_col] array */</span></div>
<div class="line"><a id="l00353" name="l00353"></a><span class="lineno"> 353</span> IndexType n_col2 ; <span class="comment">/* number of non-dense, non-empty columns */</span></div>
<div class="line"><a id="l00354" name="l00354"></a><span class="lineno"> 354</span> IndexType n_row2 ; <span class="comment">/* number of non-dense, non-empty rows */</span></div>
<div class="line"><a id="l00355" name="l00355"></a><span class="lineno"> 355</span> IndexType ngarbage ; <span class="comment">/* number of garbage collections performed */</span></div>
<div class="line"><a id="l00356" name="l00356"></a><span class="lineno"> 356</span> IndexType max_deg ; <span class="comment">/* maximum row degree */</span></div>
<div class="line"><a id="l00357" name="l00357"></a><span class="lineno"> 357</span> <span class="keywordtype">double</span> default_knobs [NKnobs] ; <span class="comment">/* default knobs array */</span></div>
<div class="line"><a id="l00358" name="l00358"></a><span class="lineno"> 358</span> </div>
<div class="line"><a id="l00359" name="l00359"></a><span class="lineno"> 359</span> </div>
<div class="line"><a id="l00360" name="l00360"></a><span class="lineno"> 360</span> <span class="comment">/* === Check the input arguments ======================================== */</span></div>
<div class="line"><a id="l00361" name="l00361"></a><span class="lineno"> 361</span> </div>
<div class="line"><a id="l00362" name="l00362"></a><span class="lineno"> 362</span> <span class="keywordflow">if</span> (!stats)</div>
<div class="line"><a id="l00363" name="l00363"></a><span class="lineno"> 363</span> {</div>
<div class="line"><a id="l00364" name="l00364"></a><span class="lineno"> 364</span> COLAMD_DEBUG0 ((<span class="stringliteral">"colamd: stats not present\n"</span>)) ;</div>
<div class="line"><a id="l00365" name="l00365"></a><span class="lineno"> 365</span> <span class="keywordflow">return</span> (<span class="keyword">false</span>) ;</div>
<div class="line"><a id="l00366" name="l00366"></a><span class="lineno"> 366</span> }</div>
<div class="line"><a id="l00367" name="l00367"></a><span class="lineno"> 367</span> <span class="keywordflow">for</span> (i = 0 ; i < NStats ; i++)</div>
<div class="line"><a id="l00368" name="l00368"></a><span class="lineno"> 368</span> {</div>
<div class="line"><a id="l00369" name="l00369"></a><span class="lineno"> 369</span> stats [i] = 0 ;</div>
<div class="line"><a id="l00370" name="l00370"></a><span class="lineno"> 370</span> }</div>
<div class="line"><a id="l00371" name="l00371"></a><span class="lineno"> 371</span> stats [Colamd::Status] = Colamd::Ok ;</div>
<div class="line"><a id="l00372" name="l00372"></a><span class="lineno"> 372</span> stats [Colamd::Info1] = -1 ;</div>
<div class="line"><a id="l00373" name="l00373"></a><span class="lineno"> 373</span> stats [Colamd::Info2] = -1 ;</div>
<div class="line"><a id="l00374" name="l00374"></a><span class="lineno"> 374</span> </div>
<div class="line"><a id="l00375" name="l00375"></a><span class="lineno"> 375</span> <span class="keywordflow">if</span> (!A) <span class="comment">/* A is not present */</span></div>
<div class="line"><a id="l00376" name="l00376"></a><span class="lineno"> 376</span> {</div>
<div class="line"><a id="l00377" name="l00377"></a><span class="lineno"> 377</span> stats [Colamd::Status] = Colamd::ErrorANotPresent ;</div>
<div class="line"><a id="l00378" name="l00378"></a><span class="lineno"> 378</span> COLAMD_DEBUG0 ((<span class="stringliteral">"colamd: A not present\n"</span>)) ;</div>
<div class="line"><a id="l00379" name="l00379"></a><span class="lineno"> 379</span> <span class="keywordflow">return</span> (<span class="keyword">false</span>) ;</div>
<div class="line"><a id="l00380" name="l00380"></a><span class="lineno"> 380</span> }</div>
<div class="line"><a id="l00381" name="l00381"></a><span class="lineno"> 381</span> </div>
<div class="line"><a id="l00382" name="l00382"></a><span class="lineno"> 382</span> <span class="keywordflow">if</span> (!p) <span class="comment">/* p is not present */</span></div>
<div class="line"><a id="l00383" name="l00383"></a><span class="lineno"> 383</span> {</div>
<div class="line"><a id="l00384" name="l00384"></a><span class="lineno"> 384</span> stats [Colamd::Status] = Colamd::ErrorPNotPresent ;</div>
<div class="line"><a id="l00385" name="l00385"></a><span class="lineno"> 385</span> COLAMD_DEBUG0 ((<span class="stringliteral">"colamd: p not present\n"</span>)) ;</div>
<div class="line"><a id="l00386" name="l00386"></a><span class="lineno"> 386</span> <span class="keywordflow">return</span> (<span class="keyword">false</span>) ;</div>
<div class="line"><a id="l00387" name="l00387"></a><span class="lineno"> 387</span> }</div>
<div class="line"><a id="l00388" name="l00388"></a><span class="lineno"> 388</span> </div>
<div class="line"><a id="l00389" name="l00389"></a><span class="lineno"> 389</span> <span class="keywordflow">if</span> (n_row < 0) <span class="comment">/* n_row must be >= 0 */</span></div>
<div class="line"><a id="l00390" name="l00390"></a><span class="lineno"> 390</span> {</div>
<div class="line"><a id="l00391" name="l00391"></a><span class="lineno"> 391</span> stats [Colamd::Status] = Colamd::ErrorNrowNegative ;</div>
<div class="line"><a id="l00392" name="l00392"></a><span class="lineno"> 392</span> stats [Colamd::Info1] = n_row ;</div>
<div class="line"><a id="l00393" name="l00393"></a><span class="lineno"> 393</span> COLAMD_DEBUG0 ((<span class="stringliteral">"colamd: nrow negative %d\n"</span>, n_row)) ;</div>
<div class="line"><a id="l00394" name="l00394"></a><span class="lineno"> 394</span> <span class="keywordflow">return</span> (<span class="keyword">false</span>) ;</div>
<div class="line"><a id="l00395" name="l00395"></a><span class="lineno"> 395</span> }</div>
<div class="line"><a id="l00396" name="l00396"></a><span class="lineno"> 396</span> </div>
<div class="line"><a id="l00397" name="l00397"></a><span class="lineno"> 397</span> <span class="keywordflow">if</span> (n_col < 0) <span class="comment">/* n_col must be >= 0 */</span></div>
<div class="line"><a id="l00398" name="l00398"></a><span class="lineno"> 398</span> {</div>
<div class="line"><a id="l00399" name="l00399"></a><span class="lineno"> 399</span> stats [Colamd::Status] = Colamd::ErrorNcolNegative ;</div>
<div class="line"><a id="l00400" name="l00400"></a><span class="lineno"> 400</span> stats [Colamd::Info1] = n_col ;</div>
<div class="line"><a id="l00401" name="l00401"></a><span class="lineno"> 401</span> COLAMD_DEBUG0 ((<span class="stringliteral">"colamd: ncol negative %d\n"</span>, n_col)) ;</div>
<div class="line"><a id="l00402" name="l00402"></a><span class="lineno"> 402</span> <span class="keywordflow">return</span> (<span class="keyword">false</span>) ;</div>
<div class="line"><a id="l00403" name="l00403"></a><span class="lineno"> 403</span> }</div>
<div class="line"><a id="l00404" name="l00404"></a><span class="lineno"> 404</span> </div>
<div class="line"><a id="l00405" name="l00405"></a><span class="lineno"> 405</span> nnz = p [n_col] ;</div>
<div class="line"><a id="l00406" name="l00406"></a><span class="lineno"> 406</span> <span class="keywordflow">if</span> (nnz < 0) <span class="comment">/* nnz must be >= 0 */</span></div>
<div class="line"><a id="l00407" name="l00407"></a><span class="lineno"> 407</span> {</div>
<div class="line"><a id="l00408" name="l00408"></a><span class="lineno"> 408</span> stats [Colamd::Status] = Colamd::ErrorNnzNegative ;</div>
<div class="line"><a id="l00409" name="l00409"></a><span class="lineno"> 409</span> stats [Colamd::Info1] = nnz ;</div>
<div class="line"><a id="l00410" name="l00410"></a><span class="lineno"> 410</span> COLAMD_DEBUG0 ((<span class="stringliteral">"colamd: number of entries negative %d\n"</span>, nnz)) ;</div>
<div class="line"><a id="l00411" name="l00411"></a><span class="lineno"> 411</span> <span class="keywordflow">return</span> (<span class="keyword">false</span>) ;</div>
<div class="line"><a id="l00412" name="l00412"></a><span class="lineno"> 412</span> }</div>
<div class="line"><a id="l00413" name="l00413"></a><span class="lineno"> 413</span> </div>
<div class="line"><a id="l00414" name="l00414"></a><span class="lineno"> 414</span> <span class="keywordflow">if</span> (p [0] != 0)</div>
<div class="line"><a id="l00415" name="l00415"></a><span class="lineno"> 415</span> {</div>
<div class="line"><a id="l00416" name="l00416"></a><span class="lineno"> 416</span> stats [Colamd::Status] = Colamd::ErrorP0Nonzero ;</div>
<div class="line"><a id="l00417" name="l00417"></a><span class="lineno"> 417</span> stats [Colamd::Info1] = p [0] ;</div>
<div class="line"><a id="l00418" name="l00418"></a><span class="lineno"> 418</span> COLAMD_DEBUG0 ((<span class="stringliteral">"colamd: p[0] not zero %d\n"</span>, p [0])) ;</div>
<div class="line"><a id="l00419" name="l00419"></a><span class="lineno"> 419</span> <span class="keywordflow">return</span> (<span class="keyword">false</span>) ;</div>
<div class="line"><a id="l00420" name="l00420"></a><span class="lineno"> 420</span> }</div>
<div class="line"><a id="l00421" name="l00421"></a><span class="lineno"> 421</span> </div>
<div class="line"><a id="l00422" name="l00422"></a><span class="lineno"> 422</span> <span class="comment">/* === If no knobs, set default knobs =================================== */</span></div>
<div class="line"><a id="l00423" name="l00423"></a><span class="lineno"> 423</span> </div>
<div class="line"><a id="l00424" name="l00424"></a><span class="lineno"> 424</span> <span class="keywordflow">if</span> (!knobs)</div>
<div class="line"><a id="l00425" name="l00425"></a><span class="lineno"> 425</span> {</div>
<div class="line"><a id="l00426" name="l00426"></a><span class="lineno"> 426</span> set_defaults (default_knobs) ;</div>
<div class="line"><a id="l00427" name="l00427"></a><span class="lineno"> 427</span> knobs = default_knobs ;</div>
<div class="line"><a id="l00428" name="l00428"></a><span class="lineno"> 428</span> }</div>
<div class="line"><a id="l00429" name="l00429"></a><span class="lineno"> 429</span> </div>
<div class="line"><a id="l00430" name="l00430"></a><span class="lineno"> 430</span> <span class="comment">/* === Allocate the Row and Col arrays from array A ===================== */</span></div>
<div class="line"><a id="l00431" name="l00431"></a><span class="lineno"> 431</span> </div>
<div class="line"><a id="l00432" name="l00432"></a><span class="lineno"> 432</span> Col_size = colamd_c (n_col) ;</div>
<div class="line"><a id="l00433" name="l00433"></a><span class="lineno"> 433</span> Row_size = colamd_r (n_row) ;</div>
<div class="line"><a id="l00434" name="l00434"></a><span class="lineno"> 434</span> need = 2*nnz + n_col + Col_size + Row_size ;</div>
<div class="line"><a id="l00435" name="l00435"></a><span class="lineno"> 435</span> </div>
<div class="line"><a id="l00436" name="l00436"></a><span class="lineno"> 436</span> <span class="keywordflow">if</span> (need > Alen)</div>
<div class="line"><a id="l00437" name="l00437"></a><span class="lineno"> 437</span> {</div>
<div class="line"><a id="l00438" name="l00438"></a><span class="lineno"> 438</span> <span class="comment">/* not enough space in array A to perform the ordering */</span></div>
<div class="line"><a id="l00439" name="l00439"></a><span class="lineno"> 439</span> stats [Colamd::Status] = Colamd::ErrorATooSmall ;</div>
<div class="line"><a id="l00440" name="l00440"></a><span class="lineno"> 440</span> stats [Colamd::Info1] = need ;</div>
<div class="line"><a id="l00441" name="l00441"></a><span class="lineno"> 441</span> stats [Colamd::Info2] = Alen ;</div>
<div class="line"><a id="l00442" name="l00442"></a><span class="lineno"> 442</span> COLAMD_DEBUG0 ((<span class="stringliteral">"colamd: Need Alen >= %d, given only Alen = %d\n"</span>, need,Alen));</div>
<div class="line"><a id="l00443" name="l00443"></a><span class="lineno"> 443</span> <span class="keywordflow">return</span> (<span class="keyword">false</span>) ;</div>
<div class="line"><a id="l00444" name="l00444"></a><span class="lineno"> 444</span> }</div>
<div class="line"><a id="l00445" name="l00445"></a><span class="lineno"> 445</span> </div>
<div class="line"><a id="l00446" name="l00446"></a><span class="lineno"> 446</span> Alen -= Col_size + Row_size ;</div>
<div class="line"><a id="l00447" name="l00447"></a><span class="lineno"> 447</span> Col = (ColStructure<IndexType> *) &A [Alen] ;</div>
<div class="line"><a id="l00448" name="l00448"></a><span class="lineno"> 448</span> Row = (RowStructure<IndexType> *) &A [Alen + Col_size] ;</div>
<div class="line"><a id="l00449" name="l00449"></a><span class="lineno"> 449</span> </div>
<div class="line"><a id="l00450" name="l00450"></a><span class="lineno"> 450</span> <span class="comment">/* === Construct the row and column data structures ===================== */</span></div>
<div class="line"><a id="l00451" name="l00451"></a><span class="lineno"> 451</span> </div>
<div class="line"><a id="l00452" name="l00452"></a><span class="lineno"> 452</span> <span class="keywordflow">if</span> (!Colamd::init_rows_cols (n_row, n_col, Row, Col, A, p, stats))</div>
<div class="line"><a id="l00453" name="l00453"></a><span class="lineno"> 453</span> {</div>
<div class="line"><a id="l00454" name="l00454"></a><span class="lineno"> 454</span> <span class="comment">/* input matrix is invalid */</span></div>
<div class="line"><a id="l00455" name="l00455"></a><span class="lineno"> 455</span> COLAMD_DEBUG0 ((<span class="stringliteral">"colamd: Matrix invalid\n"</span>)) ;</div>
<div class="line"><a id="l00456" name="l00456"></a><span class="lineno"> 456</span> <span class="keywordflow">return</span> (<span class="keyword">false</span>) ;</div>
<div class="line"><a id="l00457" name="l00457"></a><span class="lineno"> 457</span> }</div>
<div class="line"><a id="l00458" name="l00458"></a><span class="lineno"> 458</span> </div>
<div class="line"><a id="l00459" name="l00459"></a><span class="lineno"> 459</span> <span class="comment">/* === Initialize scores, kill dense rows/columns ======================= */</span></div>
<div class="line"><a id="l00460" name="l00460"></a><span class="lineno"> 460</span> </div>
<div class="line"><a id="l00461" name="l00461"></a><span class="lineno"> 461</span> Colamd::init_scoring (n_row, n_col, Row, Col, A, p, knobs,</div>
<div class="line"><a id="l00462" name="l00462"></a><span class="lineno"> 462</span> &n_row2, &n_col2, &max_deg) ;</div>
<div class="line"><a id="l00463" name="l00463"></a><span class="lineno"> 463</span> </div>
<div class="line"><a id="l00464" name="l00464"></a><span class="lineno"> 464</span> <span class="comment">/* === Order the supercolumns =========================================== */</span></div>
<div class="line"><a id="l00465" name="l00465"></a><span class="lineno"> 465</span> </div>
<div class="line"><a id="l00466" name="l00466"></a><span class="lineno"> 466</span> ngarbage = Colamd::find_ordering (n_row, n_col, Alen, Row, Col, A, p,</div>
<div class="line"><a id="l00467" name="l00467"></a><span class="lineno"> 467</span> n_col2, max_deg, 2*nnz) ;</div>
<div class="line"><a id="l00468" name="l00468"></a><span class="lineno"> 468</span> </div>
<div class="line"><a id="l00469" name="l00469"></a><span class="lineno"> 469</span> <span class="comment">/* === Order the non-principal columns ================================== */</span></div>
<div class="line"><a id="l00470" name="l00470"></a><span class="lineno"> 470</span> </div>
<div class="line"><a id="l00471" name="l00471"></a><span class="lineno"> 471</span> Colamd::order_children (n_col, Col, p) ;</div>
<div class="line"><a id="l00472" name="l00472"></a><span class="lineno"> 472</span> </div>
<div class="line"><a id="l00473" name="l00473"></a><span class="lineno"> 473</span> <span class="comment">/* === Return statistics in stats ======================================= */</span></div>
<div class="line"><a id="l00474" name="l00474"></a><span class="lineno"> 474</span> </div>
<div class="line"><a id="l00475" name="l00475"></a><span class="lineno"> 475</span> stats [Colamd::DenseRow] = n_row - n_row2 ;</div>
<div class="line"><a id="l00476" name="l00476"></a><span class="lineno"> 476</span> stats [Colamd::DenseCol] = n_col - n_col2 ;</div>
<div class="line"><a id="l00477" name="l00477"></a><span class="lineno"> 477</span> stats [Colamd::DefragCount] = ngarbage ;</div>
<div class="line"><a id="l00478" name="l00478"></a><span class="lineno"> 478</span> COLAMD_DEBUG0 ((<span class="stringliteral">"colamd: done.\n"</span>)) ;</div>
<div class="line"><a id="l00479" name="l00479"></a><span class="lineno"> 479</span> <span class="keywordflow">return</span> (<span class="keyword">true</span>) ;</div>
<div class="line"><a id="l00480" name="l00480"></a><span class="lineno"> 480</span>}</div>
<div class="line"><a id="l00481" name="l00481"></a><span class="lineno"> 481</span> </div>
<div class="line"><a id="l00482" name="l00482"></a><span class="lineno"> 482</span><span class="comment">/* ========================================================================== */</span></div>
<div class="line"><a id="l00483" name="l00483"></a><span class="lineno"> 483</span><span class="comment">/* === NON-USER-CALLABLE ROUTINES: ========================================== */</span></div>
<div class="line"><a id="l00484" name="l00484"></a><span class="lineno"> 484</span><span class="comment">/* ========================================================================== */</span></div>
<div class="line"><a id="l00485" name="l00485"></a><span class="lineno"> 485</span> </div>
<div class="line"><a id="l00486" name="l00486"></a><span class="lineno"> 486</span><span class="comment">/* There are no user-callable routines beyond this point in the file */</span></div>
<div class="line"><a id="l00487" name="l00487"></a><span class="lineno"> 487</span> </div>
<div class="line"><a id="l00488" name="l00488"></a><span class="lineno"> 488</span><span class="comment">/* ========================================================================== */</span></div>
<div class="line"><a id="l00489" name="l00489"></a><span class="lineno"> 489</span><span class="comment">/* === init_rows_cols ======================================================= */</span></div>
<div class="line"><a id="l00490" name="l00490"></a><span class="lineno"> 490</span><span class="comment">/* ========================================================================== */</span></div>
<div class="line"><a id="l00491" name="l00491"></a><span class="lineno"> 491</span> </div>
<div class="line"><a id="l00492" name="l00492"></a><span class="lineno"> 492</span><span class="comment">/*</span></div>
<div class="line"><a id="l00493" name="l00493"></a><span class="lineno"> 493</span><span class="comment"> Takes the column form of the matrix in A and creates the row form of the</span></div>
<div class="line"><a id="l00494" name="l00494"></a><span class="lineno"> 494</span><span class="comment"> matrix. Also, row and column attributes are stored in the Col and Row</span></div>
<div class="line"><a id="l00495" name="l00495"></a><span class="lineno"> 495</span><span class="comment"> structs. If the columns are un-sorted or contain duplicate row indices,</span></div>
<div class="line"><a id="l00496" name="l00496"></a><span class="lineno"> 496</span><span class="comment"> this routine will also sort and remove duplicate row indices from the</span></div>
<div class="line"><a id="l00497" name="l00497"></a><span class="lineno"> 497</span><span class="comment"> column form of the matrix. Returns false if the matrix is invalid,</span></div>
<div class="line"><a id="l00498" name="l00498"></a><span class="lineno"> 498</span><span class="comment"> true otherwise. Not user-callable.</span></div>
<div class="line"><a id="l00499" name="l00499"></a><span class="lineno"> 499</span><span class="comment">*/</span></div>
<div class="line"><a id="l00500" name="l00500"></a><span class="lineno"> 500</span><span class="keyword">template</span> <<span class="keyword">typename</span> IndexType></div>
<div class="line"><a id="l00501" name="l00501"></a><span class="lineno"> 501</span><span class="keyword">static</span> IndexType init_rows_cols <span class="comment">/* returns true if OK, or false otherwise */</span></div>
<div class="line"><a id="l00502" name="l00502"></a><span class="lineno"> 502</span> (</div>
<div class="line"><a id="l00503" name="l00503"></a><span class="lineno"> 503</span> <span class="comment">/* === Parameters ======================================================= */</span></div>
<div class="line"><a id="l00504" name="l00504"></a><span class="lineno"> 504</span> </div>
<div class="line"><a id="l00505" name="l00505"></a><span class="lineno"> 505</span> IndexType n_row, <span class="comment">/* number of rows of A */</span></div>
<div class="line"><a id="l00506" name="l00506"></a><span class="lineno"> 506</span> IndexType n_col, <span class="comment">/* number of columns of A */</span></div>
<div class="line"><a id="l00507" name="l00507"></a><span class="lineno"> 507</span> RowStructure<IndexType> Row [], <span class="comment">/* of size n_row+1 */</span></div>
<div class="line"><a id="l00508" name="l00508"></a><span class="lineno"> 508</span> ColStructure<IndexType> Col [], <span class="comment">/* of size n_col+1 */</span></div>
<div class="line"><a id="l00509" name="l00509"></a><span class="lineno"> 509</span> IndexType A [], <span class="comment">/* row indices of A, of size Alen */</span></div>
<div class="line"><a id="l00510" name="l00510"></a><span class="lineno"> 510</span> IndexType p [], <span class="comment">/* pointers to columns in A, of size n_col+1 */</span></div>
<div class="line"><a id="l00511" name="l00511"></a><span class="lineno"> 511</span> IndexType stats [NStats] <span class="comment">/* colamd statistics */</span></div>
<div class="line"><a id="l00512" name="l00512"></a><span class="lineno"> 512</span> )</div>
<div class="line"><a id="l00513" name="l00513"></a><span class="lineno"> 513</span>{</div>
<div class="line"><a id="l00514" name="l00514"></a><span class="lineno"> 514</span> <span class="comment">/* === Local variables ================================================== */</span></div>
<div class="line"><a id="l00515" name="l00515"></a><span class="lineno"> 515</span> </div>
<div class="line"><a id="l00516" name="l00516"></a><span class="lineno"> 516</span> IndexType col ; <span class="comment">/* a column index */</span></div>
<div class="line"><a id="l00517" name="l00517"></a><span class="lineno"> 517</span> IndexType row ; <span class="comment">/* a row index */</span></div>
<div class="line"><a id="l00518" name="l00518"></a><span class="lineno"> 518</span> IndexType *cp ; <span class="comment">/* a column pointer */</span></div>
<div class="line"><a id="l00519" name="l00519"></a><span class="lineno"> 519</span> IndexType *cp_end ; <span class="comment">/* a pointer to the end of a column */</span></div>
<div class="line"><a id="l00520" name="l00520"></a><span class="lineno"> 520</span> IndexType *rp ; <span class="comment">/* a row pointer */</span></div>
<div class="line"><a id="l00521" name="l00521"></a><span class="lineno"> 521</span> IndexType *rp_end ; <span class="comment">/* a pointer to the end of a row */</span></div>
<div class="line"><a id="l00522" name="l00522"></a><span class="lineno"> 522</span> IndexType last_row ; <span class="comment">/* previous row */</span></div>
<div class="line"><a id="l00523" name="l00523"></a><span class="lineno"> 523</span> </div>
<div class="line"><a id="l00524" name="l00524"></a><span class="lineno"> 524</span> <span class="comment">/* === Initialize columns, and check column pointers ==================== */</span></div>
<div class="line"><a id="l00525" name="l00525"></a><span class="lineno"> 525</span> </div>
<div class="line"><a id="l00526" name="l00526"></a><span class="lineno"> 526</span> <span class="keywordflow">for</span> (col = 0 ; col < n_col ; col++)</div>
<div class="line"><a id="l00527" name="l00527"></a><span class="lineno"> 527</span> {</div>
<div class="line"><a id="l00528" name="l00528"></a><span class="lineno"> 528</span> Col [col].start = p [col] ;</div>
<div class="line"><a id="l00529" name="l00529"></a><span class="lineno"> 529</span> Col [col].length = p [col+1] - p [col] ;</div>
<div class="line"><a id="l00530" name="l00530"></a><span class="lineno"> 530</span> </div>
<div class="line"><a id="l00531" name="l00531"></a><span class="lineno"> 531</span> <span class="keywordflow">if</span> ((Col [col].length) < 0) <span class="comment">// extra parentheses to work-around gcc bug 10200</span></div>
<div class="line"><a id="l00532" name="l00532"></a><span class="lineno"> 532</span> {</div>
<div class="line"><a id="l00533" name="l00533"></a><span class="lineno"> 533</span> <span class="comment">/* column pointers must be non-decreasing */</span></div>
<div class="line"><a id="l00534" name="l00534"></a><span class="lineno"> 534</span> stats [Colamd::Status] = Colamd::ErrorColLengthNegative ;</div>
<div class="line"><a id="l00535" name="l00535"></a><span class="lineno"> 535</span> stats [Colamd::Info1] = col ;</div>
<div class="line"><a id="l00536" name="l00536"></a><span class="lineno"> 536</span> stats [Colamd::Info2] = Col [col].length ;</div>
<div class="line"><a id="l00537" name="l00537"></a><span class="lineno"> 537</span> COLAMD_DEBUG0 ((<span class="stringliteral">"colamd: col %d length %d < 0\n"</span>, col, Col [col].length)) ;</div>
<div class="line"><a id="l00538" name="l00538"></a><span class="lineno"> 538</span> <span class="keywordflow">return</span> (<span class="keyword">false</span>) ;</div>
<div class="line"><a id="l00539" name="l00539"></a><span class="lineno"> 539</span> }</div>
<div class="line"><a id="l00540" name="l00540"></a><span class="lineno"> 540</span> </div>
<div class="line"><a id="l00541" name="l00541"></a><span class="lineno"> 541</span> Col [col].shared1.thickness = 1 ;</div>
<div class="line"><a id="l00542" name="l00542"></a><span class="lineno"> 542</span> Col [col].shared2.score = 0 ;</div>
<div class="line"><a id="l00543" name="l00543"></a><span class="lineno"> 543</span> Col [col].shared3.prev = Empty ;</div>
<div class="line"><a id="l00544" name="l00544"></a><span class="lineno"> 544</span> Col [col].shared4.degree_next = Empty ;</div>
<div class="line"><a id="l00545" name="l00545"></a><span class="lineno"> 545</span> }</div>
<div class="line"><a id="l00546" name="l00546"></a><span class="lineno"> 546</span> </div>
<div class="line"><a id="l00547" name="l00547"></a><span class="lineno"> 547</span> <span class="comment">/* p [0..n_col] no longer needed, used as "head" in subsequent routines */</span></div>
<div class="line"><a id="l00548" name="l00548"></a><span class="lineno"> 548</span> </div>
<div class="line"><a id="l00549" name="l00549"></a><span class="lineno"> 549</span> <span class="comment">/* === Scan columns, compute row degrees, and check row indices ========= */</span></div>
<div class="line"><a id="l00550" name="l00550"></a><span class="lineno"> 550</span> </div>
<div class="line"><a id="l00551" name="l00551"></a><span class="lineno"> 551</span> stats [Info3] = 0 ; <span class="comment">/* number of duplicate or unsorted row indices*/</span></div>
<div class="line"><a id="l00552" name="l00552"></a><span class="lineno"> 552</span> </div>
<div class="line"><a id="l00553" name="l00553"></a><span class="lineno"> 553</span> <span class="keywordflow">for</span> (row = 0 ; row < n_row ; row++)</div>
<div class="line"><a id="l00554" name="l00554"></a><span class="lineno"> 554</span> {</div>
<div class="line"><a id="l00555" name="l00555"></a><span class="lineno"> 555</span> Row [row].length = 0 ;</div>
<div class="line"><a id="l00556" name="l00556"></a><span class="lineno"> 556</span> Row [row].shared2.mark = -1 ;</div>
<div class="line"><a id="l00557" name="l00557"></a><span class="lineno"> 557</span> }</div>
<div class="line"><a id="l00558" name="l00558"></a><span class="lineno"> 558</span> </div>
<div class="line"><a id="l00559" name="l00559"></a><span class="lineno"> 559</span> <span class="keywordflow">for</span> (col = 0 ; col < n_col ; col++)</div>
<div class="line"><a id="l00560" name="l00560"></a><span class="lineno"> 560</span> {</div>
<div class="line"><a id="l00561" name="l00561"></a><span class="lineno"> 561</span> last_row = -1 ;</div>
<div class="line"><a id="l00562" name="l00562"></a><span class="lineno"> 562</span> </div>
<div class="line"><a id="l00563" name="l00563"></a><span class="lineno"> 563</span> cp = &A [p [col]] ;</div>
<div class="line"><a id="l00564" name="l00564"></a><span class="lineno"> 564</span> cp_end = &A [p [col+1]] ;</div>
<div class="line"><a id="l00565" name="l00565"></a><span class="lineno"> 565</span> </div>
<div class="line"><a id="l00566" name="l00566"></a><span class="lineno"> 566</span> <span class="keywordflow">while</span> (cp < cp_end)</div>
<div class="line"><a id="l00567" name="l00567"></a><span class="lineno"> 567</span> {</div>
<div class="line"><a id="l00568" name="l00568"></a><span class="lineno"> 568</span> row = *cp++ ;</div>
<div class="line"><a id="l00569" name="l00569"></a><span class="lineno"> 569</span> </div>
<div class="line"><a id="l00570" name="l00570"></a><span class="lineno"> 570</span> <span class="comment">/* make sure row indices within range */</span></div>
<div class="line"><a id="l00571" name="l00571"></a><span class="lineno"> 571</span> <span class="keywordflow">if</span> (row < 0 || row >= n_row)</div>
<div class="line"><a id="l00572" name="l00572"></a><span class="lineno"> 572</span> {</div>
<div class="line"><a id="l00573" name="l00573"></a><span class="lineno"> 573</span> stats [Colamd::Status] = Colamd::ErrorRowIndexOutOfBounds ;</div>
<div class="line"><a id="l00574" name="l00574"></a><span class="lineno"> 574</span> stats [Colamd::Info1] = col ;</div>
<div class="line"><a id="l00575" name="l00575"></a><span class="lineno"> 575</span> stats [Colamd::Info2] = row ;</div>
<div class="line"><a id="l00576" name="l00576"></a><span class="lineno"> 576</span> stats [Colamd::Info3] = n_row ;</div>
<div class="line"><a id="l00577" name="l00577"></a><span class="lineno"> 577</span> COLAMD_DEBUG0 ((<span class="stringliteral">"colamd: row %d col %d out of bounds\n"</span>, row, col)) ;</div>
<div class="line"><a id="l00578" name="l00578"></a><span class="lineno"> 578</span> <span class="keywordflow">return</span> (<span class="keyword">false</span>) ;</div>
<div class="line"><a id="l00579" name="l00579"></a><span class="lineno"> 579</span> }</div>
<div class="line"><a id="l00580" name="l00580"></a><span class="lineno"> 580</span> </div>
<div class="line"><a id="l00581" name="l00581"></a><span class="lineno"> 581</span> <span class="keywordflow">if</span> (row <= last_row || Row [row].shared2.mark == col)</div>
<div class="line"><a id="l00582" name="l00582"></a><span class="lineno"> 582</span> {</div>
<div class="line"><a id="l00583" name="l00583"></a><span class="lineno"> 583</span> <span class="comment">/* row index are unsorted or repeated (or both), thus col */</span></div>
<div class="line"><a id="l00584" name="l00584"></a><span class="lineno"> 584</span> <span class="comment">/* is jumbled. This is a notice, not an error condition. */</span></div>
<div class="line"><a id="l00585" name="l00585"></a><span class="lineno"> 585</span> stats [Colamd::Status] = Colamd::OkButJumbled ;</div>
<div class="line"><a id="l00586" name="l00586"></a><span class="lineno"> 586</span> stats [Colamd::Info1] = col ;</div>
<div class="line"><a id="l00587" name="l00587"></a><span class="lineno"> 587</span> stats [Colamd::Info2] = row ;</div>
<div class="line"><a id="l00588" name="l00588"></a><span class="lineno"> 588</span> (stats [Colamd::Info3]) ++ ;</div>
<div class="line"><a id="l00589" name="l00589"></a><span class="lineno"> 589</span> COLAMD_DEBUG1 ((<span class="stringliteral">"colamd: row %d col %d unsorted/duplicate\n"</span>,row,col));</div>
<div class="line"><a id="l00590" name="l00590"></a><span class="lineno"> 590</span> }</div>
<div class="line"><a id="l00591" name="l00591"></a><span class="lineno"> 591</span> </div>
<div class="line"><a id="l00592" name="l00592"></a><span class="lineno"> 592</span> <span class="keywordflow">if</span> (Row [row].shared2.mark != col)</div>
<div class="line"><a id="l00593" name="l00593"></a><span class="lineno"> 593</span> {</div>
<div class="line"><a id="l00594" name="l00594"></a><span class="lineno"> 594</span> Row [row].length++ ;</div>
<div class="line"><a id="l00595" name="l00595"></a><span class="lineno"> 595</span> }</div>
<div class="line"><a id="l00596" name="l00596"></a><span class="lineno"> 596</span> <span class="keywordflow">else</span></div>
<div class="line"><a id="l00597" name="l00597"></a><span class="lineno"> 597</span> {</div>
<div class="line"><a id="l00598" name="l00598"></a><span class="lineno"> 598</span> <span class="comment">/* this is a repeated entry in the column, */</span></div>
<div class="line"><a id="l00599" name="l00599"></a><span class="lineno"> 599</span> <span class="comment">/* it will be removed */</span></div>
<div class="line"><a id="l00600" name="l00600"></a><span class="lineno"> 600</span> Col [col].length-- ;</div>
<div class="line"><a id="l00601" name="l00601"></a><span class="lineno"> 601</span> }</div>
<div class="line"><a id="l00602" name="l00602"></a><span class="lineno"> 602</span> </div>
<div class="line"><a id="l00603" name="l00603"></a><span class="lineno"> 603</span> <span class="comment">/* mark the row as having been seen in this column */</span></div>
<div class="line"><a id="l00604" name="l00604"></a><span class="lineno"> 604</span> Row [row].shared2.mark = col ;</div>
<div class="line"><a id="l00605" name="l00605"></a><span class="lineno"> 605</span> </div>
<div class="line"><a id="l00606" name="l00606"></a><span class="lineno"> 606</span> last_row = row ;</div>
<div class="line"><a id="l00607" name="l00607"></a><span class="lineno"> 607</span> }</div>
<div class="line"><a id="l00608" name="l00608"></a><span class="lineno"> 608</span> }</div>
<div class="line"><a id="l00609" name="l00609"></a><span class="lineno"> 609</span> </div>
<div class="line"><a id="l00610" name="l00610"></a><span class="lineno"> 610</span> <span class="comment">/* === Compute row pointers ============================================= */</span></div>
<div class="line"><a id="l00611" name="l00611"></a><span class="lineno"> 611</span> </div>
<div class="line"><a id="l00612" name="l00612"></a><span class="lineno"> 612</span> <span class="comment">/* row form of the matrix starts directly after the column */</span></div>
<div class="line"><a id="l00613" name="l00613"></a><span class="lineno"> 613</span> <span class="comment">/* form of matrix in A */</span></div>
<div class="line"><a id="l00614" name="l00614"></a><span class="lineno"> 614</span> Row [0].start = p [n_col] ;</div>
<div class="line"><a id="l00615" name="l00615"></a><span class="lineno"> 615</span> Row [0].shared1.p = Row [0].start ;</div>
<div class="line"><a id="l00616" name="l00616"></a><span class="lineno"> 616</span> Row [0].shared2.mark = -1 ;</div>
<div class="line"><a id="l00617" name="l00617"></a><span class="lineno"> 617</span> <span class="keywordflow">for</span> (row = 1 ; row < n_row ; row++)</div>
<div class="line"><a id="l00618" name="l00618"></a><span class="lineno"> 618</span> {</div>
<div class="line"><a id="l00619" name="l00619"></a><span class="lineno"> 619</span> Row [row].start = Row [row-1].start + Row [row-1].length ;</div>
<div class="line"><a id="l00620" name="l00620"></a><span class="lineno"> 620</span> Row [row].shared1.p = Row [row].start ;</div>
<div class="line"><a id="l00621" name="l00621"></a><span class="lineno"> 621</span> Row [row].shared2.mark = -1 ;</div>
<div class="line"><a id="l00622" name="l00622"></a><span class="lineno"> 622</span> }</div>
<div class="line"><a id="l00623" name="l00623"></a><span class="lineno"> 623</span> </div>
<div class="line"><a id="l00624" name="l00624"></a><span class="lineno"> 624</span> <span class="comment">/* === Create row form ================================================== */</span></div>
<div class="line"><a id="l00625" name="l00625"></a><span class="lineno"> 625</span> </div>
<div class="line"><a id="l00626" name="l00626"></a><span class="lineno"> 626</span> <span class="keywordflow">if</span> (stats [Status] == OkButJumbled)</div>
<div class="line"><a id="l00627" name="l00627"></a><span class="lineno"> 627</span> {</div>
<div class="line"><a id="l00628" name="l00628"></a><span class="lineno"> 628</span> <span class="comment">/* if cols jumbled, watch for repeated row indices */</span></div>
<div class="line"><a id="l00629" name="l00629"></a><span class="lineno"> 629</span> <span class="keywordflow">for</span> (col = 0 ; col < n_col ; col++)</div>
<div class="line"><a id="l00630" name="l00630"></a><span class="lineno"> 630</span> {</div>
<div class="line"><a id="l00631" name="l00631"></a><span class="lineno"> 631</span> cp = &A [p [col]] ;</div>
<div class="line"><a id="l00632" name="l00632"></a><span class="lineno"> 632</span> cp_end = &A [p [col+1]] ;</div>
<div class="line"><a id="l00633" name="l00633"></a><span class="lineno"> 633</span> <span class="keywordflow">while</span> (cp < cp_end)</div>
<div class="line"><a id="l00634" name="l00634"></a><span class="lineno"> 634</span> {</div>
<div class="line"><a id="l00635" name="l00635"></a><span class="lineno"> 635</span> row = *cp++ ;</div>
<div class="line"><a id="l00636" name="l00636"></a><span class="lineno"> 636</span> <span class="keywordflow">if</span> (Row [row].shared2.mark != col)</div>
<div class="line"><a id="l00637" name="l00637"></a><span class="lineno"> 637</span> {</div>
<div class="line"><a id="l00638" name="l00638"></a><span class="lineno"> 638</span> A [(Row [row].shared1.p)++] = col ;</div>
<div class="line"><a id="l00639" name="l00639"></a><span class="lineno"> 639</span> Row [row].shared2.mark = col ;</div>
<div class="line"><a id="l00640" name="l00640"></a><span class="lineno"> 640</span> }</div>
<div class="line"><a id="l00641" name="l00641"></a><span class="lineno"> 641</span> }</div>
<div class="line"><a id="l00642" name="l00642"></a><span class="lineno"> 642</span> }</div>
<div class="line"><a id="l00643" name="l00643"></a><span class="lineno"> 643</span> }</div>
<div class="line"><a id="l00644" name="l00644"></a><span class="lineno"> 644</span> <span class="keywordflow">else</span></div>
<div class="line"><a id="l00645" name="l00645"></a><span class="lineno"> 645</span> {</div>
<div class="line"><a id="l00646" name="l00646"></a><span class="lineno"> 646</span> <span class="comment">/* if cols not jumbled, we don't need the mark (this is faster) */</span></div>
<div class="line"><a id="l00647" name="l00647"></a><span class="lineno"> 647</span> <span class="keywordflow">for</span> (col = 0 ; col < n_col ; col++)</div>
<div class="line"><a id="l00648" name="l00648"></a><span class="lineno"> 648</span> {</div>
<div class="line"><a id="l00649" name="l00649"></a><span class="lineno"> 649</span> cp = &A [p [col]] ;</div>
<div class="line"><a id="l00650" name="l00650"></a><span class="lineno"> 650</span> cp_end = &A [p [col+1]] ;</div>
<div class="line"><a id="l00651" name="l00651"></a><span class="lineno"> 651</span> <span class="keywordflow">while</span> (cp < cp_end)</div>
<div class="line"><a id="l00652" name="l00652"></a><span class="lineno"> 652</span> {</div>
<div class="line"><a id="l00653" name="l00653"></a><span class="lineno"> 653</span> A [(Row [*cp++].shared1.p)++] = col ;</div>
<div class="line"><a id="l00654" name="l00654"></a><span class="lineno"> 654</span> }</div>
<div class="line"><a id="l00655" name="l00655"></a><span class="lineno"> 655</span> }</div>
<div class="line"><a id="l00656" name="l00656"></a><span class="lineno"> 656</span> }</div>
<div class="line"><a id="l00657" name="l00657"></a><span class="lineno"> 657</span> </div>
<div class="line"><a id="l00658" name="l00658"></a><span class="lineno"> 658</span> <span class="comment">/* === Clear the row marks and set row degrees ========================== */</span></div>
<div class="line"><a id="l00659" name="l00659"></a><span class="lineno"> 659</span> </div>
<div class="line"><a id="l00660" name="l00660"></a><span class="lineno"> 660</span> <span class="keywordflow">for</span> (row = 0 ; row < n_row ; row++)</div>
<div class="line"><a id="l00661" name="l00661"></a><span class="lineno"> 661</span> {</div>
<div class="line"><a id="l00662" name="l00662"></a><span class="lineno"> 662</span> Row [row].shared2.mark = 0 ;</div>
<div class="line"><a id="l00663" name="l00663"></a><span class="lineno"> 663</span> Row [row].shared1.degree = Row [row].length ;</div>
<div class="line"><a id="l00664" name="l00664"></a><span class="lineno"> 664</span> }</div>
<div class="line"><a id="l00665" name="l00665"></a><span class="lineno"> 665</span> </div>
<div class="line"><a id="l00666" name="l00666"></a><span class="lineno"> 666</span> <span class="comment">/* === See if we need to re-create columns ============================== */</span></div>
<div class="line"><a id="l00667" name="l00667"></a><span class="lineno"> 667</span> </div>
<div class="line"><a id="l00668" name="l00668"></a><span class="lineno"> 668</span> <span class="keywordflow">if</span> (stats [Status] == OkButJumbled)</div>
<div class="line"><a id="l00669" name="l00669"></a><span class="lineno"> 669</span> {</div>
<div class="line"><a id="l00670" name="l00670"></a><span class="lineno"> 670</span> COLAMD_DEBUG0 ((<span class="stringliteral">"colamd: reconstructing column form, matrix jumbled\n"</span>)) ;</div>
<div class="line"><a id="l00671" name="l00671"></a><span class="lineno"> 671</span> </div>
<div class="line"><a id="l00672" name="l00672"></a><span class="lineno"> 672</span> </div>
<div class="line"><a id="l00673" name="l00673"></a><span class="lineno"> 673</span> <span class="comment">/* === Compute col pointers ========================================= */</span></div>
<div class="line"><a id="l00674" name="l00674"></a><span class="lineno"> 674</span> </div>
<div class="line"><a id="l00675" name="l00675"></a><span class="lineno"> 675</span> <span class="comment">/* col form of the matrix starts at A [0]. */</span></div>
<div class="line"><a id="l00676" name="l00676"></a><span class="lineno"> 676</span> <span class="comment">/* Note, we may have a gap between the col form and the row */</span></div>
<div class="line"><a id="l00677" name="l00677"></a><span class="lineno"> 677</span> <span class="comment">/* form if there were duplicate entries, if so, it will be */</span></div>
<div class="line"><a id="l00678" name="l00678"></a><span class="lineno"> 678</span> <span class="comment">/* removed upon the first garbage collection */</span></div>
<div class="line"><a id="l00679" name="l00679"></a><span class="lineno"> 679</span> Col [0].start = 0 ;</div>
<div class="line"><a id="l00680" name="l00680"></a><span class="lineno"> 680</span> p [0] = Col [0].start ;</div>
<div class="line"><a id="l00681" name="l00681"></a><span class="lineno"> 681</span> <span class="keywordflow">for</span> (col = 1 ; col < n_col ; col++)</div>
<div class="line"><a id="l00682" name="l00682"></a><span class="lineno"> 682</span> {</div>
<div class="line"><a id="l00683" name="l00683"></a><span class="lineno"> 683</span> <span class="comment">/* note that the lengths here are for pruned columns, i.e. */</span></div>
<div class="line"><a id="l00684" name="l00684"></a><span class="lineno"> 684</span> <span class="comment">/* no duplicate row indices will exist for these columns */</span></div>
<div class="line"><a id="l00685" name="l00685"></a><span class="lineno"> 685</span> Col [col].start = Col [col-1].start + Col [col-1].length ;</div>
<div class="line"><a id="l00686" name="l00686"></a><span class="lineno"> 686</span> p [col] = Col [col].start ;</div>
<div class="line"><a id="l00687" name="l00687"></a><span class="lineno"> 687</span> }</div>
<div class="line"><a id="l00688" name="l00688"></a><span class="lineno"> 688</span> </div>
<div class="line"><a id="l00689" name="l00689"></a><span class="lineno"> 689</span> <span class="comment">/* === Re-create col form =========================================== */</span></div>
<div class="line"><a id="l00690" name="l00690"></a><span class="lineno"> 690</span> </div>
<div class="line"><a id="l00691" name="l00691"></a><span class="lineno"> 691</span> <span class="keywordflow">for</span> (row = 0 ; row < n_row ; row++)</div>
<div class="line"><a id="l00692" name="l00692"></a><span class="lineno"> 692</span> {</div>
<div class="line"><a id="l00693" name="l00693"></a><span class="lineno"> 693</span> rp = &A [Row [row].start] ;</div>
<div class="line"><a id="l00694" name="l00694"></a><span class="lineno"> 694</span> rp_end = rp + Row [row].length ;</div>
<div class="line"><a id="l00695" name="l00695"></a><span class="lineno"> 695</span> <span class="keywordflow">while</span> (rp < rp_end)</div>
<div class="line"><a id="l00696" name="l00696"></a><span class="lineno"> 696</span> {</div>
<div class="line"><a id="l00697" name="l00697"></a><span class="lineno"> 697</span> A [(p [*rp++])++] = row ;</div>
<div class="line"><a id="l00698" name="l00698"></a><span class="lineno"> 698</span> }</div>
<div class="line"><a id="l00699" name="l00699"></a><span class="lineno"> 699</span> }</div>
<div class="line"><a id="l00700" name="l00700"></a><span class="lineno"> 700</span> }</div>
<div class="line"><a id="l00701" name="l00701"></a><span class="lineno"> 701</span> </div>
<div class="line"><a id="l00702" name="l00702"></a><span class="lineno"> 702</span> <span class="comment">/* === Done. Matrix is not (or no longer) jumbled ====================== */</span></div>
<div class="line"><a id="l00703" name="l00703"></a><span class="lineno"> 703</span> </div>
<div class="line"><a id="l00704" name="l00704"></a><span class="lineno"> 704</span> <span class="keywordflow">return</span> (<span class="keyword">true</span>) ;</div>
<div class="line"><a id="l00705" name="l00705"></a><span class="lineno"> 705</span>}</div>
<div class="line"><a id="l00706" name="l00706"></a><span class="lineno"> 706</span> </div>
<div class="line"><a id="l00707" name="l00707"></a><span class="lineno"> 707</span> </div>
<div class="line"><a id="l00708" name="l00708"></a><span class="lineno"> 708</span><span class="comment">/* ========================================================================== */</span></div>
<div class="line"><a id="l00709" name="l00709"></a><span class="lineno"> 709</span><span class="comment">/* === init_scoring ========================================================= */</span></div>
<div class="line"><a id="l00710" name="l00710"></a><span class="lineno"> 710</span><span class="comment">/* ========================================================================== */</span></div>
<div class="line"><a id="l00711" name="l00711"></a><span class="lineno"> 711</span> </div>
<div class="line"><a id="l00712" name="l00712"></a><span class="lineno"> 712</span><span class="comment">/*</span></div>
<div class="line"><a id="l00713" name="l00713"></a><span class="lineno"> 713</span><span class="comment"> Kills dense or empty columns and rows, calculates an initial score for</span></div>
<div class="line"><a id="l00714" name="l00714"></a><span class="lineno"> 714</span><span class="comment"> each column, and places all columns in the degree lists. Not user-callable.</span></div>
<div class="line"><a id="l00715" name="l00715"></a><span class="lineno"> 715</span><span class="comment">*/</span></div>
<div class="line"><a id="l00716" name="l00716"></a><span class="lineno"> 716</span><span class="keyword">template</span> <<span class="keyword">typename</span> IndexType></div>
<div class="line"><a id="l00717" name="l00717"></a><span class="lineno"> 717</span><span class="keyword">static</span> <span class="keywordtype">void</span> init_scoring</div>
<div class="line"><a id="l00718" name="l00718"></a><span class="lineno"> 718</span> (</div>
<div class="line"><a id="l00719" name="l00719"></a><span class="lineno"> 719</span> <span class="comment">/* === Parameters ======================================================= */</span></div>
<div class="line"><a id="l00720" name="l00720"></a><span class="lineno"> 720</span> </div>
<div class="line"><a id="l00721" name="l00721"></a><span class="lineno"> 721</span> IndexType n_row, <span class="comment">/* number of rows of A */</span></div>
<div class="line"><a id="l00722" name="l00722"></a><span class="lineno"> 722</span> IndexType n_col, <span class="comment">/* number of columns of A */</span></div>
<div class="line"><a id="l00723" name="l00723"></a><span class="lineno"> 723</span> RowStructure<IndexType> Row [], <span class="comment">/* of size n_row+1 */</span></div>
<div class="line"><a id="l00724" name="l00724"></a><span class="lineno"> 724</span> ColStructure<IndexType> Col [], <span class="comment">/* of size n_col+1 */</span></div>
<div class="line"><a id="l00725" name="l00725"></a><span class="lineno"> 725</span> IndexType A [], <span class="comment">/* column form and row form of A */</span></div>
<div class="line"><a id="l00726" name="l00726"></a><span class="lineno"> 726</span> IndexType head [], <span class="comment">/* of size n_col+1 */</span></div>
<div class="line"><a id="l00727" name="l00727"></a><span class="lineno"> 727</span> <span class="keywordtype">double</span> knobs [NKnobs],<span class="comment">/* parameters */</span></div>
<div class="line"><a id="l00728" name="l00728"></a><span class="lineno"> 728</span> IndexType *p_n_row2, <span class="comment">/* number of non-dense, non-empty rows */</span></div>
<div class="line"><a id="l00729" name="l00729"></a><span class="lineno"> 729</span> IndexType *p_n_col2, <span class="comment">/* number of non-dense, non-empty columns */</span></div>
<div class="line"><a id="l00730" name="l00730"></a><span class="lineno"> 730</span> IndexType *p_max_deg <span class="comment">/* maximum row degree */</span></div>
<div class="line"><a id="l00731" name="l00731"></a><span class="lineno"> 731</span> )</div>
<div class="line"><a id="l00732" name="l00732"></a><span class="lineno"> 732</span>{</div>
<div class="line"><a id="l00733" name="l00733"></a><span class="lineno"> 733</span> <span class="comment">/* === Local variables ================================================== */</span></div>
<div class="line"><a id="l00734" name="l00734"></a><span class="lineno"> 734</span> </div>
<div class="line"><a id="l00735" name="l00735"></a><span class="lineno"> 735</span> IndexType c ; <span class="comment">/* a column index */</span></div>
<div class="line"><a id="l00736" name="l00736"></a><span class="lineno"> 736</span> IndexType r, row ; <span class="comment">/* a row index */</span></div>
<div class="line"><a id="l00737" name="l00737"></a><span class="lineno"> 737</span> IndexType *cp ; <span class="comment">/* a column pointer */</span></div>
<div class="line"><a id="l00738" name="l00738"></a><span class="lineno"> 738</span> IndexType deg ; <span class="comment">/* degree of a row or column */</span></div>
<div class="line"><a id="l00739" name="l00739"></a><span class="lineno"> 739</span> IndexType *cp_end ; <span class="comment">/* a pointer to the end of a column */</span></div>
<div class="line"><a id="l00740" name="l00740"></a><span class="lineno"> 740</span> IndexType *new_cp ; <span class="comment">/* new column pointer */</span></div>
<div class="line"><a id="l00741" name="l00741"></a><span class="lineno"> 741</span> IndexType col_length ; <span class="comment">/* length of pruned column */</span></div>
<div class="line"><a id="l00742" name="l00742"></a><span class="lineno"> 742</span> IndexType score ; <span class="comment">/* current column score */</span></div>
<div class="line"><a id="l00743" name="l00743"></a><span class="lineno"> 743</span> IndexType n_col2 ; <span class="comment">/* number of non-dense, non-empty columns */</span></div>
<div class="line"><a id="l00744" name="l00744"></a><span class="lineno"> 744</span> IndexType n_row2 ; <span class="comment">/* number of non-dense, non-empty rows */</span></div>
<div class="line"><a id="l00745" name="l00745"></a><span class="lineno"> 745</span> IndexType dense_row_count ; <span class="comment">/* remove rows with more entries than this */</span></div>
<div class="line"><a id="l00746" name="l00746"></a><span class="lineno"> 746</span> IndexType dense_col_count ; <span class="comment">/* remove cols with more entries than this */</span></div>
<div class="line"><a id="l00747" name="l00747"></a><span class="lineno"> 747</span> IndexType min_score ; <span class="comment">/* smallest column score */</span></div>
<div class="line"><a id="l00748" name="l00748"></a><span class="lineno"> 748</span> IndexType max_deg ; <span class="comment">/* maximum row degree */</span></div>
<div class="line"><a id="l00749" name="l00749"></a><span class="lineno"> 749</span> IndexType next_col ; <span class="comment">/* Used to add to degree list.*/</span></div>
<div class="line"><a id="l00750" name="l00750"></a><span class="lineno"> 750</span> </div>
<div class="line"><a id="l00751" name="l00751"></a><span class="lineno"> 751</span> </div>
<div class="line"><a id="l00752" name="l00752"></a><span class="lineno"> 752</span> <span class="comment">/* === Extract knobs ==================================================== */</span></div>
<div class="line"><a id="l00753" name="l00753"></a><span class="lineno"> 753</span> </div>
<div class="line"><a id="l00754" name="l00754"></a><span class="lineno"> 754</span> dense_row_count = numext::maxi(IndexType(0), numext::mini(IndexType(knobs [Colamd::DenseRow] * n_col), n_col)) ;</div>
<div class="line"><a id="l00755" name="l00755"></a><span class="lineno"> 755</span> dense_col_count = numext::maxi(IndexType(0), numext::mini(IndexType(knobs [Colamd::DenseCol] * n_row), n_row)) ;</div>
<div class="line"><a id="l00756" name="l00756"></a><span class="lineno"> 756</span> COLAMD_DEBUG1 ((<span class="stringliteral">"colamd: densecount: %d %d\n"</span>, dense_row_count, dense_col_count)) ;</div>
<div class="line"><a id="l00757" name="l00757"></a><span class="lineno"> 757</span> max_deg = 0 ;</div>
<div class="line"><a id="l00758" name="l00758"></a><span class="lineno"> 758</span> n_col2 = n_col ;</div>
<div class="line"><a id="l00759" name="l00759"></a><span class="lineno"> 759</span> n_row2 = n_row ;</div>
<div class="line"><a id="l00760" name="l00760"></a><span class="lineno"> 760</span> </div>
<div class="line"><a id="l00761" name="l00761"></a><span class="lineno"> 761</span> <span class="comment">/* === Kill empty columns =============================================== */</span></div>
<div class="line"><a id="l00762" name="l00762"></a><span class="lineno"> 762</span> </div>
<div class="line"><a id="l00763" name="l00763"></a><span class="lineno"> 763</span> <span class="comment">/* Put the empty columns at the end in their natural order, so that LU */</span></div>
<div class="line"><a id="l00764" name="l00764"></a><span class="lineno"> 764</span> <span class="comment">/* factorization can proceed as far as possible. */</span></div>
<div class="line"><a id="l00765" name="l00765"></a><span class="lineno"> 765</span> <span class="keywordflow">for</span> (c = n_col-1 ; c >= 0 ; c--)</div>
<div class="line"><a id="l00766" name="l00766"></a><span class="lineno"> 766</span> {</div>
<div class="line"><a id="l00767" name="l00767"></a><span class="lineno"> 767</span> deg = Col [c].length ;</div>
<div class="line"><a id="l00768" name="l00768"></a><span class="lineno"> 768</span> <span class="keywordflow">if</span> (deg == 0)</div>
<div class="line"><a id="l00769" name="l00769"></a><span class="lineno"> 769</span> {</div>
<div class="line"><a id="l00770" name="l00770"></a><span class="lineno"> 770</span> <span class="comment">/* this is a empty column, kill and order it last */</span></div>
<div class="line"><a id="l00771" name="l00771"></a><span class="lineno"> 771</span> Col [c].shared2.order = --n_col2 ;</div>
<div class="line"><a id="l00772" name="l00772"></a><span class="lineno"> 772</span> Col[c].kill_principal() ;</div>
<div class="line"><a id="l00773" name="l00773"></a><span class="lineno"> 773</span> }</div>
<div class="line"><a id="l00774" name="l00774"></a><span class="lineno"> 774</span> }</div>
<div class="line"><a id="l00775" name="l00775"></a><span class="lineno"> 775</span> COLAMD_DEBUG1 ((<span class="stringliteral">"colamd: null columns killed: %d\n"</span>, n_col - n_col2)) ;</div>
<div class="line"><a id="l00776" name="l00776"></a><span class="lineno"> 776</span> </div>
<div class="line"><a id="l00777" name="l00777"></a><span class="lineno"> 777</span> <span class="comment">/* === Kill dense columns =============================================== */</span></div>
<div class="line"><a id="l00778" name="l00778"></a><span class="lineno"> 778</span> </div>
<div class="line"><a id="l00779" name="l00779"></a><span class="lineno"> 779</span> <span class="comment">/* Put the dense columns at the end, in their natural order */</span></div>
<div class="line"><a id="l00780" name="l00780"></a><span class="lineno"> 780</span> <span class="keywordflow">for</span> (c = n_col-1 ; c >= 0 ; c--)</div>
<div class="line"><a id="l00781" name="l00781"></a><span class="lineno"> 781</span> {</div>
<div class="line"><a id="l00782" name="l00782"></a><span class="lineno"> 782</span> <span class="comment">/* skip any dead columns */</span></div>
<div class="line"><a id="l00783" name="l00783"></a><span class="lineno"> 783</span> <span class="keywordflow">if</span> (Col[c].is_dead())</div>
<div class="line"><a id="l00784" name="l00784"></a><span class="lineno"> 784</span> {</div>
<div class="line"><a id="l00785" name="l00785"></a><span class="lineno"> 785</span> continue ;</div>
<div class="line"><a id="l00786" name="l00786"></a><span class="lineno"> 786</span> }</div>
<div class="line"><a id="l00787" name="l00787"></a><span class="lineno"> 787</span> deg = Col [c].length ;</div>
<div class="line"><a id="l00788" name="l00788"></a><span class="lineno"> 788</span> <span class="keywordflow">if</span> (deg > dense_col_count)</div>
<div class="line"><a id="l00789" name="l00789"></a><span class="lineno"> 789</span> {</div>
<div class="line"><a id="l00790" name="l00790"></a><span class="lineno"> 790</span> <span class="comment">/* this is a dense column, kill and order it last */</span></div>
<div class="line"><a id="l00791" name="l00791"></a><span class="lineno"> 791</span> Col [c].shared2.order = --n_col2 ;</div>
<div class="line"><a id="l00792" name="l00792"></a><span class="lineno"> 792</span> <span class="comment">/* decrement the row degrees */</span></div>
<div class="line"><a id="l00793" name="l00793"></a><span class="lineno"> 793</span> cp = &A [Col [c].start] ;</div>
<div class="line"><a id="l00794" name="l00794"></a><span class="lineno"> 794</span> cp_end = cp + Col [c].length ;</div>
<div class="line"><a id="l00795" name="l00795"></a><span class="lineno"> 795</span> <span class="keywordflow">while</span> (cp < cp_end)</div>
<div class="line"><a id="l00796" name="l00796"></a><span class="lineno"> 796</span> {</div>
<div class="line"><a id="l00797" name="l00797"></a><span class="lineno"> 797</span> Row [*cp++].shared1.degree-- ;</div>
<div class="line"><a id="l00798" name="l00798"></a><span class="lineno"> 798</span> }</div>
<div class="line"><a id="l00799" name="l00799"></a><span class="lineno"> 799</span> Col[c].kill_principal() ;</div>
<div class="line"><a id="l00800" name="l00800"></a><span class="lineno"> 800</span> }</div>
<div class="line"><a id="l00801" name="l00801"></a><span class="lineno"> 801</span> }</div>
<div class="line"><a id="l00802" name="l00802"></a><span class="lineno"> 802</span> COLAMD_DEBUG1 ((<span class="stringliteral">"colamd: Dense and null columns killed: %d\n"</span>, n_col - n_col2)) ;</div>
<div class="line"><a id="l00803" name="l00803"></a><span class="lineno"> 803</span> </div>
<div class="line"><a id="l00804" name="l00804"></a><span class="lineno"> 804</span> <span class="comment">/* === Kill dense and empty rows ======================================== */</span></div>
<div class="line"><a id="l00805" name="l00805"></a><span class="lineno"> 805</span> </div>
<div class="line"><a id="l00806" name="l00806"></a><span class="lineno"> 806</span> <span class="keywordflow">for</span> (r = 0 ; r < n_row ; r++)</div>
<div class="line"><a id="l00807" name="l00807"></a><span class="lineno"> 807</span> {</div>
<div class="line"><a id="l00808" name="l00808"></a><span class="lineno"> 808</span> deg = Row [r].shared1.degree ;</div>
<div class="line"><a id="l00809" name="l00809"></a><span class="lineno"> 809</span> COLAMD_ASSERT (deg >= 0 && deg <= n_col) ;</div>
<div class="line"><a id="l00810" name="l00810"></a><span class="lineno"> 810</span> <span class="keywordflow">if</span> (deg > dense_row_count || deg == 0)</div>
<div class="line"><a id="l00811" name="l00811"></a><span class="lineno"> 811</span> {</div>
<div class="line"><a id="l00812" name="l00812"></a><span class="lineno"> 812</span> <span class="comment">/* kill a dense or empty row */</span></div>
<div class="line"><a id="l00813" name="l00813"></a><span class="lineno"> 813</span> Row[r].kill() ;</div>
<div class="line"><a id="l00814" name="l00814"></a><span class="lineno"> 814</span> --n_row2 ;</div>
<div class="line"><a id="l00815" name="l00815"></a><span class="lineno"> 815</span> }</div>
<div class="line"><a id="l00816" name="l00816"></a><span class="lineno"> 816</span> <span class="keywordflow">else</span></div>
<div class="line"><a id="l00817" name="l00817"></a><span class="lineno"> 817</span> {</div>
<div class="line"><a id="l00818" name="l00818"></a><span class="lineno"> 818</span> <span class="comment">/* keep track of max degree of remaining rows */</span></div>
<div class="line"><a id="l00819" name="l00819"></a><span class="lineno"> 819</span> max_deg = numext::maxi(max_deg, deg) ;</div>
<div class="line"><a id="l00820" name="l00820"></a><span class="lineno"> 820</span> }</div>
<div class="line"><a id="l00821" name="l00821"></a><span class="lineno"> 821</span> }</div>
<div class="line"><a id="l00822" name="l00822"></a><span class="lineno"> 822</span> COLAMD_DEBUG1 ((<span class="stringliteral">"colamd: Dense and null rows killed: %d\n"</span>, n_row - n_row2)) ;</div>
<div class="line"><a id="l00823" name="l00823"></a><span class="lineno"> 823</span> </div>
<div class="line"><a id="l00824" name="l00824"></a><span class="lineno"> 824</span> <span class="comment">/* === Compute initial column scores ==================================== */</span></div>
<div class="line"><a id="l00825" name="l00825"></a><span class="lineno"> 825</span> </div>
<div class="line"><a id="l00826" name="l00826"></a><span class="lineno"> 826</span> <span class="comment">/* At this point the row degrees are accurate. They reflect the number */</span></div>
<div class="line"><a id="l00827" name="l00827"></a><span class="lineno"> 827</span> <span class="comment">/* of "live" (non-dense) columns in each row. No empty rows exist. */</span></div>
<div class="line"><a id="l00828" name="l00828"></a><span class="lineno"> 828</span> <span class="comment">/* Some "live" columns may contain only dead rows, however. These are */</span></div>
<div class="line"><a id="l00829" name="l00829"></a><span class="lineno"> 829</span> <span class="comment">/* pruned in the code below. */</span></div>
<div class="line"><a id="l00830" name="l00830"></a><span class="lineno"> 830</span> </div>
<div class="line"><a id="l00831" name="l00831"></a><span class="lineno"> 831</span> <span class="comment">/* now find the initial matlab score for each column */</span></div>
<div class="line"><a id="l00832" name="l00832"></a><span class="lineno"> 832</span> <span class="keywordflow">for</span> (c = n_col-1 ; c >= 0 ; c--)</div>
<div class="line"><a id="l00833" name="l00833"></a><span class="lineno"> 833</span> {</div>
<div class="line"><a id="l00834" name="l00834"></a><span class="lineno"> 834</span> <span class="comment">/* skip dead column */</span></div>
<div class="line"><a id="l00835" name="l00835"></a><span class="lineno"> 835</span> <span class="keywordflow">if</span> (Col[c].is_dead())</div>
<div class="line"><a id="l00836" name="l00836"></a><span class="lineno"> 836</span> {</div>
<div class="line"><a id="l00837" name="l00837"></a><span class="lineno"> 837</span> continue ;</div>
<div class="line"><a id="l00838" name="l00838"></a><span class="lineno"> 838</span> }</div>
<div class="line"><a id="l00839" name="l00839"></a><span class="lineno"> 839</span> score = 0 ;</div>
<div class="line"><a id="l00840" name="l00840"></a><span class="lineno"> 840</span> cp = &A [Col [c].start] ;</div>
<div class="line"><a id="l00841" name="l00841"></a><span class="lineno"> 841</span> new_cp = cp ;</div>
<div class="line"><a id="l00842" name="l00842"></a><span class="lineno"> 842</span> cp_end = cp + Col [c].length ;</div>
<div class="line"><a id="l00843" name="l00843"></a><span class="lineno"> 843</span> <span class="keywordflow">while</span> (cp < cp_end)</div>
<div class="line"><a id="l00844" name="l00844"></a><span class="lineno"> 844</span> {</div>
<div class="line"><a id="l00845" name="l00845"></a><span class="lineno"> 845</span> <span class="comment">/* get a row */</span></div>
<div class="line"><a id="l00846" name="l00846"></a><span class="lineno"> 846</span> row = *cp++ ;</div>
<div class="line"><a id="l00847" name="l00847"></a><span class="lineno"> 847</span> <span class="comment">/* skip if dead */</span></div>
<div class="line"><a id="l00848" name="l00848"></a><span class="lineno"> 848</span> <span class="keywordflow">if</span> (Row[row].is_dead())</div>
<div class="line"><a id="l00849" name="l00849"></a><span class="lineno"> 849</span> {</div>
<div class="line"><a id="l00850" name="l00850"></a><span class="lineno"> 850</span> continue ;</div>
<div class="line"><a id="l00851" name="l00851"></a><span class="lineno"> 851</span> }</div>
<div class="line"><a id="l00852" name="l00852"></a><span class="lineno"> 852</span> <span class="comment">/* compact the column */</span></div>
<div class="line"><a id="l00853" name="l00853"></a><span class="lineno"> 853</span> *new_cp++ = row ;</div>
<div class="line"><a id="l00854" name="l00854"></a><span class="lineno"> 854</span> <span class="comment">/* add row's external degree */</span></div>
<div class="line"><a id="l00855" name="l00855"></a><span class="lineno"> 855</span> score += Row [row].shared1.degree - 1 ;</div>
<div class="line"><a id="l00856" name="l00856"></a><span class="lineno"> 856</span> <span class="comment">/* guard against integer overflow */</span></div>
<div class="line"><a id="l00857" name="l00857"></a><span class="lineno"> 857</span> score = numext::mini(score, n_col) ;</div>
<div class="line"><a id="l00858" name="l00858"></a><span class="lineno"> 858</span> }</div>
<div class="line"><a id="l00859" name="l00859"></a><span class="lineno"> 859</span> <span class="comment">/* determine pruned column length */</span></div>
<div class="line"><a id="l00860" name="l00860"></a><span class="lineno"> 860</span> col_length = (IndexType) (new_cp - &A [Col [c].start]) ;</div>
<div class="line"><a id="l00861" name="l00861"></a><span class="lineno"> 861</span> <span class="keywordflow">if</span> (col_length == 0)</div>
<div class="line"><a id="l00862" name="l00862"></a><span class="lineno"> 862</span> {</div>
<div class="line"><a id="l00863" name="l00863"></a><span class="lineno"> 863</span> <span class="comment">/* a newly-made null column (all rows in this col are "dense" */</span></div>
<div class="line"><a id="l00864" name="l00864"></a><span class="lineno"> 864</span> <span class="comment">/* and have already been killed) */</span></div>
<div class="line"><a id="l00865" name="l00865"></a><span class="lineno"> 865</span> COLAMD_DEBUG2 ((<span class="stringliteral">"Newly null killed: %d\n"</span>, c)) ;</div>
<div class="line"><a id="l00866" name="l00866"></a><span class="lineno"> 866</span> Col [c].shared2.order = --n_col2 ;</div>
<div class="line"><a id="l00867" name="l00867"></a><span class="lineno"> 867</span> Col[c].kill_principal() ;</div>
<div class="line"><a id="l00868" name="l00868"></a><span class="lineno"> 868</span> }</div>
<div class="line"><a id="l00869" name="l00869"></a><span class="lineno"> 869</span> <span class="keywordflow">else</span></div>
<div class="line"><a id="l00870" name="l00870"></a><span class="lineno"> 870</span> {</div>
<div class="line"><a id="l00871" name="l00871"></a><span class="lineno"> 871</span> <span class="comment">/* set column length and set score */</span></div>
<div class="line"><a id="l00872" name="l00872"></a><span class="lineno"> 872</span> COLAMD_ASSERT (score >= 0) ;</div>
<div class="line"><a id="l00873" name="l00873"></a><span class="lineno"> 873</span> COLAMD_ASSERT (score <= n_col) ;</div>
<div class="line"><a id="l00874" name="l00874"></a><span class="lineno"> 874</span> Col [c].length = col_length ;</div>
<div class="line"><a id="l00875" name="l00875"></a><span class="lineno"> 875</span> Col [c].shared2.score = score ;</div>
<div class="line"><a id="l00876" name="l00876"></a><span class="lineno"> 876</span> }</div>
<div class="line"><a id="l00877" name="l00877"></a><span class="lineno"> 877</span> }</div>
<div class="line"><a id="l00878" name="l00878"></a><span class="lineno"> 878</span> COLAMD_DEBUG1 ((<span class="stringliteral">"colamd: Dense, null, and newly-null columns killed: %d\n"</span>,</div>
<div class="line"><a id="l00879" name="l00879"></a><span class="lineno"> 879</span> n_col-n_col2)) ;</div>
<div class="line"><a id="l00880" name="l00880"></a><span class="lineno"> 880</span> </div>
<div class="line"><a id="l00881" name="l00881"></a><span class="lineno"> 881</span> <span class="comment">/* At this point, all empty rows and columns are dead. All live columns */</span></div>
<div class="line"><a id="l00882" name="l00882"></a><span class="lineno"> 882</span> <span class="comment">/* are "clean" (containing no dead rows) and simplicial (no supercolumns */</span></div>
<div class="line"><a id="l00883" name="l00883"></a><span class="lineno"> 883</span> <span class="comment">/* yet). Rows may contain dead columns, but all live rows contain at */</span></div>
<div class="line"><a id="l00884" name="l00884"></a><span class="lineno"> 884</span> <span class="comment">/* least one live column. */</span></div>
<div class="line"><a id="l00885" name="l00885"></a><span class="lineno"> 885</span> </div>
<div class="line"><a id="l00886" name="l00886"></a><span class="lineno"> 886</span> <span class="comment">/* === Initialize degree lists ========================================== */</span></div>
<div class="line"><a id="l00887" name="l00887"></a><span class="lineno"> 887</span> </div>
<div class="line"><a id="l00888" name="l00888"></a><span class="lineno"> 888</span> </div>
<div class="line"><a id="l00889" name="l00889"></a><span class="lineno"> 889</span> <span class="comment">/* clear the hash buckets */</span></div>
<div class="line"><a id="l00890" name="l00890"></a><span class="lineno"> 890</span> <span class="keywordflow">for</span> (c = 0 ; c <= n_col ; c++)</div>
<div class="line"><a id="l00891" name="l00891"></a><span class="lineno"> 891</span> {</div>
<div class="line"><a id="l00892" name="l00892"></a><span class="lineno"> 892</span> head [c] = Empty ;</div>
<div class="line"><a id="l00893" name="l00893"></a><span class="lineno"> 893</span> }</div>
<div class="line"><a id="l00894" name="l00894"></a><span class="lineno"> 894</span> min_score = n_col ;</div>
<div class="line"><a id="l00895" name="l00895"></a><span class="lineno"> 895</span> <span class="comment">/* place in reverse order, so low column indices are at the front */</span></div>
<div class="line"><a id="l00896" name="l00896"></a><span class="lineno"> 896</span> <span class="comment">/* of the lists. This is to encourage natural tie-breaking */</span></div>
<div class="line"><a id="l00897" name="l00897"></a><span class="lineno"> 897</span> <span class="keywordflow">for</span> (c = n_col-1 ; c >= 0 ; c--)</div>
<div class="line"><a id="l00898" name="l00898"></a><span class="lineno"> 898</span> {</div>
<div class="line"><a id="l00899" name="l00899"></a><span class="lineno"> 899</span> <span class="comment">/* only add principal columns to degree lists */</span></div>
<div class="line"><a id="l00900" name="l00900"></a><span class="lineno"> 900</span> <span class="keywordflow">if</span> (Col[c].is_alive())</div>
<div class="line"><a id="l00901" name="l00901"></a><span class="lineno"> 901</span> {</div>
<div class="line"><a id="l00902" name="l00902"></a><span class="lineno"> 902</span> COLAMD_DEBUG4 ((<span class="stringliteral">"place %d score %d minscore %d ncol %d\n"</span>,</div>
<div class="line"><a id="l00903" name="l00903"></a><span class="lineno"> 903</span> c, Col [c].shared2.score, min_score, n_col)) ;</div>
<div class="line"><a id="l00904" name="l00904"></a><span class="lineno"> 904</span> </div>
<div class="line"><a id="l00905" name="l00905"></a><span class="lineno"> 905</span> <span class="comment">/* === Add columns score to DList =============================== */</span></div>
<div class="line"><a id="l00906" name="l00906"></a><span class="lineno"> 906</span> </div>
<div class="line"><a id="l00907" name="l00907"></a><span class="lineno"> 907</span> score = Col [c].shared2.score ;</div>
<div class="line"><a id="l00908" name="l00908"></a><span class="lineno"> 908</span> </div>
<div class="line"><a id="l00909" name="l00909"></a><span class="lineno"> 909</span> COLAMD_ASSERT (min_score >= 0) ;</div>
<div class="line"><a id="l00910" name="l00910"></a><span class="lineno"> 910</span> COLAMD_ASSERT (min_score <= n_col) ;</div>
<div class="line"><a id="l00911" name="l00911"></a><span class="lineno"> 911</span> COLAMD_ASSERT (score >= 0) ;</div>
<div class="line"><a id="l00912" name="l00912"></a><span class="lineno"> 912</span> COLAMD_ASSERT (score <= n_col) ;</div>
<div class="line"><a id="l00913" name="l00913"></a><span class="lineno"> 913</span> COLAMD_ASSERT (head [score] >= Empty) ;</div>
<div class="line"><a id="l00914" name="l00914"></a><span class="lineno"> 914</span> </div>
<div class="line"><a id="l00915" name="l00915"></a><span class="lineno"> 915</span> <span class="comment">/* now add this column to dList at proper score location */</span></div>
<div class="line"><a id="l00916" name="l00916"></a><span class="lineno"> 916</span> next_col = head [score] ;</div>
<div class="line"><a id="l00917" name="l00917"></a><span class="lineno"> 917</span> Col [c].shared3.prev = Empty ;</div>
<div class="line"><a id="l00918" name="l00918"></a><span class="lineno"> 918</span> Col [c].shared4.degree_next = next_col ;</div>
<div class="line"><a id="l00919" name="l00919"></a><span class="lineno"> 919</span> </div>
<div class="line"><a id="l00920" name="l00920"></a><span class="lineno"> 920</span> <span class="comment">/* if there already was a column with the same score, set its */</span></div>
<div class="line"><a id="l00921" name="l00921"></a><span class="lineno"> 921</span> <span class="comment">/* previous pointer to this new column */</span></div>
<div class="line"><a id="l00922" name="l00922"></a><span class="lineno"> 922</span> <span class="keywordflow">if</span> (next_col != Empty)</div>
<div class="line"><a id="l00923" name="l00923"></a><span class="lineno"> 923</span> {</div>
<div class="line"><a id="l00924" name="l00924"></a><span class="lineno"> 924</span> Col [next_col].shared3.prev = c ;</div>
<div class="line"><a id="l00925" name="l00925"></a><span class="lineno"> 925</span> }</div>
<div class="line"><a id="l00926" name="l00926"></a><span class="lineno"> 926</span> head [score] = c ;</div>
<div class="line"><a id="l00927" name="l00927"></a><span class="lineno"> 927</span> </div>
<div class="line"><a id="l00928" name="l00928"></a><span class="lineno"> 928</span> <span class="comment">/* see if this score is less than current min */</span></div>
<div class="line"><a id="l00929" name="l00929"></a><span class="lineno"> 929</span> min_score = numext::mini(min_score, score) ;</div>
<div class="line"><a id="l00930" name="l00930"></a><span class="lineno"> 930</span> </div>
<div class="line"><a id="l00931" name="l00931"></a><span class="lineno"> 931</span> </div>
<div class="line"><a id="l00932" name="l00932"></a><span class="lineno"> 932</span> }</div>
<div class="line"><a id="l00933" name="l00933"></a><span class="lineno"> 933</span> }</div>
<div class="line"><a id="l00934" name="l00934"></a><span class="lineno"> 934</span> </div>
<div class="line"><a id="l00935" name="l00935"></a><span class="lineno"> 935</span> </div>
<div class="line"><a id="l00936" name="l00936"></a><span class="lineno"> 936</span> <span class="comment">/* === Return number of remaining columns, and max row degree =========== */</span></div>
<div class="line"><a id="l00937" name="l00937"></a><span class="lineno"> 937</span> </div>
<div class="line"><a id="l00938" name="l00938"></a><span class="lineno"> 938</span> *p_n_col2 = n_col2 ;</div>
<div class="line"><a id="l00939" name="l00939"></a><span class="lineno"> 939</span> *p_n_row2 = n_row2 ;</div>
<div class="line"><a id="l00940" name="l00940"></a><span class="lineno"> 940</span> *p_max_deg = max_deg ;</div>