307 SCIP_Bool determinesize,
330 assert( *internodeid >= 0 );
333 assert( *maxdegrees > 0 );
340 assert( commonnodeidx <= *internodeid );
349 curcolor = colors[0];
351 for (e = 1; e < nneighbors; ++e)
354 if ( colors[e] != curcolor )
360 (*degrees)[*internodeid] = 1;
361 ++(*degrees)[commonnodeidx];
362 (*colorstostore)[*internodeid] = curcolor;
364 for (f = curstart; f < e; ++f)
366 assert( neighbors[f] <= *internodeid );
367 ++(*degrees)[*internodeid];
368 ++(*degrees)[neighbors[f]];
373 SG->e[edgestartpos[commonnodeidx]++] = *internodeid;
374 SG->e[edgestartpos[*internodeid]++] = commonnodeidx;
376 for (f = curstart; f < e; ++f)
378 SG->e[edgestartpos[neighbors[f]]++] = *internodeid;
379 SG->e[edgestartpos[*internodeid]++] = neighbors[f];
383 *naddededges += e - curstart + 1;
386 curcolor = colors[e];
397 (*degrees)[*internodeid] = 1;
398 ++(*degrees)[commonnodeidx];
399 (*colorstostore)[*internodeid] = curcolor;
401 for (f = curstart; f < nneighbors; ++f)
403 assert( neighbors[f] <= *internodeid );
404 ++(*degrees)[*internodeid];
405 ++(*degrees)[neighbors[f]];
410 SG->e[edgestartpos[commonnodeidx]++] = *internodeid;
411 SG->e[edgestartpos[*internodeid]++] = commonnodeidx;
413 for (f = curstart; f < nneighbors; ++f)
415 SG->e[edgestartpos[*internodeid]++] = neighbors[f];
416 SG->e[edgestartpos[neighbors[f]]++] = *internodeid;
420 *naddededges += nneighbors - curstart + 1;
431 SCIP_Bool determinesize,
444 SCIP_Bool groupByConstraints;
445 int* groupfirsts =
NULL;
446 int* groupseconds =
NULL;
447 int* groupcolors =
NULL;
449 int edgebegincnt = 0;
479 nvarnodestoadd = nsymvars;
483 nvarnodestoadd = 2 * nsymvars;
499 for (j = 0; j < *
nnodes; ++j)
506 for (j = 0; j < nvarnodestoadd; ++j)
516 for (j = 0; j < *
nnodes; ++j)
518 SG->d[j] = (*degrees)[j];
519 SG->v[j] = (size_t) (
unsigned) edgebegincnt;
520 pos[j] = edgebegincnt;
521 edgebegincnt += (*degrees)[j];
545 first += nvarnodestoadd;
547 second = -second - 1;
549 second += nvarnodestoadd;
561 groupfirsts[ngroupedges] = first;
562 groupseconds[ngroupedges] = second;
566 groupfirsts[ngroupedges] = second;
567 groupseconds[ngroupedges] = first;
585 ++(*degrees)[second];
586 (*degrees)[internodeid] = 2;
597 SG->e[pos[first]++] = internodeid;
598 SG->e[pos[internodeid]++] = first;
599 SG->e[pos[second]++] = internodeid;
600 SG->e[pos[internodeid]++] = second;
602 assert( first == *
nnodes - 1 || pos[first] <= (
int) SG->v[first+1] );
603 assert( second == *
nnodes - 1 || pos[second] <= (
int) SG->v[second+1] );
604 assert( internodeid == *
nnodes - 1 || pos[internodeid] <= (
int) SG->v[internodeid+1] );
614 ++(*degrees)[second];
620 SG->e[pos[first]++] = second;
621 SG->e[pos[second]++] = first;
623 assert( first == *
nnodes - 1 || pos[first] <= (
int) SG->v[first+1] );
624 assert( second == *
nnodes - 1 || pos[second] <= (
int) SG->v[second+1] );
631 if ( ngroupedges > 0 )
640 firstnodeidx = groupfirsts[0];
642 for (j = 1; j < ngroupedges; ++j)
645 if ( groupfirsts[j] != firstnodeidx )
648 degrees, maxdegrees, colors, ncolors,
nnodes, nedges, firstnodeidx, &groupseconds[firstidx],
649 &groupcolors[firstidx], j - firstidx, &naddednodes, &naddededges) );
652 firstnodeidx = groupfirsts[j];
657 *nedges += naddededges;
664 degrees, maxdegrees, colors, ncolors,
nnodes, nedges, firstnodeidx, &groupseconds[firstidx],
665 &groupcolors[firstidx], ngroupedges - firstidx, &naddednodes, &naddededges) );
670 *nedges += naddededges;
684 for (j = 0; j < nvarnodestoadd; ++j)
690 for (j = 0; j < nsymvars; ++j)
692 SG->e[pos[j]++] = j + nsymvars;
693 SG->e[pos[j + nsymvars]++] = j;
695 assert( pos[j] <= (
int) SG->v[j+1] );
696 assert( j + nsymvars == *
nnodes - 1 || pos[j+nsymvars] <= (
int) SG->v[j+nsymvars+1] );
731 SCIP_Bool determinesize,
740 int* nnodesfromgraph1,
746 SCIP_Bool groupByConstraints;
748 int* nvarused1 =
NULL;
749 int* nvarused2 =
NULL;
750 int* varlabel =
NULL;
751 int* groupfirsts =
NULL;
752 int* groupseconds =
NULL;
753 int* groupcolors =
NULL;
756 int edgebegincnt = 0;
782 assert( ! determinesize || nnodesfromgraph1 !=
NULL );
806 nvarnodestoadd = nsymvars;
810 nvarnodestoadd = 2 * nsymvars;
818 for (e = 0; e < nsymedges; ++e)
823 nvarused1[-first - 1] += 1;
825 nvarused1[-second - 1] += 1;
830 nvarused2[-first - 1] += 1;
832 nvarused2[-second - 1] += 1;
835 for (j = 0; j < nvarnodestoadd; ++j)
838 if ( nvarused1[j] != nvarused2[j] )
849 varlabel[j] = nusdvars++;
870 for (j = 0; j < *
nnodes; ++j)
872 SG->d[j] = (*degrees)[j];
873 SG->v[j] = (size_t) (
unsigned) edgebegincnt;
874 pos[j] = edgebegincnt;
875 edgebegincnt += (*degrees)[j];
889 for (
i = 0;
i < 2; ++
i)
892 symgraph =
i == 0 ? graph1 : graph2;
899 for (j = 0; j < nvarnodestoadd; ++j)
901 if ( varlabel[j] >= 0 )
904 (*degrees)[nodeshift + varlabel[j]] = 0;
915 (*degrees)[nodeshift + nusdvars + j] = 0;
924 for (j = 0; j < nvarnodestoadd; ++j)
926 if ( varlabel[j] >= 0 )
933 internodeid = nodeshift + curnnodes;
934 for (e = 0; e < nsymedges; ++e)
941 first = varlabel[-first - 1];
943 first = nusdvars + first;
945 second = varlabel[-second - 1];
947 second = nusdvars + second;
957 groupfirsts[ngroupedges] = nodeshift + first;
958 groupseconds[ngroupedges] = nodeshift + second;
962 groupfirsts[ngroupedges] = nodeshift + second;
963 groupseconds[ngroupedges] = nodeshift + first;
981 ++(*degrees)[nodeshift + first];
982 ++(*degrees)[nodeshift + second];
983 (*degrees)[internodeid] = 2;
986 (*colors)[internodeid] = nusdvars + color;
995 SG->e[pos[internodeid]++] = nodeshift + first;
996 SG->e[pos[internodeid]++] = nodeshift + second;
997 SG->e[pos[nodeshift + first]++] = internodeid;
998 SG->e[pos[nodeshift + second]++] = internodeid;
1001 || pos[internodeid] <= (
int) SG->v[internodeid+1] );
1003 || pos[nodeshift + first] <= (
int) SG->v[nodeshift+first+1] );
1005 pos[nodeshift + second] <= (
int) SG->v[nodeshift+second+1] );
1012 if ( determinesize )
1014 ++(*degrees)[nodeshift + first];
1015 ++(*degrees)[nodeshift + second];
1020 SG->e[pos[nodeshift + first]++] = nodeshift + second;
1021 SG->e[pos[nodeshift + second]++] = nodeshift + first;
1023 assert( nodeshift+first == *
nnodes - 1 || pos[nodeshift+first] <= (
int) SG->v[nodeshift+first+1] );
1024 assert( nodeshift+second == *
nnodes - 1 || pos[nodeshift+second] <= (
int) SG->v[nodeshift+second+1] );
1031 if ( ngroupedges > 0 )
1040 firstnodeidx = groupfirsts[0];
1042 for (j = 1; j < ngroupedges; ++j)
1045 if ( groupfirsts[j] != firstnodeidx )
1048 degrees, maxdegrees, colors, ncolors,
nnodes, nedges, firstnodeidx,
1049 &groupseconds[firstidx], &groupcolors[firstidx], j - firstidx, &naddednodes, &naddededges) );
1052 firstnodeidx = groupfirsts[j];
1054 if ( determinesize )
1057 *nedges += naddededges;
1059 curnnodes += naddednodes;
1065 degrees, maxdegrees, colors, ncolors,
nnodes, nedges, firstnodeidx,
1066 &groupseconds[firstidx], &groupcolors[firstidx], ngroupedges - firstidx, &naddednodes, &naddededges) );
1068 if ( determinesize )
1071 *nedges += naddededges;
1073 curnnodes += naddednodes;
1079 if ( determinesize )
1081 for (j = 0; j < nusdvars; ++j)
1082 ++(*degrees)[nodeshift + j];
1083 (*nedges) += nusdvars / 2;
1087 for (j = 0; j < nusdvars/2; ++j)
1089 SG->e[pos[nodeshift+j]++] = nodeshift + j + nusdvars/2;
1090 SG->e[pos[nodeshift + j + nusdvars/2]++] = nodeshift + j;
1092 assert( pos[nodeshift+j] <= (
int) SG->v[nodeshift+j+1] );
1094 || pos[nodeshift+j+nusdvars/2] <= (
int) SG->v[nodeshift+j+nusdvars/2+1] );
1098 nodeshift = curnnodes;
1101 if ( determinesize &&
i == 0 )
1102 *nnodesfromgraph1 = *
nnodes;
1106 if ( determinesize )
1112 for (j = 0; j < *
nnodes - 1; ++j)
1115 (*nedges) += *
nnodes - 1;
1116 (*colors)[*
nnodes - 1] = 8;
1120 for (j = 0; j < *
nnodes - 1; ++j)
1122 SG->e[pos[j]++] = *
nnodes - 1;
1123 SG->e[pos[*
nnodes-1]++] = j;
1137 if ( determinesize )
1138 *nusedvars = nusdvars;
1369 &colors, &ncolors, &nusedvars, &nnodesfromG1, &success) );
1386 DEFAULTOPTIONS_SPARSEGRAPH(options);
1389 static DEFAULTOPTIONS_TRACES(options);
1396 options.writeautoms =
FALSE;
1398 options.defaultptn =
FALSE;
1401 options.writeautoms =
FALSE;
1402 options.userautomproc = traceshook;
1403 options.defaultptn =
FALSE;
1409 SG_ALLOC(SG, (
size_t)
nnodes, 2 * (
size_t)(
unsigned) nedges,
"malloc");
1412 SG.nde = (size_t) (
unsigned) (2 * nedges);
1416 &colors, &ncolors, &nusedvars,
NULL, &success) );
1421#ifdef SCIP_DISABLED_CODE
1426 for (v = 0; v < SG.nv; ++v)
1431 for (v = 0; v < SG.nv; ++v)
1436 for (v = 0; v < SG.nv; ++v)
1438 for (
int w = 0;
w < SG.d[v]; ++
w)
1451 for (v = 0; v <
nnodes; ++v)
1458 for (v = 0; v <
nnodes; ++v)
1460 if ( v <
nnodes-1 && colors[v] == colors[v+1] )
1466#ifdef SCIP_DISABLED_CODE
1469 for (v = 0; v < SG.nv; ++v)
1487 sparsenauty(&SG, lab, ptn, orbits, &options, &stats,
NULL);
1489 Traces(&SG, lab, ptn, orbits, &options, &stats,
NULL);
1507 for (
int i = 0;
i < nnodesfromG1; ++
i)
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)