array_op.h 11.3 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

namespace dgl {
namespace aten {
namespace impl {

19
20
template <DGLDeviceType XPU, typename IdType>
IdArray Full(IdType val, int64_t length, DGLContext ctx);
21

22
23
template <DGLDeviceType XPU, typename IdType>
IdArray Range(IdType low, IdType high, DGLContext ctx);
24

25
template <DGLDeviceType XPU, typename IdType>
26
27
IdArray AsNumBits(IdArray arr, uint8_t bits);

28
template <DGLDeviceType XPU, typename IdType, typename Op>
29
30
IdArray BinaryElewise(IdArray lhs, IdArray rhs);

31
template <DGLDeviceType XPU, typename IdType, typename Op>
32
33
IdArray BinaryElewise(IdArray lhs, IdType rhs);

34
template <DGLDeviceType XPU, typename IdType, typename Op>
35
36
IdArray BinaryElewise(IdType lhs, IdArray rhs);

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

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

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

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

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

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

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

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

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

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

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

70
template <DGLDeviceType XPU, typename DType, typename IdType>
71
72
std::pair<NDArray, IdArray> ConcatSlices(NDArray array, IdArray lengths);

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

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

79
80
// sparse arrays

81
template <DGLDeviceType XPU, typename IdType>
82
83
bool CSRIsNonZero(CSRMatrix csr, int64_t row, int64_t col);

84
template <DGLDeviceType XPU, typename IdType>
85
86
runtime::NDArray CSRIsNonZero(CSRMatrix csr, runtime::NDArray row, runtime::NDArray col);

87
template <DGLDeviceType XPU, typename IdType>
88
89
bool CSRHasDuplicate(CSRMatrix csr);

90
template <DGLDeviceType XPU, typename IdType>
91
92
int64_t CSRGetRowNNZ(CSRMatrix csr, int64_t row);

93
template <DGLDeviceType XPU, typename IdType>
94
95
runtime::NDArray CSRGetRowNNZ(CSRMatrix csr, runtime::NDArray row);

96
template <DGLDeviceType XPU, typename IdType>
97
98
runtime::NDArray CSRGetRowColumnIndices(CSRMatrix csr, int64_t row);

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

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

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

110
template <DGLDeviceType XPU, typename IdType, typename DType>
111
112
113
114
115
116
runtime::NDArray CSRGetData(
    CSRMatrix csr, runtime::NDArray rows, runtime::NDArray cols,
    runtime::NDArray weights, DType filler) {
  return CSRGetData<XPU, IdType, DType>(csr, rows, cols, false, weights, filler);
}

117
template <DGLDeviceType XPU, typename IdType>
118
NDArray CSRGetData(CSRMatrix csr, NDArray rows, NDArray cols) {
119
  return CSRGetData<XPU, IdType, IdType>(csr, rows, cols, true, NullArray(rows->dtype), -1);
120
}
121

122
template <DGLDeviceType XPU, typename IdType>
123
124
125
std::vector<runtime::NDArray> CSRGetDataAndIndices(
    CSRMatrix csr, runtime::NDArray rows, runtime::NDArray cols);

126
template <DGLDeviceType XPU, typename IdType>
127
128
129
CSRMatrix CSRTranspose(CSRMatrix csr);

// Convert CSR to COO
130
template <DGLDeviceType XPU, typename IdType>
131
132
133
COOMatrix CSRToCOO(CSRMatrix csr);

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

137
template <DGLDeviceType XPU, typename IdType>
138
139
CSRMatrix CSRSliceRows(CSRMatrix csr, int64_t start, int64_t end);

140
template <DGLDeviceType XPU, typename IdType>
141
142
CSRMatrix CSRSliceRows(CSRMatrix csr, runtime::NDArray rows);

143
template <DGLDeviceType XPU, typename IdType>
144
145
CSRMatrix CSRSliceMatrix(CSRMatrix csr, runtime::NDArray rows, runtime::NDArray cols);

146
template <DGLDeviceType XPU, typename IdType>
147
148
void CSRSort_(CSRMatrix* csr);

149
template <DGLDeviceType XPU, typename IdType, typename TagType>
150
151
152
std::pair<CSRMatrix, NDArray> CSRSortByTag(
    const CSRMatrix &csr, IdArray tag_array, int64_t num_tags);

153
template <DGLDeviceType XPU, typename IdType>
Da Zheng's avatar
Da Zheng committed
154
155
CSRMatrix CSRReorder(CSRMatrix csr, runtime::NDArray new_row_ids, runtime::NDArray new_col_ids);

156
template <DGLDeviceType XPU, typename IdType>
Da Zheng's avatar
Da Zheng committed
157
158
COOMatrix COOReorder(COOMatrix coo, runtime::NDArray new_row_ids, runtime::NDArray new_col_ids);

159
template <DGLDeviceType XPU, typename IdType>
160
161
CSRMatrix CSRRemove(CSRMatrix csr, IdArray entries);

162
// FloatType is the type of probability data.
163
template <DGLDeviceType XPU, typename IdType, typename FloatType>
164
165
166
COOMatrix CSRRowWiseSampling(
    CSRMatrix mat, IdArray rows, int64_t num_samples, FloatArray prob, bool replace);

167
// FloatType is the type of probability data.
168
template <DGLDeviceType XPU, typename IdType, typename FloatType>
169
170
COOMatrix CSRRowWisePerEtypeSampling(
    CSRMatrix mat, IdArray rows, IdArray etypes,
171
172
    const std::vector<int64_t>& num_samples, FloatArray prob, bool replace,
    bool etype_sorted);
173

174
template <DGLDeviceType XPU, typename IdType>
175
176
177
COOMatrix CSRRowWiseSamplingUniform(
    CSRMatrix mat, IdArray rows, int64_t num_samples, bool replace);

178
template <DGLDeviceType XPU, typename IdType>
179
COOMatrix CSRRowWisePerEtypeSamplingUniform(
180
    CSRMatrix mat, IdArray rows, IdArray etypes, const std::vector<int64_t>& num_samples,
181
    bool replace, bool etype_sorted);
182

183
// FloatType is the type of weight data.
184
template <DGLDeviceType XPU, typename IdType, typename DType>
185
COOMatrix CSRRowWiseTopk(
186
    CSRMatrix mat, IdArray rows, int64_t k, NDArray weight, bool ascending);
187

188
template <DGLDeviceType XPU, typename IdType, typename FloatType>
189
190
191
192
193
194
COOMatrix CSRRowWiseSamplingBiased(
    CSRMatrix mat,
    IdArray rows,
    int64_t num_samples,
    NDArray tag_offset,
    FloatArray bias,
195
196
    bool replace);

197
template <DGLDeviceType XPU, typename IdType>
198
199
200
201
202
203
204
std::pair<IdArray, IdArray> CSRGlobalUniformNegativeSampling(
    const CSRMatrix& csr,
    int64_t num_samples,
    int num_trials,
    bool exclude_self_loops,
    bool replace,
    double redundancy);
205

206
// Union CSRMatrixes
207
template <DGLDeviceType XPU, typename IdType>
208
209
CSRMatrix UnionCsr(const std::vector<CSRMatrix>& csrs);

210
template <DGLDeviceType XPU, typename IdType>
211
std::tuple<CSRMatrix, IdArray, IdArray> CSRToSimple(CSRMatrix csr);
212

213
///////////////////////////////////////////////////////////////////////////////////////////
Da Zheng's avatar
Da Zheng committed
214

215
template <DGLDeviceType XPU, typename IdType>
216
217
bool COOIsNonZero(COOMatrix coo, int64_t row, int64_t col);

218
template <DGLDeviceType XPU, typename IdType>
219
220
runtime::NDArray COOIsNonZero(COOMatrix coo, runtime::NDArray row, runtime::NDArray col);

221
template <DGLDeviceType XPU, typename IdType>
222
223
bool COOHasDuplicate(COOMatrix coo);

224
template <DGLDeviceType XPU, typename IdType>
225
226
int64_t COOGetRowNNZ(COOMatrix coo, int64_t row);

227
template <DGLDeviceType XPU, typename IdType>
228
229
runtime::NDArray COOGetRowNNZ(COOMatrix coo, runtime::NDArray row);

230
template <DGLDeviceType XPU, typename IdType>
231
232
233
std::pair<runtime::NDArray, runtime::NDArray>
COOGetRowDataAndIndices(COOMatrix coo, int64_t row);

234
template <DGLDeviceType XPU, typename IdType>
235
236
237
std::vector<runtime::NDArray> COOGetDataAndIndices(
    COOMatrix coo, runtime::NDArray rows, runtime::NDArray cols);

238
template <DGLDeviceType XPU, typename IdType>
239
240
runtime::NDArray COOGetData(COOMatrix mat, runtime::NDArray rows, runtime::NDArray cols);

241
template <DGLDeviceType XPU, typename IdType>
242
243
COOMatrix COOTranspose(COOMatrix coo);

244
template <DGLDeviceType XPU, typename IdType>
245
246
CSRMatrix COOToCSR(COOMatrix coo);

247
template <DGLDeviceType XPU, typename IdType>
248
249
COOMatrix COOSliceRows(COOMatrix coo, int64_t start, int64_t end);

250
template <DGLDeviceType XPU, typename IdType>
251
252
COOMatrix COOSliceRows(COOMatrix coo, runtime::NDArray rows);

253
template <DGLDeviceType XPU, typename IdType>
254
255
COOMatrix COOSliceMatrix(COOMatrix coo, runtime::NDArray rows, runtime::NDArray cols);

256
template <DGLDeviceType XPU, typename IdType>
257
258
std::pair<COOMatrix, IdArray> COOCoalesce(COOMatrix coo);

259
template <DGLDeviceType XPU, typename IdType>
260
261
COOMatrix DisjointUnionCoo(const std::vector<COOMatrix>& coos);

262
template <DGLDeviceType XPU, typename IdType>
263
264
void COOSort_(COOMatrix* mat, bool sort_column);

265
template <DGLDeviceType XPU, typename IdType>
266
std::pair<bool, bool> COOIsSorted(COOMatrix coo);
267

268
template <DGLDeviceType XPU, typename IdType>
269
270
COOMatrix COORemove(COOMatrix coo, IdArray entries);

271
// FloatType is the type of probability data.
272
template <DGLDeviceType XPU, typename IdType, typename FloatType>
273
274
275
COOMatrix COORowWiseSampling(
    COOMatrix mat, IdArray rows, int64_t num_samples, FloatArray prob, bool replace);

276
// FloatType is the type of probability data.
277
template <DGLDeviceType XPU, typename IdType, typename FloatType>
278
279
COOMatrix COORowWisePerEtypeSampling(
    COOMatrix mat, IdArray rows, IdArray etypes,
280
    const std::vector<int64_t>& num_samples, FloatArray prob, bool replace, bool etype_sorted);
281

282
template <DGLDeviceType XPU, typename IdType>
283
284
285
COOMatrix COORowWiseSamplingUniform(
    COOMatrix mat, IdArray rows, int64_t num_samples, bool replace);

286
template <DGLDeviceType XPU, typename IdType>
287
COOMatrix COORowWisePerEtypeSamplingUniform(
288
    COOMatrix mat, IdArray rows, IdArray etypes, const std::vector<int64_t>& num_samples,
289
    bool replace, bool etype_sorted);
290

291
// FloatType is the type of weight data.
292
template <DGLDeviceType XPU, typename IdType, typename FloatType>
293
294
COOMatrix COORowWiseTopk(
    COOMatrix mat, IdArray rows, int64_t k, FloatArray weight, bool ascending);
295

296
297
///////////////////////// Graph Traverse routines //////////////////////////

298
template <DGLDeviceType XPU, typename IdType>
299
300
Frontiers BFSNodesFrontiers(const CSRMatrix& csr, IdArray source);

301
template <DGLDeviceType XPU, typename IdType>
302
303
Frontiers BFSEdgesFrontiers(const CSRMatrix& csr, IdArray source);

304
template <DGLDeviceType XPU, typename IdType>
305
306
Frontiers TopologicalNodesFrontiers(const CSRMatrix& csr);

307
template <DGLDeviceType XPU, typename IdType>
308
309
Frontiers DGLDFSEdges(const CSRMatrix& csr, IdArray source);

310
template <DGLDeviceType XPU, typename IdType>
311
312
313
314
315
316
Frontiers DGLDFSLabeledEdges(const CSRMatrix& csr,
                             IdArray source,
                             const bool has_reverse_edge,
                             const bool has_nontree_edge,
                             const bool return_labels);

317
template <DGLDeviceType XPU, typename IdType>
318
COOMatrix COOLineGraph(const COOMatrix &coo, bool backtracking);
319

320
321
322
323
324
}  // namespace impl
}  // namespace aten
}  // namespace dgl

#endif  // DGL_ARRAY_ARRAY_OP_H_