array_op.h 9.19 KB
Newer Older
1
2
3
4
5
6
7
8
9
/*!
 *  Copyright (c) 2019 by Contributors
 * \file array/array_op.h
 * \brief Array operator templates
 */
#ifndef DGL_ARRAY_ARRAY_OP_H_
#define DGL_ARRAY_ARRAY_OP_H_

#include <dgl/array.h>
10
#include <dgl/graph_traversal.h>
11
#include <vector>
12
13
#include <tuple>
#include <utility>
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

namespace dgl {
namespace aten {
namespace impl {

template <DLDeviceType XPU, typename IdType>
IdArray Full(IdType val, int64_t length, DLContext ctx);

template <DLDeviceType XPU, typename IdType>
IdArray Range(IdType low, IdType high, DLContext ctx);

template <DLDeviceType XPU, typename IdType>
IdArray AsNumBits(IdArray arr, uint8_t bits);

template <DLDeviceType XPU, typename IdType, typename Op>
IdArray BinaryElewise(IdArray lhs, IdArray rhs);

template <DLDeviceType XPU, typename IdType, typename Op>
IdArray BinaryElewise(IdArray lhs, IdType rhs);

template <DLDeviceType XPU, typename IdType, typename Op>
IdArray BinaryElewise(IdType lhs, IdArray rhs);

37
38
39
template <DLDeviceType XPU, typename IdType, typename Op>
IdArray UnaryElewise(IdArray array);

40
41
template <DLDeviceType XPU, typename DType, typename IdType>
NDArray IndexSelect(NDArray array, IdArray index);
42

43
template <DLDeviceType XPU, typename DType>
44
DType IndexSelect(NDArray array, int64_t index);
45

Jinjing Zhou's avatar
Jinjing Zhou committed
46
47
48
template <DLDeviceType XPU, typename DType>
IdArray NonZero(BoolArray bool_arr);

49
template <DLDeviceType XPU, typename DType>
50
std::pair<IdArray, IdArray> Sort(IdArray array, int num_bits);
51

52
53
54
template <DLDeviceType XPU, typename DType, typename IdType>
NDArray Scatter(NDArray array, IdArray indices);

55
56
57
template <DLDeviceType XPU, typename DType, typename IdType>
void Scatter_(IdArray index, NDArray value, NDArray out);

58
59
60
template <DLDeviceType XPU, typename DType, typename IdType>
NDArray Repeat(NDArray array, IdArray repeats);

61
62
63
template <DLDeviceType XPU, typename IdType>
IdArray Relabel_(const std::vector<IdArray>& arrays);

64
65
66
template <DLDeviceType XPU, typename IdType>
NDArray Concat(const std::vector<IdArray>& arrays);

67
68
69
70
71
72
template <DLDeviceType XPU, typename DType>
std::tuple<NDArray, IdArray, IdArray> Pack(NDArray array, DType pad_value);

template <DLDeviceType XPU, typename DType, typename IdType>
std::pair<NDArray, IdArray> ConcatSlices(NDArray array, IdArray lengths);

73
74
75
template <DLDeviceType XPU, typename IdType>
IdArray CumSum(IdArray array, bool prepend_zero);

76
77
78
template <DLDeviceType XPU, typename IdType>
IdArray NonZero(NDArray array);

79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// sparse arrays

template <DLDeviceType XPU, typename IdType>
bool CSRIsNonZero(CSRMatrix csr, int64_t row, int64_t col);

template <DLDeviceType XPU, typename IdType>
runtime::NDArray CSRIsNonZero(CSRMatrix csr, runtime::NDArray row, runtime::NDArray col);

template <DLDeviceType XPU, typename IdType>
bool CSRHasDuplicate(CSRMatrix csr);

template <DLDeviceType XPU, typename IdType>
int64_t CSRGetRowNNZ(CSRMatrix csr, int64_t row);

template <DLDeviceType XPU, typename IdType>
runtime::NDArray CSRGetRowNNZ(CSRMatrix csr, runtime::NDArray row);

template <DLDeviceType XPU, typename IdType>
runtime::NDArray CSRGetRowColumnIndices(CSRMatrix csr, int64_t row);

99
template <DLDeviceType XPU, typename IdType>
100
101
runtime::NDArray CSRGetRowData(CSRMatrix csr, int64_t row);

102
103
104
template <DLDeviceType XPU, typename IdType>
bool CSRIsSorted(CSRMatrix csr);

105
106
107
108
109
template <DLDeviceType XPU, typename IdType, typename DType>
runtime::NDArray CSRGetData(
    CSRMatrix csr, runtime::NDArray rows, runtime::NDArray cols,
    runtime::NDArray weights, DType filler);

110
template <DLDeviceType XPU, typename IdType>
111
112
113
NDArray CSRGetData(CSRMatrix csr, NDArray rows, NDArray cols) {
  return CSRGetData<XPU, IdType, IdType>(csr, rows, cols, NullArray(rows->dtype), -1);
}
114

115
template <DLDeviceType XPU, typename IdType>
116
117
118
std::vector<runtime::NDArray> CSRGetDataAndIndices(
    CSRMatrix csr, runtime::NDArray rows, runtime::NDArray cols);

119
template <DLDeviceType XPU, typename IdType>
120
121
122
123
124
125
126
127
128
129
CSRMatrix CSRTranspose(CSRMatrix csr);

// Convert CSR to COO
template <DLDeviceType XPU, typename IdType>
COOMatrix CSRToCOO(CSRMatrix csr);

// Convert CSR to COO using data array as order
template <DLDeviceType XPU, typename IdType>
COOMatrix CSRToCOODataAsOrder(CSRMatrix csr);

130
template <DLDeviceType XPU, typename IdType>
131
132
CSRMatrix CSRSliceRows(CSRMatrix csr, int64_t start, int64_t end);

133
template <DLDeviceType XPU, typename IdType>
134
135
CSRMatrix CSRSliceRows(CSRMatrix csr, runtime::NDArray rows);

136
template <DLDeviceType XPU, typename IdType>
137
138
CSRMatrix CSRSliceMatrix(CSRMatrix csr, runtime::NDArray rows, runtime::NDArray cols);

139
140
141
template <DLDeviceType XPU, typename IdType>
void CSRSort_(CSRMatrix* csr);

Da Zheng's avatar
Da Zheng committed
142
143
144
145
146
147
template <DLDeviceType XPU, typename IdType>
CSRMatrix CSRReorder(CSRMatrix csr, runtime::NDArray new_row_ids, runtime::NDArray new_col_ids);

template <DLDeviceType XPU, typename IdType>
COOMatrix COOReorder(COOMatrix coo, runtime::NDArray new_row_ids, runtime::NDArray new_col_ids);

148
149
150
template <DLDeviceType XPU, typename IdType>
CSRMatrix CSRRemove(CSRMatrix csr, IdArray entries);

151
152
153
154
155
156
157
158
159
160
// FloatType is the type of probability data.
template <DLDeviceType XPU, typename IdType, typename FloatType>
COOMatrix CSRRowWiseSampling(
    CSRMatrix mat, IdArray rows, int64_t num_samples, FloatArray prob, bool replace);

template <DLDeviceType XPU, typename IdType>
COOMatrix CSRRowWiseSamplingUniform(
    CSRMatrix mat, IdArray rows, int64_t num_samples, bool replace);

// FloatType is the type of weight data.
161
template <DLDeviceType XPU, typename IdType, typename DType>
162
COOMatrix CSRRowWiseTopk(
163
    CSRMatrix mat, IdArray rows, int64_t k, NDArray weight, bool ascending);
164

165
166
167
168
// Union CSRMatrixes
template <DLDeviceType XPU, typename IdType>
CSRMatrix UnionCsr(const std::vector<CSRMatrix>& csrs);

169
170
template <DLDeviceType XPU, typename IdType>
std::tuple<CSRMatrix, IdArray, IdArray> CSRToSimple(CSRMatrix csr);
171

172
///////////////////////////////////////////////////////////////////////////////////////////
Da Zheng's avatar
Da Zheng committed
173

174
175
176
177
178
179
template <DLDeviceType XPU, typename IdType>
bool COOIsNonZero(COOMatrix coo, int64_t row, int64_t col);

template <DLDeviceType XPU, typename IdType>
runtime::NDArray COOIsNonZero(COOMatrix coo, runtime::NDArray row, runtime::NDArray col);

180
181
182
template <DLDeviceType XPU, typename IdType>
bool COOHasDuplicate(COOMatrix coo);

183
184
185
186
187
188
template <DLDeviceType XPU, typename IdType>
int64_t COOGetRowNNZ(COOMatrix coo, int64_t row);

template <DLDeviceType XPU, typename IdType>
runtime::NDArray COOGetRowNNZ(COOMatrix coo, runtime::NDArray row);

189
template <DLDeviceType XPU, typename IdType>
190
191
192
std::pair<runtime::NDArray, runtime::NDArray>
COOGetRowDataAndIndices(COOMatrix coo, int64_t row);

193
template <DLDeviceType XPU, typename IdType>
194
195
196
std::vector<runtime::NDArray> COOGetDataAndIndices(
    COOMatrix coo, runtime::NDArray rows, runtime::NDArray cols);

197
198
199
template <DLDeviceType XPU, typename IdType>
runtime::NDArray COOGetData(COOMatrix mat, runtime::NDArray rows, runtime::NDArray cols);

200
template <DLDeviceType XPU, typename IdType>
201
202
COOMatrix COOTranspose(COOMatrix coo);

203
template <DLDeviceType XPU, typename IdType>
204
205
CSRMatrix COOToCSR(COOMatrix coo);

206
template <DLDeviceType XPU, typename IdType>
207
208
COOMatrix COOSliceRows(COOMatrix coo, int64_t start, int64_t end);

209
template <DLDeviceType XPU, typename IdType>
210
211
COOMatrix COOSliceRows(COOMatrix coo, runtime::NDArray rows);

212
template <DLDeviceType XPU, typename IdType>
213
214
COOMatrix COOSliceMatrix(COOMatrix coo, runtime::NDArray rows, runtime::NDArray cols);

215
216
217
template <DLDeviceType XPU, typename IdType>
std::pair<COOMatrix, IdArray> COOCoalesce(COOMatrix coo);

218
template <DLDeviceType XPU, typename IdType>
219
220
221
222
void COOSort_(COOMatrix* mat, bool sort_column);

template <DLDeviceType XPU, typename IdType>
std::pair<bool, bool> COOIsSorted(COOMatrix coo);
223

224
225
226
template <DLDeviceType XPU, typename IdType>
COOMatrix COORemove(COOMatrix coo, IdArray entries);

227
228
229
230
231
232
233
234
235
236
237
238
239
// FloatType is the type of probability data.
template <DLDeviceType XPU, typename IdType, typename FloatType>
COOMatrix COORowWiseSampling(
    COOMatrix mat, IdArray rows, int64_t num_samples, FloatArray prob, bool replace);

template <DLDeviceType XPU, typename IdType>
COOMatrix COORowWiseSamplingUniform(
    COOMatrix mat, IdArray rows, int64_t num_samples, bool replace);

// FloatType is the type of weight data.
template <DLDeviceType XPU, typename IdType, typename FloatType>
COOMatrix COORowWiseTopk(
    COOMatrix mat, IdArray rows, int64_t k, FloatArray weight, bool ascending);
240

241
242
///////////////////////// Graph Traverse routines //////////////////////////

243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
template <DLDeviceType XPU, typename IdType>
Frontiers BFSNodesFrontiers(const CSRMatrix& csr, IdArray source);

template <DLDeviceType XPU, typename IdType>
Frontiers BFSEdgesFrontiers(const CSRMatrix& csr, IdArray source);

template <DLDeviceType XPU, typename IdType>
Frontiers TopologicalNodesFrontiers(const CSRMatrix& csr);

template <DLDeviceType XPU, typename IdType>
Frontiers DGLDFSEdges(const CSRMatrix& csr, IdArray source);

template <DLDeviceType XPU, typename IdType>
Frontiers DGLDFSLabeledEdges(const CSRMatrix& csr,
                             IdArray source,
                             const bool has_reverse_edge,
                             const bool has_nontree_edge,
                             const bool return_labels);

262
263
template <DLDeviceType XPU, typename IdType>
COOMatrix COOLineGraph(const COOMatrix &coo, bool backtracking);
264

265
266
267
268
269
}  // namespace impl
}  // namespace aten
}  // namespace dgl

#endif  // DGL_ARRAY_ARRAY_OP_H_