110 sassy::static_graph* G,
111 SCIP_Bool determinesize,
132 assert( *internodeid >= 0 );
135 assert( *maxdegrees > 0 );
142 assert( commonnodeidx <= *internodeid );
151 curcolor = colors[0];
153 for (e = 1; e < nneighbors; ++e)
156 if ( colors[e] != curcolor )
161 (*degrees)[*internodeid] = 1;
162 ++(*degrees)[commonnodeidx];
164 for (f = curstart; f < e; ++f)
166 assert( neighbors[f] <= *internodeid );
167 ++(*degrees)[*internodeid];
168 ++(*degrees)[neighbors[f]];
173 (void) G->add_vertex(curcolor, (*degrees)[*internodeid]);
174 G->add_edge((
unsigned) commonnodeidx, (unsigned) *internodeid);
176 for (f = curstart; f < e; ++f)
177 (*G).add_edge((
unsigned) neighbors[f], (unsigned) *internodeid);
180 *naddededges += e - curstart + 1;
183 curcolor = colors[e];
193 (*degrees)[*internodeid] = 1;
194 ++(*degrees)[commonnodeidx];
196 for (f = curstart; f < nneighbors; ++f)
198 assert( neighbors[f] <= *internodeid );
199 ++(*degrees)[*internodeid];
200 ++(*degrees)[neighbors[f]];
205 (void) G->add_vertex(curcolor, (*degrees)[*internodeid]);
206 G->add_edge((
unsigned) commonnodeidx, (unsigned) *internodeid);
208 for (f = curstart; f < nneighbors; ++f)
209 G->add_edge((
unsigned) neighbors[f], (unsigned) *internodeid);
212 *naddededges += nneighbors - curstart + 1;
223 SCIP_Bool determinesize,
224 sassy::static_graph* G,
234 SCIP_Bool groupByConstraints;
235 int* groupfirsts =
NULL;
236 int* groupseconds =
NULL;
237 int* groupcolors =
NULL;
266 nvarnodestoadd = nsymvars;
270 nvarnodestoadd = 2 * nsymvars;
284 for (j = 0; j < *
nnodes; ++j)
292 for (j = 0; j < nvarnodestoadd; ++j)
302 groupByConstraints =
TRUE;
304 groupByConstraints =
FALSE;
323 first += nvarnodestoadd;
325 second = -second - 1;
327 second += nvarnodestoadd;
339 groupfirsts[ngroupedges] = first;
340 groupseconds[ngroupedges] = second;
344 groupfirsts[ngroupedges] = second;
345 groupseconds[ngroupedges] = first;
363 ++(*degrees)[second];
364 (*degrees)[internodeid] = 2;
375 (void) G->add_vertex(color, (*degrees)[internodeid]);
377 G->add_edge((
unsigned) first, (unsigned) internodeid);
378 G->add_edge((
unsigned) second, (unsigned) internodeid++);
386 ++(*degrees)[second];
392 if ( first < second )
393 G->add_edge((
unsigned) first, (
unsigned) second);
395 G->add_edge((
unsigned) second, (
unsigned) first);
402 if ( ngroupedges > 0 )
411 firstnodeidx = groupfirsts[0];
413 for (j = 1; j < ngroupedges; ++j)
416 if ( groupfirsts[j] != firstnodeidx )
419 nnodes, nedges, firstnodeidx, &groupseconds[firstidx], &groupcolors[firstidx], j - firstidx,
420 &naddednodes, &naddededges) );
423 firstnodeidx = groupfirsts[j];
428 *nedges += naddededges;
435 nnodes, nedges, firstnodeidx, &groupseconds[firstidx], &groupcolors[firstidx], ngroupedges - firstidx,
436 &naddednodes, &naddededges) );
441 *nedges += naddededges;
455 for (j = 0; j < nvarnodestoadd; ++j)
462 for (j = 0; j < nsymvars; ++j)
463 G->add_edge((
unsigned) j, (
unsigned) (j + nsymvars));
492 SCIP_Bool determinesize,
493 sassy::static_graph* G,
504 SCIP_Bool groupByConstraints;
506 int* nvarused1 =
NULL;
507 int* nvarused2 =
NULL;
508 int* varlabel =
NULL;
509 int* groupfirsts =
NULL;
510 int* groupseconds =
NULL;
511 int* groupcolors =
NULL;
551 nvarnodestoadd = nsymvars;
555 nvarnodestoadd = 2 * nsymvars;
563 for (e = 0; e < nsymedges; ++e)
568 nvarused1[-first - 1] += 1;
570 nvarused1[-second - 1] += 1;
575 nvarused2[-first - 1] += 1;
577 nvarused2[-second - 1] += 1;
580 for (j = 0; j < nvarnodestoadd; ++j)
583 if ( nvarused1[j] != nvarused2[j] )
594 varlabel[j] = nusedvars++;
613 groupByConstraints =
TRUE;
615 groupByConstraints =
FALSE;
624 for (
i = 0;
i < 2; ++
i)
627 graph =
i == 0 ? graph1 : graph2;
634 for (j = 0; j < nvarnodestoadd; ++j)
636 if ( varlabel[j] >= 0 )
639 (*degrees)[nodeshift + varlabel[j]] = 0;
649 (*degrees)[nodeshift + nusedvars + j] = 0;
659 for (j = 0; j < nvarnodestoadd; ++j)
661 if ( varlabel[j] >= 0 )
663 (void) G->add_vertex(j, (*degrees)[nodeshift + varlabel[j]]);
672 (*degrees)[nodeshift + nusedvars + j]);
678 internodeid = nodeshift + curnnodes;
679 for (e = 0; e < nsymedges; ++e)
686 first = varlabel[-first - 1];
688 first = nusedvars + first;
690 second = varlabel[-second - 1];
692 second = nusedvars + second;
702 groupfirsts[ngroupedges] = nodeshift + first;
703 groupseconds[ngroupedges] = nodeshift + second;
707 groupfirsts[ngroupedges] = nodeshift + second;
708 groupseconds[ngroupedges] = nodeshift + first;
725 ++(*degrees)[nodeshift + first];
726 ++(*degrees)[nodeshift + second];
727 (*degrees)[internodeid] = 2;
737 (void) G->add_vertex(nusedvars + color, (*degrees)[internodeid]);
738 G->add_edge((
unsigned) (nodeshift + first), (
unsigned) internodeid);
739 G->add_edge((
unsigned) (nodeshift + second), (
unsigned) internodeid);
748 ++(*degrees)[nodeshift + first];
749 ++(*degrees)[nodeshift + second];
756 if ( first < second )
757 G->add_edge((
unsigned) (nodeshift + first), (
unsigned) (nodeshift + second));
759 G->add_edge((
unsigned) (nodeshift + second), (
unsigned) (nodeshift + first));
766 if ( ngroupedges > 0 )
775 firstnodeidx = groupfirsts[0];
777 for (j = 1; j < ngroupedges; ++j)
780 if ( groupfirsts[j] != firstnodeidx )
783 nnodes, nedges, firstnodeidx, &groupseconds[firstidx], &groupcolors[firstidx], j - firstidx,
784 &naddednodes, &naddededges) );
787 firstnodeidx = groupfirsts[j];
792 *nedges += naddededges;
794 curnnodes += naddednodes;
800 nnodes, nedges, firstnodeidx, &groupseconds[firstidx], &groupcolors[firstidx], ngroupedges - firstidx,
801 &naddednodes, &naddededges) );
806 *nedges += naddededges;
808 curnnodes += naddednodes;
816 for (j = 0; j < nusedvars; ++j)
817 ++(*degrees)[nodeshift + j];
818 (*nedges) += nusedvars / 2;
824 for (j = 0; j < nusedvars/2; ++j)
825 G->add_edge((
unsigned) (nodeshift + j), (
unsigned) (nodeshift + j + nusedvars / 2));
828 nodeshift = curnnodes;
830 if (
i == 0 && nnodesfromG1 !=
NULL )
831 *nnodesfromG1 = curnnodes;
static SCIP_RETCODE addOrDetermineEffectOfGroupedEdges(SCIP *scip, sassy::static_graph *G, SCIP_Bool determinesize, int *internodeid, int **degrees, int *maxdegrees, int *nnodes, int *nedges, int commonnodeidx, int *neighbors, int *colors, int nneighbors, int *naddednodes, int *naddededges)