#include <cmr/graphic.h>
#include <cmr/network.h>
#include <cmr/camion.h>
#include "graphic_internal.h"
#include "env_internal.h"
#include "matrix_internal.h"
#include "block_decomposition.h"
#include "heap.h"
#include "sort.h"
#include <assert.h>
#include <limits.h>
#include <stdlib.h>
#include <time.h>

Classes
struct	NetworkEdgeData

struct	NetworkNodeData

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

Functions
CMR_ERROR	CMRnetworkStatsInit (CMR_NETWORK_STATISTICS *stats)
	Initializes all statistics for recognition algorithm for network matrices.

CMR_ERROR	CMRnetworkStatsPrint (FILE stream, CMR_NETWORK_STATISTICS stats, const char *prefix)
	Prints statistics for recognition algorithm for network matrices.

CMR_ERROR	CMRnetworkComputeMatrix (CMR cmr, CMR_GRAPH digraph, CMR_CHRMAT pmatrix, CMR_CHRMAT ptranspose, bool arcsReversed, int numForestArcs, CMR_GRAPH_EDGE forestArcs, int numCoforestArcs, CMR_GRAPH_EDGE coforestArcs, bool pisCorrectForest)
	Computes the network matrix of a given digraph \( D = (V,A) \).

CMR_ERROR	CMRnetworkTestTranspose (CMR cmr, CMR_CHRMAT matrix, bool pisConetwork, bool psupportIsCographic, CMR_GRAPH pdigraph, CMR_GRAPH_EDGE pforestArcs, CMR_GRAPH_EDGE pcoforestArcs, bool parcsReversed, CMR_SUBMAT *psubmatrix, CMR_NETWORK_STATISTICS stats, double timeLimit)
	Tests a matrix \( M \) for being a conetwork matrix.

CMR_ERROR	CMRnetworkTestMatrix (CMR cmr, CMR_CHRMAT matrix, bool pisNetwork, bool psupportIsGraphic, CMR_GRAPH pdigraph, CMR_GRAPH_EDGE pforestArcs, CMR_GRAPH_EDGE pcoforestArcs, bool parcsReversed, CMR_SUBMAT *psubmatrix, CMR_NETWORK_STATISTICS stats, double timeLimit)
	Tests a matrix \( M \) for being a network matrix.

Enumeration Type Documentation

◆ DIJKSTRA_STAGE

enum DIJKSTRA_STAGE

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

◆ CMRnetworkComputeMatrix()

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

Computes the network matrix of a given digraph \( D = (V,A) \).

Computes the network matrix \( M := M(D,T) \) for given \( D \) and optionally given (directed) spanning forest \( T \subseteq A \). 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) \).
pmatrix	Pointer for storing \( M \) (may be `NULL`).
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`).

◆ CMRnetworkStatsInit()

CMR_ERROR CMRnetworkStatsInit ( CMR_NETWORK_STATISTICS * stats )

Initializes all statistics for recognition algorithm for network matrices.

Parameters

stats Pointer to statistics.

◆ CMRnetworkStatsPrint()

CMR_ERROR CMRnetworkStatsPrint	(	FILE *	stream,
		CMR_NETWORK_STATISTICS *	stats,
		const char *	prefix
	)

Prints statistics for recognition algorithm for network matrices.

Parameters

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

◆ CMRnetworkTestMatrix()

CMR_ERROR CMRnetworkTestMatrix	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisNetwork,
		bool *	psupportIsGraphic,
		CMR_GRAPH **	pdigraph,
		CMR_GRAPH_EDGE **	pforestArcs,
		CMR_GRAPH_EDGE **	pcoforestArcs,
		bool **	parcsReversed,
		CMR_SUBMAT **	psubmatrix,
		CMR_NETWORK_STATISTICS *	stats,
		double	timeLimit
	)

Tests a matrix \( M \) for being a network matrix.

Tests if \( M = M(D,T) \) for some digraph \( D = (V,A) \) and some (directed) spanning forest \( T \subseteq A \) of \( D \) and sets *pisNetwork and *psupportIsGraphic accordingly.

Note: If a column-wise representation of \( M \) is available, it is recommended to call CMRnetworkTestTranspose() for that. In fact, the implementation explicitly constructs \( M^{\mathsf{T}} \) before calling this function.

If \( M \) is a network matrix and pdigraph != NULL, then one possible digraph \( D \) is computed and stored in *pdigraph. The caller must release its memory via CMRgraphFree. If in addition to pdigraph also pforestArcs != NULL (resp. pcoforestArcs != NULL), then a corresponding (directed) spanning forest \( T \) (resp. its complement \( A \setminus T \)) is stored in *pforestArcs (resp. *pcoforestArcs). The caller must release this memory via CMRfreeBlockArray.

Note: Retrieval of minimal non-network submatrices via *psubmatrix is not implemented, yet.

Parameters

cmr	CMR environment.
matrix	Matrix \( M \).
pisNetwork	Pointer for storing `true` if and only if \( M \) is a network matrix.
psupportIsGraphic	Pointer for storing `true` if and only if the support matrix is graphic.
pdigraph	Pointer for storing the digraph \( D \) (if \( M \) is network).
pforestArcs	Pointer for storing \( T \), indexed by the rows of \( M \) (if \( M \) is network).
pcoforestArcs	Pointer for storing \( A \setminus T \), indexed by the columns of \( M \) (if \( M \) is network).
parcsReversed	Pointer for storing indicators which arcs are reversed for the correct sign (if \( M \) is network).
psubmatrix	Pointer for storing a minimal non-network submatrix (if \( M \) is not network and such a matrix is found by coincidence).
stats	Pointer to statistics (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRnetworkTestTranspose()

CMR_ERROR CMRnetworkTestTranspose	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisConetwork,
		bool *	psupportIsCographic,
		CMR_GRAPH **	pdigraph,
		CMR_GRAPH_EDGE **	pforestArcs,
		CMR_GRAPH_EDGE **	pcoforestArcs,
		bool **	parcsReversed,
		CMR_SUBMAT **	psubmatrix,
		CMR_NETWORK_STATISTICS *	stats,
		double	timeLimit
	)

Tests a matrix \( M \) for being a conetwork matrix.

Tests if \( M = M(D,T)^{\mathsf{T}} \) for some digraph \( D = (V,A) \) and some (directed) spanning forest \( T \subseteq A \) of \( D \) and sets *pisConetwork accordingly.

If \( M \) is a conetwork matrix and pdigraph != NULL, then one possible digraph \( D \) is computed and stored in *pdigraph. The caller must release its memory via CMRgraphFree. If in addition to pdigraph also pforestArcs != NULL (resp. pcoforestArcs != NULL), then a corresponding (directed) spanning forest \( T \) (resp. its complement \( A \setminus T \)) is stored in *pforestArcs (resp. *pcoforestArcs). The caller must release this memory via CMRfreeBlockArray.

Note: Retrieval of minimal non-conetwork submatrices via *psubmatrix is not implemented, yet.

Parameters

cmr	CMR environment.
matrix	Matrix \( M \).
pisConetwork	Returns true if and only if \( M \) is a conetwork matrix.
psupportIsCographic	Pointer for storing `true` if and only if the support matrix is cographic.
pdigraph	Pointer for storing `true` if and only if \( M \) is conetwork.
pforestArcs	Pointer for storing \( T \), indexed by the columns of \( M \) (if \( M \) is network).
pcoforestArcs	Pointer for storing \( A \setminus T \), indexed by the rows of \( M \) (if \( M \) is conetwork).
parcsReversed	Pointer for storing indicators which arcs are reversed for the correct sign (if \( M \) is conetwork).
psubmatrix	Pointer for storing a minimal non-conetwork submatrix (if \( M \) is not conetwork and such a matrix is found by coincidence).
stats	Pointer to statistics (may be `NULL`).
timeLimit	Time limit to impose.

Classes

Enumerations

Functions

Enumeration Type Documentation

◆ DIJKSTRA_STAGE

Function Documentation

◆ CMRnetworkComputeMatrix()

◆ CMRnetworkStatsInit()

◆ CMRnetworkStatsPrint()

◆ CMRnetworkTestMatrix()

◆ CMRnetworkTestTranspose()