Coverage for /usr/lib/python3/dist-packages/scipy/sparse/_csr.py: 27%

1"""Compressed Sparse Row matrix format""" 

2 

3__docformat__ = "restructuredtext en" 

4 

5__all__ = ['csr_array', 'csr_matrix', 'isspmatrix_csr'] 

6 

7import numpy as np 

8 

9from ._matrix import spmatrix, _array_doc_to_matrix 

10from ._base import _spbase, sparray 

11from ._sparsetools import (csr_tocsc, csr_tobsr, csr_count_blocks, 

12 get_csr_submatrix) 

13from ._sputils import upcast 

14 

15from ._compressed import _cs_matrix 

16 

17 

18class _csr_base(_cs_matrix): 

19 """ 

20 Compressed Sparse Row matrix 

21 

22 This can be instantiated in several ways: 

23 csr_array(D) 

24 with a dense matrix or rank-2 ndarray D 

25 

26 csr_array(S) 

27 with another sparse matrix S (equivalent to S.tocsr()) 

28 

29 csr_array((M, N), [dtype]) 

30 to construct an empty matrix with shape (M, N) 

31 dtype is optional, defaulting to dtype='d'. 

32 

33 csr_array((data, (row_ind, col_ind)), [shape=(M, N)]) 

34 where ``data``, ``row_ind`` and ``col_ind`` satisfy the 

35 relationship ``a[row_ind[k], col_ind[k]] = data[k]``. 

36 

37 csr_array((data, indices, indptr), [shape=(M, N)]) 

38 is the standard CSR representation where the column indices for 

39 row i are stored in ``indices[indptr[i]:indptr[i+1]]`` and their 

40 corresponding values are stored in ``data[indptr[i]:indptr[i+1]]``. 

41 If the shape parameter is not supplied, the matrix dimensions 

42 are inferred from the index arrays. 

43 

44 Attributes 

45 ---------- 

46 dtype : dtype 

47 Data type of the matrix 

48 shape : 2-tuple 

49 Shape of the matrix 

50 ndim : int 

51 Number of dimensions (this is always 2) 

52 nnz 

53 Number of stored values, including explicit zeros 

54 data 

55 CSR format data array of the matrix 

56 indices 

57 CSR format index array of the matrix 

58 indptr 

59 CSR format index pointer array of the matrix 

60 has_sorted_indices 

61 Whether indices are sorted 

62 

63 Notes 

64 ----- 

65 

66 Sparse matrices can be used in arithmetic operations: they support 

67 addition, subtraction, multiplication, division, and matrix power. 

68 

69 Advantages of the CSR format 

70 - efficient arithmetic operations CSR + CSR, CSR * CSR, etc. 

71 - efficient row slicing 

72 - fast matrix vector products 

73 

74 Disadvantages of the CSR format 

75 - slow column slicing operations (consider CSC) 

76 - changes to the sparsity structure are expensive (consider LIL or DOK) 

77 

78 Canonical Format 

79 - Within each row, indices are sorted by column. 

80 - There are no duplicate entries. 

81 

82 Examples 

83 -------- 

84 

85 >>> import numpy as np 

86 >>> from scipy.sparse import csr_array 

87 >>> csr_array((3, 4), dtype=np.int8).toarray() 

88 array([[0, 0, 0, 0], 

89 [0, 0, 0, 0], 

90 [0, 0, 0, 0]], dtype=int8) 

91 

92 >>> row = np.array([0, 0, 1, 2, 2, 2]) 

93 >>> col = np.array([0, 2, 2, 0, 1, 2]) 

94 >>> data = np.array([1, 2, 3, 4, 5, 6]) 

95 >>> csr_array((data, (row, col)), shape=(3, 3)).toarray() 

96 array([[1, 0, 2], 

97 [0, 0, 3], 

98 [4, 5, 6]]) 

99 

100 >>> indptr = np.array([0, 2, 3, 6]) 

101 >>> indices = np.array([0, 2, 2, 0, 1, 2]) 

102 >>> data = np.array([1, 2, 3, 4, 5, 6]) 

103 >>> csr_array((data, indices, indptr), shape=(3, 3)).toarray() 

104 array([[1, 0, 2], 

105 [0, 0, 3], 

106 [4, 5, 6]]) 

107 

108 Duplicate entries are summed together: 

109 

110 >>> row = np.array([0, 1, 2, 0]) 

111 >>> col = np.array([0, 1, 1, 0]) 

112 >>> data = np.array([1, 2, 4, 8]) 

113 >>> csr_array((data, (row, col)), shape=(3, 3)).toarray() 

114 array([[9, 0, 0], 

115 [0, 2, 0], 

116 [0, 4, 0]]) 

117 

118 As an example of how to construct a CSR matrix incrementally, 

119 the following snippet builds a term-document matrix from texts: 

120 

121 >>> docs = [["hello", "world", "hello"], ["goodbye", "cruel", "world"]] 

122 >>> indptr = [0] 

123 >>> indices = [] 

124 >>> data = [] 

125 >>> vocabulary = {} 

126 >>> for d in docs: 

127 ... for term in d: 

128 ... index = vocabulary.setdefault(term, len(vocabulary)) 

129 ... indices.append(index) 

130 ... data.append(1) 

131 ... indptr.append(len(indices)) 

132 ... 

133 >>> csr_array((data, indices, indptr), dtype=int).toarray() 

134 array([[2, 1, 0, 0], 

135 [0, 1, 1, 1]]) 

136 

137 """ 

138 _format = 'csr' 

139 

140 def transpose(self, axes=None, copy=False): 

141 if axes is not None: 

142 raise ValueError("Sparse matrices do not support " 

143 "an 'axes' parameter because swapping " 

144 "dimensions is the only logical permutation.") 

145 

146 M, N = self.shape 

147 return self._csc_container((self.data, self.indices, 

148 self.indptr), shape=(N, M), copy=copy) 

149 

150 transpose.__doc__ = _spbase.transpose.__doc__ 

151 

152 def tolil(self, copy=False): 

153 lil = self._lil_container(self.shape, dtype=self.dtype) 

154 

155 self.sum_duplicates() 

156 ptr,ind,dat = self.indptr,self.indices,self.data 

157 rows, data = lil.rows, lil.data 

158 

159 for n in range(self.shape[0]): 

160 start = ptr[n] 

161 end = ptr[n+1] 

162 rows[n] = ind[start:end].tolist() 

163 data[n] = dat[start:end].tolist() 

164 

165 return lil 

166 

167 tolil.__doc__ = _spbase.tolil.__doc__ 

168 

169 def tocsr(self, copy=False): 

170 if copy: 

171 return self.copy() 

172 else: 

173 return self 

174 

175 tocsr.__doc__ = _spbase.tocsr.__doc__ 

176 

177 def tocsc(self, copy=False): 

178 idx_dtype = self._get_index_dtype((self.indptr, self.indices), 

179 maxval=max(self.nnz, self.shape[0])) 

180 indptr = np.empty(self.shape[1] + 1, dtype=idx_dtype) 

181 indices = np.empty(self.nnz, dtype=idx_dtype) 

182 data = np.empty(self.nnz, dtype=upcast(self.dtype)) 

183 

184 csr_tocsc(self.shape[0], self.shape[1], 

185 self.indptr.astype(idx_dtype), 

186 self.indices.astype(idx_dtype), 

187 self.data, 

188 indptr, 

189 indices, 

190 data) 

191 

192 A = self._csc_container((data, indices, indptr), shape=self.shape) 

193 A.has_sorted_indices = True 

194 return A 

195 

196 tocsc.__doc__ = _spbase.tocsc.__doc__ 

197 

198 def tobsr(self, blocksize=None, copy=True): 

199 if blocksize is None: 

200 from ._spfuncs import estimate_blocksize 

201 return self.tobsr(blocksize=estimate_blocksize(self)) 

202 

203 elif blocksize == (1,1): 

204 arg1 = (self.data.reshape(-1,1,1),self.indices,self.indptr) 

205 return self._bsr_container(arg1, shape=self.shape, copy=copy) 

206 

207 else: 

208 R,C = blocksize 

209 M,N = self.shape 

210 

211 if R < 1 or C < 1 or M % R != 0 or N % C != 0: 

212 raise ValueError('invalid blocksize %s' % blocksize) 

213 

214 blks = csr_count_blocks(M,N,R,C,self.indptr,self.indices) 

215 

216 idx_dtype = self._get_index_dtype((self.indptr, self.indices), 

217 maxval=max(N//C, blks)) 

218 indptr = np.empty(M//R+1, dtype=idx_dtype) 

219 indices = np.empty(blks, dtype=idx_dtype) 

220 data = np.zeros((blks,R,C), dtype=self.dtype) 

221 

222 csr_tobsr(M, N, R, C, 

223 self.indptr.astype(idx_dtype), 

224 self.indices.astype(idx_dtype), 

225 self.data, 

226 indptr, indices, data.ravel()) 

227 

228 return self._bsr_container( 

229 (data, indices, indptr), shape=self.shape 

230 ) 

231 

232 tobsr.__doc__ = _spbase.tobsr.__doc__ 

233 

234 # these functions are used by the parent class (_cs_matrix) 

235 # to remove redundancy between csc_matrix and csr_array 

236 def _swap(self, x): 

237 """swap the members of x if this is a column-oriented matrix 

238 """ 

239 return x 

240 

241 def __iter__(self): 

242 indptr = np.zeros(2, dtype=self.indptr.dtype) 

243 shape = (1, self.shape[1]) 

244 i0 = 0 

245 for i1 in self.indptr[1:]: 

246 indptr[1] = i1 - i0 

247 indices = self.indices[i0:i1] 

248 data = self.data[i0:i1] 

249 yield self.__class__( 

250 (data, indices, indptr), shape=shape, copy=True 

251 ) 

252 i0 = i1 

253 

254 def _getrow(self, i): 

255 """Returns a copy of row i of the matrix, as a (1 x n) 

256 CSR matrix (row vector). 

257 """ 

258 M, N = self.shape 

259 i = int(i) 

260 if i < 0: 

261 i += M 

262 if i < 0 or i >= M: 

263 raise IndexError('index (%d) out of range' % i) 

264 indptr, indices, data = get_csr_submatrix( 

265 M, N, self.indptr, self.indices, self.data, i, i + 1, 0, N) 

266 return self.__class__((data, indices, indptr), shape=(1, N), 

267 dtype=self.dtype, copy=False) 

268 

269 def _getcol(self, i): 

270 """Returns a copy of column i of the matrix, as a (m x 1) 

271 CSR matrix (column vector). 

272 """ 

273 M, N = self.shape 

274 i = int(i) 

275 if i < 0: 

276 i += N 

277 if i < 0 or i >= N: 

278 raise IndexError('index (%d) out of range' % i) 

279 indptr, indices, data = get_csr_submatrix( 

280 M, N, self.indptr, self.indices, self.data, 0, M, i, i + 1) 

281 return self.__class__((data, indices, indptr), shape=(M, 1), 

282 dtype=self.dtype, copy=False) 

283 

284 def _get_intXarray(self, row, col): 

285 return self._getrow(row)._minor_index_fancy(col) 

286 

287 def _get_intXslice(self, row, col): 

288 if col.step in (1, None): 

289 return self._get_submatrix(row, col, copy=True) 

290 # TODO: uncomment this once it's faster: 

291 # return self._getrow(row)._minor_slice(col) 

292 

293 M, N = self.shape 

294 start, stop, stride = col.indices(N) 

295 

296 ii, jj = self.indptr[row:row+2] 

297 row_indices = self.indices[ii:jj] 

298 row_data = self.data[ii:jj] 

299 

300 if stride > 0: 

301 ind = (row_indices >= start) & (row_indices < stop) 

302 else: 

303 ind = (row_indices <= start) & (row_indices > stop) 

304 

305 if abs(stride) > 1: 

306 ind &= (row_indices - start) % stride == 0 

307 

308 row_indices = (row_indices[ind] - start) // stride 

309 row_data = row_data[ind] 

310 row_indptr = np.array([0, len(row_indices)]) 

311 

312 if stride < 0: 

313 row_data = row_data[::-1] 

314 row_indices = abs(row_indices[::-1]) 

315 

316 shape = (1, max(0, int(np.ceil(float(stop - start) / stride)))) 

317 return self.__class__((row_data, row_indices, row_indptr), shape=shape, 

318 dtype=self.dtype, copy=False) 

319 

320 def _get_sliceXint(self, row, col): 

321 if row.step in (1, None): 

322 return self._get_submatrix(row, col, copy=True) 

323 return self._major_slice(row)._get_submatrix(minor=col) 

324 

325 def _get_sliceXarray(self, row, col): 

326 return self._major_slice(row)._minor_index_fancy(col) 

327 

328 def _get_arrayXint(self, row, col): 

329 return self._major_index_fancy(row)._get_submatrix(minor=col) 

330 

331 def _get_arrayXslice(self, row, col): 

332 if col.step not in (1, None): 

333 col = np.arange(*col.indices(self.shape[1])) 

334 return self._get_arrayXarray(row, col) 

335 return self._major_index_fancy(row)._get_submatrix(minor=col) 

336 

337 

338def isspmatrix_csr(x): 

339 """Is `x` of csr_matrix type? 

340 

341 Parameters 

342 ---------- 

343 x 

344 object to check for being a csr matrix 

345 

346 Returns 

347 ------- 

348 bool 

349 True if `x` is a csr matrix, False otherwise 

350 

351 Examples 

352 -------- 

353 >>> from scipy.sparse import csr_array, csr_matrix, coo_matrix, isspmatrix_csr 

354 >>> isspmatrix_csr(csr_matrix([[5]])) 

355 True 

356 >>> isspmatrix_csr(csr_array([[5]])) 

357 False 

358 >>> isspmatrix_csr(coo_matrix([[5]])) 

359 False 

360 """ 

361 return isinstance(x, csr_matrix) 

362 

363 

364# This namespace class separates array from matrix with isinstance 

365class csr_array(_csr_base, sparray): 

366 pass 

367 

368csr_array.__doc__ = _csr_base.__doc__ 

369 

370class csr_matrix(spmatrix, _csr_base): 

371 pass 

372 

373csr_matrix.__doc__ = _array_doc_to_matrix(_csr_base.__doc__)