Coverage for /usr/lib/python3/dist-packages/sympy/matrices/graph.py: 13%

1from sympy.utilities.iterables import \

2 flatten, connected_components, strongly_connected_components

3from .common import NonSquareMatrixError

6def _connected_components(M):

7 """Returns the list of connected vertices of the graph when

8 a square matrix is viewed as a weighted graph.

10 Examples

11 ========

13 >>> from sympy import Matrix

14 >>> A = Matrix([

15 ... [66, 0, 0, 68, 0, 0, 0, 0, 67],

16 ... [0, 55, 0, 0, 0, 0, 54, 53, 0],

17 ... [0, 0, 0, 0, 1, 2, 0, 0, 0],

18 ... [86, 0, 0, 88, 0, 0, 0, 0, 87],

19 ... [0, 0, 10, 0, 11, 12, 0, 0, 0],

20 ... [0, 0, 20, 0, 21, 22, 0, 0, 0],

21 ... [0, 45, 0, 0, 0, 0, 44, 43, 0],

22 ... [0, 35, 0, 0, 0, 0, 34, 33, 0],

23 ... [76, 0, 0, 78, 0, 0, 0, 0, 77]])

24 >>> A.connected_components()

25 [[0, 3, 8], [1, 6, 7], [2, 4, 5]]

27 Notes

28 =====

30 Even if any symbolic elements of the matrix can be indeterminate

31 to be zero mathematically, this only takes the account of the

32 structural aspect of the matrix, so they will considered to be

33 nonzero.

34 """

35 if not M.is_square:

36 raise NonSquareMatrixError

38 V = range(M.rows)

39 E = sorted(M.todok().keys())

40 return connected_components((V, E))

43def _strongly_connected_components(M):

44 """Returns the list of strongly connected vertices of the graph when

45 a square matrix is viewed as a weighted graph.

47 Examples

48 ========

50 >>> from sympy import Matrix

51 >>> A = Matrix([

52 ... [44, 0, 0, 0, 43, 0, 45, 0, 0],

53 ... [0, 66, 62, 61, 0, 68, 0, 60, 67],

54 ... [0, 0, 22, 21, 0, 0, 0, 20, 0],

55 ... [0, 0, 12, 11, 0, 0, 0, 10, 0],

56 ... [34, 0, 0, 0, 33, 0, 35, 0, 0],

57 ... [0, 86, 82, 81, 0, 88, 0, 80, 87],

58 ... [54, 0, 0, 0, 53, 0, 55, 0, 0],

59 ... [0, 0, 2, 1, 0, 0, 0, 0, 0],

60 ... [0, 76, 72, 71, 0, 78, 0, 70, 77]])

61 >>> A.strongly_connected_components()

62 [[0, 4, 6], [2, 3, 7], [1, 5, 8]]

63 """

64 if not M.is_square:

65 raise NonSquareMatrixError

67 # RepMatrix uses the more efficient DomainMatrix.scc() method

68 rep = getattr(M, '_rep', None)

69 if rep is not None:

70 return rep.scc()

72 V = range(M.rows)

73 E = sorted(M.todok().keys())

74 return strongly_connected_components((V, E))

77def _connected_components_decomposition(M):

78 """Decomposes a square matrix into block diagonal form only

79 using the permutations.

81 Explanation

82 ===========

84 The decomposition is in a form of $A = P^{-1} B P$ where $P$ is a

85 permutation matrix and $B$ is a block diagonal matrix.

87 Returns

88 =======

90 P, B : PermutationMatrix, BlockDiagMatrix

91 *P* is a permutation matrix for the similarity transform

92 as in the explanation. And *B* is the block diagonal matrix of

93 the result of the permutation.

95 If you would like to get the diagonal blocks from the

96 BlockDiagMatrix, see

97 :meth:`~sympy.matrices.expressions.blockmatrix.BlockDiagMatrix.get_diag_blocks`.

99 Examples

100 ========

101

102 >>> from sympy import Matrix, pprint

103 >>> A = Matrix([

104 ... [66, 0, 0, 68, 0, 0, 0, 0, 67],

105 ... [0, 55, 0, 0, 0, 0, 54, 53, 0],

106 ... [0, 0, 0, 0, 1, 2, 0, 0, 0],

107 ... [86, 0, 0, 88, 0, 0, 0, 0, 87],

108 ... [0, 0, 10, 0, 11, 12, 0, 0, 0],

109 ... [0, 0, 20, 0, 21, 22, 0, 0, 0],

110 ... [0, 45, 0, 0, 0, 0, 44, 43, 0],

111 ... [0, 35, 0, 0, 0, 0, 34, 33, 0],

112 ... [76, 0, 0, 78, 0, 0, 0, 0, 77]])

113

114 >>> P, B = A.connected_components_decomposition()

115 >>> pprint(P)

116 PermutationMatrix((1 3)(2 8 5 7 4 6))

117 >>> pprint(B)

118 [[66 68 67] ]

119 [[ ] ]

120 [[86 88 87] 0 0 ]

121 [[ ] ]

122 [[76 78 77] ]

123 [ ]

124 [ [55 54 53] ]

125 [ [ ] ]

126 [ 0 [45 44 43] 0 ]

127 [ [ ] ]

128 [ [35 34 33] ]

129 [ ]

130 [ [0 1 2 ]]

131 [ [ ]]

132 [ 0 0 [10 11 12]]

133 [ [ ]]

134 [ [20 21 22]]

135

136 >>> P = P.as_explicit()

137 >>> B = B.as_explicit()

138 >>> P.T*B*P == A

139 True

140

141 Notes

142 =====

143

144 This problem corresponds to the finding of the connected components

145 of a graph, when a matrix is viewed as a weighted graph.

146 """

147 from sympy.combinatorics.permutations import Permutation

148 from sympy.matrices.expressions.blockmatrix import BlockDiagMatrix

149 from sympy.matrices.expressions.permutation import PermutationMatrix

150

151 iblocks = M.connected_components()

152

153 p = Permutation(flatten(iblocks))

154 P = PermutationMatrix(p)

155

156 blocks = []

157 for b in iblocks:

158 blocks.append(M[b, b])

159 B = BlockDiagMatrix(*blocks)

160 return P, B

161

162

163def _strongly_connected_components_decomposition(M, lower=True):

164 """Decomposes a square matrix into block triangular form only

165 using the permutations.

166

167 Explanation

168 ===========

169

170 The decomposition is in a form of $A = P^{-1} B P$ where $P$ is a

171 permutation matrix and $B$ is a block diagonal matrix.

172

173 Parameters

174 ==========

175

176 lower : bool

177 Makes $B$ lower block triangular when ``True``.

178 Otherwise, makes $B$ upper block triangular.

179

180 Returns

181 =======

182

183 P, B : PermutationMatrix, BlockMatrix

184 *P* is a permutation matrix for the similarity transform

185 as in the explanation. And *B* is the block triangular matrix of

186 the result of the permutation.

187

188 Examples

189 ========

190

191 >>> from sympy import Matrix, pprint

192 >>> A = Matrix([

193 ... [44, 0, 0, 0, 43, 0, 45, 0, 0],

194 ... [0, 66, 62, 61, 0, 68, 0, 60, 67],

195 ... [0, 0, 22, 21, 0, 0, 0, 20, 0],

196 ... [0, 0, 12, 11, 0, 0, 0, 10, 0],

197 ... [34, 0, 0, 0, 33, 0, 35, 0, 0],

198 ... [0, 86, 82, 81, 0, 88, 0, 80, 87],

199 ... [54, 0, 0, 0, 53, 0, 55, 0, 0],

200 ... [0, 0, 2, 1, 0, 0, 0, 0, 0],

201 ... [0, 76, 72, 71, 0, 78, 0, 70, 77]])

202

203 A lower block triangular decomposition:

204

205 >>> P, B = A.strongly_connected_components_decomposition()

206 >>> pprint(P)

207 PermutationMatrix((8)(1 4 3 2 6)(5 7))

208 >>> pprint(B)

209 [[44 43 45] [0 0 0] [0 0 0] ]

210 [[ ] [ ] [ ] ]

211 [[34 33 35] [0 0 0] [0 0 0] ]

212 [[ ] [ ] [ ] ]

213 [[54 53 55] [0 0 0] [0 0 0] ]

214 [ ]

215 [ [0 0 0] [22 21 20] [0 0 0] ]

216 [ [ ] [ ] [ ] ]

217 [ [0 0 0] [12 11 10] [0 0 0] ]

218 [ [ ] [ ] [ ] ]

219 [ [0 0 0] [2 1 0 ] [0 0 0] ]

220 [ ]

221 [ [0 0 0] [62 61 60] [66 68 67]]

222 [ [ ] [ ] [ ]]

223 [ [0 0 0] [82 81 80] [86 88 87]]

224 [ [ ] [ ] [ ]]

225 [ [0 0 0] [72 71 70] [76 78 77]]

226

227 >>> P = P.as_explicit()

228 >>> B = B.as_explicit()

229 >>> P.T * B * P == A

230 True

231

232 An upper block triangular decomposition:

233

234 >>> P, B = A.strongly_connected_components_decomposition(lower=False)

235 >>> pprint(P)

236 PermutationMatrix((0 1 5 7 4 3 2 8 6))

237 >>> pprint(B)

238 [[66 68 67] [62 61 60] [0 0 0] ]

239 [[ ] [ ] [ ] ]

240 [[86 88 87] [82 81 80] [0 0 0] ]

241 [[ ] [ ] [ ] ]

242 [[76 78 77] [72 71 70] [0 0 0] ]

243 [ ]

244 [ [0 0 0] [22 21 20] [0 0 0] ]

245 [ [ ] [ ] [ ] ]

246 [ [0 0 0] [12 11 10] [0 0 0] ]

247 [ [ ] [ ] [ ] ]

248 [ [0 0 0] [2 1 0 ] [0 0 0] ]

249 [ ]

250 [ [0 0 0] [0 0 0] [44 43 45]]

251 [ [ ] [ ] [ ]]

252 [ [0 0 0] [0 0 0] [34 33 35]]

253 [ [ ] [ ] [ ]]

254 [ [0 0 0] [0 0 0] [54 53 55]]

255

256 >>> P = P.as_explicit()

257 >>> B = B.as_explicit()

258 >>> P.T * B * P == A

259 True

260 """

261 from sympy.combinatorics.permutations import Permutation

262 from sympy.matrices.expressions.blockmatrix import BlockMatrix

263 from sympy.matrices.expressions.permutation import PermutationMatrix

264

265 iblocks = M.strongly_connected_components()

266 if not lower:

267 iblocks = list(reversed(iblocks))

268

269 p = Permutation(flatten(iblocks))

270 P = PermutationMatrix(p)

271

272 rows = []

273 for a in iblocks:

274 cols = []

275 for b in iblocks:

276 cols.append(M[a, b])

277 rows.append(cols)

278 B = BlockMatrix(rows)

279 return P, B