class_indexclassifier.cpp
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2018 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include "class_indexclassifier.h"
37 
38 #include <assert.h>
39 #include <sstream>
40 #include <algorithm>
41 
42 namespace gcg {
43 
46 struct sort_pred {
47  bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {
48  return left.second < right.second;
49  }
50 };
51 
54  SCIP* _scip,
55  const char* givenName,
56  int givenNClasses,
57  int givenNIndices
58 ) :
59  scip(_scip), name(std::string(givenName)), nClasses(givenNClasses), nIndices(givenNIndices), indicesToClasses(givenNIndices, -1),
60  classNames(givenNClasses, ""),
61  classDescriptions(givenNClasses, ""),
62  classDecompInfo( nClasses, 0 )
63 {
64 }
65 
68 {
69  assert( toCopy != NULL );
70  scip = toCopy->scip;
71  name = toCopy->name;
72  nClasses = toCopy->nClasses;
73  nIndices = toCopy->nIndices;
74  indicesToClasses = toCopy->indicesToClasses;
75  classNames.assign(nClasses, "");
76  classDescriptions.assign(nClasses, "");
77  classDecompInfo.assign(nClasses, 0);
78  for ( int i = 0; i < nClasses; ++i )
79  {
80  classNames[i] = toCopy->classNames[i];
81  classDescriptions[i] = toCopy->classDescriptions[i];
82  classDecompInfo[i] = toCopy->classDecompInfo[i];
83  }
84 }
85 
88 {
89 }
90 
92 int IndexClassifier::addClass( const char* givenName, const char* givenDesc )
93 {
94  assert((int) classNames.size() == nClasses);
95  assert((int) classDescriptions.size() == nClasses);
96  assert((int) classDecompInfo.size() == nClasses);
97 
98  std::string givenClassName = std::string(givenName);
99 
100  classNames.push_back( givenClassName );
101  classDescriptions.push_back( givenDesc );
102  classDecompInfo.push_back( 0 );
103 
104  ++nClasses;
105 
106  return nClasses - 1;
107 }
108 
110 void IndexClassifier::assignIndexToClass( int givenIndex, int givenClassindex )
111 {
112  assert(0 <= givenIndex && givenIndex < nIndices);
113  assert(-1 <= givenClassindex && givenClassindex < nClasses);
114 
115  indicesToClasses[givenIndex] = givenClassindex;
116 }
117 
121 {
122  std::vector<int> classMapping ( getNClasses(), -1 );
123 
125  assert( getNIndices() == otherClassifier->getNIndices() );
126  if ( getNClasses() != otherClassifier->getNClasses() )
127  return false;
128 
130  for ( int i = 0; i < getNIndices(); ++i )
131  {
132  if ( isIndexClassified( i ) )
133  {
134  int compClass = getClassOfIndex( i );
135 
136  if ( classMapping[ compClass ] == -1 )
137  classMapping[ compClass ] = otherClassifier->getClassOfIndex( i );
138  else if ( classMapping[ compClass ] != otherClassifier->getClassOfIndex( i ) )
139  return false;
140  }
141  else if ( otherClassifier->isIndexClassified( i ) )
142  {
143  return false;
144  }
145  }
146 
148  for ( size_t c = 0; c < classMapping.size(); ++c )
149  {
150  if ( classMapping[c] != -1 )
151  {
152  for ( size_t j = c + 1; j < classMapping.size(); ++j )
153  {
154  if ( classMapping[c] == classMapping[j] )
155  return false;
156  }
157  }
158  }
159 
160  return true;
161 }
162 
164 std::vector<std::vector<int>> IndexClassifier::getAllSubsets( std::vector<int>& givenClassindices )
165 {
166  std::vector<std::vector<int>> subsets;
167  std::vector<int> empty;
168  subsets.push_back( empty );
169 
170  for ( size_t i = 0; i < givenClassindices.size(); ++i )
171  {
172  std::vector< std::vector<int> > subsetTemp = subsets;
173 
174  for (size_t j = 0; j < subsetTemp.size(); ++j)
175  subsetTemp[j].push_back( givenClassindices[i] );
176 
177  for (size_t j = 0; j < subsetTemp.size(); ++j)
178  subsets.push_back( subsetTemp[j] );
179  }
180  return subsets;
181 }
182 
184 int IndexClassifier::getClassDecompInfo( int givenClassindex )
185 {
186  assert(0 <= givenClassindex && givenClassindex < nClasses);
187 
188  return classDecompInfo[givenClassindex];
189 }
190 
192 const char* IndexClassifier::getClassDescription( int givenClassindex )
193 {
194  assert(0 <= givenClassindex && givenClassindex < nClasses);
195 
196  return classDescriptions[givenClassindex].c_str();
197 }
198 
200 const char* IndexClassifier::getClassName( int givenClassindex )
201 {
202  assert(0 <= givenClassindex && givenClassindex < nClasses);
203 
204  return classNames[givenClassindex].c_str();
205 }
206 
208 const char* IndexClassifier::getClassNameOfIndex( int givenIndex )
209 {
210  assert(0 <= givenIndex && givenIndex < nIndices);
211  assert(0 <= indicesToClasses[givenIndex] && indicesToClasses[givenIndex] < nClasses);
212 
213  return classNames[indicesToClasses[givenIndex]].c_str();
214 }
215 
216 
218 int IndexClassifier::getClassOfIndex( int givenIndex )
219 {
220  assert(0 <= givenIndex && givenIndex < nIndices);
221 
222  return indicesToClasses[givenIndex];
223 }
224 
227 {
228  return indicesToClasses;
229 }
230 
231 
234 {
235  return name.c_str();
236 }
237 
238 
241 {
242  return nClasses;
243 }
244 
247 {
248  return nIndices;
249 }
250 
253 {
254  std::vector<int> nIndicesOfClasses( nClasses, 0 );
255 
256  if ( nClasses == 0 )
257  return nIndicesOfClasses;
258 
259  for ( int i = 0; i < nIndices; ++i)
260  {
261  if ( indicesToClasses[i] != -1 )
262  ++nIndicesOfClasses[indicesToClasses[i]];
263  }
264  return nIndicesOfClasses;
265 }
266 
269 {
270  assert(0 <= givenIndex && givenIndex < nIndices);
271 
272  return indicesToClasses[givenIndex] != -1;
273 }
274 
276 std::vector<int> IndexClassifier::reduceClasses( int givenMaxNumber )
277 {
278  assert( givenMaxNumber > 0 );
279 
280  if ( getNClasses() <= givenMaxNumber || nClasses >= 2*givenMaxNumber )
281  return std::vector<int>(0);
282 
283  std::vector<int> classindexmapping(nClasses, 0);
284  int enlargedclass = nClasses - givenMaxNumber;
285 
287  std::vector<std::pair<int,int>> nmembers( nClasses, std::pair<int,int>(0,0) );
288  for( int i = 0; i < nClasses; ++i )
289  {
290  nmembers[i].first = i;
291  }
292 
293  std::vector<int>::const_iterator iter = indicesToClasses.begin();
294  std::vector<int>::const_iterator iterend = indicesToClasses.end();
295  for( ; iter < iterend; ++iter )
296  {
297  if ( *iter != -1 )
298  nmembers[*iter].second++;
299  }
300 
302  std::sort( nmembers.begin(), nmembers.end(), sort_pred() );
303  for( int i = 1; i < givenMaxNumber; ++i )
304  {
305  classindexmapping[nmembers[enlargedclass + i].first] = i;
306  }
307 
308  return classindexmapping;
309 }
310 
314 {
315  if ( nClasses == 0 )
316  return 0;
317 
319  std::vector<int> toDelete(0);
320  std::vector<int> nIndicesPerClasses(nClasses, 0);
321 
322  for ( int i = 0; i < nIndices; ++i )
323  {
324  if ( indicesToClasses[i] != -1 )
325  ++nIndicesPerClasses[indicesToClasses[i]];
326  }
327 
328  for ( int i = 0; i < nClasses; ++i )
329  {
330  if ( nIndicesPerClasses[i] == 0 )
331  {
332  toDelete.push_back(i);
333  }
334  }
335 
337  for ( size_t i = 0; i < toDelete.size(); ++i )
338  {
339  int classindex = toDelete[toDelete.size() - 1 - i];
340 
341  for ( int j = 0; j < nIndices; ++j )
342  {
343  assert( indicesToClasses[j] != classindex );
344  if ( indicesToClasses[j] > classindex )
345  --indicesToClasses[j];
346  }
347  classNames.erase(classNames.begin() + classindex);
348  classDescriptions.erase(classDescriptions.begin() + classindex);
349  classDecompInfo.erase(classDecompInfo.begin() + classindex);
350  --nClasses;
351  }
352 
353  return toDelete.size();
354 }
355 
357 void IndexClassifier::setClassDecompInfo( int givenClassindex, int givenDecompInfo )
358 {
359  assert(0 <= givenClassindex && givenClassindex < nClasses);
360 
361  classDecompInfo[givenClassindex] = givenDecompInfo;
362 }
363 
365 void IndexClassifier::setClassDescription( int givenClassindex, const char* givenDesc )
366 {
367  assert(0 <= givenClassindex && givenClassindex < nClasses);
368 
369  classDescriptions[givenClassindex] = std::string(givenDesc);
370 }
371 
373 void IndexClassifier::setClassName( int givenClassindex, const char* givenName )
374 {
375  assert(0 <= givenClassindex && givenClassindex < nClasses);
376 
377  classNames[givenClassindex] = std::string(givenName);
378 }
379 
380 } /* namespace gcg */
381 
void setClassName(int classindex, const char *name)
void setClassDecompInfo(int classindex, int decompInfo)
const char * getClassName(int classindex)
std::vector< int > getIndicesToClasses()
STL namespace.
const char * getClassNameOfIndex(int index)
int addClass(const char *name, const char *desc)
bool classifierIsDuplicateOfClassifier(IndexClassifier *otherClassifier)
generalization of ConsClassifier and VarClassifier
int getClassDecompInfo(int classindex)
bool operator()(const std::pair< int, int > &left, const std::pair< int, int > &right)
void assignIndexToClass(int index, int classindex)
std::vector< int > getNIndicesOfClasses()
const char * getClassDescription(int classindex)
void setClassDescription(int classindex, const char *desc)
std::vector< std::vector< int > > getAllSubsets(std::vector< int > &classindices)
std::vector< int > reduceClasses(int maxNumberOfClasses)
IndexClassifier(SCIP *scip, const char *name, int nClasses, int nIndices)