#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 , 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. More...

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

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) \). More...

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

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

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.
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).
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).
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()