356 SCIP_Bool determinesize,
379 assert( *internodeid >= 0 );
382 assert( *maxdegrees > 0 );
389 assert( commonnodeidx <= *internodeid );
398 curcolor = colors[0];
400 for (e = 1; e < nneighbors; ++e)
403 if ( colors[e] != curcolor )
409 (*degrees)[*internodeid] = 1;
410 ++(*degrees)[commonnodeidx];
411 (*colorstostore)[*internodeid] = curcolor;
413 for (f = curstart; f < e; ++f)
415 assert( neighbors[f] <= *internodeid );
416 ++(*degrees)[*internodeid];
417 ++(*degrees)[neighbors[f]];
422 SG->e[edgestartpos[commonnodeidx]++] = *internodeid;
423 SG->e[edgestartpos[*internodeid]++] = commonnodeidx;
425 for (f = curstart; f < e; ++f)
427 SG->e[edgestartpos[neighbors[f]]++] = *internodeid;
428 SG->e[edgestartpos[*internodeid]++] = neighbors[f];
432 *naddededges += e - curstart + 1;
435 curcolor = colors[e];
446 (*degrees)[*internodeid] = 1;
447 ++(*degrees)[commonnodeidx];
448 (*colorstostore)[*internodeid] = curcolor;
450 for (f = curstart; f < nneighbors; ++f)
452 assert( neighbors[f] <= *internodeid );
453 ++(*degrees)[*internodeid];
454 ++(*degrees)[neighbors[f]];
459 SG->e[edgestartpos[commonnodeidx]++] = *internodeid;
460 SG->e[edgestartpos[*internodeid]++] = commonnodeidx;
462 for (f = curstart; f < nneighbors; ++f)
464 SG->e[edgestartpos[*internodeid]++] = neighbors[f];
465 SG->e[edgestartpos[neighbors[f]]++] = *internodeid;
469 *naddededges += nneighbors - curstart + 1;
480 SCIP_Bool determinesize,
493 SCIP_Bool groupByConstraints;
494 int* groupfirsts =
NULL;
495 int* groupseconds =
NULL;
496 int* groupcolors =
NULL;
498 int edgebegincnt = 0;
528 nvarnodestoadd = nsymvars;
532 nvarnodestoadd = 2 * nsymvars;
548 for (j = 0; j < *
nnodes; ++j)
555 for (j = 0; j < nvarnodestoadd; ++j)
565 for (j = 0; j < *
nnodes; ++j)
567 SG->d[j] = (*degrees)[j];
568 SG->v[j] = (size_t) (
unsigned) edgebegincnt;
569 pos[j] = edgebegincnt;
570 edgebegincnt += (*degrees)[j];
594 first += nvarnodestoadd;
596 second = -second - 1;
598 second += nvarnodestoadd;
610 groupfirsts[ngroupedges] = first;
611 groupseconds[ngroupedges] = second;
615 groupfirsts[ngroupedges] = second;
616 groupseconds[ngroupedges] = first;
634 ++(*degrees)[second];
635 (*degrees)[internodeid] = 2;
646 SG->e[pos[first]++] = internodeid;
647 SG->e[pos[internodeid]++] = first;
648 SG->e[pos[second]++] = internodeid;
649 SG->e[pos[internodeid]++] = second;
651 assert( first == *
nnodes - 1 || pos[first] <= (
int) SG->v[first+1] );
652 assert( second == *
nnodes - 1 || pos[second] <= (
int) SG->v[second+1] );
653 assert( internodeid == *
nnodes - 1 || pos[internodeid] <= (
int) SG->v[internodeid+1] );
663 ++(*degrees)[second];
669 SG->e[pos[first]++] = second;
670 SG->e[pos[second]++] = first;
672 assert( first == *
nnodes - 1 || pos[first] <= (
int) SG->v[first+1] );
673 assert( second == *
nnodes - 1 || pos[second] <= (
int) SG->v[second+1] );
680 if ( ngroupedges > 0 )
689 firstnodeidx = groupfirsts[0];
691 for (j = 1; j < ngroupedges; ++j)
694 if ( groupfirsts[j] != firstnodeidx )
697 degrees, maxdegrees, colors, ncolors,
nnodes, nedges, firstnodeidx, &groupseconds[firstidx],
698 &groupcolors[firstidx], j - firstidx, &naddednodes, &naddededges) );
701 firstnodeidx = groupfirsts[j];
706 *nedges += naddededges;
713 degrees, maxdegrees, colors, ncolors,
nnodes, nedges, firstnodeidx, &groupseconds[firstidx],
714 &groupcolors[firstidx], ngroupedges - firstidx, &naddednodes, &naddededges) );
719 *nedges += naddededges;
733 for (j = 0; j < nvarnodestoadd; ++j)
739 for (j = 0; j < nsymvars; ++j)
741 SG->e[pos[j]++] = j + nsymvars;
742 SG->e[pos[j + nsymvars]++] = j;
744 assert( pos[j] <= (
int) SG->v[j+1] );
745 assert( j + nsymvars == *
nnodes - 1 || pos[j+nsymvars] <= (
int) SG->v[j+nsymvars+1] );
780 SCIP_Bool determinesize,
789 int* nnodesfromgraph1,
795 SCIP_Bool groupByConstraints;
797 int* nvarused1 =
NULL;
798 int* nvarused2 =
NULL;
799 int* varlabel =
NULL;
800 int* groupfirsts =
NULL;
801 int* groupseconds =
NULL;
802 int* groupcolors =
NULL;
805 int edgebegincnt = 0;
831 assert( ! determinesize || nnodesfromgraph1 !=
NULL );
855 nvarnodestoadd = nsymvars;
859 nvarnodestoadd = 2 * nsymvars;
867 for (e = 0; e < nsymedges; ++e)
872 nvarused1[-first - 1] += 1;
874 nvarused1[-second - 1] += 1;
879 nvarused2[-first - 1] += 1;
881 nvarused2[-second - 1] += 1;
884 for (j = 0; j < nvarnodestoadd; ++j)
887 if ( nvarused1[j] != nvarused2[j] )
898 varlabel[j] = nusdvars++;
919 for (j = 0; j < *
nnodes; ++j)
921 SG->d[j] = (*degrees)[j];
922 SG->v[j] = (size_t) (
unsigned) edgebegincnt;
923 pos[j] = edgebegincnt;
924 edgebegincnt += (*degrees)[j];
938 for (
i = 0;
i < 2; ++
i)
941 symgraph =
i == 0 ? graph1 : graph2;
948 for (j = 0; j < nvarnodestoadd; ++j)
950 if ( varlabel[j] >= 0 )
953 (*degrees)[nodeshift + varlabel[j]] = 0;
964 (*degrees)[nodeshift + nusdvars + j] = 0;
973 for (j = 0; j < nvarnodestoadd; ++j)
975 if ( varlabel[j] >= 0 )
982 internodeid = nodeshift + curnnodes;
983 for (e = 0; e < nsymedges; ++e)
990 first = varlabel[-first - 1];
992 first = nusdvars + first;
994 second = varlabel[-second - 1];
996 second = nusdvars + second;
1006 groupfirsts[ngroupedges] = nodeshift + first;
1007 groupseconds[ngroupedges] = nodeshift + second;
1011 groupfirsts[ngroupedges] = nodeshift + second;
1012 groupseconds[ngroupedges] = nodeshift + first;
1025 if ( determinesize )
1030 ++(*degrees)[nodeshift + first];
1031 ++(*degrees)[nodeshift + second];
1032 (*degrees)[internodeid] = 2;
1035 (*colors)[internodeid] = nusdvars + color;
1044 SG->e[pos[internodeid]++] = nodeshift + first;
1045 SG->e[pos[internodeid]++] = nodeshift + second;
1046 SG->e[pos[nodeshift + first]++] = internodeid;
1047 SG->e[pos[nodeshift + second]++] = internodeid;
1050 || pos[internodeid] <= (
int) SG->v[internodeid+1] );
1052 || pos[nodeshift + first] <= (
int) SG->v[nodeshift+first+1] );
1054 pos[nodeshift + second] <= (
int) SG->v[nodeshift+second+1] );
1061 if ( determinesize )
1063 ++(*degrees)[nodeshift + first];
1064 ++(*degrees)[nodeshift + second];
1069 SG->e[pos[nodeshift + first]++] = nodeshift + second;
1070 SG->e[pos[nodeshift + second]++] = nodeshift + first;
1072 assert( nodeshift+first == *
nnodes - 1 || pos[nodeshift+first] <= (
int) SG->v[nodeshift+first+1] );
1073 assert( nodeshift+second == *
nnodes - 1 || pos[nodeshift+second] <= (
int) SG->v[nodeshift+second+1] );
1080 if ( ngroupedges > 0 )
1089 firstnodeidx = groupfirsts[0];
1091 for (j = 1; j < ngroupedges; ++j)
1094 if ( groupfirsts[j] != firstnodeidx )
1097 degrees, maxdegrees, colors, ncolors,
nnodes, nedges, firstnodeidx,
1098 &groupseconds[firstidx], &groupcolors[firstidx], j - firstidx, &naddednodes, &naddededges) );
1101 firstnodeidx = groupfirsts[j];
1103 if ( determinesize )
1106 *nedges += naddededges;
1108 curnnodes += naddednodes;
1114 degrees, maxdegrees, colors, ncolors,
nnodes, nedges, firstnodeidx,
1115 &groupseconds[firstidx], &groupcolors[firstidx], ngroupedges - firstidx, &naddednodes, &naddededges) );
1117 if ( determinesize )
1120 *nedges += naddededges;
1122 curnnodes += naddednodes;
1128 if ( determinesize )
1130 for (j = 0; j < nusdvars; ++j)
1131 ++(*degrees)[nodeshift + j];
1132 (*nedges) += nusdvars / 2;
1136 for (j = 0; j < nusdvars/2; ++j)
1138 SG->e[pos[nodeshift+j]++] = nodeshift + j + nusdvars/2;
1139 SG->e[pos[nodeshift + j + nusdvars/2]++] = nodeshift + j;
1141 assert( pos[nodeshift+j] <= (
int) SG->v[nodeshift+j+1] );
1143 || pos[nodeshift+j+nusdvars/2] <= (
int) SG->v[nodeshift+j+nusdvars/2+1] );
1147 nodeshift = curnnodes;
1150 if ( determinesize &&
i == 0 )
1151 *nnodesfromgraph1 = *
nnodes;
1155 if ( determinesize )
1161 for (j = 0; j < *
nnodes - 1; ++j)
1164 (*nedges) += *
nnodes - 1;
1165 (*colors)[*
nnodes - 1] = 8;
1169 for (j = 0; j < *
nnodes - 1; ++j)
1171 SG->e[pos[j]++] = *
nnodes - 1;
1172 SG->e[pos[*
nnodes-1]++] = j;
1186 if ( determinesize )
1187 *nusedvars = nusdvars;
static SCIP_RETCODE addOrDetermineEffectOfGroupedEdges(SCIP *scip, sparsegraph *SG, int *edgestartpos, SCIP_Bool determinesize, int *internodeid, int **degrees, int *maxdegrees, int **colorstostore, int *ncolorstostore, int *nnodes, int *nedges, int commonnodeidx, int *neighbors, int *colors, int nneighbors, int *naddednodes, int *naddededges)