EMAN2
Classes | Public Member Functions | Private Member Functions | Private Attributes
Maxclique Class Reference

#include <mcqd.h>

Collaboration diagram for Maxclique:
Collaboration graph
[legend]

List of all members.

Classes

class  ColorClass
class  StepCount
class  Vertices

Public Member Functions

 Maxclique (const bool *const *, const int, const float=0.025)
int steps () const
void mcq (int *&maxclique, int &sz)
void mcqdyn (int *&maxclique, int &sz)
 ~Maxclique ()

Private Member Functions

bool connection (const int i, const int j) const
bool cut1 (const int, const ColorClass &)
void cut2 (const Vertices &, Vertices &)
void color_sort (Vertices &)
void expand (Vertices)
void expand_dyn (Vertices)
void _mcq (int *&, int &, bool)
void degree_sort (Vertices &R)

Private Attributes

const bool *const e
int pk
int level
const float Tlimit
Vertices V
ColorClassC
ColorClass QMAX
ColorClass Q
StepCountS

Detailed Description

Definition at line 34 of file mcqd.h.


Constructor & Destructor Documentation

Maxclique::Maxclique ( const bool *const *  conn,
const int  sz,
const float  tt = 0.025 
)

Definition at line 148 of file mcqd.h.

References C, e, Maxclique::Vertices::push(), S, and V.

                                                                           : pk(0), level(1), Tlimit(tt), V(sz), Q(sz), QMAX(sz) {
  assert(conn!=0 && sz>0);
  for (int i=0; i < sz; i++) V.push(i);
  e = conn;
  C = new ColorClass[sz + 1];
  for (int i=0; i < sz + 1; i++) C[i].init(sz + 1);
  S = new StepCount[sz + 1];
}
Maxclique::~Maxclique ( ) [inline]

Definition at line 141 of file mcqd.h.

References C, and V.

               {
    if (C) delete [] C;
    if (S) delete [] S;
    V.dispose();
  };

Member Function Documentation

void Maxclique::_mcq ( int *&  maxclique,
int &  sz,
bool  dyn 
) [private]

Definition at line 157 of file mcqd.h.

References Maxclique::ColorClass::at(), expand(), expand_dyn(), Maxclique::Vertices::init_colors(), QMAX, S, Maxclique::Vertices::set_degrees(), Maxclique::StepCount::set_i1(), Maxclique::StepCount::set_i2(), Maxclique::ColorClass::size(), Maxclique::Vertices::size(), Maxclique::Vertices::sort(), and V.

                                                       { 
  V.set_degrees(*this);
  V.sort();
  V.init_colors();
  if (dyn) {
    for (int i=0; i < V.size() + 1; i++) {
      S[i].set_i1(0);
      S[i].set_i2(0);
    }
    expand_dyn(V);
  }
  else
    expand(V);
  maxclique = new int[QMAX.size()]; 
  for (int i=0; i<QMAX.size(); i++) { 
    maxclique[i] = QMAX.at(i);
  }
  sz = QMAX.size();
}
void Maxclique::color_sort ( Vertices R) [private]

Definition at line 208 of file mcqd.h.

References Maxclique::Vertices::at(), C, cut1(), pi, Maxclique::ColorClass::push(), Q, QMAX, Maxclique::ColorClass::rewind(), Maxclique::Vertices::size(), and Maxclique::ColorClass::size().

Referenced by expand(), and expand_dyn().

                                      {
  int j = 0;
  int maxno = 1;
  int min_k = QMAX.size() - Q.size() + 1;
  C[1].rewind();
  C[2].rewind();
  int k = 1;
  for (int i=0; i < R.size(); i++) {
    int pi = R.at(i).get_i();
    k = 1;
    while (cut1(pi, C[k]))
      k++;
    if (k > maxno) {
      maxno = k;
      C[maxno + 1].rewind();
    }
    C[k].push(pi);
    if (k < min_k) {
      R.at(j++).set_i(pi);
    }
  }
  if (j > 0) R.at(j-1).set_degree(0);
  if (min_k <= 0) min_k = 1;
  for (k = min_k; k <= maxno; k++)
    for (int i = 0; i < C[k].size(); i++) {
      R.at(j).set_i(C[k].at(i));
      R.at(j++).set_degree(k);
    }
}
bool Maxclique::connection ( const int  i,
const int  j 
) const [inline, private]

Definition at line 112 of file mcqd.h.

Referenced by cut1(), cut2(), and Maxclique::Vertices::set_degrees().

{ return e[i][j]; }
bool Maxclique::cut1 ( const int  pi,
const ColorClass A 
) [private]

Definition at line 194 of file mcqd.h.

References Maxclique::ColorClass::at(), connection(), and Maxclique::ColorClass::size().

Referenced by color_sort().

                                                      {
  for (int i = 0; i < A.size(); i++)
    if (connection(pi, A.at(i)))
      return true;
  return false;
}
void Maxclique::cut2 ( const Vertices A,
Vertices B 
) [private]

Definition at line 201 of file mcqd.h.

References Maxclique::Vertices::at(), connection(), Maxclique::Vertices::end(), Maxclique::Vertices::push(), and Maxclique::Vertices::size().

Referenced by expand(), and expand_dyn().

                                                   {
  for (int i = 0; i < A.size() - 1; i++) {
    if (connection(A.end().get_i(), A.at(i).get_i()))
      B.push(A.at(i).get_i());
  }
}
void Maxclique::degree_sort ( Vertices R) [inline, private]

Definition at line 119 of file mcqd.h.

References Maxclique::Vertices::set_degrees(), and Maxclique::Vertices::sort().

Referenced by expand_dyn().

{ R.set_degrees(*this); R.sort(); }
void Maxclique::expand ( Vertices  R) [private]

Definition at line 238 of file mcqd.h.

References color_sort(), cut2(), Maxclique::Vertices::end(), pk, Maxclique::Vertices::pop(), Maxclique::ColorClass::pop(), Maxclique::ColorClass::push(), Q, QMAX, Maxclique::ColorClass::size(), and Maxclique::Vertices::size().

Referenced by _mcq().

                                 {
  while (R.size()) {
    if (Q.size() + R.end().get_degree() > QMAX.size()) {
      Q.push(R.end().get_i());
      Vertices Rp(R.size());
      cut2(R, Rp);
      if (Rp.size()) {
        color_sort(Rp);
        pk++;
        expand(Rp);
      }
      else if (Q.size() > QMAX.size()) { 
//        std::cout << "step = " << pk << " current max. clique size = " << Q.size() << std::endl;
        QMAX = Q;
      }    
      Rp.dispose();
      Q.pop();
    }
    else {
      return;
    }
    R.pop();
  }
}
void Maxclique::expand_dyn ( Vertices  R) [private]

Definition at line 263 of file mcqd.h.

References color_sort(), cut2(), degree_sort(), Maxclique::Vertices::end(), Maxclique::StepCount::get_i1(), Maxclique::StepCount::inc_i1(), level, pk, Maxclique::Vertices::pop(), Maxclique::ColorClass::pop(), Maxclique::ColorClass::push(), Q, QMAX, S, Maxclique::StepCount::set_i1(), Maxclique::StepCount::set_i2(), Maxclique::ColorClass::size(), Maxclique::Vertices::size(), and Tlimit.

Referenced by _mcq().

                                     {
  S[level].set_i1(S[level].get_i1() + S[level - 1].get_i1() - S[level].get_i2());
  S[level].set_i2(S[level - 1].get_i1());
  while (R.size()) {
    if (Q.size() + R.end().get_degree() > QMAX.size()) {
      Q.push(R.end().get_i());
      Vertices Rp(R.size());
      cut2(R, Rp);
      if (Rp.size()) {
        if ((float)S[level].get_i1()/++pk < Tlimit) {
          degree_sort(Rp);
        }
        color_sort(Rp);
        S[level].inc_i1();
        level++;
        expand_dyn(Rp);
        level--;
      }
      else if (Q.size() > QMAX.size()) { 
//        std::cout << "step = " << pk << " current max. clique size = " << Q.size() << std::endl;
        QMAX = Q;
      }    
      Rp.dispose();
      Q.pop();
    }
    else {
      return;
    }
    R.pop();
  }
}
void Maxclique::mcq ( int *&  maxclique,
int &  sz 
) [inline]

Definition at line 139 of file mcqd.h.

Referenced by EMAN::Util::max_clique().

{ _mcq(maxclique, sz, false); }
void Maxclique::mcqdyn ( int *&  maxclique,
int &  sz 
) [inline]

Definition at line 140 of file mcqd.h.

{ _mcq(maxclique, sz, true); }
int Maxclique::steps ( ) const [inline]

Definition at line 138 of file mcqd.h.

{ return pk; }

Member Data Documentation

Definition at line 100 of file mcqd.h.

Referenced by color_sort(), and Maxclique().

const bool* const Maxclique::e [private]

Definition at line 35 of file mcqd.h.

Referenced by Maxclique().

int Maxclique::level [private]

Definition at line 36 of file mcqd.h.

Referenced by expand_dyn().

int Maxclique::pk [private]

Definition at line 36 of file mcqd.h.

Referenced by expand(), and expand_dyn().

Definition at line 100 of file mcqd.h.

Referenced by color_sort(), expand(), and expand_dyn().

Definition at line 100 of file mcqd.h.

Referenced by _mcq(), color_sort(), expand(), and expand_dyn().

StepCount* Maxclique::S [private]

Definition at line 111 of file mcqd.h.

Referenced by _mcq(), expand_dyn(), and Maxclique().

const float Maxclique::Tlimit [private]

Definition at line 37 of file mcqd.h.

Referenced by expand_dyn().

Definition at line 99 of file mcqd.h.

Referenced by _mcq(), and Maxclique().


The documentation for this class was generated from the following file: