Detailed Description

methods for detecting network matrices and converting them to the underlying graphs

A matrix \(M \in \{-1,0,1\}^{m\times n} \) is a network matrix if there exists a directed graph \(G = (V,A)\) with \(|A| = m+n\) arcs and a spanning forest \(T\) with \(|T| = m\) such that \(M\)'s rows index \(T\) and \(M\)'s columns index \(A\setminus T\), and for each arc \( a = (u,v) \in A\setminus T\) and each arc \(t\in T\)

\[ M_{t,a} = \begin{cases} +1 & \textrm{if the unique } u-v \textrm{ path in } T \textrm{ passes through } a \textrm{ forwardly}, \\ -1 & \textrm{if the unique } u-v \textrm{ path in } T \textrm{ passes through } a \textrm{ backwardly}, \\ 0 & \textrm{if the unique } u-v \textrm{ path in } T \textrm{ does not pass through } a \end{cases} \]

holds.

The main difficulty with detecting network matrices is that there may exist many pairs of a graph and a spanning tree that realize a matrix. The algorithms in this file maintain and update an SPQR forest, which is a graph decomposition that represents all graphs that correspond to a given network matrix.

Note that all addition algorithms expect that each nonzero is given exactly once and not more often; in particular, it is up to the user to ensure this when interleaving column and row addition steps.

More details can be found in:

R.P. van der Hulst and M. Walter "A Row-wise Algorithm for Graph Realization"
R.E. Bixby and D.K. Wagner "An almost linear-time algorithm for graph realization"

Note that although these publications contain the methods for undirected graphs (and binary matrices), their ideas are relatively easily extended to directed graphs and ternary matrices. Implementation details are described in further detail in network.c

Typedefs
typedef struct SCIP_Netmatdec	SCIP_NETMATDEC

Functions
SCIP_RETCODE	SCIPnetmatdecCreate (BMS_BLKMEM blkmem, SCIP_NETMATDEC *pdec, int nrows, int ncols)

void	SCIPnetmatdecFree (SCIP_NETMATDEC **pdec)

SCIP_RETCODE	SCIPnetmatdecTryAddCol (SCIP_NETMATDEC dec, int column, int nonzrows, double nonzvals, int nnonzs, SCIP_Bool success)

SCIP_RETCODE	SCIPnetmatdecTryAddRow (SCIP_NETMATDEC dec, int row, int nonzcols, double nonzvals, int nnonzs, SCIP_Bool success)

SCIP_Bool	SCIPnetmatdecContainsRow (SCIP_NETMATDEC *dec, int row)

SCIP_Bool	SCIPnetmatdecContainsColumn (SCIP_NETMATDEC *dec, int column)

void	SCIPnetmatdecRemoveComponent (SCIP_NETMATDEC dec, int componentrows, int nrows, int *componentcols, int ncols)

SCIP_Bool	SCIPnetmatdecIsMinimal (SCIP_NETMATDEC *dec)

SCIP_Bool	SCIPnetmatdecVerifyCycle (BMS_BUFMEM bufmem, SCIP_NETMATDEC dec, int column, int nonzrowidx, double nonzvals, int nnonzs, int pathrowstorage, SCIP_Bool pathsignstorage)

SCIP_RETCODE	SCIPnetmatdecCreateDiGraph (SCIP_NETMATDEC dec, BMS_BLKMEM blkmem, SCIP_DIGRAPH **pdigraph, SCIP_Bool createrowarcs)

Typedef Documentation

◆ SCIP_NETMATDEC

typedef struct SCIP_Netmatdec SCIP_NETMATDEC

this class stores a decomposition of the network matrix using SPQR trees

Definition at line 85 of file pub_network.h.

Function Documentation

◆ SCIPnetmatdecCreate()

SCIP_RETCODE SCIPnetmatdecCreate	(	BMS_BLKMEM *	blkmem,
		SCIP_NETMATDEC **	pdec,
		int	nrows,
		int	ncols
	)

create an empty network matrix decomposition that can store a matrix with at most the given dimensions

Initially, the network matrix decomposition stores an empty submatrix

Parameters

blkmem	Block memory
pdec	buffer to store pointer to created decomposition
nrows	The maximal number of rows that the decomposition can expect
ncols	The maximal number of columns that the decomposition can expect

Definition at line 11566 of file network.c.

References BMSallocBlockMemory, SCIP_Netmatdec::coladd, SCIP_Netmatdec::dec, netMatDecDataCreate(), NULL, SCIP_Netmatdec::rowadd, SCIP_ALLOC, SCIP_CALL, and SCIP_OKAY.

Referenced by findImpliedIntegers().

◆ SCIPnetmatdecFree()

void SCIPnetmatdecFree ( SCIP_NETMATDEC ** pdec )

frees a network matrix decomposition

Parameters

pdec	pointer to the network matrix decomposition to free

Definition at line 11584 of file network.c.

References BMSfreeBlockMemory, SCIP_Netmatdec::coladd, SCIP_Netmatdec::dec, SCIP_NETMATDECDATA::env, netcoladdFree(), netMatDecDataFree(), netrowaddFree(), NULL, and SCIP_Netmatdec::rowadd.

Referenced by findImpliedIntegers().

◆ SCIPnetmatdecTryAddCol()

SCIP_RETCODE SCIPnetmatdecTryAddCol	(	SCIP_NETMATDEC *	dec,
		int	column,
		int *	nonzrows,
		double *	nonzvals,
		int	nnonzs,
		SCIP_Bool *	success
	)

tries to add a given column to the network matrix. Any nonzero row indices in the column that are not yet in the network matrix decomposition are added, too.

Note: Each column and row may be added only once. Trying to add a column that is already in the decomposition will result in an error.

Note that the first call to this method for a given decomposition may be a bit slower, due to memory initialization.

Parameters

dec	Network matrix decomposition
column	The column to add
nonzrows	The column's nonzero row indices
nonzvals	The column's nonzero entries
nnonzs	The number of nonzeros in the column
success	Buffer to store whether the column was added

Definition at line 11603 of file network.c.

References SCIP_Netmatdec::coladd, SCIP_Netmatdec::dec, SCIP_NETMATDECDATA::env, netcoladdAdd(), netcoladdCheck(), netcoladdCreate(), netcoladdRemainsNetwork(), NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by findImpliedIntegers().

◆ SCIPnetmatdecTryAddRow()

SCIP_RETCODE SCIPnetmatdecTryAddRow	(	SCIP_NETMATDEC *	dec,
		int	row,
		int *	nonzcols,
		double *	nonzvals,
		int	nnonzs,
		SCIP_Bool *	success
	)

tries to add a given row to the network matrix. Any nonzero column indices in the row that are not yet in the network matrix decomposition are added, too.

Note: Each column and row may be added only once. Trying to add a row that is already in the decomposition will result in an error.

Note that the first call to this method for a given decomposition may be a bit slower, due to memory initialization.

If the user is only interested in determining if a certain (sub)matrix is network or not, using SCIPnetmatdecTryAddCol() will generally be faster, unless the (sub)matrix has many more columns than rows.

Parameters

dec	Network matrix decomposition
row	The row to add
nonzcols	The row's nonzero column indices
nonzvals	The row's nonzero entries
nnonzs	The number of nonzeros in the row
success	Buffer to store whether the row was added

Definition at line 11627 of file network.c.

References SCIP_Netmatdec::dec, SCIP_NETMATDECDATA::env, netrowaddAdd(), netrowaddCheck(), netrowaddCreate(), netrowaddRemainsNetwork(), NULL, SCIP_Netmatdec::rowadd, SCIP_CALL, and SCIP_OKAY.

Referenced by findImpliedIntegers().

◆ SCIPnetmatdecContainsRow()

SCIP_Bool SCIPnetmatdecContainsRow	(	SCIP_NETMATDEC *	dec,
		int	row
	)

checks if the network matrix decomposition contains the given row

Parameters

dec	The network matrix decomposition
row	The row index that is checked

Definition at line 11651 of file network.c.

References SCIP_Netmatdec::dec, and netMatDecDataContainsRow().

Referenced by findImpliedIntegers().

◆ SCIPnetmatdecContainsColumn()

SCIP_Bool SCIPnetmatdecContainsColumn	(	SCIP_NETMATDEC *	dec,
		int	column
	)

checks if the network matrix decomposition contains the given column

Parameters

dec	The network matrix decomposition
column	The column index that is checked

Definition at line 11659 of file network.c.

References SCIP_Netmatdec::dec, and netMatDecDataContainsColumn().

Referenced by findImpliedIntegers().

◆ SCIPnetmatdecRemoveComponent()

void SCIPnetmatdecRemoveComponent	(	SCIP_NETMATDEC *	dec,
		int *	componentrows,
		int	nrows,
		int *	componentcols,
		int	ncols
	)

removes a connected component of the matrix from the network decomposition

Note: This method is 'stupid', and does not delete the associated graph data structure in the decomposition. Moreover, it does not explicitly check if the rows/columns that the user provides are a connected component of the submatrix given by the decomposition. If this is not the case, this will lead to buggy behavior. Use with care!

Parameters

dec	The network matrix decomposition
componentrows	Array of rows to delete
nrows	The number of rows to delete
componentcols	Array of columns to delete
ncols	The number of columns to delete

Definition at line 11667 of file network.c.

References SCIP_Netmatdec::dec, and netMatDecDataRemoveComponent().

Referenced by findImpliedIntegers().

◆ SCIPnetmatdecIsMinimal()

SCIP_Bool SCIPnetmatdecIsMinimal ( SCIP_NETMATDEC * dec )

checks if the network matrix decomposition is minimal.

A network matrix decomposition is minimal if it does not contain adjacent parallel or series skeletons. The network matrix decomposition we compute should always be minimal. This method should only be used in tests or asserts.

Parameters

dec	The network matrix decomposition

Definition at line 11678 of file network.c.

References SCIP_Netmatdec::dec, and netMatDecDataIsMinimal().

◆ SCIPnetmatdecVerifyCycle()

SCIP_Bool SCIPnetmatdecVerifyCycle	(	BMS_BUFMEM *	bufmem,
		SCIP_NETMATDEC *	dec,
		int	column,
		int *	nonzrowidx,
		double *	nonzvals,
		int	nnonzs,
		int *	pathrowstorage,
		SCIP_Bool *	pathsignstorage
	)

checks if the cycle stored in the Decomposition matches the given array

This method should only be used in tests

Parameters

bufmem	Buffer memory
dec	The network matrix decomposition
column	The column to check
nonzrowidx	Array with the column's nonzero row indices
nonzvals	Array with the column's nonzero values
nnonzs	Number of nonzeros in the column
pathrowstorage	A buffer to hold the computed path's rows. Should have size equal or greater than the number of rows in the decomposition.
pathsignstorage	A buffer to store the computed path's row signs. Should have size equal or greater than the number of rows in the decomposition.

Definition at line 11685 of file network.c.

References SCIP_Netmatdec::dec, and netMatDecDataVerifyCycle().

◆ SCIPnetmatdecCreateDiGraph()

SCIP_RETCODE SCIPnetmatdecCreateDiGraph	(	SCIP_NETMATDEC *	dec,
		BMS_BLKMEM *	blkmem,
		SCIP_DIGRAPH **	pdigraph,
		SCIP_Bool	createrowarcs
	)

Constructs a realization of an underlying directed graph belonging to the network matrix.

The arc data of the digraph contains the row/column indices of the graph. If index < nrows, then the index is the corresponding row. If the index >= nrows, then index-nrows is the column index. Since many different realizations are possible, we use the default orientation of the two-separations to associate pairs of nodes to each other. In particular, we choose to connect the nodes of different 2-connected components in node 0. This way, the rank of the underlying matrix is equal to m+1-c, where c is the number of undirected connected components of the graph where the row/tree edges have been left out.

Parameters

dec	The network matrix decomposition
blkmem	The block memory to use for the created digraph
pdigraph	Pointer to the pointer to store the created digraph
createrowarcs	Should the row arcs be added to the created digraph?

Definition at line 11701 of file network.c.

References SCIP_Netmatdec::dec, and netMatDecDataCreateDiGraph().

SCIP

Detailed Description

Typedefs

Functions

Typedef Documentation

◆ SCIP_NETMATDEC

Function Documentation

◆ SCIPnetmatdecCreate()

◆ SCIPnetmatdecFree()

◆ SCIPnetmatdecTryAddCol()

◆ SCIPnetmatdecTryAddRow()

◆ SCIPnetmatdecContainsRow()

◆ SCIPnetmatdecContainsColumn()

◆ SCIPnetmatdecRemoveComponent()

◆ SCIPnetmatdecIsMinimal()

◆ SCIPnetmatdecVerifyCycle()

◆ SCIPnetmatdecCreateDiGraph()