| 140 | } |
| 141 | |
| 142 | BitMatrix *TransitiveClosure(BitMatrix *mat) { |
| 143 | // Floyd-Warshall algorithm |
| 144 | require(IsMatrix(mat), "not a proper matrix"); |
| 145 | Int rows = mat->len(); |
| 146 | if (rows == 0) |
| 147 | return MakeBitMatrix(0, 0); |
| 148 | Int cols = mat->at(0)->len(); |
| 149 | require(mat->len() == mat->at(0)->len(), "not a square matrix"); |
| 150 | mat = Clone(mat); |
| 151 | for (Int col = 0; col < cols; col++) { |
| 152 | for (Int row = 0; row < rows; row++) { |
| 153 | if (mat->at(row)->test(col)) { |
| 154 | mat->at(row)->union_in_place(mat->at(col)); |
| 155 | } |
| 156 | } |
| 157 | } |
| 158 | return mat; |
| 159 | } |