basiclu-sys 0.1.2

Rust FFI bindings for BasicLU
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

/*
 * lu_dfs.c
 *
 * Copyright (C) 2016-2018  ERGO-Code
 *
 * Depth first search in a graph
 *
 */

#include "lu_internal.h"

static lu_int 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);

static lu_int 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);


/*
 * lu_dfs() - compute reach(i) in a graph by depth first search
 *
 * @begin, @end, @index define the graph. When end is not NULL, then node j
 * has neighbours index[begin[j]..end[j]-1]. When end is NULL, then the
 * neighbour list is terminated by a negative index.
 *
 * On return xi[newtop..top-1] hold reach(i) in topological order; newtop is
 * the function return value. Nodes that were already marked are excluded from
 * the reach.
 *
 * @pstack is size m workspace (m the number of nodes in the graph); the
 * contents of pstack is undefined on entry/return.
 *
 * @marked is size m array. Node j is marked iff marked[j] == M.
 * On return nodes xi[newtop..top-1] are marked.
 *
 * If node i is marked on entry, the function does nothing.
 *
 */

lu_int 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)
{
    if (marked[i] == M)
        return top;

    return end ?
        dfs_end(i, begin, end, index, top, xi, pstack, marked, M) :
        dfs(i, begin, index, top, xi, pstack, marked, M);
}


/* ==========================================================================
 * dfs_end
 *
 * adapted from T. Davis, CSPARSE
 * ========================================================================== */

static lu_int 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)
{
    lu_int inext, done, p, head = 0;
    assert(marked[i] != M);

    xi[0] = i;
    while (head >= 0)
    {
        i = xi[head];
        if (marked[i] != M)     /* node i has not been visited */
        {
            marked[i] = M;
            pstack[head] = begin[i];
        }
        done = 1;
        /* continue dfs at node i */
        for (p = pstack[head]; p < end[i]; p++)
        {
            inext = index[p];
            if (marked[inext] == M)
                continue;       /* skip visited node */
            pstack[head] = p+1;
            xi[++head] = inext; /* start dfs at node inext */
            done = 0;
            break;
        }
        if (done)               /* node i has no unvisited neighbours */
        {
            head--;
            xi[--top] = i;
        }
    }

    return top;
}


/* ==========================================================================
 * dfs
 *
 * adapted from T. Davis, CSPARSE
 * ========================================================================== */

static lu_int 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)
{
    lu_int inext, done, p, head = 0;
    assert(marked[i] != M);

    xi[0] = i;
    while (head >= 0)
    {
        i = xi[head];
        if (marked[i] != M)     /* node i has not been visited */
        {
            marked[i] = M;
            pstack[head] = begin[i];
        }
        done = 1;
        /* continue dfs at node i */
        for (p = pstack[head]; (inext = index[p]) >= 0; p++)
        {
            if (marked[inext] == M)
                continue;       /* skip visited node */
            pstack[head] = p+1;
            xi[++head] = inext; /* start dfs at node inext */
            done = 0;
            break;
        }
        if (done)               /* node i has no unvisited neighbours */
        {
            head--;
            xi[--top] = i;
        }
    }

    return top;
}