CMR
1.3.0

#include <cmr/graphic.h>
#include <cmr/network.h>
#include <cmr/camion.h>
#include "graphic_internal.h"
#include "env_internal.h"
#include "matrix_internal.h"
#include "block_decomposition.h"
#include "heap.h"
#include "sort.h"
#include <assert.h>
#include <limits.h>
#include <stdlib.h>
#include <time.h>
Classes  
struct  NetworkEdgeData 
struct  NetworkNodeData 
Enumerations  
enum  DIJKSTRA_STAGE { UNKNOWN = 0 , SEEN = 1 , COMPLETED = 2 , BASIC = 3 , UNKNOWN = 0 , SEEN = 1 , COMPLETED = 2 , BASIC = 3 } 
Functions  
CMR_ERROR  CMRnetworkStatsInit (CMR_NETWORK_STATISTICS *stats) 
Initializes all statistics for recognition algorithm for network matrices. More...  
CMR_ERROR  CMRnetworkStatsPrint (FILE *stream, CMR_NETWORK_STATISTICS *stats, const char *prefix) 
Prints statistics for recognition algorithm for network matrices. More...  
CMR_ERROR  CMRnetworkComputeMatrix (CMR *cmr, CMR_GRAPH *digraph, CMR_CHRMAT **pmatrix, CMR_CHRMAT **ptranspose, bool *arcsReversed, int numForestArcs, CMR_GRAPH_EDGE *forestArcs, int numCoforestArcs, CMR_GRAPH_EDGE *coforestArcs, bool *pisCorrectForest) 
Computes the network matrix of a given digraph \( D = (V,A) \). More...  
CMR_ERROR  CMRnetworkTestTranspose (CMR *cmr, CMR_CHRMAT *matrix, bool *pisConetwork, bool *psupportIsCographic, CMR_GRAPH **pdigraph, CMR_GRAPH_EDGE **pforestArcs, CMR_GRAPH_EDGE **pcoforestArcs, bool **parcsReversed, CMR_SUBMAT **psubmatrix, CMR_NETWORK_STATISTICS *stats, double timeLimit) 
Tests a matrix \( M \) for being a conetwork matrix. More...  
CMR_ERROR  CMRnetworkTestMatrix (CMR *cmr, CMR_CHRMAT *matrix, bool *pisNetwork, bool *psupportIsGraphic, CMR_GRAPH **pdigraph, CMR_GRAPH_EDGE **pforestArcs, CMR_GRAPH_EDGE **pcoforestArcs, bool **parcsReversed, CMR_SUBMAT **psubmatrix, CMR_NETWORK_STATISTICS *stats, double timeLimit) 
Tests a matrix \( M \) for being a network matrix. More...  
enum DIJKSTRA_STAGE 
CMR_ERROR CMRnetworkComputeMatrix  (  CMR *  cmr, 
CMR_GRAPH *  digraph,  
CMR_CHRMAT **  pmatrix,  
CMR_CHRMAT **  ptranspose,  
bool *  arcsReversed,  
int  numForestArcs,  
CMR_GRAPH_EDGE *  forestArcs,  
int  numCoforestArcs,  
CMR_GRAPH_EDGE *  coforestArcs,  
bool *  pisCorrectForest  
) 
Computes the network matrix of a given digraph \( D = (V,A) \).
Computes the network matrix \( M := M(D,T) \) for given \( D \) and optionally given (directed) spanning forest \( T \subseteq A \). If \( T \) is not given, an arbitrary (directed) spanning forest of \( D \) is used. The direction of the edges is that of digraph
, but may be flipped by specifying arcsReversed
. If forestArcs
is NULL
, an arbitrary (directed) spanning forest \( T \) of \( D \) is computed. The ordering of the columns can be specified via coforestArcs
.
forestArcs
is a correct (directed) spanning forest. Whether this was the case is indicated via *pisCorrectForest
. cmr  CMR environment. 
digraph  Digraph \( D = (V,A) \). 
pmatrix  Pointer for storing \( M \) (may be NULL ). 
ptranspose  Pointer for storing \( M^{\mathsf{T}} \) (may be NULL ). 
arcsReversed  Indicates, for each edge \( \{u, v\}\), whether we consider \( (u, v)\) (if false ) or \( (v,u)\) (if true ). 
numForestArcs  \( T \) (0 if forestArcs is NULL ). 
forestArcs  \( T \), ordered by the rows of \( M \) (may be NULL ). 
numCoforestArcs  \( A \setminus T \) (0 if coforestArcs is NULL ). 
coforestArcs  \( A \setminus T \), ordered by the columns of \( M \) (may be NULL ). 
pisCorrectForest  Pointer for storing whether forestArcs is a (directed) spanning forest of \( D \)'s underlying undirected graph (may be NULL ). 
CMR_ERROR CMRnetworkStatsInit  (  CMR_NETWORK_STATISTICS *  stats  ) 
Initializes all statistics for recognition algorithm for network matrices.
stats  Pointer to statistics. 
CMR_ERROR CMRnetworkStatsPrint  (  FILE *  stream, 
CMR_NETWORK_STATISTICS *  stats,  
const char *  prefix  
) 
Prints statistics for recognition algorithm for network matrices.
stream  File stream to print to. 
stats  Pointer to statistics. 
prefix  Prefix string to prepend to each printed line (may be NULL ). 
CMR_ERROR CMRnetworkTestMatrix  (  CMR *  cmr, 
CMR_CHRMAT *  matrix,  
bool *  pisNetwork,  
bool *  psupportIsGraphic,  
CMR_GRAPH **  pdigraph,  
CMR_GRAPH_EDGE **  pforestArcs,  
CMR_GRAPH_EDGE **  pcoforestArcs,  
bool **  parcsReversed,  
CMR_SUBMAT **  psubmatrix,  
CMR_NETWORK_STATISTICS *  stats,  
double  timeLimit  
) 
Tests a matrix \( M \) for being a network matrix.
Tests if \( M = M(D,T) \) for some digraph \( D = (V,A) \) and some (directed) spanning forest \( T \subseteq A \) of \( D \) and sets *pisNetwork
and *psupportIsGraphic
accordingly.
If \( M \) is a network matrix and pdigraph
!= NULL
, then one possible digraph \( D \) is computed and stored in *pdigraph
. The caller must release its memory via CMRgraphFree. If in addition to pdigraph
also pforestArcs
!= NULL
(resp. pcoforestArcs
!= NULL
), then a corresponding (directed) spanning forest \( T \) (resp. its complement \( A \setminus T \)) is stored in *pforestArcs
(resp. *pcoforestArcs
). The caller must release this memory via CMRfreeBlockArray.
*psubmatrix
is not implemented, yet. cmr  CMR environment. 
matrix  Matrix \( M \). 
pisNetwork  Pointer for storing true if and only if \( M \) is a network matrix. 
psupportIsGraphic  Pointer for storing true if and only if the support matrix is graphic. 
pdigraph  Pointer for storing the digraph \( D \) (if \( M \) is network). 
pforestArcs  Pointer for storing \( T \), indexed by the rows of \( M \) (if \( M \) is network). 
pcoforestArcs  Pointer for storing \( A \setminus T \), indexed by the columns of \( M \) (if \( M \) is network). 
parcsReversed  Pointer for storing indicators which arcs are reversed for the correct sign (if \( M \) is network). 
psubmatrix  Pointer for storing a minimal nonnetwork submatrix (if \( M \) is not network). 
stats  Pointer to statistics (may be NULL ). 
timeLimit  Time limit to impose. 
CMR_ERROR CMRnetworkTestTranspose  (  CMR *  cmr, 
CMR_CHRMAT *  matrix,  
bool *  pisConetwork,  
bool *  psupportIsCographic,  
CMR_GRAPH **  pdigraph,  
CMR_GRAPH_EDGE **  pforestArcs,  
CMR_GRAPH_EDGE **  pcoforestArcs,  
bool **  parcsReversed,  
CMR_SUBMAT **  psubmatrix,  
CMR_NETWORK_STATISTICS *  stats,  
double  timeLimit  
) 
Tests a matrix \( M \) for being a conetwork matrix.
Tests if \( M = M(D,T)^{\mathsf{T}} \) for some digraph \( D = (V,A) \) and some (directed) spanning forest \( T \subseteq A \) of \( D \) and sets *pisConetwork
accordingly.
If \( M \) is a conetwork matrix and pdigraph
!= NULL
, then one possible digraph \( D \) is computed and stored in *pdigraph
. The caller must release its memory via CMRgraphFree. If in addition to pdigraph
also pforestArcs
!= NULL
(resp. pcoforestArcs
!= NULL
), then a corresponding (directed) spanning forest \( T \) (resp. its complement \( A \setminus T \)) is stored in *pforestArcs
(resp. *pcoforestArcs
). The caller must release this memory via CMRfreeBlockArray.
*psubmatrix
is not implemented, yet. cmr  CMR environment. 
matrix  Matrix \( M \). 
pisConetwork  Returns true if and only if \( M \) is a conetwork matrix. 
psupportIsCographic  Pointer for storing true if and only if the support matrix is cographic. 
pdigraph  Pointer for storing true if and only if \( M \) is conetwork. 
pforestArcs  Pointer for storing \( T \), indexed by the columns of \( M \) (if \( M \) is network). 
pcoforestArcs  Pointer for storing \( A \setminus T \), indexed by the rows of \( M \) (if \( M \) is conetwork). 
parcsReversed  Pointer for storing indicators which arcs are reversed for the correct sign (if \( M \) is conetwork). 
psubmatrix  Pointer for storing a minimal nonconetwork submatrix (if \( M \) is not conetwork). 
stats  Pointer to statistics (may be NULL ). 
timeLimit  Time limit to impose. 