csReach.js (1801B)
1 "use strict"; 2 3 Object.defineProperty(exports, "__esModule", { 4 value: true 5 }); 6 exports.csReach = csReach; 7 8 var _csMarked = require("./csMarked.js"); 9 10 var _csMark = require("./csMark.js"); 11 12 var _csDfs = require("./csDfs.js"); 13 14 /** 15 * The csReach function computes X = Reach(B), where B is the nonzero pattern of the n-by-1 16 * sparse column of vector b. The function returns the set of nodes reachable from any node in B. The 17 * nonzero pattern xi of the solution x to the sparse linear system Lx=b is given by X=Reach(B). 18 * 19 * @param {Matrix} g The G matrix 20 * @param {Matrix} b The B matrix 21 * @param {Number} k The kth column in B 22 * @param {Array} xi The nonzero pattern xi[top] .. xi[n - 1], an array of size = 2 * n 23 * The first n entries is the nonzero pattern, the last n entries is the stack 24 * @param {Array} pinv The inverse row permutation vector 25 * 26 * @return {Number} The index for the nonzero pattern 27 * 28 * Reference: http://faculty.cse.tamu.edu/davis/publications.html 29 */ 30 function csReach(g, b, k, xi, pinv) { 31 // g arrays 32 var gptr = g._ptr; 33 var gsize = g._size; // b arrays 34 35 var bindex = b._index; 36 var bptr = b._ptr; // columns 37 38 var n = gsize[1]; // vars 39 40 var p, p0, p1; // initialize top 41 42 var top = n; // loop column indeces in B 43 44 for (p0 = bptr[k], p1 = bptr[k + 1], p = p0; p < p1; p++) { 45 // node i 46 var i = bindex[p]; // check node i is marked 47 48 if (!(0, _csMarked.csMarked)(gptr, i)) { 49 // start a dfs at unmarked node i 50 top = (0, _csDfs.csDfs)(i, g, top, xi, pinv); 51 } 52 } // loop columns from top -> n - 1 53 54 55 for (p = top; p < n; p++) { 56 // restore G 57 (0, _csMark.csMark)(gptr, xi[p]); 58 } 59 60 return top; 61 }