SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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.c
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 */
46static
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);
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
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 {
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 */
107static
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 );
143
144 *naddednodes = 0;
145 *naddededges = 0;
146
147 /* sort edges according to color */
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 {
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 G->add_vertex((unsigned) 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 {
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 G->add_vertex((unsigned) curcolor, (unsigned) (*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;
213 ++(*internodeid);
214
215 return SCIP_OKAY;
216}
217
218/** either creates a graph or determines its size */
219static
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;
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 */
278 *nedges = 0;
279
280 /* possibly allocate memory for degrees (will grow dynamically) */
281 *degrees = NULL;
282 *maxdegrees = 0;
284 for (j = 0; j < *nnodes; ++j)
285 (*degrees)[j] = 0;
286 }
287 else
288 {
289 /* add nodes for variables */
290 for (j = 0; j < nvarnodestoadd; ++j)
291 G->add_vertex((unsigned) SCIPgetSymgraphVarnodeColor(graph, j), (*degrees)[j]);
292
293 /* add nodes for remaining nodes of graph */
294 for (j = 0; j < SCIPgetSymgraphNNodes(graph); ++j)
295 G->add_vertex((unsigned) SCIPgetSymgraphNodeColor(graph, j), (*degrees)[nvarnodestoadd + j]);
296 }
297
298 /* determine grouping depending on the number of rhs vs. variables */
300
301 /* allocate arrays to collect edges to be grouped */
306
307 /* loop through all edges of the symmetry detection graph and either get degrees of nodes or add edges */
309 for (e = 0; e < SCIPgetSymgraphNEdges(graph); ++e)
310 {
311 first = SCIPgetSymgraphEdgeFirst(graph, e);
313
314 /* get the first and second node in edge (corrected by variable shift) */
315 if ( first < 0 )
316 first = -first - 1;
317 else
318 first += nvarnodestoadd;
319 if ( second < 0 )
320 second = -second - 1;
321 else
323 assert(first >= 0);
324 assert(second >= 0);
325
326 /* check whether edge is used for grouping */
328 {
329 /* store edge, first becomes the cons or var node */
331
333 {
334 groupfirsts[ngroupedges] = first;
336 }
337 else
338 {
340 groupseconds[ngroupedges] = first;
341 }
343 }
344 else
345 {
346 /* immediately add edge or increase degrees */
347 assert(0 <= first && first < *nnodes);
348 assert(0 <= second && second < *nnodes);
349
350 /* possibly split edge if it is colored */
352 {
353 if ( determinesize )
354 {
356
357 ++(*degrees)[first];
358 ++(*degrees)[second];
359 (*degrees)[internodeid] = 2;
360 ++(*nnodes);
361 *nedges += 2;
362 ++internodeid;
363 }
364 else
365 {
367
369 G->add_vertex((unsigned) color, (unsigned) (*degrees)[internodeid]);
370
371 G->add_edge((unsigned) first, (unsigned) internodeid);
372 G->add_edge((unsigned) second, (unsigned) internodeid++);
373 }
374 }
375 else
376 {
377 if ( determinesize )
378 {
379 ++(*degrees)[first];
380 ++(*degrees)[second];
381 ++(*nedges);
382 }
383 else
384 {
385 if ( first < second )
386 G->add_edge((unsigned) first, (unsigned) second);
387 else
388 G->add_edge((unsigned) second, (unsigned) first);
389 }
390 }
391 }
392 }
393
394 /* possibly add groupable edges */
395 if ( ngroupedges > 0 )
396 {
397 int firstidx = 0;
398 int firstnodeidx;
399 int naddednodes;
400 int naddededges;
401
402 /* sort edges according to their first nodes */
405
406 for (j = 1; j < ngroupedges; ++j)
407 {
408 /* if a new first node has been found, group the edges of the previous first node; ignoring the last group */
409 if ( groupfirsts[j] != firstnodeidx )
410 {
412 nnodes, nedges, firstnodeidx, &groupseconds[firstidx], &groupcolors[firstidx], j - firstidx,
414
415 firstidx = j;
417
418 if ( determinesize )
419 {
421 *nedges += naddededges;
422 }
423 }
424 }
425
426 /* process the last group */
428 nnodes, nedges, firstnodeidx, &groupseconds[firstidx], &groupcolors[firstidx], ngroupedges - firstidx,
430
431 if ( determinesize )
432 {
434 *nedges += naddededges;
435 }
436 }
437
441
442 /* for signed permutation, also add edges connecting a variable and its negation */
443 switch ( SCIPgetSymgraphSymtype(graph) )
444 {
446 if ( determinesize )
447 {
448 for (j = 0; j < nvarnodestoadd; ++j)
449 ++(*degrees)[j];
450 *nedges += nsymvars;
451 }
452 else
453 {
454 for (j = 0; j < nsymvars; ++j)
455 G->add_edge((unsigned) j, (unsigned) j + nsymvars);
456 }
457 break;
458 default:
460 }
461
462 if ( determinesize )
463 {
464 SCIPdebugMsg(scip, "#nodes: %d\n", *nnodes);
465 SCIPdebugMsg(scip, "#nodes for variables: %d\n", nvarnodestoadd);
466 SCIPdebugMsg(scip, "#nodes for rhs: %d\n", SCIPgetSymgraphNConsnodes(graph));
467 SCIPdebugMsg(scip, "#edges: %d\n", *nedges);
468 }
469
470 return SCIP_OKAY;
471}
472
473/** either creates a graph for checking symmetries or determines its size
474 *
475 * The input are two graphs and the graph to be constructed consists of copies
476 * of the two input graphs, in which non-variable nodes are colored according
477 * to the colors used in symmetry detection. Each variable gets a unique color.
478 */
479static
481 SCIP* scip, /**< SCIP instance */
482 SYM_GRAPH* graph1, /**< first symmetry detection graph */
483 SYM_GRAPH* graph2, /**< second symmetry detection graph */
484 SCIP_Bool determinesize, /**< whether only the size of the graph shall be determined */
485 sassy::static_graph* G, /**< graph to be constructed */
486 int* nnodes, /**< pointer to store the total number of nodes in graph */
487 int* nedges, /**< pointer to store the total number of edges in graph */
488 int** degrees, /**< pointer to store the degrees of the nodes */
489 int* maxdegrees, /**< pointer to store the maximal size of the degree array */
490 int* nnodesfromG1, /**< pointer to store number of nodes in sassy graph arising from G1 (or NULL) */
491 SCIP_Bool* success /**< pointer to store whether the graph could be built */
492 )
493{
494 SYM_SYMTYPE symtype;
496 SCIP_Bool groupByConstraints;
497 SYM_GRAPH* graph;
498 int* nvarused1 = NULL;
499 int* nvarused2 = NULL;
500 int* varlabel = NULL;
501 int* groupfirsts = NULL;
502 int* groupseconds = NULL;
503 int* groupcolors = NULL;
504 int ngroupedges = 0;
505 int nusedvars = 0;
506 int nodeshift;
507 int curnnodes;
508 int nvarnodestoadd;
509 int internodeid;
510 int nsymvars;
511 int nsymedges;
512 int first;
513 int second;
514 int color;
515 int e;
516 int i;
517 int j;
518
519 assert( scip != NULL );
520 assert( graph1 != NULL );
521 assert( graph2 != NULL );
522 assert( G != NULL || determinesize );
523 assert( nnodes != NULL );
524 assert( nedges != NULL );
525 assert( degrees != NULL );
526 assert( maxdegrees != NULL );
527 assert( success != NULL );
528
529 *success = FALSE;
530
531 /* graphs cannot be symmetric */
534 return SCIP_OKAY;
535
536 /* collect basic information from symmetry detection graph */
537 nsymvars = SCIPgetSymgraphNVars(graph1);
540 switch ( symtype )
541 {
542 case SYM_SYMTYPE_PERM:
543 nvarnodestoadd = nsymvars;
544 break;
545 default:
546 assert( symtype == SYM_SYMTYPE_SIGNPERM );
547 nvarnodestoadd = 2 * nsymvars;
548 }
549
550 /* find the variables that are contained in an edge */
554
555 for (e = 0; e < nsymedges; ++e)
556 {
559 if ( first < 0 )
560 nvarused1[-first - 1] += 1;
561 if ( second < 0 )
562 nvarused1[-second - 1] += 1;
563
566 if ( first < 0 )
567 nvarused2[-first - 1] += 1;
568 if ( second < 0 )
569 nvarused2[-second - 1] += 1;
570 }
571
572 for (j = 0; j < nvarnodestoadd; ++j)
573 {
574 /* graphs cannot be identical */
575 if ( nvarused1[j] != nvarused2[j] )
576 {
580
581 return SCIP_OKAY;
582 }
583
584 /* relabel variables by restricting to variables used in constraint (or their negation) */
585 if ( nvarused1[j] > 0 || nvarused1[j % SCIPgetSymgraphNVars(graph1)] > 0 )
586 varlabel[j] = nusedvars++;
587 else
588 varlabel[j] = -1;
589 }
590
591 /* possibly find number of nodes in sassy graph and allocate memory for dynamic array */
592 if ( determinesize )
593 {
594 *degrees = NULL;
595 *maxdegrees = 0;
598
599 *nnodes = 0;
600 *nedges = 0;
601 }
602
603 /* determine grouping depending on the number of rhs vs. variables */
605
606 /* allocate arrays to collect edges to be grouped */
610
611 /* collect information or generate graphs, we shift the node indices of the second graph when adding them to G */
612 nodeshift = 0;
613 for (i = 0; i < 2; ++i)
614 {
615 curnnodes = 0;
616 graph = i == 0 ? graph1 : graph2;
617 ngroupedges = 0;
618
619 /* possibly add nodes for variables and remaining nodes, each variable gets a unique color */
620 if ( determinesize )
621 {
622 /* add nodes for variables */
623 for (j = 0; j < nvarnodestoadd; ++j)
624 {
625 if ( varlabel[j] >= 0 )
626 {
628 (*degrees)[nodeshift + varlabel[j]] = 0;
629 ++(*nnodes);
630 ++curnnodes;
631 }
632 }
633
634 /* add nodes for remaining nodes of graph */
635 for (j = 0; j < SCIPgetSymgraphNNodes(graph); ++j)
636 {
638 (*degrees)[nodeshift + nusedvars + j] = 0;
639 ++(*nnodes);
640 ++curnnodes;
641 }
642 }
643 else
644 {
645 /* add nodes for variables, each variable gets a unique color */
646 for (j = 0; j < nvarnodestoadd; ++j)
647 {
648 if ( varlabel[j] >= 0 )
649 {
650 G->add_vertex((unsigned) j, (*degrees)[nodeshift + varlabel[j]]);
651 ++curnnodes;
652 }
653 }
654
655 /* add nodes for remaining nodes of graph, ensure that colors do not conflict with variable colors */
656 for (j = 0; j < SCIPgetSymgraphNNodes(graph); ++j)
657 {
658 G->add_vertex((unsigned) nusedvars + SCIPgetSymgraphNodeColor(graph, j),
659 (*degrees)[nodeshift + nusedvars + j]);
660 ++curnnodes;
661 }
662 }
663
664 /* loop through all edges of the symmetry detection graph and either get degrees of nodes or add edges */
666 for (e = 0; e < nsymedges; ++e)
667 {
668 first = SCIPgetSymgraphEdgeFirst(graph, e);
670
671 /* get the first and second node in edge (corrected by variable shift) */
672 if ( first < 0 )
673 first = varlabel[-first - 1];
674 else
675 first = nusedvars + first;
676 if ( second < 0 )
677 second = varlabel[-second - 1];
678 else
680
681 /* check whether edge is used for grouping */
683 {
684 /* store edge, first becomes the cons or var node */
686
688 {
691 }
692 else
693 {
696 }
698 }
699 else
700 {
701 /* immediately add edge or increase degrees */
702 assert(0 <= first && first < *nnodes);
703 assert(0 <= second && second < *nnodes);
704
705 /* possibly split edge if it is colored */
707 {
708 if ( determinesize )
709 {
711
712 ++(*degrees)[nodeshift + first];
713 ++(*degrees)[nodeshift + second];
714 (*degrees)[internodeid] = 2;
715 ++(*nnodes);
716 *nedges += 2;
717 }
718 else
719 {
721
723 G->add_vertex((unsigned) nusedvars + color, (unsigned) (*degrees)[internodeid]);
724 G->add_edge((unsigned) nodeshift + first, (unsigned) internodeid);
725 G->add_edge((unsigned) nodeshift + second, (unsigned) internodeid);
726 }
727 ++internodeid;
728 ++curnnodes;
729 }
730 else
731 {
732 if ( determinesize )
733 {
734 ++(*degrees)[nodeshift + first];
735 ++(*degrees)[nodeshift + second];
736 ++(*nedges);
737 }
738 else
739 {
740 if ( first < second )
741 G->add_edge((unsigned) nodeshift + first, (unsigned) nodeshift + second);
742 else
743 G->add_edge((unsigned) nodeshift + second, (unsigned) nodeshift + first);
744 }
745 }
746 }
747 }
748
749 /* possibly add groupable edges */
750 if ( ngroupedges > 0 )
751 {
752 int firstidx = 0;
753 int firstnodeidx;
754 int naddednodes;
755 int naddededges;
756
757 /* sort edges according to their first nodes */
760
761 for (j = 1; j < ngroupedges; ++j)
762 {
763 /* if a new first node has been found, group the edges of the previous first node; ignoring the last group */
764 if ( groupfirsts[j] != firstnodeidx )
765 {
767 nnodes, nedges, firstnodeidx, &groupseconds[firstidx], &groupcolors[firstidx], j - firstidx,
769
770 firstidx = j;
772
773 if ( determinesize )
774 {
776 *nedges += naddededges;
777 }
779 }
780 }
781
782 /* process the last group */
784 nnodes, nedges, firstnodeidx, &groupseconds[firstidx], &groupcolors[firstidx], ngroupedges - firstidx,
786
787 if ( determinesize )
788 {
790 *nedges += naddededges;
791 }
793 }
794
795 /* for signed permutation, also add edges connecting a variable and its negation */
797 {
798 if ( determinesize )
799 {
800 for (j = 0; j < nusedvars; ++j)
801 ++(*degrees)[nodeshift + j];
802 (*nedges) += nusedvars / 2;
803 }
804 else
805 {
806 for (j = 0; j < nusedvars/2; ++j)
807 G->add_edge((unsigned) nodeshift + j, (unsigned) nodeshift + j + nusedvars/2);
808 }
809 }
811
812 if ( i == 0 && nnodesfromG1 != NULL )
814 }
815
819
823
824 *success = TRUE;
825
826 return SCIP_OKAY;
827}
828
829
830/** compute generators of symmetry group */
832 SCIP* scip, /**< SCIP pointer */
833 sassy::static_graph* sassygraph, /**< pointer to hold sassy graph being created */
834 SYM_GRAPH* graph, /**< symmetry detection graph */
835 SCIP_Bool* success /**< pointer to store whether sassygraph could be built */
836 )
837{
838 int* degrees;
839 int maxdegrees;
840 int nnodes;
841 int nedges;
842
843 assert( scip != NULL );
844 assert( sassygraph != NULL );
845 assert( graph != NULL );
846
847 *success = FALSE;
848
849 /* determine number of nodes and edges */
850 SCIP_CALL( createOrDetermineSizeGraph(scip, graph, TRUE, NULL, &nnodes, &nedges, &degrees, &maxdegrees, success) );
851
852 if ( ! *success )
853 {
855 "Stopped symmetry computation: Symmetry graph would become too large.\n");
856 return SCIP_OKAY;
857 }
858
859 /* init graph */
860 (*sassygraph).initialize_graph((unsigned) nnodes, (unsigned) nedges);
861
862 /* add the nodes for linear and nonlinear constraints to the graph */
864 &nnodes, &nedges, &degrees, &maxdegrees, success) );
865
867
868 SCIPdebugMsg(scip, "Symmetry detection graph has %d nodes.\n", nnodes);
869
870 return SCIP_OKAY;
871}
872
873/** returns whether two given graphs are identical */
875 SCIP* scip, /**< SCIP pointer */
876 sassy::static_graph* sassygraph, /**< pointer to hold sassy graph being created */
877 SYM_GRAPH* G1, /**< first graph */
878 SYM_GRAPH* G2, /**< second graph */
879 int* nnodes, /**< pointer to store number of nodes in sassy graph */
880 int* nnodesfromG1, /**< pointer to store number of nodes in sassy graph arising from G1 */
881 SCIP_Bool* success /**< pointer to store whether sassygraph could be built */
882 )
883{
884 int* degrees = NULL;
885 int maxdegrees = 0;
886 int nedges;
887
888 assert( scip != NULL );
889 assert( sassygraph != NULL );
890 assert( G1 != NULL );
891 assert( G2 != NULL );
892 assert( nnodes != NULL );
894 assert( success != NULL );
895
896 *success = FALSE;
897 *nnodes = 0;
898 *nnodesfromG1 = 0;
899
900 /* some simple checks */
901 if ( G1->nnodes != G2->nnodes || G1->nopnodes != G2->nopnodes || G1->nvalnodes != G2->nvalnodes
902 || G1->nconsnodes != G2->nconsnodes || G1->nedges != G2->nedges )
903 return SCIP_OKAY;
904
905 /* determine number of nodes and edges */
907 nnodes, &nedges, &degrees, &maxdegrees, nnodesfromG1, success) );
908
909 if ( ! *success )
910 {
911 assert( degrees == NULL );
912 assert( maxdegrees == 0 );
913 return SCIP_OKAY;
914 }
915 if ( *nnodes % 2 != 0 )
916 {
917 assert( degrees != NULL );
918 assert( maxdegrees > 0 );
919
921 return SCIP_OKAY;
922 }
923
924 /* init graph */
925 (*sassygraph).initialize_graph((unsigned) *nnodes, (unsigned) nedges);
926
927 /* add the nodes for linear and nonlinear constraints to the graph */
929 nnodes, &nedges, &degrees, &maxdegrees, NULL, success) );
930 assert( *success );
931
933
934 return SCIP_OKAY;
935}
static SCIP_Bool isEdgeGroupable(SYM_GRAPH *graph, int edgeidx, SCIP_Bool groupbycons)
SCIP_RETCODE SYMbuildSassyGraph(SCIP *scip, sassy::static_graph *sassygraph, SYM_GRAPH *graph, SCIP_Bool *success)
SCIP_RETCODE SYMbuildSassyGraphCheck(SCIP *scip, sassy::static_graph *sassygraph, SYM_GRAPH *G1, SYM_GRAPH *G2, int *nnodes, int *nnodesfromG1, SCIP_Bool *success)
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)
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)
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)
methods to build sassy graph for symmetry detection
Constraint handler for linear constraints in their most general form, .
constraint handler for nonlinear constraints specified by algebraic expressions
#define NULL
Definition def.h:267
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define SCIP_CALL_ABORT(x)
Definition def.h:353
#define SCIP_CALL(x)
Definition def.h:374
private functions to work with algebraic expressions
power and signed power expression handlers
sum expression handler
variable expression handler
#define nnodes
Definition gastrans.c:74
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
#define SCIPensureBlockMemoryArray(scip, ptr, arraysizeptr, minsize)
Definition scip_mem.h:107
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition scip_mem.h:126
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
SYM_NODETYPE SCIPgetSymgraphNodeType(SYM_GRAPH *graph, int nodeidx)
int SCIPgetSymgraphEdgeFirst(SYM_GRAPH *graph, int edgeidx)
SCIP_Bool SCIPhasGraphUniqueEdgetype(SYM_GRAPH *graph)
int SCIPgetSymgraphVarnodeColor(SYM_GRAPH *graph, int nodeidx)
int SCIPgetSymgraphNEdges(SYM_GRAPH *graph)
SYM_SYMTYPE SCIPgetSymgraphSymtype(SYM_GRAPH *graph)
int SCIPgetSymgraphEdgeSecond(SYM_GRAPH *graph, int edgeidx)
int SCIPgetSymgraphNConsnodes(SYM_GRAPH *graph)
int SCIPgetSymgraphNVars(SYM_GRAPH *graph)
SCIP_Bool SCIPisSymgraphEdgeColored(SYM_GRAPH *graph, int edgeidx)
int SCIPgetSymgraphNodeColor(SYM_GRAPH *graph, int nodeidx)
int SCIPgetSymgraphEdgeColor(SYM_GRAPH *graph, int edgeidx)
int SCIPgetSymgraphNNodes(SYM_GRAPH *graph)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortIntIntInt(int *intarray1, int *intarray2, int *intarray3, int len)
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
public methods for memory management
methods for dealing with symmetry detection graphs
@ SCIP_VERBLEVEL_MINIMAL
enum SCIP_Retcode SCIP_RETCODE
enum SYM_Symtype SYM_SYMTYPE
enum SYM_Nodetype SYM_NODETYPE
@ SYM_NODETYPE_CONS
@ SYM_NODETYPE_VAR
@ SYM_SYMTYPE_SIGNPERM
@ SYM_SYMTYPE_PERM