1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright 2002-2023 Zuse Institute Berlin                                */
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   symmetry_graph.h
26   	 * @ingroup PUBLICCOREAPI
27   	 * @brief  methods for dealing with symmetry detection graphs
28   	 * @author Christopher Hojny
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#ifndef __SCIP_SYMMETRY_GRAPH_H__
34   	#define __SCIP_SYMMETRY_GRAPH_H__
35   	
36   	#include "scip/def.h"
37   	#include "scip/type_retcode.h"
38   	#include "scip/type_scip.h"
39   	#include "scip/type_var.h"
40   	#include <symmetry/type_symmetry.h>
41   	
42   	#ifdef __cplusplus
43   	extern "C" {
44   	#endif
45   	
46   	
47   	/**@addtogroup PublicSymmetryGraphMethods
48   	 *
49   	 * @{
50   	 */
51   	
52   	/** creates and initializes a symmetry detection graph with memory for the given number of nodes and edges
53   	 *
54   	 *  @note at some point, the graph needs to be freed!
55   	 */
56   	SCIP_EXPORT
57   	SCIP_RETCODE SCIPcreateSymgraph(
58   	   SCIP*                 scip,               /**< SCIP data structure */
59   	   SYM_SYMTYPE           symtype,            /**< type of symmetries encoded in graph */
60   	   SYM_GRAPH**           graph,              /**< pointer to hold symmetry detection graph */
61   	   SCIP_VAR**            symvars,            /**< variables used in symmetry detection */
62   	   int                   nsymvars,           /**< number of variables used in symmetry detection */
63   	   int                   nopnodes,           /**< number of operator nodes */
64   	   int                   nvalnodes,          /**< number of value nodes */
65   	   int                   nconsnodes,         /**< number of constraint nodes */
66   	   int                   nedges              /**< number of edges */
67   	   );
68   	
69   	/** frees a symmetry detection graph */
70   	SCIP_EXPORT
71   	SCIP_RETCODE SCIPfreeSymgraph(
72   	   SCIP*                 scip,               /**< SCIP data structure */
73   	   SYM_GRAPH**           graph               /**< pointer to symmetry detection graph */
74   	   );
75   	
76   	/** copies an existing graph and changes variable nodes according to a permutation */
77   	SCIP_EXPORT
78   	SCIP_RETCODE SCIPcopySymgraph(
79   	   SCIP*                 scip,               /**< SCIP data structure */
80   	   SYM_GRAPH**           graph,              /**< pointer to hold copy of symmetry detection graph */
81   	   SYM_GRAPH*            origgraph,          /**< graph to be copied */
82   	   int*                  perm,               /**< permutation of variables */
83   	   SYM_SPEC              fixedtype           /**< variable types that must be fixed by symmetries */
84   	   );
85   	
86   	/** adds a symmetry detection graph for a linear constraint to existing graph
87   	 *
88   	 *  For permutation symmetries, a constraint node is added that is connected to all
89   	 *  variable nodes in the constraint. Edges are colored according to the variable coefficients.
90   	 *  For signed permutation symmetries, also edges connecting the constraint node and
91   	 *  the negated variable nodes are added, these edges are colored by the negative coefficients.
92   	 */
93   	SCIP_EXPORT
94   	SCIP_RETCODE SCIPextendPermsymDetectionGraphLinear(
95   	   SCIP*                 scip,               /**< SCIP data structure */
96   	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
97   	   SCIP_VAR**            vars,               /**< variable array of linear constraint */
98   	   SCIP_Real*            vals,               /**< coefficients of linear constraint */
99   	   int                   nvars,              /**< number of variables in linear constraint */
100  	   SCIP_CONS*            cons,               /**< constraint for which we encode symmetries */
101  	   SCIP_Real             lhs,                /**< left-hand side of constraint */
102  	   SCIP_Real             rhs,                /**< right-hand side of constraint */
103  	   SCIP_Bool*            success             /**< pointer to store whether graph could be built */
104  	   );
105  	
106  	/** adds nodes and edges corresponding to the aggregation of a variable to a symmetry detection graph
107  	 *
108  	 *  For permutation symmetries, the root node is connected with all variable nodes in the aggregation.
109  	 *  Edges are colored according to the variable coefficients.
110  	 *  For signed permutation symmetries, also edges connecting the root node and the negated variable
111  	 *  nodes are added, these edges are colored by the negative coefficients.
112  	 */
113  	SCIP_EXPORT
114  	SCIP_RETCODE SCIPaddSymgraphVarAggegration(
115  	   SCIP*                 scip,               /**< SCIP data structure */
116  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
117  	   int                   rootidx,            /**< index of root node of the aggregation */
118  	   SCIP_VAR**            vars,               /**< array of variables in aggregation */
119  	   SCIP_Real*            vals,               /**< coefficients of variables */
120  	   int                   nvars,              /**< number of variables in aggregation */
121  	   SCIP_Real             constant            /**< constant of aggregation */
122  	   );
123  	
124  	/*
125  	 * methods for adding and accessing nodes
126  	 */
127  	
128  	/** adds an operator node to a symmetry detection graph and returns its node index */
129  	SCIP_EXPORT
130  	SCIP_RETCODE SCIPaddSymgraphOpnode(
131  	   SCIP*                 scip,               /**< SCIP data structure */
132  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
133  	   int                   op,                 /**< int associated with operator of node */
134  	   int*                  nodeidx             /**< pointer to hold index of created node */
135  	   );
136  	
137  	/** adds a value node to a symmetry detection graph and returns its node index */
138  	SCIP_EXPORT
139  	SCIP_RETCODE SCIPaddSymgraphValnode(
140  	   SCIP*                 scip,               /**< SCIP data structure */
141  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
142  	   SCIP_Real             val,                /**< value of node */
143  	   int*                  nodeidx             /**< pointer to hold index of created node */
144  	   );
145  	
146  	/** adds a constraint node to a symmetry detection graph and returns its node index */
147  	SCIP_EXPORT
148  	SCIP_RETCODE SCIPaddSymgraphConsnode(
149  	   SCIP*                 scip,               /**< SCIP data structure */
150  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
151  	   SCIP_CONS*            cons,               /**< constraint of node */
152  	   SCIP_Real             lhs,                /**< left-hand side of node */
153  	   SCIP_Real             rhs,                /**< right-hand side of node */
154  	   int*                  nodeidx             /**< pointer to hold index of created node */
155  	   );
156  	
157  	/** returns the (hypothetical) node index of a variable */
158  	SCIP_EXPORT
159  	int SCIPgetSymgraphVarnodeidx(
160  	   SCIP*                 scip,               /**< SCIP data structure */
161  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
162  	   SCIP_VAR*             var                 /**< variable */
163  	   );
164  	
165  	/** returns the (hypothetical) node index of a negated variable */
166  	SCIP_EXPORT
167  	int SCIPgetSymgraphNegatedVarnodeidx(
168  	   SCIP*                 scip,               /**< SCIP data structure */
169  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
170  	   SCIP_VAR*             var                 /**< variable */
171  	   );
172  	
173  	/** updates the lhs of a constraint node */
174  	SCIP_EXPORT
175  	SCIP_RETCODE SCIPupdateSymgraphLhs(
176  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
177  	   int                   nodeidx,            /**< index of constraint node in graph */
178  	   SCIP_Real             newlhs              /**< new left-hand side of node */
179  	   );
180  	
181  	/** updates the rhs of a constraint node */
182  	SCIP_EXPORT
183  	SCIP_RETCODE SCIPupdateSymgraphRhs(
184  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
185  	   int                   nodeidx,            /**< index of constraint node in graph */
186  	   SCIP_Real             newrhs              /**< new reft-hand side of node */
187  	   );
188  	
189  	/** registers a variable node (corresponding to active variable) to be fixed by symmetry */
190  	SCIP_EXPORT
191  	SCIP_RETCODE SCIPfixSymgraphVarnode(
192  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
193  	   SCIP_VAR*             var                 /**< active variable that needs to be fixed */
194  	   );
195  	
196  	/*
197  	 * methods for adding edges
198  	 */
199  	
200  	/** adds an edge to a symmetry detection graph */
201  	SCIP_EXPORT
202  	SCIP_RETCODE SCIPaddSymgraphEdge(
203  	   SCIP*                 scip,               /**< SCIP data structure */
204  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
205  	   int                   first,              /**< first node index of edge */
206  	   int                   second,             /**< second node index of edge */
207  	   SCIP_Bool             hasval,             /**< whether the edge has a value */
208  	   SCIP_Real             val                 /**< value of the edge (is it has a value) */
209  	   );
210  	
211  	/*
212  	 * methods to compute colors
213  	 */
214  	
215  	/** computes colors of nodes and edges */
216  	SCIP_EXPORT
217  	SCIP_RETCODE SCIPcomputeSymgraphColors(
218  	   SCIP*                 scip,               /**< SCIP data structure */
219  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
220  	   SYM_SPEC              fixedtype           /**< variable types that must be fixed by symmetries */
221  	   );
222  	
223  	/*
224  	 * general methods
225  	 */
226  	
227  	/** returns the type of symmetries encoded in graph */
228  	SCIP_EXPORT
229  	SYM_SYMTYPE SCIPgetSymgraphSymtype(
230  	   SYM_GRAPH*            graph               /**< symmetry detection graph */
231  	   );
232  	
233  	/** returns the variables in a symmetry detection graph */
234  	SCIP_EXPORT
235  	SCIP_VAR** SCIPgetSymgraphVars(
236  	   SYM_GRAPH*            graph               /**< symmetry detection graph */
237  	   );
238  	
239  	/** returns the number of variables in a symmetry detection graph */
240  	SCIP_EXPORT
241  	int SCIPgetSymgraphNVars(
242  	   SYM_GRAPH*            graph               /**< symmetry detection graph */
243  	   );
244  	
245  	/** returns the number of constraint nodes in a symmetry detection graph */
246  	SCIP_EXPORT
247  	int SCIPgetSymgraphNConsnodes(
248  	   SYM_GRAPH*            graph               /**< symmetry detection graph */
249  	   );
250  	
251  	/** returns the number of non-variable nodes in a graph */
252  	SCIP_EXPORT
253  	int SCIPgetSymgraphNNodes(
254  	   SYM_GRAPH*            graph               /**< symmetry detection graph */
255  	   );
256  	
257  	/** returns the number of edges in a graph */
258  	SCIP_EXPORT
259  	int SCIPgetSymgraphNEdges(
260  	   SYM_GRAPH*            graph               /**< symmetry detection graph */
261  	   );
262  	
263  	/** return the first node index of an edge */
264  	SCIP_EXPORT
265  	int SCIPgetSymgraphEdgeFirst(
266  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
267  	   int                   edgeidx             /**< index of edge */
268  	   );
269  	
270  	/** return the second node index of an edge */
271  	SCIP_EXPORT
272  	int SCIPgetSymgraphEdgeSecond(
273  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
274  	   int                   edgeidx             /**< index of edge */
275  	   );
276  	
277  	/** returns the color of a variable node */
278  	SCIP_EXPORT
279  	int SCIPgetSymgraphVarnodeColor(
280  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
281  	   int                   nodeidx             /**< index of variable node */
282  	   );
283  	
284  	/** returns the type of a node */
285  	SCIP_EXPORT
286  	SYM_NODETYPE SCIPgetSymgraphNodeType(
287  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
288  	   int                   nodeidx             /**< index of node */
289  	   );
290  	
291  	/** returns the color of a non-variable node */
292  	SCIP_EXPORT
293  	int SCIPgetSymgraphNodeColor(
294  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
295  	   int                   nodeidx             /**< index of node */
296  	   );
297  	
298  	/** returns whether an edge is colored */
299  	SCIP_EXPORT
300  	SCIP_Bool SCIPisSymgraphEdgeColored(
301  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
302  	   int                   edgeidx             /**< index of edge */
303  	   );
304  	
305  	/** returns color of an edge */
306  	SCIP_EXPORT
307  	int SCIPgetSymgraphEdgeColor(
308  	   SYM_GRAPH*            graph,              /**< symmetry detection graph */
309  	   int                   edgeidx             /**< index of edge */
310  	   );
311  	
312  	/** returns the number of unique variable colors in the graph */
313  	SCIP_EXPORT
314  	int SCIPgetSymgraphNVarcolors(
315  	   SYM_GRAPH*            graph               /**< symmetry detection graph */
316  	   );
317  	
318  	/** returns whether the graph has a unique edge type */
319  	SCIP_EXPORT
320  	SCIP_Bool SCIPhasGraphUniqueEdgetype(
321  	   SYM_GRAPH*            graph               /**< symmetry detection graph */
322  	   );
323  	
324  	/** creates consnodeperm array for symmetry detection graph
325  	 *
326  	 *  @note @p colors of symmetry detection graph must have been computed
327  	 */
328  	SCIP_EXPORT
329  	SCIP_RETCODE SCIPallocateSymgraphConsnodeperm(
330  	   SCIP*                 scip,               /**< SCIP data structure */
331  	   SYM_GRAPH*            graph               /**< symmetry detection graph */
332  	   );
333  	
334  	/** creates consnodeperm array for symmetry detection graph
335  	 *
336  	 *  @note @p colors of symmetry detection graph must have been computed
337  	 */
338  	SCIP_EXPORT
339  	SCIP_RETCODE SCIPcreateSymgraphConsnodeperm(
340  	   SCIP*                 scip,               /**< SCIP data structure */
341  	   SYM_GRAPH*            graph               /**< symmetry detection graph */
342  	   );
343  	
344  	/** returns consnodeperm array for symmetry detection graph
345  	 *
346  	 *  @note @p colors of symmetry detection graph must have been computed
347  	 */
348  	SCIP_EXPORT
349  	int* SCIPgetSymgraphConsnodeperm(
350  	   SCIP*                 scip,               /**< SCIP data structure */
351  	   SYM_GRAPH*            graph               /**< symmetry detection graph */
352  	   );
353  	
354  	/** frees consnodeperm array for symmetry detection graph */
355  	SCIP_EXPORT
356  	SCIP_RETCODE SCIPfreeSymgraphConsnodeperm(
357  	   SCIP*                 scip,               /**< SCIP data structure */
358  	   SYM_GRAPH*            graph               /**< symmetry detection graph */
359  	   );
360  	
361  	/** Transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant.
362  	 *
363  	 *  For permutation symmetries, active variables as encoded in SCIP are used. For signed permutation symmetries,
364  	 *  active variables are shifted such that their domain is centered at 0 (if both their upper and lower bounds
365  	 *  are finite).
366  	 *
367  	 *  @note @p constant needs to be initialized!
368  	 */
369  	SCIP_EXPORT
370  	SCIP_RETCODE SCIPgetActiveVariables(
371  	   SCIP*                 scip,               /**< SCIP data structure */
372  	   SYM_SYMTYPE           symtype,            /**< type of symmetries for which variables are required */
373  	   SCIP_VAR***           vars,               /**< pointer to vars array to get active variables for */
374  	   SCIP_Real**           scalars,            /**< pointer to scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */
375  	   int*                  nvars,              /**< pointer to number of variables and values in vars and vals array */
376  	   SCIP_Real*            constant,           /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c */
377  	   SCIP_Bool             transformed         /**< transformed constraint? */
378  	   );
379  	
380  	/** frees symmetry information of an expression */
381  	SCIP_EXPORT
382  	SCIP_RETCODE SCIPfreeSymDataExpr(
383  	   SCIP*                 scip,               /**< SCIP data structure */
384  	   SYM_EXPRDATA**        symdata             /**< symmetry information of an expression */
385  	   );
386  	
387  	/** returns number of coefficients from exprdata */
388  	SCIP_EXPORT
389  	int SCIPgetSymExprdataNConstants(
390  	   SYM_EXPRDATA*         symdata             /**< symmetry information of an expression */
391  	   );
392  	
393  	/** returns number of coefficients form exprdata */
394  	SCIP_EXPORT
395  	SCIP_Real* SCIPgetSymExprdataConstants(
396  	   SYM_EXPRDATA*         symdata             /**< symmetry information of an expression */
397  	   );
398  	
399  	/** gets coefficient of expression from parent expression */
400  	SCIP_EXPORT
401  	SCIP_RETCODE SCIPgetCoefSymData(
402  	   SCIP*                 scip,               /**< SCIP data structure */
403  	   SCIP_EXPR*            expr,               /**< expression for which coefficient needs to be found */
404  	   SCIP_EXPR*            parentexpr,         /**< parent of expr */
405  	   SCIP_Real*            coef,               /**< buffer to store coefficient */
406  	   SCIP_Bool*            success             /**< whether a coefficient is found */
407  	   );
408  	
409  	
410  	/** @} */
411  	
412  	#ifdef __cplusplus
413  	}
414  	#endif
415  	
416  	#endif
417