csEtree.js (1719B)
1 "use strict"; 2 3 Object.defineProperty(exports, "__esModule", { 4 value: true 5 }); 6 exports.csEtree = csEtree; 7 8 /** 9 * Computes the elimination tree of Matrix A (using triu(A)) or the 10 * elimination tree of A'A without forming A'A. 11 * 12 * @param {Matrix} a The A Matrix 13 * @param {boolean} ata A value of true the function computes the etree of A'A 14 * 15 * Reference: http://faculty.cse.tamu.edu/davis/publications.html 16 */ 17 function csEtree(a, ata) { 18 // check inputs 19 if (!a) { 20 return null; 21 } // a arrays 22 23 24 var aindex = a._index; 25 var aptr = a._ptr; 26 var asize = a._size; // rows & columns 27 28 var m = asize[0]; 29 var n = asize[1]; // allocate result 30 31 var parent = []; // (n) 32 // allocate workspace 33 34 var w = []; // (n + (ata ? m : 0)) 35 36 var ancestor = 0; // first n entries in w 37 38 var prev = n; // last m entries (ata = true) 39 40 var i, inext; // check we are calculating A'A 41 42 if (ata) { 43 // initialize workspace 44 for (i = 0; i < m; i++) { 45 w[prev + i] = -1; 46 } 47 } // loop columns 48 49 50 for (var k = 0; k < n; k++) { 51 // node k has no parent yet 52 parent[k] = -1; // nor does k have an ancestor 53 54 w[ancestor + k] = -1; // values in column k 55 56 for (var p0 = aptr[k], p1 = aptr[k + 1], p = p0; p < p1; p++) { 57 // row 58 var r = aindex[p]; // node 59 60 i = ata ? w[prev + r] : r; // traverse from i to k 61 62 for (; i !== -1 && i < k; i = inext) { 63 // inext = ancestor of i 64 inext = w[ancestor + i]; // path compression 65 66 w[ancestor + i] = k; // check no anc., parent is k 67 68 if (inext === -1) { 69 parent[i] = k; 70 } 71 } 72 73 if (ata) { 74 w[prev + r] = k; 75 } 76 } 77 } 78 79 return parent; 80 }