CMR  1.3.0
Classes | Functions
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
cmrCMR environment.
matrixMatrix \( M \).
cographCograph \( 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 \).
arcsReversedIndicates, for each edge \( \{u, v\} \in E\), whether \( (u,v) \in A \) (if false) or \( (v,u) \in A \) (if true).
pisCamionSignedPointer for storing whether \( M \) is [Camion-signed](Camion's Signing Algorithm).
psubmatrixPointer for storing a non-Camion submatrix (may be NULL).
statsStatistics 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
cmrCMR environment.
matrixMatrix \( M \) to be modified.
pwasCamionSignedPointer for storing whether \( M \) was already [Camion-signed](Camion's Signing Algorithm).
psubmatrixPointer for storing a non-Camion submatrix (may be NULL).
statsStatistics for the computation (may be NULL).
timeLimitTime limit to impose.

◆ CMRcamionStatsInit()

CMR_EXPORT CMR_ERROR CMRcamionStatsInit ( CMR_CAMION_STATISTICS stats)

Initializes all statistics for Camion-signing algorithm.

Parameters
statsPointer to statistics.

◆ CMRcamionStatsPrint()

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

Prints statistics for Camion-signing algorithm.

Parameters
streamFile stream to print to.
statsPointer to statistics.
prefixPrefix 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
cmrCMR environment.
matrixMatrix \( M \).
pisCamionSignedPointer for storing whether \( M \) is [Camion-signed](Camion's Signing Algorithm).
psubmatrixPointer for storing a non-Camion submatrix (may be NULL).
statsStatistics for the computation (may be NULL).
timeLimitTime limit to impose.