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.

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; 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-(co)network submatrix to file NON-SUB; default: skip computation.

Advanced options:

• --stats Print statistics about the computation to stderr.
• --time-limit LIMIT Allow at most LIMIT seconds for the computation.

Formats for matrices: dense, sparse 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; 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.

Advanced options:

• --stats Print statistics about the computation to stderr.
• --time-limit LIMIT Allow at most LIMIT seconds for the computation.

Formats for matrices: dense, sparse 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.