/*
 * MATLAB Compiler: 3.0
 * Date: Mon Nov 03 13:00:57 2003
 * Arguments: "-B" "macro_default" "-O" "all" "-O" "fold_scalar_mxarrays:on"
 * "-O" "fold_non_scalar_mxarrays:on" "-O" "optimize_integer_for_loops:on" "-O"
 * "array_indexing:on" "-O" "optimize_conditionals:on" "-m" "-W" "main" "-L"
 * "C" "-t" "-T" "link:exe" "-h" "libmmfile.mlib" "DancingMonkeys" 
 */
#include "maximalcliques.h"
#include "libmatlbm.h"
static mxArray * _mxarray0_;
static mxArray * _mxarray1_;
static mxArray * _mxarray2_;
static mxArray * _mxarray3_;
static mxArray * _mxarray4_;
static mxArray * _mxarray5_;

void InitializeModule_maximalcliques(void) {
    _mxarray0_ = mclInitializeDouble(1.0);
    _mxarray1_ = mclInitializeDouble(0.0);
    _mxarray2_ = mclInitializeDoubleVector(0, 0, (double *)NULL);
    _mxarray3_ = mclInitializeCellVector(0, 0, (mxArray * *)NULL);
    _mxarray4_ = mclInitializeDouble(2.0);
    _mxarray5_ = mclInitializeDouble(-1.0);
}

void TerminateModule_maximalcliques(void) {
    mxDestroyArray(_mxarray5_);
    mxDestroyArray(_mxarray4_);
    mxDestroyArray(_mxarray3_);
    mxDestroyArray(_mxarray2_);
    mxDestroyArray(_mxarray1_);
    mxDestroyArray(_mxarray0_);
}

static mxArray * mlfMaximalcliques_extend(mxArray * ne,
                                          mxArray * compsub,
                                          mxArray * connected,
                                          mxArray * index);
static void mlxMaximalcliques_extend(int nlhs,
                                     mxArray * plhs[],
                                     int nrhs,
                                     mxArray * prhs[]);
static mxArray * Mmaximalcliques(int nargout_, mxArray * connected);
static mxArray * Mmaximalcliques_extend(int nargout_,
                                        mxArray * ne,
                                        mxArray * compsub,
                                        mxArray * connected,
                                        mxArray * index);

static mexFunctionTableEntry local_function_table_[1]
  = { { "extend", mlxMaximalcliques_extend, 4, 1, NULL } };

_mexLocalFunctionTable _local_function_table_maximalcliques
  = { 1, local_function_table_ };

/*
 * The function "mlfMaximalcliques" contains the normal interface for the
 * "maximalcliques" M-function from file "c:\matlab65\work\maximalcliques.m"
 * (lines 1-28). This function processes any input arguments and passes them to
 * the implementation version of the function, appearing above.
 */
mxArray * mlfMaximalcliques(mxArray * connected) {
    int nargout = 1;
    mxArray * cliques = NULL;
    mlfEnterNewContext(0, 1, connected);
    cliques = Mmaximalcliques(nargout, connected);
    mlfRestorePreviousContext(0, 1, connected);
    return mlfReturnValue(cliques);
}

/*
 * The function "mlxMaximalcliques" contains the feval interface for the
 * "maximalcliques" M-function from file "c:\matlab65\work\maximalcliques.m"
 * (lines 1-28). The feval function calls the implementation version of
 * maximalcliques through this function. This function processes any input
 * arguments and passes them to the implementation version of the function,
 * appearing above.
 */
void mlxMaximalcliques(int nlhs, mxArray * plhs[], int nrhs, mxArray * prhs[]) {
    mxArray * mprhs[1];
    mxArray * mplhs[1];
    int i;
    if (nlhs > 1) {
        mlfError(
          mxCreateString(
            "Run-time Error: File: maximalcliques Line: 1 Colum"
            "n: 1 The function \"maximalcliques\" was called wi"
            "th more than the declared number of outputs (1)."),
          NULL);
    }
    if (nrhs > 1) {
        mlfError(
          mxCreateString(
            "Run-time Error: File: maximalcliques Line: 1 Colum"
            "n: 1 The function \"maximalcliques\" was called wi"
            "th more than the declared number of inputs (1)."),
          NULL);
    }
    for (i = 0; i < 1; ++i) {
        mplhs[i] = NULL;
    }
    for (i = 0; i < 1 && i < nrhs; ++i) {
        mprhs[i] = prhs[i];
    }
    for (; i < 1; ++i) {
        mprhs[i] = NULL;
    }
    mlfEnterNewContext(0, 1, mprhs[0]);
    mplhs[0] = Mmaximalcliques(nlhs, mprhs[0]);
    mlfRestorePreviousContext(0, 1, mprhs[0]);
    plhs[0] = mplhs[0];
}

/*
 * The function "mlfMaximalcliques_extend" contains the normal interface for
 * the "maximalcliques/extend" M-function from file
 * "c:\matlab65\work\maximalcliques.m" (lines 28-75). This function processes
 * any input arguments and passes them to the implementation version of the
 * function, appearing above.
 */
static mxArray * mlfMaximalcliques_extend(mxArray * ne,
                                          mxArray * compsub,
                                          mxArray * connected,
                                          mxArray * index) {
    int nargout = 1;
    mxArray * cliques = NULL;
    mlfEnterNewContext(0, 4, ne, compsub, connected, index);
    cliques = Mmaximalcliques_extend(nargout, ne, compsub, connected, index);
    mlfRestorePreviousContext(0, 4, ne, compsub, connected, index);
    return mlfReturnValue(cliques);
}

/*
 * The function "mlxMaximalcliques_extend" contains the feval interface for the
 * "maximalcliques/extend" M-function from file
 * "c:\matlab65\work\maximalcliques.m" (lines 28-75). The feval function calls
 * the implementation version of maximalcliques/extend through this function.
 * This function processes any input arguments and passes them to the
 * implementation version of the function, appearing above.
 */
static void mlxMaximalcliques_extend(int nlhs,
                                     mxArray * plhs[],
                                     int nrhs,
                                     mxArray * prhs[]) {
    mxArray * mprhs[4];
    mxArray * mplhs[1];
    int i;
    if (nlhs > 1) {
        mlfError(
          mxCreateString(
            "Run-time Error: File: maximalcliques/extend Line: 28 Co"
            "lumn: 1 The function \"maximalcliques/extend\" was call"
            "ed with more than the declared number of outputs (1)."),
          NULL);
    }
    if (nrhs > 4) {
        mlfError(
          mxCreateString(
            "Run-time Error: File: maximalcliques/extend Line: 28 Co"
            "lumn: 1 The function \"maximalcliques/extend\" was call"
            "ed with more than the declared number of inputs (4)."),
          NULL);
    }
    for (i = 0; i < 1; ++i) {
        mplhs[i] = NULL;
    }
    for (i = 0; i < 4 && i < nrhs; ++i) {
        mprhs[i] = prhs[i];
    }
    for (; i < 4; ++i) {
        mprhs[i] = NULL;
    }
    mlfEnterNewContext(0, 4, mprhs[0], mprhs[1], mprhs[2], mprhs[3]);
    mplhs[0]
      = Mmaximalcliques_extend(nlhs, mprhs[0], mprhs[1], mprhs[2], mprhs[3]);
    mlfRestorePreviousContext(0, 4, mprhs[0], mprhs[1], mprhs[2], mprhs[3]);
    plhs[0] = mplhs[0];
}

/*
 * The function "Mmaximalcliques" is the implementation version of the
 * "maximalcliques" M-function from file "c:\matlab65\work\maximalcliques.m"
 * (lines 1-28). It contains the actual compiled code for that M-function. It
 * is a static function and must only be called from one of the interface
 * functions, appearing below.
 */
/*
 * function cliques = maximalcliques( connected );
 */
static mxArray * Mmaximalcliques(int nargout_, mxArray * connected) {
    mexLocalFunctionTable save_local_function_table_
      = mclSetCurrentLocalFunctionTable(&_local_function_table_maximalcliques);
    mxArray * cliques = NULL;
    mxArray * ndx = NULL;
    mclCopyArray(&connected);
    /*
     * % CLIQUES = cliqueBK (PAIRS);
     * %
     * % PAIRS has list of pairs of data items, this routine finds mutual pairs (maximal cliques)
     * % PAIRS are of form 1 1 1 1 2 2 2 6
     * %                   2 3 6 7 3 5 7 7
     * % CLIQUES returned   {1 2 3}, {1 2 7}, {1 6 7} and {2 5} 
     * % MATLAB efficient Implementation of algorithm due to Bron and Kerbosch
     * % forms connected, a symmetrical Boolean matrix connected. 
     * % n is the number of nodes in the graph. The values of the diagonal elements should be true
     * % then processes connected using backtracking, but with branch and bound method to
     * % prevent paths searched more than once.
     * %
     * % Dr Richard Mitchell, 22.5.02; 
     * % revised 29.7.02 - to speed first half, and use smaller connected
     * %         08.8.02
     * %
     * 
     * % n = max(max(pairs));                                    % find maximum number in pairs
     * % connected = eye(n);                                     % set matrix with each node connected to self
     * % for ct = 1:size(pairs,1),                               % fill in connections
     * %     connected(pairs(ct,1),pairs(ct,2)) = 1; 
     * %     connected(pairs(ct,2),pairs(ct,1)) = 1; 
     * % end; 
     * ndx = find(sum(connected)>1);                           % ndx is numbers which do exist
     */
    mlfAssign(
      &ndx,
      mlfFind(
        NULL,
        NULL,
        mclGt(mlfSum(mclVa(connected, "connected"), NULL), _mxarray0_)));
    /*
     * cliques = extend (0, [], connected(ndx,ndx), ndx);      % find the cliques
     */
    mlfAssign(
      &cliques,
      mlfMaximalcliques_extend(
        _mxarray1_,
        _mxarray2_,
        mclArrayRef2(
          mclVa(connected, "connected"), mclVv(ndx, "ndx"), mclVv(ndx, "ndx")),
        mclVv(ndx, "ndx")));
    mclValidateOutput(cliques, 1, nargout_, "cliques", "maximalcliques");
    mxDestroyArray(ndx);
    mxDestroyArray(connected);
    mclSetCurrentLocalFunctionTable(save_local_function_table_);
    return cliques;
    /*
     * 
     */
}

/*
 * The function "Mmaximalcliques_extend" is the implementation version of the
 * "maximalcliques/extend" M-function from file
 * "c:\matlab65\work\maximalcliques.m" (lines 28-75). It contains the actual
 * compiled code for that M-function. It is a static function and must only be
 * called from one of the interface functions, appearing below.
 */
/*
 * function cliques = extend(ne, compsub, connected, index);
 */
static mxArray * Mmaximalcliques_extend(int nargout_,
                                        mxArray * ne,
                                        mxArray * compsub,
                                        mxArray * connected,
                                        mxArray * index) {
    mexLocalFunctionTable save_local_function_table_
      = mclSetCurrentLocalFunctionTable(&_local_function_table_maximalcliques);
    mxArray * cliques = NULL;
    mxArray * newcliques = NULL;
    mxArray * newce = NULL;
    mxArray * new = NULL;
    mxArray * newne = NULL;
    mxArray * sel = NULL;
    mxArray * nod = NULL;
    mxArray * nocons = NULL;
    mxArray * s = NULL;
    mxArray * minnod = NULL;
    mxArray * fixp = NULL;
    mxArray * maxw = NULL;
    mxArray * maxv = NULL;
    mxArray * old = NULL;
    mxArray * ce = NULL;
    mclCopyArray(&ne);
    mclCopyArray(&compsub);
    mclCopyArray(&connected);
    mclCopyArray(&index);
    /*
     * % old[1..ne] are NOT, OLD[ne+1..ce] are CANDIDATES
     * % compsub is clique array, c is position in array
     * cliques = {};                                           % no cliques initially
     */
    mlfAssign(&cliques, _mxarray3_);
    /*
     * ce = size(connected,1);                                 % set ce
     */
    mlfAssign(
      &ce,
      mlfSize(mclValueVarargout(), mclVa(connected, "connected"), _mxarray0_));
    /*
     * old = 1:ce;                                             % old is range 1 to ce
     */
    mlfAssign(&old, mlfColon(_mxarray0_, mclVv(ce, "ce"), NULL));
    /*
     * 
     * [maxv, maxw] = max(sum(connected(:,ne+1:ce),2));        % find column with most 1's
     */
    mlfAssign(
      &maxv,
      mlfMax(
        &maxw,
        mlfSum(
          mclArrayRef2(
            mclVa(connected, "connected"),
            mlfCreateColonIndex(),
            mlfColon(
              mclPlus(mclVa(ne, "ne"), _mxarray0_), mclVv(ce, "ce"), NULL)),
          _mxarray4_),
        NULL,
        NULL));
    /*
     * fixp = maxw(1);                                         % this is column to use: remember it
     */
    mlfAssign(&fixp, mclIntArrayRef1(mclVv(maxw, "maxw"), 1));
    /*
     * minnod = ce - ne - maxv;                                % this is number of zeros
     */
    mlfAssign(
      &minnod,
      mclMinus(
        mclMinus(mclVv(ce, "ce"), mclVa(ne, "ne")), mclVv(maxv, "maxv")));
    /*
     * if fixp > ne                                            % if minimum is from CANDIDATES
     */
    if (mclGtBool(mclVv(fixp, "fixp"), mclVa(ne, "ne"))) {
        /*
         * s = fixp;                                           % this is first column to use
         */
        mlfAssign(&s, mclVv(fixp, "fixp"));
        /*
         * minnod = minnod + 1;                                % preincrement number of disconnections
         */
        mlfAssign(&minnod, mclPlus(mclVv(minnod, "minnod"), _mxarray0_));
    /*
     * elseif minnod > 0                                       % if some non connections
     */
    } else if (mclGtBool(mclVv(minnod, "minnod"), _mxarray1_)) {
        /*
         * nocons = find (connected(ne+1:ce,fixp)==0);
         */
        mlfAssign(
          &nocons,
          mlfFind(
            NULL,
            NULL,
            mclEq(
              mclArrayRef2(
                mclVa(connected, "connected"),
                mlfColon(
                  mclPlus(mclVa(ne, "ne"), _mxarray0_), mclVv(ce, "ce"), NULL),
                mclVv(fixp, "fixp")),
              _mxarray1_)));
        /*
         * s = ne + nocons(length(nocons));                    % s is last non connection
         */
        mlfAssign(
          &s,
          mclPlus(
            mclVa(ne, "ne"),
            mclIntArrayRef1(
              mclVv(nocons, "nocons"), mclLengthInt(mclVv(nocons, "nocons")))));
    /*
     * end
     */
    }
    /*
     * % BACKTRACKCYCLE
     * for nod = minnod : -1 : 1, 
     */
    {
        mclForLoopIterator viter__;
        for (mclForStart(
               &viter__, mclVv(minnod, "minnod"), _mxarray5_, _mxarray0_);
             mclForNext(&viter__, &nod);
             ) {
            /*
             * sel = old(s);                                       % select item, and swap with ne+1'th
             */
            mlfAssign(&sel, mclArrayRef1(mclVv(old, "old"), mclVv(s, "s")));
            /*
             * old(s) = old(ne + 1);                               % so can add selected to NOT set
             */
            mclArrayAssign1(
              &old,
              mclArrayRef1(
                mclVv(old, "old"), mclPlus(mclVa(ne, "ne"), _mxarray0_)),
              mclVv(s, "s"));
            /*
             * old(ne + 1) = sel;
             */
            mclArrayAssign1(
              &old, mclVv(sel, "sel"), mclPlus(mclVa(ne, "ne"), _mxarray0_));
            /*
             * 
             * connected(sel,sel)=0;                               % so sel not included in new sets
             */
            mclArrayAssign2(
              &connected, _mxarray1_, mclVv(sel, "sel"), mclVv(sel, "sel"));
            /*
             * newne = sum(connected(old(1:ne),sel)>0);            % num in NOT = those in sel connected to NOT
             */
            mlfAssign(
              &newne,
              mlfSum(
                mclGt(
                  mclArrayRef2(
                    mclVa(connected, "connected"),
                    mclArrayRef1(
                      mclVv(old, "old"),
                      mlfColon(_mxarray0_, mclVa(ne, "ne"), NULL)),
                    mclVv(sel, "sel")),
                  _mxarray1_),
                NULL));
            /*
             * new = old(connected(old,sel)>0);                    % new is old items connected to sel
             */
            mlfAssign(
              &new,
              mclArrayRef1(
                mclVv(old, "old"),
                mclGt(
                  mclArrayRef2(
                    mclVa(connected, "connected"),
                    mclVv(old, "old"),
                    mclVv(sel, "sel")),
                  _mxarray1_)));
            /*
             * newce = length(new);
             */
            mlfAssign(&newce, mlfScalar(mclLengthInt(mclVv(new, "new"))));
            /*
             * 
             * if newce==0                                         % compsub + sel is new cliqe
             */
            if (mclEqBool(mclVv(newce, "newce"), _mxarray1_)) {
                /*
                 * if length(compsub)>0, cliques = [cliques, {[compsub, index(sel)]}]; end
                 */
                if (mclLengthInt(mclVa(compsub, "compsub")) > 0) {
                    mlfAssign(
                      &cliques,
                      mlfHorzcat(
                        mclVv(cliques, "cliques"),
                        mlfCellhcat(
                          mlfHorzcat(
                            mclVa(compsub, "compsub"),
                            mclArrayRef1(
                              mclVa(index, "index"), mclVv(sel, "sel")),
                            NULL),
                          NULL),
                        NULL));
                }
            /*
             * % add found CLIQUE to cliques
             * elseif newce == 1 & newne == 0                      % only 1 new candidate
             */
            } else {
                mxArray * a_
                  = mclInitialize(mclEq(mclVv(newce, "newce"), _mxarray0_));
                if (mlfTobool(a_)
                    && mlfTobool(
                         mclAnd(
                           a_, mclEq(mclVv(newne, "newne"), _mxarray1_)))) {
                    mxDestroyArray(a_);
                    /*
                     * % so compsub, sel and candidate is clique
                     * cliques = [cliques, {[compsub, index([sel, new(1)])]}];
                     */
                    mlfAssign(
                      &cliques,
                      mlfHorzcat(
                        mclVv(cliques, "cliques"),
                        mlfCellhcat(
                          mlfHorzcat(
                            mclVa(compsub, "compsub"),
                            mclArrayRef1(
                              mclVa(index, "index"),
                              mlfHorzcat(
                                mclVv(sel, "sel"),
                                mclIntArrayRef1(mclVv(new, "new"), 1),
                                NULL)),
                            NULL),
                          NULL),
                        NULL));
                /*
                 * % add CLIQUE
                 * elseif newne < newce                                % if some CANDIDATES, search
                 */
                } else {
                    mxDestroyArray(a_);
                    if (mclLtBool(
                          mclVv(newne, "newne"), mclVv(newce, "newce"))) {
                        /*
                         * newcliques = extend(newne, [compsub, index(sel)], connected(new,new), index(new));
                         */
                        mlfAssign(
                          &newcliques,
                          mlfMaximalcliques_extend(
                            mclVv(newne, "newne"),
                            mlfHorzcat(
                              mclVa(compsub, "compsub"),
                              mclArrayRef1(
                                mclVa(index, "index"), mclVv(sel, "sel")),
                              NULL),
                            mclArrayRef2(
                              mclVa(connected, "connected"),
                              mclVv(new, "new"),
                              mclVv(new, "new")),
                            mclArrayRef1(
                              mclVa(index, "index"), mclVv(new, "new"))));
                        /*
                         * if ~isempty(newcliques), cliques = [cliques, newcliques]; end
                         */
                        if (mclNotBool(
                              mlfIsempty(mclVv(newcliques, "newcliques")))) {
                            mlfAssign(
                              &cliques,
                              mlfHorzcat(
                                mclVv(cliques, "cliques"),
                                mclVv(newcliques, "newcliques"),
                                NULL));
                        }
                    }
                }
            /*
             * end	                                                % if new cliques, add them
             */
            }
            /*
             * 
             * if nod > 1 
             */
            if (mclGtBool(mclVv(nod, "nod"), _mxarray0_)) {
                /*
                 * ne = ne + 1;                                    % add selected candidate to NOT
                 */
                mlfAssign(&ne, mclPlus(mclVa(ne, "ne"), _mxarray0_));
                /*
                 * s = ne + 1;                                     % select candidate not connected to fixp
                 */
                mlfAssign(&s, mclPlus(mclVa(ne, "ne"), _mxarray0_));
                /*
                 * while connected(fixp, old(s)), s = s + 1; end
                 */
                while (mlfTobool(
                         mclArrayRef2(
                           mclVa(connected, "connected"),
                           mclVv(fixp, "fixp"),
                           mclArrayRef1(mclVv(old, "old"), mclVv(s, "s"))))) {
                    mlfAssign(&s, mclPlus(mclVv(s, "s"), _mxarray0_));
                }
            /*
             * end
             */
            }
        /*
         * end
         */
        }
        mclDestroyForLoopIterator(viter__);
    }
    mclValidateOutput(cliques, 1, nargout_, "cliques", "maximalcliques/extend");
    mxDestroyArray(ce);
    mxDestroyArray(old);
    mxDestroyArray(maxv);
    mxDestroyArray(maxw);
    mxDestroyArray(fixp);
    mxDestroyArray(minnod);
    mxDestroyArray(s);
    mxDestroyArray(nocons);
    mxDestroyArray(nod);
    mxDestroyArray(sel);
    mxDestroyArray(newne);
    mxDestroyArray(new);
    mxDestroyArray(newce);
    mxDestroyArray(newcliques);
    mxDestroyArray(index);
    mxDestroyArray(connected);
    mxDestroyArray(compsub);
    mxDestroyArray(ne);
    mclSetCurrentLocalFunctionTable(save_local_function_table_);
    return cliques;
    /*
     * 
     */
}
