141#define SPQR_INVALID INT_MAX
142#define SPQR_INVALID_ROW SPQR_INVALID
143#define SPQR_INVALID_COL SPQR_INVALID
188#define MARKER_ROW_ELEMENT (INT_MIN)
189#define MARKER_COLUMN_ELEMENT (INT_MAX)
260#define SPQR_INVALID_MEMBER (-1)
285#define SPQR_INVALID_NODE (-1)
313#define SPQR_INVALID_ARC (-1)
446 assert(node < dec->memNodes);
463 assert(node < dec->memNodes);
472 assert(current < dec->memNodes);
483 assert(current < dec->memNodes);
500 assert(node < dec->memNodes);
509 assert(current < dec->memNodes);
527 assert(arc < dec->memArcs);
530 dec->
arcs[arc].
tail = representative;
532 return representative;
547 assert(arc < dec->memArcs);
550 dec->
arcs[arc].
head = representative;
552 return representative;
567 assert(arc < dec->memArcs);
570 return representative;
585 assert(arc < dec->memArcs);
588 return representative;
603 assert(node < dec->memNodes);
622 assert(arc < dec->memArcs);
649 assert(arc < dec->memArcs);
677 assert(arc < dec->memArcs);
742 firstIntoNode->
previous = lastFromArc;
743 lastIntoNode->
next = firstFromArc;
744 firstFromNode->
previous = lastIntoArc;
745 lastFromNode->
next = firstIntoArc;
761 assert(arc < dec->memArcs);
776 assert(arc < dec->memArcs);
797 assert(arc < dec->memArcs);
818 assert(first < dec->memNodes);
819 assert(second < dec->memNodes);
825 if( firstRank > secondRank )
832 if( firstRank == secondRank )
847 assert(member < dec->memMembers);
861 assert(member < dec->memMembers);
871 assert(current < dec->memMembers);
882 assert(current < dec->memMembers);
898 assert(member < dec->memMembers);
908 assert(current < dec->memMembers);
930 assert(first < dec->memMembers);
931 assert(second < dec->memMembers);
937 if( firstRank > secondRank )
942 if( firstRank == secondRank )
958 assert(arc < dec->memArcs);
962 return representative;
974 assert(arc < dec->memArcs);
977 return representative;
991 assert(member < dec->memMembers);
1002 return parent_representative;
1017 assert(member < dec->memMembers);
1026 return parent_representative;
1038 assert(arc < dec->memArcs);
1042 return representative;
1057 assert(arc < dec->memArcs);
1060 return representative;
1072 assert(arc < dec->memArcs);
1086 assert(arc < dec->memArcs);
1111 assert(arc < dec->memArcs);
1127 assert(arc < dec->memArcs);
1138 assert(current < dec->memArcs);
1140 totalReversed = ( totalReversed != dec->
arcs[current].
reversed );
1154 currentReversed = ( currentReversed != wasReversed );
1158 assert(current < dec->memArcs);
1178 assert(arc < dec->memArcs);
1189 assert(current < dec->memArcs);
1191 totalReversed = ( totalReversed != dec->
arcs[current].
reversed );
1296 assert(first < dec->memArcs);
1297 assert(second < dec->memArcs);
1304 if( firstRank > secondRank )
1309 if( firstRank == secondRank )
1316 dec->
arcs[second].
reversed = ( equal == reflectRelative );
1317 if( firstRank > secondRank )
1336 assert(arc < dec->memArcs);
1350 assert(arc < dec->memArcs);
1455 int initialMemArcs = 8;
1457 assert(initialMemArcs > 0);
1458 dec->
memArcs = initialMemArcs;
1471 int initialMemMembers = 8;
1473 assert(initialMemMembers > 0);
1480 int initialMemNodes = 8;
1482 assert(initialMemNodes > 0);
1539 assert(member < dec->memMembers);
1553 assert(arc < dec->memArcs);
1568 assert(arc < dec->memArcs);
1623 int newSize = 2 * dec->
memArcs;
1625 for(
int i = dec->
memArcs + 1;
i < newSize; ++
i )
1772 prevListNode->
next = next_arc;
1804 arcListNode->
next = firstNodeArc;
1805 arcListNode->
previous = lastNodeArc;
1810 previousListNode->
next = arc;
1815 arcListNode->
next = arc;
1897 assert(node < dec->memNodes);
1911 assert(member < dec->memMembers);
1927 assert(member < dec->memMembers);
1942 assert(member < dec->memMembers);
1977 assert(member < dec->memMembers);
1992 assert(member < dec->memMembers);
2042 for(
int i = 0;
i < num_columns; ++
i )
2075 for(
int i = 0;
i < num_columns; ++
i )
2106 for(
int i = 0;
i < numRows; ++
i )
2138 for(
int i = 0;
i < numRows; ++
i )
2193 int* num_cycle_arcs,
2211 callStack[*callStackSize].
arc = other_arc;
2212 callStack[*callStackSize].
reversed = arcIsReversed;
2213 ++( *callStackSize );
2220 cyclearcs[*num_cycle_arcs] = row;
2221 cycledir[*num_cycle_arcs] = arcIsReversed;
2222 ++( *num_cycle_arcs );
2230 callStack[*callStackSize].
arc = other_arc;
2231 callStack[*callStackSize].
reversed = arcIsReversed;
2232 ++( *callStackSize );
2264 int callStackSize = 1;
2265 callStack[0].
arc = arc;
2288 int pathSearchCallStackSize = 0;
2290 while( callStackSize > 0 )
2292 spqr_arc column_arc = callStack[callStackSize - 1].
arc;
2303 assert(pathSearchCallStackSize == 0);
2304 pathSearchCallStack[0].
node = source;
2306 pathSearchCallStackSize++;
2307 while( pathSearchCallStackSize > 0 )
2309 DFSCallData* dfsData = &pathSearchCallStack[pathSearchCallStackSize - 1];
2313 ( pathSearchCallStackSize <= 1 ||
2314 dfsData->
nodeArc != pathSearchCallStack[pathSearchCallStackSize - 2].
nodeArc ))
2320 assert(!nodeVisited[other]);
2321 if( other == target )
2327 pathSearchCallStack[pathSearchCallStackSize].
node = other;
2329 ++pathSearchCallStackSize;
2337 --pathSearchCallStackSize;
2338 dfsData = &pathSearchCallStack[pathSearchCallStackSize - 1];
2345 while( pathSearchCallStackSize > 0 );
2347 for(
int i = 0;
i < pathSearchCallStackSize; ++
i )
2349 if(
arcIsTree(dec, pathSearchCallStack[
i].nodeArc))
2353 pathSearchCallStack[
i].
node;
2354 process_arc(output, &num_rows, callStack, &callStackSize, pathSearchCallStack[
i].nodeArc, dec,
2355 computedSignStorage, arcReversedInPath != reverseEverything);
2359 pathSearchCallStackSize = 0;
2374 process_arc(output, &num_rows, callStack, &callStackSize, iter_arc, dec,
2375 computedSignStorage, ( columnReversed != treeIsReversed ) != reverseEverything);
2380 while( iter_arc != first_arc );
2381 if( tree_count != 1 )
2393 int nontree_count = 0;
2399 process_arc(output, &num_rows, callStack, &callStackSize, iter_arc, dec,
2400 computedSignStorage, ( columnReversed == treeIsReversed ) != reverseEverything);
2408 while( iter_arc != first_arc );
2409 if( nontree_count != 1 )
2436 const int* nonzrowidx,
2437 const double* nonzvals,
2439 int* pathrowstorage,
2447 if( num_found_rows != num_rows )
2456 int * pathRowReversed;
2468 for(
int i = 0;
i < num_rows; ++
i )
2470 pathRow[
i] = pathrowstorage[
i];
2471 pathRowReversed[
i] = pathsignstorage[
i] ? 1 : 0;
2476 int * secondPathRowReversed;
2491 for(
int i = 0;
i < num_rows; ++
i )
2493 secondPathRow[
i] = nonzrowidx[
i];
2494 secondPathRowReversed[
i] = nonzvals[
i] < 0.0 ? 1 : 0;
2500 for(
int i = 0;
i < num_rows; ++
i )
2502 if( pathRow[
i] != secondPathRow[
i] || pathRowReversed[
i] != secondPathRowReversed[
i] )
2612 &childToParentMarker, parentMarkerReversed) );
2632 parentMarkerReversed) );
2649 assert(arc < dec->memArcs);
2717 assert(member < dec->memMembers);
2735 assert(member < dec->memMembers);
2826 newMarkerToParent = oldMarkerOfParent;
2827 markerOfNewParent = oldMarkerToParent;
2849 const int* componentRows,
2851 const int* componentCols,
2858 for(
int i = 0;
i < numRows; ++
i )
2867 for(
int i = 0;
i < numCols; ++
i )
2905 unsigned long dot_head,
2906 unsigned long dot_tail,
2914 char type = typeToChar(member_type);
2915 const char *color =
arcIsTree(dec, arc) ?
",color=red" :
",color=blue";
2921 if( useElementNames )
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);
2927 fprintf(stream,
" %c_%d_%lu [shape=box];\n", type, member, dot_tail);
2928 fprintf(stream,
" %c_%d_%lu [shape=box];\n", type, member, dot_head);
2929 fprintf(stream,
" %c_p_%d [style=dashed];\n", type, member);
2935 if( useElementNames )
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);
2941 fprintf(stream,
" %c_%d_%lu [shape=box];\n", type, member, dot_tail);
2942 fprintf(stream,
" %c_%d_%lu [shape=box];\n", type, member, dot_head);
2943 fprintf(stream,
" %c_c_%d [style=dotted];\n", type, child);
2944 fprintf(stream,
" %c_p_%d -> %c_c_%d [style=dashed,dir=forward];\n", childType, child, type, child);
2948 if( useElementNames )
2961 fprintf(stream,
" %c_%d_%lu -> %c_%d_%lu [label=\"%d \",style=bold%s];\n", type, member, dot_tail, type, member, dot_head,
2963 fprintf(stream,
" %c_%d_%lu [shape=box];\n", type, member, dot_tail);
2964 fprintf(stream,
" %c_%d_%lu [shape=box];\n", type, member, dot_head);
2970void decompositionToDot(
2977 fprintf(stream,
"//decomposition\ndigraph decomposition{\n compound = TRUE;\n");
2982 fprintf(stream,
" subgraph member_%d{\n", member);
2993 arcToDot(stream, dec, arc, arcHead, arcTail, useElementNames);
2996 while( arc != first_arc );
3008 arcToDot(stream, dec, arc, 1, 0, useElementNames);
3012 arcToDot(stream, dec, arc, 0, 1, useElementNames);
3016 while( arc != first_arc );
3021 unsigned long i = 0;
3022 unsigned long num_member_arcs = (
unsigned long)
getNumMemberArcs(dec, member);
3027 unsigned long head =
i;
3028 unsigned long tail = (
i + 1) % num_member_arcs;
3031 unsigned long temp = head;
3035 arcToDot(stream, dec, arc, head, tail, useElementNames);
3039 while( arc != first_arc );
3045 fprintf(stream,
" }\n");
3047 fprintf(stream,
"}\n");
3078 spqr_node parentArcNodes[2] = { parentTail, parentHead };
3079 spqr_node childArcNodes[2] = { childTail, childHead };
3084 spqr_node first = childArcNodes[headToHead ? 0 : 1];
3085 spqr_node second = childArcNodes[headToHead ? 1 : 0];
3088 spqr_node toRemoveFrom = newNode == first ? parentArcNodes[0] : first;
3093 spqr_node toRemoveFrom = newNode == second ? parentArcNodes[1] : second;
3098 spqr_member toRemoveFrom = newMember == member ? parent : member;
3100 if( toRemoveFrom == parent )
3105 *mergedMember = newMember;
3124 int nvertices = nrows + 1;
3129 int* dectographnode;
3131 for(
int i = 0;
i < largestNode; ++
i )
3132 dectographnode[
i] = -1;
3140 int graphfirstarchead;
3141 int graphfirstarctail;
3152 int nextnodeindex = 1;
3160 if( rowprocessed[
i] )
3171 rootmember = parent;
3176 calldata[0].member = rootmember;
3178 calldata[0].graphfirstarchead = 0;
3179 calldata[0].graphfirstarctail = nextnodeindex;
3183 while( ncalldata != 0 )
3186 CallData explore = calldata[ncalldata-1];
3201 dectographnode[exploreHead] = explore.graphfirstarchead;
3202 dectographnode[exploreTail] = explore.graphfirstarctail;
3215 if( dectographnode[head] == -1 )
3217 dectographnode[head] = nextnodeindex;
3220 if( dectographnode[tail] == -1 )
3222 dectographnode[tail] = nextnodeindex;
3234 calldata[ncalldata].member = child;
3235 calldata[ncalldata].arc = toparent;
3236 calldata[ncalldata].graphfirstarchead = dectographnode[head];
3237 calldata[ncalldata].graphfirstarctail = dectographnode[tail];
3244 if( createrowarcs || !
arcIsTree(dec, arc) )
3264 assert(row < dec->memRows);
3265 rowprocessed[row] =
TRUE;
3269 while( arc != firstArc );
3290 calldata[ncalldata].member = child;
3291 calldata[ncalldata].arc = toparent;
3292 calldata[ncalldata].graphfirstarchead = directionsmatch ? explore.graphfirstarchead
3293 : explore.graphfirstarctail;
3294 calldata[ncalldata].graphfirstarctail = directionsmatch ? explore.graphfirstarctail
3295 : explore.graphfirstarchead;
3302 if( createrowarcs || !
arcIsTree(dec, arc) )
3317 explore.graphfirstarchead, (
void*) ind) );
3322 explore.graphfirstarctail, (
void*) ind) );
3330 assert(row < dec->memRows);
3331 rowprocessed[row] =
TRUE;
3335 while( arc != firstArc );
3343 int firstnode = explore.graphfirstarchead;
3344 int secondnode = explore.graphfirstarctail;
3345 for(
int j = 0; j < count; ++j )
3356 calldata[ncalldata].member = child;
3357 calldata[ncalldata].arc = toparent;
3358 calldata[ncalldata].graphfirstarchead = directionsmatch ? firstnode : secondnode;
3359 calldata[ncalldata].graphfirstarctail = directionsmatch ? secondnode : firstnode;
3366 if( createrowarcs || !
arcIsTree(dec, arc) )
3394 rowprocessed[row] =
TRUE;
3398 secondnode = firstnode;
3399 if( j >= count - 2 )
3401 firstnode = explore.graphfirstarctail;
3405 firstnode = nextnodeindex;
3409 assert(arc == explore.arc);
3415 SCIPerrorMessage(
"Can not create graph for unassigned member type, exiting.\n");
3426 assert(nextnodeindex == nvertices);
3439#define INVALID_PATH_ARC (-1)
3480#define INVALID_REDUCED_MEMBER (-1)
3698 if( arc < newCol->memArcsInPath )
3831 callstack[0].
member = firstMember;
3834 while( callDepth >= 0 )
3848 reducedMemberData->
member = member;
3869 assert(callDepth < newCol->memCreateReducedMembersCallStack);
3870 callstack[callDepth].
member = parentMember;
3878 reducedMemberData->
depth = 0;
3892 assert(reducedMember < newCol->numReducedMembers);
3899 *depthMinimizer = reducedMember;
3915 reducedMemberData->
parent = parentReducedMember;
3916 reducedMemberData->
depth = parentReducedMemberData->
depth + 1;
3927 return returnedMember;
4001 *depthMinimizer = reducedMember;
4012 component->
root = reducedMinimizer;
4020 int numTotalChildren = 0;
4027 reducedMember->
firstChild = numTotalChildren;
4045 if( reducedMemberData->
depth <=
4058 parentReducedMemberData->
numChildren] = reducedMember;
4070 assert(rootMember < dec->memMembers);
4112 listNode->
arc = arc;
4124 assert(arc < newCol->memArcsInPath);
4159 int newMaxNumArcs = 2 * maxNumPathArcs;
4166 int newSize = 2 * maxPathArcIndex;
4180 int newSize = 2 * maxNumNodes;
4211 const double* nonzeroValues,
4220 for(
int i = 0;
i < numNonzeros; ++
i )
4314 isValidPath =
FALSE;
4323 isValidPath =
FALSE;
4334 isValidPath =
FALSE;
4383 int numNonPropagatedAdjacent =
4388 ++numNonPropagatedAdjacent;
4391 if( numNonPropagatedAdjacent > 2 )
4421 int countedPathArcs = 0;
4427 if( countedPathArcs == 0 )
4490 int countedPathArcs = 0;
4497 if( countedPathArcs == 0 )
4520 assert(countedPathArcs > 0);
4526 if(( firstReversed == targetReversed ) == reversePath )
4538 if( countedPathArcs > 0 )
4541 SCIP_Bool isGood = isIntoHeadOrOutTail == ( sourceReversed == passesForwards );
4553 SCIP_Bool inSameDirection = sourceReversed == targetReversed;
4556 switch( previousType )
4585 assert(countedPathArcs > 0);
4587 if(
isInto(previousType))
4619 SCIP_Bool inSameDirection = sourceReversed == targetReversed;
4631 SCIP_Bool good = intoHeadOrOutTail == ( pathArcReversed != sourceReversed );
4641 SCIP_Bool swapHeadTail = arcPresent != inSameDirection;
4642 switch( previousType )
4689 SCIP_Bool sourceHeadIsTargetHead = sourceHead == targetHead;
4690 SCIP_Bool sourceTailIsTargetHead = sourceTail == targetHead;
4691 SCIP_Bool sourceHeadIsTargetTail = sourceHead == targetTail;
4692 SCIP_Bool sourceTailIsTargetTail = sourceTail == targetTail;
4694 if( !(sourceHeadIsTargetHead || sourceTailIsTargetHead || sourceHeadIsTargetTail || sourceTailIsTargetTail) )
4701 ( sourceHeadIsTargetHead ? 1 : 0 ) + ( sourceHeadIsTargetTail ? 1 : 0 ) + ( sourceTailIsTargetHead ? 1 : 0 ) +
4702 ( sourceTailIsTargetTail ? 1 : 0 ) == 1);
4704 SCIP_Bool isSourceHead = sourceHeadIsTargetHead || sourceHeadIsTargetTail;
4705 SCIP_Bool isTargetTail = sourceHeadIsTargetTail || sourceTailIsTargetTail;
4706 if(
isHead(previousType) == isSourceHead )
4710 if(
isInto(previousType))
4737 if(
isInto(previousType))
4807 if( isIntoHeadOrOutTail )
4810 if( !startsAtHead && !endsAtTail )
4816 assert(startsAtHead || endsAtTail);
4822 if( !startsAtTail && !endsAtHead )
4828 assert(startsAtTail || endsAtHead);
4838 assert(!(( targetHead == sourceHead && targetTail == sourceTail ) ||
4839 ( targetHead == sourceTail && targetTail == sourceHead )));
4846 if( !(startsAtTargetHead || startsAtTargetTail || endsAtTargetHead || endsAtTargetTail) )
4857 if( startsAtHead && endsAtTail )
4859 outReverse = ( startsAtTargetHead || startsAtTargetTail ) ==
isInto(previousType);
4861 else if( startsAtHead )
4863 outReverse = !
isInto(previousType);
4868 outReverse =
isInto(previousType);
4873 if( startsAtTail && endsAtHead )
4875 outReverse = ( startsAtTargetHead || startsAtTargetTail ) ==
isInto(previousType);
4877 else if( startsAtTail )
4879 outReverse = !
isInto(previousType);
4884 outReverse =
isInto(previousType);
4892 if( startsAtHead && endsAtTail )
4894 outHead = ( startsAtTargetTail || endsAtTargetHead ) ==
isInto(previousType);
4896 else if( startsAtHead )
4898 if( endsAtTargetHead )
4900 outHead =
isInto(previousType);
4902 else if( endsAtTargetTail )
4904 outHead = !
isInto(previousType);
4914 if( startsAtTargetTail )
4916 outHead =
isInto(previousType);
4918 else if( startsAtTargetHead )
4920 outHead = !
isInto(previousType);
4930 if( startsAtTail && endsAtHead )
4932 outHead = ( startsAtTargetTail || endsAtTargetHead ) ==
isInto(previousType);
4934 else if( startsAtTail )
4936 if( endsAtTargetHead )
4938 outHead =
isInto(previousType);
4940 else if( endsAtTargetTail )
4942 outHead = !
isInto(previousType);
4952 if( startsAtTargetTail )
4954 outHead =
isInto(previousType);
4956 else if( startsAtTargetHead )
4958 outHead = !
isInto(previousType);
4974 if(
isInto(previousType) )
4996 if(
isInto(previousType) )
5079 while( reducedMember != component->
root )
5090 previousReducedMember = reducedMember;
5107 childReduced != previousReducedMember )
5109 child = childReduced;
5125 member = childMember;
5126 previousReducedMember = reducedMember;
5127 reducedMember = child;
5163 if( matches || opposite )
5210 createPathArc(dec, newCol, toChild, parent, ( arcPathArcIsReverse == parentReversed ) == pathArcReversed);
5217 int countedPathArcs = 0;
5223 if( countedPathArcs == 0 )
5255 ( parentReversed == firstArcReversed ) != firstArcInPathReverse);
5285 int leafArrayIndex = 0;
5364 child = childReduced;
5443 const int* nonzrows,
5444 const double* nonzvals,
5450 assert(nnonzs == 0 || ( nonzrows && nonzvals ));
5498#define NEWCOLINFORMATION_EMPTY { SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, SPQR_INVALID_NODE, SPQR_INVALID_ARC, FALSE }
5584 SCIP_Bool parentMoved = toParent == arc1 || toParent == arc2;
5626 if( !createPathSeries && !convertOriginal )
5637 *loopMember = parallel;
5651 if( !createPathSeries && convertOriginal )
5656 *loopMember = member;
5668 if( createPathSeries && !convertOriginal )
5703 assert(createPathSeries && convertOriginal);
5733 while( arc != firstArc );
5777 *loopMember = member;
5809 SCIP_Bool createNonPathSeries = numNonPathArcs > 1;
5813 if( createPathSeries )
5824 assert(pathArc != exceptionArc1 && pathArc != exceptionArc2);
5825 parentMoved = parentMoved ||
markerToParent(dec, member) == pathArc;
5836 &ignored, pathRepresentative) );
5841 pathRepresentative, &ignored) );
5856 if( createNonPathSeries )
5867 if( arc != *pathRepresentative && arc != exceptionArc1 && arc != exceptionArc2 )
5887 representativeIsTree = representativeIsTree || !
arcIsTree(dec, exceptionArc2);
5895 inNewReversed, inOldReversed, &ignored, nonPathRepresentative) );
5900 inOldReversed, inNewReversed, nonPathRepresentative, &ignored) );
5906 if( numNonPathArcs != 0 )
5912 if( arc != *pathRepresentative && arc != exceptionArc1 && arc != exceptionArc2 )
5914 *nonPathRepresentative = arc;
5919 while( arc != firstArc );
5955 *mergedMember = member;
5970 target != pathRepresentative && target != nonPathRepresentative && pathRepresentative != nonPathRepresentative);
6016 *representativeArc = target;
6027 *mergedMember = member;
6052 nextMember = childParallel;
6083 while( arc != firstArc );
6096 &newMergedMember) );
6102 &newMergedMember) );
6104 *mergedMember = newMergedMember;
6130 splitSeriesMerging(dec, newCol, redMem, nextMember, &pathRepresentative, &nonPathRepresentative, source, target) );
6138 assert(pathRepresentative != source && nonPathRepresentative != source &&
6139 (
SPQRarcIsInvalid(target) || ( target != pathRepresentative && target != nonPathRepresentative )));
6156 if( hasNonPath && hasTarget )
6174 if( pathStartInHead )
6232 &newMergedMember) );
6238 &newMergedMember) );
6240 *mergedMember = newMergedMember;
6286 &newMergedMember) );
6292 &newMergedMember) );
6295 *mergedMember = newMergedMember;
6351 representativeArc, mergedMember, info) );
6357 representativeArc, mergedMember) );
6363 representativeArc, mergedMember, info) );
6398 transformAndMerge(dec, newCol, current, next, &representativeArc, &mergedMember, nextIsParent, newColInfo));
6437 newColInfo->
member = member;
6482 existingArcWithPath = arc;
6483 pathInSameDirection = ( head == other ) !=
findArcSign(dec, existingArcWithPath).
reversed;
6488 while( arc != firstArc );
6536 &duplicate,
FALSE) );
6545 ¶llelMarker,
FALSE) );
6550 member, existingArcWithPath, ¶llelMarker,
FALSE) );
6700 &markerArc, &ignore) );
6747 TRUE, &ignore, &markerArc) );
6772#define INVALID_CUT_ARC (-1)
7016#define NEWROWINFORMATION_EMPTY { SPQR_INVALID_MEMBER, SPQR_INVALID_NODE, SPQR_INVALID_NODE, SPQR_INVALID_ARC, FALSE }
7027 const double* columnValues,
7028 const int numColumns
7036 for(
int i = 0;
i < numColumns; ++
i )
7089 callstack[0].
member = firstMember;
7092 while( callDepth >= 0 )
7106 reducedMemberData->
member = member;
7130 assert(callDepth < newRow->memCreateReducedMembersCallstack);
7131 callstack[callDepth].
member = parentMember;
7139 reducedMemberData->
depth = 0;
7149 assert(reducedMember < newRow->numReducedMembers);
7156 *depthMinimizer = reducedMember;
7172 reducedMemberData->
parent = parentReducedMember;
7173 reducedMemberData->
depth = parentReducedMemberData->
depth + 1;
7181 return returnedMember;
7254 *depthMinimizer = reducedMember;
7265 component->
root = reducedMinimizer;
7273 int numTotalChildren = 0;
7280 reducedMember->
firstChild = numTotalChildren;
7299 if( reducedMemberData->
depth <=
7312 parentReducedMemberData->
numChildren] = reducedMember;
7324 assert(rootMember < dec->memMembers);
7347 listNode->
arc = arc;
7359 assert(arc < newRow->memIsArcCut);
7475 int maxNumNodes = 2 * dec->
numArcs;
7584 assert(firstRemoveNode < newRow->memNodeColors);
7593 data[0].
node = firstRemoveNode;
7609 assert(otherNode < newRow->memNodeColors);
7694 spqr_node cutArcsHead = reverse ? tail : head;
7695 spqr_node cutArcsTail = reverse ? head : tail;
7707 spqr_node intersectionNodes[2] = {head, tail};
7716 spqr_node effectiveHead = reverse ? tail : head;
7717 spqr_node effectiveTail = reverse ? head : tail;
7718 if( effectiveHead != cutArcsHead )
7722 if( effectiveTail != cutArcsTail )
7728 for(
int i = 0;
i < 2; ++
i )
7730 if( intersectionNodes[
i] != head && intersectionNodes[
i] != tail )
7752 spqr_node splitNode = headSplittable ? cutArcsHead : cutArcsTail;
7759 spqr_arc neighbourArc = firstNodeArc;
7767 }
while( neighbourArc != firstNodeArc );
7797 spqr_node otherNode = articulationNode == head ? tail : head;
7798 neighbourColors[
i] = newRow->
nodeColors[otherNode];
7803 while( artItArc != artFirstArc );
7815 spqr_node otherNode = articulationNode == head ? tail : head;
7816 newRow->
nodeColors[otherNode] = neighbourColors[
i];
7821 while( artItArc != artFirstArc );
7835 int*
const nodeNumPaths
7849 assert(intersectionPathDepth[root] == -1);
7852 int pathSearchCallStackSize = 0;
7854 intersectionPathDepth[root] = 0;
7857 pathSearchCallStack[0].
node = root;
7859 pathSearchCallStackSize++;
7860 while( pathSearchCallStackSize > 0 )
7862 assert(pathSearchCallStackSize <= newRow->memIntersectionDFSData);
7863 DFSCallData* dfsData = &pathSearchCallStack[pathSearchCallStackSize - 1];
7866 ( pathSearchCallStackSize <= 1 ||
7867 dfsData->
nodeArc != pathSearchCallStack[pathSearchCallStackSize - 2].
nodeArc ) )
7875 pathSearchCallStack[pathSearchCallStackSize].
node = other;
7878 assert(intersectionPathDepth[other] == -1);
7880 intersectionPathParent[other] = dfsData->
node;
7881 intersectionPathDepth[other] = pathSearchCallStackSize;
7882 ++pathSearchCallStackSize;
7890 --pathSearchCallStackSize;
7891 dfsData = &pathSearchCallStack[pathSearchCallStackSize - 1];
7898 while( pathSearchCallStackSize > 0 );
7912 int sourceDepth = intersectionPathDepth[source];
7913 int targetDepth = intersectionPathDepth[target];
7914 nodeNumPaths[source]++;
7915 nodeNumPaths[target]++;
7917 while( sourceDepth > targetDepth )
7919 assert(source != target);
7920 source = intersectionPathParent[source];
7921 nodeNumPaths[source]++;
7924 while( targetDepth > sourceDepth )
7926 assert(source != target);
7927 target = intersectionPathParent[target];
7928 nodeNumPaths[target]++;
7931 while( source != target && targetDepth >= 0 )
7933 source = intersectionPathParent[source];
7934 target = intersectionPathParent[target];
7935 nodeNumPaths[source]++;
7936 nodeNumPaths[target]++;
7940 nodeNumPaths[source]--;
7942 assert(source == target);
7978 int rootChildren = 0;
7991 nodeInfo[root_node].
low = time;
7996 if( !arcRemoved[callStack[
depth].arc] )
8001 spqr_node otherNode = node == head ? tail : head;
8002 if( otherNode != callStack[
depth].parent )
8004 if( nodeInfo[otherNode].discoveryTime == 0 )
8019 nodeInfo[otherNode].
low = time;
8025 nodeInfo[node].
low =
MIN(nodeInfo[node].low, nodeInfo[otherNode].discoveryTime);
8035 if(
depth < 0 )
break;
8039 nodeInfo[current_node].
low =
MIN(nodeInfo[current_node].low, nodeInfo[other_node].low);
8041 !callStack[
depth].isAP &&
8042 nodeInfo[current_node].discoveryTime <= nodeInfo[other_node].low )
8049 if( rootChildren > 1 )
8075 data[0].
node = firstProcessNode;
8077 newRow->
nodeColors[firstProcessNode] = firstColor;
8092 if( isArcCut[callData->
arc] && currentColor != otherColor )
8103 if( otherNode != articulationNode )
8107 if( isArcCut[callData->
arc] )
8113 nodeColors[otherNode] = currentColor;
8123 if( isArcCut[callData->
arc] != ( currentColor != otherColor ) )
8165 while( firstArc != memberArc );
8185 firstProcessNode = tail;
8191 firstProcessNode = head;
8223 spqr_arc*
const adjacentSplittingArc
8230 int numFirstSide = 0;
8231 int numSecondSide = 0;
8239 spqr_node otherNode = articulationNode == head ? tail : head;
8243 if( numFirstSide == 0 &&
arcIsTree(dec, moveArc))
8245 firstSideCandidate = otherNode;
8246 firstSideArc = moveArc;
8248 else if( numFirstSide > 0 )
8256 if( numSecondSide == 0 &&
arcIsTree(dec, moveArc))
8258 secondSideCandidate = otherNode;
8259 secondSideArc = moveArc;
8261 else if( numSecondSide > 0 )
8269 while( moveArc != firstArc );
8271 if( numFirstSide == 1 )
8273 *adjacentSplittingArc = firstSideArc;
8274 return firstSideCandidate;
8276 else if( numSecondSide == 1 )
8278 *adjacentSplittingArc = secondSideArc;
8279 return secondSideCandidate;
8302 for(
int i = 0;
i < totalNumNodes; ++
i )
8304 nodeNumPaths[
i] = 0;
8314 for(
int i = 0;
i < totalNumNodes; ++
i )
8316 artNodeInfo[
i].
low = 0;
8327 SCIP_Bool isOnPath = nodeNumPaths[articulationNode] == numCutArcs;
8330 articulationNode == secondNode ) )
8344 &adjacentSplittingArc);
8350 adjacentSplittingNode == secondNode ) )
8357 isArticulationNode =
TRUE;
8361 if( isArticulationNode )
8376 spqr_node otherNode = articulationNode == head ? tail : head;
8380 while( itArc != firstNodeArc );
8408 int countedCutArcs = 0;
8414 if( countedCutArcs == 0 )
8416 isReversed = arcIsReversed;
8418 else if( arcIsReversed != isReversed )
8441 createCutArc(dec, newRow, markerToCheck, otherMember, markerIsReversed != isReversed);
8493 markerHead = markerTail;
8514 createCutArc(dec, newRow, markerToCheck, otherMember, reverse);
8551 determineRigidType(dec, newRow, toCheckMember, markerToOther, otherMember, markerToCheck);
8562 determineSeriesType(dec, newRow, toCheckMember, markerToOther, otherMember, markerToCheck);
8581 int leafArrayIndex = 0;
8644 child = childReduced;
8719 if( pair.
first != head && pair.
first != tail )
8747 if( pair.
first != head && pair.
first != tail )
8824 int countedCutArcs = 0;
8830 if( countedCutArcs == 0 )
8832 isReversed = arcIsReversed;
8834 else if( arcIsReversed != isReversed )
8883 if( splitNode == candidateOne || splitNode == candidateTwo )
8897 while( iterArc != firstNodeArc );
8903 if(
SPQRnodeIsInvalid(splitNode) || ( splitNode != candidateOne && splitNode != candidateTwo ) )
8928 while( iterArc != firstNodeArc );
8944 while( iterArc != firstNodeArc );
8976 int countedCutArcs = 0;
8982 if( countedCutArcs == 0 )
8984 isReversed = arcIsReversed;
8986 else if( arcIsReversed != isReversed )
9016 markerHead = markerTail;
9054 assert(!(( splitNode == markerTail || splitNode == markerHead ) &&
9055 ( otherNode == markerTail || otherNode == markerHead )));
9064 assert(splitNode == markerHead || splitNode == markerTail);
9113 assert(arcHead == splitNode || arcTail == splitNode);
9114 spqr_node other = arcHead == splitNode ? arcTail : arcHead;
9120 orientation.
headSplit = arcHead != splitNode;
9125 orientation.
headSplit = arcHead == splitNode;
9221 int numAdjacentMembers =
9226 ++numAdjacentMembers;
9228 assert(numAdjacentMembers > 1);
9229 if( numAdjacentMembers > 2 )
9275 int countedCutArcs = 0;
9281 if( countedCutArcs == 0 )
9283 isReversed = arcIsReversed;
9285 else if( arcIsReversed != isReversed )
9298 if( countedCutArcs == 0 )
9353 markerHead = markerTail;
9360 if( nodes.
first != markerHead && nodes.
first != markerTail )
9410 assert(splitNode == markerHead || splitNode == markerTail);
9412 spqr_node otherNode = splitNode == markerHead ? markerTail : markerHead;
9553 data[0].
id = nextNode;
9580 data[
depth].
id = currentchild;
9584 baseNode = nextNode;
9632 markerCycleMember = adjacentMember;
9641 markerCycleMember = adjacentMember;
9647 newRowInfo->
member = markerCycleMember;
9650 newRowInfo->
reversed = reverseArcDirection;
9654 newRowInfo->
reversed = !reverseArcDirection;
9697 &cycleMarker,
FALSE) );
9702 member, arc, &cycleMarker,
FALSE) );
9720 newRowInfo->
member = newCycle;
9721 newRowInfo->
reversed = !reverseArcDirection;
9757 reversed, newRowInfo) );
9776 if( arcHead == splitNode )
9789 newRowInfo->
member = member;
9792 newRowInfo->
head = newNode;
9793 newRowInfo->
tail = splitNode;
9797 newRowInfo->
head = splitNode;
9798 newRowInfo->
tail = newNode;
9819 spqr_node otherEnd = otherHead == splitNode ? otherTail : otherHead;
9823 SCIP_Bool changeArcEnd = isCut == isMoveColor;
9826 if( otherHead == splitNode )
9840 if( iterArc == firstNodeArc )
9844 if( changeArcEnd && previousArc == firstNodeArc )
9846 firstNodeArc = iterArc;
9852 newRowInfo->
member = member;
9853 newRowInfo->
head = newNode;
9854 newRowInfo->
tail = splitNode;
9877 SCIP_Bool createCutParallel = numCutArcs > 1;
9878 SCIP_Bool convertOriginalParallel = ( numCutArcs + 1 ) == numParallelArcs;
9895 assert(!( !createCutParallel &&
9896 convertOriginalParallel ));
9897 if( createCutParallel )
9899 if( convertOriginalParallel )
9920 newRowInfo->
member = adjacentMember;
9923 newRowInfo->
reversed = !firstReversed;
9927 newRowInfo->
reversed = firstReversed;
9957 newRowInfo->
member = member;
9998 newRowInfo->
member = newSeries;
10003 newRowInfo->
reversed = firstReversed;
10009 assert(!createCutParallel && !convertOriginalParallel);
10010 assert(numCutArcs == 1);
10051 newRowInfo->
member = newSeries;
10100 if( testArc != splitArc )
10102 otherArc = testArc;
10121 if( arc != splitArc && arc != otherArc )
10123 *representativeEdge = arc;
10128 while( arc != firstArc );
10129 *mergingMember = member;
10153 coTreeToMergingMember =
TRUE;
10167 parentToMergingMember =
TRUE;
10170 coTreeToMergingMember =
TRUE;
10174 if( parentToMergingMember )
10177 representativeEdge, &ignoreArc) );
10183 representativeEdge) );
10186 *mergingMember = mergingSeries;
10207 int numMergeableAdjacent =
10212 numMergeableAdjacent++;
10217 int numBaseSplitAwayArcs =
getNumMemberArcs(dec, member) - numMergeableAdjacent - numCutArcs;
10219 SCIP_Bool createCutParallel = numCutArcs > 1;
10220 SCIP_Bool keepOriginalParallel = numBaseSplitAwayArcs <= 1;
10224 if( createCutParallel && keepOriginalParallel )
10254 *pMergeMember = member;
10256 else if( createCutParallel )
10258 assert(!keepOriginalParallel);
10295 i < newRow->reducedMembers[reducedMember].firstChild +
10308 treeToMergingMember =
TRUE;
10318 parentToMergingMember =
TRUE;
10321 treeToMergingMember =
TRUE;
10329 parentToMergingMember =
TRUE;
10334 if( parentToMergingMember || parentCut )
10337 &ignoreArgument, &noCutRepresentative) );
10342 &noCutRepresentative, &ignoreArgument) );
10344 *pMergeMember = mergingMember;
10346 else if( keepOriginalParallel )
10348 assert(!createCutParallel);
10353 *pMergeMember = member;
10357 assert(!keepOriginalParallel && !createCutParallel);
10371 i < newRow->reducedMembers[reducedMember].firstChild +
10384 treeToMergingMember =
TRUE;
10394 parentToMergingMember =
TRUE;
10397 treeToMergingMember =
TRUE;
10405 parentToMergingMember =
TRUE;
10410 if( parentToMergingMember )
10413 &ignoreArgument, &noCutRepresentative) );
10418 &noCutRepresentative, &ignoreArgument) );
10420 *pMergeMember = mergingMember;
10456 spqr_node splitArcHead = splitArcReversed ? secondNode : firstNode;
10457 spqr_node splitArcTail = splitArcReversed ? firstNode : secondNode;
10458 spqr_node splitNode = splitHead ? splitArcHead : splitArcTail;
10459 spqr_node otherNode = splitHead ? splitArcTail : splitArcHead;
10466 if( arc != cutRepresentative )
10489 if( arc == splitArc )
10499 while( arc != first_arc );
10502 newRowInfo->
member = mergeMember;
10505 newRowInfo->
head = thirdNode;
10506 newRowInfo->
tail = splitNode;
10510 newRowInfo->
head = splitNode;
10511 newRowInfo->
tail = thirdNode;
10532 spqr_node otherEnd = otherHead == splitNode ? otherTail : otherHead;
10537 SCIP_Bool changeArcEnd = isCut == isMoveColor;
10540 if( otherHead == splitNode )
10553 if( iterArc == firstNodeArc )
10557 if( changeArcEnd && previousArc == firstNodeArc )
10559 firstNodeArc = iterArc;
10563 newRowInfo->
head = newNode;
10564 newRowInfo->
tail = splitNode;
10565 newRowInfo->
member = member;
10609 spqr_node parentArcNodes[2] = { parentTail, parentHead };
10610 spqr_node childArcNodes[2] = { childTail, childHead };
10615 spqr_node first = childArcNodes[headToHead ? 0 : 1];
10616 spqr_node second = childArcNodes[headToHead ? 1 : 0];
10619 spqr_node toRemoveFrom = newNode == first ? parentArcNodes[0] : first;
10621 *arcNodeOne = newNode;
10626 spqr_node toRemoveFrom = newNode == second ? parentArcNodes[1] : second;
10628 *arcNodeTwo = newNode;
10633 spqr_node toRemoveFrom = newNode == childNode ? parentNode : childNode;
10635 *thirdNode = newNode;
10640 spqr_member toRemoveFrom = newMember == member ? parent : member;
10642 if( toRemoveFrom == parent )
10647 *mergedMember = newMember;
10692 if( arc == splitArc )
10703 else if( arc == nonVirtualArc )
10730 while( arc != firstArc );
10743 assert(splitNode == newRowInfo->
head || splitNode == newRowInfo->
tail);
10750 if( largeIsParent )
10753 otherNode,
c, &mergedMember,
10761 c, otherNode, &mergedMember,
10768 newRowInfo->
member = mergedMember;
10770 SCIP_Bool splitIsNewRowHead = splitNode == newRowInfo->
head;
10771 if( !splitIsReferenceHead && !splitIsNewRowHead )
10773 newRowInfo->
head = thirdNode;
10774 newRowInfo->
tail = arcNodeOne;
10776 else if( !splitIsReferenceHead && splitIsNewRowHead )
10778 newRowInfo->
head = arcNodeOne;
10779 newRowInfo->
tail = thirdNode;
10781 else if( splitIsReferenceHead && !splitIsNewRowHead )
10783 newRowInfo->
head = thirdNode;
10784 newRowInfo->
tail = arcNodeTwo;
10786 else if( splitIsReferenceHead && splitIsNewRowHead )
10788 newRowInfo->
head = arcNodeTwo;
10789 newRowInfo->
tail = thirdNode;
10826 spqr_node splitArcHead = splitArcReversed ? secondNode : firstNode;
10827 spqr_node splitArcTail = splitArcReversed ? firstNode : secondNode;
10828 spqr_node otherNode = splitHead ? splitArcTail : splitArcHead;
10835 if( arc != cutRepresentative )
10861 while( arc != first_arc );
10873 largeSplitNode == newRowInfo->
head ? newRowInfo->
tail : newRowInfo->
head;
10874 assert(largeSplitNode == newRowInfo->
head || largeSplitNode == newRowInfo->
tail);
10882 if( largeIsParent )
10885 largeOtherNode, thirdNode, &mergedMember,
10888 &mergeNodeThree) );
10893 thirdNode, largeOtherNode, &mergedMember,
10896 &mergeNodeThree) );
10899 newRowInfo->
member = mergedMember;
10902 SCIP_Bool splitIsNewRowHead = largeSplitNode == newRowInfo->
head;
10903 if( !splitIsReferenceHead && !splitIsNewRowHead )
10905 newRowInfo->
head = mergeNodeThree;
10906 newRowInfo->
tail = arcNodeOne;
10908 else if( !splitIsReferenceHead && splitIsNewRowHead )
10910 newRowInfo->
head = arcNodeOne;
10911 newRowInfo->
tail = mergeNodeThree;
10913 else if( splitIsReferenceHead && !splitIsNewRowHead )
10915 newRowInfo->
head = mergeNodeThree;
10916 newRowInfo->
tail = arcNodeTwo;
10918 else if( splitIsReferenceHead && splitIsNewRowHead )
10920 newRowInfo->
head = arcNodeTwo;
10921 newRowInfo->
tail = mergeNodeThree;
10948 largeMemberMember);
10950 largeMemberMember);
10963 spqr_node otherEnd = otherHead == splitNode ? otherTail : otherHead;
10968 SCIP_Bool changeArcEnd = isCut == isMoveColor;
10971 if( otherHead == splitNode )
10979 if( iterArc == smallMarker )
10981 smallOtherNode = splitNode;
10988 if( iterArc == firstNodeArc )
10992 if( changeArcEnd && previousArc == firstNodeArc )
10994 firstNodeArc = iterArc;
11010 largeMarkerHead = largeMarkerTail;
11011 largeMarkerTail = temp;
11013 assert(newRowInfo->
head == largeMarkerHead || newRowInfo->
head == largeMarkerTail ||
11014 newRowInfo->
tail == largeMarkerHead || newRowInfo->
tail == largeMarkerTail);
11015 spqr_node largeOtherNode = ( newRowInfo->
head == largeMarkerHead || newRowInfo->
head == largeMarkerTail )
11016 ? newRowInfo->
tail : newRowInfo->
head;
11022 if( largeIsParent )
11026 largeOtherNode, smallOtherNode, &mergedMember,
11029 &mergeNodeThree) );
11035 smallOtherNode, largeOtherNode, &mergedMember,
11038 &mergeNodeThree) );
11040 newRowInfo->
member = mergedMember;
11042 SCIP_Bool otherIsHead = largeOtherNode == newRowInfo->
head;
11043 SCIP_Bool adjacentToMarkerHead = ( newRowInfo->
tail == largeMarkerHead ||
11044 newRowInfo->
head == largeMarkerHead );
11045 if( adjacentToMarkerHead )
11049 newRowInfo->
head = mergeNodeThree;
11050 newRowInfo->
tail = arcNodeTwo;
11054 newRowInfo->
head = arcNodeTwo;
11055 newRowInfo->
tail = mergeNodeThree;
11062 newRowInfo->
head = mergeNodeThree;
11063 newRowInfo->
tail = arcNodeOne;
11067 newRowInfo->
head = arcNodeOne;
11068 newRowInfo->
tail = mergeNodeThree;
11158 data[0].
id = nextNode;
11161 while(
depth >= 0 )
11182 data[
depth].
id = currentchild;
11186 baseNode = nextNode;
11225 newRowInfo->
member = member;
11392 const int* nonzcols,
11393 const double* nonzvals,
11399 assert(nnonzs == 0 || nonzcols);
11481 &markerArc, &ignore) );
11530 &ignore, &markerArc) );
11669 int* componentrows,
11671 int* componentcols,
11692 int* pathrowstorage,
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
SCIP_Bool SCIPnetmatdecVerifyCycle(BMS_BUFMEM *bufmem, SCIP_NETMATDEC *dec, int column, int *nonzrowidx, double *nonzvals, int nnonzs, int *pathrowstorage, SCIP_Bool *pathsignstorage)
struct SCIP_Netmatdec SCIP_NETMATDEC
SCIP_RETCODE SCIPnetmatdecCreateDiGraph(SCIP_NETMATDEC *dec, BMS_BLKMEM *blkmem, SCIP_DIGRAPH **pdigraph, SCIP_Bool createrowarcs)
SCIP_Bool SCIPnetmatdecContainsRow(SCIP_NETMATDEC *dec, int row)
void SCIPnetmatdecRemoveComponent(SCIP_NETMATDEC *dec, int *componentrows, int nrows, int *componentcols, int ncols)
SCIP_Bool SCIPnetmatdecContainsColumn(SCIP_NETMATDEC *dec, int column)
SCIP_RETCODE SCIPnetmatdecTryAddRow(SCIP_NETMATDEC *dec, int row, int *nonzcols, double *nonzvals, int nnonzs, SCIP_Bool *success)
SCIP_RETCODE SCIPnetmatdecCreate(BMS_BLKMEM *blkmem, SCIP_NETMATDEC **pdec, int nrows, int ncols)
SCIP_RETCODE SCIPnetmatdecTryAddCol(SCIP_NETMATDEC *dec, int column, int *nonzrows, double *nonzvals, int nnonzs, SCIP_Bool *success)
SCIP_Bool SCIPnetmatdecIsMinimal(SCIP_NETMATDEC *dec)
void SCIPnetmatdecFree(SCIP_NETMATDEC **pdec)
void SCIPswapInts(int *value1, int *value2)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
assert(minobj< SCIPgetCutoffbound(scip))
memory allocation routines
#define BMSfreeBlockMemory(mem, ptr)
#define BMSallocBlockMemory(mem, ptr)
#define BMSfreeBufferMemoryArray(mem, ptr)
#define BMSallocBlockMemoryArray(mem, ptr, num)
#define BMSfreeBlockMemoryArray(mem, ptr, num)
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
#define BMSallocClearBlockMemoryArray(mem, ptr, num)
#define BMSallocBufferMemoryArray(mem, ptr, num)
struct BMS_BufMem BMS_BUFMEM
struct BMS_BlkMem BMS_BLKMEM
SCIP_RETCODE SCIPdigraphCreate(SCIP_DIGRAPH **digraph, BMS_BLKMEM *blkmem, int nnodes)
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)
static reduced_member_id createReducedMembersToRoot(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, const spqr_member firstMember)
static spqr_node findNode(SCIP_NETMATDECDATA *dec, spqr_node node)
static spqr_arc getPreviousNodeArc(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node node)
static SCIP_RETCODE transformPath(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, SPQRColReducedComponent *component, NewColInformation *newColInfo)
static void mergeMemberArcList(SCIP_NETMATDECDATA *dec, spqr_member toMergeInto, spqr_member toRemove)
static SCIP_Bool SPQRelementIsRow(spqr_element element)
static SplitOrientation getRelativeOrientationRigid(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedId, spqr_arc arcToNext)
static SCIP_Bool SPQRcolIsValid(spqr_col col)
static void setTerminalMember(NewColInformation *info, spqr_member member)
static SCIP_RETCODE netrowaddCheck(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *rowadd, int row, const int *nonzcols, const double *nonzvals, int nnonzs)
static void netMatDecDataRemoveComponent(SCIP_NETMATDECDATA *dec, const int *componentRows, int numRows, const int *componentCols, int numCols)
static SCIP_RETCODE splitParallelMerging(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedMember, spqr_member member, spqr_member *const pMergeMember, spqr_arc *const cutRepresentative)
static SCIP_Bool nodeIsRepresentative(const SCIP_NETMATDECDATA *dec, spqr_node node)
static SCIP_Bool SPQRnodeIsValid(spqr_node node)
static SCIP_RETCODE splitParallel(SCIP_NETMATDECDATA *dec, spqr_member parallel, spqr_arc arc1, spqr_arc arc2, spqr_member *childParallel)
static void determinePathTypes(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, SPQRColReducedComponent *component)
static void articulationPoints(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, ArticulationNodeInformation *nodeInfo, reduced_member_id reducedMember)
@ REDUCEDMEMBER_TYPE_NOT_NETWORK
@ REDUCEDMEMBER_TYPE_MERGED
@ REDUCEDMEMBER_TYPE_UNASSIGNED
@ REDUCEDMEMBER_TYPE_CYCLE
static SCIP_RETCODE newColUpdateColInformation(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, spqr_col column, const spqr_row *nonzeroRows, const double *nonzeroValues, int numNonzeros)
static SCIP_Bool cutArcIsInvalid(const cut_arc_id arc)
static void determineSingleSeriesType(SCIP_NETROWADD *newRow, reduced_member_id reducedMember)
static void moveArcToNewMember(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_member oldMember, spqr_member newMember)
static SCIP_Bool SPQRarcIsValid(spqr_arc arc)
static SCIP_Bool SPQRmemberIsInvalid(spqr_member member)
static int decompositionGetFundamentalCycleRows(const SCIP_NETMATDECDATA *dec, spqr_col column, spqr_row *output, SCIP_Bool *computedSignStorage)
static spqr_member findArcChildMember(SCIP_NETMATDECDATA *dec, spqr_arc arc)
static SCIP_RETCODE netMatDecDataCreateDiGraph(SCIP_NETMATDECDATA *dec, BMS_BLKMEM *blkmem, SCIP_DIGRAPH **pdigraph, SCIP_Bool createrowarcs)
static ReducedMemberType checkLeaf(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id leaf, spqr_arc toParent, reduced_member_id parent, spqr_arc toChild)
static void determineSingleParallelType(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedMember)
static spqr_element SPQRrowToElement(spqr_row row)
static SCIP_RETCODE createMarkerPair(SCIP_NETMATDECDATA *dec, spqr_member parentMember, spqr_member childMember, SCIP_Bool parentIsTree, SCIP_Bool childMarkerReversed, SCIP_Bool parentMarkerReversed)
static void cleanUpPreviousIteration(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow)
static void determineMergeableTypes(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id root)
static SCIP_Bool pathArcIsValid(const path_arc_id arc)
static void determineSplitTypeRigid(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedId, spqr_member member, spqr_arc marker, SplitOrientation previousOrientation)
static void rigidGetSplittableArticulationPointsOnPath(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id toCheck, spqr_node firstNode, spqr_node secondNode)
static SCIP_RETCODE createConnectedSeries(SCIP_NETMATDECDATA *dec, spqr_row *rows, SCIP_Bool *reversed, int numRows, spqr_col col, spqr_member *pMember)
#define MARKER_ROW_ELEMENT
static SCIP_RETCODE createStandaloneParallel(SCIP_NETMATDECDATA *dec, spqr_col *columns, SCIP_Bool *reversed, int num_columns, spqr_row row, spqr_member *pMember)
static void zeroOutColors(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const spqr_node firstRemoveNode)
static SCIP_RETCODE transformComponentRowAddition(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, SPQRRowReducedComponent *component, NewRowInformation *const newRowInfo)
static SCIP_RETCODE allocateTreeSearchMemory(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow)
static spqr_member findMemberParent(SCIP_NETMATDECDATA *dec, spqr_member member)
static SCIP_RETCODE splitAndMergeParallel(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id smallMember, SCIP_Bool largeIsParent, NewRowInformation *const newRowInfo, spqr_member member)
static SCIP_RETCODE createPathArcs(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol)
static SCIP_RETCODE columnTransformSingleRigid(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMemberId, spqr_member member, NewColInformation *newColInfo)
static spqr_member findArcMemberNoCompression(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
static void determineSplitTypeNext(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id current, reduced_member_id next, SCIP_Bool currentIsParent)
static spqr_arc markerOfParent(const SCIP_NETMATDECDATA *dec, spqr_member member)
static SCIP_RETCODE splitSeriesMergingRowAddition(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id reducedMember, const spqr_member member, spqr_member *const mergingMember, SCIP_Bool *const isCut, spqr_arc *representativeEdge)
static SCIP_RETCODE splitSeries(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, SPQRColReducedMember *reducedMember, spqr_member member, spqr_member *loopMember, NewColInformation *newColInfo)
static spqr_member findMember(SCIP_NETMATDECDATA *dec, spqr_member member)
static spqr_arc markerToParent(const SCIP_NETMATDECDATA *dec, spqr_member member)
static void mergeNodeArcList(SCIP_NETMATDECDATA *dec, spqr_node toMergeInto, spqr_node toRemove)
static void updateMemberType(const SCIP_NETMATDECDATA *dec, spqr_member member, SPQRMemberType type)
static void determineSingleRigidType(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMember)
#define NEWROWINFORMATION_EMPTY
static int numConnectedComponents(const SCIP_NETMATDECDATA *dec)
static void determinePathRigidType(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMember, MemberPathType previousType, spqr_arc source, spqr_arc target)
static void addArcToMemberArcList(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_member member)
static void arcFlipReversed(SCIP_NETMATDECDATA *dec, spqr_arc arc)
static spqr_node findEffectiveArcTailNoCompression(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
#define INVALID_REDUCED_MEMBER
static void determineRigidPath(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, SPQRColReducedMember *redMem)
static void removeArcFromNodeArcList(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node node, SCIP_Bool nodeIsHead)
#define SPQR_INVALID_MEMBER
static spqr_member findArcChildMemberNoCompression(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
static SCIP_Bool netMatDecDataVerifyCycle(BMS_BUFMEM *bufmem, const SCIP_NETMATDECDATA *dec, int column, const int *nonzrowidx, const double *nonzvals, int num_rows, int *pathrowstorage, SCIP_Bool *pathsignstorage)
static SCIP_RETCODE rigidTransformArcIntoCycle(SCIP_NETMATDECDATA *dec, const spqr_member member, const spqr_arc arc, const SCIP_Bool reverseArcDirection, NewRowInformation *const newRowInfo)
static int nodeDegree(SCIP_NETMATDECDATA *dec, spqr_node node)
static int getNumMembers(const SCIP_NETMATDECDATA *dec)
static SCIP_RETCODE splitFirstLeaf(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id leaf, NewRowInformation *const newRowInfo)
static void setTerminalRepresentative(NewColInformation *info, spqr_arc representative)
static spqr_member findMemberNoCompression(const SCIP_NETMATDECDATA *dec, spqr_member member)
static void decreaseNumConnectedComponents(SCIP_NETMATDECDATA *dec, int by)
static SplitOrientation getRelativeOrientationParallel(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedId, spqr_arc arcToNext)
static void cleanUpMemberInformation(SCIP_NETCOLADD *newCol)
static SCIP_RETCODE netcoladdCreate(BMS_BLKMEM *blkmem, SCIP_NETCOLADD **pcoladd)
static spqr_node findEffectiveArcHead(SCIP_NETMATDECDATA *dec, spqr_arc arc)
static spqr_element arcGetElement(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
static SCIP_Bool SPQRrowIsValid(spqr_row row)
static spqr_node mergeNodes(SCIP_NETMATDECDATA *dec, spqr_node first, spqr_node second)
static spqr_arc getFirstNodeArc(const SCIP_NETMATDECDATA *dec, spqr_node node)
static SCIP_RETCODE transformComponent(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, SPQRColReducedComponent *component, NewColInformation *newColInfo)
static void netrowaddFree(BMS_BLKMEM *blkmem, SCIP_NETROWADD **prowadd)
static void setTerminalTail(NewColInformation *info, spqr_node node)
static void setArcHeadAndTail(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node head, spqr_node tail)
static SCIP_RETCODE columnTransformSingleParallel(SCIP_NETCOLADD *newCol, reduced_member_id reducedMemberId, spqr_member member, NewColInformation *newColInfo)
static spqr_arc getNextNodeArcNoCompression(const SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node node)
static SCIP_Bool isHead(MemberPathType type)
static void addArcToNodeArcList(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node node, SCIP_Bool nodeIsHead)
static void setDecompositionRowArc(SCIP_NETMATDECDATA *dec, spqr_row row, spqr_arc arc)
static SCIP_RETCODE createStandaloneSeries(SCIP_NETMATDECDATA *dec, spqr_row *rows, SCIP_Bool *reversed, int numRows, spqr_col col, spqr_member *pMember)
static void updateMemberParentInformation(SCIP_NETMATDECDATA *dec, const spqr_member newMember, const spqr_member toRemove)
static void netcoladdFree(BMS_BLKMEM *blkmem, SCIP_NETCOLADD **pcoladd)
static SCIP_Bool SPQRmemberIsValid(spqr_member member)
static SCIP_RETCODE createMarkerPairWithReferences(SCIP_NETMATDECDATA *dec, spqr_member parentMember, spqr_member childMember, SCIP_Bool parentIsTree, SCIP_Bool childMarkerReversed, SCIP_Bool parentMarkerReversed, spqr_arc *parentToChild, spqr_arc *childToParent)
static SPQRMemberType getMemberType(const SCIP_NETMATDECDATA *dec, spqr_member member)
static void determinePathSeriesType(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMember, spqr_member member, MemberPathType previousType, spqr_arc source, spqr_arc target)
static SCIP_RETCODE columnTransformSingleSeries(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMemberId, spqr_member member, NewColInformation *newColInfo)
static SCIP_RETCODE netrowaddAdd(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *rowadd)
static spqr_node findArcHead(SCIP_NETMATDECDATA *dec, spqr_arc arc)
static void reorderComponent(SCIP_NETMATDECDATA *dec, spqr_member newRoot)
static SCIP_RETCODE transformSingleParallel(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id reducedMember, const spqr_member member, NewRowInformation *info)
static SCIP_Bool arcIsChildMarker(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
static SplitOrientation getRelativeOrientationSeries(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedId, spqr_arc arcToNext)
static spqr_node findArcTailNoCompression(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
static SCIP_RETCODE mergeGivenMemberIntoParent(SCIP_NETMATDECDATA *dec, spqr_member member, spqr_member parent, spqr_arc parentToChild, spqr_arc childToParent, SCIP_Bool headToHead, spqr_member *mergedMember)
static SCIP_Bool isInto(MemberPathType type)
static void changeLoopToSeries(SCIP_NETMATDECDATA *dec, spqr_member member)
static spqr_node largestNodeID(const SCIP_NETMATDECDATA *dec)
static void removeArcFromMemberArcList(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_member member)
static SCIP_RETCODE netrowaddCreate(BMS_BLKMEM *blkmem, SCIP_NETROWADD **prowadd)
static spqr_member findArcMember(SCIP_NETMATDECDATA *dec, spqr_arc arc)
static SCIP_Bool reducedMemberIsValid(const reduced_member_id id)
static SplitOrientation getRelativeOrientation(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedId, spqr_arc arcToNext)
static spqr_node findArcTail(SCIP_NETMATDECDATA *dec, spqr_arc arc)
static spqr_member findMemberParentNoCompression(const SCIP_NETMATDECDATA *dec, spqr_member member)
static void determineSingleComponentType(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMember)
static spqr_node findArcHeadNoCompression(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
static SCIP_RETCODE transformFirstPathMember(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMember, NewColInformation *newColInfo, spqr_arc *representativeArc, spqr_member *mergedMember)
static void changeLoopToParallel(SCIP_NETMATDECDATA *dec, spqr_member member)
static SCIP_RETCODE transformAndMergeSeries(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id current, reduced_member_id next, spqr_member nextMember, SCIP_Bool nextIsParent, spqr_arc *representativeArc, spqr_member *mergedMember, NewColInformation *info)
static SCIP_RETCODE createColumnArc(SCIP_NETMATDECDATA *dec, spqr_member member, spqr_arc *pArc, spqr_col column, SCIP_Bool reversed)
static SCIP_Bool netrowaddRemainsNetwork(const SCIP_NETROWADD *rowadd)
static void process_arc(spqr_row *cyclearcs, int *num_cycle_arcs, FindCycleCall *callStack, int *callStackSize, spqr_arc arc, const SCIP_NETMATDECDATA *dec, SCIP_Bool *cycledir, SCIP_Bool arcIsReversed)
static void propagateComponents(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow)
static SCIP_Bool reducedMemberIsInvalid(const reduced_member_id id)
static void zeroOutColorsExceptNeighbourhood(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const spqr_node articulationNode, const spqr_node startRemoveNode)
static void determineRigidType(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id toCheckMember, const spqr_arc markerToOther, const reduced_member_id otherMember, const spqr_arc markerToCheck)
static spqr_element SPQRcolumnToElement(spqr_col column)
static SCIP_Bool memberIsRepresentative(const SCIP_NETMATDECDATA *dec, spqr_member member)
static SCIP_RETCODE createMember(SCIP_NETMATDECDATA *dec, SPQRMemberType type, spqr_member *pMember)
static SCIP_Bool netMatDecDataContainsColumn(SCIP_NETMATDECDATA *dec, int column)
static void createCutArc(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const spqr_arc arc, const reduced_member_id reducedMember, SCIP_Bool reversed)
static spqr_node findNodeNoCompression(const SCIP_NETMATDECDATA *dec, spqr_node node)
static void determinePathParallelType(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMember, spqr_member member, MemberPathType previousType, spqr_arc source, spqr_arc target)
static void setTerminalReversed(NewColInformation *info, SCIP_Bool reversed)
static spqr_node findEffectiveArcTail(SCIP_NETMATDECDATA *dec, spqr_arc arc)
static SCIP_RETCODE createReducedDecompositionCutArcs(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow)
static SCIP_RETCODE createRowArc(SCIP_NETMATDECDATA *dec, spqr_member member, spqr_arc *pArc, spqr_row row, SCIP_Bool reversed)
static Nodes rigidDetermineCandidateNodesFromAdjacentComponents(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id toCheck)
#define NEWCOLINFORMATION_EMPTY
static SCIP_RETCODE netMatDecDataCreate(BMS_BLKMEM *blkmem, SCIP_NETMATDECDATA **pdec, int nrows, int ncols)
spqr_matrix_size spqr_col
static void determineSingleRowRigidType(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedMember)
static void addArticulationNode(SCIP_NETROWADD *newRow, spqr_node articulationNode)
static void determineSeriesType(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id toCheckMember, const spqr_arc markerToOther, const reduced_member_id otherMember, const spqr_arc markerToCheck)
static SCIP_RETCODE createArc(SCIP_NETMATDECDATA *dec, spqr_member member, SCIP_Bool reversed, spqr_arc *pArc)
static void createPathArc(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, const spqr_arc arc, const reduced_member_id reducedMember, SCIP_Bool reversed)
static void netMatDecDataFree(SCIP_NETMATDECDATA **pdec)
static void arcSetRepresentative(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_arc representative)
static SCIP_RETCODE constructRowReducedDecomposition(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow)
static SCIP_RETCODE createChildMarker(SCIP_NETMATDECDATA *dec, spqr_member member, spqr_member child, SCIP_Bool isTree, spqr_arc *pArc, SCIP_Bool reversed)
static SCIP_RETCODE transformAndMerge(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id current, reduced_member_id next, spqr_arc *representativeArc, spqr_member *mergedMember, SCIP_Bool nextIsParent, NewColInformation *info)
static spqr_node findEffectiveArcHeadNoCompression(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
#define SPQR_INVALID_NODE
static void determineSplitTypeParallel(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedId, spqr_arc marker, SplitOrientation previousOrientation)
static spqr_arc getNextMemberArc(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
static spqr_node determineAndColorSplitNode(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id id, spqr_node candidateOne, spqr_node candidateTwo)
static int getNumMemberArcs(const SCIP_NETMATDECDATA *dec, spqr_member member)
#define MARKER_COLUMN_ELEMENT
static spqr_member mergeMembers(SCIP_NETMATDECDATA *dec, spqr_member first, spqr_member second)
static SCIP_RETCODE createParentMarker(SCIP_NETMATDECDATA *dec, spqr_member member, SCIP_Bool isTree, spqr_member parent, spqr_arc parentMarker, spqr_arc *arc, SCIP_Bool reversed)
static SCIP_RETCODE mergeTree(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id root, NewRowInformation *const newRowInfo)
static spqr_member largestMemberID(const SCIP_NETMATDECDATA *dec)
static void rigidConnectedColoring(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id reducedMember, const spqr_node node, SCIP_Bool *const isGood)
static void changeArcHead(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node oldHead, spqr_node newHead)
static SCIP_RETCODE createConnectedParallel(SCIP_NETMATDECDATA *dec, spqr_col *columns, SCIP_Bool *reversed, int num_columns, spqr_row row, spqr_member *pMember)
static SCIP_RETCODE determineLeafReducedMembers(const SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow)
static spqr_arc mergeArcSigns(SCIP_NETMATDECDATA *dec, spqr_arc first, spqr_arc second, SCIP_Bool reflectRelative)
static SCIP_Bool SPQRarcIsInvalid(spqr_arc arc)
static int getNumNodes(const SCIP_NETMATDECDATA *dec)
static void rigidConnectedColoringRecursive(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, spqr_node articulationNode, spqr_node firstProcessNode, COLOR_STATUS firstColor, SCIP_Bool *isGood)
static void checkRigidLeaf(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id leaf, spqr_arc toParent, reduced_member_id parent, spqr_arc toChild)
static SCIP_RETCODE transformSingleRigid(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id reducedMember, const spqr_member member, NewRowInformation *const newRowInfo)
static SCIP_Bool pathArcIsInvalid(const path_arc_id arc)
static void intersectionOfAllPaths(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id toCheck, int *const nodeNumPaths)
static void determineComponentTypes(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, SPQRColReducedComponent *component)
static SCIP_Bool SPQRnodeIsInvalid(spqr_node node)
static spqr_row SPQRelementToRow(spqr_element element)
static void arcSetReversed(SCIP_NETMATDECDATA *dec, spqr_arc arc, SCIP_Bool reversed)
static SCIP_Bool netMatDecDataIsMinimal(const SCIP_NETMATDECDATA *dec)
static void clearArcHeadAndTail(SCIP_NETMATDECDATA *dec, spqr_arc arc)
static SCIP_Bool arcIsReversedNonRigid(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
static SCIP_RETCODE transformAndMergeRigid(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id current, reduced_member_id next, spqr_member nextMember, SCIP_Bool nextIsParent, spqr_arc *representativeArc, spqr_member *mergedMember, NewColInformation *info)
static SCIP_RETCODE newRowUpdateRowInformation(const SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const spqr_row row, const spqr_col *columns, const double *columnValues, const int numColumns)
static void propagateCycles(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol)
static spqr_node checkNeighbourColoringArticulationNode(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const spqr_node articulationNode, spqr_arc *const adjacentSplittingArc)
static ArcSign findArcSign(SCIP_NETMATDECDATA *dec, spqr_arc arc)
static SCIP_RETCODE createNode(SCIP_NETMATDECDATA *dec, spqr_node *pNode)
static SCIP_RETCODE allocateRigidSearchMemory(const SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow)
static SCIP_RETCODE netcoladdCheck(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *coladd, int column, const int *nonzrows, const double *nonzvals, int nnonzs)
static SCIP_Bool netMatDecDataContainsRow(SCIP_NETMATDECDATA *dec, int row)
static SCIP_Bool netcoladdRemainsNetwork(const SCIP_NETCOLADD *newCol)
static spqr_arc getFirstMemberArc(const SCIP_NETMATDECDATA *dec, spqr_member member)
static void determineParallelType(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id toCheckMember, const spqr_arc markerToOther, const reduced_member_id otherMember, const spqr_arc markerToCheck)
static void changeArcTail(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node oldTail, spqr_node newTail)
static SCIP_RETCODE splitAndMergeSeries(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id smallMember, SCIP_Bool largeIsParent, NewRowInformation *const newRowInfo, spqr_member member)
static spqr_arc getPreviousMemberArc(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
static spqr_arc getDecompositionColumnArc(const SCIP_NETMATDECDATA *dec, spqr_col col)
static void cleanupPreviousIteration(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol)
spqr_matrix_size spqr_row
static spqr_arc getNextNodeArc(SCIP_NETMATDECDATA *dec, spqr_arc arc, spqr_node node)
static spqr_arc getDecompositionRowArc(const SCIP_NETMATDECDATA *dec, spqr_row row)
static ArcSign findArcSignNoCompression(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
static SCIP_Bool SPQRelementIsColumn(spqr_element element)
static SCIP_RETCODE netcoladdAdd(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol)
static SCIP_RETCODE computeLeafMembers(const SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol)
static void determineSplitTypeFirstLeaf(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedId)
static reduced_member_id createRowReducedMembersToRoot(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const spqr_member firstMember)
static void rigidFindStarNodes(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id toCheck)
static RowReducedMemberType determineType(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id toCheckMember, const spqr_arc markerToOther, const reduced_member_id otherMember, const spqr_arc markerToCheck)
static spqr_col SPQRelementToColumn(spqr_element element)
static SCIP_Bool cutArcIsValid(const cut_arc_id arc)
static SCIP_RETCODE transformAndMergeParallel(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id current, reduced_member_id next, spqr_member nextMember, SCIP_Bool nextIsParent, spqr_arc *representativeArc, spqr_member *mergedMember)
static SCIP_RETCODE splitSeriesMerging(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, SPQRColReducedMember *reducedMember, spqr_member member, spqr_arc *pathRepresentative, spqr_arc *nonPathRepresentative, spqr_arc exceptionArc1, spqr_arc exceptionArc2)
static SCIP_Bool SPQRrowIsInvalid(spqr_row row)
static void setDecompositionColumnArc(SCIP_NETMATDECDATA *dec, spqr_col col, spqr_arc arc)
static void cleanUpRowMemberInformation(SCIP_NETROWADD *newRow)
static SCIP_RETCODE mergeSplitMemberIntoParent(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, spqr_member member, spqr_member parent, spqr_arc parentToChild, spqr_arc childToParent, SCIP_Bool headToHead, spqr_node parentNode, spqr_node childNode, spqr_member *mergedMember, spqr_node *arcNodeOne, spqr_node *arcNodeTwo, spqr_node *thirdNode)
static SCIP_RETCODE splitParallelRowAddition(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, const reduced_member_id reducedMember, const spqr_member member, NewRowInformation *const newRowInfo)
static SCIP_Bool arcIsRepresentative(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
static void determinePathMemberType(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol, reduced_member_id reducedMember, spqr_member member, MemberPathType previousType, spqr_arc source, spqr_arc target)
static spqr_arc largestArcID(const SCIP_NETMATDECDATA *dec)
static SCIP_Bool arcIsTree(const SCIP_NETMATDECDATA *dec, spqr_arc arc)
static void determineSplitTypeSeries(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id reducedId, spqr_arc marker, SplitOrientation previousOrientation)
static void setTerminalHead(NewColInformation *info, spqr_node node)
static SCIP_RETCODE constructReducedDecomposition(SCIP_NETMATDECDATA *dec, SCIP_NETCOLADD *newCol)
static SCIP_Bool SPQRcolIsInvalid(spqr_col col)
static SCIP_RETCODE splitAndMerge(SCIP_NETMATDECDATA *dec, SCIP_NETROWADD *newRow, reduced_member_id smallMember, SCIP_Bool largeIsParent, NewRowInformation *const newRowInfo)
@ SPQR_MEMBERTYPE_PARALLEL
@ SPQR_MEMBERTYPE_UNASSIGNED
public data structures and miscellaneous methods
Methods for detecting network matrices.
reduced_member_id reducedMember
reduced_member_id rootDepthMinimizer
children_idx currentChild
SPQRColReducedMember * reducedMembers
int numDecompositionRowArcs
spqr_member * leafMembers
PathArcListNode * pathArcs
MemberInfo * memberInformation
SCIP_Bool * arcInPathReversed
int memCreateReducedMembersCallStack
int memDecompositionRowArcs
CreateReducedMembersCallstack * createReducedMembersCallStack
path_arc_id firstOverallPathArc
SCIP_Bool * decompositionArcReversed
spqr_arc * decompositionRowArcs
SCIP_Bool * newRowArcReversed
SPQRColReducedComponent * reducedComponents
reduced_member_id * childrenStorage
SPQRNetworkDecompositionArc * arcs
SPQRNetworkDecompositionMember * members
SPQRNetworkDecompositionNode * nodes
int numConnectedComponents
int memCreateReducedMembersCallstack
ArticulationNodeInformation * articulationNodeSearchInfo
COLOR_STATUS * temporaryColorArray
MemberInfo * memberInformation
SCIP_Bool * newColumnReversed
reduced_member_id * childrenStorage
SCIP_Bool * decompositionColumnArcReversed
int memDecompositionColumnArcs
ColorDFSCallData * colorDFSData
ArticulationPointCallStack * artDFSData
DFSCallData * intersectionDFSData
int memIntersectionDFSData
int memTemporaryColorArray
SPQRRowReducedMember * reducedMembers
int * intersectionPathDepth
spqr_arc * decompositionColumnArcs
COLOR_STATUS * nodeColors
int memIntersectionPathParent
int memIntersectionPathDepth
SPQRRowReducedComponent * reducedComponents
SCIP_Bool * isArcCutReversed
spqr_node * articulationNodes
MergeTreeCallData * mergeTreeCallData
int numDecompositionColumnArcs
cut_arc_id firstOverallCutArc
CreateReducedMembersCallstack * createReducedMembersCallstack
reduced_member_id * leafMembers
spqr_node * intersectionPathParent
reduced_member_id pathEndMembers[2]
reduced_member_id nextPathMember
int numPropagatedChildren
SCIP_Bool nextPathMemberIsParent
SPQRNetworkDecompositionArcListNode arcListNode
SPQRNetworkDecompositionArcListNode headArcListNode
SPQRNetworkDecompositionArcListNode tailArcListNode
spqr_member representativeMember
spqr_node representativeNode
RowReducedMemberType type
children_idx numPropagatedChildren
SCIP_Bool allHaveCommonNode
struct SCIP_Digraph SCIP_DIGRAPH
enum SCIP_Retcode SCIP_RETCODE