Scippy

SCIP

Solving Constraint Integer Programs

build_sassy_graph.cpp
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file build_sassy_graph.cpp
26  * @brief methods to build sassy graph for symmetry detection
27  * @author Christopher Hojny
28  */
29 
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31 
32 #include "build_sassy_graph.h"
33 #include "scip/expr_var.h"
34 #include "scip/expr_sum.h"
35 #include "scip/expr_pow.h"
36 #include "scip/expr.h"
37 #include "scip/cons_nonlinear.h"
38 #include "scip/cons_linear.h"
39 #include "scip/scip_mem.h"
40 #include "scip/symmetry_graph.h"
41 
42 
43 /* ------------------- auxiliary functions ------------------- */
44 
45 /** returns whether an edge is considered in grouping process */
46 static
48  SYM_GRAPH* graph, /**< symmetry detection graph */
49  int edgeidx, /**< index of edge to be checked */
50  SCIP_Bool groupbycons /**< whether edges are grouped by constraints */
51  )
52 {
53  int first;
54  int second;
55 
56  assert(graph != NULL);
57 
58  first = SCIPgetSymgraphEdgeFirst(graph, edgeidx);
59  second = SCIPgetSymgraphEdgeSecond(graph, edgeidx);
60 
61  /* uncolored edges are not grouped */
62  if ( ! SCIPisSymgraphEdgeColored(graph, edgeidx) )
63  return FALSE;
64 
65  /* two variable nodes are connected */
66  if ( first < 0 && second < 0 )
67  return FALSE;
68 
69  if ( ! groupbycons )
70  {
71  /* grouping by variables requires one variable node */
72  if ( first < 0 || second < 0 )
73  return TRUE;
74  }
75  else
76  {
77  /* check whether there is exactly one constraint node in edge */
78  if ( first >= 0 && second >= 0 )
79  {
80  if ( (SCIPgetSymgraphNodeType(graph, first) == SYM_NODETYPE_CONS
81  && SCIPgetSymgraphNodeType(graph, second) != SYM_NODETYPE_CONS)
82  || (SCIPgetSymgraphNodeType(graph, first) != SYM_NODETYPE_CONS
83  && SCIPgetSymgraphNodeType(graph, second) == SYM_NODETYPE_CONS) )
84  return TRUE;
85  }
86  else if ( first >= 0 )
87  {
88  if ( SCIPgetSymgraphNodeType(graph, first) == SYM_NODETYPE_CONS )
89  return TRUE;
90  }
91  else
92  {
93  if ( SCIPgetSymgraphNodeType(graph, second) == SYM_NODETYPE_CONS )
94  return TRUE;
95  }
96  }
97 
98  return FALSE;
99 }
100 
101 /** adds grouped edges all of which have one common endpoint to a graph
102  *
103  * The grouping mechanism works by sorting the edges according to their color. If two
104  * edges have the same color, they share the same intermediate node, which is connected
105  * to the common node and the other endpoints of equivalent edges.
106  */
107 static
109  SCIP* scip, /**< SCIP pointer */
110  sassy::static_graph* G, /**< graph which gets extended */
111  SCIP_Bool determinesize, /**< whether only the effect of grouping on the graph shall be checked */
112  int* internodeid, /**< (initialized) pointer to store the ID of the next intermediate node */
113  int** degrees, /**< pointer to array of degrees for nodes in G */
114  int* maxdegrees, /**< (initialized) pointer to maximum number of entries degrees can hold */
115  int* nnodes, /**< (initialized) pointer to store the number of */
116  int* nedges, /**< (initialized) pointer to store the number of */
117  int commonnodeidx, /**< index of common node in G */
118  int* neighbors, /**< neighbors of common node */
119  int* colors, /**< colors of edges to neighbors */
120  int nneighbors, /**< number of neighbors */
121  int* naddednodes, /**< pointer to store number of nodes added to G */
122  int* naddededges /**< pointer to store number of edges added to G */
123  )
124 {
125  int curcolor;
126  int curstart;
127  int e;
128  int f;
129 
130  assert( G != NULL || determinesize );
131  assert( internodeid != NULL );
132  assert( *internodeid >= 0 );
133  assert( degrees != NULL );
134  assert( maxdegrees != NULL );
135  assert( *maxdegrees > 0 );
136  assert( nnodes != NULL );
137  assert( nedges != NULL );
138  assert( neighbors != NULL );
139  assert( colors != NULL );
140  assert( naddednodes != NULL );
141  assert( naddededges != NULL );
142  assert( commonnodeidx <= *internodeid );
143 
144  *naddednodes = 0;
145  *naddededges = 0;
146 
147  /* sort edges according to color */
148  SCIPsortIntInt(colors, neighbors, nneighbors);
149 
150  /* iterate over groups of identical edges and group them, ignoring the last group */
151  curcolor = colors[0];
152  curstart = 0;
153  for (e = 1; e < nneighbors; ++e)
154  {
155  /* if a new group started, add edges for previous group */
156  if ( colors[e] != curcolor )
157  {
158  if ( determinesize )
159  {
160  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, *internodeid + 1) );
161  (*degrees)[*internodeid] = 1;
162  ++(*degrees)[commonnodeidx];
163 
164  for (f = curstart; f < e; ++f)
165  {
166  assert( neighbors[f] <= *internodeid );
167  ++(*degrees)[*internodeid];
168  ++(*degrees)[neighbors[f]];
169  }
170  }
171  else
172  {
173  (void) G->add_vertex(curcolor, (*degrees)[*internodeid]);
174  G->add_edge((unsigned) commonnodeidx, (unsigned) *internodeid);
175 
176  for (f = curstart; f < e; ++f)
177  (*G).add_edge((unsigned) neighbors[f], (unsigned) *internodeid);
178  }
179  *naddednodes += 1;
180  *naddededges += e - curstart + 1;
181  ++(*internodeid);
182 
183  curcolor = colors[e];
184  curstart = e;
185  }
186  }
187 
188  /* add edges of last group */
189  if ( determinesize )
190  {
191  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, *internodeid + 1) );
192 
193  (*degrees)[*internodeid] = 1;
194  ++(*degrees)[commonnodeidx];
195 
196  for (f = curstart; f < nneighbors; ++f)
197  {
198  assert( neighbors[f] <= *internodeid );
199  ++(*degrees)[*internodeid];
200  ++(*degrees)[neighbors[f]];
201  }
202  }
203  else
204  {
205  (void) G->add_vertex(curcolor, (*degrees)[*internodeid]);
206  G->add_edge((unsigned) commonnodeidx, (unsigned) *internodeid);
207 
208  for (f = curstart; f < nneighbors; ++f)
209  G->add_edge((unsigned) neighbors[f], (unsigned) *internodeid);
210  }
211  *naddednodes += 1;
212  *naddededges += nneighbors - curstart + 1;
213  ++(*internodeid);
214 
215  return SCIP_OKAY;
216 }
217 
218 /** either creates a graph or determines its size */
219 static
221  SCIP* scip, /**< SCIP instance */
222  SYM_GRAPH* graph, /**< symmetry detection graph */
223  SCIP_Bool determinesize, /**< whether only the size of the graph shall be determined */
224  sassy::static_graph* G, /**< graph to be constructed */
225  int* nnodes, /**< pointer to store the total number of nodes in graph */
226  int* nedges, /**< pointer to store the total number of edges in graph */
227  int** degrees, /**< pointer to store the degrees of the nodes */
228  int* maxdegrees, /**< pointer to store the maximal size of the degree array */
229  SCIP_Bool* success /**< pointer to store whether the construction was successful */
230  )
231 {
232  SYM_SYMTYPE symtype;
233  SYM_NODETYPE comparetype;
234  SCIP_Bool groupByConstraints;
235  int* groupfirsts = NULL;
236  int* groupseconds = NULL;
237  int* groupcolors = NULL;
238  int ngroupedges = 0;
239  int nvarnodestoadd;
240  int internodeid;
241  int nsymvars;
242  int nsymedges;
243  int first;
244  int second;
245  int color;
246  int e;
247  int j;
248 
249  assert( scip != NULL );
250  assert( graph != NULL );
251  assert( G != NULL || determinesize );
252  assert( nnodes != NULL );
253  assert( nedges != NULL );
254  assert( degrees != NULL );
255  assert( maxdegrees != NULL );
256  assert( success != NULL );
257 
258  *success = TRUE;
259 
260  /* collect basic information from symmetry detection graph */
261  nsymvars = SCIPgetSymgraphNVars(graph);
262  symtype = SCIPgetSymgraphSymtype(graph);
263  switch ( symtype )
264  {
265  case SYM_SYMTYPE_PERM:
266  nvarnodestoadd = nsymvars;
267  break;
268  default:
269  assert( symtype == SYM_SYMTYPE_SIGNPERM );
270  nvarnodestoadd = 2 * nsymvars;
271  }
272 
273  /* possibly find number of nodes in sassy graph */
274  if ( determinesize )
275  {
276  /* initialize counters */
277  *nnodes = SCIPgetSymgraphNNodes(graph) + nvarnodestoadd;
278  *nedges = 0;
279 
280  /* possibly allocate memory for degrees (will grow dynamically) */
281  *degrees = NULL;
282  *maxdegrees = 0;
283  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, *nnodes + 100) );
284  for (j = 0; j < *nnodes; ++j)
285  (*degrees)[j] = 0;
286  }
287  else
288  {
289  assert( G != NULL );
290 
291  /* add nodes for variables */
292  for (j = 0; j < nvarnodestoadd; ++j)
293  (void) G->add_vertex(SCIPgetSymgraphVarnodeColor(graph, j), (*degrees)[j]);
294 
295  /* add nodes for remaining nodes of graph */
296  for (j = 0; j < SCIPgetSymgraphNNodes(graph); ++j)
297  (void) G->add_vertex(SCIPgetSymgraphNodeColor(graph, j), (*degrees)[nvarnodestoadd + j]);
298  }
299 
300  /* determine grouping depending on the number of rhs vs. variables */
301  if ( SCIPgetSymgraphNConsnodes(graph) < SCIPgetSymgraphNVars(graph) )
302  groupByConstraints = TRUE;
303  else
304  groupByConstraints = FALSE;
305 
306  /* allocate arrays to collect edges to be grouped */
307  nsymedges = SCIPgetSymgraphNEdges(graph);
308  SCIP_CALL( SCIPallocBufferArray(scip, &groupfirsts, nsymedges) );
309  SCIP_CALL( SCIPallocBufferArray(scip, &groupseconds, nsymedges) );
310  SCIP_CALL( SCIPallocBufferArray(scip, &groupcolors, nsymedges) );
311 
312  /* loop through all edges of the symmetry detection graph and either get degrees of nodes or add edges */
313  internodeid = SCIPgetSymgraphNNodes(graph) + nvarnodestoadd;
314  for (e = 0; e < SCIPgetSymgraphNEdges(graph); ++e)
315  {
316  first = SCIPgetSymgraphEdgeFirst(graph, e);
317  second = SCIPgetSymgraphEdgeSecond(graph, e);
318 
319  /* get the first and second node in edge (corrected by variable shift) */
320  if ( first < 0 )
321  first = -first - 1;
322  else
323  first += nvarnodestoadd;
324  if ( second < 0 )
325  second = -second - 1;
326  else
327  second += nvarnodestoadd;
328  assert(first >= 0);
329  assert(second >= 0);
330 
331  /* check whether edge is used for grouping */
332  if ( ! SCIPhasGraphUniqueEdgetype(graph) && isEdgeGroupable(graph, e, groupByConstraints) )
333  {
334  /* store edge, first becomes the cons or var node */
335  comparetype = groupByConstraints ? SYM_NODETYPE_CONS : SYM_NODETYPE_VAR;
336 
337  if ( SCIPgetSymgraphNodeType(graph, SCIPgetSymgraphEdgeFirst(graph, e)) == comparetype )
338  {
339  groupfirsts[ngroupedges] = first;
340  groupseconds[ngroupedges] = second;
341  }
342  else
343  {
344  groupfirsts[ngroupedges] = second;
345  groupseconds[ngroupedges] = first;
346  }
347  groupcolors[ngroupedges++] = SCIPgetSymgraphEdgeColor(graph, e);
348  }
349  else
350  {
351  /* immediately add edge or increase degrees */
352  assert(0 <= first && first < *nnodes);
353  assert(0 <= second && second < *nnodes);
354 
355  /* possibly split edge if it is colored */
356  if ( ! SCIPhasGraphUniqueEdgetype(graph) && SCIPisSymgraphEdgeColored(graph, e) )
357  {
358  if ( determinesize )
359  {
360  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, internodeid + 1) );
361 
362  ++(*degrees)[first];
363  ++(*degrees)[second];
364  (*degrees)[internodeid] = 2;
365  ++(*nnodes);
366  *nedges += 2;
367  ++internodeid;
368  }
369  else
370  {
371  assert( internodeid < *nnodes );
372  assert( G != NULL );
373 
374  color = SCIPgetSymgraphEdgeColor(graph, e);
375  (void) G->add_vertex(color, (*degrees)[internodeid]);
376 
377  G->add_edge((unsigned) first, (unsigned) internodeid);
378  G->add_edge((unsigned) second, (unsigned) internodeid++);
379  }
380  }
381  else
382  {
383  if ( determinesize )
384  {
385  ++(*degrees)[first];
386  ++(*degrees)[second];
387  ++(*nedges);
388  }
389  else
390  {
391  assert( G != NULL );
392  if ( first < second )
393  G->add_edge((unsigned) first, (unsigned) second);
394  else
395  G->add_edge((unsigned) second, (unsigned) first);
396  }
397  }
398  }
399  }
400 
401  /* possibly add groupable edges */
402  if ( ngroupedges > 0 )
403  {
404  int firstidx = 0;
405  int firstnodeidx;
406  int naddednodes;
407  int naddededges;
408 
409  /* sort edges according to their first nodes */
410  SCIPsortIntIntInt(groupfirsts, groupseconds, groupcolors, ngroupedges);
411  firstnodeidx = groupfirsts[0];
412 
413  for (j = 1; j < ngroupedges; ++j)
414  {
415  /* if a new first node has been found, group the edges of the previous first node; ignoring the last group */
416  if ( groupfirsts[j] != firstnodeidx )
417  {
418  SCIP_CALL( addOrDetermineEffectOfGroupedEdges(scip, G, determinesize, &internodeid, degrees, maxdegrees,
419  nnodes, nedges, firstnodeidx, &groupseconds[firstidx], &groupcolors[firstidx], j - firstidx,
420  &naddednodes, &naddededges) );
421 
422  firstidx = j;
423  firstnodeidx = groupfirsts[j];
424 
425  if ( determinesize )
426  {
427  *nnodes += naddednodes;
428  *nedges += naddededges;
429  }
430  }
431  }
432 
433  /* process the last group */
434  SCIP_CALL( addOrDetermineEffectOfGroupedEdges(scip, G, determinesize, &internodeid, degrees, maxdegrees,
435  nnodes, nedges, firstnodeidx, &groupseconds[firstidx], &groupcolors[firstidx], ngroupedges - firstidx,
436  &naddednodes, &naddededges) );
437 
438  if ( determinesize )
439  {
440  *nnodes += naddednodes;
441  *nedges += naddededges;
442  }
443  }
444 
445  SCIPfreeBufferArray(scip, &groupcolors);
446  SCIPfreeBufferArray(scip, &groupseconds);
447  SCIPfreeBufferArray(scip, &groupfirsts);
448 
449  /* for signed permutation, also add edges connecting a variable and its negation */
450  switch ( SCIPgetSymgraphSymtype(graph) )
451  {
453  if ( determinesize )
454  {
455  for (j = 0; j < nvarnodestoadd; ++j)
456  ++(*degrees)[j];
457  *nedges += nsymvars;
458  }
459  else
460  {
461  assert( G != NULL );
462  for (j = 0; j < nsymvars; ++j)
463  G->add_edge((unsigned) j, (unsigned) (j + nsymvars));
464  }
465  break;
466  default:
467  assert( SCIPgetSymgraphSymtype(graph) == SYM_SYMTYPE_PERM );
468  }
469 
470  if ( determinesize )
471  {
472  SCIPdebugMsg(scip, "#nodes: %d\n", *nnodes);
473  SCIPdebugMsg(scip, "#nodes for variables: %d\n", nvarnodestoadd);
474  SCIPdebugMsg(scip, "#nodes for rhs: %d\n", SCIPgetSymgraphNConsnodes(graph));
475  SCIPdebugMsg(scip, "#edges: %d\n", *nedges);
476  }
477 
478  return SCIP_OKAY;
479 }
480 
481 /** either creates a graph for checking symmetries or determines its size
482  *
483  * The input are two graphs and the graph to be constructed consists of copies
484  * of the two input graphs, in which non-variable nodes are colored according
485  * to the colors used in symmetry detection. Each variable gets a unique color.
486  */
487 static
489  SCIP* scip, /**< SCIP instance */
490  SYM_GRAPH* graph1, /**< first symmetry detection graph */
491  SYM_GRAPH* graph2, /**< second symmetry detection graph */
492  SCIP_Bool determinesize, /**< whether only the size of the graph shall be determined */
493  sassy::static_graph* G, /**< graph to be constructed */
494  int* nnodes, /**< pointer to store the total number of nodes in graph */
495  int* nedges, /**< pointer to store the total number of edges in graph */
496  int** degrees, /**< pointer to store the degrees of the nodes */
497  int* maxdegrees, /**< pointer to store the maximal size of the degree array */
498  int* nnodesfromG1, /**< pointer to store number of nodes in sassy graph arising from G1 (or NULL) */
499  SCIP_Bool* success /**< pointer to store whether the graph could be built */
500  )
501 {
502  SYM_SYMTYPE symtype;
503  SYM_NODETYPE comparetype;
504  SCIP_Bool groupByConstraints;
505  SYM_GRAPH* graph;
506  int* nvarused1 = NULL;
507  int* nvarused2 = NULL;
508  int* varlabel = NULL;
509  int* groupfirsts = NULL;
510  int* groupseconds = NULL;
511  int* groupcolors = NULL;
512  int ngroupedges = 0;
513  int nusedvars = 0;
514  int nodeshift;
515  int curnnodes;
516  int nvarnodestoadd;
517  int internodeid;
518  int nsymvars;
519  int nsymedges;
520  int first;
521  int second;
522  int color;
523  int e;
524  int i;
525  int j;
526 
527  assert( scip != NULL );
528  assert( graph1 != NULL );
529  assert( graph2 != NULL );
530  assert( G != NULL || determinesize );
531  assert( nnodes != NULL );
532  assert( nedges != NULL );
533  assert( degrees != NULL );
534  assert( maxdegrees != NULL );
535  assert( success != NULL );
536 
537  *success = FALSE;
538 
539  /* graphs cannot be symmetric */
540  if ( SCIPgetSymgraphNEdges(graph1) != SCIPgetSymgraphNEdges(graph2)
541  || SCIPgetSymgraphNVars(graph1) != SCIPgetSymgraphNVars(graph2) )
542  return SCIP_OKAY;
543 
544  /* collect basic information from symmetry detection graph */
545  nsymvars = SCIPgetSymgraphNVars(graph1);
546  nsymedges = SCIPgetSymgraphNEdges(graph1);
547  symtype = SCIPgetSymgraphSymtype(graph1);
548  switch ( symtype )
549  {
550  case SYM_SYMTYPE_PERM:
551  nvarnodestoadd = nsymvars;
552  break;
553  default:
554  assert( symtype == SYM_SYMTYPE_SIGNPERM );
555  nvarnodestoadd = 2 * nsymvars;
556  }
557 
558  /* find the variables that are contained in an edge */
559  SCIP_CALL( SCIPallocClearBufferArray(scip, &nvarused1, nvarnodestoadd) );
560  SCIP_CALL( SCIPallocClearBufferArray(scip, &nvarused2, nvarnodestoadd) );
561  SCIP_CALL( SCIPallocBufferArray(scip, &varlabel, nvarnodestoadd) );
562 
563  for (e = 0; e < nsymedges; ++e)
564  {
565  first = SCIPgetSymgraphEdgeFirst(graph1, e);
566  second = SCIPgetSymgraphEdgeSecond(graph1, e);
567  if ( first < 0 )
568  nvarused1[-first - 1] += 1;
569  if ( second < 0 )
570  nvarused1[-second - 1] += 1;
571 
572  first = SCIPgetSymgraphEdgeFirst(graph2, e);
573  second = SCIPgetSymgraphEdgeSecond(graph2, e);
574  if ( first < 0 )
575  nvarused2[-first - 1] += 1;
576  if ( second < 0 )
577  nvarused2[-second - 1] += 1;
578  }
579 
580  for (j = 0; j < nvarnodestoadd; ++j)
581  {
582  /* graphs cannot be identical */
583  if ( nvarused1[j] != nvarused2[j] )
584  {
585  SCIPfreeBufferArray(scip, &varlabel);
586  SCIPfreeBufferArray(scip, &nvarused2);
587  SCIPfreeBufferArray(scip, &nvarused1);
588 
589  return SCIP_OKAY;
590  }
591 
592  /* relabel variables by restricting to variables used in constraint (or their negation) */
593  if ( nvarused1[j] > 0 || nvarused1[j % SCIPgetSymgraphNVars(graph1)] > 0 )
594  varlabel[j] = nusedvars++;
595  else
596  varlabel[j] = -1;
597  }
598 
599  /* possibly find number of nodes in sassy graph and allocate memory for dynamic array */
600  if ( determinesize )
601  {
602  *degrees = NULL;
603  *maxdegrees = 0;
604  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees,
605  SCIPgetSymgraphNNodes(graph1) + SCIPgetSymgraphNNodes(graph2) + 2 * nusedvars + 100) );
606 
607  *nnodes = 0;
608  *nedges = 0;
609  }
610 
611  /* determine grouping depending on the number of rhs vs. variables */
612  if ( SCIPgetSymgraphNConsnodes(graph1) < SCIPgetSymgraphNVars(graph1) )
613  groupByConstraints = TRUE;
614  else
615  groupByConstraints = FALSE;
616 
617  /* allocate arrays to collect edges to be grouped */
618  SCIP_CALL( SCIPallocBufferArray(scip, &groupfirsts, nsymedges) );
619  SCIP_CALL( SCIPallocBufferArray(scip, &groupseconds, nsymedges) );
620  SCIP_CALL( SCIPallocBufferArray(scip, &groupcolors, nsymedges) );
621 
622  /* collect information or generate graphs, we shift the node indices of the second graph when adding them to G */
623  nodeshift = 0;
624  for (i = 0; i < 2; ++i)
625  {
626  curnnodes = 0;
627  graph = i == 0 ? graph1 : graph2;
628  ngroupedges = 0;
629 
630  /* possibly add nodes for variables and remaining nodes, each variable gets a unique color */
631  if ( determinesize )
632  {
633  /* add nodes for variables */
634  for (j = 0; j < nvarnodestoadd; ++j)
635  {
636  if ( varlabel[j] >= 0 )
637  {
638  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, *nnodes + 1) );
639  (*degrees)[nodeshift + varlabel[j]] = 0;
640  ++(*nnodes);
641  ++curnnodes;
642  }
643  }
644 
645  /* add nodes for remaining nodes of graph */
646  for (j = 0; j < SCIPgetSymgraphNNodes(graph); ++j)
647  {
648  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, *nnodes + 1) );
649  (*degrees)[nodeshift + nusedvars + j] = 0;
650  ++(*nnodes);
651  ++curnnodes;
652  }
653  }
654  else
655  {
656  assert( G != NULL );
657 
658  /* add nodes for variables, each variable gets a unique color */
659  for (j = 0; j < nvarnodestoadd; ++j)
660  {
661  if ( varlabel[j] >= 0 )
662  {
663  (void) G->add_vertex(j, (*degrees)[nodeshift + varlabel[j]]);
664  ++curnnodes;
665  }
666  }
667 
668  /* add nodes for remaining nodes of graph, ensure that colors do not conflict with variable colors */
669  for (j = 0; j < SCIPgetSymgraphNNodes(graph); ++j)
670  {
671  (void) G->add_vertex(nusedvars + SCIPgetSymgraphNodeColor(graph, j),
672  (*degrees)[nodeshift + nusedvars + j]);
673  ++curnnodes;
674  }
675  }
676 
677  /* loop through all edges of the symmetry detection graph and either get degrees of nodes or add edges */
678  internodeid = nodeshift + curnnodes;
679  for (e = 0; e < nsymedges; ++e)
680  {
681  first = SCIPgetSymgraphEdgeFirst(graph, e);
682  second = SCIPgetSymgraphEdgeSecond(graph, e);
683 
684  /* get the first and second node in edge (corrected by variable shift) */
685  if ( first < 0 )
686  first = varlabel[-first - 1];
687  else
688  first = nusedvars + first;
689  if ( second < 0 )
690  second = varlabel[-second - 1];
691  else
692  second = nusedvars + second;
693 
694  /* check whether edge is used for grouping */
695  if ( ! SCIPhasGraphUniqueEdgetype(graph) && isEdgeGroupable(graph, e, groupByConstraints) )
696  {
697  /* store edge, first becomes the cons or var node */
698  comparetype = groupByConstraints ? SYM_NODETYPE_CONS : SYM_NODETYPE_VAR;
699 
700  if ( SCIPgetSymgraphNodeType(graph, SCIPgetSymgraphEdgeFirst(graph, e)) == comparetype )
701  {
702  groupfirsts[ngroupedges] = nodeshift + first;
703  groupseconds[ngroupedges] = nodeshift + second;
704  }
705  else
706  {
707  groupfirsts[ngroupedges] = nodeshift + second;
708  groupseconds[ngroupedges] = nodeshift + first;
709  }
710  groupcolors[ngroupedges++] = nusedvars + SCIPgetSymgraphEdgeColor(graph, e);
711  }
712  else
713  {
714  /* immediately add edge or increase degrees */
715  assert(0 <= first && first < *nnodes);
716  assert(0 <= second && second < *nnodes);
717 
718  /* possibly split edge if it is colored */
719  if ( ! SCIPhasGraphUniqueEdgetype(graph) && SCIPisSymgraphEdgeColored(graph, e) )
720  {
721  if ( determinesize )
722  {
723  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, internodeid + 1) );
724 
725  ++(*degrees)[nodeshift + first];
726  ++(*degrees)[nodeshift + second];
727  (*degrees)[internodeid] = 2;
728  ++(*nnodes);
729  *nedges += 2;
730  }
731  else
732  {
733  assert( internodeid < *nnodes );
734  assert( G != NULL );
735 
736  color = SCIPgetSymgraphEdgeColor(graph, e);
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);
740  }
741  ++internodeid;
742  ++curnnodes;
743  }
744  else
745  {
746  if ( determinesize )
747  {
748  ++(*degrees)[nodeshift + first];
749  ++(*degrees)[nodeshift + second];
750  ++(*nedges);
751  }
752  else
753  {
754  assert( G != NULL );
755 
756  if ( first < second )
757  G->add_edge((unsigned) (nodeshift + first), (unsigned) (nodeshift + second));
758  else
759  G->add_edge((unsigned) (nodeshift + second), (unsigned) (nodeshift + first));
760  }
761  }
762  }
763  }
764 
765  /* possibly add groupable edges */
766  if ( ngroupedges > 0 )
767  {
768  int firstidx = 0;
769  int firstnodeidx;
770  int naddednodes;
771  int naddededges;
772 
773  /* sort edges according to their first nodes */
774  SCIPsortIntIntInt(groupfirsts, groupseconds, groupcolors, ngroupedges);
775  firstnodeidx = groupfirsts[0];
776 
777  for (j = 1; j < ngroupedges; ++j)
778  {
779  /* if a new first node has been found, group the edges of the previous first node; ignoring the last group */
780  if ( groupfirsts[j] != firstnodeidx )
781  {
782  SCIP_CALL( addOrDetermineEffectOfGroupedEdges(scip, G, determinesize, &internodeid, degrees, maxdegrees,
783  nnodes, nedges, firstnodeidx, &groupseconds[firstidx], &groupcolors[firstidx], j - firstidx,
784  &naddednodes, &naddededges) );
785 
786  firstidx = j;
787  firstnodeidx = groupfirsts[j];
788 
789  if ( determinesize )
790  {
791  *nnodes += naddednodes;
792  *nedges += naddededges;
793  }
794  curnnodes += naddednodes;
795  }
796  }
797 
798  /* process the last group */
799  SCIP_CALL( addOrDetermineEffectOfGroupedEdges(scip, G, determinesize, &internodeid, degrees, maxdegrees,
800  nnodes, nedges, firstnodeidx, &groupseconds[firstidx], &groupcolors[firstidx], ngroupedges - firstidx,
801  &naddednodes, &naddededges) );
802 
803  if ( determinesize )
804  {
805  *nnodes += naddednodes;
806  *nedges += naddededges;
807  }
808  curnnodes += naddednodes;
809  }
810 
811  /* for signed permutation, also add edges connecting a variable and its negation */
813  {
814  if ( determinesize )
815  {
816  for (j = 0; j < nusedvars; ++j)
817  ++(*degrees)[nodeshift + j];
818  (*nedges) += nusedvars / 2;
819  }
820  else
821  {
822  assert( G != NULL );
823 
824  for (j = 0; j < nusedvars/2; ++j)
825  G->add_edge((unsigned) (nodeshift + j), (unsigned) (nodeshift + j + nusedvars / 2));
826  }
827  }
828  nodeshift = curnnodes;
829 
830  if ( i == 0 && nnodesfromG1 != NULL )
831  *nnodesfromG1 = curnnodes;
832  }
833 
834  SCIPfreeBufferArray(scip, &groupcolors);
835  SCIPfreeBufferArray(scip, &groupseconds);
836  SCIPfreeBufferArray(scip, &groupfirsts);
837 
838  SCIPfreeBufferArray(scip, &varlabel);
839  SCIPfreeBufferArray(scip, &nvarused2);
840  SCIPfreeBufferArray(scip, &nvarused1);
841 
842  *success = TRUE;
843 
844  return SCIP_OKAY;
845 }
846 
847 
848 /** compute generators of symmetry group */
850  SCIP* scip, /**< SCIP pointer */
851  sassy::static_graph* sassygraph, /**< pointer to hold sassy graph being created */
852  SYM_GRAPH* graph, /**< symmetry detection graph */
853  SCIP_Bool* success /**< pointer to store whether sassygraph could be built */
854  )
855 {
856  int* degrees;
857  int maxdegrees;
858  int nnodes;
859  int nedges;
860 
861  assert( scip != NULL );
862  assert( sassygraph != NULL );
863  assert( graph != NULL );
864 
865  *success = FALSE;
866 
867  /* determine number of nodes and edges */
868  SCIP_CALL( createOrDetermineSizeGraph(scip, graph, TRUE, NULL, &nnodes, &nedges, &degrees, &maxdegrees, success) );
869 
870  if ( ! *success )
871  {
873  "Stopped symmetry computation: Symmetry graph would become too large.\n");
874  return SCIP_OKAY;
875  }
876 
877  /* init graph */
878  (*sassygraph).initialize_graph((unsigned) nnodes, (unsigned) nedges);
879 
880  /* add the nodes for linear and nonlinear constraints to the graph */
881  SCIP_CALL( createOrDetermineSizeGraph(scip, graph, FALSE, sassygraph,
882  &nnodes, &nedges, &degrees, &maxdegrees, success) );
883 
884  SCIPfreeBlockMemoryArray(scip, &degrees, maxdegrees);
885 
886  SCIPdebugMsg(scip, "Symmetry detection graph has %d nodes.\n", nnodes);
887 
888  return SCIP_OKAY;
889 }
890 
891 /** returns whether two given graphs are identical */
893  SCIP* scip, /**< SCIP pointer */
894  sassy::static_graph* sassygraph, /**< pointer to hold sassy graph being created */
895  SYM_GRAPH* G1, /**< first graph */
896  SYM_GRAPH* G2, /**< second graph */
897  int* nnodes, /**< pointer to store number of nodes in sassy graph */
898  int* nnodesfromG1, /**< pointer to store number of nodes in sassy graph arising from G1 */
899  SCIP_Bool* success /**< pointer to store whether sassygraph could be built */
900  )
901 {
902  int* degrees = NULL;
903  int maxdegrees = 0;
904  int nedges;
905 
906  assert( scip != NULL );
907  assert( sassygraph != NULL );
908  assert( G1 != NULL );
909  assert( G2 != NULL );
910  assert( nnodes != NULL );
911  assert( nnodesfromG1 != NULL );
912  assert( success != NULL );
913 
914  *success = FALSE;
915  *nnodes = 0;
916  *nnodesfromG1 = 0;
917 
918  /* some simple checks */
919  if ( G1->nnodes != G2->nnodes || G1->nopnodes != G2->nopnodes || G1->nvalnodes != G2->nvalnodes
920  || G1->nconsnodes != G2->nconsnodes || G1->nedges != G2->nedges )
921  return SCIP_OKAY;
922 
923  /* determine number of nodes and edges */
925  nnodes, &nedges, &degrees, &maxdegrees, nnodesfromG1, success) );
926 
927  if ( ! *success )
928  {
929  assert( degrees == NULL );
930  assert( maxdegrees == 0 );
931  return SCIP_OKAY;
932  }
933  if ( *nnodes % 2 != 0 )
934  {
935  assert( degrees != NULL );
936  assert( maxdegrees > 0 );
937 
938  SCIPfreeBlockMemoryArray(scip, &degrees, maxdegrees);
939  return SCIP_OKAY;
940  }
941 
942  /* init graph */
943  (*sassygraph).initialize_graph((unsigned) *nnodes, (unsigned) nedges);
944 
945  /* add the nodes for linear and nonlinear constraints to the graph */
946  SCIP_CALL_ABORT( createOrDetermineSizeGraphCheck(scip, G1, G2, FALSE, sassygraph,
947  nnodes, &nedges, &degrees, &maxdegrees, NULL, success) );
948  assert( *success );
949 
950  SCIPfreeBlockMemoryArray(scip, &degrees, maxdegrees);
951 
952  return SCIP_OKAY;
953 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define NULL
Definition: def.h:267
public methods for memory management
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
int SCIPgetSymgraphNodeColor(SYM_GRAPH *graph, int nodeidx)
void SCIPsortIntIntInt(int *intarray1, int *intarray2, int *intarray3, int len)
methods to build sassy graph for symmetry detection
private functions to work with algebraic expressions
#define FALSE
Definition: def.h:94
int SCIPgetSymgraphNEdges(SYM_GRAPH *graph)
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_Bool SCIPhasGraphUniqueEdgetype(SYM_GRAPH *graph)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
variable expression handler
#define SCIPdebugMsg
Definition: scip_message.h:78
static SCIP_Bool isEdgeGroupable(SYM_GRAPH *graph, int edgeidx, SCIP_Bool groupbycons)
methods for dealing with symmetry detection graphs
int SCIPgetSymgraphEdgeFirst(SYM_GRAPH *graph, int edgeidx)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIP_Bool SCIPisSymgraphEdgeColored(SYM_GRAPH *graph, int edgeidx)
power and signed power expression handlers
#define SCIP_CALL(x)
Definition: def.h:380
SYM_SYMTYPE SCIPgetSymgraphSymtype(SYM_GRAPH *graph)
#define SCIPensureBlockMemoryArray(scip, ptr, arraysizeptr, minsize)
Definition: scip_mem.h:107
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIP_Bool
Definition: def.h:91
constraint handler for nonlinear constraints specified by algebraic expressions
SCIP_RETCODE SYMbuildSassyGraphCheck(SCIP *scip, sassy::static_graph *sassygraph, SYM_GRAPH *G1, SYM_GRAPH *G2, int *nnodes, int *nnodesfromG1, SCIP_Bool *success)
enum SYM_Symtype SYM_SYMTYPE
Definition: type_symmetry.h:64
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SYMbuildSassyGraph(SCIP *scip, sassy::static_graph *sassygraph, SYM_GRAPH *graph, SCIP_Bool *success)
int SCIPgetSymgraphEdgeColor(SYM_GRAPH *graph, int edgeidx)
static SCIP_RETCODE createOrDetermineSizeGraph(SCIP *scip, SYM_GRAPH *graph, SCIP_Bool determinesize, sassy::static_graph *G, int *nnodes, int *nedges, int **degrees, int *maxdegrees, SCIP_Bool *success)
int SCIPgetSymgraphNConsnodes(SYM_GRAPH *graph)
SYM_NODETYPE SCIPgetSymgraphNodeType(SYM_GRAPH *graph, int nodeidx)
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)
int SCIPgetSymgraphNVars(SYM_GRAPH *graph)
sum expression handler
#define nnodes
Definition: gastrans.c:74
#define SCIP_CALL_ABORT(x)
Definition: def.h:359
enum SYM_Nodetype SYM_NODETYPE
Definition: type_symmetry.h:74
int SCIPgetSymgraphVarnodeColor(SYM_GRAPH *graph, int nodeidx)
int SCIPgetSymgraphNNodes(SYM_GRAPH *graph)
int SCIPgetSymgraphEdgeSecond(SYM_GRAPH *graph, int edgeidx)
static SCIP_RETCODE createOrDetermineSizeGraphCheck(SCIP *scip, SYM_GRAPH *graph1, SYM_GRAPH *graph2, SCIP_Bool determinesize, sassy::static_graph *G, int *nnodes, int *nedges, int **degrees, int *maxdegrees, int *nnodesfromG1, SCIP_Bool *success)