Detailed Description

Methods for detecting network (sub)matrices.

Author: Rolf van der Hulst

Detecting if a matrix is a network matrix can be quite complex. Below is an introductory text, which may help with navigating the functions and datastructures in this file by giving a general overview. More details can be found in; R.P. van der Hulst and M. Walter "A row-wise algorithm for graph realization" and R.E. Bixby and D.K. Wagner "An almost linear-time algorithm for graph realization" for the column-wise algorithm.

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 ambiguity of these graphs may be characterized in terms of \(k\)-separations on the graph associated to the network matrix. An edge partition \((E_1,E_2)\) is considered a \(k\)-separation if \(|E_i|\geq k \) holds for \(i\in\{1,2\}\). The ambiguity of network matrices is completely given by all the 1-separations and 2-separations of the associated graph(s). In particular, if the graph realizing a network matrix is 3-connected, then it is unique, up to inverting all edges of the graph.

A 1-separation given by edge sets \((E_1,E_2)\), which is given by a singular node that is referred to as an articulation node, implies that no column of the network matrix contains edges in both \(E_1\) and \(E_2\). Remember that each edge in a realizing graph is associated with a row or column of the network matrix. Then, we have a 1-separation exactly when the network matrix contains two (or more) disconnected blocks, where the rows and columns of each block are contained in either \(E_1\) or \(E_2\). To obtain a graph realizing our network matrix, we can attach the graph realizing \(E_2\) at any node of the graph realizing \(E_1\). Thus, we store the graphs corresponding to the connected blocks of the network matrix separately. Each block has a 2-connected realization graph.

If a graph \(G\) realizing the network matrix has a 2-separation \((E_1,E_2)\) at vertices u and v, then we can obtain another graph representing the network matrix, by inverting the direction of all edges in \(E_2\) and replacing u by v and vice-versa. One can also imagine adding a virtual edge \(e'=\{u,v\}\) to both E_1 and E_2. In the trivial realization, we simply map the head of \(e'\) in \(E_1\) to the head of \(e'\) in \(E_2\) and remove \(e'\) from both graphs. In the second realization we do the same thing, but first invert all the edges in \(E_2\), including \(e'\). An SPQR tree \(\mathcal{T}=(\mathcal{V},\mathcal{E})\) is a tree data structure that represents the structure of all 2-separations in a 2-connected graph. Each member \(\nu\in\mathcal{V}\) has an associated skeleton graph that has one of four different types:

(S) The member's skeleton graph is a cycle with at least 3 edges (also referred to as series or polygon)
(P) The member's skeleton graph consists of at least 3 parallel edges and 2 nodes (also referred to as bond)
(Q) The member's skeleton graph consists of at most 2 edges connecting two nodes (also referred to as loop)
(R) The member's skeleton graph is 3-connected and consists of at least 4 edges.

An SPQR tree is considered minimal if it has no P-P or S-S connections. Each connected matrix has a unique minimal SPQR tree. Each edge \(\{\nu,\mu\}\in\mathcal{E}\) defines a 2-separation of the underlying graph. In particular, each edge has one virtual edge in the member graph that it connects to the other member graph in the edge.

We can obtain a realization of the graph underlying the network matrix by doing the following operations:

Permute the edges of each (S)-member arbitrarily
For each edge in \(\mathcal{E}\), pick one of the two orientations of the virtual edges and merge the adjacent member graphs accordingly.

In this way, all the graphs given by the network matrix are represented. In order to efficiently perform the merge of two member graphs, the member and node labels are given by union-find datastructures. Additionally, we also introduce a signed-union-find datastructure on the arcs of the graphs, so that we can efficiently invert the arcs of one side of a 2-separation. The 1-separations can be handled by storing an SPQR forest, with a (minimal) SPQR tree for every connected block of the network matrix.

For adding a column to the network matrix, one can show that one can add a column only if the nonzeros of the column form a path with the correct signs in some graph represented by the network matrix. We solve the problem for each graph represented by the network matrix simultaneously by decomposing over the SPQR tree. First, we compute the path in each member. Then, we attempt to combine the paths by orienting the 2-separations so that the different member paths form a path in the represented graph. If some member has a set of edges that do not form a path, we can terminate. An important step is 'propagation'; when we are in a leaf node of the sub-SPQR tree containing path edges and the path in our leaf node forms a cycle with the virtual arc e connecting to the rest of the sub-tree, then we can remove the leaf node from the SPQR tree and mark the virtual arc f that is paired with e. After performing all such propagations, the sub-SPQR tree should form a path. Then, we merge these members into one, forming a single path. By adding the new column edge to the end nodes of this path, we form a new member of type R. Finally, we can easily join the paths of multiple SPQR trees using a series node to obtain the final path.

The ideas for the row-wise algorithm have many parallels with the column-wise algorithm. One can add a row to a network matrix if and only if a node is 'splittable' with respect to a certain auxiliary graph formed by the nonzero columns indices of the row, for a graph represented by the network matrix. In particular, this auxiliary graph must be a directed bipartite graph; then, the arcs incident to the given node can be reassigned to two new nodes, so that the paths of the columns corresponding to the nonzeros of the row can be elongated to contain the new row, which is placed between the two new nodes. Similarly to the column-case, splittability of each graph represented by the network matrix can be computed at once by computing the splittability (and the corresponding bipartition) of every member graph. Similarly to the column algorithm, we can propagate; If a member is a leaf of the SPQR tree and both nodes of the 2-separation connecting it to the rest of graph are splittable, then we can remove the leaf from the reduced SPQR tree and mark the virtual edge connecting to the subtree. Finally, we are left with some minimal subtree with splittable vertices for each member graph. If we can merge all splittable vertices of the member graphs in the subtree into a single splittable vertex, then we perform this merge, and split this vertex. This yields us a new, larger node of type R (rigid).

Implementation notes:

Quite a few algorithms used for network matrix detection are recursive in nature. However, recursive calls can cause stack overflows, particularly with large graphs. Quite frequently in the code, we need to allocate the call-data of these algorithms on the heap, instead, and use while loops to simulate the recursion.
In order to make the code fast in practice, a lot of emphasis is put on reusing allocated memory and avoiding allocations. In particular for the column-wise algorithm, even allocating and zeroing an array of size m+n for an m x n matrix can significantly slow down the code!
The graphs of the S, P and Q members do not need to be stored explicitly, as they always have the same structure. This also makes it easier to permute edges of S nodes on the fly.

Definition in file network.c.

#include <assert.h>
#include "scip/misc.h"
#include "scip/pub_misc.h"
#include "scip/pub_network.h"
#include "scip/scip.h"
#include "blockmemshell/memory.h"

Go to the source code of this file.

Data Structures
struct	SPQRNetworkDecompositionArcListNode

struct	SPQRNetworkDecompositionNode

struct	SPQRNetworkDecompositionArc

struct	SPQRNetworkDecompositionMember

struct	SCIP_NETMATDECDATA

struct	ArcSign

struct	FindCycleCall

struct	PathArcListNode

struct	SPQRColReducedMember

struct	SPQRColReducedComponent

struct	MemberInfo

struct	CreateReducedMembersCallstack

struct	SCIP_NETCOLADD

struct	NewColInformation

struct	CutArcListNode

struct	ArticulationNodeInformation

struct	DFSCallData

struct	MergeTreeCallData

struct	ColorDFSCallData

struct	ArticulationPointCallStack

struct	SPQRRowReducedMember

struct	SPQRRowReducedComponent

struct	SCIP_NETROWADD

struct	NewRowInformation

struct	Nodes

struct	SplitOrientation

struct	SCIP_Netmatdec

Macros
#define	SPQR_INVALID INT_MAX

#define	SPQR_INVALID_ROW SPQR_INVALID

#define	SPQR_INVALID_COL SPQR_INVALID

#define	MARKER_ROW_ELEMENT (INT_MIN)

#define	MARKER_COLUMN_ELEMENT (INT_MAX)

#define	SPQR_INVALID_MEMBER (-1)

#define	SPQR_INVALID_NODE (-1)

#define	SPQR_INVALID_ARC (-1)

#define	INVALID_PATH_ARC (-1)

#define	INVALID_REDUCED_MEMBER (-1)

#define	NEWCOLINFORMATION_EMPTY { SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, SPQR_INVALID_NODE, SPQR_INVALID_ARC, FALSE }

#define	INVALID_CUT_ARC (-1)

#define	NEWROWINFORMATION_EMPTY { SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, SPQR_INVALID_NODE, SPQR_INVALID_ARC, FALSE }

Typedefs
typedef int	spqr_matrix_size

typedef spqr_matrix_size	spqr_row

typedef spqr_matrix_size	spqr_col

typedef int	spqr_element

typedef int	spqr_member

typedef int	spqr_node

typedef int	spqr_arc

typedef int	path_arc_id

typedef int	reduced_member_id

typedef int	children_idx

typedef int	cut_arc_id

Enumerations
enum	SPQRMemberType { SPQR_MEMBERTYPE_RIGID = 0 , SPQR_MEMBERTYPE_PARALLEL = 1 , SPQR_MEMBERTYPE_SERIES = 2 , SPQR_MEMBERTYPE_LOOP = 3 , SPQR_MEMBERTYPE_UNASSIGNED = 4 }

enum	ReducedMemberType { REDUCEDMEMBER_TYPE_UNASSIGNED = 0 , REDUCEDMEMBER_TYPE_CYCLE = 1 , REDUCEDMEMBER_TYPE_MERGED = 2 , REDUCEDMEMBER_TYPE_NOT_NETWORK = 3 }

enum	MemberPathType { INTO_HEAD = 0 , INTO_TAIL = 1 , OUT_HEAD = 2 , OUT_TAIL = 3 }

enum	RowReducedMemberType { TYPE_UNDETERMINED = 0 , TYPE_PROPAGATED = 1 , TYPE_MERGED = 2 , TYPE_NOT_NETWORK = 3 }

enum	COLOR_STATUS { UNCOLORED = 0 , COLOR_SOURCE = 1 , COLOR_SINK = 2 }

Functions
static SCIP_Bool	SPQRrowIsInvalid (spqr_row row)

static SCIP_Bool	SPQRcolIsInvalid (spqr_col col)

static SCIP_Bool	SPQRrowIsValid (spqr_row row)

static SCIP_Bool	SPQRcolIsValid (spqr_col col)

static SCIP_Bool	SPQRelementIsRow (spqr_element element)

static SCIP_Bool	SPQRelementIsColumn (spqr_element element)

static spqr_row	SPQRelementToRow (spqr_element element)

static spqr_element	SPQRrowToElement (spqr_row row)

static spqr_col	SPQRelementToColumn (spqr_element element)

static spqr_element	SPQRcolumnToElement (spqr_col column)

static SCIP_Bool	SPQRmemberIsInvalid (spqr_member member)

static SCIP_Bool	SPQRmemberIsValid (spqr_member member)

static SCIP_Bool	SPQRnodeIsInvalid (spqr_node node)

static SCIP_Bool	SPQRnodeIsValid (spqr_node node)

static SCIP_Bool	SPQRarcIsInvalid (spqr_arc arc)

static SCIP_Bool	SPQRarcIsValid (spqr_arc arc)

static SCIP_Bool	nodeIsRepresentative (const SCIP_NETMATDECDATA *dec, spqr_node node)

static spqr_node	findNode (SCIP_NETMATDECDATA *dec, spqr_node node)

static spqr_node	findNodeNoCompression (const SCIP_NETMATDECDATA *dec, spqr_node node)

static spqr_node	findArcTail (SCIP_NETMATDECDATA *dec, spqr_arc arc)

static spqr_node	findArcHead (SCIP_NETMATDECDATA *dec, spqr_arc arc)

static spqr_node	findArcHeadNoCompression (const SCIP_NETMATDECDATA *dec, spqr_arc arc)

static spqr_node	findArcTailNoCompression (const SCIP_NETMATDECDATA *dec, spqr_arc arc)

static spqr_arc	getFirstNodeArc (const SCIP_NETMATDECDATA *dec, spqr_node node)

static spqr_arc	getNextNodeArcNoCompression (const SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node node)

static spqr_arc	getNextNodeArc (SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node node)

static spqr_arc	getPreviousNodeArc (SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node node)

static void	mergeNodeArcList (SCIP_NETMATDECDATA *dec, spqr_node toMergeInto, spqr_node toRemove)

static void	arcFlipReversed (SCIP_NETMATDECDATA *dec, spqr_arc arc)

static void	arcSetReversed (SCIP_NETMATDECDATA *dec, spqr_arc arc, SCIP_Bool reversed)

static void	arcSetRepresentative (SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_arc representative)

static spqr_node	mergeNodes (SCIP_NETMATDECDATA *dec, spqr_node first, spqr_node second)

static SCIP_Bool	memberIsRepresentative (const SCIP_NETMATDECDATA *dec, spqr_member member)

static spqr_member	findMember (SCIP_NETMATDECDATA *dec, spqr_member member)

static spqr_member	findMemberNoCompression (const SCIP_NETMATDECDATA *dec, spqr_member member)

static spqr_member	mergeMembers (SCIP_NETMATDECDATA *dec, spqr_member first, spqr_member second)

static spqr_member	findArcMember (SCIP_NETMATDECDATA *dec, spqr_arc arc)

static spqr_member	findArcMemberNoCompression (const SCIP_NETMATDECDATA *dec, spqr_arc arc)

static spqr_member	findMemberParent (SCIP_NETMATDECDATA *dec, spqr_member member)

static spqr_member	findMemberParentNoCompression (const SCIP_NETMATDECDATA *dec, spqr_member member)

static spqr_member	findArcChildMember (SCIP_NETMATDECDATA *dec, spqr_arc arc)

static spqr_member	findArcChildMemberNoCompression (const SCIP_NETMATDECDATA *dec, spqr_arc arc)

static SCIP_Bool	arcIsChildMarker (const SCIP_NETMATDECDATA *dec, spqr_arc arc)

static SCIP_Bool	arcIsTree (const SCIP_NETMATDECDATA *dec, spqr_arc arc)

static SCIP_Bool	arcIsRepresentative (const SCIP_NETMATDECDATA *dec, spqr_arc arc)

static ArcSign	findArcSign (SCIP_NETMATDECDATA *dec, spqr_arc arc)

static ArcSign	findArcSignNoCompression (const SCIP_NETMATDECDATA *dec, spqr_arc arc)

static spqr_node	findEffectiveArcHead (SCIP_NETMATDECDATA *dec, spqr_arc arc)

static spqr_node	findEffectiveArcTail (SCIP_NETMATDECDATA *dec, spqr_arc arc)

static spqr_node	findEffectiveArcHeadNoCompression (const SCIP_NETMATDECDATA *dec, spqr_arc arc)

static spqr_node	findEffectiveArcTailNoCompression (const SCIP_NETMATDECDATA *dec, spqr_arc arc)

static spqr_arc	mergeArcSigns (SCIP_NETMATDECDATA *dec, spqr_arc first, spqr_arc second, SCIP_Bool reflectRelative)

static SCIP_Bool	arcIsReversedNonRigid (const SCIP_NETMATDECDATA *dec, spqr_arc arc)

static spqr_element	arcGetElement (const SCIP_NETMATDECDATA *dec, spqr_arc arc)

static SCIP_Bool	netMatDecDataContainsRow (SCIP_NETMATDECDATA *dec, int row)

static SCIP_Bool	netMatDecDataContainsColumn (SCIP_NETMATDECDATA *dec, int column)

static void	setDecompositionColumnArc (SCIP_NETMATDECDATA *dec, spqr_col col, spqr_arc arc)

static void	setDecompositionRowArc (SCIP_NETMATDECDATA *dec, spqr_row row, spqr_arc arc)

static spqr_arc	getDecompositionColumnArc (const SCIP_NETMATDECDATA *dec, spqr_col col)

static spqr_arc	getDecompositionRowArc (const SCIP_NETMATDECDATA *dec, spqr_row row)

static SCIP_RETCODE	netMatDecDataCreate (BMS_BLKMEM blkmem, SCIP_NETMATDECDATA *pdec, int nrows, int ncols)

static void	netMatDecDataFree (SCIP_NETMATDECDATA **pdec)

static spqr_arc	getFirstMemberArc (const SCIP_NETMATDECDATA *dec, spqr_member member)

static spqr_arc	getNextMemberArc (const SCIP_NETMATDECDATA *dec, spqr_arc arc)

static spqr_arc	getPreviousMemberArc (const SCIP_NETMATDECDATA *dec, spqr_arc arc)

static void	addArcToMemberArcList (SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_member member)

static SCIP_RETCODE	createArc (SCIP_NETMATDECDATA dec, spqr_member member, SCIP_Bool reversed, spqr_arc pArc)

static SCIP_RETCODE	createRowArc (SCIP_NETMATDECDATA dec, spqr_member member, spqr_arc pArc, spqr_row row, SCIP_Bool reversed)

static SCIP_RETCODE	createColumnArc (SCIP_NETMATDECDATA dec, spqr_member member, spqr_arc pArc, spqr_col column, SCIP_Bool reversed)

static SCIP_RETCODE	createMember (SCIP_NETMATDECDATA dec, SPQRMemberType type, spqr_member pMember)

static SCIP_RETCODE	createNode (SCIP_NETMATDECDATA dec, spqr_node pNode)

static void	removeArcFromNodeArcList (SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node node, SCIP_Bool nodeIsHead)

static void	addArcToNodeArcList (SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node node, SCIP_Bool nodeIsHead)

static void	setArcHeadAndTail (SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node head, spqr_node tail)

static void	clearArcHeadAndTail (SCIP_NETMATDECDATA *dec, spqr_arc arc)

static void	changeArcHead (SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node oldHead, spqr_node newHead)

static void	changeArcTail (SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node oldTail, spqr_node newTail)

static int	nodeDegree (SCIP_NETMATDECDATA *dec, spqr_node node)

static SPQRMemberType	getMemberType (const SCIP_NETMATDECDATA *dec, spqr_member member)

static void	updateMemberType (const SCIP_NETMATDECDATA *dec, spqr_member member, SPQRMemberType type)

static spqr_arc	markerToParent (const SCIP_NETMATDECDATA *dec, spqr_member member)

static void	updateMemberParentInformation (SCIP_NETMATDECDATA *dec, const spqr_member newMember, const spqr_member toRemove)

static spqr_arc	markerOfParent (const SCIP_NETMATDECDATA *dec, spqr_member member)

static int	getNumMemberArcs (const SCIP_NETMATDECDATA *dec, spqr_member member)

static int	getNumNodes (const SCIP_NETMATDECDATA *dec)

static int	getNumMembers (const SCIP_NETMATDECDATA *dec)

static SCIP_RETCODE	createStandaloneParallel (SCIP_NETMATDECDATA dec, spqr_col columns, SCIP_Bool reversed, int num_columns, spqr_row row, spqr_member pMember)

static SCIP_RETCODE	createConnectedParallel (SCIP_NETMATDECDATA dec, spqr_col columns, SCIP_Bool reversed, int num_columns, spqr_row row, spqr_member pMember)

static SCIP_RETCODE	createStandaloneSeries (SCIP_NETMATDECDATA dec, spqr_row rows, SCIP_Bool reversed, int numRows, spqr_col col, spqr_member pMember)

static SCIP_RETCODE	createConnectedSeries (SCIP_NETMATDECDATA dec, spqr_row rows, SCIP_Bool reversed, int numRows, spqr_col col, spqr_member pMember)

static void	removeArcFromMemberArcList (SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_member member)

static void	process_arc (spqr_row cyclearcs, int num_cycle_arcs, FindCycleCall callStack, int callStackSize, spqr_arc arc, const SCIP_NETMATDECDATA dec, SCIP_Bool cycledir, SCIP_Bool arcIsReversed)

static int	decompositionGetFundamentalCycleRows (const SCIP_NETMATDECDATA dec, spqr_col column, spqr_row output, SCIP_Bool *computedSignStorage)

static SCIP_Bool	netMatDecDataVerifyCycle (BMS_BUFMEM bufmem, const SCIP_NETMATDECDATA dec, int column, const int nonzrowidx, const double nonzvals, int num_rows, int pathrowstorage, SCIP_Bool pathsignstorage)

static spqr_member	largestMemberID (const SCIP_NETMATDECDATA *dec)

static spqr_arc	largestArcID (const SCIP_NETMATDECDATA *dec)

static spqr_node	largestNodeID (const SCIP_NETMATDECDATA *dec)

static int	numConnectedComponents (const SCIP_NETMATDECDATA *dec)

static SCIP_RETCODE	createChildMarker (SCIP_NETMATDECDATA dec, spqr_member member, spqr_member child, SCIP_Bool isTree, spqr_arc pArc, SCIP_Bool reversed)

static SCIP_RETCODE	createParentMarker (SCIP_NETMATDECDATA dec, spqr_member member, SCIP_Bool isTree, spqr_member parent, spqr_arc parentMarker, spqr_arc arc, SCIP_Bool reversed)

static SCIP_RETCODE	createMarkerPair (SCIP_NETMATDECDATA *dec, spqr_member parentMember, spqr_member childMember, SCIP_Bool parentIsTree, SCIP_Bool childMarkerReversed, SCIP_Bool parentMarkerReversed)

static SCIP_RETCODE	createMarkerPairWithReferences (SCIP_NETMATDECDATA dec, spqr_member parentMember, spqr_member childMember, SCIP_Bool parentIsTree, SCIP_Bool childMarkerReversed, SCIP_Bool parentMarkerReversed, spqr_arc parentToChild, spqr_arc *childToParent)

static void	moveArcToNewMember (SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_member oldMember, spqr_member newMember)

static void	mergeMemberArcList (SCIP_NETMATDECDATA *dec, spqr_member toMergeInto, spqr_member toRemove)

static void	changeLoopToSeries (SCIP_NETMATDECDATA *dec, spqr_member member)

static void	changeLoopToParallel (SCIP_NETMATDECDATA *dec, spqr_member member)

static SCIP_Bool	netMatDecDataIsMinimal (const SCIP_NETMATDECDATA *dec)

static void	decreaseNumConnectedComponents (SCIP_NETMATDECDATA *dec, int by)

static void	reorderComponent (SCIP_NETMATDECDATA *dec, spqr_member newRoot)

static void	netMatDecDataRemoveComponent (SCIP_NETMATDECDATA dec, const int componentRows, int numRows, const int *componentCols, int numCols)

static SCIP_RETCODE	mergeGivenMemberIntoParent (SCIP_NETMATDECDATA dec, spqr_member member, spqr_member parent, spqr_arc parentToChild, spqr_arc childToParent, SCIP_Bool headToHead, spqr_member mergedMember)

static SCIP_RETCODE	netMatDecDataCreateDiGraph (SCIP_NETMATDECDATA dec, BMS_BLKMEM blkmem, SCIP_DIGRAPH **pdigraph, SCIP_Bool createrowarcs)

static SCIP_Bool	pathArcIsInvalid (const path_arc_id arc)

static SCIP_Bool	pathArcIsValid (const path_arc_id arc)

static SCIP_Bool	reducedMemberIsInvalid (const reduced_member_id id)

static SCIP_Bool	reducedMemberIsValid (const reduced_member_id id)

static SCIP_Bool	isInto (MemberPathType type)

static SCIP_Bool	isHead (MemberPathType type)

static void	cleanupPreviousIteration (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol)

static SCIP_RETCODE	netcoladdCreate (BMS_BLKMEM blkmem, SCIP_NETCOLADD *pcoladd)

static void	netcoladdFree (BMS_BLKMEM blkmem, SCIP_NETCOLADD *pcoladd)

static reduced_member_id	createReducedMembersToRoot (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, const spqr_member firstMember)

static SCIP_RETCODE	constructReducedDecomposition (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol)

static void	cleanUpMemberInformation (SCIP_NETCOLADD *newCol)

static void	createPathArc (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, const spqr_arc arc, const reduced_member_id reducedMember, SCIP_Bool reversed)

static SCIP_RETCODE	createPathArcs (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol)

static SCIP_RETCODE	newColUpdateColInformation (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, spqr_col column, const spqr_row nonzeroRows, const double nonzeroValues, int numNonzeros)

static SCIP_RETCODE	computeLeafMembers (const SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol)

static void	determineRigidPath (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, SPQRColReducedMember *redMem)

static void	determineSingleRigidType (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, reduced_member_id reducedMember)

static void	determineSingleComponentType (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, reduced_member_id reducedMember)

static void	determinePathSeriesType (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, reduced_member_id reducedMember, spqr_member member, MemberPathType previousType, spqr_arc source, spqr_arc target)

static void	determinePathParallelType (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, reduced_member_id reducedMember, spqr_member member, MemberPathType previousType, spqr_arc source, spqr_arc target)

static void	determinePathRigidType (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, reduced_member_id reducedMember, MemberPathType previousType, spqr_arc source, spqr_arc target)

static void	determinePathMemberType (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, reduced_member_id reducedMember, spqr_member member, MemberPathType previousType, spqr_arc source, spqr_arc target)

static void	determinePathTypes (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, SPQRColReducedComponent *component)

static void	checkRigidLeaf (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, reduced_member_id leaf, spqr_arc toParent, reduced_member_id parent, spqr_arc toChild)

static ReducedMemberType	checkLeaf (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, reduced_member_id leaf, spqr_arc toParent, reduced_member_id parent, spqr_arc toChild)

static void	propagateCycles (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol)

static void	determineComponentTypes (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, SPQRColReducedComponent *component)

static SCIP_RETCODE	netcoladdCheck (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD coladd, int column, const int nonzrows, const double nonzvals, int nnonzs)

static void	setTerminalHead (NewColInformation *info, spqr_node node)

static void	setTerminalTail (NewColInformation *info, spqr_node node)

static void	setTerminalReversed (NewColInformation *info, SCIP_Bool reversed)

static void	setTerminalMember (NewColInformation *info, spqr_member member)

static void	setTerminalRepresentative (NewColInformation *info, spqr_arc representative)

static SCIP_RETCODE	splitParallel (SCIP_NETMATDECDATA dec, spqr_member parallel, spqr_arc arc1, spqr_arc arc2, spqr_member childParallel)

static SCIP_RETCODE	splitSeries (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, SPQRColReducedMember reducedMember, spqr_member member, spqr_member loopMember, NewColInformation *newColInfo)

static SCIP_RETCODE	splitSeriesMerging (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, SPQRColReducedMember reducedMember, spqr_member member, spqr_arc pathRepresentative, spqr_arc *nonPathRepresentative, spqr_arc exceptionArc1, spqr_arc exceptionArc2)

static SCIP_RETCODE	transformFirstPathMember (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, reduced_member_id reducedMember, NewColInformation newColInfo, spqr_arc representativeArc, spqr_member *mergedMember)

static SCIP_RETCODE	transformAndMergeParallel (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, reduced_member_id current, reduced_member_id next, spqr_member nextMember, SCIP_Bool nextIsParent, spqr_arc representativeArc, spqr_member mergedMember)

static SCIP_RETCODE	transformAndMergeSeries (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, reduced_member_id current, reduced_member_id next, spqr_member nextMember, SCIP_Bool nextIsParent, spqr_arc representativeArc, spqr_member mergedMember, NewColInformation *info)

static SCIP_RETCODE	transformAndMergeRigid (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, reduced_member_id current, reduced_member_id next, spqr_member nextMember, SCIP_Bool nextIsParent, spqr_arc representativeArc, spqr_member mergedMember, NewColInformation *info)

static SCIP_RETCODE	transformAndMerge (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, reduced_member_id current, reduced_member_id next, spqr_arc representativeArc, spqr_member mergedMember, SCIP_Bool nextIsParent, NewColInformation *info)

static SCIP_RETCODE	transformPath (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, SPQRColReducedComponent component, NewColInformation newColInfo)

static SCIP_RETCODE	columnTransformSingleParallel (SCIP_NETCOLADD newCol, reduced_member_id reducedMemberId, spqr_member member, NewColInformation newColInfo)

static SCIP_RETCODE	columnTransformSingleSeries (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, reduced_member_id reducedMemberId, spqr_member member, NewColInformation *newColInfo)

static SCIP_RETCODE	columnTransformSingleRigid (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, reduced_member_id reducedMemberId, spqr_member member, NewColInformation *newColInfo)

static SCIP_RETCODE	transformComponent (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol, SPQRColReducedComponent component, NewColInformation newColInfo)

static SCIP_Bool	netcoladdRemainsNetwork (const SCIP_NETCOLADD *newCol)

static SCIP_RETCODE	netcoladdAdd (SCIP_NETMATDECDATA dec, SCIP_NETCOLADD newCol)

static SCIP_Bool	cutArcIsInvalid (const cut_arc_id arc)

static SCIP_Bool	cutArcIsValid (const cut_arc_id arc)

static SCIP_RETCODE	newRowUpdateRowInformation (const SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const spqr_row row, const spqr_col columns, const double columnValues, const int numColumns)

static reduced_member_id	createRowReducedMembersToRoot (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const spqr_member firstMember)

static SCIP_RETCODE	constructRowReducedDecomposition (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow)

static void	createCutArc (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const spqr_arc arc, const reduced_member_id reducedMember, SCIP_Bool reversed)

static SCIP_RETCODE	createReducedDecompositionCutArcs (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow)

static SCIP_RETCODE	determineLeafReducedMembers (const SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow)

static SCIP_RETCODE	allocateRigidSearchMemory (const SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow)

static void	zeroOutColors (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const spqr_node firstRemoveNode)

static void	cleanUpPreviousIteration (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow)

static void	rigidFindStarNodes (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const reduced_member_id toCheck)

static void	zeroOutColorsExceptNeighbourhood (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const spqr_node articulationNode, const spqr_node startRemoveNode)

static void	intersectionOfAllPaths (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const reduced_member_id toCheck, int *const nodeNumPaths)

static void	addArticulationNode (SCIP_NETROWADD *newRow, spqr_node articulationNode)

static void	articulationPoints (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, ArticulationNodeInformation *nodeInfo, reduced_member_id reducedMember)

static void	rigidConnectedColoringRecursive (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, spqr_node articulationNode, spqr_node firstProcessNode, COLOR_STATUS firstColor, SCIP_Bool *isGood)

static void	rigidConnectedColoring (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const reduced_member_id reducedMember, const spqr_node node, SCIP_Bool *const isGood)

static spqr_node	checkNeighbourColoringArticulationNode (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const spqr_node articulationNode, spqr_arc *const adjacentSplittingArc)

static void	rigidGetSplittableArticulationPointsOnPath (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const reduced_member_id toCheck, spqr_node firstNode, spqr_node secondNode)

static void	determineParallelType (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const reduced_member_id toCheckMember, const spqr_arc markerToOther, const reduced_member_id otherMember, const spqr_arc markerToCheck)

static void	determineSeriesType (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const reduced_member_id toCheckMember, const spqr_arc markerToOther, const reduced_member_id otherMember, const spqr_arc markerToCheck)

static void	determineRigidType (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const reduced_member_id toCheckMember, const spqr_arc markerToOther, const reduced_member_id otherMember, const spqr_arc markerToCheck)

static RowReducedMemberType	determineType (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const reduced_member_id toCheckMember, const spqr_arc markerToOther, const reduced_member_id otherMember, const spqr_arc markerToCheck)

static void	propagateComponents (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow)

static Nodes	rigidDetermineCandidateNodesFromAdjacentComponents (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const reduced_member_id toCheck)

static SCIP_RETCODE	allocateTreeSearchMemory (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow)

static void	determineSingleRowRigidType (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id reducedMember)

static void	determineSingleParallelType (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id reducedMember)

static void	determineSingleSeriesType (SCIP_NETROWADD *newRow, reduced_member_id reducedMember)

static spqr_node	determineAndColorSplitNode (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id id, spqr_node candidateOne, spqr_node candidateTwo)

static void	determineSplitTypeFirstLeaf (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id reducedId)

static SplitOrientation	getRelativeOrientationRigid (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id reducedId, spqr_arc arcToNext)

static SplitOrientation	getRelativeOrientationParallel (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id reducedId, spqr_arc arcToNext)

static SplitOrientation	getRelativeOrientationSeries (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id reducedId, spqr_arc arcToNext)

static SplitOrientation	getRelativeOrientation (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id reducedId, spqr_arc arcToNext)

static void	determineSplitTypeSeries (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id reducedId, spqr_arc marker, SplitOrientation previousOrientation)

static void	determineSplitTypeParallel (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id reducedId, spqr_arc marker, SplitOrientation previousOrientation)

static void	determineSplitTypeRigid (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id reducedId, spqr_member member, spqr_arc marker, SplitOrientation previousOrientation)

static void	determineSplitTypeNext (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id current, reduced_member_id next, SCIP_Bool currentIsParent)

static void	determineMergeableTypes (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id root)

static void	cleanUpRowMemberInformation (SCIP_NETROWADD *newRow)

static SCIP_RETCODE	rigidTransformArcIntoCycle (SCIP_NETMATDECDATA dec, const spqr_member member, const spqr_arc arc, const SCIP_Bool reverseArcDirection, NewRowInformation const newRowInfo)

static SCIP_RETCODE	transformSingleRigid (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const reduced_member_id reducedMember, const spqr_member member, NewRowInformation *const newRowInfo)

static SCIP_RETCODE	splitParallelRowAddition (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const reduced_member_id reducedMember, const spqr_member member, NewRowInformation *const newRowInfo)

static SCIP_RETCODE	transformSingleParallel (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const reduced_member_id reducedMember, const spqr_member member, NewRowInformation *info)

static SCIP_RETCODE	splitSeriesMergingRowAddition (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, const reduced_member_id reducedMember, const spqr_member member, spqr_member const mergingMember, SCIP_Bool const isCut, spqr_arc *representativeEdge)

static SCIP_RETCODE	splitParallelMerging (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id reducedMember, spqr_member member, spqr_member const pMergeMember, spqr_arc const cutRepresentative)

static SCIP_RETCODE	splitFirstLeaf (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id leaf, NewRowInformation *const newRowInfo)

static SCIP_RETCODE	mergeSplitMemberIntoParent (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, spqr_member member, spqr_member parent, spqr_arc parentToChild, spqr_arc childToParent, SCIP_Bool headToHead, spqr_node parentNode, spqr_node childNode, spqr_member mergedMember, spqr_node arcNodeOne, spqr_node arcNodeTwo, spqr_node thirdNode)

static SCIP_RETCODE	splitAndMergeSeries (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id smallMember, SCIP_Bool largeIsParent, NewRowInformation *const newRowInfo, spqr_member member)

static SCIP_RETCODE	splitAndMergeParallel (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id smallMember, SCIP_Bool largeIsParent, NewRowInformation *const newRowInfo, spqr_member member)

static SCIP_RETCODE	splitAndMergeRigid (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id smallMember, SCIP_Bool largeIsParent, NewRowInformation *const newRowInfo, spqr_member member)

static SCIP_RETCODE	splitAndMerge (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id smallMember, SCIP_Bool largeIsParent, NewRowInformation *const newRowInfo)

static SCIP_RETCODE	mergeTree (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, reduced_member_id root, NewRowInformation *const newRowInfo)

static SCIP_RETCODE	transformComponentRowAddition (SCIP_NETMATDECDATA dec, SCIP_NETROWADD newRow, SPQRRowReducedComponent component, NewRowInformation const newRowInfo)

static SCIP_RETCODE	netrowaddCreate (BMS_BLKMEM blkmem, SCIP_NETROWADD *prowadd)

static void	netrowaddFree (BMS_BLKMEM blkmem, SCIP_NETROWADD *prowadd)

static SCIP_RETCODE	netrowaddCheck (SCIP_NETMATDECDATA dec, SCIP_NETROWADD rowadd, int row, const int nonzcols, const double nonzvals, int nnonzs)

static SCIP_RETCODE	netrowaddAdd (SCIP_NETMATDECDATA dec, SCIP_NETROWADD rowadd)

static SCIP_Bool	netrowaddRemainsNetwork (const SCIP_NETROWADD *rowadd)

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)

Macro Definition Documentation

◆ SPQR_INVALID

#define SPQR_INVALID INT_MAX

Definition at line 141 of file network.c.

◆ SPQR_INVALID_ROW

#define SPQR_INVALID_ROW SPQR_INVALID

Definition at line 142 of file network.c.

◆ SPQR_INVALID_COL

#define SPQR_INVALID_COL SPQR_INVALID

Definition at line 143 of file network.c.

◆ MARKER_ROW_ELEMENT

#define MARKER_ROW_ELEMENT (INT_MIN)

Columns 0..x correspond to elements 0..x and rows 0..y correspond to elements -1.. -y-1

Definition at line 188 of file network.c.

◆ MARKER_COLUMN_ELEMENT

#define MARKER_COLUMN_ELEMENT (INT_MAX)

Definition at line 189 of file network.c.

◆ SPQR_INVALID_MEMBER

#define SPQR_INVALID_MEMBER (-1)

Definition at line 260 of file network.c.

◆ SPQR_INVALID_NODE

#define SPQR_INVALID_NODE (-1)

Definition at line 285 of file network.c.

◆ SPQR_INVALID_ARC

#define SPQR_INVALID_ARC (-1)

Definition at line 313 of file network.c.

◆ INVALID_PATH_ARC

#define INVALID_PATH_ARC (-1)

Definition at line 3439 of file network.c.

◆ INVALID_REDUCED_MEMBER

#define INVALID_REDUCED_MEMBER (-1)

Definition at line 3480 of file network.c.

◆ NEWCOLINFORMATION_EMPTY

#define NEWCOLINFORMATION_EMPTY { SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, SPQR_INVALID_NODE, SPQR_INVALID_ARC, FALSE }

Definition at line 5498 of file network.c.

◆ INVALID_CUT_ARC

#define INVALID_CUT_ARC (-1)

Definition at line 6772 of file network.c.

◆ NEWROWINFORMATION_EMPTY

#define NEWROWINFORMATION_EMPTY { SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, SPQR_INVALID_NODE, SPQR_INVALID_ARC, FALSE }

Definition at line 7016 of file network.c.

Typedef Documentation

◆ spqr_matrix_size

typedef int spqr_matrix_size

Definition at line 137 of file network.c.

◆ spqr_row

typedef spqr_matrix_size spqr_row

Definition at line 138 of file network.c.

◆ spqr_col

typedef spqr_matrix_size spqr_col

Definition at line 139 of file network.c.

◆ spqr_element

typedef int spqr_element

Definition at line 190 of file network.c.

◆ spqr_member

typedef int spqr_member

spqr_member is an index for the members of the SPQR decomposition

The members are the nodes of the SPQR tree. Each member has an associated subgraph, sometimes called a skeleton. If two members are adjacent in the SPQR tree, the two corresponding subgraphs are connected by a 2-separation in any graph represented by the matrix. For members, we reserve all negative values as invalid. We use these negative values in union-find datastructure, where we store the rank of the representative as a negative number.

Definition at line 259 of file network.c.

◆ spqr_node

typedef int spqr_node

spqr_node is an index for the nodes stored in the decomposition.

The nodes are part of each member's skeleton. Similar to spqr_member, we reserve all negative values as invalid and use these in union-find.

Definition at line 284 of file network.c.

◆ spqr_arc

typedef int spqr_arc

spqr_arc is an index for the arcs stored in the decomposition.

The arcs are part of each member's skeleton. Similar to spqr_node and spqr_member, we reserve all negative values as invalid and use these in some union-find. However, in contrast to spqr_node and spqr_member, the union-find data structure does not represent the arcs, but rather if all arcs that have the same representative we know they are in the same member.

Definition at line 312 of file network.c.

◆ path_arc_id

typedef int path_arc_id

Path arcs are all those arcs that correspond to nonzeros of the column to be added.

Definition at line 3438 of file network.c.

◆ reduced_member_id

typedef int reduced_member_id

Index for the reduced members, which are the members of the sub-SPQR tree containing all path arcs.

Note that these are indexed separately from the members of the SPQR tree!

Definition at line 3479 of file network.c.

◆ children_idx

typedef int children_idx

Array index for the children of a reduced member

Definition at line 3501 of file network.c.

◆ cut_arc_id

typedef int cut_arc_id

Index type for the nonzeros of the new row, e.g. the columns whose tree path must be elongated with the new row

Definition at line 6771 of file network.c.

Enumeration Type Documentation

◆ SPQRMemberType

enum SPQRMemberType

The type of the member

Enumerator
SPQR_MEMBERTYPE_RIGID	The member's skeleton is 3-connected and has at least 4 edges
SPQR_MEMBERTYPE_PARALLEL	The member's skeleton consists of 2 nodes with at least 3 edges
SPQR_MEMBERTYPE_SERIES	The member's skeleton is a cycle with at least 3 edges
SPQR_MEMBERTYPE_LOOP	The member's skeleton consists of 2 nodes connected by 1 or 2 edges
SPQR_MEMBERTYPE_UNASSIGNED	To indicate that the member is not a representative member anymore

Definition at line 334 of file network.c.

◆ ReducedMemberType

enum ReducedMemberType

Type of the member, signifies to what degree we processed the member and how to treat with it when updating the graph.

Enumerator
REDUCEDMEMBER_TYPE_UNASSIGNED	We have not yet decided if the reduced member contains a valid path
REDUCEDMEMBER_TYPE_CYCLE	The reduced member is a leaf node of the SPQR tree and contains a path that forms a cycle with the corresponding virtual edge, i.e. it is propagated
REDUCEDMEMBER_TYPE_MERGED	The reduced member contains a path and is not propagated
REDUCEDMEMBER_TYPE_NOT_NETWORK	The reduced member does not have a valid path or can not be oriented to form a valid path with the other members.

Definition at line 3506 of file network.c.

◆ MemberPathType

enum MemberPathType

Defines the structure of the path in the reduced member

Enumerator
INTO_HEAD	The directed path goes into the head of the virtual arc
INTO_TAIL	The directed path goes into the tail of the virtual arc
OUT_HEAD	The directed path goes out of the head of the virtual arc
OUT_TAIL	The directed path goes out of the tail of the virtual arc

Definition at line 3518 of file network.c.

◆ RowReducedMemberType

enum RowReducedMemberType

Type of the reduced member

Indicates whether the member is processed, and whether it should be merged or left the same.

Enumerator
TYPE_UNDETERMINED	The type of this member has not yet been determined
TYPE_PROPAGATED	The member contains cut arcs, but should not be merged
TYPE_MERGED	This member should be merged into a rigid member
TYPE_NOT_NETWORK	This member implies that the addition of the new row does not create a network matrix

Definition at line 6811 of file network.c.

◆ COLOR_STATUS

enum COLOR_STATUS

Colors assigned to the node in the partitioning algorithm.

It must either be in the source or the sink partition.

Enumerator
UNCOLORED	The current node has not yet been processed
COLOR_SOURCE	The current node belongs to the source partition
COLOR_SINK	The current node belongs to the sink partition

Definition at line 6862 of file network.c.

Function Documentation

◆ SPQRrowIsInvalid()

static SCIP_Bool SPQRrowIsInvalid ( spqr_row row )

static

Determine if the row index is invalid

Parameters

row	The row to check

Definition at line 151 of file network.c.

References SPQR_INVALID_ROW.

Referenced by SPQRrowIsValid().

◆ SPQRcolIsInvalid()

static SCIP_Bool SPQRcolIsInvalid ( spqr_col col )

static

Determine if the column index is invalid

Parameters

col	The column to check

Definition at line 160 of file network.c.

References SPQR_INVALID_COL.

Referenced by SPQRcolIsValid().

◆ SPQRrowIsValid()

static SCIP_Bool SPQRrowIsValid ( spqr_row row )

static

Determine if the row index is valid

Parameters

row	The row to check

Definition at line 169 of file network.c.

References SPQRrowIsInvalid().

Referenced by getDecompositionRowArc(), netMatDecDataContainsRow(), setDecompositionRowArc(), and SPQRrowToElement().

◆ SPQRcolIsValid()

static SCIP_Bool SPQRcolIsValid ( spqr_col col )

static

Determine if the column index is valid

Parameters

col	The column to check

Definition at line 178 of file network.c.

References SPQRcolIsInvalid().

Referenced by getDecompositionColumnArc(), netMatDecDataContainsColumn(), setDecompositionColumnArc(), and SPQRcolumnToElement().

◆ SPQRelementIsRow()

static SCIP_Bool SPQRelementIsRow ( spqr_element element )

static

Checks if an element is a row

Parameters

element The element to check

Definition at line 194 of file network.c.

Referenced by arcIsTree(), netMatDecDataCreateDiGraph(), process_arc(), SPQRelementIsColumn(), and SPQRelementToRow().

◆ SPQRelementIsColumn()

static SCIP_Bool SPQRelementIsColumn ( spqr_element element )

static

Checks if an element is a column

Parameters

element The element to check

Definition at line 203 of file network.c.

References SPQRelementIsRow().

Referenced by columnTransformSingleRigid(), rigidTransformArcIntoCycle(), and SPQRelementToColumn().

◆ SPQRelementToRow()

static spqr_row SPQRelementToRow ( spqr_element element )

static

Convert an element to the corresponding row index

Parameters

element The element to convert

Definition at line 212 of file network.c.

References SPQRelementIsRow().

Referenced by columnTransformSingleRigid(), netMatDecDataCreateDiGraph(), process_arc(), and rigidTransformArcIntoCycle().

◆ SPQRrowToElement()

static spqr_element SPQRrowToElement ( spqr_row row )

static

Convert a row to the corresponding element

Parameters

row	The row to convert

Definition at line 222 of file network.c.

References SPQRrowIsValid().

Referenced by createRowArc().

◆ SPQRelementToColumn()

static spqr_col SPQRelementToColumn ( spqr_element element )

static

Convert an element to the corresponding column index

Parameters

element The element to convert

Definition at line 232 of file network.c.

References SPQRelementIsColumn().

Referenced by columnTransformSingleRigid(), netMatDecDataCreateDiGraph(), and rigidTransformArcIntoCycle().

◆ SPQRcolumnToElement()

static spqr_element SPQRcolumnToElement ( spqr_col column )

static

Convert a column to the corresponding element

Parameters

column The column to convert

Definition at line 242 of file network.c.

References SPQRcolIsValid().

Referenced by createColumnArc().

◆ SPQRmemberIsInvalid()

static SCIP_Bool SPQRmemberIsInvalid ( spqr_member member )

static

Check if a member is invalid

Parameters

member The member to check

Definition at line 264 of file network.c.

Referenced by createArc(), findMemberParent(), findMemberParentNoCompression(), memberIsRepresentative(), netMatDecDataCreateDiGraph(), and SPQRmemberIsValid().

◆ SPQRmemberIsValid()

static SCIP_Bool SPQRmemberIsValid ( spqr_member member )

static

Check if a member is valid

Parameters

member The member to check

Definition at line 272 of file network.c.

References SPQRmemberIsInvalid().

Referenced by arcIsChildMarker(), changeLoopToParallel(), changeLoopToSeries(), columnTransformSingleRigid(), constructReducedDecomposition(), constructRowReducedDecomposition(), createReducedMembersToRoot(), createRowReducedMembersToRoot(), determinePathParallelType(), determinePathSeriesType(), findMember(), findMemberNoCompression(), findMemberParent(), findMemberParentNoCompression(), getFirstMemberArc(), getMemberType(), getNumMemberArcs(), markerOfParent(), markerToParent(), memberIsRepresentative(), mergeGivenMemberIntoParent(), mergeSplitMemberIntoParent(), moveArcToNewMember(), netMatDecDataIsMinimal(), propagateComponents(), propagateCycles(), reorderComponent(), splitParallel(), splitParallelRowAddition(), splitSeries(), splitSeriesMerging(), and updateMemberType().

◆ SPQRnodeIsInvalid()

static SCIP_Bool SPQRnodeIsInvalid ( spqr_node node )

static

Check if a node is invalid

Parameters

node	The node to check

Definition at line 289 of file network.c.

Referenced by determineAndColorSplitNode(), determineRigidType(), determineSingleRowRigidType(), determineSplitTypeFirstLeaf(), determineSplitTypeRigid(), nodeIsRepresentative(), rigidDetermineCandidateNodesFromAdjacentComponents(), rigidFindStarNodes(), rigidGetSplittableArticulationPointsOnPath(), setTerminalHead(), setTerminalTail(), and SPQRnodeIsValid().

◆ SPQRnodeIsValid()

static SCIP_Bool SPQRnodeIsValid ( spqr_node node )

static

Check if a node is valid

Parameters

node	The node to check

Definition at line 298 of file network.c.

References SPQRnodeIsInvalid().

Referenced by cleanupPreviousIteration(), cleanUpPreviousIteration(), columnTransformSingleRigid(), createCutArc(), createPathArc(), determineRigidPath(), determineSingleRowRigidType(), determineSplitTypeFirstLeaf(), determineSplitTypeRigid(), findNode(), findNodeNoCompression(), getFirstNodeArc(), getRelativeOrientationRigid(), intersectionOfAllPaths(), netcoladdAdd(), netrowaddAdd(), nodeDegree(), nodeIsRepresentative(), rigidConnectedColoring(), rigidFindStarNodes(), rigidGetSplittableArticulationPointsOnPath(), setTerminalHead(), setTerminalTail(), and transformSingleRigid().

◆ SPQRarcIsInvalid()

static SCIP_Bool SPQRarcIsInvalid ( spqr_arc arc )

static

Check if an arc is invalid

Parameters

arc	The arc to check

Definition at line 317 of file network.c.

Referenced by arcIsRepresentative(), decompositionGetFundamentalCycleRows(), determinePathRigidType(), mergeNodeArcList(), netMatDecDataCreateDiGraph(), splitSeriesMergingRowAddition(), SPQRarcIsValid(), transformAndMergeRigid(), transformAndMergeSeries(), and zeroOutColors().

◆ SPQRarcIsValid()

static SCIP_Bool SPQRarcIsValid ( spqr_arc arc )

static

Check if an arc is valid

Parameters

arc	The arc to check

Definition at line 326 of file network.c.

References SPQRarcIsInvalid().

Referenced by addArcToMemberArcList(), addArcToNodeArcList(), arcFlipReversed(), arcGetElement(), arcIsChildMarker(), arcIsRepresentative(), arcIsReversedNonRigid(), arcIsTree(), arcSetRepresentative(), arcSetReversed(), checkLeaf(), columnTransformSingleRigid(), createArc(), determineAndColorSplitNode(), determinePathParallelType(), determinePathRigidType(), determinePathSeriesType(), determineRigidType(), findArcChildMember(), findArcChildMemberNoCompression(), findArcHead(), findArcHeadNoCompression(), findArcMember(), findArcMemberNoCompression(), findArcSign(), findArcSignNoCompression(), findArcTail(), findArcTailNoCompression(), getNextMemberArc(), getNextNodeArc(), getNextNodeArcNoCompression(), getPreviousMemberArc(), getPreviousNodeArc(), getRelativeOrientationParallel(), getRelativeOrientationSeries(), mergeMemberArcList(), mergeNodeArcList(), moveArcToNewMember(), netcoladdAdd(), netMatDecDataContainsColumn(), netMatDecDataContainsRow(), netMatDecDataRemoveComponent(), netrowaddAdd(), newColUpdateColInformation(), newRowUpdateRowInformation(), propagateComponents(), propagateCycles(), rigidConnectedColoring(), setDecompositionColumnArc(), setDecompositionRowArc(), splitParallel(), splitParallelMerging(), splitSeriesMerging(), transformAndMergeSeries(), transformFirstPathMember(), and transformSingleRigid().

◆ nodeIsRepresentative()

static SCIP_Bool nodeIsRepresentative	(	const SCIP_NETMATDECDATA *	dec,
		spqr_node	node
	)

static

Check if a node is a representative in the union-find data structure for nodes

Parameters

dec	The network decomposition
node	The node to check if it is representative

Definition at line 440 of file network.c.

References SCIP_NETMATDECDATA::nodes, SPQRNetworkDecompositionNode::representativeNode, SPQRnodeIsInvalid(), and SPQRnodeIsValid().

Referenced by addArcToNodeArcList(), changeArcHead(), changeArcTail(), determineRigidPath(), getNextNodeArc(), getNextNodeArcNoCompression(), getPreviousNodeArc(), mergeNodes(), rigidGetSplittableArticulationPointsOnPath(), splitAndMergeParallel(), and splitAndMergeSeries().

◆ findNode()

static spqr_node findNode	(	SCIP_NETMATDECDATA *	dec,
		spqr_node	node
	)

static

Find the node its representative node in the union-find data structure

Parameters

dec	The network decomposition
node	The node to find the representative for

Definition at line 456 of file network.c.

References SCIP_NETMATDECDATA::nodes, SPQRNetworkDecompositionNode::representativeNode, and SPQRnodeIsValid().

Referenced by findArcHead(), findArcTail(), netcoladdAdd(), and netrowaddAdd().

◆ findNodeNoCompression()

static spqr_node findNodeNoCompression	(	const SCIP_NETMATDECDATA *	dec,
		spqr_node	node
	)

static

Find the node its representative node in the union-find data structure, without compressing the union-find tree.

Should only be used for debugging or asserts.

Parameters

dec	The network decomposition
node	The node to find the representative for

Definition at line 493 of file network.c.

References SCIP_NETMATDECDATA::nodes, SPQRNetworkDecompositionNode::representativeNode, and SPQRnodeIsValid().

Referenced by findArcHeadNoCompression(), and findArcTailNoCompression().

◆ findArcTail()

static spqr_node findArcTail	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Find the arc's tail node in the union find data structure of the nodes.

Updates the arc's tail to point to the representative for faster future queries.

Parameters

dec	The network decomposition
arc	The arc whose tail we want to find

Definition at line 520 of file network.c.

References SCIP_NETMATDECDATA::arcs, findNode(), SPQRarcIsValid(), and SPQRNetworkDecompositionArc::tail.

Referenced by articulationPoints(), checkNeighbourColoringArticulationNode(), clearArcHeadAndTail(), columnTransformSingleRigid(), determineAndColorSplitNode(), determineRigidType(), determineSplitTypeFirstLeaf(), determineSplitTypeRigid(), findEffectiveArcHead(), findEffectiveArcTail(), getRelativeOrientationRigid(), intersectionOfAllPaths(), netMatDecDataCreateDiGraph(), rigidConnectedColoring(), rigidConnectedColoringRecursive(), rigidDetermineCandidateNodesFromAdjacentComponents(), rigidFindStarNodes(), rigidGetSplittableArticulationPointsOnPath(), splitAndMergeRigid(), splitFirstLeaf(), transformSingleRigid(), zeroOutColors(), and zeroOutColorsExceptNeighbourhood().

◆ findArcHead()

static spqr_node findArcHead	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Find the arc's head node in the union find data structure of the nodes.

Updates the arc's head to point to the representative for faster future queries.

Parameters

dec	The network decomposition
arc	The arc whose head we want to find

Definition at line 540 of file network.c.

References SCIP_NETMATDECDATA::arcs, findNode(), SPQRNetworkDecompositionArc::head, and SPQRarcIsValid().

Referenced by addArcToNodeArcList(), articulationPoints(), checkNeighbourColoringArticulationNode(), clearArcHeadAndTail(), columnTransformSingleRigid(), determineAndColorSplitNode(), determineRigidType(), determineSplitTypeFirstLeaf(), determineSplitTypeRigid(), findEffectiveArcHead(), findEffectiveArcTail(), getNextNodeArc(), getPreviousNodeArc(), getRelativeOrientationRigid(), intersectionOfAllPaths(), mergeNodeArcList(), netMatDecDataCreateDiGraph(), removeArcFromNodeArcList(), rigidConnectedColoring(), rigidConnectedColoringRecursive(), rigidDetermineCandidateNodesFromAdjacentComponents(), rigidFindStarNodes(), rigidGetSplittableArticulationPointsOnPath(), splitAndMergeRigid(), splitFirstLeaf(), transformSingleRigid(), zeroOutColors(), and zeroOutColorsExceptNeighbourhood().

◆ findArcHeadNoCompression()

static spqr_node findArcHeadNoCompression	(	const SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Find the arc's head node in the union find data structure of the nodes, without compressing the union-find tree.

Should only be used in debugging statements or asserts.

Parameters

dec	The network decomposition
arc	The arc whose head we want to find

Definition at line 560 of file network.c.

References SCIP_NETMATDECDATA::arcs, findNodeNoCompression(), SPQRNetworkDecompositionArc::head, and SPQRarcIsValid().

Referenced by findEffectiveArcHeadNoCompression(), findEffectiveArcTailNoCompression(), getNextNodeArcNoCompression(), intersectionOfAllPaths(), and rigidConnectedColoring().

◆ findArcTailNoCompression()

static spqr_node findArcTailNoCompression	(	const SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Find the arc's tail node in the union find data structure of the nodes, without compressing the union-find tree.

Should only be used in debugging statements or asserts.

Parameters

dec	The network decomposition
arc	The arc whose tail we want to find

Definition at line 578 of file network.c.

References SCIP_NETMATDECDATA::arcs, findNodeNoCompression(), SPQRarcIsValid(), and SPQRNetworkDecompositionArc::tail.

Referenced by findEffectiveArcHeadNoCompression(), findEffectiveArcTailNoCompression(), getNextNodeArc(), getNextNodeArcNoCompression(), getPreviousNodeArc(), intersectionOfAllPaths(), and rigidConnectedColoring().

◆ getFirstNodeArc()

static spqr_arc getFirstNodeArc	(	const SCIP_NETMATDECDATA *	dec,
		spqr_node	node
	)

static

Find the first arc in the list of arcs that are adjacent to the given node.

These arcs form a cyclic linked-list.

Parameters

dec	The network decomposition
node	The node to find the arc for

Definition at line 596 of file network.c.

References SPQRNetworkDecompositionNode::firstArc, SCIP_NETMATDECDATA::nodes, and SPQRnodeIsValid().

Referenced by addArcToNodeArcList(), articulationPoints(), checkNeighbourColoringArticulationNode(), columnTransformSingleRigid(), decompositionGetFundamentalCycleRows(), determineAndColorSplitNode(), intersectionOfAllPaths(), mergeNodeArcList(), rigidConnectedColoringRecursive(), rigidFindStarNodes(), rigidGetSplittableArticulationPointsOnPath(), splitAndMergeRigid(), splitFirstLeaf(), transformSingleRigid(), zeroOutColors(), and zeroOutColorsExceptNeighbourhood().

◆ getNextNodeArcNoCompression()

static spqr_arc getNextNodeArcNoCompression	(	const SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc,
		spqr_node	node
	)

static

Given the current arc adjacent to this node, find the next arc in the cyclic linked list of adjacent arcs to the given node.

This function does not compress the union-find tree, and should only be used in debugging or asserts.

Parameters

dec	The network decomposition
arc	The current arc that is adjacent to this node
node	The node to which the arc is adjacent

Definition at line 614 of file network.c.

References SCIP_NETMATDECDATA::arcs, findArcHeadNoCompression(), findArcTailNoCompression(), SPQRNetworkDecompositionArc::headArcListNode, SPQRNetworkDecompositionArcListNode::next, nodeIsRepresentative(), SPQRarcIsValid(), and SPQRNetworkDecompositionArc::tailArcListNode.

Referenced by decompositionGetFundamentalCycleRows().

◆ getNextNodeArc()

static spqr_arc getNextNodeArc	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc,
		spqr_node	node
	)

static

Given the current arc adjacent to this node, find the next arc in the cyclic linked list of adjacent arcs to the given node.

Parameters

dec	The network decomposition
arc	The current arc that is adjacent to this node
node	The node to which the arc is adjacent

Definition at line 641 of file network.c.

References SCIP_NETMATDECDATA::arcs, findArcHead(), findArcTailNoCompression(), SPQRNetworkDecompositionArc::headArcListNode, SPQRNetworkDecompositionArcListNode::next, nodeIsRepresentative(), SPQRarcIsValid(), SPQRNetworkDecompositionArc::tail, and SPQRNetworkDecompositionArc::tailArcListNode.

Referenced by articulationPoints(), checkNeighbourColoringArticulationNode(), columnTransformSingleRigid(), determineAndColorSplitNode(), intersectionOfAllPaths(), rigidConnectedColoringRecursive(), rigidFindStarNodes(), rigidGetSplittableArticulationPointsOnPath(), splitAndMergeRigid(), splitFirstLeaf(), transformSingleRigid(), zeroOutColors(), and zeroOutColorsExceptNeighbourhood().

◆ getPreviousNodeArc()

static spqr_arc getPreviousNodeArc	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc,
		spqr_node	node
	)

static

Given the current arc adjacent to this node, find the previous arc in the cyclic linked list of adjacent arcs to the given node.

Parameters

dec	The network decomposition
arc	The current arc that is adjacent to this node
node	The node to which the arc is adjacent

Definition at line 669 of file network.c.

References SCIP_NETMATDECDATA::arcs, findArcHead(), findArcTailNoCompression(), SPQRNetworkDecompositionArc::headArcListNode, nodeIsRepresentative(), SPQRNetworkDecompositionArcListNode::previous, SPQRarcIsValid(), SPQRNetworkDecompositionArc::tail, and SPQRNetworkDecompositionArc::tailArcListNode.

Referenced by mergeNodeArcList().

◆ mergeNodeArcList()

static void mergeNodeArcList	(	SCIP_NETMATDECDATA *	dec,
		spqr_node	toMergeInto,
		spqr_node	toRemove
	)

static

Update the cyclic node-arc incidence data structure to move all arcs adjacent to one node to another node.

We typically call this when two nodes are identified with one another, and we need to merge their adjacent arcs.

Parameters

dec	The network decomposition
toMergeInto	The node that we want to give all the arcs of both nodes
toRemove	The node whose arcs we want to remove

Definition at line 698 of file network.c.

References SCIP_NETMATDECDATA::arcs, findArcHead(), SPQRNetworkDecompositionNode::firstArc, getFirstNodeArc(), getPreviousNodeArc(), SPQRNetworkDecompositionArc::headArcListNode, SPQRNetworkDecompositionArcListNode::next, SCIP_NETMATDECDATA::nodes, SPQRNetworkDecompositionNode::numArcs, SPQRNetworkDecompositionArcListNode::previous, SPQR_INVALID_ARC, SPQRarcIsInvalid(), SPQRarcIsValid(), and SPQRNetworkDecompositionArc::tailArcListNode.

Referenced by mergeGivenMemberIntoParent(), mergeNodes(), and mergeSplitMemberIntoParent().

◆ arcFlipReversed()

static void arcFlipReversed	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Flips the direction a given arc.

Parameters

dec	The network decomposition
arc	The arc that we want to flip

Definition at line 754 of file network.c.

References SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::reversed, and SPQRarcIsValid().

Referenced by splitSeries().

◆ arcSetReversed()

static void arcSetReversed	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc,
		SCIP_Bool	reversed
	)

static

Sets the direction of a given arc

Parameters

dec	The network decomposition
arc	The given arc
reversed	Are the head and tail reversed?

Definition at line 768 of file network.c.

References SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::reversed, and SPQRarcIsValid().

Referenced by netcoladdAdd(), netrowaddAdd(), splitAndMergeParallel(), splitAndMergeSeries(), splitFirstLeaf(), transformAndMergeParallel(), transformAndMergeSeries(), and transformFirstPathMember().

◆ arcSetRepresentative()

static void arcSetRepresentative	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc,
		spqr_arc	representative
	)

static

Sets the representative of a given arc.

The arcs reversed field is given with respect to the representative. In particular, whether an arc is reversed or not is determined by the sign of the path in the signed union-find data structure for arcs, which can be computed by multiplying the signs of the individual edges (xor over bools).

Parameters

dec	The network decomposition
arc	The given arc
representative	The representative to set the arc to

Definition at line 789 of file network.c.

References SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::representative, SPQR_INVALID_ARC, and SPQRarcIsValid().

Referenced by netcoladdAdd(), netrowaddAdd(), splitAndMergeParallel(), splitAndMergeSeries(), splitFirstLeaf(), transformAndMergeParallel(), transformAndMergeSeries(), and transformFirstPathMember().

◆ mergeNodes()

static spqr_node mergeNodes	(	SCIP_NETMATDECDATA *	dec,
		spqr_node	first,
		spqr_node	second
	)

static

Merge two representative nodes (Union operation) in the union-find data structure for nodes.

Returns the id of the node that becomes representative for both.

Parameters

dec	The network decomposition
first	A node to merge
second	A second node to merge

Definition at line 808 of file network.c.

References mergeNodeArcList(), nodeIsRepresentative(), SCIP_NETMATDECDATA::nodes, SPQRNetworkDecompositionNode::representativeNode, and SCIPswapInts().

Referenced by mergeGivenMemberIntoParent(), and mergeSplitMemberIntoParent().

◆ memberIsRepresentative()

static SCIP_Bool memberIsRepresentative	(	const SCIP_NETMATDECDATA *	dec,
		spqr_member	member
	)

static

Check if a member is a representative in the union-find data structure for members.

Parameters

dec	The network decomposition
member	The member to check

Definition at line 841 of file network.c.

References SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::representativeMember, SPQRmemberIsInvalid(), and SPQRmemberIsValid().

Referenced by changeLoopToParallel(), changeLoopToSeries(), constructReducedDecomposition(), constructRowReducedDecomposition(), createArc(), createCutArc(), createPathArc(), createReducedMembersToRoot(), createRowReducedMembersToRoot(), determinePathParallelType(), determinePathSeriesType(), findMemberParent(), findMemberParentNoCompression(), getMemberType(), getNumMemberArcs(), markerOfParent(), markerToParent(), mergeGivenMemberIntoParent(), mergeMembers(), mergeSplitMemberIntoParent(), moveArcToNewMember(), netcoladdAdd(), netMatDecDataIsMinimal(), removeArcFromMemberArcList(), reorderComponent(), splitSeries(), splitSeriesMerging(), updateMemberParentInformation(), and updateMemberType().

◆ findMember()

static spqr_member findMember	(	SCIP_NETMATDECDATA *	dec,
		spqr_member	member
	)

static

Find the member its representative member in the union-find data structure

Parameters

dec	The network decomposition
member	The member to find the representative for

Definition at line 855 of file network.c.

References SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::representativeMember, and SPQRmemberIsValid().

Referenced by checkLeaf(), determineSingleComponentType(), findArcChildMember(), findArcMember(), findMemberParent(), splitParallelMerging(), and splitSeriesMergingRowAddition().

◆ findMemberNoCompression()

static spqr_member findMemberNoCompression	(	const SCIP_NETMATDECDATA *	dec,
		spqr_member	member
	)

static

Find the member's representative member in the union-find data structure, without compressing the union-find tree.

Should only be used for debugging or asserts.

Parameters

dec	The network decomposition
member	The member to find the representative for

Definition at line 892 of file network.c.

References SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::representativeMember, and SPQRmemberIsValid().

Referenced by findArcChildMemberNoCompression(), findArcMemberNoCompression(), findMemberParentNoCompression(), and updateMemberParentInformation().

◆ mergeMembers()

static spqr_member mergeMembers	(	SCIP_NETMATDECDATA *	dec,
		spqr_member	first,
		spqr_member	second
	)

static

Merge two representative members (Union operation) in the union-find data structure.

Returns the id of the member that becomes representative for both.

Parameters

dec	The network decomposition
first	The first member to merge
second	The second member to merge

Definition at line 920 of file network.c.

References memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::representativeMember, and SCIPswapInts().

Referenced by mergeGivenMemberIntoParent(), and mergeSplitMemberIntoParent().

◆ findArcMember()

static spqr_member findArcMember	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Finds the member in which the arc is located

Parameters

dec	The network decomposition
arc	The arc to find the member for

Definition at line 951 of file network.c.

References SCIP_NETMATDECDATA::arcs, findMember(), SPQRNetworkDecompositionArc::member, and SPQRarcIsValid().

Referenced by constructReducedDecomposition(), constructRowReducedDecomposition(), createPathArcs(), createReducedDecompositionCutArcs(), and netMatDecDataCreateDiGraph().

◆ findArcMemberNoCompression()

static spqr_member findArcMemberNoCompression	(	const SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Finds the member in which the arc is located, without compressing the member union-find tree

Parameters

dec	The network decomposition
arc	The arc to find the member for

Definition at line 967 of file network.c.

References SCIP_NETMATDECDATA::arcs, findMemberNoCompression(), SPQRNetworkDecompositionArc::member, and SPQRarcIsValid().

Referenced by decompositionGetFundamentalCycleRows(), getRelativeOrientationParallel(), getRelativeOrientationRigid(), getRelativeOrientationSeries(), moveArcToNewMember(), process_arc(), removeArcFromMemberArcList(), splitAndMergeParallel(), and splitFirstLeaf().

◆ findMemberParent()

static spqr_member findMemberParent	(	SCIP_NETMATDECDATA *	dec,
		spqr_member	member
	)

static

Find the representative parent member of the given member.

Note the given member must be representative.

Parameters

dec	The network decomposition
member	The member to find the parent for. Must be representative.

Definition at line 985 of file network.c.

References findMember(), memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::parentMember, SPQRmemberIsInvalid(), and SPQRmemberIsValid().

Referenced by columnTransformSingleRigid(), constructReducedDecomposition(), constructRowReducedDecomposition(), createReducedMembersToRoot(), createRowReducedMembersToRoot(), determinePathTypes(), netMatDecDataCreateDiGraph(), reorderComponent(), rigidTransformArcIntoCycle(), splitParallelRowAddition(), and splitSeries().

◆ findMemberParentNoCompression()

static spqr_member findMemberParentNoCompression	(	const SCIP_NETMATDECDATA *	dec,
		spqr_member	member
	)

static

Find the representative parent member of the given member.

Note the given member must be representative. This version does not perform compression of the union-find tree, and should only be used in debug or asserts.

Parameters

dec	The network decomposition
member	The member to find the parent for. Must be representative.

Definition at line 1011 of file network.c.

References findMemberNoCompression(), memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::parentMember, SPQRmemberIsInvalid(), and SPQRmemberIsValid().

Referenced by mergeGivenMemberIntoParent(), mergeSplitMemberIntoParent(), and netMatDecDataIsMinimal().

◆ findArcChildMember()

static spqr_member findArcChildMember	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Find the child member associated to the given arc, which must be virtual.

Parameters

dec	The network decomposition
arc	The arc to find the child member for

Definition at line 1031 of file network.c.

References SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::childMember, findMember(), and SPQRarcIsValid().

Referenced by columnTransformSingleRigid(), moveArcToNewMember(), netMatDecDataCreateDiGraph(), rigidTransformArcIntoCycle(), splitParallelRowAddition(), and splitSeries().

◆ findArcChildMemberNoCompression()

static spqr_member findArcChildMemberNoCompression	(	const SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Find the child member associated to the given virtual arc.

This version does not compress the union-find tree and should only be used for debugging and asserts.

Parameters

dec	The network decomposition
arc	The arc to find the child member for

Definition at line 1050 of file network.c.

References SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::childMember, findMemberNoCompression(), and SPQRarcIsValid().

Referenced by moveArcToNewMember(), and process_arc().

◆ arcIsChildMarker()

static SCIP_Bool arcIsChildMarker	(	const SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Checks if the arc has a child member

Parameters

dec	The network decomposition
arc	The arc to check

Definition at line 1065 of file network.c.

References SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::childMember, SPQRarcIsValid(), and SPQRmemberIsValid().

Referenced by columnTransformSingleRigid(), netMatDecDataCreateDiGraph(), process_arc(), rigidTransformArcIntoCycle(), splitParallelRowAddition(), and splitSeries().

◆ arcIsTree()

static SCIP_Bool arcIsTree	(	const SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Check whether the given arc is a tree arc or not, i.e. whether it belongs to a (virtual) row or column or not

Parameters

dec	The network decomposition
arc	The arc to check

Definition at line 1079 of file network.c.

References SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::element, SPQRarcIsValid(), and SPQRelementIsRow().

Referenced by checkLeaf(), checkNeighbourColoringArticulationNode(), columnTransformSingleRigid(), decompositionGetFundamentalCycleRows(), determineParallelType(), determineSeriesType(), intersectionOfAllPaths(), netMatDecDataCreateDiGraph(), process_arc(), propagateComponents(), propagateCycles(), rigidFindStarNodes(), rigidTransformArcIntoCycle(), splitParallel(), splitParallelMerging(), splitParallelRowAddition(), splitSeriesMerging(), and splitSeriesMergingRowAddition().

◆ arcIsRepresentative()

static SCIP_Bool arcIsRepresentative	(	const SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Check if an arc is a representative in the signed union-find data structure for arc directions.

In each member, exactly one arc is the representative.

Parameters

dec	The network decomposition
arc	The arc to check

Definition at line 1105 of file network.c.

References SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::representative, SPQRarcIsInvalid(), and SPQRarcIsValid().

Referenced by mergeArcSigns().

◆ findArcSign()

static ArcSign findArcSign	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Find an arcs representative and its direction in the signed union-find data structure for arcs.

Parameters

dec	The network decomposition
arc	The arc to find the representative and direction for

Definition at line 1121 of file network.c.

References SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::representative, ArcSign::representative, SPQRNetworkDecompositionArc::reversed, ArcSign::reversed, SCIP_Bool, and SPQRarcIsValid().

Referenced by columnTransformSingleRigid(), determineRigidType(), determineSplitTypeFirstLeaf(), determineSplitTypeRigid(), findEffectiveArcHead(), findEffectiveArcTail(), getRelativeOrientationRigid(), netMatDecDataCreateDiGraph(), rigidConnectedColoring(), rigidConnectedColoringRecursive(), rigidFindStarNodes(), splitAndMergeRigid(), splitFirstLeaf(), transformAndMergeRigid(), transformFirstPathMember(), and transformSingleRigid().

◆ findArcSignNoCompression()

static ArcSign findArcSignNoCompression	(	const SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Find an arcs representative and its direction in the signed union-find data structure for arcs.

This version does not compress the union-find tree and should only be used in debug and asserts.

Parameters

dec	The network decomposition
arc	The arc to find the representative and direction for

Definition at line 1172 of file network.c.

References SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::representative, ArcSign::representative, SPQRNetworkDecompositionArc::reversed, ArcSign::reversed, SCIP_Bool, and SPQRarcIsValid().

Referenced by findEffectiveArcHeadNoCompression(), and findEffectiveArcTailNoCompression().

◆ findEffectiveArcHead()

static spqr_node findEffectiveArcHead	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Finds the arcs head, taking into account whether it is reversed by the signed union-find data structure.

Parameters

dec	The network decomposition
arc	The arc to find the head for

Definition at line 1201 of file network.c.

References findArcHead(), findArcSign(), and findArcTail().

Referenced by checkRigidLeaf(), createCutArc(), createPathArc(), determinePathRigidType(), getRelativeOrientationRigid(), mergeGivenMemberIntoParent(), mergeSplitMemberIntoParent(), splitAndMergeParallel(), splitAndMergeSeries(), and transformSingleRigid().

◆ findEffectiveArcTail()

static spqr_node findEffectiveArcTail	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Finds the arcs tail, taking into account whether it is reversed by the signed union-find data structure.

Parameters

dec	The network decomposition
arc	The arc to find the tail for

Definition at line 1219 of file network.c.

References findArcHead(), findArcSign(), and findArcTail().

Referenced by checkRigidLeaf(), createCutArc(), createPathArc(), determinePathRigidType(), mergeGivenMemberIntoParent(), mergeSplitMemberIntoParent(), splitAndMergeParallel(), and splitAndMergeSeries().

◆ findEffectiveArcHeadNoCompression()

static spqr_node findEffectiveArcHeadNoCompression	(	const SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Finds the arcs head, taking into account whether it is reversed by the signed union-find data structure.

This version does not compress the union-find tree and should only be used in debug and asserts.

Parameters

dec	The network decomposition
arc	The arc to find the head for

Definition at line 1240 of file network.c.

References findArcHeadNoCompression(), findArcSignNoCompression(), and findArcTailNoCompression().

Referenced by decompositionGetFundamentalCycleRows(), netMatDecDataCreateDiGraph(), and transformSingleRigid().

◆ findEffectiveArcTailNoCompression()

static spqr_node findEffectiveArcTailNoCompression	(	const SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Finds the arcs tail, taking into account whether it is reversed by the signed union-find data structure.

This version does not compress the union-find tree and should only be used in debug and asserts.

Parameters

dec	The network decomposition
arc	The arc to find the tail for

Definition at line 1262 of file network.c.

References findArcHeadNoCompression(), findArcSignNoCompression(), and findArcTailNoCompression().

Referenced by decompositionGetFundamentalCycleRows(), getRelativeOrientationRigid(), netMatDecDataCreateDiGraph(), and transformSingleRigid().

◆ mergeArcSigns()

static spqr_arc mergeArcSigns	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	first,
		spqr_arc	second,
		SCIP_Bool	reflectRelative
	)

static

Merges the sign union-find structures for two arc sets.

If reflectRelative is set to true then all arcs of the represented by the second arc are reversed w.r.t. their current orientation. Otherwise, all arcs keep the same reversed status with respect to the root node of the union find tree.

Parameters

dec	The decomposition data structure
first	Representative arc of the first arc set
second	Representative arc of the second arc set
reflectRelative	Should all arcs in the second arc set be reversed?

Definition at line 1285 of file network.c.

References arcIsRepresentative(), SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::representative, SPQRNetworkDecompositionArc::reversed, SCIP_Bool, and SCIPswapInts().

Referenced by splitAndMergeParallel(), splitAndMergeRigid(), splitAndMergeSeries(), transformAndMergeParallel(), transformAndMergeRigid(), and transformAndMergeSeries().

◆ arcIsReversedNonRigid()

static SCIP_Bool arcIsReversedNonRigid	(	const SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Checks whether an arc is reversed for arcs in non-rigid members.

For non-rigid members, we do not use the union-find datastructure, as we can get away without it.

Parameters

dec	The network decomposition
arc	The arc to check

Definition at line 1329 of file network.c.

References SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::reversed, and SPQRarcIsValid().

Referenced by checkLeaf(), columnTransformSingleRigid(), decompositionGetFundamentalCycleRows(), determineParallelType(), determinePathParallelType(), determinePathSeriesType(), determineSeriesType(), determineSingleComponentType(), determineSingleParallelType(), determineSplitTypeFirstLeaf(), determineSplitTypeParallel(), determineSplitTypeSeries(), getRelativeOrientationParallel(), getRelativeOrientationSeries(), netcoladdAdd(), netMatDecDataCreateDiGraph(), netrowaddAdd(), rigidTransformArcIntoCycle(), splitAndMergeParallel(), splitAndMergeSeries(), splitFirstLeaf(), splitParallelRowAddition(), splitSeries(), transformAndMergeParallel(), transformAndMergeSeries(), transformComponentRowAddition(), and transformFirstPathMember().

◆ arcGetElement()

static spqr_element arcGetElement	(	const SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Gets the element (row/column) associated to the given arc.

Parameters

dec	The network decomposition
arc	The arc to get the element for

Definition at line 1343 of file network.c.

References SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::element, and SPQRarcIsValid().

Referenced by columnTransformSingleRigid(), netMatDecDataCreateDiGraph(), process_arc(), and rigidTransformArcIntoCycle().

◆ netMatDecDataContainsRow()

static SCIP_Bool netMatDecDataContainsRow	(	SCIP_NETMATDECDATA *	dec,
		int	row
	)

static

Check whether the network matrix decomposition contains an edge for the given row index.

Parameters

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

Definition at line 1357 of file network.c.

References SCIP_NETMATDECDATA::rowArcs, SPQRarcIsValid(), and SPQRrowIsValid().

Referenced by netMatDecDataCreateDiGraph(), netrowaddCheck(), and SCIPnetmatdecContainsRow().

◆ netMatDecDataContainsColumn()

static SCIP_Bool netMatDecDataContainsColumn	(	SCIP_NETMATDECDATA *	dec,
		int	column
	)

static

Check whether the network matrix decomposition contains an edge for the given column index.

Parameters

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

Definition at line 1370 of file network.c.

References SCIP_NETMATDECDATA::columnArcs, SPQRarcIsValid(), and SPQRcolIsValid().

Referenced by netcoladdCheck(), and SCIPnetmatdecContainsColumn().

◆ setDecompositionColumnArc()

static void setDecompositionColumnArc	(	SCIP_NETMATDECDATA *	dec,
		spqr_col	col,
		spqr_arc	arc
	)

static

Associate the given arc to the given column in the network matrix decomposition.

Parameters

dec	The network matrix decomposition
col	The column to associate
arc	The arc to associate to the column

Definition at line 1383 of file network.c.

References SCIP_NETMATDECDATA::columnArcs, SPQRarcIsValid(), and SPQRcolIsValid().

Referenced by createColumnArc().

◆ setDecompositionRowArc()

static void setDecompositionRowArc	(	SCIP_NETMATDECDATA *	dec,
		spqr_row	row,
		spqr_arc	arc
	)

static

Associate the given arc to the given row in the network matrix decomposition.

Parameters

dec	The network matrix decomposition
row	The row to associate
arc	The arc to associate to the row

Definition at line 1398 of file network.c.

References SCIP_NETMATDECDATA::rowArcs, SPQRarcIsValid(), and SPQRrowIsValid().

Referenced by createRowArc().

◆ getDecompositionColumnArc()

static spqr_arc getDecompositionColumnArc	(	const SCIP_NETMATDECDATA *	dec,
		spqr_col	col
	)

static

Get the decomposition arc associated to the given column.

Parameters

dec	The network matrix decomposition
col	The given column

Definition at line 1413 of file network.c.

References SCIP_NETMATDECDATA::columnArcs, and SPQRcolIsValid().

Referenced by decompositionGetFundamentalCycleRows(), and newRowUpdateRowInformation().

◆ getDecompositionRowArc()

static spqr_arc getDecompositionRowArc	(	const SCIP_NETMATDECDATA *	dec,
		spqr_row	row
	)

static

Get the decomposition arc associated to the given row.

Parameters

dec	The network matrix decomposition
row	The given row

Definition at line 1426 of file network.c.

References SCIP_NETMATDECDATA::rowArcs, and SPQRrowIsValid().

Referenced by newColUpdateColInformation().

◆ netMatDecDataCreate()

static SCIP_RETCODE netMatDecDataCreate	(	BMS_BLKMEM *	blkmem,
		SCIP_NETMATDECDATA **	pdec,
		int	nrows,
		int	ncols
	)

static

Initialize the network matrix decomposition data structure.

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 1439 of file network.c.

Referenced by SCIPnetmatdecCreate().

◆ netMatDecDataFree()

static void netMatDecDataFree ( SCIP_NETMATDECDATA ** pdec )

static

Free the network matrix decomposition data structure

Parameters

pdec	pointer to the network matrix decomposition to freed

Definition at line 1513 of file network.c.

References SCIP_NETMATDECDATA::arcs, BMSfreeBlockMemory, BMSfreeBlockMemoryArray, SCIP_NETMATDECDATA::columnArcs, SCIP_NETMATDECDATA::env, SCIP_NETMATDECDATA::memArcs, SCIP_NETMATDECDATA::members, SCIP_NETMATDECDATA::memColumns, SCIP_NETMATDECDATA::memMembers, SCIP_NETMATDECDATA::memNodes, SCIP_NETMATDECDATA::memRows, SCIP_NETMATDECDATA::nodes, and SCIP_NETMATDECDATA::rowArcs.

Referenced by SCIPnetmatdecFree().

◆ getFirstMemberArc()

static spqr_arc getFirstMemberArc	(	const SCIP_NETMATDECDATA *	dec,
		spqr_member	member
	)

static

Get the first arc of the linked list of arcs contained in the given member.

Parameters

dec	The network matrix decomposition
member	The given member

Definition at line 1532 of file network.c.

References SPQRNetworkDecompositionMember::firstArc, SCIP_NETMATDECDATA::members, and SPQRmemberIsValid().

Referenced by addArcToMemberArcList(), articulationPoints(), columnTransformSingleSeries(), decompositionGetFundamentalCycleRows(), mergeMemberArcList(), netcoladdAdd(), netMatDecDataCreateDiGraph(), netrowaddAdd(), rigidConnectedColoring(), splitAndMergeParallel(), splitAndMergeSeries(), splitFirstLeaf(), splitParallelRowAddition(), splitSeries(), splitSeriesMerging(), splitSeriesMergingRowAddition(), and transformAndMergeParallel().

◆ getNextMemberArc()

static spqr_arc getNextMemberArc	(	const SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Given the current arc, get the next arc of the linked list of arcs that are in the same member.

Parameters

dec	The network matrix decomposition
arc	The current arc

Definition at line 1546 of file network.c.

References SPQRNetworkDecompositionArc::arcListNode, SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArcListNode::next, and SPQRarcIsValid().

Referenced by decompositionGetFundamentalCycleRows(), netMatDecDataCreateDiGraph(), rigidConnectedColoring(), splitAndMergeParallel(), splitAndMergeSeries(), splitFirstLeaf(), splitParallelRowAddition(), splitSeries(), splitSeriesMerging(), splitSeriesMergingRowAddition(), and transformAndMergeParallel().

◆ getPreviousMemberArc()

static spqr_arc getPreviousMemberArc	(	const SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Given the current arc, get the previous arc of the linked list of arcs that are in the same member.

Parameters

dec	The network matrix decomposition
arc	The current arc

Definition at line 1561 of file network.c.

References SPQRNetworkDecompositionArc::arcListNode, SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArcListNode::previous, and SPQRarcIsValid().

Referenced by addArcToMemberArcList(), and mergeMemberArcList().

◆ addArcToMemberArcList()

static void addArcToMemberArcList	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc,
		spqr_member	member
	)

static

Adds an arc to the linked list of arcs of the given member.

Parameters

dec	The network matrix decomposition
arc	The arc to add
member	The member to add the arc to

Definition at line 1576 of file network.c.

References SPQRNetworkDecompositionArc::arcListNode, SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionMember::firstArc, getFirstMemberArc(), getPreviousMemberArc(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionArcListNode::next, SPQRNetworkDecompositionMember::numArcs, SPQRNetworkDecompositionArcListNode::previous, and SPQRarcIsValid().

Referenced by createChildMarker(), createColumnArc(), createParentMarker(), createRowArc(), and moveArcToNewMember().

◆ createArc()

static SCIP_RETCODE createArc	(	SCIP_NETMATDECDATA *	dec,
		spqr_member	member,
		SCIP_Bool	reversed,
		spqr_arc *	pArc
	)

static

Create a new arc in the network matrix decomposition.

Parameters

dec	The network matrix decomposition
member	The member that contains the arc
reversed	Is the arc reversed or not?
pArc	out-pointer to the id that is assigned to the arc.

Definition at line 1604 of file network.c.

Referenced by createChildMarker(), createColumnArc(), createParentMarker(), and createRowArc().

◆ createRowArc()

static SCIP_RETCODE createRowArc	(	SCIP_NETMATDECDATA *	dec,
		spqr_member	member,
		spqr_arc *	pArc,
		spqr_row	row,
		SCIP_Bool	reversed
	)

static

Create a new arc in the network matrix decomposition that is associated to the given row.

Parameters

dec	The network matrix decomposition
member	The member that contains the arc
pArc	out-pointer to the id that is assigned to the arc.
row	The row associated to the arc
reversed	Is the arc reversed or not?

Definition at line 1656 of file network.c.

References addArcToMemberArcList(), SCIP_NETMATDECDATA::arcs, createArc(), SPQRNetworkDecompositionArc::element, SCIP_CALL, SCIP_OKAY, setDecompositionRowArc(), and SPQRrowToElement().

Referenced by columnTransformSingleRigid(), createConnectedParallel(), createConnectedSeries(), createStandaloneParallel(), createStandaloneSeries(), netrowaddAdd(), and rigidTransformArcIntoCycle().

◆ createColumnArc()

static SCIP_RETCODE createColumnArc	(	SCIP_NETMATDECDATA *	dec,
		spqr_member	member,
		spqr_arc *	pArc,
		spqr_col	column,
		SCIP_Bool	reversed
	)

static

Create a new arc in the network matrix decomposition that is associated to the given column.

Parameters

dec	The network matrix decomposition
member	The member that contains the arc
pArc	out-pointer to the id that is assigned to the arc.
column	The column associated to the arc
reversed	Is the arc reversed or not?

Definition at line 1674 of file network.c.

References addArcToMemberArcList(), SCIP_NETMATDECDATA::arcs, createArc(), SPQRNetworkDecompositionArc::element, SCIP_CALL, SCIP_OKAY, setDecompositionColumnArc(), and SPQRcolumnToElement().

Referenced by columnTransformSingleRigid(), createConnectedParallel(), createConnectedSeries(), createStandaloneParallel(), createStandaloneSeries(), netcoladdAdd(), and rigidTransformArcIntoCycle().

◆ createMember()

static SCIP_RETCODE createMember	(	SCIP_NETMATDECDATA *	dec,
		SPQRMemberType	type,
		spqr_member *	pMember
	)

static

Create a new member in the network matrix decomposition.

Parameters

dec	The network matrix decomposition
type	The SPQR-type of the member
pMember	out-pointer to the id that is assigned to the member

Definition at line 1692 of file network.c.

References BMSreallocBlockMemoryArray, SCIP_NETMATDECDATA::env, SPQRNetworkDecompositionMember::firstArc, SPQRNetworkDecompositionMember::markerOfParent, SPQRNetworkDecompositionMember::markerToParent, SCIP_NETMATDECDATA::members, SCIP_NETMATDECDATA::memMembers, SPQRNetworkDecompositionMember::numArcs, SCIP_NETMATDECDATA::numMembers, SPQRNetworkDecompositionMember::parentMember, SPQRNetworkDecompositionMember::representativeMember, SCIP_ALLOC, SCIP_OKAY, SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, and SPQRNetworkDecompositionMember::type.

Referenced by columnTransformSingleRigid(), createConnectedParallel(), createConnectedSeries(), createStandaloneParallel(), createStandaloneSeries(), rigidTransformArcIntoCycle(), splitParallel(), splitParallelMerging(), splitParallelRowAddition(), splitSeries(), splitSeriesMerging(), and splitSeriesMergingRowAddition().

◆ createNode()

static SCIP_RETCODE createNode	(	SCIP_NETMATDECDATA *	dec,
		spqr_node *	pNode
	)

static

Create a new node in the network matrix decomposition.

Parameters

dec	The network matrix decomposition
pNode	out-pointer to the id that is assigned to the node

Definition at line 1724 of file network.c.

References BMSreallocBlockMemoryArray, SCIP_NETMATDECDATA::env, SPQRNetworkDecompositionNode::firstArc, SCIP_NETMATDECDATA::memNodes, SCIP_NETMATDECDATA::nodes, SPQRNetworkDecompositionNode::numArcs, SCIP_NETMATDECDATA::numNodes, SPQRNetworkDecompositionNode::representativeNode, SCIP_ALLOC, SCIP_OKAY, SPQR_INVALID_ARC, and SPQR_INVALID_NODE.

Referenced by splitAndMergeParallel(), splitAndMergeRigid(), splitAndMergeSeries(), splitFirstLeaf(), transformAndMergeParallel(), transformAndMergeSeries(), transformFirstPathMember(), and transformSingleRigid().

◆ removeArcFromNodeArcList()

static void removeArcFromNodeArcList	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc,
		spqr_node	node,
		SCIP_Bool	nodeIsHead
	)

static

Remove an arc from the linked list of arcs that are adjacent to a given node.

Parameters

dec	The network matrix decomposition
arc	The arc to remove
node	The node to remove the arc from
nodeIsHead	Indicates whether the node is the arcs head, or tail

Definition at line 1746 of file network.c.

References SCIP_NETMATDECDATA::arcs, findArcHead(), SPQRNetworkDecompositionNode::firstArc, SPQRNetworkDecompositionArc::headArcListNode, SPQRNetworkDecompositionArcListNode::next, SCIP_NETMATDECDATA::nodes, SPQRNetworkDecompositionNode::numArcs, SPQRNetworkDecompositionArcListNode::previous, SPQR_INVALID_ARC, and SPQRNetworkDecompositionArc::tailArcListNode.

Referenced by changeArcHead(), changeArcTail(), and clearArcHeadAndTail().

◆ addArcToNodeArcList()

static void addArcToNodeArcList	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc,
		spqr_node	node,
		SCIP_Bool	nodeIsHead
	)

static

Add an arc to the linked list of arcs that are adjacent to a given node.

Parameters

dec	The network matrix decomposition
arc	The arc to add
node	The node to add the arc to
nodeIsHead	Indicates whether the node is the arcs head, or tail

Definition at line 1784 of file network.c.

References SCIP_NETMATDECDATA::arcs, findArcHead(), SPQRNetworkDecompositionNode::firstArc, getFirstNodeArc(), SPQRNetworkDecompositionArc::head, SPQRNetworkDecompositionArc::headArcListNode, SPQRNetworkDecompositionArcListNode::next, nodeIsRepresentative(), SCIP_NETMATDECDATA::nodes, SPQRNetworkDecompositionNode::numArcs, SPQRNetworkDecompositionArcListNode::previous, SCIP_Bool, SPQRarcIsValid(), SPQRNetworkDecompositionArc::tail, and SPQRNetworkDecompositionArc::tailArcListNode.

Referenced by changeArcHead(), changeArcTail(), and setArcHeadAndTail().

◆ setArcHeadAndTail()

static void setArcHeadAndTail	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc,
		spqr_node	head,
		spqr_node	tail
	)

static

Initializes the data structures of the arcs head and tail nodes.

Parameters

dec	The network matrix decomposition
arc	The arc to initialize
head	The arc its head node
tail	The arc its tail node

Definition at line 1832 of file network.c.

References addArcToNodeArcList(), FALSE, and TRUE.

Referenced by netcoladdAdd(), netrowaddAdd(), splitAndMergeParallel(), splitAndMergeSeries(), splitFirstLeaf(), transformAndMergeParallel(), transformAndMergeSeries(), and transformFirstPathMember().

◆ clearArcHeadAndTail()

static void clearArcHeadAndTail	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc
	)

static

Deinitializes the data structures of the arcs head and tail nodes.

Parameters

dec	The network matrix decomposition
arc	The arc to deinitialize

Definition at line 1845 of file network.c.

References SCIP_NETMATDECDATA::arcs, FALSE, findArcHead(), findArcTail(), SPQRNetworkDecompositionArc::head, removeArcFromNodeArcList(), SPQR_INVALID_NODE, SPQRNetworkDecompositionArc::tail, and TRUE.

Referenced by mergeGivenMemberIntoParent(), and mergeSplitMemberIntoParent().

◆ changeArcHead()

static void changeArcHead	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc,
		spqr_node	oldHead,
		spqr_node	newHead
	)

static

Change the arc's head node to a new node.

Parameters

dec	The network matrix decomposition
arc	The given arc
oldHead	The current head node of the arc
newHead	The new head node of the arc

Definition at line 1858 of file network.c.

References addArcToNodeArcList(), nodeIsRepresentative(), removeArcFromNodeArcList(), and TRUE.

Referenced by splitAndMergeRigid(), splitFirstLeaf(), and transformSingleRigid().

◆ changeArcTail()

static void changeArcTail	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc,
		spqr_node	oldTail,
		spqr_node	newTail
	)

static

Change the arc's head node to a new node.

Parameters

dec	The network matrix decomposition
arc	The given arc
oldTail	The current tail node of the arc
newTail	The new tail node of the arc

Definition at line 1874 of file network.c.

References addArcToNodeArcList(), FALSE, nodeIsRepresentative(), and removeArcFromNodeArcList().

Referenced by splitAndMergeRigid(), splitFirstLeaf(), and transformSingleRigid().

◆ nodeDegree()

static int nodeDegree	(	SCIP_NETMATDECDATA *	dec,
		spqr_node	node
	)

static

Returns the degree of the given node.

Parameters

dec	The network matrix decomposition
node	The given node

Definition at line 1890 of file network.c.

References SCIP_NETMATDECDATA::nodes, SPQRNetworkDecompositionNode::numArcs, and SPQRnodeIsValid().

Referenced by rigidFindStarNodes(), and zeroOutColorsExceptNeighbourhood().

◆ getMemberType()

static SPQRMemberType getMemberType	(	const SCIP_NETMATDECDATA *	dec,
		spqr_member	member
	)

static

Get the SPQR-type of the given member.

Parameters

dec	The network matrix decomposition
member	The given member

Definition at line 1904 of file network.c.

References memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQRmemberIsValid(), and SPQRNetworkDecompositionMember::type.

Referenced by changeLoopToParallel(), changeLoopToSeries(), checkLeaf(), columnTransformSingleRigid(), createCutArc(), createPathArc(), decompositionGetFundamentalCycleRows(), determineMergeableTypes(), determinePathMemberType(), determinePathParallelType(), determinePathSeriesType(), determineSingleComponentType(), determineSplitTypeFirstLeaf(), determineSplitTypeNext(), determineSplitTypeRigid(), determineType(), getRelativeOrientation(), netcoladdAdd(), netMatDecDataCreateDiGraph(), netMatDecDataIsMinimal(), netrowaddAdd(), rigidTransformArcIntoCycle(), splitAndMerge(), splitFirstLeaf(), splitParallelRowAddition(), splitSeries(), transformAndMerge(), transformComponent(), transformComponentRowAddition(), and transformFirstPathMember().

◆ updateMemberType()

static void updateMemberType	(	const SCIP_NETMATDECDATA *	dec,
		spqr_member	member,
		SPQRMemberType	type
	)

static

Update the SPQR-type of the given member.

Parameters

dec	The network matrix decomposition
member	The member to update the type for
type	The new SPQR-type of the member

Definition at line 1919 of file network.c.

References memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQRmemberIsValid(), and SPQRNetworkDecompositionMember::type.

Referenced by mergeGivenMemberIntoParent(), mergeSplitMemberIntoParent(), and splitFirstLeaf().

◆ markerToParent()

static spqr_arc markerToParent	(	const SCIP_NETMATDECDATA *	dec,
		spqr_member	member
	)

static

Returns the virtual arc pointing to the parent member (in the arborescence) of the given member.

Parameters

dec	The network matrix decomposition
member	The given member

Definition at line 1935 of file network.c.

References SPQRNetworkDecompositionMember::markerToParent, memberIsRepresentative(), SCIP_NETMATDECDATA::members, and SPQRmemberIsValid().

Referenced by columnTransformSingleRigid(), determinePathTypes(), determineSplitTypeFirstLeaf(), determineSplitTypeNext(), mergeGivenMemberIntoParent(), mergeSplitMemberIntoParent(), netMatDecDataCreateDiGraph(), process_arc(), propagateComponents(), propagateCycles(), rigidDetermineCandidateNodesFromAdjacentComponents(), rigidTransformArcIntoCycle(), splitAndMergeParallel(), splitAndMergeRigid(), splitAndMergeSeries(), splitParallel(), splitParallelMerging(), splitParallelRowAddition(), splitSeries(), splitSeriesMerging(), and splitSeriesMergingRowAddition().

◆ updateMemberParentInformation()

static void updateMemberParentInformation	(	SCIP_NETMATDECDATA *	dec,
		const spqr_member	newMember,
		const spqr_member	toRemove
	)

static

Updates the parent information of a member that is identified with another another member.

Parameters

dec	The network matrix decomposition
newMember	The new large member containing both members
toRemove	The member that was merged and removed

Definition at line 1950 of file network.c.

References findMemberNoCompression(), SPQRNetworkDecompositionMember::markerOfParent, SPQRNetworkDecompositionMember::markerToParent, memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::parentMember, SPQR_INVALID_ARC, and SPQR_INVALID_MEMBER.

Referenced by mergeGivenMemberIntoParent(), and mergeSplitMemberIntoParent().

◆ markerOfParent()

static spqr_arc markerOfParent	(	const SCIP_NETMATDECDATA *	dec,
		spqr_member	member
	)

static

Returns the virtual arc of the parent member that points to the given member.

Parameters

dec	The network matrix decomposition
member	The given member

Definition at line 1970 of file network.c.

References SPQRNetworkDecompositionMember::markerOfParent, memberIsRepresentative(), SCIP_NETMATDECDATA::members, and SPQRmemberIsValid().

Referenced by columnTransformSingleRigid(), determinePathTypes(), determineSplitTypeNext(), mergeGivenMemberIntoParent(), mergeSplitMemberIntoParent(), process_arc(), propagateComponents(), propagateCycles(), rigidDetermineCandidateNodesFromAdjacentComponents(), rigidTransformArcIntoCycle(), splitAndMergeParallel(), splitAndMergeRigid(), splitAndMergeSeries(), splitParallelMerging(), splitParallelRowAddition(), splitSeries(), and splitSeriesMergingRowAddition().

◆ getNumMemberArcs()

static int getNumMemberArcs	(	const SCIP_NETMATDECDATA *	dec,
		spqr_member	member
	)

static

Returns the number of arcs in the member.

Parameters

dec	The network matrix decomposition
member	The member to get the number of arcs of

Definition at line 1985 of file network.c.

References memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::numArcs, and SPQRmemberIsValid().

Referenced by changeLoopToParallel(), changeLoopToSeries(), checkLeaf(), columnTransformSingleSeries(), determineParallelType(), determineSingleComponentType(), netcoladdAdd(), netMatDecDataCreateDiGraph(), netrowaddAdd(), splitAndMergeSeries(), splitParallelMerging(), splitParallelRowAddition(), splitSeries(), splitSeriesMerging(), splitSeriesMergingRowAddition(), transformAndMergeParallel(), transformAndMergeSeries(), transformComponentRowAddition(), and transformFirstPathMember().

◆ getNumNodes()

static int getNumNodes ( const SCIP_NETMATDECDATA * dec )

static

Returns the number of nodes in complete network matrix decomposition.

Parameters

dec	The network matrix decomposition

Definition at line 2000 of file network.c.

References SCIP_NETMATDECDATA::numNodes.

Referenced by allocateRigidSearchMemory(), and rigidGetSplittableArticulationPointsOnPath().

◆ getNumMembers()

static int getNumMembers ( const SCIP_NETMATDECDATA * dec )

static

Returns the number of members in complete network matrix decomposition.

Parameters

dec	The network matrix decomposition

Definition at line 2011 of file network.c.

References SCIP_NETMATDECDATA::numMembers.

Referenced by constructReducedDecomposition(), constructRowReducedDecomposition(), and createPathArcs().

◆ createStandaloneParallel()

static SCIP_RETCODE createStandaloneParallel	(	SCIP_NETMATDECDATA *	dec,
		spqr_col *	columns,
		SCIP_Bool *	reversed,
		int	num_columns,
		spqr_row	row,
		spqr_member *	pMember
	)

static

Creates a standalone parallel member with the given row and columns that is not connected to other members of the network matrix decomposition.

New arcs are created for the given row and columns.

Parameters

dec	The network matrix decomposition
columns	The columns in the parallel member
reversed	Array indicating the direction of each column edge
num_columns	The number of columns in the parallel member
row	The row in the parallel member
pMember	out-pointer to the new parallel member id

Definition at line 2026 of file network.c.

References createColumnArc(), createMember(), createRowArc(), SCIP_NETMATDECDATA::numConnectedComponents, SCIP_CALL, SCIP_OKAY, SPQR_MEMBERTYPE_LOOP, and SPQR_MEMBERTYPE_PARALLEL.

Referenced by netrowaddAdd().

◆ createConnectedParallel()

static SCIP_RETCODE createConnectedParallel	(	SCIP_NETMATDECDATA *	dec,
		spqr_col *	columns,
		SCIP_Bool *	reversed,
		int	num_columns,
		spqr_row	row,
		spqr_member *	pMember
	)

static

Creates a parallel member with the given row and columns is connected to other members of the network matrix decomposition.

New arcs are created for the given row and columns.

Parameters

dec	The network matrix decomposition
columns	The columns in the parallel member
reversed	Array indicating the direction of each column edge
num_columns	The number of columns in the parallel member
row	The row in the parallel member
pMember	out-pointer to the new parallel member id

Definition at line 2059 of file network.c.

References createColumnArc(), createMember(), createRowArc(), FALSE, SCIP_CALL, SCIP_OKAY, and SPQR_MEMBERTYPE_PARALLEL.

Referenced by netrowaddAdd().

◆ createStandaloneSeries()

static SCIP_RETCODE createStandaloneSeries	(	SCIP_NETMATDECDATA *	dec,
		spqr_row *	rows,
		SCIP_Bool *	reversed,
		int	numRows,
		spqr_col	col,
		spqr_member *	pMember
	)

static

Creates a standalone series member with the given row and columns that is not connected to other members of the network matrix decomposition.

New arcs are created for the given rows and column.

Parameters

dec	The network matrix decomposition
rows	The rows in the series member
reversed	Array indicating the direction of each row edge
numRows	The number of rows in the parallel member
col	The column in the parallel member
pMember	out-pointer to the new series member id

Definition at line 2090 of file network.c.

References createColumnArc(), createMember(), createRowArc(), FALSE, SCIP_NETMATDECDATA::numConnectedComponents, SCIP_CALL, SCIP_OKAY, SPQR_MEMBERTYPE_LOOP, and SPQR_MEMBERTYPE_SERIES.

Referenced by netcoladdAdd().

◆ createConnectedSeries()

static SCIP_RETCODE createConnectedSeries	(	SCIP_NETMATDECDATA *	dec,
		spqr_row *	rows,
		SCIP_Bool *	reversed,
		int	numRows,
		spqr_col	col,
		spqr_member *	pMember
	)

static

Creates a series member with the given row and columns that is connected to some other member of the network matrix decomposition.

New arcs are created for the given rows and column.

Parameters

dec	The network matrix decomposition
rows	The rows in the series member
reversed	Array indicating the direction of each row edge
numRows	The number of rows in the parallel member
col	The column in the parallel member
pMember	out-pointer to the new series member id

Definition at line 2122 of file network.c.

References createColumnArc(), createMember(), createRowArc(), FALSE, SCIP_CALL, SCIP_OKAY, and SPQR_MEMBERTYPE_SERIES.

Referenced by netcoladdAdd().

◆ removeArcFromMemberArcList()

static void removeArcFromMemberArcList	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc,
		spqr_member	member
	)

static

Remove an arc from the linked list containing all arcs of a single member.

Parameters

dec	The network matrix decomposition
arc	The arc to remove
member	The member to remove it from

Definition at line 2149 of file network.c.

References SPQRNetworkDecompositionArc::arcListNode, SCIP_NETMATDECDATA::arcs, findArcMemberNoCompression(), SPQRNetworkDecompositionMember::firstArc, memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionArcListNode::next, SPQRNetworkDecompositionMember::numArcs, SPQRNetworkDecompositionArcListNode::previous, and SPQR_INVALID_ARC.

Referenced by mergeGivenMemberIntoParent(), mergeSplitMemberIntoParent(), and moveArcToNewMember().

◆ process_arc()

static void process_arc	(	spqr_row *	cyclearcs,
		int *	num_cycle_arcs,
		FindCycleCall *	callStack,
		int *	callStackSize,
		spqr_arc	arc,
		const SCIP_NETMATDECDATA *	dec,
		SCIP_Bool *	cycledir,
		SCIP_Bool	arcIsReversed
	)

static

Processes a single arc for the algorithm to find cycles in the network matrix decomposition.

if virtual, pushes it on the callstack, if non-virtual, adds it to the found cycle

Parameters

cyclearcs	The found cycle so far
num_cycle_arcs	The number of arcs in the cycle so far
callStack	The call stack of virtual edges to process still
callStackSize	The number of virtual edges on the callstack
arc	The current arc to process
dec	The network matrix decomposition
cycledir	Whether the current arc is reversed w.r.t to the cycle/path
arcIsReversed	The arcIsReversed status from the network matrix decomposition

Definition at line 2191 of file network.c.

References FindCycleCall::arc, arcGetElement(), arcIsChildMarker(), arcIsTree(), findArcChildMemberNoCompression(), findArcMemberNoCompression(), markerOfParent(), markerToParent(), FindCycleCall::reversed, SPQRelementIsRow(), and SPQRelementToRow().

Referenced by decompositionGetFundamentalCycleRows().

◆ decompositionGetFundamentalCycleRows()

static int decompositionGetFundamentalCycleRows	(	const SCIP_NETMATDECDATA *	dec,
		spqr_col	column,
		spqr_row *	output,
		SCIP_Bool *	computedSignStorage
	)

static

Find the fundamental path of a cycle.

This is a slow method and only intended for debugging and testing.

Parameters

dec	The network matrix decomposition
column	The column to find the fundamental path for
output	preallocated array to store fundamental path in. Must have at least the number of rows in the decomposition allocated
computedSignStorage	Boolean array for storage of whether the path occurs forwards or backwards. Must have at least the same size as output array.

Definition at line 2241 of file network.c.

References FindCycleCall::arc, arcIsReversedNonRigid(), arcIsTree(), BMSallocBlockMemoryArray, BMSfreeBlockMemoryArray, SCIP_NETMATDECDATA::env, FALSE, findArcMemberNoCompression(), findEffectiveArcHeadNoCompression(), findEffectiveArcTailNoCompression(), getDecompositionColumnArc(), getFirstMemberArc(), getFirstNodeArc(), getMemberType(), getNextMemberArc(), getNextNodeArcNoCompression(), SCIP_NETMATDECDATA::memRows, DFSCallData::node, DFSCallData::nodeArc, NULL, SCIP_NETMATDECDATA::numNodes, process_arc(), FindCycleCall::reversed, SCIP_Bool, SCIPABORT, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_SERIES, SPQR_MEMBERTYPE_UNASSIGNED, SPQRarcIsInvalid(), and TRUE.

Referenced by netMatDecDataVerifyCycle().

◆ netMatDecDataVerifyCycle()

static SCIP_Bool netMatDecDataVerifyCycle	(	BMS_BUFMEM *	bufmem,
		const SCIP_NETMATDECDATA *	dec,
		int	column,
		const int *	nonzrowidx,
		const double *	nonzvals,
		int	num_rows,
		int *	pathrowstorage,
		SCIP_Bool *	pathsignstorage
	)

static

Given a cycle (e.g. a matrix column), checks if the column's cycle matches the cycle in the network matrix decomposition.

Parameters

bufmem	Buffer memory
dec	The network matrix decomposition
column	The column to check
nonzrowidx	Array with the nonzero row indices of the column
nonzvals	Array with the nonzero entry values of the column's row indices
num_rows	The number of nonzeros in the column
pathrowstorage	Temporary storage vector for storing the fundamental path. Must have at least as many entries allocated as the number of rows in dec.
pathsignstorage	Temporary storage for the fundamental path directions. Must have at least as many entries allocated as the number of rows in dec.

Definition at line 2432 of file network.c.

References BMSallocBufferMemoryArray, BMSfreeBufferMemoryArray, decompositionGetFundamentalCycleRows(), FALSE, NULL, SCIP_Bool, SCIPsortIntInt(), and TRUE.

Referenced by SCIPnetmatdecVerifyCycle().

◆ largestMemberID()

static spqr_member largestMemberID ( const SCIP_NETMATDECDATA * dec )

static

Returns the largest member id that is currently in the decomposition.

Parameters

dec	The network matrix decomposition

Definition at line 2518 of file network.c.

References SCIP_NETMATDECDATA::numMembers.

Referenced by constructReducedDecomposition(), constructRowReducedDecomposition(), and netMatDecDataCreateDiGraph().

◆ largestArcID()

static spqr_arc largestArcID ( const SCIP_NETMATDECDATA * dec )

static

Returns the largest arc id that is currently in the decomposition.

Parameters

dec	The network matrix decomposition

Definition at line 2527 of file network.c.

References SCIP_NETMATDECDATA::numArcs.

Referenced by createPathArcs(), and createReducedDecompositionCutArcs().

◆ largestNodeID()

static spqr_node largestNodeID ( const SCIP_NETMATDECDATA * dec )

static

Returns the largest node id that is currently in the decomposition.

Parameters

dec	The network matrix decomposition

Definition at line 2536 of file network.c.

References SCIP_NETMATDECDATA::numNodes.

Referenced by allocateRigidSearchMemory(), createPathArcs(), and netMatDecDataCreateDiGraph().

◆ numConnectedComponents()

static int numConnectedComponents ( const SCIP_NETMATDECDATA * dec )

static

Returns the number of SPQR trees in the SPQR forest, i.e. the number of connected components.

Parameters

dec	The network matrix decomposition

Definition at line 2545 of file network.c.

References SCIP_NETMATDECDATA::numConnectedComponents.

Referenced by constructReducedDecomposition(), constructRowReducedDecomposition(), netcoladdAdd(), and netrowaddAdd().

◆ createChildMarker()

static SCIP_RETCODE createChildMarker	(	SCIP_NETMATDECDATA *	dec,
		spqr_member	member,
		spqr_member	child,
		SCIP_Bool	isTree,
		spqr_arc *	pArc,
		SCIP_Bool	reversed
	)

static

Creates a child marker in the network decomposition.

Parameters

dec	The network matrix decomposition
member	The member to create the arc in
child	The member that the arc points to
isTree	Indicates if the new arc is a tree arc
pArc	Out-pointer to store the new arc's id
reversed	Sets the reversed field of the arc

Definition at line 2554 of file network.c.

References addArcToMemberArcList(), SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::childMember, createArc(), SPQRNetworkDecompositionArc::element, MARKER_COLUMN_ELEMENT, MARKER_ROW_ELEMENT, SCIP_CALL, and SCIP_OKAY.

Referenced by columnTransformSingleRigid(), createMarkerPair(), createMarkerPairWithReferences(), and rigidTransformArcIntoCycle().

◆ createParentMarker()

static SCIP_RETCODE createParentMarker	(	SCIP_NETMATDECDATA *	dec,
		spqr_member	member,
		SCIP_Bool	isTree,
		spqr_member	parent,
		spqr_arc	parentMarker,
		spqr_arc *	arc,
		SCIP_Bool	reversed
	)

static

Creates a parent marker in the network decomposition.

Parameters

dec	The network matrix decomposition
member	The member to create the arc in
isTree	Indicates if the new arc is a tree arc
parent	The member that the arc points to
parentMarker	The parent arc in the parent that points to this member
arc	Out-pointer to store the new arc's id
reversed	Sets the reversed field of the arc

Definition at line 2574 of file network.c.

References addArcToMemberArcList(), SCIP_NETMATDECDATA::arcs, createArc(), SPQRNetworkDecompositionArc::element, MARKER_COLUMN_ELEMENT, MARKER_ROW_ELEMENT, SPQRNetworkDecompositionMember::markerOfParent, SPQRNetworkDecompositionMember::markerToParent, SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::parentMember, SCIP_CALL, and SCIP_OKAY.

Referenced by columnTransformSingleRigid(), createMarkerPair(), createMarkerPairWithReferences(), and rigidTransformArcIntoCycle().

◆ createMarkerPair()

static SCIP_RETCODE createMarkerPair	(	SCIP_NETMATDECDATA *	dec,
		spqr_member	parentMember,
		spqr_member	childMember,
		SCIP_Bool	parentIsTree,
		SCIP_Bool	childMarkerReversed,
		SCIP_Bool	parentMarkerReversed
	)

static

Creates a child-marker parent-marker pair in the network decomposition.

Parameters

dec	The network matrix decomposition
parentMember	The parent member
childMember	The child member
parentIsTree	Is the edge in the parent member (the child marker) a tree edge?
childMarkerReversed	Is the child marker arc reversed?
parentMarkerReversed	IS the parent marker arc reversed?

Definition at line 2598 of file network.c.

References createChildMarker(), createParentMarker(), SCIP_CALL, SCIP_OKAY, and SPQR_INVALID_ARC.

Referenced by splitParallel(), splitParallelRowAddition(), and splitSeries().

◆ createMarkerPairWithReferences()

static SCIP_RETCODE createMarkerPairWithReferences	(	SCIP_NETMATDECDATA *	dec,
		spqr_member	parentMember,
		spqr_member	childMember,
		SCIP_Bool	parentIsTree,
		SCIP_Bool	childMarkerReversed,
		SCIP_Bool	parentMarkerReversed,
		spqr_arc *	parentToChild,
		spqr_arc *	childToParent
	)

static

Creates a child-marker parent-marker pair in the network decomposition, and returns the assigned arc id's.

Parameters

dec	The network matrix decomposition
parentMember	The parent member
childMember	The child member
parentIsTree	Is the edge in the parent member (the child marker) a tree edge?
childMarkerReversed	Is the child marker arc reversed?
parentMarkerReversed	IS the parent marker arc reversed?
parentToChild	Output-pointer containing arc id of the arc in the parent member
childToParent	Output-pointer containing arc id of the arc in the child member

Definition at line 2619 of file network.c.

References createChildMarker(), createParentMarker(), SCIP_CALL, and SCIP_OKAY.

Referenced by netcoladdAdd(), netrowaddAdd(), splitParallelMerging(), splitSeriesMerging(), and splitSeriesMergingRowAddition().

◆ moveArcToNewMember()

static void moveArcToNewMember	(	SCIP_NETMATDECDATA *	dec,
		spqr_arc	arc,
		spqr_member	oldMember,
		spqr_member	newMember
	)

static

Moves a given arc from one member to another, updating the linked lists it is contained in and the parent/child information of the relevant members.

Parameters

dec	The network matrix decomposition
arc	The arc to move
oldMember	The member that currently contains the arc
newMember	The member to move the arc to

Definition at line 2641 of file network.c.

References addArcToMemberArcList(), SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::childMember, findArcChildMember(), findArcChildMemberNoCompression(), findArcMemberNoCompression(), SPQRNetworkDecompositionMember::markerOfParent, SPQRNetworkDecompositionMember::markerToParent, SPQRNetworkDecompositionArc::member, memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::parentMember, removeArcFromMemberArcList(), SPQRarcIsValid(), and SPQRmemberIsValid().

Referenced by netcoladdAdd(), netrowaddAdd(), splitParallel(), splitParallelMerging(), splitParallelRowAddition(), splitSeries(), splitSeriesMerging(), and splitSeriesMergingRowAddition().

◆ mergeMemberArcList()

static void mergeMemberArcList	(	SCIP_NETMATDECDATA *	dec,
		spqr_member	toMergeInto,
		spqr_member	toRemove
	)

static

Merges the arc linked list of two members into one linked list.

Parameters

dec	The network matrix decomposition
toMergeInto	The member id that gets the new large linked list containing both
toRemove	The member id that is invalidated, whose linked list is moved away.

Definition at line 2683 of file network.c.

References SPQRNetworkDecompositionArc::arcListNode, SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionMember::firstArc, getFirstMemberArc(), getPreviousMemberArc(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionArcListNode::next, SPQRNetworkDecompositionMember::numArcs, SPQRNetworkDecompositionArcListNode::previous, SPQR_INVALID_ARC, and SPQRarcIsValid().

Referenced by mergeGivenMemberIntoParent(), and mergeSplitMemberIntoParent().

◆ changeLoopToSeries()

static void changeLoopToSeries	(	SCIP_NETMATDECDATA *	dec,
		spqr_member	member
	)

static

Changes the type of a member from loop to series.

Parameters

dec	The network matrix decomposition
member	The member whose type is changed

Definition at line 2711 of file network.c.

References getMemberType(), getNumMemberArcs(), memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_SERIES, SPQRmemberIsValid(), and SPQRNetworkDecompositionMember::type.

Referenced by netrowaddAdd(), splitParallelRowAddition(), and transformComponentRowAddition().

◆ changeLoopToParallel()

static void changeLoopToParallel	(	SCIP_NETMATDECDATA *	dec,
		spqr_member	member
	)

static

Changes the type of a member from loop to parallel.

Parameters

dec	The network matrix decomposition
member	The member whose type is changed

Definition at line 2729 of file network.c.

References getMemberType(), getNumMemberArcs(), memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_SERIES, SPQRmemberIsValid(), and SPQRNetworkDecompositionMember::type.

Referenced by netcoladdAdd(), and splitSeries().

◆ netMatDecDataIsMinimal()

static SCIP_Bool netMatDecDataIsMinimal ( const SCIP_NETMATDECDATA * dec )

static

Checks if the network decomposition is minimal, i.e. if it does not contain two adjacent parallel or series members.

Parameters

dec	The network matrix decomposition

Definition at line 2749 of file network.c.

References FALSE, findMemberParentNoCompression(), getMemberType(), memberIsRepresentative(), SCIP_NETMATDECDATA::numMembers, SCIP_Bool, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_UNASSIGNED, SPQRmemberIsValid(), and TRUE.

Referenced by SCIPnetmatdecIsMinimal().

◆ decreaseNumConnectedComponents()

static void decreaseNumConnectedComponents	(	SCIP_NETMATDECDATA *	dec,
		int	by
	)

static

Decreases the count of the number of connected components in the network matrix decomposition.

Parameters

dec	The network matrix decomposition
by	The number of connected components to remove.

Definition at line 2779 of file network.c.

References SCIP_NETMATDECDATA::numConnectedComponents.

Referenced by netcoladdAdd(), and netrowaddAdd().

◆ reorderComponent()

static void reorderComponent	(	SCIP_NETMATDECDATA *	dec,
		spqr_member	newRoot
	)

static

Reorders the arborescence of the SPQR that contains a given member so that the given member becomes the new root of the arborescence.

Parameters

dec	The network matrix decomposition
newRoot	The member to make the new root

Definition at line 2792 of file network.c.

References SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::childMember, findMemberParent(), SPQRNetworkDecompositionMember::markerOfParent, SPQRNetworkDecompositionMember::markerToParent, memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::parentMember, SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, SPQRmemberIsValid(), and TRUE.

Referenced by netcoladdAdd(), and netrowaddAdd().

◆ netMatDecDataRemoveComponent()

static void netMatDecDataRemoveComponent	(	SCIP_NETMATDECDATA *	dec,
		const int *	componentRows,
		int	numRows,
		const int *	componentCols,
		int	numCols
	)

static

Deletes the SPQR tree (connected component) containing the given component rows and columns.

Note that the implementation of this method does not actually modify the SPQR tree, but rather unlinks the rows and columns from the relevant arcs. Thus, this method is a bit hacky and should be used with care.

Parameters

dec	The network matrix decomposition
componentRows	The rows of the connected component
numRows	The number of rows
componentCols	The columns of the connected component
numCols	The number of columns

Definition at line 2847 of file network.c.

References SCIP_NETMATDECDATA::columnArcs, SCIP_NETMATDECDATA::rowArcs, SPQR_INVALID_ARC, and SPQRarcIsValid().

Referenced by SCIPnetmatdecRemoveComponent().

◆ mergeGivenMemberIntoParent()

static SCIP_RETCODE mergeGivenMemberIntoParent	(	SCIP_NETMATDECDATA *	dec,
		spqr_member	member,
		spqr_member	parent,
		spqr_arc	parentToChild,
		spqr_arc	childToParent,
		SCIP_Bool	headToHead,
		spqr_member *	mergedMember
	)

static

Parameters

dec	The network matrix decomposition
member	The member to merge
parent	The parent of the member to merge into
parentToChild	The arc from the parent pointing to the member
childToParent	The arc in the child pointing to the parent
headToHead	Identify the head of parentToChild with the head of childToParent?
mergedMember	Out-pointer to the member id of the final member

Definition at line 3052 of file network.c.

References clearArcHeadAndTail(), findEffectiveArcHead(), findEffectiveArcTail(), findMemberParentNoCompression(), markerOfParent(), markerToParent(), memberIsRepresentative(), mergeMemberArcList(), mergeMembers(), mergeNodeArcList(), mergeNodes(), removeArcFromMemberArcList(), SCIP_OKAY, SPQR_MEMBERTYPE_RIGID, SPQRmemberIsValid(), updateMemberParentInformation(), and updateMemberType().

Referenced by transformAndMergeParallel(), transformAndMergeRigid(), and transformAndMergeSeries().

◆ netMatDecDataCreateDiGraph()

static SCIP_RETCODE netMatDecDataCreateDiGraph	(	SCIP_NETMATDECDATA *	dec,
		BMS_BLKMEM *	blkmem,
		SCIP_DIGRAPH **	pdigraph,
		SCIP_Bool	createrowarcs
	)

static

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 3111 of file network.c.

References arcGetElement(), arcIsChildMarker(), arcIsReversedNonRigid(), arcIsTree(), BMSallocBlockMemoryArray, BMSallocClearBlockMemoryArray, BMSfreeBlockMemoryArray, findArcChildMember(), findArcHead(), findArcMember(), findArcSign(), findArcTail(), findEffectiveArcHeadNoCompression(), findEffectiveArcTailNoCompression(), findMemberParent(), getFirstMemberArc(), getMemberType(), getNextMemberArc(), getNumMemberArcs(), largestMemberID(), largestNodeID(), MARKER_ROW_ELEMENT, markerToParent(), SCIP_NETMATDECDATA::memRows, netMatDecDataContainsRow(), ArcSign::reversed, SCIP_NETMATDECDATA::rowArcs, SCIP_ALLOC, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPABORT, SCIPdigraphAddArc(), SCIPdigraphCreate(), SCIPerrorMessage, SCIPswapInts(), SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_SERIES, SPQR_MEMBERTYPE_UNASSIGNED, SPQRarcIsInvalid(), SPQRelementIsRow(), SPQRelementToColumn(), SPQRelementToRow(), SPQRmemberIsInvalid(), and TRUE.

Referenced by SCIPnetmatdecCreateDiGraph().

◆ pathArcIsInvalid()

static SCIP_Bool pathArcIsInvalid ( const path_arc_id arc )

static

Returns true if the path arc is invalid.

Parameters

arc	The path arc to check

Definition at line 3443 of file network.c.

Referenced by determinePathRigidType(), and pathArcIsValid().

◆ pathArcIsValid()

static SCIP_Bool pathArcIsValid ( const path_arc_id arc )

static

Returns true if the path arc is valid.

Parameters

arc	The path arc to check

Definition at line 3452 of file network.c.

References pathArcIsInvalid().

Referenced by checkLeaf(), cleanupPreviousIteration(), columnTransformSingleParallel(), determinePathParallelType(), determinePathSeriesType(), determineRigidPath(), determineSingleComponentType(), determineSingleRigidType(), splitSeries(), and splitSeriesMerging().

◆ reducedMemberIsInvalid()

static SCIP_Bool reducedMemberIsInvalid ( const reduced_member_id id )

static

Returns true if the reduced member is invalid.

Parameters

id	The reduced member to check

Definition at line 3484 of file network.c.

Referenced by cleanUpMemberInformation(), cleanUpRowMemberInformation(), constructReducedDecomposition(), constructRowReducedDecomposition(), createReducedMembersToRoot(), createRowReducedMembersToRoot(), reducedMemberIsValid(), and splitSeriesMergingRowAddition().

◆ reducedMemberIsValid()

static SCIP_Bool reducedMemberIsValid ( const reduced_member_id id )

static

Returns true if the reduced member is valid.

Parameters

id	The reduced member to check

Definition at line 3493 of file network.c.

References reducedMemberIsInvalid().

Referenced by checkLeaf(), columnTransformSingleRigid(), constructReducedDecomposition(), constructRowReducedDecomposition(), createReducedDecompositionCutArcs(), createReducedMembersToRoot(), createRowReducedMembersToRoot(), determineMergeableTypes(), determinePathParallelType(), determinePathSeriesType(), determinePathTypes(), determineSingleComponentType(), determineSingleRigidType(), determineSplitTypeSeries(), mergeTree(), propagateComponents(), propagateCycles(), rigidDetermineCandidateNodesFromAdjacentComponents(), splitParallelMerging(), splitSeriesMergingRowAddition(), transformComponent(), transformComponentRowAddition(), and transformPath().

◆ isInto()

static SCIP_Bool isInto ( MemberPathType type )

static

Check if the path type is into.

Parameters

type	The path type to check

Definition at line 3528 of file network.c.

References INTO_HEAD, and INTO_TAIL.

Referenced by determinePathParallelType(), determinePathRigidType(), determinePathSeriesType(), transformAndMergeRigid(), and transformAndMergeSeries().

◆ isHead()

static SCIP_Bool isHead ( MemberPathType type )

static

Check if the path end node is the head or tail node of the corresponding arc.

Parameters

type	The path type to check

Definition at line 3537 of file network.c.

References INTO_HEAD, and OUT_HEAD.

Referenced by determinePathParallelType(), determinePathRigidType(), determinePathSeriesType(), and transformAndMergeSeries().

◆ cleanupPreviousIteration()

static void cleanupPreviousIteration	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol
	)

static

Clean up internal temporary data structures that were used in the previous column iteration.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure

Definition at line 3675 of file network.c.

References PathArcListNode::arc, PathArcListNode::arcHead, SCIP_NETCOLADD::arcInPath, SCIP_NETCOLADD::arcInPathReversed, PathArcListNode::arcTail, FALSE, SCIP_NETCOLADD::firstOverallPathArc, INVALID_PATH_ARC, SCIP_NETCOLADD::memArcsInPath, SCIP_NETCOLADD::memNodePathDegree, PathArcListNode::nextOverall, SCIP_NETCOLADD::nodeInPathDegree, SCIP_NETCOLADD::nodeOutPathDegree, SCIP_NETCOLADD::numPathArcs, pathArcIsValid(), SCIP_NETCOLADD::pathArcs, and SPQRnodeIsValid().

Referenced by netcoladdCheck().

◆ netcoladdCreate()

static SCIP_RETCODE netcoladdCreate	(	BMS_BLKMEM *	blkmem,
		SCIP_NETCOLADD **	pcoladd
	)

static

Create a new network column addition datastructure.

Parameters

blkmem	Block memory
pcoladd	Out-pointer for the created network column addition datastructure

Definition at line 3725 of file network.c.

Referenced by SCIPnetmatdecTryAddCol().

◆ netcoladdFree()

static void netcoladdFree	(	BMS_BLKMEM *	blkmem,
		SCIP_NETCOLADD **	pcoladd
	)

static

Free a network column addition datastructure

Parameters

blkmem	Block memory
pcoladd	Pointer to the network column addition datastructure to be freed

Definition at line 3789 of file network.c.

References SCIP_NETCOLADD::arcInPath, SCIP_NETCOLADD::arcInPathReversed, BMSfreeBlockMemory, BMSfreeBlockMemoryArray, SCIP_NETCOLADD::childrenStorage, SCIP_NETCOLADD::createReducedMembersCallStack, SCIP_NETCOLADD::decompositionArcReversed, SCIP_NETCOLADD::decompositionRowArcs, SCIP_NETCOLADD::leafMembers, SCIP_NETCOLADD::memArcsInPath, SCIP_NETCOLADD::memberInformation, SCIP_NETCOLADD::memChildrenStorage, SCIP_NETCOLADD::memCreateReducedMembersCallStack, SCIP_NETCOLADD::memDecompositionRowArcs, SCIP_NETCOLADD::memLeafMembers, SCIP_NETCOLADD::memMemberInformation, SCIP_NETCOLADD::memNewRowArcs, SCIP_NETCOLADD::memNodePathDegree, SCIP_NETCOLADD::memPathArcs, SCIP_NETCOLADD::memReducedComponents, SCIP_NETCOLADD::memReducedMembers, SCIP_NETCOLADD::newRowArcReversed, SCIP_NETCOLADD::newRowArcs, SCIP_NETCOLADD::nodeInPathDegree, SCIP_NETCOLADD::nodeOutPathDegree, SCIP_NETCOLADD::pathArcs, SCIP_NETCOLADD::reducedComponents, and SCIP_NETCOLADD::reducedMembers.

Referenced by SCIPnetmatdecFree().

◆ createReducedMembersToRoot()

static reduced_member_id createReducedMembersToRoot	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		const spqr_member	firstMember
	)

static

Adds members to the reduced member tree, by starting at the given member, jumping up to the parent, repeating this procedure until the root has been added.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
firstMember	The member to create a reduced member for

Definition at line 3820 of file network.c.

Referenced by constructReducedDecomposition().

◆ constructReducedDecomposition()

static SCIP_RETCODE constructReducedDecomposition	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol
	)

static

Construct the reduced decomposition, which is the smallest subtree containing all members path arcs.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure

Definition at line 3932 of file network.c.

References BMSreallocBlockMemoryArray, SCIP_NETCOLADD::childrenStorage, SCIP_NETCOLADD::createReducedMembersCallStack, createReducedMembersToRoot(), SCIP_NETCOLADD::decompositionRowArcs, SPQRColReducedMember::depth, SCIP_NETMATDECDATA::env, findArcMember(), findMemberParent(), SPQRColReducedMember::firstChild, getNumMembers(), INVALID_REDUCED_MEMBER, largestMemberID(), MAX, SPQRColReducedMember::member, SCIP_NETCOLADD::memberInformation, memberIsRepresentative(), SCIP_NETCOLADD::memChildrenStorage, SCIP_NETCOLADD::memCreateReducedMembersCallStack, SCIP_NETCOLADD::memMemberInformation, SCIP_NETCOLADD::memReducedComponents, SCIP_NETCOLADD::memReducedMembers, SPQRColReducedMember::numChildren, SCIP_NETCOLADD::numChildrenStorage, numConnectedComponents(), SCIP_NETCOLADD::numDecompositionRowArcs, SCIP_NETCOLADD::numReducedComponents, SCIP_NETCOLADD::numReducedMembers, SPQRColReducedMember::parent, SCIP_NETCOLADD::reducedComponents, MemberInfo::reducedMember, reducedMemberIsInvalid(), reducedMemberIsValid(), SCIP_NETCOLADD::reducedMembers, SPQRColReducedComponent::root, SPQRColReducedComponent::rootDepth, MemberInfo::rootDepthMinimizer, SPQRColReducedMember::rootMember, SCIP_ALLOC, SCIP_OKAY, and SPQRmemberIsValid().

Referenced by netcoladdCheck().

◆ cleanUpMemberInformation()

static void cleanUpMemberInformation ( SCIP_NETCOLADD * newCol )

static

Clean up the memberinformation array at the end of an iteration.

Parameters

newCol The network matrix column addition data structure

Definition at line 4079 of file network.c.

References INVALID_REDUCED_MEMBER, SPQRColReducedMember::member, SCIP_NETCOLADD::memberInformation, SCIP_NETCOLADD::memMemberInformation, SCIP_NETCOLADD::numReducedMembers, MemberInfo::reducedMember, reducedMemberIsInvalid(), and SCIP_NETCOLADD::reducedMembers.

Referenced by netcoladdCheck().

◆ createPathArc()

static void createPathArc	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		const spqr_arc	arc,
		const reduced_member_id	reducedMember,
		SCIP_Bool	reversed
	)

static

Marks the given arc as a path arc and adds it to the relevant data structures.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
arc	The arc to mark as a path arc
reducedMember	The reduced member containing the arc
reversed	Indicates if the new column entry has +1 or -1 (TRUE) for the arc

Definition at line 4099 of file network.c.

References PathArcListNode::arc, PathArcListNode::arcHead, SCIP_NETCOLADD::arcInPath, SCIP_NETCOLADD::arcInPathReversed, PathArcListNode::arcTail, findEffectiveArcHead(), findEffectiveArcTail(), SCIP_NETCOLADD::firstOverallPathArc, SPQRColReducedMember::firstPathArc, getMemberType(), SPQRColReducedMember::member, memberIsRepresentative(), SCIP_NETCOLADD::memNodePathDegree, SCIP_NETCOLADD::memPathArcs, PathArcListNode::nextMember, PathArcListNode::nextOverall, SCIP_NETCOLADD::nodeInPathDegree, SCIP_NETCOLADD::nodeOutPathDegree, SPQRColReducedMember::numPathArcs, SCIP_NETCOLADD::numPathArcs, SCIP_NETCOLADD::pathArcs, SCIP_NETCOLADD::reducedMembers, PathArcListNode::reversed, SCIPswapInts(), SPQR_INVALID_NODE, SPQR_MEMBERTYPE_RIGID, SPQRnodeIsValid(), and TRUE.

Referenced by checkLeaf(), checkRigidLeaf(), and createPathArcs().

◆ createPathArcs()

static SCIP_RETCODE createPathArcs	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol
	)

static

Mark all the row indices of the new column as path arcs

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure

Definition at line 4151 of file network.c.

References SCIP_NETCOLADD::arcInPath, SCIP_NETCOLADD::arcInPathReversed, BMSreallocBlockMemoryArray, createPathArc(), SCIP_NETCOLADD::decompositionArcReversed, SCIP_NETCOLADD::decompositionRowArcs, SCIP_NETMATDECDATA::env, FALSE, findArcMember(), getNumMembers(), largestArcID(), largestNodeID(), SCIP_NETCOLADD::memArcsInPath, SCIP_NETCOLADD::memberInformation, SCIP_NETCOLADD::memNodePathDegree, SCIP_NETCOLADD::memPathArcs, SCIP_NETCOLADD::nodeInPathDegree, SCIP_NETCOLADD::nodeOutPathDegree, SCIP_NETCOLADD::numDecompositionRowArcs, SCIP_NETCOLADD::pathArcs, MemberInfo::reducedMember, SCIP_ALLOC, and SCIP_OKAY.

Referenced by netcoladdCheck().

◆ newColUpdateColInformation()

static SCIP_RETCODE newColUpdateColInformation	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		spqr_col	column,
		const spqr_row *	nonzeroRows,
		const double *	nonzeroValues,
		int	numNonzeros
	)

static

Saves the information of the current row and partitions it based on whether or not the given columns are already part of the decomposition.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
column	The column that is checked
nonzeroRows	The column's row indices
nonzeroValues	The column's nonzero values
numNonzeros	The number of nonzeros in the column

Definition at line 4206 of file network.c.

References BMSreallocBlockMemoryArray, SCIP_NETCOLADD::decompositionArcReversed, SCIP_NETCOLADD::decompositionRowArcs, SCIP_NETMATDECDATA::env, getDecompositionRowArc(), SCIP_NETCOLADD::memDecompositionRowArcs, SCIP_NETCOLADD::memNewRowArcs, SCIP_NETCOLADD::newColIndex, SCIP_NETCOLADD::newRowArcReversed, SCIP_NETCOLADD::newRowArcs, SCIP_NETCOLADD::numDecompositionRowArcs, SCIP_NETCOLADD::numNewRowArcs, SCIP_ALLOC, SCIP_Bool, SCIP_OKAY, and SPQRarcIsValid().

Referenced by netcoladdCheck().

◆ computeLeafMembers()

static SCIP_RETCODE computeLeafMembers	(	const SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol
	)

static

Compute and store the leaf members of the reduced SPQR forest

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure

Definition at line 4262 of file network.c.

References BMSreallocBlockMemoryArray, SCIP_NETMATDECDATA::env, SCIP_NETCOLADD::leafMembers, MAX, SCIP_NETCOLADD::memLeafMembers, SPQRColReducedMember::numChildren, SCIP_NETCOLADD::numLeafMembers, SCIP_NETCOLADD::numReducedMembers, SCIP_NETCOLADD::reducedMembers, SCIP_ALLOC, and SCIP_OKAY.

Referenced by netcoladdCheck().

◆ determineRigidPath()

static void determineRigidPath	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		SPQRColReducedMember *	redMem
	)

static

Checks if the path arcs in the given rigid member form a path

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
redMem	The rigid reduced member to determine the path in

Definition at line 4289 of file network.c.

References PathArcListNode::arcHead, PathArcListNode::arcTail, FALSE, SPQRColReducedMember::firstPathArc, PathArcListNode::nextMember, SCIP_NETCOLADD::nodeInPathDegree, nodeIsRepresentative(), SCIP_NETCOLADD::nodeOutPathDegree, pathArcIsValid(), SCIP_NETCOLADD::pathArcs, REDUCEDMEMBER_TYPE_NOT_NETWORK, SCIP_NETCOLADD::remainsNetwork, SPQRColReducedMember::rigidPathEnd, SPQRColReducedMember::rigidPathStart, SCIP_Bool, SPQR_INVALID_NODE, SPQRnodeIsValid(), TRUE, and SPQRColReducedMember::type.

Referenced by checkRigidLeaf(), determinePathRigidType(), and determineSingleRigidType().

◆ determineSingleRigidType()

static void determineSingleRigidType	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		reduced_member_id	reducedMember
	)

static

Determines the member's type for the case where the reduced tree consists of a single rigid member.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
reducedMember	The reduced member to check

Definition at line 4353 of file network.c.

References determineRigidPath(), SPQRColReducedMember::firstPathArc, pathArcIsValid(), REDUCEDMEMBER_TYPE_MERGED, REDUCEDMEMBER_TYPE_NOT_NETWORK, reducedMemberIsValid(), SCIP_NETCOLADD::reducedMembers, and SPQRColReducedMember::type.

Referenced by determineSingleComponentType().

◆ determineSingleComponentType()

static void determineSingleComponentType	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		reduced_member_id	reducedMember
	)

static

Determines the member's type for the case where the reduced tree consists of a single member.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
reducedMember	The reduced member to check

Definition at line 4374 of file network.c.

References PathArcListNode::arc, arcIsReversedNonRigid(), determineSingleRigidType(), FALSE, findMember(), SPQRColReducedMember::firstPathArc, getMemberType(), getNumMemberArcs(), SPQRColReducedMember::member, PathArcListNode::nextMember, SPQRColReducedMember::numChildren, SPQRColReducedMember::numPropagatedChildren, SPQRColReducedMember::parent, pathArcIsValid(), SCIP_NETCOLADD::pathArcs, SPQRColReducedMember::pathBackwards, REDUCEDMEMBER_TYPE_CYCLE, REDUCEDMEMBER_TYPE_MERGED, REDUCEDMEMBER_TYPE_NOT_NETWORK, reducedMemberIsValid(), SCIP_NETCOLADD::reducedMembers, SCIP_NETCOLADD::remainsNetwork, PathArcListNode::reversed, SCIP_Bool, SCIPABORT, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_SERIES, SPQR_MEMBERTYPE_UNASSIGNED, TRUE, and SPQRColReducedMember::type.

Referenced by determineComponentTypes().

◆ determinePathSeriesType()

static void determinePathSeriesType	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		reduced_member_id	reducedMember,
		spqr_member	member,
		MemberPathType	previousType,
		spqr_arc	source,
		spqr_arc	target
	)

static

Determines the path type of a series member.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
reducedMember	The reduced member to check
member	The reduced member's member id
previousType	Type of the previous reduced member in the path
source	The marker connecting to the previous reduced member in the path
target	The marker connecting to the next reduced member in the path

Definition at line 4473 of file network.c.

References PathArcListNode::arc, arcIsReversedNonRigid(), FALSE, SPQRColReducedMember::firstPathArc, getMemberType(), INTO_HEAD, INTO_TAIL, isHead(), isInto(), memberIsRepresentative(), PathArcListNode::nextMember, OUT_HEAD, OUT_TAIL, pathArcIsValid(), SCIP_NETCOLADD::pathArcs, SPQRColReducedMember::pathBackwards, SPQRColReducedMember::pathType, REDUCEDMEMBER_TYPE_NOT_NETWORK, reducedMemberIsValid(), SCIP_NETCOLADD::reducedMembers, SCIP_NETCOLADD::remainsNetwork, PathArcListNode::reversed, SCIP_Bool, SPQR_MEMBERTYPE_SERIES, SPQRarcIsValid(), SPQRmemberIsValid(), TRUE, and SPQRColReducedMember::type.

Referenced by determinePathMemberType().

◆ determinePathParallelType()

static void determinePathParallelType	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		reduced_member_id	reducedMember,
		spqr_member	member,
		MemberPathType	previousType,
		spqr_arc	source,
		spqr_arc	target
	)

static

Determines the path type of a parallel member.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
reducedMember	The reduced member to check
member	The reduced member's member id
previousType	Type of the previous reduced member in the path
source	The marker connecting to the previous reduced member in the path
target	The marker connecting to the next reduced member in the path

Definition at line 4599 of file network.c.

References PathArcListNode::arc, arcIsReversedNonRigid(), FALSE, SPQRColReducedMember::firstPathArc, getMemberType(), INTO_HEAD, INTO_TAIL, isHead(), isInto(), memberIsRepresentative(), OUT_HEAD, OUT_TAIL, pathArcIsValid(), SCIP_NETCOLADD::pathArcs, SPQRColReducedMember::pathType, REDUCEDMEMBER_TYPE_NOT_NETWORK, reducedMemberIsValid(), SCIP_NETCOLADD::reducedMembers, SCIP_NETCOLADD::remainsNetwork, PathArcListNode::reversed, SCIP_Bool, SPQR_MEMBERTYPE_PARALLEL, SPQRarcIsValid(), SPQRmemberIsValid(), TRUE, and SPQRColReducedMember::type.

Referenced by determinePathMemberType().

◆ determinePathRigidType()

static void determinePathRigidType	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		reduced_member_id	reducedMember,
		MemberPathType	previousType,
		spqr_arc	source,
		spqr_arc	target
	)

static

Determines the path type of a rigid member.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
reducedMember	The reduced member to check
previousType	Type of the previous reduced member in the path
source	The marker connecting to the previous reduced member in the path
target	The marker connecting to the next reduced member in the path

Definition at line 4669 of file network.c.

References determineRigidPath(), FALSE, findEffectiveArcHead(), findEffectiveArcTail(), SPQRColReducedMember::firstPathArc, INTO_HEAD, INTO_TAIL, isHead(), isInto(), OUT_HEAD, OUT_TAIL, pathArcIsInvalid(), SPQRColReducedMember::pathType, REDUCEDMEMBER_TYPE_NOT_NETWORK, SCIP_NETCOLADD::reducedMembers, SCIP_NETCOLADD::remainsNetwork, SPQRColReducedMember::reverseArcs, SPQRColReducedMember::rigidPathEnd, SPQRColReducedMember::rigidPathStart, SCIP_Bool, SPQRarcIsInvalid(), SPQRarcIsValid(), TRUE, and SPQRColReducedMember::type.

Referenced by determinePathMemberType().

◆ determinePathMemberType()

static void determinePathMemberType	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		reduced_member_id	reducedMember,
		spqr_member	member,
		MemberPathType	previousType,
		spqr_arc	source,
		spqr_arc	target
	)

static

Determines the path type of a single member.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
reducedMember	The reduced member to check
member	The reduced member's member id
previousType	Type of the previous reduced member in the path
source	The marker connecting to the previous reduced member in the path
target	The marker connecting to the next reduced member in the path

Definition at line 5008 of file network.c.

References determinePathParallelType(), determinePathRigidType(), determinePathSeriesType(), FALSE, getMemberType(), SPQRColReducedMember::pathSourceArc, SPQRColReducedMember::pathTargetArc, SCIP_NETCOLADD::reducedMembers, SCIP_NETCOLADD::remainsNetwork, SCIPABORT, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_SERIES, and SPQR_MEMBERTYPE_UNASSIGNED.

Referenced by determinePathTypes().

◆ determinePathTypes()

static void determinePathTypes	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		SPQRColReducedComponent *	component
	)

static

Determines the path types of all reduced members.

The reduced members themselves also form a path in the reduced decomposition.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
component	The component to determine the path types for

Definition at line 5055 of file network.c.

References SCIP_NETCOLADD::childrenStorage, determinePathMemberType(), FALSE, findMemberParent(), SPQRColReducedMember::firstChild, INTO_HEAD, INVALID_REDUCED_MEMBER, markerOfParent(), markerToParent(), SPQRColReducedMember::member, SCIP_NETCOLADD::memberInformation, SPQRColReducedMember::nextPathMember, SPQRColReducedMember::nextPathMemberIsParent, SPQRColReducedMember::numChildren, SPQRColReducedComponent::numPathEndMembers, SPQRColReducedComponent::pathEndMembers, SPQRColReducedMember::pathType, MemberInfo::reducedMember, REDUCEDMEMBER_TYPE_CYCLE, reducedMemberIsValid(), SCIP_NETCOLADD::reducedMembers, SCIP_NETCOLADD::remainsNetwork, SPQRColReducedComponent::root, SPQR_INVALID_ARC, TRUE, and SPQRColReducedMember::type.

Referenced by determineComponentTypes().

◆ checkRigidLeaf()

static void checkRigidLeaf	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		reduced_member_id	leaf,
		spqr_arc	toParent,
		reduced_member_id	parent,
		spqr_arc	toChild
	)

static

Check if a rigid leaf closes a cycle with its child.

If so, we can propagate this cycle to a virtual arc of the child node member and shrink the decomposition.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
leaf	The leaf node of the reduced SPQR tree
toParent	The virtual arc to the leaf node's neighbour
parent	The neighbouring member of the leaf node.
toChild	The virtual arc from the neighbouring member pointing to the leaf.

Definition at line 5144 of file network.c.

References createPathArc(), determineRigidPath(), findEffectiveArcHead(), findEffectiveArcTail(), REDUCEDMEMBER_TYPE_CYCLE, REDUCEDMEMBER_TYPE_MERGED, REDUCEDMEMBER_TYPE_NOT_NETWORK, SCIP_NETCOLADD::reducedMembers, SPQRColReducedMember::rigidPathEnd, SPQRColReducedMember::rigidPathStart, SCIP_Bool, and SPQRColReducedMember::type.

Referenced by checkLeaf().

◆ checkLeaf()

static ReducedMemberType checkLeaf	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		reduced_member_id	leaf,
		spqr_arc	toParent,
		reduced_member_id	parent,
		spqr_arc	toChild
	)

static

Check if a leaf node closes a cycle with its child.

If so, we can propagate this cycle to a virtual arc of the child node member and shrink the decomposition.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
leaf	The leaf node of the reduced SPQR tree
toParent	The virtual arc to the leaf node's neighbour
parent	The neighbouring member of the leaf node.
toChild	The virtual arc from the neighbouring member pointing to the leaf.

Definition at line 5177 of file network.c.

References PathArcListNode::arc, arcIsReversedNonRigid(), arcIsTree(), checkRigidLeaf(), createPathArc(), FALSE, findMember(), SPQRColReducedMember::firstPathArc, getMemberType(), getNumMemberArcs(), SPQRColReducedMember::member, PathArcListNode::nextMember, pathArcIsValid(), SCIP_NETCOLADD::pathArcs, SPQRColReducedMember::pathBackwards, REDUCEDMEMBER_TYPE_CYCLE, REDUCEDMEMBER_TYPE_MERGED, REDUCEDMEMBER_TYPE_NOT_NETWORK, reducedMemberIsValid(), SCIP_NETCOLADD::reducedMembers, SCIP_NETCOLADD::remainsNetwork, PathArcListNode::reversed, SCIP_Bool, SCIPABORT, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_SERIES, SPQR_MEMBERTYPE_UNASSIGNED, SPQRarcIsValid(), TRUE, and SPQRColReducedMember::type.

Referenced by propagateCycles().

◆ propagateCycles()

static void propagateCycles	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol
	)

static

Recursively removes leaf nodes whose path forms cycles with the virtual arc to its children.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure

Definition at line 5277 of file network.c.

References arcIsTree(), checkLeaf(), SCIP_NETCOLADD::childrenStorage, SPQRColReducedMember::componentIndex, FALSE, SPQRColReducedMember::firstChild, INVALID_REDUCED_MEMBER, SCIP_NETCOLADD::leafMembers, markerOfParent(), markerToParent(), SPQRColReducedMember::member, SPQRColReducedMember::numChildren, SCIP_NETCOLADD::numLeafMembers, SPQRColReducedComponent::numPathEndMembers, SPQRColReducedMember::numPropagatedChildren, SCIP_NETCOLADD::numReducedComponents, SPQRColReducedMember::parent, SPQRColReducedComponent::pathEndMembers, SCIP_NETCOLADD::reducedComponents, REDUCEDMEMBER_TYPE_CYCLE, REDUCEDMEMBER_TYPE_MERGED, REDUCEDMEMBER_TYPE_NOT_NETWORK, reducedMemberIsValid(), SCIP_NETCOLADD::reducedMembers, SCIP_NETCOLADD::remainsNetwork, SPQRColReducedComponent::root, SCIP_Bool, SPQR_INVALID_ARC, SPQRarcIsValid(), SPQRmemberIsValid(), TRUE, and SPQRColReducedMember::type.

Referenced by netcoladdCheck().

◆ determineComponentTypes()

static void determineComponentTypes	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		SPQRColReducedComponent *	component
	)

static

Determine the type of a single component.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
component	The component to determine the types for

Definition at line 5412 of file network.c.

References determinePathTypes(), determineSingleComponentType(), SPQRColReducedComponent::numPathEndMembers, SPQRColReducedComponent::pathEndMembers, and SPQRColReducedComponent::root.

Referenced by netcoladdCheck().

◆ netcoladdCheck()

static SCIP_RETCODE netcoladdCheck	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	coladd,
		int	column,
		const int *	nonzrows,
		const double *	nonzvals,
		int	nnonzs
	)

static

Checks if the given column can be added to the network matrix decomposition.

See header for more info.

Parameters

dec	The network matrix decomposition
coladd	The network matrix column addition data structure
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

Definition at line 5439 of file network.c.

References cleanUpMemberInformation(), cleanupPreviousIteration(), computeLeafMembers(), constructReducedDecomposition(), createPathArcs(), determineComponentTypes(), netMatDecDataContainsColumn(), newColUpdateColInformation(), SCIP_NETCOLADD::numReducedComponents, propagateCycles(), SCIP_NETCOLADD::reducedComponents, SCIP_NETCOLADD::remainsNetwork, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, and TRUE.

Referenced by SCIPnetmatdecTryAddCol().

◆ setTerminalHead()

static void setTerminalHead	(	NewColInformation *	info,
		spqr_node	node
	)

static

Set the head node of the new column edge to be added.

Parameters

info	The new column information
node	The head node of the new column edge

Definition at line 5502 of file network.c.

References NewColInformation::head, SPQRnodeIsInvalid(), and SPQRnodeIsValid().

Referenced by columnTransformSingleRigid(), transformAndMergeRigid(), transformAndMergeSeries(), and transformFirstPathMember().

◆ setTerminalTail()

static void setTerminalTail	(	NewColInformation *	info,
		spqr_node	node
	)

static

Set the tail node of the new column edge to be added.

Parameters

info	The new column information
node	The tail node of the new column edge

Definition at line 5516 of file network.c.

References SPQRnodeIsInvalid(), SPQRnodeIsValid(), and NewColInformation::tail.

Referenced by columnTransformSingleRigid(), transformAndMergeRigid(), transformAndMergeSeries(), and transformFirstPathMember().

◆ setTerminalReversed()

static void setTerminalReversed	(	NewColInformation *	info,
		SCIP_Bool	reversed
	)

static

Set whether the new column arc should be reversed.

Parameters

info	The new column information
reversed	Should the new column arc be reversed?

Definition at line 5530 of file network.c.

References NewColInformation::reversed.

Referenced by columnTransformSingleParallel(), columnTransformSingleRigid(), splitSeries(), transformAndMergeRigid(), and transformAndMergeSeries().

◆ setTerminalMember()

static void setTerminalMember	(	NewColInformation *	info,
		spqr_member	member
	)

static

Set the member that contains the new column arc.

Parameters

info	The new column information
member	The decomposition member that contains the new column arc

Definition at line 5542 of file network.c.

References NewColInformation::member.

Referenced by columnTransformSingleParallel(), columnTransformSingleRigid(), splitSeries(), transformAndMergeRigid(), and transformAndMergeSeries().

◆ setTerminalRepresentative()

static void setTerminalRepresentative	(	NewColInformation *	info,
		spqr_arc	representative
	)

static

Set the representative arc of the new column arc.

Parameters

info	The new column information
representative	The representative arc of the new column arc

Definition at line 5554 of file network.c.

References NewColInformation::representative.

Referenced by columnTransformSingleRigid(), transformAndMergeRigid(), and transformAndMergeSeries().

◆ splitParallel()

static SCIP_RETCODE splitParallel	(	SCIP_NETMATDECDATA *	dec,
		spqr_member	parallel,
		spqr_arc	arc1,
		spqr_arc	arc2,
		spqr_member *	childParallel
	)

static

Splits a parallel member into two adjacent parallel members connected by a virtual edge pair.

One member keeps the two arcs passed to this function, the other member gets all other arcs.

Parameters

dec	The network matrix decomposition
parallel	The parallel member
arc1	First arc to keep.
arc2	Second arc to keep.
childParallel	Out pointer to the new child parallel member.

Definition at line 5569 of file network.c.

References arcIsTree(), createMarkerPair(), createMember(), FALSE, markerToParent(), moveArcToNewMember(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SPQR_MEMBERTYPE_PARALLEL, SPQRarcIsValid(), and SPQRmemberIsValid().

Referenced by transformAndMergeParallel().

◆ splitSeries()

static SCIP_RETCODE splitSeries	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		SPQRColReducedMember *	reducedMember,
		spqr_member	member,
		spqr_member *	loopMember,
		NewColInformation *	newColInfo
	)

static

Very elaborate function that splits a series member into multiple members based on the structure of the path arcs.

The updated member reflects the structure of the updated SPQR tree after the new column arc is added.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
reducedMember	The reduced member of the series member to split.
member	The series member to split.
loopMember	Out-pointer to a new loop member that may be created
newColInfo	New column information struct

Definition at line 5607 of file network.c.

References PathArcListNode::arc, arcFlipReversed(), SCIP_NETCOLADD::arcInPath, arcIsChildMarker(), arcIsReversedNonRigid(), changeLoopToParallel(), createMarkerPair(), createMember(), FALSE, findArcChildMember(), findMemberParent(), SPQRColReducedMember::firstPathArc, getFirstMemberArc(), getMemberType(), getNextMemberArc(), getNumMemberArcs(), markerOfParent(), markerToParent(), SPQRColReducedMember::member, memberIsRepresentative(), moveArcToNewMember(), PathArcListNode::nextMember, SPQRColReducedMember::numPathArcs, pathArcIsValid(), SCIP_NETCOLADD::pathArcs, SPQRColReducedMember::pathBackwards, SCIP_Bool, SCIP_CALL, SCIP_OKAY, setTerminalMember(), setTerminalReversed(), SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_SERIES, SPQRmemberIsValid(), and TRUE.

Referenced by columnTransformSingleSeries().

◆ splitSeriesMerging()

static SCIP_RETCODE splitSeriesMerging	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		SPQRColReducedMember *	reducedMember,
		spqr_member	member,
		spqr_arc *	pathRepresentative,
		spqr_arc *	nonPathRepresentative,
		spqr_arc	exceptionArc1,
		spqr_arc	exceptionArc2
	)

static

Very elaborate function that splits a series member into multiple members based on the structure of the path arcs.

The updated member reflects the structure of the updated SPQR tree after the new column arc is added. This variant is only used on series members that are part of a reduced tree that is not a single member.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
reducedMember	The reduced member of the series member to split.
member	The series member to split.
pathRepresentative	Out pointer pointing to the tree arc in the final series node
nonPathRepresentative	Out pointer pointing to the non-tree arc in the final series node
exceptionArc1	The first exception arc. Set to SPQR_INVALID_ARC to ignore
exceptionArc2	The second exception arc. Set to SPQR_INVALID_ARC to ignore

Definition at line 5789 of file network.c.

References PathArcListNode::arc, SCIP_NETCOLADD::arcInPath, arcIsTree(), createMarkerPairWithReferences(), createMember(), FALSE, SPQRColReducedMember::firstPathArc, getFirstMemberArc(), getNextMemberArc(), getNumMemberArcs(), markerToParent(), memberIsRepresentative(), moveArcToNewMember(), PathArcListNode::nextMember, SPQRColReducedMember::numPathArcs, pathArcIsValid(), SCIP_NETCOLADD::pathArcs, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SPQR_INVALID_ARC, SPQR_MEMBERTYPE_SERIES, SPQRarcIsValid(), SPQRmemberIsValid(), and TRUE.

Referenced by transformAndMergeSeries(), and transformFirstPathMember().

◆ transformFirstPathMember()

static SCIP_RETCODE transformFirstPathMember	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		reduced_member_id	reducedMember,
		NewColInformation *	newColInfo,
		spqr_arc *	representativeArc,
		spqr_member *	mergedMember
	)

static

Transforms the first member in the path of members to reflect the new column update.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
reducedMember	The reduced member to transform
newColInfo	The new column information
representativeArc	Pointer to the representative of the member, needed for merging.
mergedMember	Pointer to the merged member

Definition at line 5929 of file network.c.

References a, arcIsReversedNonRigid(), arcSetRepresentative(), arcSetReversed(), b, createNode(), FALSE, findArcSign(), getMemberType(), getNumMemberArcs(), INTO_HEAD, INTO_TAIL, SPQRColReducedMember::member, OUT_HEAD, OUT_TAIL, SPQRColReducedMember::pathTargetArc, SPQRColReducedMember::pathType, SCIP_NETCOLADD::reducedMembers, ArcSign::representative, SPQRColReducedMember::rigidPathEnd, SPQRColReducedMember::rigidPathStart, SCIP_Bool, SCIP_CALL, SCIP_OKAY, setArcHeadAndTail(), setTerminalHead(), setTerminalTail(), splitSeriesMerging(), SPQR_INVALID_ARC, SPQR_INVALID_NODE, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_SERIES, and SPQRarcIsValid().

Referenced by transformPath().

◆ transformAndMergeParallel()

static SCIP_RETCODE transformAndMergeParallel	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		reduced_member_id	current,
		reduced_member_id	next,
		spqr_member	nextMember,
		SCIP_Bool	nextIsParent,
		spqr_arc *	representativeArc,
		spqr_member *	mergedMember
	)

static

Transforms the next parallel member in the path of members and merge it into the current member.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
current	The current reduced member id
next	The next reduced member
nextMember	The member of the next reduced member in the path
nextIsParent	Is the next reduced member the parent of the current member?
representativeArc	Pointer to the representative of the member, needed for merging.
mergedMember	Pointer to the merged member

Definition at line 6034 of file network.c.

References arcIsReversedNonRigid(), arcSetRepresentative(), arcSetReversed(), createNode(), FALSE, getFirstMemberArc(), getNextMemberArc(), getNumMemberArcs(), INVALID_REDUCED_MEMBER, SPQRColReducedMember::member, mergeArcSigns(), mergeGivenMemberIntoParent(), SPQRColReducedMember::pathSourceArc, SPQRColReducedMember::pathTargetArc, SCIP_NETCOLADD::reducedMembers, SCIP_Bool, SCIP_CALL, SCIP_OKAY, setArcHeadAndTail(), splitParallel(), SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, and TRUE.

Referenced by transformAndMerge().

◆ transformAndMergeSeries()

static SCIP_RETCODE transformAndMergeSeries	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		reduced_member_id	current,
		reduced_member_id	next,
		spqr_member	nextMember,
		SCIP_Bool	nextIsParent,
		spqr_arc *	representativeArc,
		spqr_member *	mergedMember,
		NewColInformation *	info
	)

static

Transforms the next series member in the path of members and merge it into the current member.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
current	The current reduced member id
next	The next reduced member
nextMember	The member of the next reduced member in the path
nextIsParent	Is the next reduced member the parent of the current member?
representativeArc	Pointer to the representative of the member, needed for merging.
mergedMember	Pointer to the merged member
info	The new column information

Definition at line 6111 of file network.c.

References a, arcIsReversedNonRigid(), arcSetRepresentative(), arcSetReversed(), b, createNode(), FALSE, getNumMemberArcs(), isHead(), isInto(), mergeArcSigns(), mergeGivenMemberIntoParent(), SPQRColReducedMember::pathSourceArc, SPQRColReducedMember::pathTargetArc, SPQRColReducedMember::pathType, SCIP_NETCOLADD::reducedMembers, SCIP_Bool, SCIP_CALL, SCIP_OKAY, setArcHeadAndTail(), setTerminalHead(), setTerminalMember(), setTerminalRepresentative(), setTerminalReversed(), setTerminalTail(), splitSeriesMerging(), SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, SPQRarcIsInvalid(), SPQRarcIsValid(), and TRUE.

Referenced by transformAndMerge().

◆ transformAndMergeRigid()

static SCIP_RETCODE transformAndMergeRigid	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		reduced_member_id	current,
		reduced_member_id	next,
		spqr_member	nextMember,
		SCIP_Bool	nextIsParent,
		spqr_arc *	representativeArc,
		spqr_member *	mergedMember,
		NewColInformation *	info
	)

static

Transforms the next rigid member in the path of members and merge it into the current member.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
current	The current reduced member id
next	The next reduced member
nextMember	The member of the next reduced member in the path
nextIsParent	Is the next reduced member the parent of the current member?
representativeArc	Pointer to the representative of the member, needed for merging.
mergedMember	Pointer to the merged member
info	The new column information

Definition at line 6264 of file network.c.

References FALSE, findArcSign(), isInto(), mergeArcSigns(), mergeGivenMemberIntoParent(), SPQRColReducedMember::pathSourceArc, SPQRColReducedMember::pathTargetArc, SPQRColReducedMember::pathType, SCIP_NETCOLADD::reducedMembers, ArcSign::representative, SPQRColReducedMember::reverseArcs, SPQRColReducedMember::rigidPathEnd, SPQRColReducedMember::rigidPathStart, SCIP_CALL, SCIP_OKAY, setTerminalHead(), setTerminalMember(), setTerminalRepresentative(), setTerminalReversed(), setTerminalTail(), SPQR_INVALID_MEMBER, and SPQRarcIsInvalid().

Referenced by transformAndMerge().

◆ transformAndMerge()

static SCIP_RETCODE transformAndMerge	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		reduced_member_id	current,
		reduced_member_id	next,
		spqr_arc *	representativeArc,
		spqr_member *	mergedMember,
		SCIP_Bool	nextIsParent,
		NewColInformation *	info
	)

static

Transforms the next member in the path of members and merge it into the current member.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
current	The current reduced member id
next	The next reduced member
representativeArc	Pointer to the representative of the member, needed for merging.
mergedMember	Pointer to the merged member
nextIsParent	Is the next reduced member the parent of the current member?
info	The new column information

Definition at line 6334 of file network.c.

References getMemberType(), SPQRColReducedMember::member, SCIP_NETCOLADD::reducedMembers, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPABORT, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_SERIES, SPQR_MEMBERTYPE_UNASSIGNED, transformAndMergeParallel(), transformAndMergeRigid(), and transformAndMergeSeries().

Referenced by transformPath().

◆ transformPath()

static SCIP_RETCODE transformPath	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		SPQRColReducedComponent *	component,
		NewColInformation *	newColInfo
	)

static

Transforms a single component when it contains multiple reduced members.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
component	The component to transform
newColInfo	The new column information

Definition at line 6378 of file network.c.

References SPQRColReducedMember::nextPathMember, SPQRColReducedMember::nextPathMemberIsParent, SPQRColReducedComponent::pathEndMembers, reducedMemberIsValid(), SCIP_NETCOLADD::reducedMembers, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, transformAndMerge(), and transformFirstPathMember().

Referenced by transformComponent().

◆ columnTransformSingleParallel()

static SCIP_RETCODE columnTransformSingleParallel	(	SCIP_NETCOLADD *	newCol,
		reduced_member_id	reducedMemberId,
		spqr_member	member,
		NewColInformation *	newColInfo
	)

static

Transform a single parallel member to add the new column.

Parameters

newCol	The network matrix column addition data structure
reducedMemberId	The reduced member to transform
member	The member to transform
newColInfo	The new column information

Definition at line 6409 of file network.c.

References SPQRColReducedMember::firstPathArc, SPQRColReducedMember::numPathArcs, pathArcIsValid(), SPQRColReducedMember::pathBackwards, SCIP_NETCOLADD::reducedMembers, SCIP_OKAY, setTerminalMember(), and setTerminalReversed().

Referenced by transformComponent().

◆ columnTransformSingleSeries()

static SCIP_RETCODE columnTransformSingleSeries	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		reduced_member_id	reducedMemberId,
		spqr_member	member,
		NewColInformation *	newColInfo
	)

static

Transform a single series member to add the new column.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
reducedMemberId	The reduced member to transform
member	The member to transform
newColInfo	The new column information

Definition at line 6427 of file network.c.

References SCIP_NETCOLADD::arcInPathReversed, getFirstMemberArc(), getNumMemberArcs(), NewColInformation::member, SCIP_NETCOLADD::reducedMembers, NewColInformation::reversed, SCIP_CALL, SCIP_OKAY, and splitSeries().

Referenced by transformComponent().

◆ columnTransformSingleRigid()

static SCIP_RETCODE columnTransformSingleRigid	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		reduced_member_id	reducedMemberId,
		spqr_member	member,
		NewColInformation *	newColInfo
	)

static

Transform a single rigid member to add the new column.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
reducedMemberId	The reduced member to transform
member	The member to transform
newColInfo	The new column information

Definition at line 6451 of file network.c.

References PathArcListNode::arc, arcGetElement(), arcIsChildMarker(), arcIsReversedNonRigid(), arcIsTree(), SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::childMember, createChildMarker(), createColumnArc(), createMember(), createParentMarker(), createRowArc(), SPQRNetworkDecompositionArc::element, FALSE, findArcChildMember(), findArcHead(), findArcSign(), findArcTail(), findMemberParent(), SPQRColReducedMember::firstPathArc, getFirstNodeArc(), getMemberType(), getNextNodeArc(), MARKER_COLUMN_ELEMENT, MARKER_ROW_ELEMENT, SPQRNetworkDecompositionMember::markerOfParent, markerOfParent(), SPQRNetworkDecompositionMember::markerToParent, markerToParent(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::parentMember, SCIP_NETCOLADD::pathArcs, reducedMemberIsValid(), SCIP_NETCOLADD::reducedMembers, ArcSign::representative, ArcSign::reversed, SPQRColReducedMember::rigidPathEnd, SPQRColReducedMember::rigidPathStart, SCIP_Bool, SCIP_CALL, SCIP_OKAY, setTerminalHead(), setTerminalMember(), setTerminalRepresentative(), setTerminalReversed(), setTerminalTail(), SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, SPQR_MEMBERTYPE_PARALLEL, SPQRarcIsValid(), SPQRelementIsColumn(), SPQRelementToColumn(), SPQRelementToRow(), SPQRmemberIsValid(), SPQRnodeIsValid(), and TRUE.

Referenced by transformComponent().

◆ transformComponent()

static SCIP_RETCODE transformComponent	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol,
		SPQRColReducedComponent *	component,
		NewColInformation *	newColInfo
	)

static

Transform a component to reflect the new column.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure
component	The component to transform
newColInfo	The new column information

Definition at line 6591 of file network.c.

References columnTransformSingleParallel(), columnTransformSingleRigid(), columnTransformSingleSeries(), getMemberType(), SPQRColReducedMember::member, SPQRColReducedMember::numChildren, SPQRColReducedMember::numPropagatedChildren, reducedMemberIsValid(), SCIP_NETCOLADD::reducedMembers, SPQRColReducedComponent::root, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPABORT, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_SERIES, SPQR_MEMBERTYPE_UNASSIGNED, and transformPath().

Referenced by netcoladdAdd().

◆ netcoladdRemainsNetwork()

static SCIP_Bool netcoladdRemainsNetwork ( const SCIP_NETCOLADD * newCol )

static

Check if the submatrix stored remains a network matrix with the new column update.

Parameters

newCol The network matrix column addition data structure

Definition at line 6647 of file network.c.

References SCIP_NETCOLADD::remainsNetwork.

Referenced by netcoladdAdd(), and SCIPnetmatdecTryAddCol().

◆ netcoladdAdd()

static SCIP_RETCODE netcoladdAdd	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETCOLADD *	newCol
	)

static

Add the new column to the network decomposition as an arc.

Only use this function after SCIPnetcoladdCheck() has been called.

Parameters

dec	The network matrix decomposition
newCol	The network matrix column addition data structure

Definition at line 6659 of file network.c.

References SCIP_NETCOLADD::arcInPath, SCIP_NETCOLADD::arcInPathReversed, arcIsReversedNonRigid(), arcSetRepresentative(), arcSetReversed(), changeLoopToParallel(), createColumnArc(), createConnectedSeries(), createMarkerPairWithReferences(), createStandaloneSeries(), decreaseNumConnectedComponents(), FALSE, findNode(), getFirstMemberArc(), getMemberType(), getNumMemberArcs(), NewColInformation::head, NewColInformation::member, memberIsRepresentative(), SCIP_NETMATDECDATA::members, moveArcToNewMember(), netcoladdRemainsNetwork(), SCIP_NETCOLADD::newColIndex, NEWCOLINFORMATION_EMPTY, SCIP_NETCOLADD::newRowArcReversed, SCIP_NETCOLADD::newRowArcs, numConnectedComponents(), SCIP_NETCOLADD::numNewRowArcs, SCIP_NETCOLADD::numReducedComponents, SCIP_NETCOLADD::reducedComponents, reorderComponent(), NewColInformation::representative, NewColInformation::reversed, SCIP_CALL, SCIP_OKAY, setArcHeadAndTail(), SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_UNASSIGNED, SPQRarcIsValid(), SPQRnodeIsValid(), NewColInformation::tail, transformComponent(), TRUE, and SPQRNetworkDecompositionMember::type.

Referenced by SCIPnetmatdecTryAddCol().

◆ cutArcIsInvalid()

static SCIP_Bool cutArcIsInvalid ( const cut_arc_id arc )

static

Checks if the given cut arc is invalid (negative).

Parameters

arc	The cut arc to check

Definition at line 6776 of file network.c.

Referenced by cutArcIsValid().

◆ cutArcIsValid()

static SCIP_Bool cutArcIsValid ( const cut_arc_id arc )

static

Checks if the given cut arc is valid (nonnegative).

Parameters

arc	The cut arc to check

Definition at line 6784 of file network.c.

References cutArcIsInvalid().

Referenced by cleanUpPreviousIteration(), determineParallelType(), determineSeriesType(), determineSingleParallelType(), determineSingleSeriesType(), determineSplitTypeFirstLeaf(), determineSplitTypeParallel(), determineSplitTypeSeries(), intersectionOfAllPaths(), rigidFindStarNodes(), splitAndMergeSeries(), splitFirstLeaf(), splitParallelMerging(), splitParallelRowAddition(), and transformSingleRigid().

◆ newRowUpdateRowInformation()

static SCIP_RETCODE newRowUpdateRowInformation	(	const SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const spqr_row	row,
		const spqr_col *	columns,
		const double *	columnValues,
		const int	numColumns
	)

static

Saves the information of the current row and partitions it based on whether or not the given columns are already part of the decomposition.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition datastructure
row	The row to check
columns	The column indices of the nonzeros in the row
columnValues	The matrix entries of the nonzeros in the row
numColumns	The number of nonzeros in the row

Definition at line 7022 of file network.c.

References BMSreallocBlockMemoryArray, SCIP_NETROWADD::decompositionColumnArcReversed, SCIP_NETROWADD::decompositionColumnArcs, SCIP_NETMATDECDATA::env, getDecompositionColumnArc(), SCIP_NETROWADD::memColumnArcs, SCIP_NETROWADD::memDecompositionColumnArcs, SCIP_NETROWADD::newColumnArcs, SCIP_NETROWADD::newColumnReversed, SCIP_NETROWADD::newRowIndex, SCIP_NETROWADD::numColumnArcs, SCIP_NETROWADD::numDecompositionColumnArcs, SCIP_ALLOC, SCIP_Bool, SCIP_OKAY, and SPQRarcIsValid().

Referenced by netrowaddCheck().

◆ createRowReducedMembersToRoot()

static reduced_member_id createRowReducedMembersToRoot	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const spqr_member	firstMember
	)

static

Adds members to the reduced member tree, by starting at the given member, jumping up to the parent, repeating this procedure until the root has been added.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition datastructure
firstMember	The member to create a reduced member for

Definition at line 7080 of file network.c.

Referenced by constructRowReducedDecomposition().

◆ constructRowReducedDecomposition()

static SCIP_RETCODE constructRowReducedDecomposition	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow
	)

static

Construct the reduced decomposition, which is the smallest subtree containing all members cut arcs.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition datastructure

Definition at line 7187 of file network.c.

References BMSreallocBlockMemoryArray, SCIP_NETROWADD::childrenStorage, SCIP_NETROWADD::createReducedMembersCallstack, createRowReducedMembersToRoot(), SCIP_NETROWADD::decompositionColumnArcs, SPQRRowReducedMember::depth, SCIP_NETMATDECDATA::env, findArcMember(), findMemberParent(), SPQRRowReducedMember::firstChild, getNumMembers(), INVALID_REDUCED_MEMBER, largestMemberID(), MAX, SPQRRowReducedMember::member, SCIP_NETROWADD::memberInformation, memberIsRepresentative(), SCIP_NETROWADD::memChildrenStorage, SCIP_NETROWADD::memCreateReducedMembersCallstack, SCIP_NETROWADD::memMemberInformation, SCIP_NETROWADD::memReducedComponents, SCIP_NETROWADD::memReducedMembers, SPQRRowReducedMember::numChildren, SCIP_NETROWADD::numChildrenStorage, numConnectedComponents(), SCIP_NETROWADD::numDecompositionColumnArcs, SCIP_NETROWADD::numReducedComponents, SCIP_NETROWADD::numReducedMembers, SPQRRowReducedMember::parent, SCIP_NETROWADD::reducedComponents, MemberInfo::reducedMember, reducedMemberIsInvalid(), reducedMemberIsValid(), SCIP_NETROWADD::reducedMembers, SPQRRowReducedComponent::root, SPQRRowReducedComponent::rootDepth, MemberInfo::rootDepthMinimizer, SPQRRowReducedMember::rootMember, SCIP_ALLOC, SCIP_OKAY, and SPQRmemberIsValid().

Referenced by netrowaddCheck().

◆ createCutArc()

static void createCutArc	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const spqr_arc	arc,
		const reduced_member_id	reducedMember,
		SCIP_Bool	reversed
	)

static

Marks an arc as 'cut'.

This implies that its cycle in the decomposition must be elongated.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition datastructure
arc	The arc to mark as a cut arc
reducedMember	The reduced member containing the arc
reversed	Indicates if the new row entry has +1 or -1 (TRUE) for the arc

Definition at line 7336 of file network.c.

References CutArcListNode::arc, CutArcListNode::arcHead, CutArcListNode::arcReversed, CutArcListNode::arcTail, SCIP_NETROWADD::cutArcs, findEffectiveArcHead(), findEffectiveArcTail(), SPQRRowReducedMember::firstCutArc, SCIP_NETROWADD::firstOverallCutArc, getMemberType(), SCIP_NETROWADD::isArcCut, SCIP_NETROWADD::isArcCutReversed, SPQRRowReducedMember::member, memberIsRepresentative(), SCIP_NETROWADD::memCutArcs, CutArcListNode::nextMember, CutArcListNode::nextOverall, SPQRRowReducedMember::numCutArcs, SCIP_NETROWADD::numCutArcs, SCIP_NETROWADD::reducedMembers, SCIPswapInts(), SPQR_INVALID_NODE, SPQR_MEMBERTYPE_RIGID, SPQRnodeIsValid(), and TRUE.

Referenced by createReducedDecompositionCutArcs(), determineParallelType(), determineRigidType(), and determineSeriesType().

◆ createReducedDecompositionCutArcs()

static SCIP_RETCODE createReducedDecompositionCutArcs	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow
	)

static

Creates all cut arcs within the decomposition for the new row.

Note this preallocates memory for cut arcs which may be created by propagation.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition datastructure

Definition at line 7388 of file network.c.

References BMSreallocBlockMemoryArray, createCutArc(), SCIP_NETROWADD::cutArcs, SCIP_NETROWADD::decompositionColumnArcReversed, SCIP_NETROWADD::decompositionColumnArcs, SCIP_NETMATDECDATA::env, FALSE, findArcMember(), SCIP_NETROWADD::firstOverallCutArc, INVALID_CUT_ARC, SCIP_NETROWADD::isArcCut, SCIP_NETROWADD::isArcCutReversed, largestArcID(), MAX, SCIP_NETROWADD::memberInformation, SCIP_NETROWADD::memCutArcs, SCIP_NETROWADD::memIsArcCut, SCIP_NETROWADD::numCutArcs, SCIP_NETROWADD::numDecompositionColumnArcs, MemberInfo::reducedMember, reducedMemberIsValid(), SCIP_ALLOC, and SCIP_OKAY.

Referenced by netrowaddCheck().

◆ determineLeafReducedMembers()

static SCIP_RETCODE determineLeafReducedMembers	(	const SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow
	)

static

Determines the members of the reduced decomposition which are leafs.

This is used in propagation to ensure propagation is only checked for components which have at most one neighbour that is not propagated.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition datastructure

Definition at line 7442 of file network.c.

References BMSreallocBlockMemoryArray, SCIP_NETMATDECDATA::env, SCIP_NETROWADD::leafMembers, MAX, SCIP_NETROWADD::memLeafMembers, SPQRRowReducedMember::numChildren, SCIP_NETROWADD::numDecompositionColumnArcs, SCIP_NETROWADD::numLeafMembers, SCIP_NETROWADD::numReducedMembers, SCIP_NETROWADD::reducedMembers, SCIP_ALLOC, and SCIP_OKAY.

Referenced by netrowaddCheck().

◆ allocateRigidSearchMemory()

static SCIP_RETCODE allocateRigidSearchMemory	(	const SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow
	)

static

Preallocates memory arrays necessary for searching rigid components.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition datastructure

Definition at line 7469 of file network.c.

Referenced by netrowaddCheck().

◆ zeroOutColors()

static void zeroOutColors	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const spqr_node	firstRemoveNode
	)

static

Clears the colors for all nodes.

We do DFS in reverse (reverse exploration order), as zeroing out the entire array is more expensive.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition datastructure
firstRemoveNode	The first node that was colored in the original DFS

Definition at line 7578 of file network.c.

References ColorDFSCallData::arc, SCIP_NETROWADD::colorDFSData, findArcHead(), findArcTail(), getFirstNodeArc(), getNextNodeArc(), ColorDFSCallData::node, SCIP_NETROWADD::nodeColors, NULL, SPQRarcIsInvalid(), and UNCOLORED.

Referenced by cleanUpPreviousIteration(), rigidConnectedColoring(), and zeroOutColorsExceptNeighbourhood().

◆ cleanUpPreviousIteration()

static void cleanUpPreviousIteration	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow
	)

static

Cleans up various arrays used in previous iterations.

This is cheaper than reallocating empty memory.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition datastructure

Definition at line 7634 of file network.c.

References CutArcListNode::arc, SPQRRowReducedMember::coloredNode, cutArcIsValid(), SCIP_NETROWADD::cutArcs, FALSE, SCIP_NETROWADD::firstOverallCutArc, SCIP_NETROWADD::isArcCut, SCIP_NETROWADD::isArcCutReversed, SCIP_NETROWADD::memIsArcCut, SCIP_NETROWADD::memNodeColors, CutArcListNode::nextOverall, SCIP_NETROWADD::nodeColors, SCIP_NETROWADD::numReducedMembers, SCIP_NETROWADD::reducedMembers, SPQRnodeIsValid(), UNCOLORED, and zeroOutColors().

Referenced by netrowaddCheck().

◆ rigidFindStarNodes()

static void rigidFindStarNodes	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const reduced_member_id	toCheck
	)

static

Finds all the star nodes, i.e. nodes that are adjacent to all cut arcs, in a rigid member.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
toCheck	The reduced member to check

Definition at line 7675 of file network.c.

Referenced by determineRigidType(), determineSingleRowRigidType(), determineSplitTypeFirstLeaf(), and determineSplitTypeRigid().

◆ zeroOutColorsExceptNeighbourhood()

static void zeroOutColorsExceptNeighbourhood	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const spqr_node	articulationNode,
		const spqr_node	startRemoveNode
	)

static

Clears the colors for all nodes, but the neighbours.

We do DFS in reverse (reverse exploration order), as zeroing out the entire array is more expensive.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
articulationNode	The node whose neighbours we want to keep
startRemoveNode	The node where DFS started

Definition at line 7780 of file network.c.

References findArcHead(), findArcTail(), getFirstNodeArc(), getNextNodeArc(), SCIP_NETROWADD::memTemporaryColorArray, SCIP_NETROWADD::nodeColors, nodeDegree(), SCIP_NETROWADD::temporaryColorArray, and zeroOutColors().

Referenced by rigidConnectedColoring().

◆ intersectionOfAllPaths()

static void intersectionOfAllPaths	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const reduced_member_id	toCheck,
		int *const	nodeNumPaths
	)

static

Find the intersection of all cut arc paths in the given rigid member.

Theoretically, there is a faster algorithm using lowest common ancestor queries, but it is quite complicated. Thus, we stick with the 'simple' version below, which is typically also faster in practice.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
toCheck	The rigid member to check
nodeNumPaths	Tracks for each node, how many cut arc paths cross it

Definition at line 7831 of file network.c.

References CutArcListNode::arc, arcIsTree(), cutArcIsValid(), SCIP_NETROWADD::cutArcs, findArcHead(), findArcHeadNoCompression(), findArcTail(), findArcTailNoCompression(), SPQRRowReducedMember::firstCutArc, getFirstNodeArc(), getNextNodeArc(), SCIP_NETROWADD::intersectionDFSData, SCIP_NETROWADD::intersectionPathDepth, SCIP_NETROWADD::intersectionPathParent, CutArcListNode::nextMember, DFSCallData::node, DFSCallData::nodeArc, SCIP_NETROWADD::reducedMembers, SPQR_INVALID_NODE, and SPQRnodeIsValid().

Referenced by rigidGetSplittableArticulationPointsOnPath().

◆ addArticulationNode()

static void addArticulationNode	(	SCIP_NETROWADD *	newRow,
		spqr_node	articulationNode
	)

static

Add a node to array of articulation nodes.

Parameters

newRow	The network matrix row addition data structure
articulationNode	The node to add

Definition at line 7949 of file network.c.

References SCIP_NETROWADD::articulationNodes, and SCIP_NETROWADD::numArticulationNodes.

Referenced by articulationPoints().

◆ articulationPoints()

static void articulationPoints	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		ArticulationNodeInformation *	nodeInfo,
		reduced_member_id	reducedMember
	)

static

Find all the articulation points of the rigid member graph where the cut arcs are removed.

Articulation points are nodes whose removal disconnects the remaining graph.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
nodeInfo	Stores information about the found articulation nodes
reducedMember	The reduced member to find the articulation nodes for

Definition at line 7969 of file network.c.

References addArticulationNode(), ArticulationPointCallStack::arc, SCIP_NETROWADD::artDFSData, ArticulationNodeInformation::discoveryTime, FALSE, findArcHead(), findArcTail(), getFirstMemberArc(), getFirstNodeArc(), getNextNodeArc(), ArticulationPointCallStack::isAP, SCIP_NETROWADD::isArcCut, ArticulationNodeInformation::low, SPQRRowReducedMember::member, MIN, ArticulationPointCallStack::node, ArticulationPointCallStack::parent, SCIP_NETROWADD::reducedMembers, SCIP_Bool, SPQR_INVALID_NODE, and TRUE.

Referenced by rigidGetSplittableArticulationPointsOnPath().

◆ rigidConnectedColoringRecursive()

static void rigidConnectedColoringRecursive	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		spqr_node	articulationNode,
		spqr_node	firstProcessNode,
		COLOR_STATUS	firstColor,
		SCIP_Bool *	isGood
	)

static

For a given articulation node, partitions the rigid member's graph where it is removed into a SOURCE and SINK partition.

All cut arcs must point (after reversal) from the source partition to the sink partition. This is akin to finding a 2-coloring, and uses a DFS to do so. This function specifically executes the DFS/recursive part.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
articulationNode	The articulation node to obtain the coloring for
firstProcessNode	The first node to process for the DFS
firstColor	The partition that the first node lies in.
isGood	Returns whether the coloring was consistent

Definition at line 8062 of file network.c.

References ColorDFSCallData::arc, COLOR_SINK, COLOR_SOURCE, SCIP_NETROWADD::colorDFSData, FALSE, findArcHead(), findArcSign(), findArcTail(), getFirstNodeArc(), getNextNodeArc(), SCIP_NETROWADD::isArcCut, SCIP_NETROWADD::isArcCutReversed, ColorDFSCallData::node, SCIP_NETROWADD::nodeColors, ArcSign::reversed, SCIP_Bool, and UNCOLORED.

Referenced by rigidConnectedColoring().

◆ rigidConnectedColoring()

static void rigidConnectedColoring	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const reduced_member_id	reducedMember,
		const spqr_node	node,
		SCIP_Bool *const	isGood
	)

static

For a given articulation node, partitions the rigid member's graph where it is removed into a SOURCE and SINK partition.

All cut arcs must point (after reversal) from the source partition to the sink partition. This is akin to finding a 2-coloring, and uses a DFS to do so.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
reducedMember	The rigid member whose graph to color
node	The articulation node to obtain the coloring for
isGood	Returns whether the coloring was consistent

Definition at line 8144 of file network.c.

References CutArcListNode::arc, CutArcListNode::arcReversed, COLOR_SINK, COLOR_SOURCE, SPQRRowReducedMember::coloredNode, SCIP_NETROWADD::cutArcs, findArcHead(), findArcHeadNoCompression(), findArcSign(), findArcTail(), findArcTailNoCompression(), SPQRRowReducedMember::firstCutArc, getFirstMemberArc(), getNextMemberArc(), SPQRRowReducedMember::member, SCIP_NETROWADD::nodeColors, SPQRRowReducedMember::numCutArcs, SCIP_NETROWADD::reducedMembers, rigidConnectedColoringRecursive(), SPQR_INVALID_NODE, SPQRarcIsValid(), SPQRnodeIsValid(), TRUE, UNCOLORED, zeroOutColors(), and zeroOutColorsExceptNeighbourhood().

Referenced by rigidGetSplittableArticulationPointsOnPath().

◆ checkNeighbourColoringArticulationNode()

static spqr_node checkNeighbourColoringArticulationNode	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const spqr_node	articulationNode,
		spqr_arc *const	adjacentSplittingArc
	)

static

Given a coloring for an articulation node, we can prove that a neighbouring node is splittable if and only if it is the unique node in the neighbourhood of the articulation node within the SOURCE or SINK partition. In this function, we check for a splittable articulation node if such an adjacent node exists, and return it if possible.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
articulationNode	The articulation whose neighbours are to be checked
adjacentSplittingArc	The arc connecting the two splittable nodes.

Definition at line 8219 of file network.c.

References arcIsTree(), COLOR_SOURCE, findArcHead(), findArcTail(), getFirstNodeArc(), getNextNodeArc(), SCIP_NETROWADD::isArcCut, SCIP_NETROWADD::nodeColors, SPQR_INVALID_ARC, SPQR_INVALID_NODE, and UNCOLORED.

Referenced by rigidGetSplittableArticulationPointsOnPath().

◆ rigidGetSplittableArticulationPointsOnPath()

static void rigidGetSplittableArticulationPointsOnPath	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const reduced_member_id	toCheck,
		spqr_node	firstNode,
		spqr_node	secondNode
	)

static

Find all the splittable articulation points that lie on the intersection of all cut arc cycles.

firstNode and secondNode can be set to limit the nodes that this function checks to the given nodes.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
toCheck	The rigid member to check
firstNode	Optional: the first given node that should be checked
secondNode	Optional: the second given node that should be checked

Definition at line 8289 of file network.c.

References SPQRRowReducedMember::articulationArc, SCIP_NETROWADD::articulationNodes, SCIP_NETROWADD::articulationNodeSearchInfo, articulationPoints(), checkNeighbourColoringArticulationNode(), COLOR_SOURCE, SCIP_NETROWADD::crossingPathCount, ArticulationNodeInformation::discoveryTime, FALSE, findArcHead(), findArcTail(), getFirstNodeArc(), getNextNodeArc(), getNumNodes(), intersectionOfAllPaths(), ArticulationNodeInformation::low, SCIP_NETROWADD::nodeColors, nodeIsRepresentative(), SCIP_NETROWADD::numArticulationNodes, SPQRRowReducedMember::numCutArcs, SPQRRowReducedMember::otherIsSource, SPQRRowReducedMember::otherNode, SCIP_NETROWADD::reducedMembers, SCIP_NETROWADD::remainsNetwork, rigidConnectedColoring(), SCIP_Bool, SPQRRowReducedMember::splitNode, SPQR_INVALID_ARC, SPQRnodeIsInvalid(), SPQRnodeIsValid(), TRUE, SPQRRowReducedMember::type, TYPE_NOT_NETWORK, and UNCOLORED.

Referenced by determineRigidType(), determineSingleRowRigidType(), determineSplitTypeFirstLeaf(), and determineSplitTypeRigid().

◆ determineParallelType()

static void determineParallelType	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const reduced_member_id	toCheckMember,
		const spqr_arc	markerToOther,
		const reduced_member_id	otherMember,
		const spqr_arc	markerToCheck
	)

static

Checks if a leaf parallel member can be propagated away from the reduced decomposition.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
toCheckMember	The parallel leaf member to check
markerToOther	Marker to the non-leaf member
otherMember	The connected non-leaf member
markerToCheck	Marker from the non-leaf to the leaf parallel member

Definition at line 8394 of file network.c.

References CutArcListNode::arc, arcIsReversedNonRigid(), arcIsTree(), CutArcListNode::arcReversed, createCutArc(), cutArcIsValid(), SCIP_NETROWADD::cutArcs, FALSE, SPQRRowReducedMember::firstCutArc, getNumMemberArcs(), SPQRRowReducedMember::member, CutArcListNode::nextMember, SCIP_NETROWADD::reducedMembers, SCIP_NETROWADD::remainsNetwork, SCIP_Bool, TRUE, SPQRRowReducedMember::type, TYPE_MERGED, TYPE_NOT_NETWORK, and TYPE_PROPAGATED.

Referenced by determineType().

◆ determineSeriesType()

static void determineSeriesType	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const reduced_member_id	toCheckMember,
		const spqr_arc	markerToOther,
		const reduced_member_id	otherMember,
		const spqr_arc	markerToCheck
	)

static

Checks if a leaf series member can be propagated away from the reduced decomposition.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
toCheckMember	The series leaf member to check
markerToOther	Marker to the non-leaf member
otherMember	The connected non-leaf member
markerToCheck	Marker from the non-leaf to the leaf series member

Definition at line 8448 of file network.c.

References CutArcListNode::arc, arcIsReversedNonRigid(), arcIsTree(), CutArcListNode::arcReversed, createCutArc(), cutArcIsValid(), SCIP_NETROWADD::cutArcs, SPQRRowReducedMember::firstCutArc, SPQRRowReducedMember::numCutArcs, SCIP_NETROWADD::reducedMembers, SPQRRowReducedMember::type, and TYPE_PROPAGATED.

Referenced by determineType().

◆ determineRigidType()

static void determineRigidType	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const reduced_member_id	toCheckMember,
		const spqr_arc	markerToOther,
		const reduced_member_id	otherMember,
		const spqr_arc	markerToCheck
	)

static

Checks if a leaf rigid member can be propagated away from the reduced decomposition.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
toCheckMember	The rigid leaf member to check
markerToOther	Marker to the non-leaf member
otherMember	The connected non-leaf member
markerToCheck	Marker from the non-leaf to the rigid leaf member

Definition at line 8471 of file network.c.

References SPQRRowReducedMember::articulationArc, createCutArc(), FALSE, findArcHead(), findArcSign(), findArcTail(), SPQRRowReducedMember::numCutArcs, SPQRRowReducedMember::otherIsSource, SPQRRowReducedMember::otherNode, SCIP_NETROWADD::reducedMembers, SCIP_NETROWADD::remainsNetwork, rigidFindStarNodes(), rigidGetSplittableArticulationPointsOnPath(), SCIP_Bool, SPQRRowReducedMember::splitNode, SPQRarcIsValid(), SPQRnodeIsInvalid(), SPQRRowReducedMember::type, TYPE_MERGED, TYPE_NOT_NETWORK, and TYPE_PROPAGATED.

Referenced by determineType().

◆ determineType()

static RowReducedMemberType determineType	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const reduced_member_id	toCheckMember,
		const spqr_arc	markerToOther,
		const reduced_member_id	otherMember,
		const spqr_arc	markerToCheck
	)

static

Checks if a leaf member can be propagated away from the reduced decomposition.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
toCheckMember	The leaf member to check
markerToOther	Marker to the non-leaf member
otherMember	The connected non-leaf member
markerToCheck	Marker from the non-leaf to the leaf member

Definition at line 8537 of file network.c.

References determineParallelType(), determineRigidType(), determineSeriesType(), getMemberType(), SPQRRowReducedMember::member, SCIP_NETROWADD::reducedMembers, SCIPABORT, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_SERIES, SPQR_MEMBERTYPE_UNASSIGNED, SPQRRowReducedMember::type, TYPE_NOT_NETWORK, and TYPE_UNDETERMINED.

Referenced by propagateComponents().

◆ propagateComponents()

static void propagateComponents	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow
	)

static

Propagates away all leaf members that are propagatable to shrink the reduced decomposition.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure

Definition at line 8576 of file network.c.

References arcIsTree(), SCIP_NETROWADD::childrenStorage, determineType(), SPQRRowReducedMember::firstChild, INVALID_REDUCED_MEMBER, SCIP_NETROWADD::leafMembers, markerOfParent(), markerToParent(), SPQRRowReducedMember::member, SPQRRowReducedMember::numChildren, SCIP_NETROWADD::numLeafMembers, SPQRRowReducedMember::numPropagatedChildren, SCIP_NETROWADD::numReducedComponents, SPQRRowReducedMember::parent, SCIP_NETROWADD::reducedComponents, reducedMemberIsValid(), SCIP_NETROWADD::reducedMembers, SPQRRowReducedComponent::root, SPQR_INVALID_ARC, SPQRarcIsValid(), SPQRmemberIsValid(), TRUE, SPQRRowReducedMember::type, TYPE_MERGED, TYPE_NOT_NETWORK, and TYPE_PROPAGATED.

Referenced by netrowaddCheck().

◆ rigidDetermineCandidateNodesFromAdjacentComponents()

static Nodes rigidDetermineCandidateNodesFromAdjacentComponents	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const reduced_member_id	toCheck
	)

static

Computes the intersection nodes of all markers that point to reduced tree members.

These are the only nodes that may become Y-splittable, after propagation.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
toCheck	The rigid member to check

Definition at line 8692 of file network.c.

References SCIP_NETROWADD::childrenStorage, findArcHead(), findArcTail(), Nodes::first, SPQRRowReducedMember::firstChild, markerOfParent(), markerToParent(), SPQRRowReducedMember::member, SPQRRowReducedMember::numChildren, SPQRRowReducedMember::parent, reducedMemberIsValid(), SCIP_NETROWADD::reducedMembers, Nodes::second, SPQR_INVALID_NODE, SPQRnodeIsInvalid(), SPQRRowReducedMember::type, and TYPE_PROPAGATED.

Referenced by determineSplitTypeRigid().

◆ allocateTreeSearchMemory()

static SCIP_RETCODE allocateTreeSearchMemory	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow
	)

static

Allocates memory for various procedures that need to do tree-search for rigid members (e.g. DFS or BFS).

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure

Definition at line 8762 of file network.c.

References BMSreallocBlockMemoryArray, SCIP_NETMATDECDATA::env, MAX, SCIP_NETROWADD::memMergeTreeCallData, SCIP_NETROWADD::mergeTreeCallData, SCIP_NETROWADD::numReducedMembers, SCIP_ALLOC, and SCIP_OKAY.

Referenced by netrowaddCheck().

◆ determineSingleRowRigidType()

static void determineSingleRowRigidType	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	reducedMember
	)

static

Determine the type of a rigid member when it is the only member in the reduced decomposition.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
reducedMember	The rigid member to determine the type for

Definition at line 8780 of file network.c.

References FALSE, SPQRRowReducedMember::numCutArcs, SCIP_NETROWADD::reducedMembers, SCIP_NETROWADD::remainsNetwork, rigidFindStarNodes(), rigidGetSplittableArticulationPointsOnPath(), SPQRRowReducedMember::splitNode, SPQR_INVALID_NODE, SPQRnodeIsInvalid(), SPQRnodeIsValid(), SPQRRowReducedMember::type, TYPE_MERGED, and TYPE_NOT_NETWORK.

Referenced by determineMergeableTypes().

◆ determineSingleParallelType()

static void determineSingleParallelType	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	reducedMember
	)

static

Determine the type of a parallel member when it is the only member in the reduced decomposition.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
reducedMember	The parallel member to determine the type for

Definition at line 8813 of file network.c.

References CutArcListNode::arc, arcIsReversedNonRigid(), CutArcListNode::arcReversed, cutArcIsValid(), SCIP_NETROWADD::cutArcs, FALSE, SPQRRowReducedMember::firstCutArc, CutArcListNode::nextMember, SCIP_NETROWADD::reducedMembers, SCIP_NETROWADD::remainsNetwork, SCIP_Bool, TRUE, SPQRRowReducedMember::type, TYPE_MERGED, and TYPE_NOT_NETWORK.

Referenced by determineMergeableTypes().

◆ determineSingleSeriesType()

static void determineSingleSeriesType	(	SCIP_NETROWADD *	newRow,
		reduced_member_id	reducedMember
	)

static

Determine the type of a series member when it is the only member in the reduced decomposition.

Parameters

newRow	The network matrix row addition data structure
reducedMember	The series member to determine the type for

Definition at line 8854 of file network.c.

References cutArcIsValid(), SPQRRowReducedMember::firstCutArc, SPQRRowReducedMember::numCutArcs, SCIP_NETROWADD::reducedMembers, SPQRRowReducedMember::type, and TYPE_MERGED.

Referenced by determineMergeableTypes().

◆ determineAndColorSplitNode()

static spqr_node determineAndColorSplitNode	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	id,
		spqr_node	candidateOne,
		spqr_node	candidateTwo
	)

static

Sets the given split nodes; performs bookkeeping so that we have an easier time updating the graph in many edge cases.

Algorithmically speaking, does nothing important.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
id	The reduced member that we compute the split node for
candidateOne	The first candidate node
candidateTwo	The second candidate node

Definition at line 8870 of file network.c.

References SPQRRowReducedMember::allHaveCommonNode, SPQRRowReducedMember::articulationArc, COLOR_SINK, COLOR_SOURCE, SPQRRowReducedMember::coloredNode, findArcHead(), findArcTail(), getFirstNodeArc(), getNextNodeArc(), SCIP_NETROWADD::nodeColors, SPQRRowReducedMember::numCutArcs, SPQRRowReducedMember::otherIsSource, SPQRRowReducedMember::otherNode, SCIP_NETROWADD::reducedMembers, SPQRRowReducedMember::splitNode, SPQR_INVALID_NODE, SPQRarcIsValid(), SPQRnodeIsInvalid(), and UNCOLORED.

Referenced by determineSplitTypeFirstLeaf(), and determineSplitTypeRigid().

◆ determineSplitTypeFirstLeaf()

static void determineSplitTypeFirstLeaf	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	reducedId
	)

static

After propagation, determines the split type of the first leaf node of the reduced decomposition.

The leaf nodes of the decomposition after propagation can only be of type P or R.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
reducedId	The member to determine the split type for

Definition at line 8958 of file network.c.

Referenced by determineMergeableTypes().

◆ getRelativeOrientationRigid()

static SplitOrientation getRelativeOrientationRigid	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	reducedId,
		spqr_arc	arcToNext
	)

static

Get the split orientation for a given rigid member and marked arc.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
reducedId	The member to determine the split orientation for
arcToNext	The marked arc to determine the orientation for

Definition at line 9082 of file network.c.

References COLOR_SINK, COLOR_SOURCE, findArcHead(), findArcMemberNoCompression(), findArcSign(), findArcTail(), findEffectiveArcHead(), findEffectiveArcTailNoCompression(), SplitOrientation::headSplit, SPQRRowReducedMember::member, SCIP_NETROWADD::nodeColors, SPQRRowReducedMember::numCutArcs, SPQRRowReducedMember::otherIsSource, SplitOrientation::otherIsSource, SCIP_NETROWADD::reducedMembers, SPQRRowReducedMember::splitNode, SPQRnodeIsValid(), and SPQRRowReducedMember::willBeReversed.

Referenced by getRelativeOrientation().

◆ getRelativeOrientationParallel()

static SplitOrientation getRelativeOrientationParallel	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	reducedId,
		spqr_arc	arcToNext
	)

static

Get the split orientation for a given parallel member and marked arc.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
reducedId	The member to determine the split orientation for
arcToNext	The marked arc to determine the orientaiton for

Definition at line 9133 of file network.c.

References arcIsReversedNonRigid(), findArcMemberNoCompression(), SplitOrientation::headSplit, SPQRRowReducedMember::member, SPQRRowReducedMember::otherIsSource, SplitOrientation::otherIsSource, SCIP_NETROWADD::reducedMembers, SPQRRowReducedMember::splitArc, SPQRRowReducedMember::splitHead, and SPQRarcIsValid().

Referenced by getRelativeOrientation().

◆ getRelativeOrientationSeries()

static SplitOrientation getRelativeOrientationSeries	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	reducedId,
		spqr_arc	arcToNext
	)

static

Get the split orientation for a given series member and marked arc.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
reducedId	The member to determine the split orientation for
arcToNext	The marked arc to determine the orientaiton for

Definition at line 9158 of file network.c.

References arcIsReversedNonRigid(), findArcMemberNoCompression(), SplitOrientation::headSplit, SPQRRowReducedMember::member, SPQRRowReducedMember::otherIsSource, SplitOrientation::otherIsSource, SCIP_NETROWADD::reducedMembers, SPQRRowReducedMember::splitArc, SPQRRowReducedMember::splitHead, and SPQRarcIsValid().

Referenced by getRelativeOrientation().

◆ getRelativeOrientation()

static SplitOrientation getRelativeOrientation	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	reducedId,
		spqr_arc	arcToNext
	)

static

Get the split orientation for a given member and marked arc.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
reducedId	The member to determine the split orientation for
arcToNext	The marked arc to determine the orientaiton for

Definition at line 9183 of file network.c.

References FALSE, getMemberType(), getRelativeOrientationParallel(), getRelativeOrientationRigid(), getRelativeOrientationSeries(), SplitOrientation::headSplit, SPQRRowReducedMember::member, SplitOrientation::otherIsSource, SCIP_NETROWADD::reducedMembers, SCIPABORT, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_SERIES, and SPQR_MEMBERTYPE_UNASSIGNED.

Referenced by determineSplitTypeNext().

◆ determineSplitTypeSeries()

static void determineSplitTypeSeries	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	reducedId,
		spqr_arc	marker,
		SplitOrientation	previousOrientation
	)

static

Determine the split type of a series node when the SPQR tree is not a singular member.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
reducedId	The member to determine the split orientation for
marker	The marker to the previous member whose type was already determined
previousOrientation	The orientation to the previous member

Definition at line 9213 of file network.c.

Referenced by determineSplitTypeNext().

◆ determineSplitTypeParallel()

static void determineSplitTypeParallel	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	reducedId,
		spqr_arc	marker,
		SplitOrientation	previousOrientation
	)

static

Determine the split type of a parallel node when the SPQR tree is not a singular member.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
reducedId	The member to determine the split orientation for
marker	The marker to the previous member whose type was already determined
previousOrientation	The orientation to the previous member

Definition at line 9263 of file network.c.

References CutArcListNode::arc, arcIsReversedNonRigid(), CutArcListNode::arcReversed, cutArcIsValid(), SCIP_NETROWADD::cutArcs, FALSE, SPQRRowReducedMember::firstCutArc, SplitOrientation::headSplit, CutArcListNode::nextMember, SPQRRowReducedMember::otherIsSource, SplitOrientation::otherIsSource, SCIP_NETROWADD::reducedMembers, SCIP_NETROWADD::remainsNetwork, SCIP_Bool, SPQRRowReducedMember::splitArc, SPQRRowReducedMember::splitHead, TRUE, SPQRRowReducedMember::type, TYPE_MERGED, and TYPE_NOT_NETWORK.

Referenced by determineSplitTypeNext().

◆ determineSplitTypeRigid()

static void determineSplitTypeRigid	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	reducedId,
		spqr_member	member,
		spqr_arc	marker,
		SplitOrientation	previousOrientation
	)

static

Determine the split type of a rigid node when the SPQR tree is not a singular member.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
reducedId	The reduced member to determine the split orientation for
member	The member belonging to the reduced member
marker	The marker to the previous member whose type was already determined
previousOrientation	The orientation to the previous member

Definition at line 9322 of file network.c.

References COLOR_SINK, COLOR_SOURCE, determineAndColorSplitNode(), FALSE, findArcHead(), findArcSign(), findArcTail(), Nodes::first, getMemberType(), SplitOrientation::headSplit, SCIP_NETROWADD::nodeColors, SPQRRowReducedMember::numCutArcs, SPQRRowReducedMember::otherIsSource, SplitOrientation::otherIsSource, SCIP_NETROWADD::reducedMembers, SCIP_NETROWADD::remainsNetwork, rigidDetermineCandidateNodesFromAdjacentComponents(), rigidFindStarNodes(), rigidGetSplittableArticulationPointsOnPath(), SCIP_Bool, Nodes::second, SPQRRowReducedMember::splitNode, SPQR_INVALID_NODE, SPQR_MEMBERTYPE_RIGID, SPQRnodeIsInvalid(), SPQRnodeIsValid(), SPQRRowReducedMember::type, TYPE_MERGED, TYPE_NOT_NETWORK, and SPQRRowReducedMember::willBeReversed.

Referenced by determineSplitTypeNext().

◆ determineSplitTypeNext()

static void determineSplitTypeNext	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	current,
		reduced_member_id	next,
		SCIP_Bool	currentIsParent
	)

static

Determine the split type of a node when the SPQR tree is not a singular member.

This function is used for all the nodes that are not first in the given ordering.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
current	The current node, whose type has already been determined
next	The next node to determine the type of, adjacent to the current node
currentIsParent	Is the current node a parent of the next node?

Definition at line 9438 of file network.c.

References determineSplitTypeParallel(), determineSplitTypeRigid(), determineSplitTypeSeries(), FALSE, getMemberType(), getRelativeOrientation(), markerOfParent(), markerToParent(), SPQRRowReducedMember::member, SCIP_NETROWADD::reducedMembers, SCIP_NETROWADD::remainsNetwork, SCIPABORT, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_SERIES, and SPQR_MEMBERTYPE_UNASSIGNED.

Referenced by determineMergeableTypes().

◆ determineMergeableTypes()

static void determineMergeableTypes	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	root
	)

static

For the given root reduced member of a component, determine if the component is updateable/transformable.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
root	The root of the given component

Definition at line 9482 of file network.c.

References SCIP_NETROWADD::childrenStorage, MergeTreeCallData::currentChild, determineSingleParallelType(), determineSingleRowRigidType(), determineSingleSeriesType(), determineSplitTypeFirstLeaf(), determineSplitTypeNext(), FALSE, SPQRRowReducedMember::firstChild, getMemberType(), MergeTreeCallData::id, SPQRRowReducedMember::member, SCIP_NETROWADD::memMergeTreeCallData, SCIP_NETROWADD::mergeTreeCallData, SPQRRowReducedMember::numChildren, SPQRRowReducedMember::numPropagatedChildren, SCIP_NETROWADD::numReducedMembers, SPQRRowReducedMember::parent, reducedMemberIsValid(), SCIP_NETROWADD::reducedMembers, SCIP_NETROWADD::remainsNetwork, SCIPABORT, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_SERIES, SPQR_MEMBERTYPE_UNASSIGNED, TRUE, SPQRRowReducedMember::type, TYPE_PROPAGATED, and TYPE_UNDETERMINED.

Referenced by netrowaddCheck().

◆ cleanUpRowMemberInformation()

static void cleanUpRowMemberInformation ( SCIP_NETROWADD * newRow )

static

Empty the new member information array.

Parameters

newRow The network matrix row addition data structure

Definition at line 9591 of file network.c.

References INVALID_REDUCED_MEMBER, SPQRRowReducedMember::member, SCIP_NETROWADD::memberInformation, SCIP_NETROWADD::memMemberInformation, SCIP_NETROWADD::numReducedMembers, MemberInfo::reducedMember, reducedMemberIsInvalid(), and SCIP_NETROWADD::reducedMembers.

Referenced by netrowaddCheck().

◆ rigidTransformArcIntoCycle()

static SCIP_RETCODE rigidTransformArcIntoCycle	(	SCIP_NETMATDECDATA *	dec,
		const spqr_member	member,
		const spqr_arc	arc,
		const SCIP_Bool	reverseArcDirection,
		NewRowInformation *const	newRowInfo
	)

static

Transforms a rigid arc by putting it in series with the new column arc.

We need to do some magic to keep our the internal datastructures consistent in this case.

Parameters

dec	The network matrix decomposition
member	The rigid member that contains the arc that is moved
arc	The arc that is moved to a new series member
reverseArcDirection	Is the given arc reversed?
newRowInfo	Stores information on how to add the new row

Definition at line 9614 of file network.c.

References arcGetElement(), arcIsChildMarker(), arcIsReversedNonRigid(), arcIsTree(), SCIP_NETMATDECDATA::arcs, SPQRNetworkDecompositionArc::childMember, createChildMarker(), createColumnArc(), createMember(), createParentMarker(), createRowArc(), SPQRNetworkDecompositionArc::element, FALSE, findArcChildMember(), findMemberParent(), getMemberType(), MARKER_COLUMN_ELEMENT, MARKER_ROW_ELEMENT, SPQRNetworkDecompositionMember::markerOfParent, markerOfParent(), SPQRNetworkDecompositionMember::markerToParent, markerToParent(), NewRowInformation::member, SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::parentMember, NewRowInformation::reversed, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, SPQR_MEMBERTYPE_SERIES, SPQRelementIsColumn(), SPQRelementToColumn(), SPQRelementToRow(), and TRUE.

Referenced by transformSingleRigid().

◆ transformSingleRigid()

static SCIP_RETCODE transformSingleRigid	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const reduced_member_id	reducedMember,
		const spqr_member	member,
		NewRowInformation *const	newRowInfo
	)

static

Updates a single rigid member to reflect the new row.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
reducedMember	The reduced member to transform
member	The member belonging to the reduced member
newRowInfo	Stores information about the new row placement

Definition at line 9728 of file network.c.

References SPQRRowReducedMember::allHaveCommonNode, CutArcListNode::arc, SPQRRowReducedMember::articulationArc, changeArcHead(), changeArcTail(), COLOR_SOURCE, SPQRRowReducedMember::coloredNode, createNode(), cutArcIsValid(), SCIP_NETROWADD::cutArcs, FALSE, findArcHead(), findArcSign(), findArcTail(), findEffectiveArcHead(), findEffectiveArcHeadNoCompression(), findEffectiveArcTailNoCompression(), SPQRRowReducedMember::firstCutArc, getFirstNodeArc(), getNextNodeArc(), NewRowInformation::head, SCIP_NETROWADD::isArcCut, NewRowInformation::member, CutArcListNode::nextMember, SCIP_NETROWADD::nodeColors, SPQRRowReducedMember::otherIsSource, SCIP_NETROWADD::reducedMembers, ArcSign::representative, NewRowInformation::representative, NewRowInformation::reversed, rigidTransformArcIntoCycle(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SPQRRowReducedMember::splitNode, SPQR_INVALID_NODE, SPQRarcIsValid(), SPQRnodeIsValid(), NewRowInformation::tail, TRUE, and UNCOLORED.

Referenced by transformComponentRowAddition().

◆ splitParallelRowAddition()

static SCIP_RETCODE splitParallelRowAddition	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const reduced_member_id	reducedMember,
		const spqr_member	member,
		NewRowInformation *const	newRowInfo
	)

static

Splits a single parallel member into two adjacent ones, where the cut arcs and non-cut arcs get their own member.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
reducedMember	The reduced member to transform
member	The member belonging to the reduced member
newRowInfo	Stores information about the new row placement

Definition at line 9864 of file network.c.

References CutArcListNode::arc, arcIsChildMarker(), arcIsReversedNonRigid(), arcIsTree(), CutArcListNode::arcReversed, changeLoopToSeries(), createMarkerPair(), createMember(), cutArcIsValid(), SCIP_NETROWADD::cutArcs, FALSE, findArcChildMember(), findMemberParent(), SPQRRowReducedMember::firstCutArc, getFirstMemberArc(), getMemberType(), getNextMemberArc(), getNumMemberArcs(), markerOfParent(), markerToParent(), NewRowInformation::member, moveArcToNewMember(), CutArcListNode::nextMember, SPQRRowReducedMember::numCutArcs, SCIP_NETROWADD::reducedMembers, NewRowInformation::reversed, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_SERIES, SPQRmemberIsValid(), and TRUE.

Referenced by transformSingleParallel().

◆ transformSingleParallel()

static SCIP_RETCODE transformSingleParallel	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const reduced_member_id	reducedMember,
		const spqr_member	member,
		NewRowInformation *	info
	)

static

Updates a single rigid member to reflect the new row.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
reducedMember	The reduced member to transform
member	The member belonging to the reduced member
info	Stores information about the new row placement

Definition at line 10061 of file network.c.

References SCIP_CALL, SCIP_OKAY, and splitParallelRowAddition().

Referenced by transformComponentRowAddition().

◆ splitSeriesMergingRowAddition()

static SCIP_RETCODE splitSeriesMergingRowAddition	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		const reduced_member_id	reducedMember,
		const spqr_member	member,
		spqr_member *const	mergingMember,
		SCIP_Bool *const	isCut,
		spqr_arc *	representativeEdge
	)

static

Split a series member into multiple series members for merging.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
reducedMember	The reduced series member
member	The member belonging to the reduced member
mergingMember	The member that contains the arcs that are to be merged
isCut	Array that contains whether each arc is Cut
representativeEdge	Pointer to the representative arc for the split off arcs

Definition at line 10075 of file network.c.

References arcIsTree(), SCIP_NETROWADD::childrenStorage, createMarkerPairWithReferences(), createMember(), FALSE, findMember(), SPQRRowReducedMember::firstChild, getFirstMemberArc(), getNextMemberArc(), getNumMemberArcs(), markerOfParent(), markerToParent(), SPQRRowReducedMember::member, moveArcToNewMember(), SPQRRowReducedMember::numChildren, SPQRRowReducedMember::numCutArcs, SPQRRowReducedMember::parent, reducedMemberIsInvalid(), reducedMemberIsValid(), SCIP_NETROWADD::reducedMembers, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SPQRRowReducedMember::splitArc, SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, SPQR_MEMBERTYPE_SERIES, SPQRarcIsInvalid(), TRUE, SPQRRowReducedMember::type, TYPE_MERGED, and TYPE_PROPAGATED.

Referenced by splitAndMergeSeries().

◆ splitParallelMerging()

static SCIP_RETCODE splitParallelMerging	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	reducedMember,
		spqr_member	member,
		spqr_member *const	pMergeMember,
		spqr_arc *const	cutRepresentative
	)

static

Split a parallel member into multiple parallel members for merging.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
reducedMember	The reduced parallel member
member	The member belonging to the reduced member
pMergeMember	The member that contains the arcs that are to be merged
cutRepresentative	Pointer to the representative arc for all cut arcs

Definition at line 10195 of file network.c.

Referenced by splitAndMergeParallel(), and splitFirstLeaf().

◆ splitFirstLeaf()

static SCIP_RETCODE splitFirstLeaf	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	leaf,
		NewRowInformation *const	newRowInfo
	)

static

Update the first leaf to reflect the addition of the new row

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
leaf	The leaf to split the first node for
newRowInfo	Stores how to add the new row

Definition at line 10428 of file network.c.

References arcIsReversedNonRigid(), arcSetRepresentative(), arcSetReversed(), changeArcHead(), changeArcTail(), COLOR_SOURCE, createNode(), cutArcIsValid(), FALSE, findArcHead(), findArcMemberNoCompression(), findArcSign(), findArcTail(), SPQRRowReducedMember::firstCutArc, getFirstMemberArc(), getFirstNodeArc(), getMemberType(), getNextMemberArc(), getNextNodeArc(), NewRowInformation::head, SCIP_NETROWADD::isArcCut, SPQRRowReducedMember::member, NewRowInformation::member, SCIP_NETROWADD::nodeColors, SPQRRowReducedMember::numCutArcs, SPQRRowReducedMember::otherIsSource, SCIP_NETROWADD::reducedMembers, ArcSign::representative, NewRowInformation::representative, NewRowInformation::reversed, SCIP_Bool, SCIP_CALL, SCIP_OKAY, setArcHeadAndTail(), SPQRRowReducedMember::splitArc, SPQRRowReducedMember::splitHead, SPQRRowReducedMember::splitNode, splitParallelMerging(), SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_RIGID, NewRowInformation::tail, TRUE, UNCOLORED, and updateMemberType().

Referenced by mergeTree().

◆ mergeSplitMemberIntoParent()

static SCIP_RETCODE mergeSplitMemberIntoParent	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		spqr_member	member,
		spqr_member	parent,
		spqr_arc	parentToChild,
		spqr_arc	childToParent,
		SCIP_Bool	headToHead,
		spqr_node	parentNode,
		spqr_node	childNode,
		spqr_member *	mergedMember,
		spqr_node *	arcNodeOne,
		spqr_node *	arcNodeTwo,
		spqr_node *	thirdNode
	)

static

Merge an (updated) member into its parent.

This function is mainly there to prevent duplication.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
member	The member to merge
parent	The member's parent
parentToChild	The marker pointing from the parent to child
childToParent	The marker pointing from the child to the parent
headToHead	Should the marker heads be identified with one another?
parentNode	A node in the parent that is not adjacent to the marker
childNode	A node in the child that is not adjacent to the marker
mergedMember	Pointer to the member that contains both members after merging
arcNodeOne	The first identified node of the two marker arcs
arcNodeTwo	The second identified node of the two marker arcs
thirdNode	The node that parentNode and childNode are identified into

Definition at line 10577 of file network.c.

References clearArcHeadAndTail(), findEffectiveArcHead(), findEffectiveArcTail(), findMemberParentNoCompression(), markerOfParent(), markerToParent(), memberIsRepresentative(), mergeMemberArcList(), mergeMembers(), mergeNodeArcList(), mergeNodes(), SCIP_NETROWADD::nodeColors, removeArcFromMemberArcList(), SCIP_OKAY, SPQR_MEMBERTYPE_RIGID, SPQRmemberIsValid(), UNCOLORED, updateMemberParentInformation(), and updateMemberType().

Referenced by splitAndMergeParallel(), splitAndMergeRigid(), and splitAndMergeSeries().

◆ splitAndMergeSeries()

static SCIP_RETCODE splitAndMergeSeries	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	smallMember,
		SCIP_Bool	largeIsParent,
		NewRowInformation *const	newRowInfo,
		spqr_member	member
	)

static

Update a series member to reflect the addition of the new row, and merge it into the previous members that were updated.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
smallMember	The reduced series member
largeIsParent	Whether the large member containing previously updated members is the parent of this member
newRowInfo	Stores the information on how to add the new row
member	The member belonging to the reduced series member

Definition at line 10656 of file network.c.

References a, arcIsReversedNonRigid(), arcSetRepresentative(), arcSetReversed(), b, createNode(), cutArcIsValid(), FALSE, findEffectiveArcHead(), findEffectiveArcTail(), SPQRRowReducedMember::firstCutArc, getFirstMemberArc(), getNextMemberArc(), getNumMemberArcs(), NewRowInformation::head, markerOfParent(), markerToParent(), SPQRRowReducedMember::member, NewRowInformation::member, mergeArcSigns(), mergeSplitMemberIntoParent(), nodeIsRepresentative(), SCIP_NETROWADD::reducedMembers, NewRowInformation::representative, SCIP_Bool, SCIP_CALL, SCIP_OKAY, setArcHeadAndTail(), SPQRRowReducedMember::splitArc, SPQRRowReducedMember::splitHead, splitSeriesMergingRowAddition(), SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, NewRowInformation::tail, and TRUE.

Referenced by splitAndMerge().

◆ splitAndMergeParallel()

static SCIP_RETCODE splitAndMergeParallel	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	smallMember,
		SCIP_Bool	largeIsParent,
		NewRowInformation *const	newRowInfo,
		spqr_member	member
	)

static

Update a parallel member to reflect the addition of the new row, and merge it into the previous members that were updated.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
smallMember	The reduced parallel member
largeIsParent	Whether the large member containing previously updated members is the parent of this member
newRowInfo	Stores the information on how to add the new row
member	The member belonging to the reduced parallel member

Definition at line 10799 of file network.c.

References arcIsReversedNonRigid(), arcSetRepresentative(), arcSetReversed(), createNode(), FALSE, findArcMemberNoCompression(), findEffectiveArcHead(), findEffectiveArcTail(), getFirstMemberArc(), getNextMemberArc(), NewRowInformation::head, markerOfParent(), markerToParent(), SPQRRowReducedMember::member, NewRowInformation::member, mergeArcSigns(), mergeSplitMemberIntoParent(), nodeIsRepresentative(), SCIP_NETROWADD::reducedMembers, NewRowInformation::representative, SCIP_Bool, SCIP_CALL, SCIP_OKAY, setArcHeadAndTail(), SPQRRowReducedMember::splitArc, SPQRRowReducedMember::splitHead, splitParallelMerging(), SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, NewRowInformation::tail, and TRUE.

Referenced by splitAndMerge().

◆ splitAndMergeRigid()

static SCIP_RETCODE splitAndMergeRigid	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	smallMember,
		SCIP_Bool	largeIsParent,
		NewRowInformation *const	newRowInfo,
		spqr_member	member
	)

static

Update a rigid member to reflect the addition of the new row, and merge it into the previous members that were updated.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
smallMember	The reduced rigid member
largeIsParent	Whether the large member containing previously updated members is the parent of this member
newRowInfo	Stores the information on how to add the new row
member	The member belonging to the reduced rigid member

Definition at line 10931 of file network.c.

References changeArcHead(), changeArcTail(), COLOR_SOURCE, createNode(), findArcHead(), findArcSign(), findArcTail(), getFirstNodeArc(), getNextNodeArc(), NewRowInformation::head, SCIP_NETROWADD::isArcCut, markerOfParent(), markerToParent(), NewRowInformation::member, mergeArcSigns(), mergeSplitMemberIntoParent(), SCIP_NETROWADD::nodeColors, SPQRRowReducedMember::numCutArcs, SCIP_NETROWADD::reducedMembers, ArcSign::representative, NewRowInformation::representative, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SPQRRowReducedMember::splitNode, SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, NewRowInformation::tail, TRUE, UNCOLORED, and SPQRRowReducedMember::willBeReversed.

Referenced by splitAndMerge().

◆ splitAndMerge()

static SCIP_RETCODE splitAndMerge	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	smallMember,
		SCIP_Bool	largeIsParent,
		NewRowInformation *const	newRowInfo
	)

static

Update a member to reflect the addition of the new row, and merge it into the previous members that were updated.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
smallMember	The reduced rigid member
largeIsParent	Whether the large member containing previously updated members is the parent of this member
newRowInfo	Stores the information on how to add the new row

Definition at line 11077 of file network.c.

References FALSE, getMemberType(), SPQRRowReducedMember::member, SCIP_NETROWADD::reducedMembers, SCIP_NETROWADD::remainsNetwork, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPABORT, splitAndMergeParallel(), splitAndMergeRigid(), splitAndMergeSeries(), SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_SERIES, and SPQR_MEMBERTYPE_UNASSIGNED.

Referenced by mergeTree().

◆ mergeTree()

static SCIP_RETCODE mergeTree	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		reduced_member_id	root,
		NewRowInformation *const	newRowInfo
	)

static

Update an SPQR tree with multiple members to reflect the addition of a new row, merging it into one big rigid node.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
root	The root node of the SPQR tree that is to be merged
newRowInfo	Stores the information on how to add the new row

Definition at line 11120 of file network.c.

References SCIP_NETROWADD::childrenStorage, MergeTreeCallData::currentChild, FALSE, SPQRRowReducedMember::firstChild, MergeTreeCallData::id, SCIP_NETROWADD::mergeTreeCallData, SPQRRowReducedMember::numChildren, SPQRRowReducedMember::numPropagatedChildren, SPQRRowReducedMember::parent, reducedMemberIsValid(), SCIP_NETROWADD::reducedMembers, SCIP_CALL, SCIP_OKAY, splitAndMerge(), splitFirstLeaf(), TRUE, SPQRRowReducedMember::type, and TYPE_PROPAGATED.

Referenced by transformComponentRowAddition().

◆ transformComponentRowAddition()

static SCIP_RETCODE transformComponentRowAddition	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	newRow,
		SPQRRowReducedComponent *	component,
		NewRowInformation *const	newRowInfo
	)

static

Update an SPQR tree (a single component of the SPQR forest) to reflect addition of a new row.

Parameters

dec	The network matrix decomposition
newRow	The network matrix row addition data structure
component	The component to transform
newRowInfo	Stores the information on how to add the new row

Definition at line 11195 of file network.c.

References CutArcListNode::arc, arcIsReversedNonRigid(), CutArcListNode::arcReversed, changeLoopToSeries(), SCIP_NETROWADD::cutArcs, SPQRRowReducedMember::firstCutArc, getMemberType(), getNumMemberArcs(), SPQRRowReducedMember::member, NewRowInformation::member, mergeTree(), SPQRRowReducedMember::numChildren, SPQRRowReducedMember::numPropagatedChildren, reducedMemberIsValid(), SCIP_NETROWADD::reducedMembers, NewRowInformation::reversed, SPQRRowReducedComponent::root, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPABORT, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_SERIES, SPQR_MEMBERTYPE_UNASSIGNED, transformSingleParallel(), and transformSingleRigid().

Referenced by netrowaddAdd().

◆ netrowaddCreate()

static SCIP_RETCODE netrowaddCreate	(	BMS_BLKMEM *	blkmem,
		SCIP_NETROWADD **	prowadd
	)

static

Create the network row addition data structure.

Parameters

blkmem	Block memory
prowadd	Pointer to store the new row addition struct at

Definition at line 11256 of file network.c.

Referenced by SCIPnetmatdecTryAddRow().

◆ netrowaddFree()

static void netrowaddFree	(	BMS_BLKMEM *	blkmem,
		SCIP_NETROWADD **	prowadd
	)

static

Frees the network row addition data structure.

Parameters

blkmem	Block memory
prowadd	Pointer to row addition struct to be freed

Definition at line 11350 of file network.c.

Referenced by SCIPnetmatdecFree().

◆ netrowaddCheck()

static SCIP_RETCODE netrowaddCheck	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	rowadd,
		int	row,
		const int *	nonzcols,
		const double *	nonzvals,
		int	nnonzs
	)

static

Checks if the given row can be added to the network decomposition.

Parameters

dec	The network matrix decomposition
rowadd	The network matrix row addition data structure
row	The row to be checked
nonzcols	The column indices of the row's nonzero values
nonzvals	The matrix entries of the row's nonzeroes
nnonzs	The number of nonzeroes in the row

Definition at line 11388 of file network.c.

References allocateRigidSearchMemory(), allocateTreeSearchMemory(), cleanUpPreviousIteration(), cleanUpRowMemberInformation(), constructRowReducedDecomposition(), createReducedDecompositionCutArcs(), determineLeafReducedMembers(), determineMergeableTypes(), netMatDecDataContainsRow(), newRowUpdateRowInformation(), SCIP_NETROWADD::numReducedComponents, propagateComponents(), SCIP_NETROWADD::reducedComponents, SCIP_NETROWADD::remainsNetwork, SPQRRowReducedComponent::root, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, and TRUE.

Referenced by SCIPnetmatdecTryAddRow().

◆ netrowaddAdd()

static SCIP_RETCODE netrowaddAdd	(	SCIP_NETMATDECDATA *	dec,
		SCIP_NETROWADD *	rowadd
	)

static

Adds the last checked row to the network decomposition.

Parameters

dec	The network matrix decomposition
rowadd	The network matrix row addition data structure

Definition at line 11442 of file network.c.

References arcIsReversedNonRigid(), arcSetRepresentative(), arcSetReversed(), changeLoopToSeries(), createConnectedParallel(), createMarkerPairWithReferences(), createRowArc(), createStandaloneParallel(), decreaseNumConnectedComponents(), FALSE, findNode(), getFirstMemberArc(), getMemberType(), getNumMemberArcs(), NewRowInformation::head, SCIP_NETROWADD::isArcCut, SCIP_NETROWADD::isArcCutReversed, NewRowInformation::member, SCIP_NETMATDECDATA::members, moveArcToNewMember(), SCIP_NETROWADD::newColumnArcs, SCIP_NETROWADD::newColumnReversed, SCIP_NETROWADD::newRowIndex, NEWROWINFORMATION_EMPTY, SCIP_NETROWADD::numColumnArcs, numConnectedComponents(), SCIP_NETROWADD::numReducedComponents, SCIP_NETROWADD::reducedComponents, SCIP_NETROWADD::remainsNetwork, reorderComponent(), NewRowInformation::representative, NewRowInformation::reversed, SCIP_CALL, SCIP_OKAY, setArcHeadAndTail(), SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_UNASSIGNED, SPQRarcIsValid(), SPQRnodeIsValid(), NewRowInformation::tail, transformComponentRowAddition(), TRUE, and SPQRNetworkDecompositionMember::type.

Referenced by SCIPnetmatdecTryAddRow().

◆ netrowaddRemainsNetwork()

static SCIP_Bool netrowaddRemainsNetwork ( const SCIP_NETROWADD * rowadd )

static

Returns whether the last checked row can be added to the network decomposition.

Parameters

rowadd The network matrix row addition data structure

Definition at line 11551 of file network.c.

References SCIP_NETROWADD::remainsNetwork.

Referenced by SCIPnetmatdecTryAddRow().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ SPQR_INVALID

◆ SPQR_INVALID_ROW

◆ SPQR_INVALID_COL

◆ MARKER_ROW_ELEMENT

◆ MARKER_COLUMN_ELEMENT

◆ SPQR_INVALID_MEMBER

◆ SPQR_INVALID_NODE

◆ SPQR_INVALID_ARC

◆ INVALID_PATH_ARC

◆ INVALID_REDUCED_MEMBER

◆ NEWCOLINFORMATION_EMPTY

◆ INVALID_CUT_ARC

◆ NEWROWINFORMATION_EMPTY

Typedef Documentation

◆ spqr_matrix_size

◆ spqr_row

◆ spqr_col

◆ spqr_element

◆ spqr_member

◆ spqr_node

◆ spqr_arc

◆ path_arc_id

◆ reduced_member_id

◆ children_idx

◆ cut_arc_id

Enumeration Type Documentation

◆ SPQRMemberType

◆ ReducedMemberType

◆ MemberPathType

◆ RowReducedMemberType

◆ COLOR_STATUS

Function Documentation

◆ SPQRrowIsInvalid()

◆ SPQRcolIsInvalid()

◆ SPQRrowIsValid()

◆ SPQRcolIsValid()

◆ SPQRelementIsRow()

◆ SPQRelementIsColumn()

◆ SPQRelementToRow()

◆ SPQRrowToElement()

◆ SPQRelementToColumn()

◆ SPQRcolumnToElement()

◆ SPQRmemberIsInvalid()

◆ SPQRmemberIsValid()

◆ SPQRnodeIsInvalid()

◆ SPQRnodeIsValid()

◆ SPQRarcIsInvalid()

◆ SPQRarcIsValid()

◆ nodeIsRepresentative()

◆ findNode()

◆ findNodeNoCompression()

◆ findArcTail()

◆ findArcHead()

◆ findArcHeadNoCompression()

◆ findArcTailNoCompression()

◆ getFirstNodeArc()

◆ getNextNodeArcNoCompression()

◆ getNextNodeArc()

◆ getPreviousNodeArc()

◆ mergeNodeArcList()

◆ arcFlipReversed()

◆ arcSetReversed()

◆ arcSetRepresentative()

◆ mergeNodes()

◆ memberIsRepresentative()

◆ findMember()

◆ findMemberNoCompression()

◆ mergeMembers()

◆ findArcMember()

◆ findArcMemberNoCompression()

◆ findMemberParent()

◆ findMemberParentNoCompression()