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

Go to the source code of this file.

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.
CMR_EXPORT CMR_ERROR	CMRgraphicStatsPrint (FILE *stream, CMR_GRAPHIC_STATISTICS *stats, const char *prefix)
	Prints statistics for graphicness computations.
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) \).
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.
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.
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.

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.