CMR  1.3.0
Classes | Functions
graphic.h File Reference

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 inclusion-wise maximal subset of columns that induces a graphic submatrix. More...
 

Detailed Description

Computation and recognition of graphic matrices and cographic matrices.

Author
Matthias Walter

The following notation is used throughout:

Function Documentation

◆ CMRcomputeGraphicMatrix()

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.

Note
The function computes a graphic matrix of \( G \) (and \( T \)) regardless of whether forestEdges is a correct spanning forest. Whether this was the case is indicated via *pisCorrectForest.
Parameters
cmrCMR environment.
graphGraph \( G = (V,E) \).
pmatrixPointer for storing \( M \) (may be NULL).
ptransposePointer 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).
pisCorrectForestPointer for storing whether forestEdges is a spanning forest of \( G \) (may be NULL).

◆ CMRstatsGraphicInit()

CMR_EXPORT CMR_ERROR CMRstatsGraphicInit ( CMR_GRAPHIC_STATISTICS stats)

Initializes all statistics for graphicness computations.

Parameters
statsPointer to statistics.

◆ CMRstatsGraphicPrint()

CMR_EXPORT CMR_ERROR CMRstatsGraphicPrint ( FILE *  stream,
CMR_GRAPHIC_STATISTICS stats,
const char *  prefix 
)

Prints statistics for graphicness computations.

Parameters
streamFile stream to print to.
statsPointer to statistics.
prefixPrefix string to prepend to each printed line (may be NULL).

◆ CMRtestCographicMatrix()

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.

Note
Retrieval of minimal non-cographic submatrices via *psubmatrix is not implemented, yet.
Parameters
cmrCMR environment.
matrixMatrix \( M \)
pisCographicReturns true if and only if \( M \) is a cographic matrix.
pgraphPointer for storing the graph \( G \) (if \( M \) is graphic).
pforestEdgesPointer for storing \( T \), indexed by the rows of \( M \) (if \( M \) is graphic).
pcoforestEdgesPointer for storing \( E \setminus T \), indexed by the columns of \( M \) (if \( M \) is graphic).
psubmatrixPointer for storing a minimal non-graphic submatrix (if \( M \) is not graphic).
statsPointer to statistics (may be NULL).
timeLimitTime limit to impose.

◆ CMRtestGraphicColumnSubmatrixGreedy()

CMR_EXPORT CMR_ERROR CMRtestGraphicColumnSubmatrixGreedy ( CMR cmr,
CMR_CHRMAT transpose,
size_t *  orderedColumns,
CMR_SUBMAT **  psubmatrix 
)

Finds an inclusion-wise maximal subset of columns that induces a graphic submatrix.

Finds an inclusion-wise 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.

Parameters
cmrCMR environment.
transpose\( M^{\mathsf{T}} \)
orderedColumnsPermutation of column indices of \( M \).
psubmatrixPointer for storing the submatrix.

◆ CMRtestGraphicMatrix()

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.

Note
If a column-wise representation of \( M \) is available, it is recommended to call CMRtestCographicMatrix() for that. In fact, the implementation explicitly constructs \( M^{\mathsf{T}} \) before calling this function.

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.

Note
Retrieval of minimal non-graphic submatrices via *psubmatrix is not implemented, yet.
Parameters
cmrCMR environment.
matrixMatrix \( M \).
pisGraphicPointer for storing true if and only if \( M \) is a graphic matrix.
pgraphPointer for storing the graph \( G \) (if \( M \) is graphic).
pforestEdgesPointer for storing \( T \), indexed by the rows of \( M \) (if \( M \) is graphic).
pcoforestEdgesPointer for storing \( E \setminus T \), indexed by the columns of \( M \) (if \( M \) is graphic).
psubmatrixPointer for storing a minimal non-graphic submatrix (if \( M \) is not graphic).
statsPointer to statistics (may be NULL).
timeLimitTime limit to impose.