camion.h File Reference

Testing whether a matrix is Camion-signed. More...

#include <cmr/matrix.h>
#include <cmr/graph.h>
#include <stdint.h>

Go to the source code of this file.

Classes
struct	CMR_CAMION_STATISTICS
	Statistics for Camion-signing algorithm. More...

Functions
CMR_EXPORT CMR_ERROR	CMRcamionStatsInit (CMR_CAMION_STATISTICS *stats)
	Initializes all statistics for Camion-signing algorithm. More...
CMR_EXPORT CMR_ERROR	CMRcamionStatsPrint (FILE *stream, CMR_CAMION_STATISTICS *stats, const char *prefix)
	Prints statistics for Camion-signing algorithm. More...
CMR_EXPORT CMR_ERROR	CMRcamionTestSigns (CMR *cmr, CMR_CHRMAT *matrix, bool *pisCamionSigned, CMR_SUBMAT **psubmatrix, CMR_CAMION_STATISTICS *stats, double timeLimit)
	Tests a matrix \( M \) for being a Camion-signed. More...
CMR_EXPORT CMR_ERROR	CMRcamionComputeSigns (CMR *cmr, CMR_CHRMAT *matrix, bool *pwasCamionSigned, CMR_SUBMAT **psubmatrix, CMR_CAMION_STATISTICS *stats, double timeLimit)
	Computes a Camion-signed version of a given ternary matrix \( M \). More...
CMR_EXPORT CMR_ERROR	CMRcamionCographicOrient (CMR *cmr, CMR_CHRMAT *matrix, CMR_GRAPH *cograph, CMR_GRAPH_EDGE *forestEdges, CMR_GRAPH_EDGE *coforestEdges, bool *arcsReversed, bool *pisCamionSigned, CMR_SUBMAT **psubmatrix, CMR_CAMION_STATISTICS *stats)
	Orients the edges of the graph cograph such that the matrix matrix \( M \) is the corresponding network matrix, which implicitly tests if matrix is Camion-signed. More...

Detailed Description

Testing whether a matrix is Camion-signed.

Author

Matthias Walter

Function Documentation

CMRcamionCographicOrient()

CMR_EXPORT CMR_ERROR CMRcamionCographicOrient	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_GRAPH *	cograph,
		CMR_GRAPH_EDGE *	forestEdges,
		CMR_GRAPH_EDGE *	coforestEdges,
		bool *	arcsReversed,
		bool *	pisCamionSigned,
		CMR_SUBMAT **	psubmatrix,
		CMR_CAMION_STATISTICS *	stats
	)

Orients the edges of the graph cograph such that the matrix matrix \( M \) is the corresponding network matrix, which implicitly tests if matrix is Camion-signed.

The cograph \( G = (V,E) \) has a spanning tree \( T \subseteq E \) indexed by the columns of \( M \). Its complement \( E \setminus T \) is indexed by the rows of \( M \). The function assumes that \( supp(M) = M(G,T)^\textsf{T} \) holds and attempts to compute an orientation \( A \) of the edges \( E \) (which is stored in arcsReversed) that corresponds to the signs of \( M \). *pisCamionSigned indicates success. If successful, \( M \) is the network matrix of the digraph \( D = (V,A) \). Otherwise, *psubmatrix will indicate a violating submatrix (if not NULL).

Parameters

cmr	CMR environment.
matrix	Matrix \( M \).
cograph	Cograph \( G = (V,E) \) claimed to correspond to \( M \).
forestEdges	\( T \), ordered by the columns of \( M \).
coforestEdges	\( E \setminus T \), ordered by the rows of \( M \).
arcsReversed	Indicates, for each edge \( \{u, v\} \in E\), whether \( (u,v) \in A \) (if false) or \( (v,u) \in A \) (if true).
pisCamionSigned	Pointer for storing whether \( M \) is [Camion-signed](Camion's Signing Algorithm).
psubmatrix	Pointer for storing a non-Camion submatrix (may be NULL).
stats	Statistics for the computation (may be NULL).

CMRcamionComputeSigns()

CMR_EXPORT CMR_ERROR CMRcamionComputeSigns	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pwasCamionSigned,
		CMR_SUBMAT **	psubmatrix,
		CMR_CAMION_STATISTICS *	stats,
		double	timeLimit
	)

Computes a Camion-signed version of a given ternary matrix \( M \).

Parameters

cmr	CMR environment.
matrix	Matrix \( M \) to be modified.
pwasCamionSigned	Pointer for storing whether \( M \) was already [Camion-signed](Camion's Signing Algorithm).
psubmatrix	Pointer for storing a non-Camion submatrix (may be NULL).
stats	Statistics for the computation (may be NULL).
timeLimit	Time limit to impose.

CMRcamionStatsInit()

CMR_EXPORT CMR_ERROR CMRcamionStatsInit

(

CMR_CAMION_STATISTICS *

stats

)

Initializes all statistics for Camion-signing algorithm.

Parameters

stats

Pointer to statistics.

CMRcamionStatsPrint()

CMR_EXPORT CMR_ERROR CMRcamionStatsPrint	(	FILE *	stream,
		CMR_CAMION_STATISTICS *	stats,
		const char *	prefix
	)

Prints statistics for Camion-signing algorithm.

Parameters

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

CMRcamionTestSigns()

CMR_EXPORT CMR_ERROR CMRcamionTestSigns	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisCamionSigned,
		CMR_SUBMAT **	psubmatrix,
		CMR_CAMION_STATISTICS *	stats,
		double	timeLimit
	)

Tests a matrix \( M \) for being a Camion-signed.

Parameters

cmr	CMR environment.
matrix	Matrix \( M \).
pisCamionSigned	Pointer for storing whether \( M \) is [Camion-signed](Camion's Signing Algorithm).
psubmatrix	Pointer for storing a non-Camion submatrix (may be NULL).
stats	Statistics for the computation (may be NULL).
timeLimit	Time limit to impose.