1 //------------------------------------------------------------------------------
2 // SLIP_LU/slip_reach: compute the set of nodes reachable from an input set
3 //------------------------------------------------------------------------------
4
5 // SLIP_LU: (c) 2019-2020, Chris Lourenco, Jinhao Chen, Erick Moreno-Centeno,
6 // Timothy A. Davis, Texas A&M University. All Rights Reserved. See
7 // SLIP_LU/License for the license.
8
9 //------------------------------------------------------------------------------
10
11 #include "slip_internal.h"
12
13 /* Purpose: This function computes the reach of column k of A on the graph of L
14 * mathematically that is: xi = Reach(A(:,k))_G_L
15 *
16 * This function is derived from CSparse/cs_reach.c
17 */
18
slip_reach(int64_t * top,SLIP_matrix * L,const SLIP_matrix * A,int64_t k,int64_t * xi,const int64_t * pinv)19 void slip_reach // compute the reach of column k of A on the graph of L
20 (
21 int64_t *top,
22 SLIP_matrix* L, // matrix representing graph of L
23 const SLIP_matrix* A, // input matrix
24 int64_t k, // column of A of interest
25 int64_t* xi, // nonzero pattern
26 const int64_t* pinv // row permutation
27 )
28 {
29
30 //--------------------------------------------------------------------------
31 // check inputs
32 //--------------------------------------------------------------------------
33 if (top == NULL) { return ;}
34 // inputs have been checked in slip_ref_triangular_solve
35 int64_t p, n = L->n;
36 *top = n;
37
38 //--------------------------------------------------------------------------
39 // Iterating across number of nonzero in column k
40 //--------------------------------------------------------------------------
41
42 for (p = A->p[k]; p < A->p[k + 1]; p++)
43 {
44 // DFS at unmarked node i
45 if (!SLIP_MARKED(L->p, A->i[p]))
46 {
47 slip_dfs(top, A->i[p], L, xi, xi+n, pinv);
48 }
49 }
50
51 // Restore L
52 for ( p = *top; p < n; p++)
53 {
54 SLIP_MARK(L->p, xi[p]);
55 }
56 }
57
58