camion.c File Reference

#include <cmr/camion.h>
#include "camion_internal.h"
#include "matrix_internal.h"
#include "block_decomposition.h"
#include "env_internal.h"
#include <assert.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

Classes
struct	GRAPH_NODE
	Graph node for BFS in signing algorithm. More...
struct	OrientationSearchEdgeData
struct	OrientationSearchNodeData

Enumerations
enum	OrientationSearchStage { UNKNOWN = 0 , SEEN = 1 , COMPLETED = 2 , BASIC = 3 }

Functions
CMR_ERROR	CMRcamionStatsInit (CMR_CAMION_STATISTICS *stats)
	Initializes all statistics for Camion-signing algorithm. More...
CMR_ERROR	CMRcamionStatsPrint (FILE *stream, CMR_CAMION_STATISTICS *stats, const char *prefix)
	Prints statistics for Camion-signing algorithm. More...
CMR_ERROR	CMRcamionComputeSignSequentiallyConnected (CMR *cmr, CMR_CHRMAT *matrix, CMR_CHRMAT *transpose, bool change, char *pmodification, CMR_SUBMAT **psubmatrix, double timeLimit)
	Ensures that sequentially connected matrix \( M \) is Camion-signed. More...
static CMR_ERROR	signCamion (CMR *cmr, CMR_CHRMAT *matrix, bool change, bool *pisCamionSigned, CMR_SUBMAT **psubmatrix, CMR_CAMION_STATISTICS *stats, double timeLimit)
	Signs a given matrix. More...
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_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...
static CMR_ERROR	constructNonCamionSubmatrix (CMR *cmr, CMR_GRAPH *cograph, OrientationSearchEdgeData *edgeData, CMR_GRAPH_EDGE conflictEdge1, CMR_GRAPH_EDGE conflictEdge2, CMR_SUBMAT **psubmatrix)
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...

Enumeration Type Documentation

OrientationSearchStage

enum OrientationSearchStage

Enumerator
UNKNOWN	The node was not considered by the shortest-path, yet.
SEEN	Some path to the node is known.
COMPLETED	The shortest path to the node is known.
BASIC	The rootEdge of that node belongs to the spanning forest.

Function Documentation

CMRcamionCographicOrient()

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_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.

CMRcamionComputeSignSequentiallyConnected()

CMR_ERROR CMRcamionComputeSignSequentiallyConnected	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose,
		bool	change,
		char *	pmodification,
		CMR_SUBMAT **	psubmatrix,
		double	timeLimit
	)

Ensures that sequentially connected matrix \( M \) is Camion-signed.

The matrix \( M \) is assumed to be ternary. If sign changes are necessary, only matrix is modified. In particular, transpose remains unchanged.

If submatrix is not NULL and sign changes are necessary, then a submatrix with determinant -2 or +2 is stored in *psubmatrix and the caller must use CMRsubmatFree() to free its memory. It is set to NULL if no sign changes are needed.

Parameters

cmr	CMR environment.
matrix	The matrix to be signed.
transpose	The transpose of matrix.
change	Whether to modify the matrix.
pmodification	Pointer for storing which matrix was modified.
psubmatrix	Pointer for storing a submatrix with bad determinant (may be NULL).
timeLimit	Time limit to impose.

CMRcamionStatsInit()

CMR_ERROR CMRcamionStatsInit

(

CMR_CAMION_STATISTICS *

stats

)

Initializes all statistics for Camion-signing algorithm.

Parameters

stats

Pointer to statistics.

CMRcamionStatsPrint()

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_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.

constructNonCamionSubmatrix()

static CMR_ERROR constructNonCamionSubmatrix ( CMR *  cmr, CMR_GRAPH *  cograph, OrientationSearchEdgeData *  edgeData, CMR_GRAPH_EDGE  conflictEdge1, CMR_GRAPH_EDGE  conflictEdge2, CMR_SUBMAT **  psubmatrix  )

static

Parameters

cmr	CMR environment.
cograph	Cograph we consider.
edgeData	Edge data array.
conflictEdge1	First edge of conflict.
conflictEdge2	Second edge of conflict.
psubmatrix	Pointer for storing the submatrix.

signCamion()

static CMR_ERROR signCamion ( CMR *  cmr, CMR_CHRMAT *  matrix, bool  change, bool *  pisCamionSigned, CMR_SUBMAT **  psubmatrix, CMR_CAMION_STATISTICS *  stats, double  timeLimit  )

static

Signs a given matrix.

Parameters

cmr	CMR environment.
matrix	Matrix \( M \).
change	Whether the signs of \( M \) shall be modified.
pisCamionSigned	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.