CMR
1.3.0

Let \( G = (V,E) \) be a graph and let \( T \) be a spanning forest. The matrix \( M(G,T) \in \{0,1\}^{T \times (E \setminus T)} \) defined via
\[ M(G,T)_{e,f} := \begin{cases} 1 & \text{if } e \text{ is contained in the unique cycle of } T \cup \{f\} \\ 0 & \text{otherwise} \end{cases} \]
is called the graphic matrix of \( G \) with respect to \( T \). A binary matrix \( M \) is called graphic if there exists a graph \( G \) with a spanning forest \( T \) such that \( M = M(G,T) \). Moreover, \( M \) is called cographic if \( M^{\textsf{T}} \) is graphic, and it is called planar if it is graphic and cographic.
The command
cmrgraphic INMAT [OPTION]...
determines whether the matrix given in file INMAT
is (co)graphic.
Options:
i FORMAT
Format of file INMAT
; default: dense.t
Test for being cographic; default: test for being graphic.G OUTGRAPH
Write a graph to file OUTGRAPH
; default: skip computation.T OUTTREE
Write a spanning tree to file OUTTREE
; default: skip computation.D OUTDOT
Write a dot file OUTDOT
with the graph and the spanning tree; default: skip computation.N NONSUB
Write a minimal non(co)graphic submatrix to file NONSUB
; default: skip computation.Advanced options:
stats
Print statistics about the computation to stderr.timelimit LIMIT
Allow at most LIMIT
seconds for the computation.Formats for matrices: dense, sparse If INMAT
is 
then the matrix is read from stdin. If OUTGRAPH
, OUTTREE
, OUTDOT
or NONSUB
is 
then the graph (resp. the tree, dot file or non(co)graphic submatrix) is written to stdout.
The implemented recognition algorithm is based on An Almost LinearTime Algorithm for Graph Realization by Robert E. Bixby and Donald K. Wagner (Mathematics of Operations Research, 1988). For a matrix \( M \in \{0,1\}^{m \times n}\) with \( k \) nonzeros it runs in \( \mathcal{O}( k \cdot \alpha(k, m) ) \) time, where \( \alpha(\cdot) \) denotes the inverse Ackerman function.
The corresponding functions in the library are
and are defined in network.h.
The command
cmrgraphic c INGRAPH OUTMAT [OPTION]...
computes a (co)graphic matrix corresponding to the graph from file INGRAPH
and writes it to OUTMAT
.
Options:
o FORMAT
Format of file OUTMAT
; default: dense.t
Return the transpose of the graphic matrix.T INTREE
Read a tree from file INTREE
; default: use first specified arcs as tree edges.Advanced options:
stats
Print statistics about the computation to stderr.timelimit LIMIT
Allow at most LIMIT
seconds for the computation.Formats for matrices: dense, sparse If INGRAPH
or INTREE
is 
then the graph (resp. tree) is read from stdin. If OUTMAT
is 
then the matrix is written to stdout.
The corresponding function in the library is
and is defined in network.h.