CMR
1.3.0

Computation and recognition of graphic matrices and cographic matrices. More...
#include <cmr/env.h>
#include <cmr/element.h>
#include <cmr/matrix.h>
#include <cmr/graph.h>
#include <stdio.h>
Go to the source code of this file.
Classes  
struct  CMR_GRAPHIC_STATISTICS 
Statistics for graphicness test. More...  
Functions  
CMR_EXPORT CMR_ERROR  CMRstatsGraphicInit (CMR_GRAPHIC_STATISTICS *stats) 
Initializes all statistics for graphicness computations. More...  
CMR_EXPORT CMR_ERROR  CMRstatsGraphicPrint (FILE *stream, CMR_GRAPHIC_STATISTICS *stats, const char *prefix) 
Prints statistics for graphicness computations. More...  
CMR_EXPORT CMR_ERROR  CMRcomputeGraphicMatrix (CMR *cmr, CMR_GRAPH *graph, CMR_CHRMAT **pmatrix, CMR_CHRMAT **ptranspose, int numForestEdges, CMR_GRAPH_EDGE *forestEdges, int numCoforestEdges, CMR_GRAPH_EDGE *coforestEdges, bool *pisCorrectForest) 
Computes the graphic matrix of a given graph \( G = (V,E) \). More...  
CMR_EXPORT CMR_ERROR  CMRtestGraphicMatrix (CMR *cmr, CMR_CHRMAT *matrix, bool *pisGraphic, CMR_GRAPH **pgraph, CMR_GRAPH_EDGE **pforestEdges, CMR_GRAPH_EDGE **pcoforestEdges, CMR_SUBMAT **psubmatrix, CMR_GRAPHIC_STATISTICS *stats, double timeLimit) 
Tests a matrix \( M \) for being a graphic matrix. More...  
CMR_EXPORT CMR_ERROR  CMRtestCographicMatrix (CMR *cmr, CMR_CHRMAT *matrix, bool *pisCographic, CMR_GRAPH **pgraph, CMR_GRAPH_EDGE **pforestEdges, CMR_GRAPH_EDGE **pcoforestEdges, CMR_SUBMAT **psubmatrix, CMR_GRAPHIC_STATISTICS *stats, double timeLimit) 
Tests a matrix \( M \) for being a cographic matrix. More...  
CMR_EXPORT CMR_ERROR  CMRtestGraphicColumnSubmatrixGreedy (CMR *cmr, CMR_CHRMAT *transpose, size_t *orderedColumns, CMR_SUBMAT **psubmatrix) 
Finds an inclusionwise maximal subset of columns that induces a graphic submatrix. More...  
Computation and recognition of graphic matrices and cographic matrices.
The following notation is used throughout:
CMR_EXPORT CMR_ERROR CMRcomputeGraphicMatrix  (  CMR *  cmr, 
CMR_GRAPH *  graph,  
CMR_CHRMAT **  pmatrix,  
CMR_CHRMAT **  ptranspose,  
int  numForestEdges,  
CMR_GRAPH_EDGE *  forestEdges,  
int  numCoforestEdges,  
CMR_GRAPH_EDGE *  coforestEdges,  
bool *  pisCorrectForest  
) 
Computes the graphic matrix of a given graph \( G = (V,E) \).
Computes the graphic matrix \( M := M(G,T) \) for given \( G \) and optionally given spanning forest \( T \subseteq E \). If \( T \) is not given, an arbitrary spanning forest of \( G \) is used. If forestEdges
is NULL
, an arbitrary spanning forest \( T \) of \( G \) is computed. The ordering of the columns can be specified via coforestEdges
.
forestEdges
is a correct spanning forest. Whether this was the case is indicated via *pisCorrectForest
. cmr  CMR environment. 
graph  Graph \( G = (V,E) \). 
pmatrix  Pointer for storing \( M \) (may be NULL ). 
ptranspose  Pointer for storing \( M^{\mathsf{T}} \) (may be NULL ). 
numForestEdges  \( T \) (0 if forestEdges is NULL ). 
forestEdges  \( T \), ordered by the rows of \( M \) (may be NULL ). 
numCoforestEdges  \( E \setminus T \) (0 if coforestEdges is NULL ). 
coforestEdges  \( E \setminus T \), ordered by the columns of \( M \) (may be NULL ). 
pisCorrectForest  Pointer for storing whether forestEdges is a spanning forest of \( G \) (may be NULL ). 
CMR_EXPORT CMR_ERROR CMRstatsGraphicInit  (  CMR_GRAPHIC_STATISTICS *  stats  ) 
Initializes all statistics for graphicness computations.
stats  Pointer to statistics. 
CMR_EXPORT CMR_ERROR CMRstatsGraphicPrint  (  FILE *  stream, 
CMR_GRAPHIC_STATISTICS *  stats,  
const char *  prefix  
) 
Prints statistics for graphicness computations.
stream  File stream to print to. 
stats  Pointer to statistics. 
prefix  Prefix string to prepend to each printed line (may be NULL ). 
CMR_EXPORT CMR_ERROR CMRtestCographicMatrix  (  CMR *  cmr, 
CMR_CHRMAT *  matrix,  
bool *  pisCographic,  
CMR_GRAPH **  pgraph,  
CMR_GRAPH_EDGE **  pforestEdges,  
CMR_GRAPH_EDGE **  pcoforestEdges,  
CMR_SUBMAT **  psubmatrix,  
CMR_GRAPHIC_STATISTICS *  stats,  
double  timeLimit  
) 
Tests a matrix \( M \) for being a cographic matrix.
Tests if \( M = M(G,T)^{\mathsf{T}} \) for some graph \( G = (V,E) \) and some spanning forest \( T \subseteq E \) of \( G \) and sets *pisCographic
accordingly.
If \( M \) is a cographic matrix and pgraph
!= NULL
, then one possible graph \( G \) is computed and stored in *pgraph
. The caller must release its memory via CMRgraphFree. If in addition to pgraph
also pforestEdges
!= NULL
(resp. pcoforestEdges
!= NULL
), then a corresponding spanning forest \( T \) (resp. its complement \( E \setminus T \)) is stored in *pforestEdges
(resp. *pcoforestEdges
). The caller must release this memory via CMRfreeBlockArray.
*psubmatrix
is not implemented, yet. cmr  CMR environment. 
matrix  Matrix \( M \) 
pisCographic  Returns true if and only if \( M \) is a cographic matrix. 
pgraph  Pointer for storing the graph \( G \) (if \( M \) is graphic). 
pforestEdges  Pointer for storing \( T \), indexed by the rows of \( M \) (if \( M \) is graphic). 
pcoforestEdges  Pointer for storing \( E \setminus T \), indexed by the columns of \( M \) (if \( M \) is graphic). 
psubmatrix  Pointer for storing a minimal nongraphic submatrix (if \( M \) is not graphic). 
stats  Pointer to statistics (may be NULL ). 
timeLimit  Time limit to impose. 
CMR_EXPORT CMR_ERROR CMRtestGraphicColumnSubmatrixGreedy  (  CMR *  cmr, 
CMR_CHRMAT *  transpose,  
size_t *  orderedColumns,  
CMR_SUBMAT **  psubmatrix  
) 
Finds an inclusionwise maximal subset of columns that induces a graphic submatrix.
Finds an inclusionwise maximal subset \( J \) of columns of \( M \) such that \( M_{\star,J} \) is a graphic representation matrix. To achieve this, it tries to append columns in the order given by orderedColumns
, maintaining graphicness.
cmr  CMR environment. 
transpose  \( M^{\mathsf{T}} \) 
orderedColumns  Permutation of column indices of \( M \). 
psubmatrix  Pointer for storing the submatrix. 
CMR_EXPORT CMR_ERROR CMRtestGraphicMatrix  (  CMR *  cmr, 
CMR_CHRMAT *  matrix,  
bool *  pisGraphic,  
CMR_GRAPH **  pgraph,  
CMR_GRAPH_EDGE **  pforestEdges,  
CMR_GRAPH_EDGE **  pcoforestEdges,  
CMR_SUBMAT **  psubmatrix,  
CMR_GRAPHIC_STATISTICS *  stats,  
double  timeLimit  
) 
Tests a matrix \( M \) for being a graphic matrix.
Tests if \( M = M(G,T) \) for some graph \( G = (V,E) \) and some spanning forest \( T \subseteq E \) of \( G \) and sets *pisGraphic
accordingly.
If \( M \) is a graphic matrix and pgraph
!= NULL
, then one possible graph \( G \) is computed and stored in *pgraph
. The caller must release its memory via CMRgraphFree. If in addition to pgraph
also pforestEdges
!= NULL
(resp. pcoforestEdges
!= NULL
), then a corresponding spanning forest \( T \) (resp. its complement \( E \setminus T \)) is stored in *pforestEdges
(resp. *pcoforestEdges
). The caller must release this memory via CMRfreeBlockArray.
*psubmatrix
is not implemented, yet. cmr  CMR environment. 
matrix  Matrix \( M \). 
pisGraphic  Pointer for storing true if and only if \( M \) is a graphic matrix. 
pgraph  Pointer for storing the graph \( G \) (if \( M \) is graphic). 
pforestEdges  Pointer for storing \( T \), indexed by the rows of \( M \) (if \( M \) is graphic). 
pcoforestEdges  Pointer for storing \( E \setminus T \), indexed by the columns of \( M \) (if \( M \) is graphic). 
psubmatrix  Pointer for storing a minimal nongraphic submatrix (if \( M \) is not graphic). 
stats  Pointer to statistics (may be NULL ). 
timeLimit  Time limit to impose. 