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 command
cmr-ctu IN-MAT [OPTION]...
determines whether the matrix given in file IN-MAT
is complement totally unimodular.
Options:
-i FORMAT
Format of file IN-MAT
, among dense
for dense-matrix and sparse
for sparse-matrix; default: dense.-o FORMAT
Format of file OUT-MAT
, among dense
for dense-matrix and sparse
for sparse-matrix; default: same as for IN-MAT
.-n OUT-OPS
Write complement operations that leads to a non-totally-unimodular matrix to file OUT-OPS
; default: skip computation.-N OUT-MAT
Write a complemented matrix that is non-totally-unimodular to file OUT-MAT
; default: skip computation.-s
Print statistics about the computation to stderr.If IN-MAT
is -
then the matrix is read from stdin. If OUT-OPS
or OUT-MAT
is -
then the list of operations (resp. the matrix) is written to stdout.
The corresponding function in the library is
and is defined in ctu.h.
The command
cmr-ctu IN-MAT OUT-MAT [OPTION]...
applies a sequence of row or column complement operations the matrix given in file IN-MAT
and writes the result to OUT-MAT
.
Options:
-i FORMAT
Format of file IN-MAT
, among dense
for dense-matrix and sparse
for sparse-matrix; default: dense.-o FORMAT
Format of file OUT-MAT
, among dense
for dense-matrix and sparse
for sparse-matrix; default: same as for IN-MAT
.-r ROW
Apply row complement operation to row ROW
.-c COLUMN
Apply column complement operation to column COLUMN
.-s
Print statistics about the computation to stderr.If IN-MAT
is -
then the matrix is read from stdin. If OUT-MAT
is -
then the matrix is written to stdout.
The corresponding function in the library is
and is defined in ctu.h.