- Generated by
1.16.1
Methods for detecting network (sub)matrices.
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:
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:
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:
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 } |
| #define SPQR_INVALID_ROW SPQR_INVALID |
Definition at line 142 of file network.c.
Referenced by netrowaddCreate(), and SPQRrowIsInvalid().
| #define SPQR_INVALID_COL SPQR_INVALID |
Definition at line 143 of file network.c.
Referenced by netcoladdCreate(), and SPQRcolIsInvalid().
| #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.
Referenced by columnTransformSingleRigid(), createChildMarker(), createParentMarker(), netMatDecDataCreateDiGraph(), and rigidTransformArcIntoCycle().
| #define MARKER_COLUMN_ELEMENT (INT_MAX) |
Definition at line 189 of file network.c.
Referenced by columnTransformSingleRigid(), createChildMarker(), createParentMarker(), and rigidTransformArcIntoCycle().
| #define SPQR_INVALID_MEMBER (-1) |
Definition at line 260 of file network.c.
Referenced by columnTransformSingleRigid(), createArc(), createMember(), netcoladdAdd(), netMatDecDataCreate(), netrowaddAdd(), reorderComponent(), rigidTransformArcIntoCycle(), splitAndMergeParallel(), splitAndMergeRigid(), splitAndMergeSeries(), splitFirstLeaf(), splitParallelMerging(), splitParallelRowAddition(), splitSeries(), splitSeriesMergingRowAddition(), transformAndMergeParallel(), transformAndMergeRigid(), transformAndMergeSeries(), transformPath(), and updateMemberParentInformation().
| #define SPQR_INVALID_NODE (-1) |
Definition at line 285 of file network.c.
Referenced by allocateRigidSearchMemory(), articulationPoints(), checkNeighbourColoringArticulationNode(), clearArcHeadAndTail(), createArc(), createCutArc(), createNode(), createPathArc(), createReducedMembersToRoot(), createRowReducedMembersToRoot(), determineAndColorSplitNode(), determineRigidPath(), determineSingleRowRigidType(), determineSplitTypeRigid(), intersectionOfAllPaths(), rigidConnectedColoring(), rigidDetermineCandidateNodesFromAdjacentComponents(), rigidFindStarNodes(), splitAndMergeParallel(), splitAndMergeRigid(), splitAndMergeSeries(), splitFirstLeaf(), transformAndMergeParallel(), transformAndMergeSeries(), transformFirstPathMember(), and transformSingleRigid().
| #define SPQR_INVALID_ARC (-1) |
Definition at line 313 of file network.c.
Referenced by arcSetRepresentative(), checkNeighbourColoringArticulationNode(), columnTransformSingleRigid(), createArc(), createMarkerPair(), createMember(), createNode(), createRowReducedMembersToRoot(), determinePathTypes(), mergeMemberArcList(), mergeNodeArcList(), netcoladdAdd(), netMatDecDataCreate(), netMatDecDataRemoveComponent(), netrowaddAdd(), propagateComponents(), propagateCycles(), removeArcFromMemberArcList(), removeArcFromNodeArcList(), reorderComponent(), rigidGetSplittableArticulationPointsOnPath(), rigidTransformArcIntoCycle(), splitAndMergeParallel(), splitAndMergeSeries(), splitFirstLeaf(), splitParallelMerging(), splitParallelRowAddition(), splitSeries(), splitSeriesMerging(), splitSeriesMergingRowAddition(), transformAndMergeParallel(), transformAndMergeSeries(), transformFirstPathMember(), transformPath(), and updateMemberParentInformation().
| #define INVALID_PATH_ARC (-1) |
Definition at line 3439 of file network.c.
Referenced by cleanupPreviousIteration(), createReducedMembersToRoot(), and netcoladdCreate().
| #define INVALID_REDUCED_MEMBER (-1) |
Definition at line 3480 of file network.c.
Referenced by cleanUpMemberInformation(), cleanUpRowMemberInformation(), constructReducedDecomposition(), constructRowReducedDecomposition(), createReducedMembersToRoot(), createRowReducedMembersToRoot(), determinePathTypes(), propagateComponents(), propagateCycles(), and transformAndMergeParallel().
| #define NEWCOLINFORMATION_EMPTY { SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, SPQR_INVALID_NODE, SPQR_INVALID_ARC, FALSE } |
Definition at line 5498 of file network.c.
Referenced by netcoladdAdd().
| #define INVALID_CUT_ARC (-1) |
Definition at line 6772 of file network.c.
Referenced by createReducedDecompositionCutArcs(), createRowReducedMembersToRoot(), and netrowaddCreate().
| #define NEWROWINFORMATION_EMPTY { SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, SPQR_INVALID_NODE, SPQR_INVALID_ARC, FALSE } |
Definition at line 7016 of file network.c.
Referenced by netrowaddAdd().
| 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 |
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.
| 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.
| 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.
| typedef int path_arc_id |
| typedef int reduced_member_id |
| typedef int children_idx |
| typedef int cut_arc_id |
| enum SPQRMemberType |
The type of the member
| enum ReducedMemberType |
Type of the member, signifies to what degree we processed the member and how to treat with it when updating the graph.
| enum MemberPathType |
Defines the structure of the path in the reduced member
| enum RowReducedMemberType |
Type of the reduced member
Indicates whether the member is processed, and whether it should be merged or left the same.
| enum COLOR_STATUS |
Determine if the row index is invalid
| row | The row to check |
Definition at line 151 of file network.c.
References SCIP_Bool, and SPQR_INVALID_ROW.
Referenced by SPQRrowIsValid().
Determine if the column index is invalid
| col | The column to check |
Definition at line 160 of file network.c.
References SCIP_Bool, and SPQR_INVALID_COL.
Referenced by SPQRcolIsValid().
Determine if the row index is valid
| row | The row to check |
Definition at line 169 of file network.c.
References SCIP_Bool, and SPQRrowIsInvalid().
Referenced by getDecompositionRowArc(), netMatDecDataContainsRow(), setDecompositionRowArc(), and SPQRrowToElement().
Determine if the column index is valid
| col | The column to check |
Definition at line 178 of file network.c.
References SCIP_Bool, and SPQRcolIsInvalid().
Referenced by getDecompositionColumnArc(), netMatDecDataContainsColumn(), setDecompositionColumnArc(), and SPQRcolumnToElement().
|
static |
Checks if an element is a row
| element | The element to check |
Definition at line 194 of file network.c.
References SCIP_Bool.
Referenced by arcIsTree(), netMatDecDataCreateDiGraph(), process_arc(), SPQRelementIsColumn(), and SPQRelementToRow().
|
static |
Checks if an element is a column
| element | The element to check |
Definition at line 203 of file network.c.
References SCIP_Bool, and SPQRelementIsRow().
Referenced by columnTransformSingleRigid(), rigidTransformArcIntoCycle(), and SPQRelementToColumn().
|
static |
Convert an element to the corresponding row index
| element | The element to convert |
Definition at line 212 of file network.c.
References assert(), and SPQRelementIsRow().
Referenced by columnTransformSingleRigid(), netMatDecDataCreateDiGraph(), process_arc(), and rigidTransformArcIntoCycle().
|
static |
Convert a row to the corresponding element
| row | The row to convert |
Definition at line 222 of file network.c.
References assert(), and SPQRrowIsValid().
Referenced by createRowArc().
|
static |
Convert an element to the corresponding column index
| element | The element to convert |
Definition at line 232 of file network.c.
References assert(), and SPQRelementIsColumn().
Referenced by columnTransformSingleRigid(), netMatDecDataCreateDiGraph(), and rigidTransformArcIntoCycle().
|
static |
Convert a column to the corresponding element
| column | The column to convert |
Definition at line 242 of file network.c.
References assert(), and SPQRcolIsValid().
Referenced by createColumnArc().
|
static |
Check if a member is invalid
| member | The member to check |
Definition at line 264 of file network.c.
References SCIP_Bool.
Referenced by createArc(), findMemberParent(), findMemberParentNoCompression(), memberIsRepresentative(), netMatDecDataCreateDiGraph(), and SPQRmemberIsValid().
|
static |
Check if a member is valid
| member | The member to check |
Definition at line 272 of file network.c.
References SCIP_Bool, and 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().
Check if a node is invalid
| node | The node to check |
Definition at line 289 of file network.c.
References SCIP_Bool.
Referenced by determineAndColorSplitNode(), determineRigidType(), determineSingleRowRigidType(), determineSplitTypeFirstLeaf(), determineSplitTypeRigid(), nodeIsRepresentative(), rigidDetermineCandidateNodesFromAdjacentComponents(), rigidFindStarNodes(), rigidGetSplittableArticulationPointsOnPath(), setTerminalHead(), setTerminalTail(), and SPQRnodeIsValid().
Check if a node is valid
| node | The node to check |
Definition at line 298 of file network.c.
References SCIP_Bool, and 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().
Check if an arc is invalid
| arc | The arc to check |
Definition at line 317 of file network.c.
References SCIP_Bool.
Referenced by arcIsRepresentative(), decompositionGetFundamentalCycleRows(), determinePathRigidType(), mergeNodeArcList(), netMatDecDataCreateDiGraph(), splitSeriesMergingRowAddition(), SPQRarcIsValid(), transformAndMergeRigid(), transformAndMergeSeries(), and zeroOutColors().
Check if an arc is valid
| arc | The arc to check |
Definition at line 326 of file network.c.
References SCIP_Bool, and 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().
|
static |
Check if a node is a representative in the union-find data structure for nodes
| dec | The network decomposition |
| node | The node to check if it is representative |
Definition at line 440 of file network.c.
References assert(), SCIP_NETMATDECDATA::nodes, SPQRNetworkDecompositionNode::representativeNode, SCIP_Bool, SPQRnodeIsInvalid(), and SPQRnodeIsValid().
Referenced by addArcToNodeArcList(), changeArcHead(), changeArcTail(), determineRigidPath(), getNextNodeArc(), getNextNodeArcNoCompression(), getPreviousNodeArc(), mergeNodes(), rigidGetSplittableArticulationPointsOnPath(), splitAndMergeParallel(), and splitAndMergeSeries().
|
static |
Find the node its representative node in the union-find data structure
| dec | The network decomposition |
| node | The node to find the representative for |
Definition at line 456 of file network.c.
References assert(), SCIP_NETMATDECDATA::nodes, SPQRNetworkDecompositionNode::representativeNode, and SPQRnodeIsValid().
Referenced by findArcHead(), findArcTail(), netcoladdAdd(), and netrowaddAdd().
|
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.
| dec | The network decomposition |
| node | The node to find the representative for |
Definition at line 493 of file network.c.
References assert(), SCIP_NETMATDECDATA::nodes, SPQRNetworkDecompositionNode::representativeNode, and SPQRnodeIsValid().
Referenced by findArcHeadNoCompression(), and findArcTailNoCompression().
|
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.
| 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, assert(), 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().
|
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.
| 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, assert(), 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().
|
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.
| 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, assert(), findNodeNoCompression(), SPQRNetworkDecompositionArc::head, and SPQRarcIsValid().
Referenced by findEffectiveArcHeadNoCompression(), findEffectiveArcTailNoCompression(), getNextNodeArcNoCompression(), intersectionOfAllPaths(), and rigidConnectedColoring().
|
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.
| 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, assert(), findNodeNoCompression(), SPQRarcIsValid(), and SPQRNetworkDecompositionArc::tail.
Referenced by findEffectiveArcHeadNoCompression(), findEffectiveArcTailNoCompression(), getNextNodeArc(), getNextNodeArcNoCompression(), getPreviousNodeArc(), intersectionOfAllPaths(), and rigidConnectedColoring().
|
static |
Find the first arc in the list of arcs that are adjacent to the given node.
These arcs form a cyclic linked-list.
| dec | The network decomposition |
| node | The node to find the arc for |
Definition at line 596 of file network.c.
References assert(), 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().
|
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.
| 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, assert(), findArcHeadNoCompression(), findArcTailNoCompression(), SPQRNetworkDecompositionArc::headArcListNode, SPQRNetworkDecompositionArcListNode::next, nodeIsRepresentative(), SPQRarcIsValid(), and SPQRNetworkDecompositionArc::tailArcListNode.
Referenced by decompositionGetFundamentalCycleRows().
|
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.
| 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, assert(), 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().
|
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.
| 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, assert(), findArcHead(), findArcTailNoCompression(), SPQRNetworkDecompositionArc::headArcListNode, nodeIsRepresentative(), SPQRNetworkDecompositionArcListNode::previous, SPQRarcIsValid(), SPQRNetworkDecompositionArc::tail, and SPQRNetworkDecompositionArc::tailArcListNode.
Referenced by mergeNodeArcList().
|
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.
| 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, assert(), 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().
|
static |
Flips the direction a given arc.
| dec | The network decomposition |
| arc | The arc that we want to flip |
Definition at line 754 of file network.c.
References SCIP_NETMATDECDATA::arcs, assert(), SPQRNetworkDecompositionArc::reversed, and SPQRarcIsValid().
Referenced by splitSeries().
|
static |
Sets the direction of a given arc
| 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, assert(), SPQRNetworkDecompositionArc::reversed, SCIP_Bool, and SPQRarcIsValid().
Referenced by netcoladdAdd(), netrowaddAdd(), splitAndMergeParallel(), splitAndMergeSeries(), splitFirstLeaf(), transformAndMergeParallel(), transformAndMergeSeries(), and transformFirstPathMember().
|
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).
| 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, assert(), SPQRNetworkDecompositionArc::representative, SPQR_INVALID_ARC, and SPQRarcIsValid().
Referenced by netcoladdAdd(), netrowaddAdd(), splitAndMergeParallel(), splitAndMergeSeries(), splitFirstLeaf(), transformAndMergeParallel(), transformAndMergeSeries(), and transformFirstPathMember().
|
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.
| dec | The network decomposition |
| first | A node to merge |
| second | A second node to merge |
Definition at line 808 of file network.c.
References assert(), mergeNodeArcList(), nodeIsRepresentative(), SCIP_NETMATDECDATA::nodes, SPQRNetworkDecompositionNode::representativeNode, and SCIPswapInts().
Referenced by mergeGivenMemberIntoParent(), and mergeSplitMemberIntoParent().
|
static |
Check if a member is a representative in the union-find data structure for members.
| dec | The network decomposition |
| member | The member to check |
Definition at line 841 of file network.c.
References assert(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::representativeMember, SCIP_Bool, 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().
|
static |
Find the member its representative member in the union-find data structure
| dec | The network decomposition |
| member | The member to find the representative for |
Definition at line 855 of file network.c.
References assert(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::representativeMember, and SPQRmemberIsValid().
Referenced by checkLeaf(), determineSingleComponentType(), findArcChildMember(), findArcMember(), findMemberParent(), splitParallelMerging(), and splitSeriesMergingRowAddition().
|
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.
| dec | The network decomposition |
| member | The member to find the representative for |
Definition at line 892 of file network.c.
References assert(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::representativeMember, and SPQRmemberIsValid().
Referenced by findArcChildMemberNoCompression(), findArcMemberNoCompression(), findMemberParentNoCompression(), and updateMemberParentInformation().
|
static |
Merge two representative members (Union operation) in the union-find data structure.
Returns the id of the member that becomes representative for both.
| 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 assert(), memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::representativeMember, and SCIPswapInts().
Referenced by mergeGivenMemberIntoParent(), and mergeSplitMemberIntoParent().
|
static |
Finds the member in which the arc is located
| dec | The network decomposition |
| arc | The arc to find the member for |
Definition at line 951 of file network.c.
References SCIP_NETMATDECDATA::arcs, assert(), findMember(), SPQRNetworkDecompositionArc::member, and SPQRarcIsValid().
Referenced by constructReducedDecomposition(), constructRowReducedDecomposition(), createPathArcs(), createReducedDecompositionCutArcs(), and netMatDecDataCreateDiGraph().
|
static |
Finds the member in which the arc is located, without compressing the member union-find tree
| dec | The network decomposition |
| arc | The arc to find the member for |
Definition at line 967 of file network.c.
References SCIP_NETMATDECDATA::arcs, assert(), findMemberNoCompression(), SPQRNetworkDecompositionArc::member, and SPQRarcIsValid().
Referenced by decompositionGetFundamentalCycleRows(), getRelativeOrientationParallel(), getRelativeOrientationRigid(), getRelativeOrientationSeries(), moveArcToNewMember(), process_arc(), removeArcFromMemberArcList(), splitAndMergeParallel(), and splitFirstLeaf().
|
static |
Find the representative parent member of the given member.
Note the given member must be representative.
| dec | The network decomposition |
| member | The member to find the parent for. Must be representative. |
Definition at line 985 of file network.c.
References assert(), findMember(), memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::parentMember, SPQRmemberIsInvalid(), and SPQRmemberIsValid().
Referenced by columnTransformSingleRigid(), constructReducedDecomposition(), constructRowReducedDecomposition(), createReducedMembersToRoot(), createRowReducedMembersToRoot(), determinePathTypes(), netMatDecDataCreateDiGraph(), reorderComponent(), rigidTransformArcIntoCycle(), splitParallelRowAddition(), and splitSeries().
|
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.
| dec | The network decomposition |
| member | The member to find the parent for. Must be representative. |
Definition at line 1011 of file network.c.
References assert(), findMemberNoCompression(), memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::parentMember, SPQRmemberIsInvalid(), and SPQRmemberIsValid().
Referenced by mergeGivenMemberIntoParent(), mergeSplitMemberIntoParent(), and netMatDecDataIsMinimal().
|
static |
Find the child member associated to the given arc, which must be virtual.
| 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, assert(), SPQRNetworkDecompositionArc::childMember, findMember(), and SPQRarcIsValid().
Referenced by columnTransformSingleRigid(), moveArcToNewMember(), netMatDecDataCreateDiGraph(), rigidTransformArcIntoCycle(), splitParallelRowAddition(), and splitSeries().
|
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.
| 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, assert(), SPQRNetworkDecompositionArc::childMember, findMemberNoCompression(), and SPQRarcIsValid().
Referenced by moveArcToNewMember(), and process_arc().
|
static |
Checks if the arc has a child member
| dec | The network decomposition |
| arc | The arc to check |
Definition at line 1065 of file network.c.
References SCIP_NETMATDECDATA::arcs, assert(), SPQRNetworkDecompositionArc::childMember, SCIP_Bool, SPQRarcIsValid(), and SPQRmemberIsValid().
Referenced by columnTransformSingleRigid(), netMatDecDataCreateDiGraph(), process_arc(), rigidTransformArcIntoCycle(), splitParallelRowAddition(), and splitSeries().
|
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
| dec | The network decomposition |
| arc | The arc to check |
Definition at line 1079 of file network.c.
References SCIP_NETMATDECDATA::arcs, assert(), SPQRNetworkDecompositionArc::element, SCIP_Bool, 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().
|
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.
| dec | The network decomposition |
| arc | The arc to check |
Definition at line 1105 of file network.c.
References SCIP_NETMATDECDATA::arcs, assert(), SPQRNetworkDecompositionArc::representative, SCIP_Bool, SPQRarcIsInvalid(), and SPQRarcIsValid().
Referenced by mergeArcSigns().
|
static |
Find an arcs representative and its direction in the signed union-find data structure for arcs.
| 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, assert(), ArcSign::representative, SPQRNetworkDecompositionArc::representative, ArcSign::reversed, SPQRNetworkDecompositionArc::reversed, SCIP_Bool, and SPQRarcIsValid().
Referenced by columnTransformSingleRigid(), determineRigidType(), determineSplitTypeFirstLeaf(), determineSplitTypeRigid(), findEffectiveArcHead(), findEffectiveArcTail(), getRelativeOrientationRigid(), netMatDecDataCreateDiGraph(), rigidConnectedColoring(), rigidConnectedColoringRecursive(), rigidFindStarNodes(), splitAndMergeRigid(), splitFirstLeaf(), transformAndMergeRigid(), transformFirstPathMember(), and transformSingleRigid().
|
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.
| 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, assert(), ArcSign::representative, SPQRNetworkDecompositionArc::representative, ArcSign::reversed, SPQRNetworkDecompositionArc::reversed, SCIP_Bool, and SPQRarcIsValid().
Referenced by findEffectiveArcHeadNoCompression(), and findEffectiveArcTailNoCompression().
|
static |
Finds the arcs head, taking into account whether it is reversed by the signed union-find data structure.
| dec | The network decomposition |
| arc | The arc to find the head for |
Definition at line 1201 of file network.c.
References assert(), findArcHead(), findArcSign(), and findArcTail().
Referenced by checkRigidLeaf(), createCutArc(), createPathArc(), determinePathRigidType(), getRelativeOrientationRigid(), mergeGivenMemberIntoParent(), mergeSplitMemberIntoParent(), splitAndMergeParallel(), splitAndMergeSeries(), and transformSingleRigid().
|
static |
Finds the arcs tail, taking into account whether it is reversed by the signed union-find data structure.
| dec | The network decomposition |
| arc | The arc to find the tail for |
Definition at line 1219 of file network.c.
References assert(), findArcHead(), findArcSign(), and findArcTail().
Referenced by checkRigidLeaf(), createCutArc(), createPathArc(), determinePathRigidType(), mergeGivenMemberIntoParent(), mergeSplitMemberIntoParent(), splitAndMergeParallel(), and splitAndMergeSeries().
|
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.
| dec | The network decomposition |
| arc | The arc to find the head for |
Definition at line 1240 of file network.c.
References assert(), findArcHeadNoCompression(), findArcSignNoCompression(), and findArcTailNoCompression().
Referenced by decompositionGetFundamentalCycleRows(), netMatDecDataCreateDiGraph(), and transformSingleRigid().
|
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.
| dec | The network decomposition |
| arc | The arc to find the tail for |
Definition at line 1262 of file network.c.
References assert(), findArcHeadNoCompression(), findArcSignNoCompression(), and findArcTailNoCompression().
Referenced by decompositionGetFundamentalCycleRows(), getRelativeOrientationRigid(), netMatDecDataCreateDiGraph(), and transformSingleRigid().
|
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.
| 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, assert(), SPQRNetworkDecompositionArc::representative, SPQRNetworkDecompositionArc::reversed, SCIP_Bool, and SCIPswapInts().
Referenced by splitAndMergeParallel(), splitAndMergeRigid(), splitAndMergeSeries(), transformAndMergeParallel(), transformAndMergeRigid(), and transformAndMergeSeries().
|
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.
| dec | The network decomposition |
| arc | The arc to check |
Definition at line 1329 of file network.c.
References SCIP_NETMATDECDATA::arcs, assert(), SPQRNetworkDecompositionArc::reversed, SCIP_Bool, 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().
|
static |
Gets the element (row/column) associated to the given arc.
| dec | The network decomposition |
| arc | The arc to get the element for |
Definition at line 1343 of file network.c.
References SCIP_NETMATDECDATA::arcs, assert(), SPQRNetworkDecompositionArc::element, and SPQRarcIsValid().
Referenced by columnTransformSingleRigid(), netMatDecDataCreateDiGraph(), process_arc(), and rigidTransformArcIntoCycle().
|
static |
Check whether the network matrix decomposition contains an edge for the given row index.
| dec | The network matrix decomposition |
| row | The row index that is checked |
Definition at line 1357 of file network.c.
References assert(), SCIP_NETMATDECDATA::rowArcs, SCIP_Bool, SPQRarcIsValid(), and SPQRrowIsValid().
Referenced by netMatDecDataCreateDiGraph(), netrowaddCheck(), and SCIPnetmatdecContainsRow().
|
static |
Check whether the network matrix decomposition contains an edge for the given column index.
| dec | The network matrix decomposition |
| column | The column index that is checked |
Definition at line 1370 of file network.c.
References assert(), SCIP_NETMATDECDATA::columnArcs, SCIP_Bool, SPQRarcIsValid(), and SPQRcolIsValid().
Referenced by netcoladdCheck(), and SCIPnetmatdecContainsColumn().
|
static |
Associate the given arc to the given column in the network matrix decomposition.
| 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 assert(), SCIP_NETMATDECDATA::columnArcs, SPQRarcIsValid(), and SPQRcolIsValid().
Referenced by createColumnArc().
|
static |
Associate the given arc to the given row in the network matrix decomposition.
| 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 assert(), SCIP_NETMATDECDATA::rowArcs, SPQRarcIsValid(), and SPQRrowIsValid().
Referenced by createRowArc().
|
static |
Get the decomposition arc associated to the given column.
| dec | The network matrix decomposition |
| col | The given column |
Definition at line 1413 of file network.c.
References assert(), SCIP_NETMATDECDATA::columnArcs, and SPQRcolIsValid().
Referenced by decompositionGetFundamentalCycleRows(), and newRowUpdateRowInformation().
|
static |
Get the decomposition arc associated to the given row.
| dec | The network matrix decomposition |
| row | The given row |
Definition at line 1426 of file network.c.
References assert(), SCIP_NETMATDECDATA::rowArcs, and SPQRrowIsValid().
Referenced by newColUpdateColInformation().
|
static |
Initialize the network matrix decomposition data structure.
| 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.
References SPQRNetworkDecompositionArc::arcListNode, SCIP_NETMATDECDATA::arcs, assert(), BMSallocBlockMemory, BMSallocBlockMemoryArray, SCIP_NETMATDECDATA::columnArcs, SCIP_NETMATDECDATA::env, SCIP_NETMATDECDATA::firstFreeArc, i, SCIP_NETMATDECDATA::memArcs, SPQRNetworkDecompositionArc::member, SCIP_NETMATDECDATA::members, SCIP_NETMATDECDATA::memColumns, SCIP_NETMATDECDATA::memMembers, SCIP_NETMATDECDATA::memNodes, SCIP_NETMATDECDATA::memRows, SPQRNetworkDecompositionArcListNode::next, SCIP_NETMATDECDATA::nodes, SCIP_NETMATDECDATA::numArcs, SCIP_NETMATDECDATA::numConnectedComponents, SCIP_NETMATDECDATA::numMembers, SCIP_NETMATDECDATA::numNodes, SCIP_NETMATDECDATA::rowArcs, SCIP_ALLOC, SCIP_OKAY, SPQR_INVALID_ARC, and SPQR_INVALID_MEMBER.
Referenced by SCIPnetmatdecCreate().
|
static |
Free the network matrix decomposition data structure
| pdec | pointer to the network matrix decomposition to freed |
Definition at line 1513 of file network.c.
References SCIP_NETMATDECDATA::arcs, assert(), 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().
|
static |
Get the first arc of the linked list of arcs contained in the given member.
| dec | The network matrix decomposition |
| member | The given member |
Definition at line 1532 of file network.c.
References assert(), 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().
|
static |
Given the current arc, get the next arc of the linked list of arcs that are in the same member.
| dec | The network matrix decomposition |
| arc | The current arc |
Definition at line 1546 of file network.c.
References SPQRNetworkDecompositionArc::arcListNode, SCIP_NETMATDECDATA::arcs, assert(), SPQRNetworkDecompositionArcListNode::next, and SPQRarcIsValid().
Referenced by decompositionGetFundamentalCycleRows(), netMatDecDataCreateDiGraph(), rigidConnectedColoring(), splitAndMergeParallel(), splitAndMergeSeries(), splitFirstLeaf(), splitParallelRowAddition(), splitSeries(), splitSeriesMerging(), splitSeriesMergingRowAddition(), and transformAndMergeParallel().
|
static |
Given the current arc, get the previous arc of the linked list of arcs that are in the same member.
| dec | The network matrix decomposition |
| arc | The current arc |
Definition at line 1561 of file network.c.
References SPQRNetworkDecompositionArc::arcListNode, SCIP_NETMATDECDATA::arcs, assert(), SPQRNetworkDecompositionArcListNode::previous, and SPQRarcIsValid().
Referenced by addArcToMemberArcList(), and mergeMemberArcList().
|
static |
Adds an arc to the linked list of arcs of the given member.
| 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, assert(), SPQRNetworkDecompositionMember::firstArc, getFirstMemberArc(), getPreviousMemberArc(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionArcListNode::next, SPQRNetworkDecompositionMember::numArcs, SPQRNetworkDecompositionArcListNode::previous, and SPQRarcIsValid().
Referenced by createChildMarker(), createColumnArc(), createParentMarker(), createRowArc(), and moveArcToNewMember().
|
static |
Create a new arc in the network matrix decomposition.
| 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.
References SPQRNetworkDecompositionArc::arcListNode, SCIP_NETMATDECDATA::arcs, assert(), BMSreallocBlockMemoryArray, SPQRNetworkDecompositionArc::childMember, SCIP_NETMATDECDATA::env, SCIP_NETMATDECDATA::firstFreeArc, SPQRNetworkDecompositionArc::head, SPQRNetworkDecompositionArc::headArcListNode, i, SCIP_NETMATDECDATA::memArcs, SPQRNetworkDecompositionArc::member, memberIsRepresentative(), SPQRNetworkDecompositionArcListNode::next, SCIP_NETMATDECDATA::numArcs, SPQRNetworkDecompositionArcListNode::previous, SPQRNetworkDecompositionArc::reversed, SCIP_ALLOC, SCIP_Bool, SCIP_OKAY, SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, SPQRarcIsValid(), SPQRmemberIsInvalid(), SPQRNetworkDecompositionArc::tail, and SPQRNetworkDecompositionArc::tailArcListNode.
Referenced by createChildMarker(), createColumnArc(), createParentMarker(), and createRowArc().
|
static |
Create a new arc in the network matrix decomposition that is associated to the given row.
| 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_Bool, SCIP_CALL, SCIP_OKAY, setDecompositionRowArc(), and SPQRrowToElement().
Referenced by columnTransformSingleRigid(), createConnectedParallel(), createConnectedSeries(), createStandaloneParallel(), createStandaloneSeries(), netrowaddAdd(), and rigidTransformArcIntoCycle().
|
static |
Create a new arc in the network matrix decomposition that is associated to the given column.
| 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_Bool, SCIP_CALL, SCIP_OKAY, setDecompositionColumnArc(), and SPQRcolumnToElement().
Referenced by columnTransformSingleRigid(), createConnectedParallel(), createConnectedSeries(), createStandaloneParallel(), createStandaloneSeries(), netcoladdAdd(), and rigidTransformArcIntoCycle().
|
static |
Create a new member in the network matrix decomposition.
| 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 assert(), 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().
|
static |
Create a new node in the network matrix decomposition.
| 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().
|
static |
Remove an arc from the linked list of arcs that are adjacent to a given node.
| 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, SCIP_Bool, SPQR_INVALID_ARC, and SPQRNetworkDecompositionArc::tailArcListNode.
Referenced by changeArcHead(), changeArcTail(), and clearArcHeadAndTail().
|
static |
Add an arc to the linked list of arcs that are adjacent to a given node.
| 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, assert(), 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().
|
static |
Initializes the data structures of the arcs head and tail nodes.
| 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().
|
static |
Deinitializes the data structures of the arcs head and tail nodes.
| 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().
|
static |
Change the arc's head node to a new node.
| 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(), assert(), nodeIsRepresentative(), removeArcFromNodeArcList(), and TRUE.
Referenced by splitAndMergeRigid(), splitFirstLeaf(), and transformSingleRigid().
|
static |
Change the arc's head node to a new node.
| 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(), assert(), FALSE, nodeIsRepresentative(), and removeArcFromNodeArcList().
Referenced by splitAndMergeRigid(), splitFirstLeaf(), and transformSingleRigid().
|
static |
Returns the degree of the given node.
| dec | The network matrix decomposition |
| node | The given node |
Definition at line 1890 of file network.c.
References assert(), SCIP_NETMATDECDATA::nodes, SPQRNetworkDecompositionNode::numArcs, and SPQRnodeIsValid().
Referenced by rigidFindStarNodes(), and zeroOutColorsExceptNeighbourhood().
|
static |
Get the SPQR-type of the given member.
| dec | The network matrix decomposition |
| member | The given member |
Definition at line 1904 of file network.c.
References assert(), 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().
|
static |
Update the SPQR-type of the given member.
| 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 assert(), memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQRmemberIsValid(), and SPQRNetworkDecompositionMember::type.
Referenced by mergeGivenMemberIntoParent(), mergeSplitMemberIntoParent(), and splitFirstLeaf().
|
static |
Returns the virtual arc pointing to the parent member (in the arborescence) of the given member.
| dec | The network matrix decomposition |
| member | The given member |
Definition at line 1935 of file network.c.
References assert(), 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().
|
static |
Updates the parent information of a member that is identified with another another member.
| 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 assert(), findMemberNoCompression(), SPQRNetworkDecompositionMember::markerOfParent, SPQRNetworkDecompositionMember::markerToParent, memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionMember::parentMember, SPQR_INVALID_ARC, and SPQR_INVALID_MEMBER.
Referenced by mergeGivenMemberIntoParent(), and mergeSplitMemberIntoParent().
|
static |
Returns the virtual arc of the parent member that points to the given member.
| dec | The network matrix decomposition |
| member | The given member |
Definition at line 1970 of file network.c.
References assert(), 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().
|
static |
Returns the number of arcs in the member.
| dec | The network matrix decomposition |
| member | The member to get the number of arcs of |
Definition at line 1985 of file network.c.
References assert(), 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().
|
static |
Returns the number of nodes in complete network matrix decomposition.
| dec | The network matrix decomposition |
Definition at line 2000 of file network.c.
References assert(), and SCIP_NETMATDECDATA::numNodes.
Referenced by allocateRigidSearchMemory(), and rigidGetSplittableArticulationPointsOnPath().
|
static |
Returns the number of members in complete network matrix decomposition.
| dec | The network matrix decomposition |
Definition at line 2011 of file network.c.
References assert(), and SCIP_NETMATDECDATA::numMembers.
Referenced by constructReducedDecomposition(), constructRowReducedDecomposition(), and createPathArcs().
|
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.
| 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(), i, SCIP_NETMATDECDATA::numConnectedComponents, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SPQR_MEMBERTYPE_LOOP, and SPQR_MEMBERTYPE_PARALLEL.
Referenced by netrowaddAdd().
|
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.
| 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, i, SCIP_Bool, SCIP_CALL, SCIP_OKAY, and SPQR_MEMBERTYPE_PARALLEL.
Referenced by netrowaddAdd().
|
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.
| 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, i, SCIP_NETMATDECDATA::numConnectedComponents, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SPQR_MEMBERTYPE_LOOP, and SPQR_MEMBERTYPE_SERIES.
Referenced by netcoladdAdd().
|
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.
| 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, i, SCIP_Bool, SCIP_CALL, SCIP_OKAY, and SPQR_MEMBERTYPE_SERIES.
Referenced by netcoladdAdd().
|
static |
Remove an arc from the linked list containing all arcs of a single member.
| 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, assert(), findArcMemberNoCompression(), SPQRNetworkDecompositionMember::firstArc, memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionArcListNode::next, SPQRNetworkDecompositionMember::numArcs, SPQRNetworkDecompositionArcListNode::previous, and SPQR_INVALID_ARC.
Referenced by mergeGivenMemberIntoParent(), mergeSplitMemberIntoParent(), and moveArcToNewMember().
|
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
| 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(), assert(), findArcChildMemberNoCompression(), findArcMemberNoCompression(), markerOfParent(), markerToParent(), FindCycleCall::reversed, SCIP_Bool, SPQRelementIsRow(), and SPQRelementToRow().
Referenced by decompositionGetFundamentalCycleRows().
|
static |
Find the fundamental path of a cycle.
This is a slow method and only intended for debugging and testing.
| 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(), assert(), BMSallocBlockMemoryArray, BMSfreeBlockMemoryArray, SCIP_NETMATDECDATA::env, FALSE, findArcMemberNoCompression(), findEffectiveArcHeadNoCompression(), findEffectiveArcTailNoCompression(), getDecompositionColumnArc(), getFirstMemberArc(), getFirstNodeArc(), getMemberType(), getNextMemberArc(), getNextNodeArcNoCompression(), i, 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().
|
static |
Given a cycle (e.g. a matrix column), checks if the column's cycle matches the cycle in the network matrix decomposition.
| 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, i, NULL, SCIP_Bool, SCIPsortIntInt(), and TRUE.
Referenced by SCIPnetmatdecVerifyCycle().
|
static |
Returns the largest member id that is currently in the decomposition.
| dec | The network matrix decomposition |
Definition at line 2518 of file network.c.
References SCIP_NETMATDECDATA::numMembers.
Referenced by constructReducedDecomposition(), constructRowReducedDecomposition(), and netMatDecDataCreateDiGraph().
|
static |
Returns the largest arc id that is currently in the decomposition.
| dec | The network matrix decomposition |
Definition at line 2527 of file network.c.
References SCIP_NETMATDECDATA::numArcs.
Referenced by createPathArcs(), and createReducedDecompositionCutArcs().
|
static |
Returns the largest node id that is currently in the decomposition.
| dec | The network matrix decomposition |
Definition at line 2536 of file network.c.
References SCIP_NETMATDECDATA::numNodes.
Referenced by allocateRigidSearchMemory(), createPathArcs(), and netMatDecDataCreateDiGraph().
|
static |
Returns the number of SPQR trees in the SPQR forest, i.e. the number of connected components.
| dec | The network matrix decomposition |
Definition at line 2545 of file network.c.
References SCIP_NETMATDECDATA::numConnectedComponents.
Referenced by constructReducedDecomposition(), constructRowReducedDecomposition(), netcoladdAdd(), and netrowaddAdd().
|
static |
Creates a child marker in the network decomposition.
| 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_Bool, SCIP_CALL, and SCIP_OKAY.
Referenced by columnTransformSingleRigid(), createMarkerPair(), createMarkerPairWithReferences(), and rigidTransformArcIntoCycle().
|
static |
Creates a parent marker in the network decomposition.
| 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_Bool, SCIP_CALL, and SCIP_OKAY.
Referenced by columnTransformSingleRigid(), createMarkerPair(), createMarkerPairWithReferences(), and rigidTransformArcIntoCycle().
|
static |
Creates a child-marker parent-marker pair in the network decomposition.
| 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_Bool, SCIP_CALL, SCIP_OKAY, and SPQR_INVALID_ARC.
Referenced by splitParallel(), splitParallelRowAddition(), and splitSeries().
|
static |
Creates a child-marker parent-marker pair in the network decomposition, and returns the assigned arc id's.
| 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_Bool, SCIP_CALL, and SCIP_OKAY.
Referenced by netcoladdAdd(), netrowaddAdd(), splitParallelMerging(), splitSeriesMerging(), and splitSeriesMergingRowAddition().
|
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.
| 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, assert(), 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().
|
static |
Merges the arc linked list of two members into one linked list.
| 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, assert(), SPQRNetworkDecompositionMember::firstArc, getFirstMemberArc(), getPreviousMemberArc(), SCIP_NETMATDECDATA::members, SPQRNetworkDecompositionArcListNode::next, SPQRNetworkDecompositionMember::numArcs, SPQRNetworkDecompositionArcListNode::previous, SPQR_INVALID_ARC, and SPQRarcIsValid().
Referenced by mergeGivenMemberIntoParent(), and mergeSplitMemberIntoParent().
|
static |
Changes the type of a member from loop to series.
| dec | The network matrix decomposition |
| member | The member whose type is changed |
Definition at line 2711 of file network.c.
References assert(), 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().
|
static |
Changes the type of a member from loop to parallel.
| dec | The network matrix decomposition |
| member | The member whose type is changed |
Definition at line 2729 of file network.c.
References assert(), getMemberType(), getNumMemberArcs(), memberIsRepresentative(), SCIP_NETMATDECDATA::members, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_SERIES, SPQRmemberIsValid(), and SPQRNetworkDecompositionMember::type.
Referenced by netcoladdAdd(), and splitSeries().
|
static |
Checks if the network decomposition is minimal, i.e. if it does not contain two adjacent parallel or series members.
| dec | The network matrix decomposition |
Definition at line 2749 of file network.c.
References assert(), FALSE, findMemberParentNoCompression(), getMemberType(), memberIsRepresentative(), SCIP_NETMATDECDATA::numMembers, SCIP_Bool, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_UNASSIGNED, SPQRmemberIsValid(), and TRUE.
Referenced by SCIPnetmatdecIsMinimal().
|
static |
Decreases the count of the number of connected components in the network matrix decomposition.
| dec | The network matrix decomposition |
| by | The number of connected components to remove. |
Definition at line 2779 of file network.c.
References assert(), and SCIP_NETMATDECDATA::numConnectedComponents.
Referenced by netcoladdAdd(), and netrowaddAdd().
|
static |
Reorders the arborescence of the SPQR that contains a given member so that the given member becomes the new root of the arborescence.
| 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, assert(), 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().
|
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.
| 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, i, SCIP_NETMATDECDATA::rowArcs, SPQR_INVALID_ARC, and SPQRarcIsValid().
Referenced by SCIPnetmatdecRemoveComponent().
|
static |
| 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 assert(), clearArcHeadAndTail(), findEffectiveArcHead(), findEffectiveArcTail(), findMemberParentNoCompression(), markerOfParent(), markerToParent(), memberIsRepresentative(), mergeMemberArcList(), mergeMembers(), mergeNodeArcList(), mergeNodes(), removeArcFromMemberArcList(), SCIP_Bool, SCIP_OKAY, SPQR_MEMBERTYPE_RIGID, SPQRmemberIsValid(), updateMemberParentInformation(), and updateMemberType().
Referenced by transformAndMergeParallel(), transformAndMergeRigid(), and transformAndMergeSeries().
|
static |
| 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(), assert(), BMSallocBlockMemoryArray, BMSallocClearBlockMemoryArray, BMSfreeBlockMemoryArray, findArcChildMember(), findArcHead(), findArcMember(), findArcSign(), findArcTail(), findEffectiveArcHeadNoCompression(), findEffectiveArcTailNoCompression(), findMemberParent(), getFirstMemberArc(), getMemberType(), getNextMemberArc(), getNumMemberArcs(), i, 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().
|
static |
Returns true if the path arc is invalid.
| arc | The path arc to check |
Definition at line 3443 of file network.c.
References SCIP_Bool.
Referenced by determinePathRigidType(), and pathArcIsValid().
|
static |
Returns true if the path arc is valid.
| arc | The path arc to check |
Definition at line 3452 of file network.c.
References pathArcIsInvalid(), and SCIP_Bool.
Referenced by checkLeaf(), cleanupPreviousIteration(), columnTransformSingleParallel(), determinePathParallelType(), determinePathSeriesType(), determineRigidPath(), determineSingleComponentType(), determineSingleRigidType(), splitSeries(), and splitSeriesMerging().
|
static |
Returns true if the reduced member is invalid.
| id | The reduced member to check |
Definition at line 3484 of file network.c.
References SCIP_Bool.
Referenced by cleanUpMemberInformation(), cleanUpRowMemberInformation(), constructReducedDecomposition(), constructRowReducedDecomposition(), createReducedMembersToRoot(), createRowReducedMembersToRoot(), reducedMemberIsValid(), and splitSeriesMergingRowAddition().
|
static |
Returns true if the reduced member is valid.
| id | The reduced member to check |
Definition at line 3493 of file network.c.
References reducedMemberIsInvalid(), and SCIP_Bool.
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().
|
static |
Check if the path type is into.
| type | The path type to check |
Definition at line 3528 of file network.c.
References INTO_HEAD, INTO_TAIL, and SCIP_Bool.
Referenced by determinePathParallelType(), determinePathRigidType(), determinePathSeriesType(), transformAndMergeRigid(), and transformAndMergeSeries().
|
static |
Check if the path end node is the head or tail node of the corresponding arc.
| type | The path type to check |
Definition at line 3537 of file network.c.
References INTO_HEAD, OUT_HEAD, and SCIP_Bool.
Referenced by determinePathParallelType(), determinePathRigidType(), determinePathSeriesType(), and transformAndMergeSeries().
|
static |
Clean up internal temporary data structures that were used in the previous column iteration.
| 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, assert(), FALSE, SCIP_NETCOLADD::firstOverallPathArc, i, 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().
|
static |
Create a new network column addition datastructure.
| blkmem | Block memory |
| pcoladd | Out-pointer for the created network column addition datastructure |
Definition at line 3725 of file network.c.
References SCIP_NETCOLADD::arcInPath, SCIP_NETCOLADD::arcInPathReversed, assert(), BMSallocBlockMemory, SCIP_NETCOLADD::childrenStorage, SCIP_NETCOLADD::createReducedMembersCallStack, SCIP_NETCOLADD::decompositionArcReversed, SCIP_NETCOLADD::decompositionRowArcs, FALSE, SCIP_NETCOLADD::firstOverallPathArc, INVALID_PATH_ARC, 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::newColIndex, SCIP_NETCOLADD::newRowArcReversed, SCIP_NETCOLADD::newRowArcs, SCIP_NETCOLADD::nodeInPathDegree, SCIP_NETCOLADD::nodeOutPathDegree, NULL, SCIP_NETCOLADD::numChildrenStorage, SCIP_NETCOLADD::numDecompositionRowArcs, SCIP_NETCOLADD::numLeafMembers, SCIP_NETCOLADD::numMemberInformation, SCIP_NETCOLADD::numNewRowArcs, SCIP_NETCOLADD::numPathArcs, SCIP_NETCOLADD::numReducedComponents, SCIP_NETCOLADD::numReducedMembers, SCIP_NETCOLADD::pathArcs, SCIP_NETCOLADD::reducedComponents, SCIP_NETCOLADD::reducedMembers, SCIP_NETCOLADD::remainsNetwork, SCIP_ALLOC, SCIP_OKAY, and SPQR_INVALID_COL.
Referenced by SCIPnetmatdecTryAddCol().
|
static |
Free a network column addition datastructure
| 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, assert(), 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().
|
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.
| 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.
References assert(), SPQRColReducedMember::componentIndex, SCIP_NETCOLADD::createReducedMembersCallStack, SPQRColReducedMember::depth, findMemberParent(), SPQRColReducedMember::firstPathArc, INVALID_PATH_ARC, INVALID_REDUCED_MEMBER, CreateReducedMembersCallstack::member, SPQRColReducedMember::member, SCIP_NETCOLADD::memberInformation, memberIsRepresentative(), SCIP_NETCOLADD::memReducedComponents, SPQRColReducedMember::numChildren, SPQRColReducedMember::numPathArcs, SPQRColReducedComponent::numPathEndMembers, SPQRColReducedMember::numPropagatedChildren, SCIP_NETCOLADD::numReducedComponents, SCIP_NETCOLADD::numReducedMembers, SPQRColReducedMember::parent, SPQRColReducedComponent::pathEndMembers, SCIP_NETCOLADD::reducedComponents, MemberInfo::reducedMember, REDUCEDMEMBER_TYPE_UNASSIGNED, reducedMemberIsInvalid(), reducedMemberIsValid(), SCIP_NETCOLADD::reducedMembers, SPQRColReducedMember::rigidPathEnd, SPQRColReducedMember::rigidPathStart, SPQRColReducedComponent::root, MemberInfo::rootDepthMinimizer, SPQRColReducedMember::rootMember, SCIP_Bool, SPQR_INVALID_NODE, SPQRmemberIsValid(), TRUE, and SPQRColReducedMember::type.
Referenced by constructReducedDecomposition().
|
static |
Construct the reduced decomposition, which is the smallest subtree containing all members path arcs.
| dec | The network matrix decomposition |
| newCol | The network matrix column addition data structure |
Definition at line 3932 of file network.c.
References assert(), BMSreallocBlockMemoryArray, SCIP_NETCOLADD::childrenStorage, SCIP_NETCOLADD::createReducedMembersCallStack, createReducedMembersToRoot(), SCIP_NETCOLADD::decompositionRowArcs, SPQRColReducedMember::depth, SCIP_NETMATDECDATA::env, findArcMember(), findMemberParent(), SPQRColReducedMember::firstChild, getNumMembers(), i, 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().
|
static |
Clean up the memberinformation array at the end of an iteration.
| newCol | The network matrix column addition data structure |
Definition at line 4079 of file network.c.
References assert(), i, INVALID_REDUCED_MEMBER, SPQRColReducedMember::member, SCIP_NETCOLADD::memberInformation, SCIP_NETCOLADD::memMemberInformation, SCIP_NETCOLADD::numReducedMembers, MemberInfo::reducedMember, reducedMemberIsInvalid(), and SCIP_NETCOLADD::reducedMembers.
Referenced by netcoladdCheck().
|
static |
Marks the given arc as a path arc and adds it to the relevant data structures.
| 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, assert(), 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, SCIP_NETCOLADD::numPathArcs, SPQRColReducedMember::numPathArcs, SCIP_NETCOLADD::pathArcs, SCIP_NETCOLADD::reducedMembers, PathArcListNode::reversed, SCIP_Bool, SCIPswapInts(), SPQR_INVALID_NODE, SPQR_MEMBERTYPE_RIGID, SPQRnodeIsValid(), and TRUE.
Referenced by checkLeaf(), checkRigidLeaf(), and createPathArcs().
|
static |
Mark all the row indices of the new column as path arcs
| 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(), i, 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().
|
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.
| 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(), i, 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().
|
static |
Compute and store the leaf members of the reduced SPQR forest
| 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().
|
static |
Checks if the path arcs in the given rigid member form a path
| 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, assert(), 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().
|
static |
Determines the member's type for the case where the reduced tree consists of a single rigid member.
| 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 assert(), determineRigidPath(), SPQRColReducedMember::firstPathArc, pathArcIsValid(), REDUCEDMEMBER_TYPE_MERGED, REDUCEDMEMBER_TYPE_NOT_NETWORK, reducedMemberIsValid(), SCIP_NETCOLADD::reducedMembers, and SPQRColReducedMember::type.
Referenced by determineSingleComponentType().
|
static |
Determines the member's type for the case where the reduced tree consists of a single member.
| 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(), assert(), 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().
|
static |
Determines the path type of a series member.
| 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(), assert(), 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().
|
static |
Determines the path type of a parallel member.
| 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(), assert(), 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().
|
static |
Determines the path type of a rigid member.
| 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 assert(), 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().
|
static |
Determines the path type of a single member.
| 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().
|
static |
Determines the path types of all reduced members.
The reduced members themselves also form a path in the reduced decomposition.
| 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 assert(), SCIP_NETCOLADD::childrenStorage, determinePathMemberType(), FALSE, findMemberParent(), SPQRColReducedMember::firstChild, i, 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().
|
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.
| 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().
|
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.
| 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(), assert(), 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().
|
static |
Recursively removes leaf nodes whose path forms cycles with the virtual arc to its children.
| dec | The network matrix decomposition |
| newCol | The network matrix column addition data structure |
Definition at line 5277 of file network.c.
References arcIsTree(), assert(), checkLeaf(), SCIP_NETCOLADD::childrenStorage, SPQRColReducedMember::componentIndex, FALSE, SPQRColReducedMember::firstChild, i, 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().
|
static |
Determine the type of a single component.
| 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 assert(), determinePathTypes(), determineSingleComponentType(), SPQRColReducedComponent::numPathEndMembers, SPQRColReducedComponent::pathEndMembers, and SPQRColReducedComponent::root.
Referenced by netcoladdCheck().
|
static |
Checks if the given column can be added to the network matrix decomposition.
See header for more info.
| 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 assert(), cleanUpMemberInformation(), cleanupPreviousIteration(), computeLeafMembers(), constructReducedDecomposition(), createPathArcs(), determineComponentTypes(), i, netMatDecDataContainsColumn(), newColUpdateColInformation(), SCIP_NETCOLADD::numReducedComponents, propagateCycles(), SCIP_NETCOLADD::reducedComponents, SCIP_NETCOLADD::remainsNetwork, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, and TRUE.
Referenced by SCIPnetmatdecTryAddCol().
|
static |
Set the head node of the new column edge to be added.
| info | The new column information |
| node | The head node of the new column edge |
Definition at line 5502 of file network.c.
References assert(), NewColInformation::head, SPQRnodeIsInvalid(), and SPQRnodeIsValid().
Referenced by columnTransformSingleRigid(), transformAndMergeRigid(), transformAndMergeSeries(), and transformFirstPathMember().
|
static |
Set the tail node of the new column edge to be added.
| info | The new column information |
| node | The tail node of the new column edge |
Definition at line 5516 of file network.c.
References assert(), SPQRnodeIsInvalid(), SPQRnodeIsValid(), and NewColInformation::tail.
Referenced by columnTransformSingleRigid(), transformAndMergeRigid(), transformAndMergeSeries(), and transformFirstPathMember().
|
static |
Set whether the new column arc should be reversed.
| info | The new column information |
| reversed | Should the new column arc be reversed? |
Definition at line 5530 of file network.c.
References assert(), NewColInformation::reversed, and SCIP_Bool.
Referenced by columnTransformSingleParallel(), columnTransformSingleRigid(), splitSeries(), transformAndMergeRigid(), and transformAndMergeSeries().
|
static |
Set the member that contains the new column arc.
| info | The new column information |
| member | The decomposition member that contains the new column arc |
Definition at line 5542 of file network.c.
References assert(), and NewColInformation::member.
Referenced by columnTransformSingleParallel(), columnTransformSingleRigid(), splitSeries(), transformAndMergeRigid(), and transformAndMergeSeries().
|
static |
Set the representative arc of the new column arc.
| info | The new column information |
| representative | The representative arc of the new column arc |
Definition at line 5554 of file network.c.
References assert(), and NewColInformation::representative.
Referenced by columnTransformSingleRigid(), transformAndMergeRigid(), and transformAndMergeSeries().
|
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.
| 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(), assert(), createMarkerPair(), createMember(), FALSE, markerToParent(), moveArcToNewMember(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SPQR_MEMBERTYPE_PARALLEL, SPQRarcIsValid(), and SPQRmemberIsValid().
Referenced by transformAndMergeParallel().
|
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.
| 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(), assert(), 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().
|
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.
| 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(), assert(), 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().
|
static |
Transforms the first member in the path of members to reflect the new column update.
| 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(), assert(), b, c, 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().
|
static |
Transforms the next parallel member in the path of members and merge it into the current member.
| 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(), assert(), 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().
|
static |
Transforms the next series member in the path of members and merge it into the current member.
| 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(), assert(), b, c, 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().
|
static |
Transforms the next rigid member in the path of members and merge it into the current member.
| 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_Bool, SCIP_CALL, SCIP_OKAY, setTerminalHead(), setTerminalMember(), setTerminalRepresentative(), setTerminalReversed(), setTerminalTail(), SPQR_INVALID_MEMBER, and SPQRarcIsInvalid().
Referenced by transformAndMerge().
|
static |
Transforms the next member in the path of members and merge it into the current member.
| 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_Bool, 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().
|
static |
Transforms a single component when it contains multiple reduced members.
| 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().
|
static |
Transform a single parallel member to add the new column.
| 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 assert(), SPQRColReducedMember::firstPathArc, SPQRColReducedMember::numPathArcs, pathArcIsValid(), SPQRColReducedMember::pathBackwards, SCIP_NETCOLADD::reducedMembers, SCIP_OKAY, setTerminalMember(), and setTerminalReversed().
Referenced by transformComponent().
|
static |
Transform a single series member to add the new column.
| 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().
|
static |
Transform a single rigid member to add the new column.
| 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, assert(), 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, markerOfParent(), SPQRNetworkDecompositionMember::markerOfParent, markerToParent(), SPQRNetworkDecompositionMember::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().
|
static |
Transform a component to reflect the new column.
| 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 assert(), 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().
|
static |
Check if the submatrix stored remains a network matrix with the new column update.
| newCol | The network matrix column addition data structure |
Definition at line 6647 of file network.c.
References SCIP_NETCOLADD::remainsNetwork, and SCIP_Bool.
Referenced by netcoladdAdd(), and SCIPnetmatdecTryAddCol().
|
static |
Add the new column to the network decomposition as an arc.
Only use this function after SCIPnetcoladdCheck() has been called.
| 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(), assert(), changeLoopToParallel(), createColumnArc(), createConnectedSeries(), createMarkerPairWithReferences(), createStandaloneSeries(), decreaseNumConnectedComponents(), FALSE, findNode(), getFirstMemberArc(), getMemberType(), getNumMemberArcs(), NewColInformation::head, i, 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().
|
static |
Checks if the given cut arc is invalid (negative).
| arc | The cut arc to check |
Definition at line 6776 of file network.c.
References SCIP_Bool.
Referenced by cutArcIsValid().
|
static |
Checks if the given cut arc is valid (nonnegative).
| arc | The cut arc to check |
Definition at line 6784 of file network.c.
References cutArcIsInvalid(), and SCIP_Bool.
Referenced by cleanUpPreviousIteration(), determineParallelType(), determineSeriesType(), determineSingleParallelType(), determineSingleSeriesType(), determineSplitTypeFirstLeaf(), determineSplitTypeParallel(), determineSplitTypeSeries(), intersectionOfAllPaths(), rigidFindStarNodes(), splitAndMergeSeries(), splitFirstLeaf(), splitParallelMerging(), splitParallelRowAddition(), and transformSingleRigid().
|
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.
| 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(), i, 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().
|
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.
| 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.
References SPQRRowReducedMember::allHaveCommonNode, SPQRRowReducedMember::articulationArc, assert(), SPQRRowReducedMember::coloredNode, SCIP_NETROWADD::createReducedMembersCallstack, SPQRRowReducedMember::depth, FALSE, findMemberParent(), SPQRRowReducedMember::firstCutArc, INVALID_CUT_ARC, INVALID_REDUCED_MEMBER, CreateReducedMembersCallstack::member, SPQRRowReducedMember::member, SCIP_NETROWADD::memberInformation, memberIsRepresentative(), SCIP_NETROWADD::memReducedComponents, SPQRRowReducedMember::numChildren, SPQRRowReducedMember::numCutArcs, SPQRRowReducedMember::numPropagatedChildren, SCIP_NETROWADD::numReducedComponents, SCIP_NETROWADD::numReducedMembers, SPQRRowReducedMember::otherNode, SPQRRowReducedMember::otherNodeSplit, SPQRRowReducedMember::parent, SCIP_NETROWADD::reducedComponents, MemberInfo::reducedMember, reducedMemberIsInvalid(), reducedMemberIsValid(), SCIP_NETROWADD::reducedMembers, SPQRRowReducedComponent::root, MemberInfo::rootDepthMinimizer, SPQRRowReducedMember::rootMember, SCIP_Bool, SPQRRowReducedMember::splitArc, SPQRRowReducedMember::splitHead, SPQRRowReducedMember::splitNode, SPQR_INVALID_ARC, SPQR_INVALID_NODE, SPQRmemberIsValid(), TRUE, SPQRRowReducedMember::type, TYPE_UNDETERMINED, and SPQRRowReducedMember::willBeReversed.
Referenced by constructRowReducedDecomposition().
|
static |
Construct the reduced decomposition, which is the smallest subtree containing all members cut arcs.
| dec | The network matrix decomposition |
| newRow | The network matrix row addition datastructure |
Definition at line 7187 of file network.c.
References assert(), BMSreallocBlockMemoryArray, SCIP_NETROWADD::childrenStorage, SCIP_NETROWADD::createReducedMembersCallstack, createRowReducedMembersToRoot(), SCIP_NETROWADD::decompositionColumnArcs, SPQRRowReducedMember::depth, SCIP_NETMATDECDATA::env, findArcMember(), findMemberParent(), SPQRRowReducedMember::firstChild, getNumMembers(), i, 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().
|
static |
Marks an arc as 'cut'.
This implies that its cycle in the decomposition must be elongated.
| 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, assert(), 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, SCIP_NETROWADD::numCutArcs, SPQRRowReducedMember::numCutArcs, SCIP_NETROWADD::reducedMembers, SCIP_Bool, SCIPswapInts(), SPQR_INVALID_NODE, SPQR_MEMBERTYPE_RIGID, SPQRnodeIsValid(), and TRUE.
Referenced by createReducedDecompositionCutArcs(), determineParallelType(), determineRigidType(), and determineSeriesType().
|
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.
| dec | The network matrix decomposition |
| newRow | The network matrix row addition datastructure |
Definition at line 7388 of file network.c.
References assert(), BMSreallocBlockMemoryArray, createCutArc(), SCIP_NETROWADD::cutArcs, SCIP_NETROWADD::decompositionColumnArcReversed, SCIP_NETROWADD::decompositionColumnArcs, SCIP_NETMATDECDATA::env, FALSE, findArcMember(), SCIP_NETROWADD::firstOverallCutArc, i, 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().
|
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.
| 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().
|
static |
Preallocates memory arrays necessary for searching rigid components.
| dec | The network matrix decomposition |
| newRow | The network matrix row addition datastructure |
Definition at line 7469 of file network.c.
References SCIP_NETROWADD::artDFSData, SCIP_NETROWADD::articulationNodes, SCIP_NETROWADD::articulationNodeSearchInfo, BMSreallocBlockMemoryArray, SCIP_NETROWADD::colorDFSData, SCIP_NETROWADD::crossingPathCount, SCIP_NETMATDECDATA::env, getNumNodes(), i, SCIP_NETROWADD::intersectionDFSData, SCIP_NETROWADD::intersectionPathDepth, SCIP_NETROWADD::intersectionPathParent, largestNodeID(), MAX, SCIP_NETROWADD::memArtDFSData, SCIP_NETROWADD::memArticulationNodes, SCIP_NETROWADD::memColorDFSData, SCIP_NETROWADD::memCrossingPathCount, SCIP_NETROWADD::memIntersectionDFSData, SCIP_NETROWADD::memIntersectionPathDepth, SCIP_NETROWADD::memIntersectionPathParent, SCIP_NETROWADD::memNodeColors, SCIP_NETROWADD::memNodeSearchInfo, SCIP_NETROWADD::memTemporaryColorArray, SCIP_NETROWADD::nodeColors, SCIP_NETMATDECDATA::numArcs, SCIP_ALLOC, SCIP_OKAY, SPQR_INVALID_NODE, SCIP_NETROWADD::temporaryColorArray, and UNCOLORED.
Referenced by netrowaddCheck().
|
static |
Clears the colors for all nodes.
We do DFS in reverse (reverse exploration order), as zeroing out the entire array is more expensive.
| 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, assert(), SCIP_NETROWADD::colorDFSData, depth, findArcHead(), findArcTail(), getFirstNodeArc(), getNextNodeArc(), ColorDFSCallData::node, SCIP_NETROWADD::nodeColors, NULL, SPQRarcIsInvalid(), and UNCOLORED.
Referenced by cleanUpPreviousIteration(), rigidConnectedColoring(), and zeroOutColorsExceptNeighbourhood().
|
static |
Cleans up various arrays used in previous iterations.
This is cheaper than reallocating empty memory.
| dec | The network matrix decomposition |
| newRow | The network matrix row addition datastructure |
Definition at line 7634 of file network.c.
References CutArcListNode::arc, assert(), SPQRRowReducedMember::coloredNode, cutArcIsValid(), SCIP_NETROWADD::cutArcs, FALSE, SCIP_NETROWADD::firstOverallCutArc, i, 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().
|
static |
Finds all the star nodes, i.e. nodes that are adjacent to all cut arcs, in a rigid member.
| 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.
References SPQRRowReducedMember::allHaveCommonNode, CutArcListNode::arc, arcIsTree(), CutArcListNode::arcReversed, SPQRRowReducedMember::articulationArc, assert(), cutArcIsValid(), SCIP_NETROWADD::cutArcs, FALSE, findArcHead(), findArcSign(), findArcTail(), SPQRRowReducedMember::firstCutArc, getFirstNodeArc(), getNextNodeArc(), i, CutArcListNode::nextMember, nodeDegree(), SPQRRowReducedMember::numCutArcs, SPQRRowReducedMember::otherIsSource, SPQRRowReducedMember::otherNode, SCIP_NETROWADD::reducedMembers, SCIP_NETROWADD::remainsNetwork, ArcSign::reversed, SCIP_Bool, SPQRRowReducedMember::splitNode, SPQR_INVALID_NODE, SPQRnodeIsInvalid(), SPQRnodeIsValid(), TRUE, SPQRRowReducedMember::type, and TYPE_NOT_NETWORK.
Referenced by determineRigidType(), determineSingleRowRigidType(), determineSplitTypeFirstLeaf(), and determineSplitTypeRigid().
|
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.
| 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 assert(), findArcHead(), findArcTail(), getFirstNodeArc(), getNextNodeArc(), i, SCIP_NETROWADD::memTemporaryColorArray, SCIP_NETROWADD::nodeColors, nodeDegree(), SCIP_NETROWADD::temporaryColorArray, and zeroOutColors().
Referenced by rigidConnectedColoring().
|
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.
| 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(), assert(), 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().
|
static |
Add a node to array of articulation nodes.
| 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, assert(), i, and SCIP_NETROWADD::numArticulationNodes.
Referenced by articulationPoints().
|
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.
| 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, assert(), depth, 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().
|
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.
| 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, assert(), COLOR_SINK, COLOR_SOURCE, SCIP_NETROWADD::colorDFSData, depth, 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().
|
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.
| 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, assert(), 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(), SCIP_Bool, SPQR_INVALID_NODE, SPQRarcIsValid(), SPQRnodeIsValid(), TRUE, UNCOLORED, zeroOutColors(), and zeroOutColorsExceptNeighbourhood().
Referenced by rigidGetSplittableArticulationPointsOnPath().
|
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.
| 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(), assert(), COLOR_SOURCE, findArcHead(), findArcTail(), getFirstNodeArc(), getNextNodeArc(), SCIP_NETROWADD::isArcCut, SCIP_NETROWADD::nodeColors, SPQR_INVALID_ARC, SPQR_INVALID_NODE, and UNCOLORED.
Referenced by rigidGetSplittableArticulationPointsOnPath().
|
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.
| 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(), assert(), checkNeighbourColoringArticulationNode(), COLOR_SOURCE, SCIP_NETROWADD::crossingPathCount, ArticulationNodeInformation::discoveryTime, FALSE, findArcHead(), findArcTail(), getFirstNodeArc(), getNextNodeArc(), getNumNodes(), i, 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().
|
static |
Checks if a leaf parallel member can be propagated away from the reduced decomposition.
| 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, assert(), 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().
|
static |
Checks if a leaf series member can be propagated away from the reduced decomposition.
| 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, assert(), createCutArc(), cutArcIsValid(), SCIP_NETROWADD::cutArcs, SPQRRowReducedMember::firstCutArc, SPQRRowReducedMember::numCutArcs, SCIP_NETROWADD::reducedMembers, SPQRRowReducedMember::type, and TYPE_PROPAGATED.
Referenced by determineType().
|
static |
Checks if a leaf rigid member can be propagated away from the reduced decomposition.
| 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, assert(), 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().
|
static |
Checks if a leaf member can be propagated away from the reduced decomposition.
| 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 assert(), 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().
|
static |
Propagates away all leaf members that are propagatable to shrink the reduced decomposition.
| dec | The network matrix decomposition |
| newRow | The network matrix row addition data structure |
Definition at line 8576 of file network.c.
References arcIsTree(), assert(), SCIP_NETROWADD::childrenStorage, determineType(), SPQRRowReducedMember::firstChild, i, 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().
|
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.
| 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, i, 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().
|
static |
Allocates memory for various procedures that need to do tree-search for rigid members (e.g. DFS or BFS).
| 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().
|
static |
Determine the type of a rigid member when it is the only member in the reduced decomposition.
| 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 assert(), 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().
|
static |
Determine the type of a parallel member when it is the only member in the reduced decomposition.
| 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, assert(), 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().
|
static |
Determine the type of a series member when it is the only member in the reduced decomposition.
| 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 assert(), cutArcIsValid(), SPQRRowReducedMember::firstCutArc, SPQRRowReducedMember::numCutArcs, SCIP_NETROWADD::reducedMembers, SPQRRowReducedMember::type, and TYPE_MERGED.
Referenced by determineMergeableTypes().
|
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.
| 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, assert(), 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().
|
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.
| 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.
References CutArcListNode::arc, arcIsReversedNonRigid(), CutArcListNode::arcReversed, assert(), cutArcIsValid(), SCIP_NETROWADD::cutArcs, determineAndColorSplitNode(), FALSE, findArcHead(), findArcSign(), findArcTail(), SPQRRowReducedMember::firstCutArc, getMemberType(), markerToParent(), SPQRRowReducedMember::member, CutArcListNode::nextMember, SPQRRowReducedMember::numCutArcs, SPQRRowReducedMember::otherIsSource, SPQRRowReducedMember::otherNode, SCIP_NETROWADD::reducedMembers, SCIP_NETROWADD::remainsNetwork, rigidFindStarNodes(), rigidGetSplittableArticulationPointsOnPath(), SCIP_Bool, SPQRRowReducedMember::splitArc, SPQRRowReducedMember::splitHead, SPQRRowReducedMember::splitNode, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_RIGID, SPQRnodeIsInvalid(), SPQRnodeIsValid(), TRUE, SPQRRowReducedMember::type, TYPE_MERGED, TYPE_NOT_NETWORK, and SPQRRowReducedMember::willBeReversed.
Referenced by determineMergeableTypes().
|
static |
Get the split orientation for a given rigid member and marked arc.
| 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 assert(), COLOR_SINK, COLOR_SOURCE, findArcHead(), findArcMemberNoCompression(), findArcSign(), findArcTail(), findEffectiveArcHead(), findEffectiveArcTailNoCompression(), SplitOrientation::headSplit, SPQRRowReducedMember::member, SCIP_NETROWADD::nodeColors, SPQRRowReducedMember::numCutArcs, SplitOrientation::otherIsSource, SPQRRowReducedMember::otherIsSource, SCIP_NETROWADD::reducedMembers, SPQRRowReducedMember::splitNode, SPQRnodeIsValid(), and SPQRRowReducedMember::willBeReversed.
Referenced by getRelativeOrientation().
|
static |
Get the split orientation for a given parallel member and marked arc.
| 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(), assert(), findArcMemberNoCompression(), SplitOrientation::headSplit, SPQRRowReducedMember::member, SplitOrientation::otherIsSource, SPQRRowReducedMember::otherIsSource, SCIP_NETROWADD::reducedMembers, SPQRRowReducedMember::splitArc, SPQRRowReducedMember::splitHead, and SPQRarcIsValid().
Referenced by getRelativeOrientation().
|
static |
Get the split orientation for a given series member and marked arc.
| 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(), assert(), findArcMemberNoCompression(), SplitOrientation::headSplit, SPQRRowReducedMember::member, SplitOrientation::otherIsSource, SPQRRowReducedMember::otherIsSource, SCIP_NETROWADD::reducedMembers, SPQRRowReducedMember::splitArc, SPQRRowReducedMember::splitHead, and SPQRarcIsValid().
Referenced by getRelativeOrientation().
|
static |
Get the split orientation for a given member and marked arc.
| 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().
|
static |
Determine the split type of a series node when the SPQR tree is not a singular member.
| 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.
References CutArcListNode::arc, arcIsReversedNonRigid(), CutArcListNode::arcReversed, assert(), cutArcIsValid(), SCIP_NETROWADD::cutArcs, FALSE, SPQRRowReducedMember::firstCutArc, SplitOrientation::headSplit, SPQRRowReducedMember::numChildren, SPQRRowReducedMember::numPropagatedChildren, SplitOrientation::otherIsSource, SPQRRowReducedMember::otherIsSource, SPQRRowReducedMember::parent, reducedMemberIsValid(), SCIP_NETROWADD::reducedMembers, SCIP_NETROWADD::remainsNetwork, SCIP_Bool, SPQRRowReducedMember::splitArc, SPQRRowReducedMember::splitHead, SPQRRowReducedMember::type, TYPE_MERGED, TYPE_NOT_NETWORK, and TYPE_PROPAGATED.
Referenced by determineSplitTypeNext().
|
static |
Determine the split type of a parallel node when the SPQR tree is not a singular member.
| 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, SplitOrientation::otherIsSource, SPQRRowReducedMember::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().
|
static |
Determine the split type of a rigid node when the SPQR tree is not a singular member.
| 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 assert(), COLOR_SINK, COLOR_SOURCE, determineAndColorSplitNode(), FALSE, findArcHead(), findArcSign(), findArcTail(), Nodes::first, getMemberType(), SplitOrientation::headSplit, SCIP_NETROWADD::nodeColors, SPQRRowReducedMember::numCutArcs, SplitOrientation::otherIsSource, SPQRRowReducedMember::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().
|
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.
| 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 assert(), determineSplitTypeParallel(), determineSplitTypeRigid(), determineSplitTypeSeries(), FALSE, getMemberType(), getRelativeOrientation(), markerOfParent(), markerToParent(), SPQRRowReducedMember::member, SCIP_NETROWADD::reducedMembers, SCIP_NETROWADD::remainsNetwork, SCIP_Bool, SCIPABORT, SPQR_MEMBERTYPE_LOOP, SPQR_MEMBERTYPE_PARALLEL, SPQR_MEMBERTYPE_RIGID, SPQR_MEMBERTYPE_SERIES, and SPQR_MEMBERTYPE_UNASSIGNED.
Referenced by determineMergeableTypes().
|
static |
For the given root reduced member of a component, determine if the component is updateable/transformable.
| 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 assert(), SCIP_NETROWADD::childrenStorage, MergeTreeCallData::currentChild, depth, determineSingleParallelType(), determineSingleRowRigidType(), determineSingleSeriesType(), determineSplitTypeFirstLeaf(), determineSplitTypeNext(), FALSE, SPQRRowReducedMember::firstChild, getMemberType(), i, 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().
|
static |
Empty the new member information array.
| newRow | The network matrix row addition data structure |
Definition at line 9591 of file network.c.
References assert(), i, INVALID_REDUCED_MEMBER, SPQRRowReducedMember::member, SCIP_NETROWADD::memberInformation, SCIP_NETROWADD::memMemberInformation, SCIP_NETROWADD::numReducedMembers, MemberInfo::reducedMember, reducedMemberIsInvalid(), and SCIP_NETROWADD::reducedMembers.
Referenced by netrowaddCheck().
|
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.
| 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, assert(), SPQRNetworkDecompositionArc::childMember, createChildMarker(), createColumnArc(), createMember(), createParentMarker(), createRowArc(), SPQRNetworkDecompositionArc::element, FALSE, findArcChildMember(), findMemberParent(), getMemberType(), MARKER_COLUMN_ELEMENT, MARKER_ROW_ELEMENT, markerOfParent(), SPQRNetworkDecompositionMember::markerOfParent, markerToParent(), SPQRNetworkDecompositionMember::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().
|
static |
Updates a single rigid member to reflect the new row.
| 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, assert(), 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().
|
static |
Splits a single parallel member into two adjacent ones, where the cut arcs and non-cut arcs get their own member.
| 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, assert(), 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().
|
static |
Updates a single rigid member to reflect the new row.
| 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().
|
static |
Split a series member into multiple series members for merging.
| 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(), assert(), SCIP_NETROWADD::childrenStorage, createMarkerPairWithReferences(), createMember(), FALSE, findMember(), SPQRRowReducedMember::firstChild, getFirstMemberArc(), getNextMemberArc(), getNumMemberArcs(), i, 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().
|
static |
Split a parallel member into multiple parallel members for merging.
| 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.
References CutArcListNode::arc, arcIsTree(), assert(), SCIP_NETROWADD::childrenStorage, createMarkerPairWithReferences(), createMember(), cutArcIsValid(), SCIP_NETROWADD::cutArcs, FALSE, findMember(), SPQRRowReducedMember::firstChild, SPQRRowReducedMember::firstCutArc, getNumMemberArcs(), i, markerOfParent(), markerToParent(), SPQRRowReducedMember::member, moveArcToNewMember(), CutArcListNode::nextMember, SPQRRowReducedMember::numChildren, SPQRRowReducedMember::numCutArcs, SPQRRowReducedMember::numPropagatedChildren, SPQRRowReducedMember::parent, reducedMemberIsValid(), SCIP_NETROWADD::reducedMembers, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SPQR_INVALID_ARC, SPQR_INVALID_MEMBER, SPQR_MEMBERTYPE_PARALLEL, SPQRarcIsValid(), TRUE, SPQRRowReducedMember::type, TYPE_MERGED, and TYPE_PROPAGATED.
Referenced by splitAndMergeParallel(), and splitFirstLeaf().
|
static |
Update the first leaf to reflect the addition of the new row
| 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(), assert(), changeArcHead(), changeArcTail(), COLOR_SOURCE, createNode(), cutArcIsValid(), FALSE, findArcHead(), findArcMemberNoCompression(), findArcSign(), findArcTail(), SPQRRowReducedMember::firstCutArc, getFirstMemberArc(), getFirstNodeArc(), getMemberType(), getNextMemberArc(), getNextNodeArc(), NewRowInformation::head, SCIP_NETROWADD::isArcCut, NewRowInformation::member, SPQRRowReducedMember::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().
|
static |
Merge an (updated) member into its parent.
This function is mainly there to prevent duplication.
| 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 assert(), clearArcHeadAndTail(), findEffectiveArcHead(), findEffectiveArcTail(), findMemberParentNoCompression(), markerOfParent(), markerToParent(), memberIsRepresentative(), mergeMemberArcList(), mergeMembers(), mergeNodeArcList(), mergeNodes(), SCIP_NETROWADD::nodeColors, removeArcFromMemberArcList(), SCIP_Bool, SCIP_OKAY, SPQR_MEMBERTYPE_RIGID, SPQRmemberIsValid(), UNCOLORED, updateMemberParentInformation(), and updateMemberType().
Referenced by splitAndMergeParallel(), splitAndMergeRigid(), and splitAndMergeSeries().
|
static |
Update a series member to reflect the addition of the new row, and merge it into the previous members that were updated.
| 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(), assert(), b, c, createNode(), cutArcIsValid(), FALSE, findEffectiveArcHead(), findEffectiveArcTail(), SPQRRowReducedMember::firstCutArc, getFirstMemberArc(), getNextMemberArc(), getNumMemberArcs(), NewRowInformation::head, markerOfParent(), markerToParent(), NewRowInformation::member, SPQRRowReducedMember::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().
|
static |
Update a parallel member to reflect the addition of the new row, and merge it into the previous members that were updated.
| 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(), assert(), createNode(), FALSE, findArcMemberNoCompression(), findEffectiveArcHead(), findEffectiveArcTail(), getFirstMemberArc(), getNextMemberArc(), NewRowInformation::head, markerOfParent(), markerToParent(), NewRowInformation::member, SPQRRowReducedMember::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().
|
static |
Update a rigid member to reflect the addition of the new row, and merge it into the previous members that were updated.
| 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 assert(), 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().
|
static |
Update a member to reflect the addition of the new row, and merge it into the previous members that were updated.
| 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_Bool, 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().
|
static |
Update an SPQR tree with multiple members to reflect the addition of a new row, merging it into one big rigid node.
| 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 assert(), SCIP_NETROWADD::childrenStorage, MergeTreeCallData::currentChild, depth, FALSE, SPQRRowReducedMember::firstChild, i, 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().
|
static |
Update an SPQR tree (a single component of the SPQR forest) to reflect addition of a new row.
| 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, assert(), changeLoopToSeries(), SCIP_NETROWADD::cutArcs, SPQRRowReducedMember::firstCutArc, getMemberType(), getNumMemberArcs(), NewRowInformation::member, SPQRRowReducedMember::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().
|
static |
Create the network row addition data structure.
| blkmem | Block memory |
| prowadd | Pointer to store the new row addition struct at |
Definition at line 11256 of file network.c.
References SCIP_NETROWADD::artDFSData, SCIP_NETROWADD::articulationNodes, SCIP_NETROWADD::articulationNodeSearchInfo, assert(), BMSallocBlockMemory, SCIP_NETROWADD::childrenStorage, SCIP_NETROWADD::colorDFSData, SCIP_NETROWADD::createReducedMembersCallstack, SCIP_NETROWADD::crossingPathCount, SCIP_NETROWADD::cutArcs, SCIP_NETROWADD::decompositionColumnArcReversed, SCIP_NETROWADD::decompositionColumnArcs, SCIP_NETROWADD::firstOverallCutArc, SCIP_NETROWADD::intersectionDFSData, SCIP_NETROWADD::intersectionPathDepth, SCIP_NETROWADD::intersectionPathParent, INVALID_CUT_ARC, SCIP_NETROWADD::isArcCut, SCIP_NETROWADD::isArcCutReversed, SCIP_NETROWADD::leafMembers, SCIP_NETROWADD::memArtDFSData, SCIP_NETROWADD::memArticulationNodes, SCIP_NETROWADD::memberInformation, SCIP_NETROWADD::memChildrenStorage, SCIP_NETROWADD::memColorDFSData, SCIP_NETROWADD::memColumnArcs, SCIP_NETROWADD::memCreateReducedMembersCallstack, SCIP_NETROWADD::memCrossingPathCount, SCIP_NETROWADD::memCutArcs, SCIP_NETROWADD::memDecompositionColumnArcs, SCIP_NETROWADD::memIntersectionDFSData, SCIP_NETROWADD::memIntersectionPathDepth, SCIP_NETROWADD::memIntersectionPathParent, SCIP_NETROWADD::memIsArcCut, SCIP_NETROWADD::memLeafMembers, SCIP_NETROWADD::memMemberInformation, SCIP_NETROWADD::memMergeTreeCallData, SCIP_NETROWADD::memNodeColors, SCIP_NETROWADD::memNodeSearchInfo, SCIP_NETROWADD::memReducedComponents, SCIP_NETROWADD::memReducedMembers, SCIP_NETROWADD::memTemporaryColorArray, SCIP_NETROWADD::mergeTreeCallData, SCIP_NETROWADD::newColumnArcs, SCIP_NETROWADD::newColumnReversed, SCIP_NETROWADD::newRowIndex, SCIP_NETROWADD::nodeColors, NULL, SCIP_NETROWADD::numArticulationNodes, SCIP_NETROWADD::numChildrenStorage, SCIP_NETROWADD::numColumnArcs, SCIP_NETROWADD::numCutArcs, SCIP_NETROWADD::numDecompositionColumnArcs, SCIP_NETROWADD::numLeafMembers, SCIP_NETROWADD::numMemberInformation, SCIP_NETROWADD::numReducedComponents, SCIP_NETROWADD::numReducedMembers, SCIP_NETROWADD::reducedComponents, SCIP_NETROWADD::reducedMembers, SCIP_NETROWADD::remainsNetwork, SCIP_ALLOC, SCIP_OKAY, SPQR_INVALID_ROW, SCIP_NETROWADD::temporaryColorArray, and TRUE.
Referenced by SCIPnetmatdecTryAddRow().
|
static |
Frees the network row addition data structure.
| blkmem | Block memory |
| prowadd | Pointer to row addition struct to be freed |
Definition at line 11350 of file network.c.
References SCIP_NETROWADD::artDFSData, SCIP_NETROWADD::articulationNodes, SCIP_NETROWADD::articulationNodeSearchInfo, assert(), BMSfreeBlockMemory, BMSfreeBlockMemoryArray, SCIP_NETROWADD::childrenStorage, SCIP_NETROWADD::colorDFSData, SCIP_NETROWADD::createReducedMembersCallstack, SCIP_NETROWADD::crossingPathCount, SCIP_NETROWADD::cutArcs, SCIP_NETROWADD::decompositionColumnArcReversed, SCIP_NETROWADD::decompositionColumnArcs, SCIP_NETROWADD::intersectionDFSData, SCIP_NETROWADD::intersectionPathDepth, SCIP_NETROWADD::intersectionPathParent, SCIP_NETROWADD::isArcCut, SCIP_NETROWADD::isArcCutReversed, SCIP_NETROWADD::leafMembers, SCIP_NETROWADD::memArtDFSData, SCIP_NETROWADD::memArticulationNodes, SCIP_NETROWADD::memberInformation, SCIP_NETROWADD::memChildrenStorage, SCIP_NETROWADD::memColorDFSData, SCIP_NETROWADD::memColumnArcs, SCIP_NETROWADD::memCreateReducedMembersCallstack, SCIP_NETROWADD::memCrossingPathCount, SCIP_NETROWADD::memCutArcs, SCIP_NETROWADD::memDecompositionColumnArcs, SCIP_NETROWADD::memIntersectionDFSData, SCIP_NETROWADD::memIntersectionPathDepth, SCIP_NETROWADD::memIntersectionPathParent, SCIP_NETROWADD::memIsArcCut, SCIP_NETROWADD::memLeafMembers, SCIP_NETROWADD::memMemberInformation, SCIP_NETROWADD::memMergeTreeCallData, SCIP_NETROWADD::memNodeColors, SCIP_NETROWADD::memNodeSearchInfo, SCIP_NETROWADD::memReducedComponents, SCIP_NETROWADD::memReducedMembers, SCIP_NETROWADD::memTemporaryColorArray, SCIP_NETROWADD::mergeTreeCallData, SCIP_NETROWADD::newColumnArcs, SCIP_NETROWADD::newColumnReversed, SCIP_NETROWADD::nodeColors, SCIP_NETROWADD::reducedComponents, SCIP_NETROWADD::reducedMembers, and SCIP_NETROWADD::temporaryColorArray.
Referenced by SCIPnetmatdecFree().
|
static |
Checks if the given row can be added to the network decomposition.
| 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(), assert(), cleanUpPreviousIteration(), cleanUpRowMemberInformation(), constructRowReducedDecomposition(), createReducedDecompositionCutArcs(), determineLeafReducedMembers(), determineMergeableTypes(), i, 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().
|
static |
Adds the last checked row to the network decomposition.
| 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(), assert(), changeLoopToSeries(), createConnectedParallel(), createMarkerPairWithReferences(), createRowArc(), createStandaloneParallel(), decreaseNumConnectedComponents(), FALSE, findNode(), getFirstMemberArc(), getMemberType(), getNumMemberArcs(), NewRowInformation::head, i, 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().
|
static |
Returns whether the last checked row can be added to the network decomposition.
| rowadd | The network matrix row addition data structure |
Definition at line 11551 of file network.c.
References SCIP_NETROWADD::remainsNetwork, and SCIP_Bool.
Referenced by SCIPnetmatdecTryAddRow().
1.16.1