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