csDfs.js (2606B)
1 "use strict"; 2 3 Object.defineProperty(exports, "__esModule", { 4 value: true 5 }); 6 exports.csDfs = csDfs; 7 8 var _csMarked = require("./csMarked.js"); 9 10 var _csMark = require("./csMark.js"); 11 12 var _csUnflip = require("./csUnflip.js"); 13 14 /** 15 * Depth-first search computes the nonzero pattern xi of the directed graph G (Matrix) starting 16 * at nodes in B (see csReach()). 17 * 18 * @param {Number} j The starting node for the DFS algorithm 19 * @param {Matrix} g The G matrix to search, ptr array modified, then restored 20 * @param {Number} top Start index in stack xi[top..n-1] 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, must be null for L * x = b 25 * 26 * @return {Number} New value of top 27 * 28 * Reference: http://faculty.cse.tamu.edu/davis/publications.html 29 */ 30 function csDfs(j, g, top, xi, pinv) { 31 // g arrays 32 var index = g._index; 33 var ptr = g._ptr; 34 var size = g._size; // columns 35 36 var n = size[1]; // vars 37 38 var i, p, p2; // initialize head 39 40 var head = 0; // initialize the recursion stack 41 42 xi[0] = j; // loop 43 44 while (head >= 0) { 45 // get j from the top of the recursion stack 46 j = xi[head]; // apply permutation vector 47 48 var jnew = pinv ? pinv[j] : j; // check node j is marked 49 50 if (!(0, _csMarked.csMarked)(ptr, j)) { 51 // mark node j as visited 52 (0, _csMark.csMark)(ptr, j); // update stack (last n entries in xi) 53 54 xi[n + head] = jnew < 0 ? 0 : (0, _csUnflip.csUnflip)(ptr[jnew]); 55 } // node j done if no unvisited neighbors 56 57 58 var done = 1; // examine all neighbors of j, stack (last n entries in xi) 59 60 for (p = xi[n + head], p2 = jnew < 0 ? 0 : (0, _csUnflip.csUnflip)(ptr[jnew + 1]); p < p2; p++) { 61 // consider neighbor node i 62 i = index[p]; // check we have visited node i, skip it 63 64 if ((0, _csMarked.csMarked)(ptr, i)) { 65 continue; 66 } // pause depth-first search of node j, update stack (last n entries in xi) 67 68 69 xi[n + head] = p; // start dfs at node i 70 71 xi[++head] = i; // node j is not done 72 73 done = 0; // break, to start dfs(i) 74 75 break; 76 } // check depth-first search at node j is done 77 78 79 if (done) { 80 // remove j from the recursion stack 81 head--; // and place in the output stack 82 83 xi[--top] = j; 84 } 85 } 86 87 return top; 88 }