1 /*
2 * lu_dfs.c
3 *
4 * Copyright (C) 2016-2018 ERGO-Code
5 *
6 * Depth first search in a graph
7 *
8 */
9
10 #include "lu_internal.h"
11
12 static lu_int dfs_end(
13 lu_int i, const lu_int *begin, const lu_int *end, const lu_int *index,
14 lu_int top, lu_int *xi, lu_int *pstack, lu_int *marked, const lu_int M);
15
16 static lu_int dfs(
17 lu_int i, const lu_int *begin, const lu_int *index,
18 lu_int top, lu_int *xi, lu_int *pstack, lu_int *marked, const lu_int M);
19
20
21 /*
22 * lu_dfs() - compute reach(i) in a graph by depth first search
23 *
24 * @begin, @end, @index define the graph. When end is not NULL, then node j
25 * has neighbours index[begin[j]..end[j]-1]. When end is NULL, then the
26 * neighbour list is terminated by a negative index.
27 *
28 * On return xi[newtop..top-1] hold reach(i) in topological order; newtop is
29 * the function return value. Nodes that were already marked are excluded from
30 * the reach.
31 *
32 * @pstack is size m workspace (m the number of nodes in the graph); the
33 * contents of pstack is undefined on entry/return.
34 *
35 * @marked is size m array. Node j is marked iff marked[j] == M.
36 * On return nodes xi[newtop..top-1] are marked.
37 *
38 * If node i is marked on entry, the function does nothing.
39 *
40 */
41
lu_dfs(lu_int i,const lu_int * begin,const lu_int * end,const lu_int * index,lu_int top,lu_int * xi,lu_int * pstack,lu_int * marked,const lu_int M)42 lu_int lu_dfs(
43 lu_int i, const lu_int *begin, const lu_int *end, const lu_int *index,
44 lu_int top, lu_int *xi, lu_int *pstack, lu_int *marked, const lu_int M)
45 {
46 if (marked[i] == M)
47 return top;
48
49 return end ?
50 dfs_end(i, begin, end, index, top, xi, pstack, marked, M) :
51 dfs(i, begin, index, top, xi, pstack, marked, M);
52 }
53
54
55 /* ==========================================================================
56 * dfs_end
57 *
58 * adapted from T. Davis, CSPARSE
59 * ========================================================================== */
60
dfs_end(lu_int i,const lu_int * begin,const lu_int * end,const lu_int * index,lu_int top,lu_int * xi,lu_int * pstack,lu_int * marked,const lu_int M)61 static lu_int dfs_end(
62 lu_int i, const lu_int *begin, const lu_int *end, const lu_int *index,
63 lu_int top, lu_int *xi, lu_int *pstack, lu_int *marked, const lu_int M)
64 {
65 lu_int inext, done, p, head = 0;
66 assert(marked[i] != M);
67
68 xi[0] = i;
69 while (head >= 0)
70 {
71 i = xi[head];
72 if (marked[i] != M) /* node i has not been visited */
73 {
74 marked[i] = M;
75 pstack[head] = begin[i];
76 }
77 done = 1;
78 /* continue dfs at node i */
79 for (p = pstack[head]; p < end[i]; p++)
80 {
81 inext = index[p];
82 if (marked[inext] == M)
83 continue; /* skip visited node */
84 pstack[head] = p+1;
85 xi[++head] = inext; /* start dfs at node inext */
86 done = 0;
87 break;
88 }
89 if (done) /* node i has no unvisited neighbours */
90 {
91 head--;
92 xi[--top] = i;
93 }
94 }
95
96 return top;
97 }
98
99
100 /* ==========================================================================
101 * dfs
102 *
103 * adapted from T. Davis, CSPARSE
104 * ========================================================================== */
105
dfs(lu_int i,const lu_int * begin,const lu_int * index,lu_int top,lu_int * xi,lu_int * pstack,lu_int * marked,const lu_int M)106 static lu_int dfs(
107 lu_int i, const lu_int *begin, const lu_int *index,
108 lu_int top, lu_int *xi, lu_int *pstack, lu_int *marked, const lu_int M)
109 {
110 lu_int inext, done, p, head = 0;
111 assert(marked[i] != M);
112
113 xi[0] = i;
114 while (head >= 0)
115 {
116 i = xi[head];
117 if (marked[i] != M) /* node i has not been visited */
118 {
119 marked[i] = M;
120 pstack[head] = begin[i];
121 }
122 done = 1;
123 /* continue dfs at node i */
124 for (p = pstack[head]; (inext = index[p]) >= 0; p++)
125 {
126 if (marked[inext] == M)
127 continue; /* skip visited node */
128 pstack[head] = p+1;
129 xi[++head] = inext; /* start dfs at node inext */
130 done = 0;
131 break;
132 }
133 if (done) /* node i has no unvisited neighbours */
134 {
135 head--;
136 xi[--top] = i;
137 }
138 }
139
140 return top;
141 }
142