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>
#include <stdint.h>

Classes
struct	CMR_GRAPHIC_STATISTICS
	Statistics for graphicness test. More...

Functions
CMR_EXPORT CMR_ERROR	CMRgraphicStatsInit (CMR_GRAPHIC_STATISTICS *stats)
	Initializes all statistics for graphicness computations. More...

CMR_EXPORT CMR_ERROR	CMRgraphicStatsPrint (FILE stream, CMR_GRAPHIC_STATISTICS stats, const char *prefix)
	Prints statistics for graphicness computations. More...

CMR_EXPORT CMR_ERROR	CMRgraphicComputeMatrix (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	CMRgraphicTestMatrix (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	CMRgraphicTestTranspose (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	CMRgraphicTestColumnSubmatrixGreedy (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:

\( G = (V,E) \) for the graph with nodes \( V \) and edges \( E \).
\( T \subseteq E \) for a spanning forest of \( G \).
\( M \) for the (potential) (co)graphic matrix.

Function Documentation

◆ CMRgraphicComputeMatrix()

CMR_EXPORT CMR_ERROR CMRgraphicComputeMatrix	(	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

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`).

◆ CMRgraphicStatsInit()

CMR_EXPORT CMR_ERROR CMRgraphicStatsInit ( CMR_GRAPHIC_STATISTICS * stats )

Initializes all statistics for graphicness computations.

Parameters

stats Pointer to statistics.

◆ CMRgraphicStatsPrint()

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

Prints statistics for graphicness computations.

Parameters

stream	File stream to print to.
stats	Pointer to statistics.
prefix	Prefix string to prepend to each printed line (may be `NULL`).

◆ CMRgraphicTestColumnSubmatrixGreedy()

CMR_EXPORT CMR_ERROR CMRgraphicTestColumnSubmatrixGreedy	(	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

cmr	CMR environment.
transpose	\( M^{\mathsf{T}} \)
orderedColumns	Permutation of column indices of \( M \).
psubmatrix	Pointer for storing the submatrix.

◆ CMRgraphicTestMatrix()

CMR_EXPORT CMR_ERROR CMRgraphicTestMatrix	(	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 CMRgraphicTestTranspose() 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

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 non-graphic submatrix (if \( M \) is not graphic).
stats	Pointer to statistics (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRgraphicTestTranspose()

CMR_EXPORT CMR_ERROR CMRgraphicTestTranspose	(	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

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 non-graphic submatrix (if \( M \) is not graphic).
stats	Pointer to statistics (may be `NULL`).
timeLimit	Time limit to impose.

Classes

Functions

Detailed Description

Function Documentation

◆ CMRgraphicComputeMatrix()

◆ CMRgraphicStatsInit()

◆ CMRgraphicStatsPrint()

◆ CMRgraphicTestColumnSubmatrixGreedy()

◆ CMRgraphicTestMatrix()

◆ CMRgraphicTestTranspose()