/home/coin/SVN-release/OS-2.4.0/Couenne/src/branch/Nauty.cpp

Go to the documentation of this file.
00001 /* $Id: Nauty.cpp 508 2011-02-15 21:52:44Z pbelotti $ 
00002  *
00003  * Name:    Nauty.cpp
00004  * Authors: Jim Ostrowski
00005  * Purpose: Branching with symmetry -- implementation of the Nauty object
00006  * Date:    October 13, 2010
00007  *
00008  * This file is licensed under the Eclipse Public License (EPL)
00009  */
00010 
00011 #include <cassert>
00012 #include <cmath>
00013 #include "Nauty.h"
00014 #include <iostream>
00015 #include <algorithm>
00016 #include <map>
00017 #include <set>
00018 #include "CoinTime.hpp"
00019 //#include "OrbitalOptions.h"
00020 //extern OrbitalOptions *options;
00021 
00022 int Nauty::nautyCalls_ = 0;
00023 double Nauty::nautyTime_ = 0.0;
00024 
00025 Nauty::Nauty(int vertices)
00026 {
00027 
00028   n_ = vertices;
00029   m_ = (n_ + WORDSIZE - 1)/WORDSIZE;
00030 
00031   //printf ("size of long = %d (%d)\nwordsize = %d\nn,m = %d,%d\n", 
00032   //          SIZEOF_LONG, sizeof (long), WORDSIZE, n_, m_);
00033 
00034   nauty_check (WORDSIZE, m_, n_, NAUTYVERSIONID);
00035 
00037 
00038 #define MULTIPLIER 2
00039 
00040   G_ = (graph *) malloc(MULTIPLIER * m_ * n_ * sizeof(int));
00041   lab_ = (int *) malloc(MULTIPLIER * n_ * sizeof(int));  
00042   ptn_ = (int *) malloc(MULTIPLIER * n_ * sizeof(int));
00043   active_ = NULL;
00044   orbits_ = (int *) malloc(MULTIPLIER * n_ * sizeof(int));
00045   options_ = (optionblk *) malloc(MULTIPLIER * sizeof(optionblk));
00046   stats_ = (statsblk *) malloc(MULTIPLIER * sizeof(statsblk));
00047   worksize_ = 100*m_;
00048   workspace_ = (setword *) malloc(MULTIPLIER * worksize_*sizeof(setword));
00049   canonG_ = NULL;
00050   if (G_ == 0 || lab_ == 0 || ptn_ == 0 || 
00051       orbits_ == 0 || options_ == 0 || stats_ == 0 ||
00052       workspace_ == 0) assert(0);
00053 
00054   // Zero allocated memory
00055   memset(G_, 0, m_*n_*sizeof(int));
00056   memset(lab_, 0, n_*sizeof(int));
00057   memset(ptn_, 0, n_*sizeof(int));
00058   memset(orbits_, 0, n_*sizeof(int));
00059   memset(workspace_, 0, worksize_*sizeof(setword));
00060 
00061   // Set the options you want
00062   options_->getcanon = FALSE;
00063   options_->digraph = FALSE;
00064   options_->writeautoms = FALSE;
00065   options_->writemarkers = FALSE;
00066   options_->defaultptn = TRUE;
00067   options_->cartesian = FALSE;
00068   options_->linelength = 78;
00069   options_->outfile = NULL;
00070   options_->userrefproc = NULL;
00071   options_->userautomproc = NULL;
00072   options_->userlevelproc = NULL;
00073   options_->usernodeproc = NULL;
00074   //  options_->usertcellproc = NULL;
00075   options_->invarproc = NULL;
00076   options_->tc_level = 100;
00077   options_->mininvarlevel = 0;
00078   options_->maxinvarlevel = 1;
00079   options_->invararg = 0;
00080   options_->dispatch = &dispatch_graph;
00081    // Make an empty graph
00082   for (int j = 0; j < n_; j++) {
00083     set *gv = GRAPHROW(G_, j, m_);
00084     EMPTYSET(gv, m_);
00085   }
00086 
00087   vstat_ = new int[n_];
00088    clearPartitions();
00089    afp_ = NULL;
00090  }
00091 
00092 Nauty::~Nauty()
00093 {
00094   if (G_) free(G_);
00095   if (lab_) free(lab_);
00096   if (ptn_) free(ptn_);
00097   if (active_) free(active_);
00098   if (orbits_) free(orbits_);
00099   if (options_) free(options_);
00100   if (stats_) free(stats_);
00101   if (workspace_) free(workspace_);
00102   if (canonG_) free(canonG_);
00103 
00104   if (vstat_) delete [] vstat_;
00105 }
00106 
00107 void
00108 Nauty::addElement(int ix, int jx)
00109 {
00110   // Right now die if bad index.  Can throw exception later
00111   //printf("addelement %d %d \n", ix, jx);
00112   assert(ix < n_ and jx < n_);
00113   if(ix != jx){  //No Loops
00114     set *gv = GRAPHROW(G_, ix, m_);
00115     ADDELEMENT(gv, jx);
00116     set *gv2 = GRAPHROW(G_, jx, m_);
00117     ADDELEMENT(gv2, ix);
00118     autoComputed_ = false;
00119   }
00120 }
00121 
00122 void 
00123 Nauty::clearPartitions()
00124 {
00125   for (int j = 0; j < n_; j++) {
00126     vstat_[j] = 1;
00127     //printf("vstat %d = %d", j, vstat_[j]);
00128   }
00129 
00130   autoComputed_ = false;
00131 }
00132 
00133 void
00134 Nauty::computeAuto()
00135 {
00136 
00137   //  if (autoComputed_) return;
00138 
00139   double startCPU = CoinCpuTime ();
00140 
00141   options_->defaultptn = FALSE;
00142 
00143   // Here we only implement the partitions
00144   // [ fix1 | fix0 (union) free | constraints ]
00145   int ix = 0;
00146   
00147   for( int color = 1; color <= n_; color++){
00148     for (int j = 0; j < n_; j++) {
00149       if (vstat_[j] == color) {
00150         lab_[ix] = j;
00151         ptn_[ix] = color;
00152         ix++;
00153       }
00154     }
00155      if (ix > 0) ptn_[ix-1] = 0;
00156   }
00157   
00158   /*
00159   for (int j = 0; j < n_; j++)
00160     printf("ptn %d = %d      lab = %d \n", j, ptn_[j], lab_[j]);
00161   */
00162   
00163 
00164   // Should be number of columns
00165   assert(ix == n_);
00166   // Now the constraints if needed
00167 
00168 
00169     // Compute Partition
00170     
00171   nauty(G_, lab_, ptn_, active_, orbits_, options_, 
00172         stats_, workspace_, worksize_, m_, n_, canonG_);
00173   autoComputed_ = true;
00174 
00175   double endCPU = CoinCpuTime ();
00176 
00177   nautyCalls_++;
00178   nautyTime_ += endCPU - startCPU;
00179   // Need to make sure all generators are written
00180   if (afp_) fflush(afp_);
00181    
00182 }
00183 
00184 void
00185 Nauty::deleteElement(int ix, int jx)
00186 {
00187   // Right now die if bad index.  Can throw exception later
00188   assert(ix < n_ and jx < n_);
00189   set *gv = GRAPHROW(G_, ix, m_);
00190   if (ISELEMENT(gv, jx)) {
00191     DELELEMENT(gv, jx);
00192   } 
00193   autoComputed_ = false;
00194 }
00195 
00196 double
00197 Nauty::getGroupSize() const
00198 {
00199   if (!autoComputed_) return -1.0;
00200   return( stats_->grpsize1 * pow(10.0, (double) stats_->grpsize2) );
00201 }
00202 
00203 int
00204 Nauty::getNumGenerators() const
00205 {
00206   if (!autoComputed_) return -1;
00207   return(stats_->numgenerators);
00208 }
00209 
00210 int
00211 Nauty::getNumOrbits() const
00212 {
00213   if (!autoComputed_) return -1;
00214   return(stats_->numorbits);
00215 }
00216 
00217 std::vector<std::vector<int> >
00218 *Nauty::getOrbits() const
00219 {
00220   std::vector<std::vector<int> > *orb = new std::vector<std::vector<int> >;
00221   if (!autoComputed_) return orb;
00222   orb -> resize(getNumOrbits());
00223   std::multimap<int, int> orbmap;
00224   std::set<int> orbkeys;
00225   for (int j = 0; j < n_; j++) {
00226     orbkeys.insert(orbits_[j]);
00227     orbmap.insert(std::make_pair(orbits_[j], j));
00228   }
00229 
00230   int orbix = 0;
00231   for (std::set<int>::iterator it = orbkeys.begin();
00232        it != orbkeys.end(); ++it) {
00233     std::multimap<int, int>::iterator pos;
00234     for (pos = orbmap.lower_bound(*it);
00235          pos != orbmap.upper_bound(*it); ++pos) {
00236       (*orb)[orbix].push_back(pos->second);
00237     }
00238     orbix++;
00239   }
00240 
00241   assert(orbix == getNumOrbits());
00242   return orb;
00243 }
00244 
00245 void
00246 Nauty::getVstat(double *v, int nv)
00247 {
00248   assert(nv == n_);
00249   memcpy(v, vstat_, nv * sizeof(VarStatus));
00250 }
00251 
00252 /*
00253 bool
00254 Nauty::isAllFixOneOrbit(const std::vector<int> &orbit) const
00255 {
00256 
00257   for(std::vector<int>::const_iterator it = orbit.begin();
00258       it != orbit.end(); ++it) {
00259     if (*it >= n_) return false;
00260     if (vstat_[*it] != FIX_AT_ONE) return false;
00261   }
00262   return true;
00263 }
00264 
00265 bool
00266 Nauty::isAllFreeOrbit(const std::vector<int> &orbit) const
00267 {
00268   for(std::vector<int>::const_iterator it = orbit.begin();
00269       it != orbit.end(); ++it) {
00270     if (*it >= n_) return false;
00271     if (vstat_[*it] != FREE) return false;
00272   }
00273   return true;
00274 }
00275 
00276 bool
00277 Nauty::isConstraintOrbit(const std::vector<int> &orbit) const
00278 {
00279   for(std::vector<int>::const_iterator it = orbit.begin();
00280       it != orbit.end(); ++it) {
00281     if (*it >= n_) return true;
00282   }
00283   return false;
00284   
00285 }
00286 
00287 bool
00288 Nauty::isMixedFreeZeroOrbit(const std::vector<int> &orbit) const
00289 {
00290   bool containsFree = false;
00291   bool containsZero = false;
00292 
00293   for(std::vector<int>::const_iterator it = orbit.begin();
00294       it != orbit.end(); ++it) {
00295     if (*it >= n_) return false;    
00296     if (vstat_[*it] == FREE) containsFree = true;
00297     if (vstat_[*it] == FIX_AT_ZERO) containsZero = true;    
00298     if (containsFree && containsZero) break;
00299   }  
00300   return (containsFree && containsZero);
00301 }
00302 */
00303 /*
00304 void 
00305 Nauty::setWriteAutoms(const std::string &fname)
00306 {
00307   afp_ = fopen(fname.c_str(), "w");
00308   options_->writeautoms = TRUE;
00309   options_->writemarkers = FALSE;
00310   options_->outfile = afp_;
00311 
00312 }
00313 
00314 void 
00315 Nauty::unsetWriteAutoms()
00316 {
00317   fclose(afp_);
00318   options_->writeautoms = FALSE;
00319 }
00320 */

Generated on Thu Sep 22 03:05:56 2011 by  doxygen 1.4.7