 CMR  1.3.0
Network Matrices

Let $$D = (V,A)$$ be a digraph and let $$T$$ be an (arbitrarily) directed spanning forest of the underlying undirected graph. The matrix $$M(D,T) \in \{-1,0,1\}^{T \times (A \setminus T)}$$ defined via

$M(D,T)_{a,(v,w)} := \begin{cases} +1 & \text{if the unique v-w-path in T passes through a forwardly}, \\ -1 & \text{if the unique v-w-path in T passes through a backwardly}, \\ 0 & \text{otherwise} \end{cases}$

is called the network matrix of $$D$$ with respect to $$T$$. A matrix $$M$$ is called network matrix if there exists a digraph $$D$$ with a directed spanning forest $$T$$ such that $$M = M(D,T)$$. Moreover, $$M$$ is called conetwork matrix if $$M^{\textsf{T}}$$ is a network matrix.

## Usage

The executable cmr-network converts digraphs to (co)network matrices and vice versa. In particular, for a given matrix $$M$$, it determines whether $$M$$ is (co)network.

./cmr-network [OPTION]... FILE


Options:

• -i FORMAT Format of input FILE; default: dense.
• -o FORMAT Format of output; default: edgelist if input is a matrix and dense if input is a graph.
• -t Tests for being / converts to conetwork matrix.
• n Output the elements of a minimal non-(co)network submatrix.
• N Output a minimal non-(co)network submatrix.
• s Print statistics about the computation to stderr.

Formats for matrices are dense-matrix and sparse-matrix. Formats for graphs are edge-list and dot (output-only). If FILE is -, then the input will be read from stdin.

## Algorithm

The implemented recognition algorithm first tests the support matrix of $$M$$ for being (co)graphic and uses Camion's Signing Algorithm for testing whether $$M$$ is signed correctly.

## C Interface

The functionality is defined in network.h. The main functions are: