![]() |
CMR
1.3.0
|
Consider a binary matrix \( M \in \{0,1\}^{m \times n} \). A row complement for row \( i \) is obtained by complementing all entries \( M_{r,c} \) with \( r \neq i \) and \( M_{i,c} = 1 \). A column complement is defined as a row complement on the transpose matrix. A binary matrix \( M \) is complement totally unimodular if all matrices obtainable by successive row- and column complements are totally unimodular. It turns out that all such matrices can be obtained already by at most one row complement and at most one column complement. Hence, complement total unimodularity can be checked by checking \( (m+1) \cdot (n+1) \) matrices for total unimodularity.
The executable cmr-ctu
determines whether a given matrix \( M \) is complement totally unimodular or applies row- or column-complement operations (or both at the same time) to \( M \).
./cmr-ctu [OPTION]... FILE
Options:
-i FORMAT
Format of input FILE; default: dense
.-o FORMAT
Format of output matrices; default: dense
.-r ROW
Perform a row complement operation on \( M \) and do not test for complement total unimodularity.-c COLUMN
Perform a row complement operation on \( M \) and do not test for complement total unimodularity.-n
Output a complement operations that leads tfile:///home/matthias/code/cmr/develop.git/src/main/tu_main.co a non-totally-unimodular matrix (if \( M \) is not complement totally unimodular).-N
Output a complemented matrix that is non-totally-unimodular (if \( M \) is not complement totally unimodular).-s
Print statistics about the computation to stderr.Formats for matrices are dense-matrix and sparse-matrix. If FILE is -
, then the input will be read from stdin. If -r
or -c
(or both) are specified, then \( M \) is not tested for complement total unimodularity.
The functionality is defined in ctu.h. The main functions are: