1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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   reader_ccg.c
26   	 * @ingroup DEFPLUGINS_READER
27   	 * @brief  Graph file reader (actually, only a writer)
28   	 * @author Marc Pfetsch
29   	 *
30   	 * Write a weighted column/variable graph, i.e., the nodes correspond to the columns (variables) of
31   	 * the constraint matrix. Two nodes are adjacent if the corresponding columns/variables appear
32   	 * in a common row/constraint (with nonzero coefficient).  The weight is obtained by summing for
33   	 * each row that produces an edge the absolute values of coefficients in the row; hence, we avoid
34   	 * parallel edges.
35   	 *
36   	 * This graph gives an indication of the connectivity structure of the constraint matrix.
37   	 *
38   	 * The graph is output in DIMACS graph format.
39   	 */
40   	
41   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
42   	
43   	#include "blockmemshell/memory.h"
44   	#include "scip/cons_knapsack.h"
45   	#include "scip/cons_linear.h"
46   	#include "scip/cons_logicor.h"
47   	#include "scip/cons_setppc.h"
48   	#include "scip/cons_varbound.h"
49   	#include "scip/pub_cons.h"
50   	#include "scip/pub_message.h"
51   	#include "scip/pub_reader.h"
52   	#include "scip/pub_var.h"
53   	#include "scip/reader_ccg.h"
54   	#include "scip/scip_cons.h"
55   	#include "scip/scip_mem.h"
56   	#include "scip/scip_message.h"
57   	#include "scip/scip_reader.h"
58   	#include "scip/scip_var.h"
59   	#include <string.h>
60   	
61   	#define READER_NAME             "ccgreader"
62   	#define READER_DESC             "file writer for column connectivity graph file format"
63   	#define READER_EXTENSION        "ccg"
64   	
65   	/*
66   	 * Data structures
67   	 */
68   	
69   	
70   	/* graph data structure */
71   	struct sparseGraph
72   	{
73   	   unsigned int          n;                  /**< number of nodes */
74   	   unsigned int          m;                  /**< number of edges */
75   	   int**                 A;                  /**< adjacency list (= adjacent nodes) for each node (-1 for end of list) */
76   	   SCIP_Real**           W;                  /**< weights for each edge */
77   	   unsigned int*         deg;                /**< degree each node */
78   	   unsigned int*         size;               /**< size of A/w for each node */
79   	};
80   	
81   	typedef struct sparseGraph SparseGraph;
82   	
83   	
84   	/*
85   	 * Local methods (for writing)
86   	 */
87   	
88   	/** initialize graph */
89   	static
90   	SCIP_RETCODE initGraph(
91   	   SCIP*                 scip,               /**< SCIP data structure */
92   	   SparseGraph*          G,                  /**< graph to free */
93   	   unsigned int          nNodes,             /**< number of nodes */
94   	   unsigned int          initSize            /**< initial size of lists */
95   	   )
96   	{
97   	   unsigned int i;
98   	
99   	   G->n = nNodes;
100  	   G->m = 0;
101  	
102  	   SCIP_CALL( SCIPallocBufferArray(scip, &G->deg, (int) nNodes) );
103  	   SCIP_CALL( SCIPallocBufferArray(scip, &G->size, (int) nNodes) );
104  	   SCIP_CALL( SCIPallocBufferArray(scip, &G->A, (int) nNodes) );
105  	   SCIP_CALL( SCIPallocBufferArray(scip, &G->W, (int) nNodes) );
106  	
107  	   for( i = 0; i < nNodes; ++i )
108  	   {
109  	      G->deg[i] = 0;
110  	      G->size[i] = initSize;
111  	
112  	      SCIP_CALL( SCIPallocBufferArray(scip, &(G->A[i]), (int) initSize) );   /*lint !e866 */
113  	      SCIP_CALL( SCIPallocBufferArray(scip, &(G->W[i]), (int) initSize) );   /*lint !e866 */
114  	
115  	      G->A[i][0] = -1;
116  	   }
117  	
118  	   return SCIP_OKAY;
119  	}
120  	
121  	
122  	/** frees graph */
123  	static
124  	void freeGraph(
125  	   SCIP*                 scip,               /**< SCIP data structure */
126  	   SparseGraph*          G                   /**< graph to free */
127  	   )
128  	{
129  	   unsigned int i;
130  	
131  	   for( i = 0; i < G->n; ++i )
132  	   {
133  	      SCIPfreeBufferArray(scip, &G->A[i]);
134  	      SCIPfreeBufferArray(scip, &G->W[i]);
135  	   }
136  	
137  	   SCIPfreeBufferArray(scip, &G->W);
138  	   SCIPfreeBufferArray(scip, &G->A);
139  	   SCIPfreeBufferArray(scip, &G->size);
140  	   SCIPfreeBufferArray(scip, &G->deg);
141  	}
142  	
143  	
144  	/** check whether there is enough capacity for one additional edge in the given adjacency list */
145  	static
146  	SCIP_RETCODE ensureEdgeCapacity(
147  	   SCIP*                 scip,               /**< SCIP data structure */
148  	   SparseGraph*          G,                  /**< graph */
149  	   unsigned int          node                /**< list for node */
150  	   )
151  	{
152  	   if( G->deg[node] + 2 > G->size[node] )
153  	   {
154  	      unsigned int newSize;
155  	      newSize = G->size[node] * 2;
156  	      SCIP_CALL( SCIPreallocBufferArray(scip, &(G->A[node]), (int) newSize) );  /*lint !e866 */
157  	      SCIP_CALL( SCIPreallocBufferArray(scip, &(G->W[node]), (int) newSize) );  /*lint !e866 */
158  	      G->size[node] = newSize;
159  	   }
160  	
161  	   return SCIP_OKAY;
162  	}
163  	
164  	
165  	/** transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant */
166  	static
167  	SCIP_RETCODE getActiveVariables(
168  	   SCIP*                 scip,               /**< SCIP data structure */
169  	   SCIP_VAR**            vars,               /**< vars array to get active variables for */
170  	   SCIP_Real*            scalars,            /**< scalars a_1, ..., a_n inrc/scip/reader_graph.c linear sum a_1*x_1 + ... + a_n*x_n + c */
171  	   int*                  nvars,              /**< pointer to number of variables and values in vars and vals array */
172  	   SCIP_Real*            constant,           /**< pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c  */
173  	   SCIP_Bool             transformed         /**< transformed constraint? */
174  	   )
175  	{
176  	   int requiredsize;
177  	   int v;
178  	
179  	   assert( scip != NULL );
180  	   assert( vars != NULL );
181  	   assert( scalars != NULL );
182  	   assert( nvars != NULL );
183  	   assert( constant != NULL );
184  	
185  	   if( transformed )
186  	   {
187  	      SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, scalars, nvars, *nvars, constant, &requiredsize, TRUE) );
188  	
189  	      if( requiredsize > *nvars )
190  	      {
191  	         SCIP_CALL( SCIPreallocBufferArray(scip, &vars, requiredsize) );
192  	         SCIP_CALL( SCIPreallocBufferArray(scip, &scalars, requiredsize) );
193  	
194  	         SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, scalars, nvars, requiredsize, constant, &requiredsize, TRUE) );
195  	         assert( requiredsize <= *nvars );
196  	      }
197  	   }
198  	   else
199  	   {
200  	      for( v = 0; v < *nvars; ++v )
201  	         SCIP_CALL( SCIPvarGetOrigvarSum(&vars[v], &scalars[v], constant) );
202  	   }
203  	   return SCIP_OKAY;
204  	}
205  	
206  	
207  	/* Generate edges from given row
208  	 *
209  	 * We avoid parallel edges. Each row generates a clique in the graph.
210  	 */
211  	static
212  	SCIP_RETCODE createEdgesFromRow(
213  	   SCIP*                 scip,               /**< SCIP data structure */
214  	   SCIP_VAR**            vars,               /**< array of constraint variables */
215  	   SCIP_Real*            vals,               /**< array of constraint values */
216  	   int                   nvars,              /**< number of constraint variables */
217  	   SparseGraph*          G                   /**< graph */
218  	   )
219  	{
220  	   int i, j;
221  	   SCIP_Real w;
222  	
223  	   assert( scip != NULL );
224  	   assert( nvars > 0 );
225  	
226  	   /* compute weight */
227  	   w = 0;
228  	   for( i = 0; i < nvars; ++i )
229  	      w += ABS(vals[i]);
230  	
231  	   /* generate edges */
232  	   for( i = 0; i < nvars; ++i )
233  	   {
234  	      int s;
235  	      s = SCIPvarGetProbindex(vars[i]);
236  	      assert( s >= 0 );
237  	
238  	      for( j = i+1; j < nvars; ++j )
239  	      {
240  	         unsigned int k;
241  	         int t;
242  	         int a;
243  	         t = SCIPvarGetProbindex(vars[j]);
244  	         assert( t >= 0 );
245  	
246  	         /* search whether edge is already present */
247  	         k = 0;
248  	         a = G->A[s][k];
249  	         while( a >= 0 )
250  	         {
251  	            /* if we found edge, add weight */
252  	            if( a == t )
253  	            {
254  	               G->W[s][k] += w;
255  	               break;
256  	            }
257  	            a = G->A[s][++k];
258  	            assert( k <= G->size[s] );
259  	         }
260  	
261  	         /* add new edge */
262  	         if( a < 0 )
263  	         {
264  	            /* forward edge */
265  	            SCIP_CALL( ensureEdgeCapacity(scip, G, (unsigned int) s) );
266  	            k = G->deg[s];
267  	            assert( G->A[s][k] == -1 );
268  	
269  	            G->A[s][k] = t;
270  	            G->W[s][k] = w;
271  	
272  	            G->A[s][k+1] = -1; /*lint !e679*/
273  	            ++G->deg[s];
274  	
275  	            /* backward edge */
276  	            SCIP_CALL( ensureEdgeCapacity(scip, G, (unsigned int) t) );
277  	            k = G->deg[t];
278  	            assert( G->A[t][k] == -1 );
279  	
280  	            G->A[t][k] = s;
281  	            G->W[t][k] = w;
282  	
283  	            G->A[t][k+1] = -1; /*lint !e679*/
284  	            ++G->deg[t];
285  	
286  	            /* increase number of edges */
287  	            ++G->m;
288  	         }
289  	      }
290  	   }
291  	
292  	   return SCIP_OKAY;
293  	}
294  	
295  	
296  	/** handle given linear constraint information */
297  	static
298  	SCIP_RETCODE handleLinearCons(
299  	   SCIP*                 scip,               /**< SCIP data structure */
300  	   SCIP_VAR**            vars,               /**< array of variables */
301  	   SCIP_Real*            vals,               /**< array of coefficients values (or NULL if all coefficient values are 1) */
302  	   int                   nvars,              /**< number of variables */
303  	   SCIP_Bool             transformed,        /**< transformed constraint? */
304  	   SparseGraph*          G                   /**< graph */
305  	   )
306  	{
307  	   int v;
308  	   SCIP_VAR** activevars;
309  	   SCIP_Real* activevals;
310  	   int nactivevars;
311  	   SCIP_Real activeconstant = 0.0;
312  	
313  	   assert( scip != NULL );
314  	   assert( nvars > 0 );
315  	
316  	   /* duplicate variable and value array */
317  	   nactivevars = nvars;
318  	   SCIP_CALL( SCIPduplicateBufferArray(scip, &activevars, vars, nactivevars ) );
319  	   if( vals != NULL )
320  	      SCIP_CALL( SCIPduplicateBufferArray(scip, &activevals, vals, nactivevars ) );
321  	   else
322  	   {
323  	      SCIP_CALL( SCIPallocBufferArray(scip, &activevals, nactivevars) );
324  	
325  	      for( v = 0; v < nactivevars; ++v )
326  	         activevals[v] = 1.0;
327  	   }
328  	
329  	   /* retransform given variables to active variables */
330  	   SCIP_CALL( getActiveVariables(scip, activevars, activevals, &nactivevars, &activeconstant, transformed) );
331  	
332  	   /* print constraint */
333  	   SCIP_CALL( createEdgesFromRow(scip, activevars, activevals, nactivevars, G) );
334  	
335  	   /* free buffer arrays */
336  	   SCIPfreeBufferArray(scip, &activevars);
337  	   SCIPfreeBufferArray(scip, &activevals);
338  	
339  	   return SCIP_OKAY;
340  	}
341  	
342  	
343  	/*
344  	 * Callback methods of reader
345  	 */
346  	
347  	/** copy method for reader plugins (called when SCIP copies plugins) */
348  	static
349  	SCIP_DECL_READERCOPY(readerCopyCcg)
350  	{  /*lint --e{715}*/
351  	   assert(scip != NULL);
352  	   assert(reader != NULL);
353  	   assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
354  	
355  	   /* call inclusion method of reader */
356  	   SCIP_CALL( SCIPincludeReaderCcg(scip) );
357  	
358  	   return SCIP_OKAY;
359  	}
360  	
361  	
362  	/** problem writing method of reader */
363  	static
364  	SCIP_DECL_READERWRITE(readerWriteCcg)
365  	{  /*lint --e{715}*/
366  	
367  	   SCIP_CALL( SCIPwriteCcg(scip, file, name, transformed, vars, nvars, conss, nconss, result) );
368  	
369  	   return SCIP_OKAY;
370  	}
371  	
372  	/*
373  	 * reader specific interface methods
374  	 */
375  	
376  	/** includes the ccg file reader in SCIP */
377  	SCIP_RETCODE SCIPincludeReaderCcg(
378  	   SCIP*                 scip                /**< SCIP data structure */
379  	   )
380  	{
381  	   SCIP_READER* reader;
382  	
383  	   /* include reader */
384  	   SCIP_CALL( SCIPincludeReaderBasic(scip, &reader, READER_NAME, READER_DESC, READER_EXTENSION, NULL) );
385  	
386  	   assert(reader != NULL);
387  	
388  	   /* set non-fundamental callbacks via setter functions */
389  	   SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopyCcg) );
390  	   SCIP_CALL( SCIPsetReaderWrite(scip, reader, readerWriteCcg) );
391  	
392  	   return SCIP_OKAY;
393  	}
394  	
395  	
396  	/** writes problem to file */
397  	SCIP_RETCODE SCIPwriteCcg(
398  	   SCIP*                 scip,               /**< SCIP data structure */
399  	   FILE*                 file,               /**< output file, or NULL if standard output should be used */
400  	   const char*           name,               /**< problem name */
401  	   SCIP_Bool             transformed,        /**< TRUE iff problem is the transformed problem */
402  	   SCIP_VAR**            vars,               /**< array with active variables ordered binary, integer, implicit, continuous */
403  	   int                   nvars,              /**< number of active variables in the problem */
404  	   SCIP_CONS**           conss,              /**< array with constraints of the problem */
405  	   int                   nconss,             /**< number of constraints in the problem */
406  	   SCIP_RESULT*          result              /**< pointer to store the result of the file writing call */
407  	   )
408  	{  /*lint --e{715}*/
409  	   int c;
410  	   int v;
411  	   int i;
412  	
413  	   SCIP_CONSHDLR* conshdlr;
414  	   const char* conshdlrname;
415  	   SCIP_CONS* cons;
416  	
417  	   SCIP_VAR** consvars;
418  	   SCIP_Real* consvals;
419  	   int nconsvars;
420  	
421  	   SparseGraph G;
422  	
423  	   assert( scip != NULL );
424  	   assert( vars != NULL );
425  	   assert( nvars >= 0 );
426  	
427  	   /* initialize graph */
428  	   SCIP_CALL( initGraph(scip, &G, (unsigned int) nvars, 10) );
429  	
430  	   /* check all constraints */
431  	   for( c = 0; c < nconss; ++c)
432  	   {
433  	      cons = conss[c];
434  	      assert( cons != NULL);
435  	
436  	      /* in case the transformed is written only constraint are posted which are enabled in the current node */
437  	      assert(!transformed || SCIPconsIsEnabled(cons));
438  	
439  	      conshdlr = SCIPconsGetHdlr(cons);
440  	      assert( conshdlr != NULL );
441  	
442  	      conshdlrname = SCIPconshdlrGetName(conshdlr);
443  	      assert( transformed == SCIPconsIsTransformed(cons) );
444  	
445  	      if( strcmp(conshdlrname, "linear") == 0 )
446  	      {  
447  	         consvars = SCIPgetVarsLinear(scip, cons);
448  	         nconsvars = SCIPgetNVarsLinear(scip, cons);
449  	         assert( consvars != NULL || nconsvars == 0 );
450  	
451  	         if( nconsvars > 0 ) 
452  	         { 
453  	            SCIP_CALL( handleLinearCons(scip, SCIPgetVarsLinear(scip, cons), SCIPgetValsLinear(scip, cons),
454  	                  SCIPgetNVarsLinear(scip, cons), transformed, &G) );
455  	         }
456  	      }
457  	      else if( strcmp(conshdlrname, "setppc") == 0 )
458  	      {
459  	         consvars = SCIPgetVarsSetppc(scip, cons);
460  	         nconsvars = SCIPgetNVarsSetppc(scip, cons);
461  	         assert( consvars != NULL || nconsvars == 0 );
462  	
463  	         if( nconsvars > 0 ) 
464  	         {
465  	            SCIP_CALL( handleLinearCons(scip, consvars, NULL, nconsvars, transformed, &G) );
466  	         }
467  	      }
468  	      else if( strcmp(conshdlrname, "logicor") == 0 )
469  	      {  
470  	         consvars = SCIPgetVarsLogicor(scip, cons);
471  	         nconsvars = SCIPgetNVarsLogicor(scip, cons);
472  	         assert( consvars != NULL || nconsvars == 0 );
473  	
474  	         if( nconsvars > 0 ) 
475  	         { 
476  	            SCIP_CALL( handleLinearCons(scip, SCIPgetVarsLogicor(scip, cons), NULL, SCIPgetNVarsLogicor(scip, cons), transformed, &G) );
477  	         }
478  	      }
479  	      else if( strcmp(conshdlrname, "knapsack") == 0 )
480  	      {
481  	         SCIP_Longint* w;
482  	
483  	         consvars = SCIPgetVarsKnapsack(scip, cons);
484  	         nconsvars = SCIPgetNVarsKnapsack(scip, cons);
485  	         assert( consvars != NULL || nconsvars == 0 );
486  	
487  	         /* copy Longint array to SCIP_Real array */
488  	         w = SCIPgetWeightsKnapsack(scip, cons);
489  	         SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nconsvars) );
490  	         for( v = 0; v < nconsvars; ++v )
491  	            consvals[v] = (SCIP_Real)w[v];
492  	
493  	         if( nconsvars > 0 ) 
494  	         { 
495  	            SCIP_CALL( handleLinearCons(scip, consvars, consvals, nconsvars, transformed, &G) );
496  	         }
497  	         SCIPfreeBufferArray(scip, &consvals);
498  	      }
499  	      else if( strcmp(conshdlrname, "varbound") == 0 )
500  	      {
501  	         SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 2) );
502  	         SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 2) );
503  	
504  	         consvars[0] = SCIPgetVarVarbound(scip, cons);
505  	         consvars[1] = SCIPgetVbdvarVarbound(scip, cons);
506  	
507  	         consvals[0] = 1.0;
508  	         consvals[1] = SCIPgetVbdcoefVarbound(scip, cons);
509  	
510  	         SCIP_CALL( handleLinearCons(scip, consvars, consvals, 2, transformed, &G) );
511  	
512  	         SCIPfreeBufferArray(scip, &consvars);
513  	         SCIPfreeBufferArray(scip, &consvals);
514  	      }
515  	      else
516  	      {
517  	         SCIPwarningMessage(scip, "constraint handler <%s> cannot print requested format\n", conshdlrname );
518  	         SCIPinfoMessage(scip, file, "\\ ");
519  	         SCIP_CALL( SCIPprintCons(scip, cons, file) );
520  	         SCIPinfoMessage(scip, file, ";\n");
521  	      }
522  	   }
523  	
524  	   /* output graph */
525  	   SCIPinfoMessage(scip, file, "c graph generated from %s\n", name);
526  	   SCIPinfoMessage(scip, file, "p edge %d %u\n", nvars, G.m);
527  	
528  	   for( i = 0; i < nvars; ++i )
529  	   {
530  	      unsigned int k;
531  	      int a;
532  	
533  	      k = 0;
534  	      a = G.A[i][k];
535  	      while( a >= 0 )
536  	      {
537  	         /* only output edges from lower to higher number */
538  	         if( i < a )
539  	         {
540  	            /* note: node numbers start with 1 in the DIMACS format */
541  	            SCIPinfoMessage(scip, file, "e %d %d %f\n", i+1, a+1, G.W[i][k]);
542  	         }
543  	
544  	         a = G.A[i][++k];
545  	         assert( k <= G.size[i] );
546  	      }
547  	      assert( k == G.deg[i] );
548  	   }
549  	
550  	   freeGraph(scip, &G);
551  	
552  	   *result = SCIP_SUCCESS;
553  	
554  	   return SCIP_OKAY;
555  	}
556