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.

Recognizing Network Matrices

The command

cmr-network IN-MAT [OPTION]...

determines whether the matrix given in file IN-MAT is (co)network.

Options:

-i FORMAT Format of file IN-MAT, among dense for dense-matrix and sparse for sparse-matrix; default: dense.
-t Test for being conetwork; default: test for being network.
-G OUT-GRAPH Write a digraph to file OUT-GRAPH; default: skip computation.
-T OUT-TREE Write a directed spanning tree to file OUT-TREE; default: skip computation.
-D OUT-DOT Write a dot file OUT-DOT with the digraph and the directed spanning tree; default: skip computation.
-N NON-SUB Write a minimal non-network submatrix to file NON-SUB; default: skip computation.
-s Print statistics about the computation to stderr.

If IN-MAT is - then the matrix is read from stdin. If OUT-GRAPH, OUT-TREE, OUT-DOT or NON-SUB is - then the graph (resp. the tree, dot file or non-(co)network submatrix) is written to stdout.

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 corresponding functions in the library are

CMRnetworkTestMatrix() tests a matrix for being network.
CMRnetworkTestTranspose() tests a matrix for being conetwork.

and are defined in network.h.

Computing network matrices

The command

cmr-network -c IN-GRAPH OUT-MAT [OPTION]...

computes a (co)network matrix corresponding to the digraph from file IN-GRAPH and writes it to OUT-MAT.

Options:

-o FORMAT Format of file OUT-MAT, among dense for dense-matrix and sparse for sparse-matrix; default: dense.
-t Return the transpose of the network matrix.
-T IN-TREE Read a directed tree from file IN-TREE; default: use first specified arcs as tree edges.
-s Print statistics about the computation to stderr.

If IN-GRAPH or IN-TREE is - then the digraph (resp. directed tree) is read from stdin. If OUT-MAT is - then the matrix is written to stdout.

C Interface

The corresponding function in the library is

CMRnetworkComputeMatrix() constructs a network matrix for a given digraph.

and is defined in network.h.