EMAN2
mcqd.h
Go to the documentation of this file.
00001 /*
00002     Copyright 2007-2012 Janez Konc 
00003 
00004     If you use this program, please cite: 
00005     Janez Konc and Dusanka Janezic. An improved branch and bound algorithm for the 
00006     maximum clique problem. MATCH Commun. Math. Comput. Chem., 2007, 58, 569-590.
00007 
00008     More information at: http://www.sicmm.org/~konc
00009 
00010     This program is free software: you can redistribute it and/or modify
00011     it under the terms of the GNU General Public License as published by
00012     the Free Software Foundation, either version 3 of the License, or
00013     (at your option) any later version.
00014 
00015     This program is distributed in the hope that it will be useful,
00016     but WITHOUT ANY WARRANTY; without even the implied warranty of
00017     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00018     GNU General Public License for more details.
00019 
00020     You should have received a copy of the GNU General Public License
00021     along with this program.  If not, see <http://www.gnu.org/licenses/>.
00022 */
00023 
00024 #ifndef MCQD
00025 #define MCQD
00026 
00027 #include <iostream>
00028 #include <algorithm>
00029 #include <assert.h>
00030 #ifdef DBG
00031 using namespace std;
00032 #endif
00033 
00034 class Maxclique {
00035   const bool* const* e;
00036   int pk, level;
00037   const float Tlimit;
00038   class Vertices {
00039     class Vertex {
00040       int i, d;
00041     public:
00042       void set_i(const int ii)  { i = ii; }
00043       int get_i() const { return i; }
00044       void set_degree(int dd) { d = dd; }
00045       int get_degree() const { return d; }
00046     };
00047     Vertex *v;
00048     int sz;
00049     static bool desc_degree(const Vertex vi, const Vertex vj) { return (vi.get_degree() > vj.get_degree()); }
00050   public:
00051 #ifdef DBG
00052     void dbg_v(const string msg="") const {
00053       std::cout << msg << " Vertices: [";
00054       for (int i=0; i < sz; i++) 
00055         std::cout << "(" << v[i].get_i() << "," << v[i].get_degree() << ") ";
00056       std::cout << "]" << std::endl;
00057     }
00058 #endif
00059     Vertices(int size) : sz(0) { v = new Vertex[size]; }
00060     ~Vertices () {}
00061     void dispose() { if (v) delete [] v; }
00062     void sort() { std::sort(v, v+sz, desc_degree); }
00063     void init_colors();
00064     void set_degrees(Maxclique&);
00065     int size() const { return sz; }
00066     void push(const int ii) { v[sz++].set_i(ii); };
00067     void pop() { sz--; };
00068     Vertex& at(const int ii) const { return v[ii]; };
00069     Vertex& end() const { return v[sz - 1]; };
00070   };
00071   class ColorClass {
00072     int *i;
00073     int sz;
00074   public:
00075 #ifdef DBG
00076     void dbg_i(const string msg="") const {
00077       std::cout << msg << " Class: [";
00078       for (int ii=0; ii < sz; ii++) 
00079         std::cout << i[ii] << " ";
00080       std::cout << "]" << std::endl;
00081     }
00082 #endif
00083     ColorClass() : sz(0), i(0) {}
00084     ColorClass(const int sz) : sz(sz), i(0) { init(sz); }
00085     ~ColorClass() { if (i) delete [] i;
00086     }
00087     void init(const int sz) { i = new int[sz]; rewind(); }
00088     void push(const int ii) { i[sz++] = ii; };
00089     void pop() { sz--; };
00090     void rewind() { sz = 0; };
00091     int size() const { return sz; }
00092     int& at(const int ii) const { return i[ii]; }
00093     ColorClass& operator=(const ColorClass& dh) {
00094       for (int j = 0; j < dh.sz; j++) i[j] = dh.i[j];
00095       sz = dh.sz;
00096       return *this;
00097     }
00098   };
00099   Vertices V;
00100   ColorClass *C, QMAX, Q;
00101   class StepCount {
00102     int i1, i2;
00103   public:
00104     StepCount() : i1(0), i2(0) {}
00105     void set_i1(const int ii)  { i1 = ii; }
00106     int get_i1() const { return i1; }
00107     void set_i2(const int ii)  { i2 = ii; }
00108     int get_i2() const { return i2; }
00109     void inc_i1()  { i1++; }
00110   };
00111   StepCount *S;
00112   bool connection(const int i, const int j) const { return e[i][j]; }
00113   bool cut1(const int, const ColorClass&);
00114   void cut2(const Vertices&, Vertices&);
00115   void color_sort(Vertices&);
00116   void expand(Vertices);
00117   void expand_dyn(Vertices);
00118   void _mcq(int*&, int&, bool);
00119   void degree_sort(Vertices &R) { R.set_degrees(*this); R.sort(); }
00120 public:
00121 #ifdef DBG
00122   void dbg_C() const {
00123     for (int i=0; i < V.size(); i++) {
00124       std::cout << "C["<< i << "] : ";
00125       C[i].dbg_i();
00126     }
00127   }
00128   void dbg_conn() const {
00129     for (int i=0; i < V.size(); i++) {
00130       for (int j=0; j < V.size(); j++) {
00131         std::cout <<e[i][j];
00132       }
00133       std::cout<< std::endl;
00134     }
00135   }
00136 #endif
00137   Maxclique(const bool* const*, const int, const float=0.025);
00138   int steps() const { return pk; }
00139   void mcq(int* &maxclique, int &sz) { _mcq(maxclique, sz, false); }
00140   void mcqdyn(int* &maxclique, int &sz) { _mcq(maxclique, sz, true); }
00141   ~Maxclique() {
00142     if (C) delete [] C;
00143     if (S) delete [] S;
00144     V.dispose();
00145   };
00146 };
00147 
00148 Maxclique::Maxclique (const bool* const* conn, const int sz, const float tt) : pk(0), level(1), Tlimit(tt), V(sz), Q(sz), QMAX(sz) {
00149   assert(conn!=0 && sz>0);
00150   for (int i=0; i < sz; i++) V.push(i);
00151   e = conn;
00152   C = new ColorClass[sz + 1];
00153   for (int i=0; i < sz + 1; i++) C[i].init(sz + 1);
00154   S = new StepCount[sz + 1];
00155 }
00156 
00157 void Maxclique::_mcq(int* &maxclique, int &sz, bool dyn) { 
00158   V.set_degrees(*this);
00159   V.sort();
00160   V.init_colors();
00161   if (dyn) {
00162     for (int i=0; i < V.size() + 1; i++) {
00163       S[i].set_i1(0);
00164       S[i].set_i2(0);
00165     }
00166     expand_dyn(V);
00167   }
00168   else
00169     expand(V);
00170   maxclique = new int[QMAX.size()]; 
00171   for (int i=0; i<QMAX.size(); i++) { 
00172     maxclique[i] = QMAX.at(i);
00173   }
00174   sz = QMAX.size();
00175 }
00176 
00177 void Maxclique::Vertices::init_colors() { 
00178   const int max_degree = v[0].get_degree();
00179   for (int i = 0; i < max_degree; i++)
00180     v[i].set_degree(i + 1);
00181   for (int i = max_degree; i < sz; i++)
00182     v[i].set_degree(max_degree + 1);
00183 }
00184 
00185 void Maxclique::Vertices::set_degrees(Maxclique &m) { 
00186   for (int i=0; i < sz; i++) {
00187     int d = 0;
00188     for (int j=0; j < sz; j++)
00189       if (m.connection(v[i].get_i(), v[j].get_i())) d++;
00190     v[i].set_degree(d);
00191   }
00192 }
00193 
00194 bool Maxclique::cut1(const int pi, const ColorClass &A) {
00195   for (int i = 0; i < A.size(); i++)
00196     if (connection(pi, A.at(i)))
00197       return true;
00198   return false;
00199 }
00200 
00201 void Maxclique::cut2(const Vertices &A, Vertices &B) {
00202   for (int i = 0; i < A.size() - 1; i++) {
00203     if (connection(A.end().get_i(), A.at(i).get_i()))
00204       B.push(A.at(i).get_i());
00205   }
00206 }
00207 
00208 void Maxclique::color_sort(Vertices &R) {
00209   int j = 0;
00210   int maxno = 1;
00211   int min_k = QMAX.size() - Q.size() + 1;
00212   C[1].rewind();
00213   C[2].rewind();
00214   int k = 1;
00215   for (int i=0; i < R.size(); i++) {
00216     int pi = R.at(i).get_i();
00217     k = 1;
00218     while (cut1(pi, C[k]))
00219       k++;
00220     if (k > maxno) {
00221       maxno = k;
00222       C[maxno + 1].rewind();
00223     }
00224     C[k].push(pi);
00225     if (k < min_k) {
00226       R.at(j++).set_i(pi);
00227     }
00228   }
00229   if (j > 0) R.at(j-1).set_degree(0);
00230   if (min_k <= 0) min_k = 1;
00231   for (k = min_k; k <= maxno; k++)
00232     for (int i = 0; i < C[k].size(); i++) {
00233       R.at(j).set_i(C[k].at(i));
00234       R.at(j++).set_degree(k);
00235     }
00236 }
00237 
00238 void Maxclique::expand(Vertices R) {
00239   while (R.size()) {
00240     if (Q.size() + R.end().get_degree() > QMAX.size()) {
00241       Q.push(R.end().get_i());
00242       Vertices Rp(R.size());
00243       cut2(R, Rp);
00244       if (Rp.size()) {
00245         color_sort(Rp);
00246         pk++;
00247         expand(Rp);
00248       }
00249       else if (Q.size() > QMAX.size()) { 
00250 //        std::cout << "step = " << pk << " current max. clique size = " << Q.size() << std::endl;
00251         QMAX = Q;
00252       }    
00253       Rp.dispose();
00254       Q.pop();
00255     }
00256     else {
00257       return;
00258     }
00259     R.pop();
00260   }
00261 }
00262 
00263 void Maxclique::expand_dyn(Vertices R) {
00264   S[level].set_i1(S[level].get_i1() + S[level - 1].get_i1() - S[level].get_i2());
00265   S[level].set_i2(S[level - 1].get_i1());
00266   while (R.size()) {
00267     if (Q.size() + R.end().get_degree() > QMAX.size()) {
00268       Q.push(R.end().get_i());
00269       Vertices Rp(R.size());
00270       cut2(R, Rp);
00271       if (Rp.size()) {
00272         if ((float)S[level].get_i1()/++pk < Tlimit) {
00273           degree_sort(Rp);
00274         }
00275         color_sort(Rp);
00276         S[level].inc_i1();
00277         level++;
00278         expand_dyn(Rp);
00279         level--;
00280       }
00281       else if (Q.size() > QMAX.size()) { 
00282 //        std::cout << "step = " << pk << " current max. clique size = " << Q.size() << std::endl;
00283         QMAX = Q;
00284       }    
00285       Rp.dispose();
00286       Q.pop();
00287     }
00288     else {
00289       return;
00290     }
00291     R.pop();
00292   }
00293 }
00294 
00295 #endif