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:

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: