graphic_internal.h File Reference

#include <cmr/graphic.h>

Go to the source code of this file.

Functions
CMR_ERROR	CMRcomputeRepresentationMatrix (CMR *cmr, CMR_GRAPH *digraph, bool ternary, CMR_CHRMAT **ptranspose, bool *arcsReversed, int numForestArcs, CMR_GRAPH_EDGE *forestArcs, int numCoforestArcs, CMR_GRAPH_EDGE *coforestArcs, bool *pisCorrectForest)
	Computes the network or graphic matrix of a given (di)graph \( D = (V,A) \).
CMR_ERROR	CMRcographicTestSupport (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 the support matrix \( M \) of the input matrix for being a cographic matrix.

Function Documentation

CMRcographicTestSupport()

CMR_ERROR CMRcographicTestSupport	(	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 the support matrix \( M \) of the input matrix 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.

CMRcomputeRepresentationMatrix()

CMR_ERROR CMRcomputeRepresentationMatrix	(	CMR *	cmr,
		CMR_GRAPH *	digraph,
		bool	ternary,
		CMR_CHRMAT **	ptranspose,
		bool *	arcsReversed,
		int	numForestArcs,
		CMR_GRAPH_EDGE *	forestArcs,
		int	numCoforestArcs,
		CMR_GRAPH_EDGE *	coforestArcs,
		bool *	pisCorrectForest
	)

Computes the network or graphic matrix of a given (di)graph \( D = (V,A) \).

Computes the network matrix \( M := M(D,T) \) for given \( D \) and optionally given (directed) spanning forest \( T \subseteq A \) or the support matrix of \( M(D,T) \). 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.

Note

The function computes a network matrix of \( D \) (and \( T \)) regardless of whether forestArcs is a correct (directed) spanning forest. Whether this was the case is indicated via *pisCorrectForest.

Parameters

cmr	CMR environment.
digraph	Digraph \( D = (V,A) \).
ternary	Whether we need to compute correct signs.
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).