bool_mat.h

Get and set the entry in row $i$ and column $j$. The value $x$ must be 0 or 1. Indices are not checked.

Initialises mat as the $r \times c$ zero matrix. No memory is allocated if $r$ or $c$ is zero.

Frees the memory used by mat.

Swaps the two matrices, including their dimensions, in constant time.

Copies src to dest, which must have the same dimensions.

Set mat to the zero matrix, or to the matrix with ones on the main diagonal and zeros elsewhere (also for non-square matrices).

Set the square matrix $A$ of order $n$ to the adjacency matrix of the directed path $0 \to 1 \to \cdots \to n - 1$, with $A_{ij} = 1$ exactly when $j = i + 1$, or of the directed cycle, with $A_{ij} = 1$ exactly when $j \equiv i + 1 \pmod n$. Throw an exception if $A$ is not square.

Set mat to a random matrix, or to a random matrix that is zero off the main diagonal. A density between 0 and 1 is chosen at random, and each entry (each diagonal entry) is 1 with that probability.

Sets the square, nonempty matrix mat to a random nilpotent matrix: a random strictly lower triangular matrix with rows and columns permuted by a common random permutation, that is, the adjacency matrix of a random directed acyclic graph. Throws an exception if mat is not square or is empty.

Print the matrix to standard output or to file, one row per line in the form [1, 0, 1].

Returns 1 if the matrices have the same dimensions and the same entries, and 0 otherwise.

Return 1 if some entry, respectively every entry, of mat is 1, and 0 otherwise. For an empty matrix bool_mat_any returns 0 and bool_mat_all returns 1.

Return 1 if mat has zero rows or zero columns, respectively the same number of rows and columns, and 0 otherwise.

Return 1 if $A_{ij} = 0$ for all $i \ne j$, respectively for all $i < j$, and 0 otherwise. The matrix need not be square.

Returns 1 if $A_{ij} \wedge A_{jk} \implies A_{ik}$ for all $i, j, k$, that is, if $A^2 \le A$ entrywise, and 0 otherwise. Requires a square matrix; uses $O(n^3)$ operations.

Returns 1 if some power $A^k$ with $k \ge 1$ is zero, that is, if the graph of $A$ has no cycles (including loops $A_{ii} = 1$), and 0 otherwise. Uses a depth-first search for cycles, in $O(n^2)$ operations. Throws an exception if $A$ is not square. For an empty matrix it returns 0.

Sets dest to the transpose of src. Throws an exception if the dimensions of dest are not those of the transpose.

Sets $B$ to the entrywise negation of $A$: $B_{ij} = \neg A_{ij}$.

Sets res to the sum of the two matrices, the entrywise or.

Sets res to the entrywise product of the two matrices, the entrywise and. Throws an exception if the input dimensions differ.

Set res to the matrix product, $\mathit{res}_{ij} = \bigvee_k (\mathit{mat1}_{ik} \wedge \mathit{mat2}_{kj})$, and $B$ to $A^2$. The product is computed by the classical algorithm with early exit, in $O(rck)$ operations. Throws an exception if the dimensions are incompatible.

Sets $B$ to $A^{\mathit{exp}}$ by binary exponentiation, with $A^0$ the identity matrix. Throws an exception if $A$ is not square.

Returns the trace of the square matrix in the Boolean semiring: 1 if some diagonal entry is 1, and 0 otherwise (also for an empty matrix). Throws an exception if the matrix is not square.

Sets $B$ to the transitive closure $A + A^2 + A^3 + \cdots$ of $A$: $B_{ij} = 1$ if and only if there is a walk of positive length from $i$ to $j$. Uses Warshall's algorithm [War1962], in $O(n^3)$ operations.

Computes the strongly connected components of the graph of $A$ and returns their number $k$. Sets $p_i$, for each vertex $i$, to the index in $\{0, \ldots, k - 1\}$ of the component containing $i$. The components form a directed acyclic graph, and they are numbered in postorder with respect to it: if there is an edge from a vertex of component $a$ to a vertex of a different component $b$, then $a > b$. Uses Tarjan's algorithm [Tar1972], in $O(n^2)$ operations.

Returns the nilpotency degree of $A$, the smallest $k \ge 1$ with $A^k = 0$, or $-1$ if $A$ is not nilpotent. For an empty matrix it returns 0. For a nilpotent matrix the degree is one more than the length of the longest path in the graph, which is computed by a topological sort.

Sets $B_{ij}$ to the length of the longest walk from vertex $i$ to vertex $j$ in the graph of $A$, where the empty walk from a vertex to itself has length 0. $B_{ij} = -1$ if there is no walk from $i$ to $j$, and $B_{ij} = -2$ if there are arbitrarily long walks (a walk from $i$ to $j$ through a cycle). The matrix $B$ must be $n \times n$.

Returns $-2$ if some entry of $B$ is $-2$, and otherwise the largest entry of $B$, which is one less than bool_mat_nilpotency_degree; for an empty matrix it returns $-1$.