network.c
Go to the documentation of this file.
30 * Detecting if a matrix is a network matrix can be quite complex. Below is an introductory text, which may help with
38 * The main difficulty with detecting network matrices is that there may exist many pairs of a graph and a spanning tree
39 * that realize a matrix. The ambiguity of these graphs may be characterized in terms of \f$k\f$-separations on the
40 * graph associated to the network matrix. An edge partition \f$(E_1,E_2)\f$ is considered a \f$k\f$-separation if
41 * \f$|E_i|\geq k \f$ holds for \f$i\in\{1,2\}\f$. The ambiguity of network matrices is completely given by all
42 * the 1-separations and 2-separations of the associated graph(s). In particular, if the graph realizing a
45 * A 1-separation given by edge sets \f$(E_1,E_2)\f$, which is given by a singular node that is referred to as an
46 * articulation node, implies that no column of the network matrix contains edges in both \f$E_1\f$ and \f$E_2\f$.
47 * Remember that each edge in a realizing graph is associated with a row or column of the network matrix. Then, we have
48 * a 1-separation exactly when the network matrix contains two (or more) disconnected blocks, where the rows and columns
49 * of each block are contained in either \f$E_1\f$ or \f$E_2\f$. To obtain a graph realizing our network matrix, we can
51 * Thus, we store the graphs corresponding to the connected blocks of the network matrix separately.
54 * If a graph \f$G\f$ realizing the network matrix has a 2-separation \f$(E_1,E_2)\f$ at vertices u and v, then we can
55 * obtain another graph representing the network matrix, by inverting the direction of all edges in \f$E_2\f$ and
57 * adding a virtual edge \f$e'=\{u,v\}\f$ to both E_1 and E_2. In the trivial realization, we simply map the head of
58 * \f$e'\f$ in \f$E_1\f$ to the head of \f$e'\f$ in \f$E_2\f$ and remove \f$e'\f$ from both graphs. In the second
59 * realization we do the same thing, but first invert all the edges in \f$E_2\f$, including \f$e'\f$.
60 * An SPQR tree \f$\mathcal{T}=(\mathcal{V},\mathcal{E})\f$ is a tree data structure that represents the structure of
61 * all 2-separations in a 2-connected graph. Each member \f$\nu\in\mathcal{V}\f$ has an associated skeleton graph that
63 * - (S) The member's skeleton graph is a cycle with at least 3 edges (also referred to as series or polygon)
64 * - (P) The member's skeleton graph consists of at least 3 parallel edges and 2 nodes (also referred to as bond)
65 * - (Q) The member's skeleton graph consists of at most 2 edges connecting two nodes (also referred to as loop)
68 * An SPQR tree is considered minimal if it has no P-P or S-S connections. Each connected matrix has a unique minimal
69 * SPQR tree. Each edge \f$\{\nu,\mu\}\in\mathcal{E}\f$ defines a 2-separation of the underlying graph. In particular,
70 * each edge has one virtual edge in the member graph that it connects to the other member graph in the edge.
72 * We can obtain a realization of the graph underlying the network matrix by doing the following operations:
74 * 2. For each edge in \f$\mathcal{E}\f$, pick one of the two orientations of the virtual edges and merge the adjacent
77 * In this way, all the graphs given by the network matrix are represented. In order to efficiently perform the merge
78 * of two member graphs, the member and node labels are given by union-find datastructures. Additionally, we also
79 * introduce a signed-union-find datastructure on the arcs of the graphs, so that we can efficiently invert the arcs
81 * The 1-separations can be handled by storing an SPQR forest, with a (minimal) SPQR tree for every connected block
84 * For adding a column to the network matrix, one can show that one can add a column only if the nonzeros of the column
85 * form a path with the correct signs in some graph represented by the network matrix. We solve the problem for each
86 * graph represented by the network matrix simultaneously by decomposing over the SPQR tree. First, we compute the path
87 * in each member. Then, we attempt to combine the paths by orienting the 2-separations so that the different member
90 * An important step is 'propagation'; when we are in a leaf node of the sub-SPQR tree containing path edges and the
91 * path in our leaf node forms a cycle with the virtual arc e connecting to the rest of the sub-tree, then we can
93 * After performing all such propagations, the sub-SPQR tree should form a path. Then, we merge these members into one,
94 * 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.
95 * Finally, we can easily join the paths of multiple SPQR trees using a series node to obtain the final path.
97 * The ideas for the row-wise algorithm have many parallels with the column-wise algorithm. One can add a row to a
98 * network matrix if and only if a node is 'splittable' with respect to a certain auxiliary graph formed by the nonzero
99 * columns indices of the row, for a graph represented by the network matrix. In particular, this auxiliary graph must
100 * be a directed bipartite graph; then, the arcs incident to the given node can be reassigned to two new nodes, so that
101 * the paths of the columns corresponding to the nonzeros of the row can be elongated to contain the new row, which is
103 * Similarly to the column-case, splittability of each graph represented by the network matrix can be computed at once
105 * Similarly to the column algorithm, we can propagate; If a member is a leaf of the SPQR tree and both nodes of the
106 * 2-separation connecting it to the rest of graph are splittable, then we can remove the leaf from the reduced
108 * Finally, we are left with some minimal subtree with splittable vertices for each member graph. If we can merge all
109 * splittable vertices of the member graphs in the subtree into a single splittable vertex, then we perform this merge,
113 * 1. Quite a few algorithms used for network matrix detection are recursive in nature. However, recursive calls can
114 * cause stack overflows, particularly with large graphs. Quite frequently in the code, we need to allocate the
115 * call-data of these algorithms on the heap, instead, and use while loops to simulate the recursion.
117 * 2. In order to make the code fast in practice, a lot of emphasis is put on reusing allocated memory and avoiding
118 * allocations. In particular for the column-wise algorithm, even allocating and zeroing an array of size m+n for an
121 * 3. The graphs of the S, P and Q members do not need to be stored explicitly, as they always have the same structure.
125 /* TODO: fix tracking connectivity more cleanly, should not be left up to the algorithms ideally
254 * If two members are adjacent in the SPQR tree, the two corresponding subgraphs are connected by a 2-separation in any
256 * For members, we reserve all negative values as invalid. We use these negative values in union-find datastructure,
282 * Similar to spqr_member, we reserve all negative values as invalid and use these in union-find.
308 * Similar to spqr_node and spqr_member, we reserve all negative values as invalid and use these in some union-find.
309 * However, in contrast to spqr_node and spqr_member, the union-find data structure does not represent the arcs,
336 SPQR_MEMBERTYPE_RIGID = 0, /**< The member's skeleton is 3-connected and has at least 4 edges */
337 SPQR_MEMBERTYPE_PARALLEL = 1, /**< The member's skeleton consists of 2 nodes with at least 3 edges */
339 SPQR_MEMBERTYPE_LOOP = 3, /**< The member's skeleton consists of 2 nodes connected by 1 or 2 edges */
340 SPQR_MEMBERTYPE_UNASSIGNED = 4 /**< To indicate that the member is not a representative member anymore */
367 SPQRNetworkDecompositionArcListNode headArcListNode; /**< Linked-list node for iterating over the head's arcs */
368 SPQRNetworkDecompositionArcListNode tailArcListNode; /**< Linked-list node for iterating over the tail's arcs */
369 SPQRNetworkDecompositionArcListNode arcListNode; /**< Linked-list node for iterating over the member's arcs */
377 * For non-rigid members every arc is it's own representative, and the direction is simply given by the boolean.
413 SPQRNetworkDecompositionArc* arcs; /**< Array of arcs of the SPQR forest, indexed by spqr_arc */
418 SPQRNetworkDecompositionMember* members; /**< Array of members of the SPQR forest. Indexed by spqr_member */
422 SPQRNetworkDecompositionNode* nodes; /**< Array of nodes of the SPQR forest. Indexed by spqr_node */
488/** Find the node its representative node in the union-find data structure, without compressing the union-find tree.
555/** Find the arc's head node in the union find data structure of the nodes, without compressing the union-find tree.
573/** Find the arc's tail node in the union find data structure of the nodes, without compressing the union-find tree.
608/** Given the current arc adjacent to this node, find the next arc in the cyclic linked list of adjacent arcs to the
611 * This function does not compress the union-find tree, and should only be used in debugging or asserts.
637/** Given the current arc adjacent to this node, find the next arc in the cyclic linked list of adjacent arcs to the
665/** Given the current arc adjacent to this node, find the previous arc in the cyclic linked list of adjacent arcs
693/** Update the cyclic node-arc incidence data structure to move all arcs adjacent to one node to another node.
695 * We typically call this when two nodes are identified with one another, and we need to merge their adjacent arcs.
785 * In particular, whether an arc is reversed or not is determined by the sign of the path in the signed union-find
786 * data structure for arcs, which can be computed by multiplying the signs of the individual edges (xor over bools).
822 //We want the new root to be the one with 'largest' rank, so smallest number. If they are equal, we decrement.
887/** Find the member's representative member in the union-find data structure, without compressing the union-find tree.
934 // We want the new root to be the one with 'largest' rank, so smallest number. If they are equal, we decrement.
965/** Finds the member in which the arc is located, without compressing the member union-find tree */
1008 * This version does not perform compression of the union-find tree, and should only be used in debug or asserts.
1025 spqr_member parent_representative = findMemberNoCompression(dec, dec->members[member].parentMember);
1047 * This version does not compress the union-find tree and should only be used for debugging and asserts.
1077/** Check whether the given arc is a tree arc or not, i.e. whether it belongs to a (virtual) row or column or not */
1100/** Check if an arc is a representative in the signed union-find data structure for arc directions.
1119/** Find an arcs representative and its direction in the signed union-find data structure for arcs. */
1167/** Find an arcs representative and its direction in the signed union-find data structure for arcs.
1169 * This version does not compress the union-find tree and should only be used in debug and asserts.
1199/** Finds the arcs head, taking into account whether it is reversed by the signed union-find data structure. */
1217/** Finds the arcs tail, taking into account whether it is reversed by the signed union-find data structure. */
1235/** Finds the arcs head, taking into account whether it is reversed by the signed union-find data structure.
1237 * This version does not compress the union-find tree and should only be used in debug and asserts.
1257/** Finds the arcs tail, taking into account whether it is reversed by the signed union-find data structure.
1259 * This version does not compress the union-find tree and should only be used in debug and asserts.
1280 * If reflectRelative is set to true then all arcs of the represented by the second arc are reversed
1300 //We want the new root to be the one with 'largest' rank, so smallest number. If they are equal, we decrement.
1313 //These boolean formula's cover all 16 possible cases, such that the relative orientation of the first is not changed
1326 * For non-rigid members, we do not use the union-find datastructure, as we can get away without it.
1368/** Check whether the network matrix decomposition contains an edge for the given column index. */
1544/** Given the current arc, get the next arc of the linked list of arcs that are in the same member. */
1559/** Given the current arc, get the previous arc of the linked list of arcs that are in the same member. */
1654/** Create a new arc in the network matrix decomposition that is associated to the given row. */
1672/** Create a new arc in the network matrix decomposition that is associated to the given column. */
1753 SPQRNetworkDecompositionArcListNode* arcListNode = nodeIsHead ? &dec->arcs[arc].headArcListNode
1795 SPQRNetworkDecompositionArcListNode* arcListNode = nodeIsHead ? &dec->arcs[arc].headArcListNode
1800 SPQRNetworkDecompositionArcListNode* nextListNode = nextIsHead ? &dec->arcs[firstNodeArc].headArcListNode
1808 SPQRNetworkDecompositionArcListNode* previousListNode = previousIsHead ? &dec->arcs[lastNodeArc].headArcListNode
1933/** Returns the virtual arc pointing to the parent member (in the arborescence) of the given member. */
1948/** Updates the parent information of a member that is identified with another another member. */
2020/** Creates a standalone parallel member with the given row and columns that is not connected to other members of the
2036 SCIP_CALL( createMember(dec, num_columns <= 1 ? SPQR_MEMBERTYPE_LOOP : SPQR_MEMBERTYPE_PARALLEL, &member) );
2053/** Creates a parallel member with the given row and columns is connected to other members of the
2084/** Creates a standalone series member with the given row and columns that is not connected to other members of the
2100 SCIP_CALL( createMember(dec, numRows <= 1 ? SPQR_MEMBERTYPE_LOOP : SPQR_MEMBERTYPE_SERIES, &member) );
2116/** Creates a series member with the given row and columns that is connected to some other member of the
2179/** Data structure for the algorithms to find fundamental cycle within the network matrix decomposition */
2186/** Processes a single arc for the algorithm to find cycles in the network matrix decomposition.
2246 SCIP_Bool* computedSignStorage /**< Boolean array for storage of whether the path occurs forwards or
2250 /*Basic idea; for each component, do a dfs over the tree formed by the row arcs to find the relevant edges.
2437 const double* nonzvals, /**< Array with the nonzero entry values of the column's row indices */
2441 SCIP_Bool* pathsignstorage /**< Temporary storage for the fundamental path directions. Must have
2445 int num_found_rows = decompositionGetFundamentalCycleRows(dec, column, pathrowstorage, pathsignstorage);
2543/** Returns the number of SPQR trees in the SPQR forest, i.e. the number of connected components. */
2602 SCIP_Bool parentIsTree, /**< Is the edge in the parent member (the child marker) a tree edge? */
2608 SCIP_CALL( createChildMarker(dec, parentMember, childMember, parentIsTree, &parentToChildMarker, childMarkerReversed) );
2611 SCIP_CALL( createParentMarker(dec, childMember, !parentIsTree, parentMember, parentToChildMarker,
2617/** Creates a child-marker parent-marker pair in the network decomposition, and returns the assigned arc id's. */
2623 SCIP_Bool parentIsTree, /**< Is the edge in the parent member (the child marker) a tree edge? */
2626 spqr_arc* parentToChild, /**< Output-pointer containing arc id of the arc in the parent member */
2627 spqr_arc* childToParent /**< Output-pointer containing arc id of the arc in the child member */
2630 SCIP_CALL( createChildMarker(dec, parentMember, childMember, parentIsTree, parentToChild, childMarkerReversed) );
2631 SCIP_CALL( createParentMarker(dec, childMember, !parentIsTree, parentMember, *parentToChild, childToParent,
2637/** Moves a given arc from one member to another, updating the linked lists it is contained in and the parent/child
2654 //Need to change the arc's member, remove it from the current member list and add it to the new member list
2669 //If this arc is a marker to the parent, update the child arc marker of the parent to reflect the move
2676 assert(findArcChildMemberNoCompression(dec, dec->members[oldMember].markerOfParent) == oldMember);
2685 spqr_member toMergeInto, /**< The member id that gets the new large linked list containing both */
2686 spqr_member toRemove /**< The member id that is invalidated, whose linked list is moved away. */
2745/** Checks if the network decomposition is minimal, i.e. if it does not contain two adjacent parallel or series
2757 if( !memberIsRepresentative(dec, member) || getMemberType(dec, member) == SPQR_MEMBERTYPE_UNASSIGNED )
2777/** Decreases the count of the number of connected components in the network matrix decomposition. */
2788/** Reorders the arborescence of the SPQR that contains a given member so that the given member becomes the new root
2841/** Deletes the SPQR tree (connected component) containing the given component rows and columns.
2843 * Note that the implementation of this method does not actually modify the SPQR tree, but rather unlinks the rows and
2844 * columns from the relevant arcs. Thus, this method is a bit hacky and should be used with care.
2856 //This is sufficient for our purposes, as long as we do not re-introduce any of the 'negated' rows/columns back into the decomposition.
2878/** Converts the members type to an associated character */ //Debugging functions to print the decomposition
2925 fprintf(stream, " %c_%d_%lu -> %c_p_%d [label=\"%d\",style=dashed%s];\n", type, member, dot_tail, type, member, arc_name, color);
2926 fprintf(stream, " %c_p_%d -> %c_%d_%lu [label=\"%d\",style=dashed%s];\n", type, member, type, member, dot_head, arc_name, color);
2939 fprintf(stream, " %c_%d_%lu -> %c_c_%d [label=\"%d\",style=dotted%s];\n", type, member, dot_tail, type, child, arc_name, color);
2940 fprintf(stream, " %c_c_%d -> %c_%d_%lu [label=\"%d\",style=dotted%s];\n", type, child, type, member, dot_head, arc_name, color);
2944 fprintf(stream, " %c_p_%d -> %c_c_%d [style=dashed,dir=forward];\n", childType, child, type, child);
2961 fprintf(stream, " %c_%d_%lu -> %c_%d_%lu [label=\"%d \",style=bold%s];\n", type, member, dot_tail, type, member, dot_head,
3058 SCIP_Bool headToHead, /**< Identify the head of parentToChild with the head of childToParent?*/
3118 /* Compute the number of rows m in the network matrix decomposition. The underlying graph has m+1 vertices. */
3127 /* Map decomposition nodes to graph nodes. The first node of each component is mapped to node 0 */
3135 /* Recursively explore the decomposition, adding the edges of each component and identifying them as needed */
3435/* ---------- START functions for column addition ------------------------------------------------------------------- */
3462 * next path arc in the SPQR tree. We additionally store copies of the corresponding arc's node indices.
3469 path_arc_id nextMember; /**< Array index of the next path arc in the member path arc linked list */
3470 path_arc_id nextOverall; /**< Array index of the next path arc in the total path arc linked list */
3475/** Index for the reduced members, which are the members of the sub-SPQR tree containing all path arcs.
3503/** Type of the member, signifies to what degree we processed the member and how to treat with it when updating the
3508 REDUCEDMEMBER_TYPE_UNASSIGNED = 0, /**< We have not yet decided if the reduced member contains a valid path */
3509 REDUCEDMEMBER_TYPE_CYCLE = 1, /**< The reduced member is a leaf node of the SPQR tree and contains a path
3512 REDUCEDMEMBER_TYPE_MERGED = 2, /**< The reduced member contains a path and is not propagated */
3513 REDUCEDMEMBER_TYPE_NOT_NETWORK = 3 /**< The reduced member does not have a valid path or can not be oriented
3544/** A struct that keeps track of the relevant data for the members that are in the subtree given by the specified row
3558 children_idx numChildren; /**< The number of children in the arborescence of this reduced member */
3564 spqr_node rigidPathStart; /**< The start node of the path. Only used for Rigid/3-connected nodes */
3565 spqr_node rigidPathEnd; /**< The end node of the path. Only used for Rigid/3-connected nodes */
3570 int numPropagatedChildren; /**< Counts the number of children that are cycles that propagated to this
3572 int componentIndex; /**< Stores the index of the component of the SPQR forest that this reduced
3576 reduced_member_id nextPathMember; /**< Indicates the id of the next reduced member in the path during merging.
3578 SCIP_Bool nextPathMemberIsParent; /**< Indicates if the next reduced member in the path is a parent of
3590 reduced_member_id pathEndMembers[2]; /**< The reduced members that contain the ends of the path */
3594/** Keeps track of the reduced member and the reduced member that is the root of the arborescence for a single member */
3598 reduced_member_id rootDepthMinimizer; /**< The ID of the reduced member that is the root of the arborescence this
3602/** Data to be used for the recursive algorithms that creates the sub-SPQR trees that contain the path edges */
3611 SCIP_Bool remainsNetwork; /**< Does the addition of the current column give a network matrix? */
3613 SPQRColReducedMember* reducedMembers; /**< The array of reduced members, that form the subtree containing the
3623 MemberInfo* memberInformation; /**< Array with member information; tracks the reduced member id that
3628 reduced_member_id* childrenStorage; /**< Array that stores the children of the reduced member arborescences.
3635 PathArcListNode* pathArcs; /**< Array that contains the linked-list nodes of the path arcs, that
3649 CreateReducedMembersCallstack* createReducedMembersCallStack; /**< Callstack for createReducedMembers() */
3650 int memCreateReducedMembersCallStack; /**< Allocated memory for callstack for createReducedMembers() */
3665 int memDecompositionRowArcs; /**< Number of allocated slots in decompositionRowArcs(Reversed) */
3673/** Clean up internal temporary data structures that were used in the previous column iteration. */
3727 SCIP_NETCOLADD** pcoladd /**< Out-pointer for the created network column addition datastructure */
3791 SCIP_NETCOLADD** pcoladd /**< Pointer to the network column addition datastructure to be freed */
3797 BMSfreeBlockMemoryArray(blkmem, &newCol->decompositionRowArcs, newCol->memDecompositionRowArcs);
3798 BMSfreeBlockMemoryArray(blkmem, &newCol->decompositionArcReversed, newCol->memDecompositionRowArcs);
3801 BMSfreeBlockMemoryArray(blkmem, &newCol->createReducedMembersCallStack, newCol->memCreateReducedMembersCallStack);
3816/** Adds members to the reduced member tree, by starting at the given member, jumping up to the parent, repeating this
3828 /* Originally a recursive algorithm, but for large matrices we need to unroll recursion to prevent stack overflows
3885 newCol->reducedComponents[newCol->numReducedComponents].pathEndMembers[0] = INVALID_REDUCED_MEMBER;
3886 newCol->reducedComponents[newCol->numReducedComponents].pathEndMembers[1] = INVALID_REDUCED_MEMBER;
3895 reduced_member_id* depthMinimizer = &newCol->memberInformation[newCol->reducedMembers[reducedMember].rootMember].rootDepthMinimizer;
3910 reduced_member_id currentReducedMember = newCol->memberInformation[currentMember].reducedMember;
3926 reduced_member_id returnedMember = newCol->memberInformation[callstack[0].member].reducedMember;
3930/** Construct the reduced decomposition, which is the smallest subtree containing all members path arcs. */
3959 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newCol->reducedMembers, newCol->memReducedMembers, newArraySize) );
3965 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newCol->memberInformation, newCol->memMemberInformation, updatedSize) );
3978 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newCol->reducedComponents, newCol->memReducedComponents, updatedSize) );
3998 reduced_member_id* depthMinimizer = &newCol->memberInformation[newCol->reducedMembers[reducedMember].rootMember].rootDepthMinimizer;
4014 //This simplifies code further down which does not need to be component-aware; just pretend that the reduced member is the new root.
4024 reduced_member_id minimizer = newCol->memberInformation[reducedMember->rootMember].rootDepthMinimizer;
4036 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newCol->childrenStorage, newCol->memChildrenStorage, newMemSize) );
4042 for( reduced_member_id reducedMember = 0; reducedMember < newCol->numReducedMembers; ++reducedMember )
4046 newCol->reducedMembers[newCol->memberInformation[reducedMemberData->rootMember].rootDepthMinimizer].depth )
4083 //This loop is at the end as memberInformation is also used to assign the cut arcs during propagation
4087 newCol->memberInformation[newCol->reducedMembers[i].member].reducedMember = INVALID_REDUCED_MEMBER;
4128 if( getMemberType(dec, newCol->reducedMembers[reducedMember].member) == SPQR_MEMBERTYPE_RIGID )
4137 assert(listNode->arcHead < newCol->memNodePathDegree && listNode->arcTail < newCol->memNodePathDegree);
4160 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newCol->pathArcs, newCol->memPathArcs, newMaxNumArcs) );
4167 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newCol->arcInPath, newCol->memArcsInPath, newSize) );
4168 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newCol->arcInPathReversed, newCol->memArcsInPath, newSize) );
4181 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newCol->nodeInPathDegree, newCol->memNodePathDegree, newSize) );
4182 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newCol->nodeOutPathDegree, newCol->memNodePathDegree, newSize) );
4202/** Saves the information of the current row and partitions it based on whether or not the given columns are
4228 int newNumArcs = newCol->memDecompositionRowArcs == 0 ? 8 : 2 * newCol->memDecompositionRowArcs;
4270 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newCol->leafMembers, newCol->memLeafMembers, newSize) );
4275 for( reduced_member_id reducedMember = 0; reducedMember < newCol->numReducedMembers; ++reducedMember )
4299 /* Simply count the in and out degrees of the nodes to check if the path arcs form a path. We have a valid path if
4300 * and only if the head of the tail of the path are the only nodes with 1 adjacent edge, and all other nodes
4305 for( path_arc_id pathArc = redMem->firstPathArc; pathArcIsValid(pathArc); pathArc = newCol->pathArcs[pathArc].nextMember )
4341 assert(!isValidPath || ( SPQRnodeIsValid(redMem->rigidPathStart) && SPQRnodeIsValid(redMem->rigidPathEnd)));
4351/** Determines the member's type for the case where the reduced tree consists of a single rigid member. */
4372/** Determines the member's type for the case where the reduced tree consists of a single member. */
4384 newCol->reducedMembers[reducedMember].numChildren - newCol->reducedMembers[reducedMember].numPropagatedChildren;
4386 newCol->reducedMembers[newCol->reducedMembers[reducedMember].parent].type != REDUCEDMEMBER_TYPE_CYCLE )
4430 newCol->pathArcs[pathArc].reversed != arcIsReversedNonRigid(dec, newCol->pathArcs[pathArc].arc);
4433 (newCol->pathArcs[pathArc].reversed != arcIsReversedNonRigid(dec, newCol->pathArcs[pathArc].arc)) !=
4500 newCol->pathArcs[pathArc].reversed != arcIsReversedNonRigid(dec, newCol->pathArcs[pathArc].arc);
4502 else if(( newCol->pathArcs[pathArc].reversed != arcIsReversedNonRigid(dec, newCol->pathArcs[pathArc].arc)) !=
4522 SCIP_Bool firstReversed = arcIsReversedNonRigid(dec, newCol->pathArcs[redMem->firstPathArc].arc);
4615 //Parallel members must always be of degree two; if they are a leaf, they must contain an edge, which could have been propagated
4629 newCol->pathArcs[pathArc].reversed != arcIsReversedNonRigid(dec, newCol->pathArcs[pathArc].arc);
4694 if( !(sourceHeadIsTargetHead || sourceTailIsTargetHead || sourceHeadIsTargetTail || sourceTailIsTargetTail) )
4701 ( sourceHeadIsTargetHead ? 1 : 0 ) + ( sourceHeadIsTargetTail ? 1 : 0 ) + ( sourceTailIsTargetHead ? 1 : 0 ) +
4816 assert(startsAtHead || endsAtTail);//both can hold; they can form cycle but other components can not be reduced
4817 // redMem->reverseArcs = isInto(previousType) != startsAtHead; //Reverse only if there is no path starting at head
4828 assert(startsAtTail || endsAtHead);// both can hold; they can form cycle but other components can not be reduced
4829 // redMem->reverseArcs = isInto(previousType) != startsAtTail; //Reverse only if there is no path starting at tail
5021 //form a (reverse) directed path from one of the source's end nodes to one of the target's end nodes
5068 //We check the path by going from end to end. We start at the leaf and process every component,
5103 newCol->reducedMembers[reducedMember].firstChild + newCol->reducedMembers[reducedMember].numChildren; ++i )
5132 //We explicitly set the target arc to invalid in order to indicate that this is the last iteration.
5141 * If so, we can propagate this cycle to a virtual arc of the child node member and shrink the decomposition.
5161 SCIP_Bool matches = leafMember->rigidPathStart == targetTail && leafMember->rigidPathEnd == targetHead;
5162 SCIP_Bool opposite = leafMember->rigidPathStart == targetHead && leafMember->rigidPathEnd == targetTail;
5174 * If so, we can propagate this cycle to a virtual arc of the child node member and shrink the decomposition.
5208 SCIP_Bool arcPathArcIsReverse = arcIsReversedNonRigid(dec, newCol->pathArcs[reducedMember->firstPathArc].arc);
5210 createPathArc(dec, newCol, toChild, parent, ( arcPathArcIsReverse == parentReversed ) == pathArcReversed);
5226 newCol->pathArcs[pathArc].reversed != arcIsReversedNonRigid(dec, newCol->pathArcs[pathArc].arc);
5229 (newCol->pathArcs[pathArc].reversed != arcIsReversedNonRigid(dec, newCol->pathArcs[pathArc].arc)) !=
5251 SCIP_Bool firstArcReversed = arcIsReversedNonRigid(dec, newCol->pathArcs[reducedMember->firstPathArc].arc);
5275/** Recursively removes leaf nodes whose path forms cycles with the virtual arc to its children. */
5301 if( newCol->reducedMembers[next].numPropagatedChildren == newCol->reducedMembers[next].numChildren )
5325 newCol->reducedComponents[component].pathEndMembers[newCol->reducedComponents[component].numPathEndMembers] = leaf;
5339 newCol->reducedComponents[component].pathEndMembers[newCol->reducedComponents[component].numPathEndMembers] = leaf;
5351 if( newCol->reducedMembers[root].numPropagatedChildren != newCol->reducedMembers[root].numChildren - 1 )
5385 //If the root has exactly one neighbour and is not contained, it is also considered a path end member
5390 rootPresent = rootPresent || ( newCol->reducedComponents[component].pathEndMembers[i] == root );
5399 newCol->reducedComponents[component].pathEndMembers[newCol->reducedComponents[component].numPathEndMembers] = root;
5484/** Struct that contains the data that tells us how to add the new column after the graph has been modified.
5486 * In the case the member is a series or parallel node, the new column and rows are placed in series or parallel,
5498#define NEWCOLINFORMATION_EMPTY { SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, SPQR_INVALID_NODE, SPQR_INVALID_ARC, FALSE }
5564/** Splits a parallel member into two adjacent parallel members connected by a virtual edge pair.
5592 SCIP_CALL( createMarkerPair(dec, *childParallel, parallel, !childContainsTree, FALSE, FALSE) );
5602/** Very elaborate function that splits a series member into multiple members based on the structure of the path arcs.
5604 * The updated member reflects the structure of the updated SPQR tree after the new column arc is added.
5625 //TODO: for now very elaborate to first get logic correct. Can probably merge some branches later...
5661 //The 'reversed' field has different meaning for parallels, so we need to change orientation when converting to a parallel
5705 //if the single unmarked (column) marker is a parent or child marker to a parallel member, we add the edge there
5783/** Very elaborate function that splits a series member into multiple members based on the structure of the path arcs.
5785 * The updated member reflects the structure of the updated SPQR tree after the new column arc is added.
5786 * This variant is only used on series members that are part of a reduced tree that is not a single member.
5794 spqr_arc* pathRepresentative, /**< Out pointer pointing to the tree arc in the final series node */
5795 spqr_arc* nonPathRepresentative, /**< Out pointer pointing to the non-tree arc in the final series node*/
5805 int numExceptionArcs = ( exceptionArc1 == SPQR_INVALID_ARC ? 0 : 1 ) + ( exceptionArc2 == SPQR_INVALID_ARC ? 0 : 1 );
5806 int numNonPathArcs = getNumMemberArcs(dec, member) - reducedMember->numPathArcs - numExceptionArcs;
5835 SCIP_CALL( createMarkerPairWithReferences(dec, pathMember, member, FALSE, inNewReversed, inOldReversed,
5840 SCIP_CALL( createMarkerPairWithReferences(dec, member, pathMember, TRUE, inOldReversed, inNewReversed,
5863 SCIP_Bool canStop = FALSE;//hack when the first arc is moved in the below loop to prevent that we immediately terminate
5934 spqr_arc* representativeArc, /**< Pointer to the representative of the member, needed for merging.*/
5954 *representativeArc = findArcSign(dec, newCol->reducedMembers[reducedMember].pathTargetArc).representative;
5966 SCIP_CALL( splitSeriesMerging(dec, newCol, redMem, member, &pathRepresentative, &nonPathRepresentative, target,
5970 target != pathRepresentative && target != nonPathRepresentative && pathRepresentative != nonPathRepresentative);
5971 assert(SPQRarcIsValid(pathRepresentative) && SPQRarcIsValid(nonPathRepresentative) && SPQRarcIsValid(target));
6009 //setup signed union find; all arcs are placed are not reversed. We pick an arbitrary arc as 'root' arc for this skeleton
6032/** Transforms the next parallel member in the path of members and merge it into the current member. */
6041 spqr_arc* representativeArc, /**< Pointer to the representative of the member, needed for merging.*/
6109/** Transforms the next series member in the path of members and merge it into the current member. */
6118 spqr_arc* representativeArc, /**< Pointer to the representative of the member, needed for merging.*/
6130 splitSeriesMerging(dec, newCol, redMem, nextMember, &pathRepresentative, &nonPathRepresentative, source, target) );
6139 ( SPQRarcIsInvalid(target) || ( target != pathRepresentative && target != nonPathRepresentative )));
6262/** Transforms the next rigid member in the path of members and merge it into the current member. */
6271 spqr_arc* representativeArc, /**< Pointer to the representative of the member, needed for merging.*/
6297 *representativeArc = mergeArcSigns(dec, *representativeArc, sourceRepresentative, redMem->reverseArcs);
6339 spqr_arc* representativeArc, /**< Pointer to the representative of the member, needed for merging.*/
6390 SCIP_CALL( transformFirstPathMember(dec, newCol, firstPathMember, newColInfo, &representativeArc, &mergedMember) );
6398 transformAndMerge(dec, newCol, current, next, &representativeArc, &mergedMember, nextIsParent, newColInfo));
6465 //However, there is one exception, which is that an arc connecting these two nodes already exists in the member
6466 //If so, we create a new parallel member with the new arc and this member, unless the existing arc already points
6469 assert(SPQRnodeIsValid(reducedMember->rigidPathStart) && SPQRnodeIsValid(reducedMember->rigidPathEnd));
6499 if( SPQRmemberIsValid(adjacentMember) && getMemberType(dec, adjacentMember) == SPQR_MEMBERTYPE_PARALLEL )
6501 spqr_arc parallelMarker = isParent ? markerOfParent(dec, member) : markerToParent(dec, adjacentMember);
6509 //This is a bit painful, because we cannot actually remove edges because of the union-find data structure
6521 SCIP_CALL( createColumnArc(dec, adjacentParallel, &duplicate, SPQRelementToColumn(element), FALSE) );
6525 SCIP_CALL( createRowArc(dec, adjacentParallel, &duplicate, SPQRelementToRow(element), FALSE) );
6530 SCIP_CALL( createParentMarker(dec, adjacentParallel, arcIsTree(dec, existingArcWithPath), adjacentMember,
6535 SCIP_CALL( createChildMarker(dec, adjacentParallel, adjacentMember, arcIsTree(dec, existingArcWithPath),
6544 SCIP_CALL( createChildMarker(dec, adjacentParallel, member, !arcIsTree(dec, existingArcWithPath),
6561 dec->arcs[existingArcWithPath].element = arcIsTree(dec, existingArcWithPath) ? MARKER_ROW_ELEMENT
6567 dec->arcs[existingArcWithPath].element = arcIsTree(dec, existingArcWithPath) ? MARKER_ROW_ELEMENT
6639 // Otherwise, the reduced members form a path which can be merged into a single component of type R
6682 SCIP_CALL( createColumnArc(dec, information.member, &colArc, newCol->newColIndex, information.reversed) );
6687 setArcHeadAndTail(dec, colArc, findNode(dec, information.head), findNode(dec, information.tail));
6689 arcSetReversed(dec, colArc, information.reversed != arcIsReversedNonRigid(dec, information.representative));
6695 SCIP_CALL( createConnectedSeries(dec, newCol->newRowArcs, newCol->newRowArcReversed, newCol->numNewRowArcs,
6699 SCIP_CALL( createMarkerPairWithReferences(dec, information.member, newSeries, FALSE, information.reversed, TRUE,
6705 setArcHeadAndTail(dec, markerArc, findNode(dec, information.head), findNode(dec, information.tail));
6713 assert(getNumMemberArcs(dec, information.member) == 2 || getNumMemberArcs(dec, information.member) == 3);
6743 reorderComponent(dec, information.member);//reorder the subtree so that the newly series member is a parent
6746 SCIP_CALL( createMarkerPairWithReferences(dec, newSeries, information.member, TRUE, information.reversed,
6752 setArcHeadAndTail(dec, markerArc, findNode(dec, information.head), findNode(dec, information.tail));
6760 assert(numConnectedComponents(dec) == ( numDecComponentsBefore - newCol->numReducedComponents + 1 ));
6766/* ---------- END functions for column addition --------------------------------------------------------------------- */
6768/* ---------- START functions for row addition ---------------------------------------------------------------------- */
6770/** Index type for the nonzeros of the new row, e.g. the columns whose tree path must be elongated with the new row */
6793 * Contains links to the next cut arc in the whole decomposition and the next cut arc in the current member.
6800 cut_arc_id nextMember; /**< Index to next linked list node of the linked list containing the cut arcs
6802 cut_arc_id nextOverall; /**< Index to next linked list node of the linked list containing the cut arcs
6820/** Stores for every vertex information needed for computing articulation nodes in rigid members. */
6842/** Call stack data structure that determines whether a bipartition of the nodes exists that satisfies the requirements. */
6849/** Call stack data structure for recursive algorithm to find articulation point in rigid member graphs (Tarjan). */
6873 spqr_member rootMember; /**< The decomposition member that is the root node of the arborescence
6880 children_idx numChildren; /**< The number of children in the arborescence of this reduced member */
6881 children_idx numPropagatedChildren; /**< Counts the number of children that are propagated to this reduced
6888 SCIP_Bool splitHead; /**< Is the head or the tail of the split arc split in the realization? */
6898 spqr_arc articulationArc; /**< Indicates the arc between the split node and the other ndoe, if both
6900 spqr_node coloredNode; /**< Points to a colored node so that we can efficiently zero out colors
6916 SPQRRowReducedMember* reducedMembers; /**< The array of reduced members, that form the subtree containing the
6926 MemberInfo* memberInformation; /**< Array with member information; tracks the reduced member id that
6931 reduced_member_id* childrenStorage; /**< Array that stores the children of the reduced member arborescences.
6941 cut_arc_id firstOverallCutArc; /**< Index of the head node of the linked list containing all cut arcs */
6947 SCIP_Bool* newColumnReversed; /**< True if the nonzero entry of the new column is -1, False otherwise */
6955 spqr_arc* decompositionColumnArcs; /**< For each nonzero column of the new row that is in the decomposition,
6957 SCIP_Bool* decompositionColumnArcReversed; /**< For each nonzero column of the new row that is in the decomposition,
6959 int memDecompositionColumnArcs; /**< Number of allocated slots in decompositionColumnArcs(Reversed) */
6960 int numDecompositionColumnArcs; /**< Number of used slots in decompositionColumnArcs(Reversed) */
6969 spqr_node* articulationNodes; /**< Temp. array for storing articulation nodes of member graph-cut arcs */
6973 ArticulationNodeInformation* articulationNodeSearchInfo; /**< Stores for each node information necessary to find
6975 int memNodeSearchInfo; /**< The number of allocated entries in articulationNodeSearchInfo array*/
6978 int memCrossingPathCount; /**< The number of allocated entries for the crossingPathCount array */
6980 DFSCallData* intersectionDFSData; /**< Call stack for computing the intersection of all cut arc paths */
6989 CreateReducedMembersCallstack* createReducedMembersCallstack; /**< Call stack for createReducedMembers() */
6990 int memCreateReducedMembersCallstack; /**< Number of allocated entries for createReducedMembersCallStack */
6992 int* intersectionPathDepth; /**< Tracks depth of each node in the intersection of all paths algorithm */
6993 int memIntersectionPathDepth; /**< Number of allocated entries in intersectionPathDepth array */
6995 spqr_node* intersectionPathParent; /**< Tracks the parents of each node in the intersection of all paths
6997 int memIntersectionPathParent; /**< Number of allocated entries in intersectionPathParent array */
7016#define NEWROWINFORMATION_EMPTY { SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, SPQR_INVALID_NODE, SPQR_INVALID_ARC, FALSE }
7018/** Saves the information of the current row and partitions it based on whether or not the given columns are
7044 int newNumArcs = newRow->memDecompositionColumnArcs == 0 ? 8 : 2 * newRow->memDecompositionColumnArcs;
7076/** Adds members to the reduced member tree, by starting at the given member, jumping up to the parent, repeating this
7152 reduced_member_id* depthMinimizer = &newRow->memberInformation[newRow->reducedMembers[reducedMember].rootMember].rootDepthMinimizer;
7167 reduced_member_id currentReducedMember = newRow->memberInformation[currentMember].reducedMember;
7180 reduced_member_id returnedMember = newRow->memberInformation[callstack[0].member].reducedMember;
7185/** Construct the reduced decomposition, which is the smallest subtree containing all members cut arcs. */
7212 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->reducedMembers, newRow->memReducedMembers, updatedSize) );
7218 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->memberInformation, newRow->memMemberInformation, updatedSize) );
7231 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->reducedComponents, newRow->memReducedComponents, updatedSize) );
7251 reduced_member_id* depthMinimizer = &newRow->memberInformation[newRow->reducedMembers[reducedMember].rootMember].rootDepthMinimizer;
7267 //This simplifies code further down which does not need to be component-aware; just pretend that the reduced member is the new root.
7277 reduced_member_id minimizer = newRow->memberInformation[reducedMember->rootMember].rootDepthMinimizer;
7289 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->childrenStorage, newRow->memChildrenStorage,
7296 for( reduced_member_id reducedMember = 0; reducedMember < newRow->numReducedMembers; ++reducedMember )
7300 newRow->reducedMembers[newRow->memberInformation[reducedMemberData->rootMember].rootDepthMinimizer].depth )
7364 if( getMemberType(dec, newRow->reducedMembers[reducedMember].member) == SPQR_MEMBERTYPE_RIGID )
7398 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->isArcCut, newRow->memIsArcCut, newSize) );
7399 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->isArcCutReversed, newRow->memIsArcCut, newSize) );
7419 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->cutArcs, newRow->memCutArcs, newSize) );
7439 * propagation is only checked for components which have at most one neighbour that is not propagated.
7450 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->leafMembers, newRow->memLeafMembers, updatedSize) );
7455 for( reduced_member_id reducedMember = 0; reducedMember < newRow->numReducedMembers; ++reducedMember )
7479 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->nodeColors, newRow->memNodeColors, newSize) );
7490 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->articulationNodes, newRow->memArticulationNodes, newSize) );
7496 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->articulationNodeSearchInfo, newRow->memNodeSearchInfo,
7503 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->crossingPathCount, newRow->memCrossingPathCount, newSize) );
7514 //TODO: see if tradeoff for performance bound by checking max # of nodes of rigid is worth it to reduce size
7517 //TODO: only update the stack sizes of the following when needed? The preallocation may not be worth it.
7521 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->intersectionDFSData, newRow->memIntersectionDFSData, newSize) );
7527 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->colorDFSData, newRow->memColorDFSData, newSize) );
7533 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->artDFSData, newRow->memArtDFSData, newSize) );
7545 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->intersectionPathDepth, newRow->memIntersectionPathDepth,
7560 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->intersectionPathParent, newRow->memIntersectionPathParent,
7673/** Finds all the star nodes, i.e. nodes that are adjacent to all cut arcs, in a rigid member. */
7686 assert(newRow->reducedMembers[toCheck].numCutArcs > 0);//calling this function otherwise is nonsensical
7693 SCIP_Bool reverse = findArcSign(dec, cutArc).reversed != newRow->cutArcs[cutArcIdx].arcReversed;
7750 //Check if the n arcs are in a n+1 degree node; if so, the other endpoint of this non split arc is also splittable
7771 newRow->reducedMembers[toCheck].otherNode = arcHead == splitNode ? findArcTail(dec, neighbourArc) : arcHead;
7777 * We do DFS in reverse (reverse exploration order), as zeroing out the entire array is more expensive.
7827 * Theoretically, there is a faster algorithm using lowest common ancestor queries, but it is quite complicated.
7846 spqr_node root = findArcHead(dec, newRow->cutArcs[newRow->reducedMembers[toCheck].firstCutArc].arc);
7972 ArticulationNodeInformation* nodeInfo, /**< Stores information about the found articulation nodes */
7979 spqr_node root_node = findArcHead(dec, getFirstMemberArc(dec, newRow->reducedMembers[reducedMember].member));
8055/** For a given articulation node, partitions the rigid member's graph where it is removed into a SOURCE and SINK
8058 * All cut arcs must point (after reversal) from the source partition to the sink partition. This is akin
8059 * to finding a 2-coloring, and uses a DFS to do so. This function specifically executes the DFS/recursive part.
8091 //Checks the direction of the arc; in the rest of the algorithm, we just need to check partition
8095 SCIP_Bool arcReversed = findArcSign(dec, callData->arc).reversed != newRow->isArcCutReversed[callData->arc];
8109 nodeColors[otherNode] = currentColor == COLOR_SOURCE ? COLOR_SINK : COLOR_SOURCE;//reverse the colors
8137/** For a given articulation node, partitions the rigid member's graph where it is removed into a SOURCE and SINK
8140 * All cut arcs must point (after reversal) from the source partition to the sink partition. This is akin
8214/** Given a coloring for an articulation node, we can prove that a neighbouring node is splittable if and only if it is
8215 * the unique node in the neighbourhood of the articulation node within the SOURCE or SINK partition. In this function,
8216 * we check for a splittable articulation node if such an adjacent node exists, and return it if possible.
8284/** Find all the splittable articulation points that lie on the intersection of all cut arc cycles.
8286 * firstNode and secondNode can be set to limit the nodes that this function checks to the given nodes.
8329 (( SPQRnodeIsInvalid(firstNode) && SPQRnodeIsInvalid(secondNode)) || articulationNode == firstNode ||
8340 //Once we have found one node, we can (possibly) find another by looking at the coloring of the neighbourhood of it.
8343 spqr_node adjacentSplittingNode = checkNeighbourColoringArticulationNode(dec, newRow, articulationNode,
8349 (( SPQRnodeIsInvalid(firstNode) && SPQRnodeIsInvalid(secondNode)) || adjacentSplittingNode == firstNode ||
8413 SCIP_Bool arcIsReversed = arcIsReversedNonRigid(dec, arc) != newRow->cutArcs[cutArc].arcReversed;
8433 countedCutArcs != ( getNumMemberArcs(dec, newRow->reducedMembers[toCheckMember].member) - 1 ) )
8500 rigidGetSplittableArticulationPointsOnPath(dec, newRow, toCheckMember, markerHead, markerTail);
8574/** Propagates away all leaf members that are propagatable to shrink the reduced decomposition. */
8601 if( newRow->reducedMembers[next].numPropagatedChildren == newRow->reducedMembers[next].numChildren )
8633 if( newRow->reducedMembers[root].numPropagatedChildren == newRow->reducedMembers[root].numChildren - 1 )
8704 i < newRow->reducedMembers[toCheck].firstChild + newRow->reducedMembers[toCheck].numChildren; ++i )
8760/** Allocates memory for various procedures that need to do tree-search for rigid members (e.g. DFS or BFS). */
8771 SCIP_ALLOC( BMSreallocBlockMemoryArray(dec->env, &newRow->mergeTreeCallData, newRow->memMergeTreeCallData,
8778/** Determine the type of a rigid member when it is the only member in the reduced decomposition. */
8798 rigidGetSplittableArticulationPointsOnPath(dec, newRow, reducedMember, SPQR_INVALID_NODE, SPQR_INVALID_NODE);
8811/** Determine the type of a parallel member when it is the only member in the reduced decomposition. */
8829 SCIP_Bool arcIsReversed = arcIsReversedNonRigid(dec, arc) != newRow->cutArcs[cutArc].arcReversed;
8852/** Determine the type of a series member when it is the only member in the reduced decomposition. */
8864/** Sets the given split nodes; performs bookkeeping so that we have an easier time updating the graph in many
8903 if( SPQRnodeIsInvalid(splitNode) || ( splitNode != candidateOne && splitNode != candidateTwo ) )
8929 newRow->nodeColors[newRow->reducedMembers[id].splitNode] = newRow->reducedMembers[id].otherIsSource ? COLOR_SINK
8945 newRow->nodeColors[newRow->reducedMembers[id].splitNode] = splitColor == COLOR_SOURCE ? COLOR_SINK : COLOR_SOURCE;
8953/** After propagation, determines the split type of the first leaf node of the reduced decomposition.
8981 SCIP_Bool arcIsReversed = arcIsReversedNonRigid(dec, arc) != newRow->cutArcs[cutArc].arcReversed;
9071/** A data structure that tells us if the head or tail of a marked arc is split, and if the other node is in the
9089 assert(findArcMemberNoCompression(dec, arcToNext) == newRow->reducedMembers[reducedId].member);
9100 orientation.headSplit = newRow->reducedMembers[reducedId].willBeReversed == ( head != splitNode );
9140 assert(findArcMemberNoCompression(dec, arcToNext) == newRow->reducedMembers[reducedId].member);
9141 assert(SPQRarcIsValid(newRow->reducedMembers[reducedId].splitArc) && SPQRarcIsValid(arcToNext));
9145 if( arcIsReversedNonRigid(dec, arcToNext) == arcIsReversedNonRigid(dec, newRow->reducedMembers[reducedId].splitArc))
9165 assert(findArcMemberNoCompression(dec, arcToNext) == newRow->reducedMembers[reducedId].member);
9166 assert(SPQRarcIsValid(newRow->reducedMembers[reducedId].splitArc) && SPQRarcIsValid(arcToNext));
9170 if( arcIsReversedNonRigid(dec, arcToNext) == arcIsReversedNonRigid(dec, newRow->reducedMembers[reducedId].splitArc))
9222 newRow->reducedMembers[reducedId].numChildren - newRow->reducedMembers[reducedId].numPropagatedChildren;
9280 SCIP_Bool arcIsReversed = arcIsReversedNonRigid(dec, arc) != newRow->cutArcs[cutArc].arcReversed;
9306 SCIP_Bool isHeadSourceOrTailTarget = previousOrientation.headSplit == previousOrientation.otherIsSource;
9307 SCIP_Bool isOkay = isHeadSourceOrTailTarget == ( isReversed == arcIsReversedNonRigid(dec, marker));
9401 spqr_node splitNode = determineAndColorSplitNode(dec, newRow, reducedId, nodes.first, nodes.second);
9442 reduced_member_id next, /**< The next node to determine the type of, adjacent to the current node */
9453 assert(type == SPQR_MEMBERTYPE_PARALLEL || type == SPQR_MEMBERTYPE_RIGID || type == SPQR_MEMBERTYPE_SERIES);
9480/** For the given root reduced member of a component, determine if the component is updateable/transformable. */
9489 if( newRow->reducedMembers[root].numPropagatedChildren == newRow->reducedMembers[root].numChildren )
9519 while( newRow->reducedMembers[leaf].numChildren != newRow->reducedMembers[leaf].numPropagatedChildren )
9560 if( childidx == newRow->reducedMembers[id].firstChild + newRow->reducedMembers[id].numChildren )
9595 //This loop is at the end as memberInformation is also used to assign the cut arcs during propagation
9599 newRow->memberInformation[newRow->reducedMembers[i].member].reducedMember = INVALID_REDUCED_MEMBER;
9663 //We would like to move the edge but unfortunately cannot do so without destroying the arc union-find datastructure.
9688 SCIP_CALL( createChildMarker(dec, newCycle, adjacentMember, arcIsTree(dec, arc), &duplicate, TRUE) );
9740 assert(newRow->reducedMembers[reducedMember].splitNode == findEffectiveArcHeadNoCompression(dec, arc) ||
9741 newRow->reducedMembers[reducedMember].splitNode == findEffectiveArcTailNoCompression(dec, arc));
9747 reversed = ( newRow->reducedMembers[reducedMember].splitNode == findEffectiveArcHead(dec, arc)) ==
9752 reversed = ( newRow->reducedMembers[reducedMember].splitNode == findEffectiveArcHead(dec, arc)) !=
9756 SCIP_CALL( rigidTransformArcIntoCycle(dec, member, newRow->reducedMembers[reducedMember].articulationArc,
9767 //Create a new node; move all cut arcs end of split node to it and add new arc between new node and split node
9821 spqr_arc nextArc = getNextNodeArc(dec, iterArc, splitNode);//Need to do this before we modify the arc :)
9862/** Splits a single parallel member into two adjacent ones, where the cut arcs and non-cut arcs get their own member. */
9896 convertOriginalParallel ));//This can only happen if the parallel member is actually a loop, which means it is mislabeled
9916 newRow->cutArcs[firstCut].arcReversed != arcIsReversedNonRigid(dec, newRow->cutArcs[firstCut].arc);
9918 if( SPQRmemberIsValid(adjacentMember) && getMemberType(dec, adjacentMember) == SPQR_MEMBERTYPE_SERIES )
10001 newRow->cutArcs[firstCut].arcReversed != arcIsReversedNonRigid(dec, newRow->cutArcs[firstCut].arc);
10054 newRow->cutArcs[cutArcId].arcReversed == arcIsReversedNonRigid(dec, newRow->cutArcs[cutArcId].arc);
10080 spqr_member* const mergingMember, /**< The member that contains the arcs that are to be merged */
10094 newRow->reducedMembers[reducedMember].firstChild + newRow->reducedMembers[reducedMember].numChildren; ++i )
10099 spqr_arc testArc = markerOfParent(dec, findMember(dec, newRow->reducedMembers[child].member));
10135 //Move all marker arcs which point to another component in the reduced decomposition to the new member
10142 i < newRow->reducedMembers[reducedMember].firstChild + newRow->reducedMembers[reducedMember].numChildren; ++i )
10146 newRow->reducedMembers[child].type == TYPE_MERGED || newRow->reducedMembers[child].type == TYPE_PROPAGATED);
10149 spqr_arc moveArc = markerOfParent(dec, findMember(dec, newRow->reducedMembers[child].member));
10159 assert(reducedMemberIsInvalid(parent) || ( newRow->reducedMembers[parent].type == TYPE_MERGED ||
10176 SCIP_CALL( createMarkerPairWithReferences(dec, mergingSeries, member, coTreeToMergingMember, TRUE, FALSE,
10182 createMarkerPairWithReferences(dec, member, mergingSeries, !coTreeToMergingMember, FALSE, TRUE, &ignoreArc,
10200 spqr_member* const pMergeMember, /**< The member that contains the arcs that are to be merged */
10205 assert(newRow->reducedMembers[reducedMember].numCutArcs < ( getNumMemberArcs(dec, member) - 1 ));
10208 newRow->reducedMembers[reducedMember].numChildren - newRow->reducedMembers[reducedMember].numPropagatedChildren;
10223 //The below cases can probably be aggregated in some way, but for now we first focus on the correct logic
10246 createMarkerPairWithReferences(dec, cutMember, member, TRUE, FALSE, FALSE, &ignoreArc, cutRepresentative) );
10251 createMarkerPairWithReferences(dec, member, cutMember, FALSE, FALSE, FALSE, cutRepresentative, &ignoreArc) );
10280 createMarkerPairWithReferences(dec, cutMember, member, TRUE, FALSE, FALSE, &ignoreArc, cutRepresentative) );
10285 createMarkerPairWithReferences(dec, member, cutMember, FALSE, FALSE, FALSE, cutRepresentative, &ignoreArc) );
10301 newRow->reducedMembers[child].type == TYPE_MERGED || newRow->reducedMembers[child].type == TYPE_PROPAGATED);
10304 spqr_arc moveArc = markerOfParent(dec, findMember(dec, newRow->reducedMembers[child].member));
10336 SCIP_CALL( createMarkerPairWithReferences(dec, mergingMember, member, !treeToMergingMember, FALSE, FALSE,
10341 SCIP_CALL( createMarkerPairWithReferences(dec, member, mergingMember, treeToMergingMember, FALSE, FALSE,
10377 newRow->reducedMembers[child].type == TYPE_MERGED || newRow->reducedMembers[child].type == TYPE_PROPAGATED);
10380 spqr_arc moveArc = markerOfParent(dec, findMember(dec, newRow->reducedMembers[child].member));
10412 SCIP_CALL( createMarkerPairWithReferences(dec, mergingMember, member, !treeToMergingMember, FALSE, FALSE,
10417 SCIP_CALL( createMarkerPairWithReferences(dec, member, mergingMember, treeToMergingMember, FALSE, FALSE,
10442 SCIP_CALL( splitParallelMerging(dec, newRow, leaf, member, &mergeMember, &cutRepresentative) );
10533 spqr_arc nextArc = getNextNodeArc(dec, iterArc, splitNode);//Need to do this before we modify the arc
10587 spqr_member* mergedMember, /**< Pointer to the member that contains both members after merging */
10652/** Update a series member to reflect the addition of the new row, and merge it into the previous members that were
10660 SCIP_Bool largeIsParent, /**< Whether the large member containing previously updated members is
10670 SCIP_CALL( splitSeriesMergingRowAddition(dec, newRow, smallMember, member, &mergingMember, &isCut, &nonVirtualArc) );
10673 //create the split series. There's two possible configurations, based on whether it contains a cut edge or not
10735 spqr_arc otherMarker = largeIsParent ? markerOfParent(dec, mergingMember) : markerToParent(dec, otherMember);
10739 spqr_node splitNode = newRow->reducedMembers[smallMember].splitHead ? findEffectiveArcHead(dec, otherMarker)
10752 SCIP_CALL( mergeSplitMemberIntoParent(dec, newRow, mergingMember, otherMember, otherMarker, splitArc, TRUE,
10760 SCIP_CALL( mergeSplitMemberIntoParent(dec, newRow, otherMember, mergingMember, splitArc, otherMarker, TRUE,
10795/** Update a parallel member to reflect the addition of the new row, and merge it into the previous members that were
10803 SCIP_Bool largeIsParent, /**< Whether the large member containing previously updated members is
10811 SCIP_CALL( splitParallelMerging(dec, newRow, smallMember, member, &mergeMember, &cutRepresentative) );
10865 spqr_arc otherMarker = largeIsParent ? markerOfParent(dec, mergeMember) : markerToParent(dec, otherMember);
10869 spqr_node largeSplitNode = newRow->reducedMembers[smallMember].splitHead ? findEffectiveArcHead(dec, otherMarker)
10884 SCIP_CALL( mergeSplitMemberIntoParent(dec, newRow, mergeMember, otherMember, otherMarker, splitArc, TRUE,
10892 SCIP_CALL( mergeSplitMemberIntoParent(dec, newRow, otherMember, mergeMember, splitArc, otherMarker, TRUE,
10927/** Update a rigid member to reflect the addition of the new row, and merge it into the previous members that were
10935 SCIP_Bool largeIsParent, /**< Whether the large member containing previously updated members is
10947 spqr_arc smallMarker = largeIsParent ? markerToParent(dec, smallMemberMember) : markerOfParent(dec,
10949 spqr_arc largeMarker = largeIsParent ? markerOfParent(dec, smallMemberMember) : markerToParent(dec,
10964 spqr_arc nextArc = getNextNodeArc(dec, iterArc, splitNode);//Need to do this before we modify the arc
11015 spqr_node largeOtherNode = ( newRowInfo->head == largeMarkerHead || newRowInfo->head == largeMarkerTail )
11025 mergeSplitMemberIntoParent(dec, newRow, smallMemberMember, largeMemberMember, largeMarker, smallMarker, TRUE,
11034 mergeSplitMemberIntoParent(dec, newRow, largeMemberMember, smallMemberMember, smallMarker, largeMarker, TRUE,
11075/** Update a member to reflect the addition of the new row, and merge it into the previous members that were updated. */
11081 SCIP_Bool largeIsParent, /**< Whether the large member containing previously updated members is
11096 SCIP_CALL( splitAndMergeParallel(dec, newRow, smallMember, largeIsParent, newRowInfo, member) );
11101 SCIP_CALL( splitAndMergeSeries(dec, newRow, smallMember, largeIsParent, newRowInfo, member) );
11131 while( newRow->reducedMembers[leaf].numChildren != newRow->reducedMembers[leaf].numPropagatedChildren )
11165 if( childidx == newRow->reducedMembers[id].firstChild + newRow->reducedMembers[id].numChildren )
11173 if( currentchild == baseNode || newRow->reducedMembers[currentchild].type == TYPE_PROPAGATED )
11193/** Update an SPQR tree (a single component of the SPQR forest) to reflect addition of a new row. */
11228 newRowInfo->reversed = arcIsReversedNonRigid(dec, arc) == newRow->cutArcs[cutArc].arcReversed;
11359 BMSfreeBlockMemoryArray(blkmem, &newRow->temporaryColorArray, newRow->memTemporaryColorArray);
11360 BMSfreeBlockMemoryArray(blkmem, &newRow->createReducedMembersCallstack, newRow->memCreateReducedMembersCallstack);
11364 BMSfreeBlockMemoryArray(blkmem, &newRow->intersectionDFSData, newRow->memIntersectionDFSData);
11365 BMSfreeBlockMemoryArray(blkmem, &newRow->intersectionPathParent, newRow->memIntersectionPathParent);
11366 BMSfreeBlockMemoryArray(blkmem, &newRow->intersectionPathDepth, newRow->memIntersectionPathDepth);
11368 BMSfreeBlockMemoryArray(blkmem, &newRow->articulationNodeSearchInfo, newRow->memNodeSearchInfo);
11373 BMSfreeBlockMemoryArray(blkmem, &newRow->decompositionColumnArcs, newRow->memDecompositionColumnArcs);
11374 BMSfreeBlockMemoryArray(blkmem, &newRow->decompositionColumnArcReversed, newRow->memDecompositionColumnArcs);
11417 //Check for each component if the cut arcs propagate through a row tree marker to a cut arc in another component
11421 //In that case, further checking may lead to errors as some invariants that the code assumes will be broken.
11457 SCIP_CALL( transformComponentRowAddition(dec, rowadd, &rowadd->reducedComponents[0], &information) );
11462 SCIP_CALL( createRowArc(dec, information.member, &rowArc, rowadd->newRowIndex, information.reversed) );
11467 setArcHeadAndTail(dec, rowArc, findNode(dec, information.head), findNode(dec, information.tail));
11469 arcSetReversed(dec, rowArc, information.reversed != arcIsReversedNonRigid(dec, information.representative));
11475 SCIP_CALL( createConnectedParallel(dec, rowadd->newColumnArcs, rowadd->newColumnReversed, rowadd->numColumnArcs,
11486 setArcHeadAndTail(dec, markerArc, findNode(dec, information.head), findNode(dec, information.tail));
11494 assert(getNumMemberArcs(dec, information.member) == 2 || getNumMemberArcs(dec, information.member) == 3);
11507 SCIP_CALL( createConnectedParallel(dec, rowadd->newColumnArcs, rowadd->newColumnReversed, rowadd->numColumnArcs,
11513 SCIP_CALL( transformComponentRowAddition(dec, rowadd, &rowadd->reducedComponents[i], &information) );
11525 reorderComponent(dec, information.member);//Make sure the new component is the root of the local decomposition tree
11535 setArcHeadAndTail(dec, markerArc, findNode(dec, information.head), findNode(dec, information.tail));
11543 assert(numConnectedComponents(dec) == ( numDecComponentsBefore - rowadd->numReducedComponents + 1 ));
11558/** A generic data structure that stores a decomposition and can perform both column and row additions. */
11692 int* pathrowstorage, /**< A buffer to hold the computed path's rows. Should have size equal or
11694 SCIP_Bool* pathsignstorage /**< A buffer to store the computed path's row signs. Should have size
11698 return netMatDecDataVerifyCycle(bufmem, dec->dec, column, nonzrowidx, nonzvals, nnonzs, pathrowstorage, pathsignstorage);
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7739
SCIP_Bool SCIPnetmatdecVerifyCycle(BMS_BUFMEM *bufmem, SCIP_NETMATDEC *dec, int column, int *nonzrowidx, double *nonzvals, int nnonzs, int *pathrowstorage, SCIP_Bool *pathsignstorage)
Definition: network.c:11685
SCIP_RETCODE SCIPnetmatdecCreateDiGraph(SCIP_NETMATDEC *dec, BMS_BLKMEM *blkmem, SCIP_DIGRAPH **pdigraph, SCIP_Bool createrowarcs)
Definition: network.c:11701
SCIP_Bool SCIPnetmatdecContainsRow(SCIP_NETMATDEC *dec, int row)
Definition: network.c:11651
void SCIPnetmatdecRemoveComponent(SCIP_NETMATDEC *dec, int *componentrows, int nrows, int *componentcols, int ncols)
Definition: network.c:11667
SCIP_Bool SCIPnetmatdecContainsColumn(SCIP_NETMATDEC *dec, int column)
Definition: network.c:11659
SCIP_RETCODE SCIPnetmatdecTryAddRow(SCIP_NETMATDEC *dec, int row, int *nonzcols, double *nonzvals, int nnonzs, SCIP_Bool *success)
Definition: network.c:11627
SCIP_RETCODE SCIPnetmatdecCreate(BMS_BLKMEM *blkmem, SCIP_NETMATDEC **pdec, int nrows, int ncols)
Definition: network.c:11566
SCIP_RETCODE SCIPnetmatdecTryAddCol(SCIP_NETMATDEC *dec, int column, int *nonzrows, double *nonzvals, int nnonzs, SCIP_Bool *success)
Definition: network.c:11603
SCIP_Bool SCIPnetmatdecIsMinimal(SCIP_NETMATDEC *dec)
Definition: network.c:11678
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
memory allocation routines
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:458
#define BMSallocClearBlockMemoryArray(mem, ptr, num)
Definition: memory.h:455
SCIP_RETCODE SCIPdigraphCreate(SCIP_DIGRAPH **digraph, BMS_BLKMEM *blkmem, int nnodes)
Definition: misc.c:7454
internal miscellaneous methods
static SCIP_RETCODE splitAndMergeRigid(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id smallMember, SCIP_Bool largeIsParent, NewRowInformation *const newRowInfo, spqr_member member)
Definition: network.c:10931
static reduced_member_id createReducedMembersToRoot(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, const spqr_member firstMember)
Definition: network.c:3820
static spqr_arc getPreviousNodeArc(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node node)
Definition: network.c:669
static SCIP_RETCODE transformPath(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, SPQRColReducedComponent *component, NewColInformation *newColInfo)
Definition: network.c:6378
static void mergeMemberArcList(SCIP_NETMATDECDATA *dec, spqr_member toMergeInto, spqr_member toRemove)
Definition: network.c:2683
static SplitOrientation getRelativeOrientationRigid(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedId, spqr_arc arcToNext)
Definition: network.c:9082
static void setTerminalMember(NewColInformation *info, spqr_member member)
Definition: network.c:5542
static SCIP_RETCODE netrowaddCheck(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *rowadd, int row, const int *nonzcols, const double *nonzvals, int nnonzs)
Definition: network.c:11388
static void netMatDecDataRemoveComponent(SCIP_NETMATDECDATA *dec, const int *componentRows, int numRows, const int *componentCols, int numCols)
Definition: network.c:2847
static SCIP_RETCODE splitParallelMerging(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedMember, spqr_member member, spqr_member *const pMergeMember, spqr_arc *const cutRepresentative)
Definition: network.c:10195
static SCIP_Bool nodeIsRepresentative(const SCIP_NETMATDECDATA *dec, spqr_node node)
Definition: network.c:440
static SCIP_RETCODE splitParallel(SCIP_NETMATDECDATA *dec, spqr_member parallel, spqr_arc arc1, spqr_arc arc2, spqr_member *childParallel)
Definition: network.c:5569
static void determinePathTypes(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, SPQRColReducedComponent *component)
Definition: network.c:5055
static void articulationPoints(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, ArticulationNodeInformation *nodeInfo, reduced_member_id reducedMember)
Definition: network.c:7969
static SCIP_RETCODE newColUpdateColInformation(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, spqr_col column, const spqr_row *nonzeroRows, const double *nonzeroValues, int numNonzeros)
Definition: network.c:4206
static void determineSingleSeriesType(SCIP_NETROWADD *newRow, reduced_member_id reducedMember)
Definition: network.c:8854
static void moveArcToNewMember(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_member oldMember, spqr_member newMember)
Definition: network.c:2641
static SCIP_Bool SPQRmemberIsInvalid(spqr_member member)
Definition: network.c:264
static int decompositionGetFundamentalCycleRows(const SCIP_NETMATDECDATA *dec, spqr_col column, spqr_row *output, SCIP_Bool *computedSignStorage)
Definition: network.c:2241
static spqr_member findArcChildMember(SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:1031
static SCIP_RETCODE netMatDecDataCreateDiGraph(SCIP_NETMATDECDATA *dec, BMS_BLKMEM *blkmem, SCIP_DIGRAPH **pdigraph, SCIP_Bool createrowarcs)
Definition: network.c:3111
static ReducedMemberType checkLeaf(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id leaf, spqr_arc toParent, reduced_member_id parent, spqr_arc toChild)
Definition: network.c:5177
static void determineSingleParallelType(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedMember)
Definition: network.c:8813
static SCIP_RETCODE createMarkerPair(SCIP_NETMATDECDATA *dec, spqr_member parentMember, spqr_member childMember, SCIP_Bool parentIsTree, SCIP_Bool childMarkerReversed, SCIP_Bool parentMarkerReversed)
Definition: network.c:2598
static void cleanUpPreviousIteration(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow)
Definition: network.c:7634
static void determineMergeableTypes(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id root)
Definition: network.c:9482
static void determineSplitTypeRigid(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedId, spqr_member member, spqr_arc marker, SplitOrientation previousOrientation)
Definition: network.c:9322
static void rigidGetSplittableArticulationPointsOnPath(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id toCheck, spqr_node firstNode, spqr_node secondNode)
Definition: network.c:8289
static SCIP_RETCODE createConnectedSeries(SCIP_NETMATDECDATA *dec, spqr_row *rows, SCIP_Bool *reversed, int numRows, spqr_col col, spqr_member *pMember)
Definition: network.c:2122
static SCIP_RETCODE createStandaloneParallel(SCIP_NETMATDECDATA *dec, spqr_col *columns, SCIP_Bool *reversed, int num_columns, spqr_row row, spqr_member *pMember)
Definition: network.c:2026
static void zeroOutColors(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const spqr_node firstRemoveNode)
Definition: network.c:7578
static SCIP_RETCODE transformComponentRowAddition(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, SPQRRowReducedComponent *component, NewRowInformation *const newRowInfo)
Definition: network.c:11195
static SCIP_RETCODE allocateTreeSearchMemory(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow)
Definition: network.c:8762
static spqr_member findMemberParent(SCIP_NETMATDECDATA *dec, spqr_member member)
Definition: network.c:985
static SCIP_RETCODE splitAndMergeParallel(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id smallMember, SCIP_Bool largeIsParent, NewRowInformation *const newRowInfo, spqr_member member)
Definition: network.c:10799
static SCIP_RETCODE createPathArcs(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol)
Definition: network.c:4151
static SCIP_RETCODE columnTransformSingleRigid(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMemberId, spqr_member member, NewColInformation *newColInfo)
Definition: network.c:6451
static spqr_member findArcMemberNoCompression(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:967
static void determineSplitTypeNext(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id current, reduced_member_id next, SCIP_Bool currentIsParent)
Definition: network.c:9438
static spqr_arc markerOfParent(const SCIP_NETMATDECDATA *dec, spqr_member member)
Definition: network.c:1970
static SCIP_RETCODE splitSeriesMergingRowAddition(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id reducedMember, const spqr_member member, spqr_member *const mergingMember, SCIP_Bool *const isCut, spqr_arc *representativeEdge)
Definition: network.c:10075
static SCIP_RETCODE splitSeries(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, SPQRColReducedMember *reducedMember, spqr_member member, spqr_member *loopMember, NewColInformation *newColInfo)
Definition: network.c:5607
static spqr_member findMember(SCIP_NETMATDECDATA *dec, spqr_member member)
Definition: network.c:855
static spqr_arc markerToParent(const SCIP_NETMATDECDATA *dec, spqr_member member)
Definition: network.c:1935
static void mergeNodeArcList(SCIP_NETMATDECDATA *dec, spqr_node toMergeInto, spqr_node toRemove)
Definition: network.c:698
static void updateMemberType(const SCIP_NETMATDECDATA *dec, spqr_member member, SPQRMemberType type)
Definition: network.c:1919
static void determineSingleRigidType(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMember)
Definition: network.c:4353
static int numConnectedComponents(const SCIP_NETMATDECDATA *dec)
Definition: network.c:2545
static void determinePathRigidType(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMember, MemberPathType previousType, spqr_arc source, spqr_arc target)
Definition: network.c:4669
static void addArcToMemberArcList(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_member member)
Definition: network.c:1576
static void arcFlipReversed(SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:754
static spqr_node findEffectiveArcTailNoCompression(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:1262
static void determineRigidPath(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, SPQRColReducedMember *redMem)
Definition: network.c:4289
static void removeArcFromNodeArcList(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node node, SCIP_Bool nodeIsHead)
Definition: network.c:1746
static spqr_member findArcChildMemberNoCompression(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:1050
static SCIP_Bool netMatDecDataVerifyCycle(BMS_BUFMEM *bufmem, const SCIP_NETMATDECDATA *dec, int column, const int *nonzrowidx, const double *nonzvals, int num_rows, int *pathrowstorage, SCIP_Bool *pathsignstorage)
Definition: network.c:2432
static SCIP_RETCODE rigidTransformArcIntoCycle(SCIP_NETMATDECDATA *dec, const spqr_member member, const spqr_arc arc, const SCIP_Bool reverseArcDirection, NewRowInformation *const newRowInfo)
Definition: network.c:9614
static SCIP_RETCODE splitFirstLeaf(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id leaf, NewRowInformation *const newRowInfo)
Definition: network.c:10428
static void setTerminalRepresentative(NewColInformation *info, spqr_arc representative)
Definition: network.c:5554
static spqr_member findMemberNoCompression(const SCIP_NETMATDECDATA *dec, spqr_member member)
Definition: network.c:892
static void decreaseNumConnectedComponents(SCIP_NETMATDECDATA *dec, int by)
Definition: network.c:2779
static SplitOrientation getRelativeOrientationParallel(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedId, spqr_arc arcToNext)
Definition: network.c:9133
static void cleanUpMemberInformation(SCIP_NETCOLADD *newCol)
Definition: network.c:4079
static SCIP_RETCODE netcoladdCreate(BMS_BLKMEM *blkmem, SCIP_NETCOLADD **pcoladd)
Definition: network.c:3725
static spqr_node findEffectiveArcHead(SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:1201
static spqr_element arcGetElement(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:1343
static spqr_node mergeNodes(SCIP_NETMATDECDATA *dec, spqr_node first, spqr_node second)
Definition: network.c:808
static spqr_arc getFirstNodeArc(const SCIP_NETMATDECDATA *dec, spqr_node node)
Definition: network.c:596
static SCIP_RETCODE transformComponent(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, SPQRColReducedComponent *component, NewColInformation *newColInfo)
Definition: network.c:6591
static void netrowaddFree(BMS_BLKMEM *blkmem, SCIP_NETROWADD **prowadd)
Definition: network.c:11350
static void setTerminalTail(NewColInformation *info, spqr_node node)
Definition: network.c:5516
static void setArcHeadAndTail(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node head, spqr_node tail)
Definition: network.c:1832
static SCIP_RETCODE columnTransformSingleParallel(SCIP_NETCOLADD *newCol, reduced_member_id reducedMemberId, spqr_member member, NewColInformation *newColInfo)
Definition: network.c:6409
static spqr_arc getNextNodeArcNoCompression(const SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node node)
Definition: network.c:614
static void addArcToNodeArcList(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node node, SCIP_Bool nodeIsHead)
Definition: network.c:1784
static void setDecompositionRowArc(SCIP_NETMATDECDATA *dec, spqr_row row, spqr_arc arc)
Definition: network.c:1398
static SCIP_RETCODE createStandaloneSeries(SCIP_NETMATDECDATA *dec, spqr_row *rows, SCIP_Bool *reversed, int numRows, spqr_col col, spqr_member *pMember)
Definition: network.c:2090
static void updateMemberParentInformation(SCIP_NETMATDECDATA *dec, const spqr_member newMember, const spqr_member toRemove)
Definition: network.c:1950
static void netcoladdFree(BMS_BLKMEM *blkmem, SCIP_NETCOLADD **pcoladd)
Definition: network.c:3789
static SCIP_RETCODE createMarkerPairWithReferences(SCIP_NETMATDECDATA *dec, spqr_member parentMember, spqr_member childMember, SCIP_Bool parentIsTree, SCIP_Bool childMarkerReversed, SCIP_Bool parentMarkerReversed, spqr_arc *parentToChild, spqr_arc *childToParent)
Definition: network.c:2619
static SPQRMemberType getMemberType(const SCIP_NETMATDECDATA *dec, spqr_member member)
Definition: network.c:1904
static void determinePathSeriesType(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMember, spqr_member member, MemberPathType previousType, spqr_arc source, spqr_arc target)
Definition: network.c:4473
static SCIP_RETCODE columnTransformSingleSeries(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMemberId, spqr_member member, NewColInformation *newColInfo)
Definition: network.c:6427
static SCIP_RETCODE netrowaddAdd(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *rowadd)
Definition: network.c:11442
static spqr_node findArcHead(SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:540
static void reorderComponent(SCIP_NETMATDECDATA *dec, spqr_member newRoot)
Definition: network.c:2792
static SCIP_RETCODE transformSingleParallel(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id reducedMember, const spqr_member member, NewRowInformation *info)
Definition: network.c:10061
static SCIP_Bool arcIsChildMarker(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:1065
static SplitOrientation getRelativeOrientationSeries(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedId, spqr_arc arcToNext)
Definition: network.c:9158
static spqr_node findArcTailNoCompression(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:578
static SCIP_RETCODE mergeGivenMemberIntoParent(SCIP_NETMATDECDATA *dec, spqr_member member, spqr_member parent, spqr_arc parentToChild, spqr_arc childToParent, SCIP_Bool headToHead, spqr_member *mergedMember)
Definition: network.c:3052
static void changeLoopToSeries(SCIP_NETMATDECDATA *dec, spqr_member member)
Definition: network.c:2711
static spqr_node largestNodeID(const SCIP_NETMATDECDATA *dec)
Definition: network.c:2536
static void removeArcFromMemberArcList(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_member member)
Definition: network.c:2149
static SCIP_RETCODE netrowaddCreate(BMS_BLKMEM *blkmem, SCIP_NETROWADD **prowadd)
Definition: network.c:11256
static spqr_member findArcMember(SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:951
static SCIP_Bool reducedMemberIsValid(const reduced_member_id id)
Definition: network.c:3493
static SplitOrientation getRelativeOrientation(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedId, spqr_arc arcToNext)
Definition: network.c:9183
static spqr_node findArcTail(SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:520
static spqr_member findMemberParentNoCompression(const SCIP_NETMATDECDATA *dec, spqr_member member)
Definition: network.c:1011
static void determineSingleComponentType(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMember)
Definition: network.c:4374
static spqr_node findArcHeadNoCompression(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:560
static SCIP_RETCODE transformFirstPathMember(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMember, NewColInformation *newColInfo, spqr_arc *representativeArc, spqr_member *mergedMember)
Definition: network.c:5929
static void changeLoopToParallel(SCIP_NETMATDECDATA *dec, spqr_member member)
Definition: network.c:2729
static SCIP_RETCODE transformAndMergeSeries(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id current, reduced_member_id next, spqr_member nextMember, SCIP_Bool nextIsParent, spqr_arc *representativeArc, spqr_member *mergedMember, NewColInformation *info)
Definition: network.c:6111
static SCIP_RETCODE createColumnArc(SCIP_NETMATDECDATA *dec, spqr_member member, spqr_arc *pArc, spqr_col column, SCIP_Bool reversed)
Definition: network.c:1674
static SCIP_Bool netrowaddRemainsNetwork(const SCIP_NETROWADD *rowadd)
Definition: network.c:11551
static void process_arc(spqr_row *cyclearcs, int *num_cycle_arcs, FindCycleCall *callStack, int *callStackSize, spqr_arc arc, const SCIP_NETMATDECDATA *dec, SCIP_Bool *cycledir, SCIP_Bool arcIsReversed)
Definition: network.c:2191
static void propagateComponents(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow)
Definition: network.c:8576
static SCIP_Bool reducedMemberIsInvalid(const reduced_member_id id)
Definition: network.c:3484
static void zeroOutColorsExceptNeighbourhood(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const spqr_node articulationNode, const spqr_node startRemoveNode)
Definition: network.c:7780
static void determineRigidType(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id toCheckMember, const spqr_arc markerToOther, const reduced_member_id otherMember, const spqr_arc markerToCheck)
Definition: network.c:8471
static spqr_element SPQRcolumnToElement(spqr_col column)
Definition: network.c:242
static SCIP_Bool memberIsRepresentative(const SCIP_NETMATDECDATA *dec, spqr_member member)
Definition: network.c:841
static SCIP_RETCODE createMember(SCIP_NETMATDECDATA *dec, SPQRMemberType type, spqr_member *pMember)
Definition: network.c:1692
static SCIP_Bool netMatDecDataContainsColumn(SCIP_NETMATDECDATA *dec, int column)
Definition: network.c:1370
static void createCutArc(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const spqr_arc arc, const reduced_member_id reducedMember, SCIP_Bool reversed)
Definition: network.c:7336
static spqr_node findNodeNoCompression(const SCIP_NETMATDECDATA *dec, spqr_node node)
Definition: network.c:493
static void determinePathParallelType(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMember, spqr_member member, MemberPathType previousType, spqr_arc source, spqr_arc target)
Definition: network.c:4599
static void setTerminalReversed(NewColInformation *info, SCIP_Bool reversed)
Definition: network.c:5530
static spqr_node findEffectiveArcTail(SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:1219
static SCIP_RETCODE createReducedDecompositionCutArcs(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow)
Definition: network.c:7388
static SCIP_RETCODE createRowArc(SCIP_NETMATDECDATA *dec, spqr_member member, spqr_arc *pArc, spqr_row row, SCIP_Bool reversed)
Definition: network.c:1656
static Nodes rigidDetermineCandidateNodesFromAdjacentComponents(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id toCheck)
Definition: network.c:8692
static SCIP_RETCODE netMatDecDataCreate(BMS_BLKMEM *blkmem, SCIP_NETMATDECDATA **pdec, int nrows, int ncols)
Definition: network.c:1439
static void determineSingleRowRigidType(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedMember)
Definition: network.c:8780
static void addArticulationNode(SCIP_NETROWADD *newRow, spqr_node articulationNode)
Definition: network.c:7949
static void determineSeriesType(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id toCheckMember, const spqr_arc markerToOther, const reduced_member_id otherMember, const spqr_arc markerToCheck)
Definition: network.c:8448
static SCIP_RETCODE createArc(SCIP_NETMATDECDATA *dec, spqr_member member, SCIP_Bool reversed, spqr_arc *pArc)
Definition: network.c:1604
static void createPathArc(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, const spqr_arc arc, const reduced_member_id reducedMember, SCIP_Bool reversed)
Definition: network.c:4099
static void arcSetRepresentative(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_arc representative)
Definition: network.c:789
static SCIP_RETCODE constructRowReducedDecomposition(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow)
Definition: network.c:7187
static SCIP_RETCODE createChildMarker(SCIP_NETMATDECDATA *dec, spqr_member member, spqr_member child, SCIP_Bool isTree, spqr_arc *pArc, SCIP_Bool reversed)
Definition: network.c:2554
static SCIP_RETCODE transformAndMerge(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id current, reduced_member_id next, spqr_arc *representativeArc, spqr_member *mergedMember, SCIP_Bool nextIsParent, NewColInformation *info)
Definition: network.c:6334
static spqr_node findEffectiveArcHeadNoCompression(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:1240
static void determineSplitTypeParallel(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedId, spqr_arc marker, SplitOrientation previousOrientation)
Definition: network.c:9263
static spqr_arc getNextMemberArc(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:1546
static spqr_node determineAndColorSplitNode(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id id, spqr_node candidateOne, spqr_node candidateTwo)
Definition: network.c:8870
static int getNumMemberArcs(const SCIP_NETMATDECDATA *dec, spqr_member member)
Definition: network.c:1985
static spqr_member mergeMembers(SCIP_NETMATDECDATA *dec, spqr_member first, spqr_member second)
Definition: network.c:920
static SCIP_RETCODE createParentMarker(SCIP_NETMATDECDATA *dec, spqr_member member, SCIP_Bool isTree, spqr_member parent, spqr_arc parentMarker, spqr_arc *arc, SCIP_Bool reversed)
Definition: network.c:2574
static SCIP_RETCODE mergeTree(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id root, NewRowInformation *const newRowInfo)
Definition: network.c:11120
static spqr_member largestMemberID(const SCIP_NETMATDECDATA *dec)
Definition: network.c:2518
static void rigidConnectedColoring(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id reducedMember, const spqr_node node, SCIP_Bool *const isGood)
Definition: network.c:8144
static void changeArcHead(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node oldHead, spqr_node newHead)
Definition: network.c:1858
static SCIP_RETCODE createConnectedParallel(SCIP_NETMATDECDATA *dec, spqr_col *columns, SCIP_Bool *reversed, int num_columns, spqr_row row, spqr_member *pMember)
Definition: network.c:2059
static SCIP_RETCODE determineLeafReducedMembers(const SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow)
Definition: network.c:7442
static spqr_arc mergeArcSigns(SCIP_NETMATDECDATA *dec, spqr_arc first, spqr_arc second, SCIP_Bool reflectRelative)
Definition: network.c:1285
static void rigidConnectedColoringRecursive(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, spqr_node articulationNode, spqr_node firstProcessNode, COLOR_STATUS firstColor, SCIP_Bool *isGood)
Definition: network.c:8062
static void checkRigidLeaf(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id leaf, spqr_arc toParent, reduced_member_id parent, spqr_arc toChild)
Definition: network.c:5144
static SCIP_RETCODE transformSingleRigid(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id reducedMember, const spqr_member member, NewRowInformation *const newRowInfo)
Definition: network.c:9728
static void intersectionOfAllPaths(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id toCheck, int *const nodeNumPaths)
Definition: network.c:7831
static void determineComponentTypes(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, SPQRColReducedComponent *component)
Definition: network.c:5412
static void arcSetReversed(SCIP_NETMATDECDATA *dec, spqr_arc arc, SCIP_Bool reversed)
Definition: network.c:768
static SCIP_Bool netMatDecDataIsMinimal(const SCIP_NETMATDECDATA *dec)
Definition: network.c:2749
static void clearArcHeadAndTail(SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:1845
static SCIP_Bool arcIsReversedNonRigid(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:1329
static SCIP_RETCODE transformAndMergeRigid(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id current, reduced_member_id next, spqr_member nextMember, SCIP_Bool nextIsParent, spqr_arc *representativeArc, spqr_member *mergedMember, NewColInformation *info)
Definition: network.c:6264
static SCIP_RETCODE newRowUpdateRowInformation(const SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const spqr_row row, const spqr_col *columns, const double *columnValues, const int numColumns)
Definition: network.c:7022
static void propagateCycles(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol)
Definition: network.c:5277
static spqr_node checkNeighbourColoringArticulationNode(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const spqr_node articulationNode, spqr_arc *const adjacentSplittingArc)
Definition: network.c:8219
static ArcSign findArcSign(SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:1121
static SCIP_RETCODE createNode(SCIP_NETMATDECDATA *dec, spqr_node *pNode)
Definition: network.c:1724
static SCIP_RETCODE allocateRigidSearchMemory(const SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow)
Definition: network.c:7469
static SCIP_RETCODE netcoladdCheck(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *coladd, int column, const int *nonzrows, const double *nonzvals, int nnonzs)
Definition: network.c:5439
static SCIP_Bool netMatDecDataContainsRow(SCIP_NETMATDECDATA *dec, int row)
Definition: network.c:1357
static SCIP_Bool netcoladdRemainsNetwork(const SCIP_NETCOLADD *newCol)
Definition: network.c:6647
static spqr_arc getFirstMemberArc(const SCIP_NETMATDECDATA *dec, spqr_member member)
Definition: network.c:1532
static void determineParallelType(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id toCheckMember, const spqr_arc markerToOther, const reduced_member_id otherMember, const spqr_arc markerToCheck)
Definition: network.c:8394
static void changeArcTail(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node oldTail, spqr_node newTail)
Definition: network.c:1874
static SCIP_RETCODE splitAndMergeSeries(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id smallMember, SCIP_Bool largeIsParent, NewRowInformation *const newRowInfo, spqr_member member)
Definition: network.c:10656
static spqr_arc getPreviousMemberArc(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:1561
static spqr_arc getDecompositionColumnArc(const SCIP_NETMATDECDATA *dec, spqr_col col)
Definition: network.c:1413
static void cleanupPreviousIteration(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol)
Definition: network.c:3675
static spqr_arc getNextNodeArc(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node node)
Definition: network.c:641
static spqr_arc getDecompositionRowArc(const SCIP_NETMATDECDATA *dec, spqr_row row)
Definition: network.c:1426
static ArcSign findArcSignNoCompression(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:1172
static SCIP_Bool SPQRelementIsColumn(spqr_element element)
Definition: network.c:203
static SCIP_RETCODE netcoladdAdd(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol)
Definition: network.c:6659
static SCIP_RETCODE computeLeafMembers(const SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol)
Definition: network.c:4262
static void determineSplitTypeFirstLeaf(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedId)
Definition: network.c:8958
static reduced_member_id createRowReducedMembersToRoot(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const spqr_member firstMember)
Definition: network.c:7080
static void rigidFindStarNodes(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id toCheck)
Definition: network.c:7675
static RowReducedMemberType determineType(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id toCheckMember, const spqr_arc markerToOther, const reduced_member_id otherMember, const spqr_arc markerToCheck)
Definition: network.c:8537
static spqr_col SPQRelementToColumn(spqr_element element)
Definition: network.c:232
static SCIP_RETCODE transformAndMergeParallel(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id current, reduced_member_id next, spqr_member nextMember, SCIP_Bool nextIsParent, spqr_arc *representativeArc, spqr_member *mergedMember)
Definition: network.c:6034
static SCIP_RETCODE splitSeriesMerging(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, SPQRColReducedMember *reducedMember, spqr_member member, spqr_arc *pathRepresentative, spqr_arc *nonPathRepresentative, spqr_arc exceptionArc1, spqr_arc exceptionArc2)
Definition: network.c:5789
static void setDecompositionColumnArc(SCIP_NETMATDECDATA *dec, spqr_col col, spqr_arc arc)
Definition: network.c:1383
static void cleanUpRowMemberInformation(SCIP_NETROWADD *newRow)
Definition: network.c:9591
static SCIP_RETCODE mergeSplitMemberIntoParent(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, spqr_member member, spqr_member parent, spqr_arc parentToChild, spqr_arc childToParent, SCIP_Bool headToHead, spqr_node parentNode, spqr_node childNode, spqr_member *mergedMember, spqr_node *arcNodeOne, spqr_node *arcNodeTwo, spqr_node *thirdNode)
Definition: network.c:10577
static SCIP_RETCODE splitParallelRowAddition(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id reducedMember, const spqr_member member, NewRowInformation *const newRowInfo)
Definition: network.c:9864
static SCIP_Bool arcIsRepresentative(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:1105
static void determinePathMemberType(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMember, spqr_member member, MemberPathType previousType, spqr_arc source, spqr_arc target)
Definition: network.c:5008
static SCIP_Bool arcIsTree(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
Definition: network.c:1079
static void determineSplitTypeSeries(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedId, spqr_arc marker, SplitOrientation previousOrientation)
Definition: network.c:9213
static void setTerminalHead(NewColInformation *info, spqr_node node)
Definition: network.c:5502
static SCIP_RETCODE constructReducedDecomposition(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol)
Definition: network.c:3932
static SCIP_RETCODE splitAndMerge(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id smallMember, SCIP_Bool largeIsParent, NewRowInformation *const newRowInfo)
Definition: network.c:11077
public data structures and miscellaneous methods
Methods for detecting network matrices.
SCIP callable library.
Definition: network.c:1093
Definition: network.c:6822
Definition: network.c:6851
Definition: memory.c:2545
Definition: network.c:6844
Definition: network.c:3604
Definition: network.c:6796
Definition: network.c:6830
Definition: network.c:2181
Definition: network.c:3596
Definition: network.c:6837
Definition: network.c:5490
Definition: network.c:7008
Definition: network.c:8682
Definition: network.c:3465
Definition: struct_misc.h:221
Definition: network.c:3610
int memCreateReducedMembersCallStack
Definition: network.c:3650
CreateReducedMembersCallstack * createReducedMembersCallStack
Definition: network.c:3649
SCIP_Bool * decompositionArcReversed
Definition: network.c:3663
SPQRColReducedComponent * reducedComponents
Definition: network.c:3618
Definition: network.c:410
Definition: network.c:6913
int memCreateReducedMembersCallstack
Definition: network.c:6990
ArticulationNodeInformation * articulationNodeSearchInfo
Definition: network.c:6973
SCIP_Bool * decompositionColumnArcReversed
Definition: network.c:6957
SPQRRowReducedComponent * reducedComponents
Definition: network.c:6921
CreateReducedMembersCallstack * createReducedMembersCallstack
Definition: network.c:6989
Definition: network.c:11560
Definition: network.c:3586
reduced_member_id pathEndMembers[2]
Definition: network.c:3590
Definition: network.c:3550
SCIP_Bool nextPathMemberIsParent
Definition: network.c:3578
Definition: network.c:345
Definition: network.c:362
SPQRNetworkDecompositionArcListNode arcListNode
Definition: network.c:369
SPQRNetworkDecompositionArcListNode headArcListNode
Definition: network.c:367
SPQRNetworkDecompositionArcListNode tailArcListNode
Definition: network.c:368
Definition: network.c:389
spqr_member representativeMember
Definition: network.c:390
Definition: network.c:352
spqr_node representativeNode
Definition: network.c:353
Definition: network.c:6906
Definition: network.c:6871
children_idx numPropagatedChildren
Definition: network.c:6881
Definition: network.c:9075