/*M///////////////////////////////////////////////////////////////////////////////////////
//
//  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
//
//  By downloading, copying, installing or using the software you agree to this license.
//  If you do not agree to this license, do not download, install,
//  copy or use the software.
//
//
//                        Intel License Agreement
//                For Open Source Computer Vision Library
//
// Copyright (C) 2000, Intel Corporation, all rights reserved.
// Third party copyrights are property of their respective owners.
//
// Redistribution and use in source and binary forms, with or without modification,
// are permitted provided that the following conditions are met:
//
//   * Redistribution's of source code must retain the above copyright notice,
//     this list of conditions and the following disclaimer.
//
//   * Redistribution's in binary form must reproduce the above copyright notice,
//     this list of conditions and the following disclaimer in the documentation
//     and/or other materials provided with the distribution.
//
//   * The name of Intel Corporation may not be used to endorse or promote products
//     derived from this software without specific prior written permission.
//
// This software is provided by the copyright holders and contributors "as is" and
// any express or implied warranties, including, but not limited to, the implied
// warranties of merchantability and fitness for a particular purpose are disclaimed.
// In no event shall the Intel Corporation or contributors be liable for any direct,
// indirect, incidental, special, exemplary, or consequential damages
// (including, but not limited to, procurement of substitute goods or services;
// loss of use, data, or profits; or business interruption) however caused
// and on any theory of liability, whether in contract, strict liability,
// or tort (including negligence or otherwise) arising in any way out of
// the use of this software, even if advised of the possibility of such damage.
//
//M*/

#include "_cvaux.h"

#if 0

#include <float.h>
#include <limits.h>
#include <stdio.h>


#include "_cvutils.h"
#include "_cvwrap.h"

/*typedef struct CvCliqueFinder
{   
    CvGraph* graph;
    int**    adj_matr;
    int N; //graph size

    // stacks, counters etc/
    int k; //stack size
    int* current_comp;
    int** All;
    
    int* ne;
    int* ce;
    int* fixp; //node with minimal disconnections
    int* nod;
    int* s; //for selected candidate
    int status;
    int best_score;

} CvCliqueFinder;
*/

#define GO 1
#define BACK 2
#define PEREBOR 3
#define NEXT PEREBOR
#define END 4


#define  CV_GET_ADJ_VTX( vertex, edge ) \
(                                       \
    assert(edge->vtx[0]==vertex||edge->vtx[1] == vertex ), \
    (edge->vtx[0] == vertex)?edge->vtx[1]:edge->vtx[0]     \
)


#define NUMBER( v ) ((v)->flags >> 1 )

void _MarkNodes( CvGraph* graph )
{
    //set number of vertices to their flags
    for( int i = 0; i < graph->total; i++ )
    {
        CvGraphVtx* ver = cvGetGraphVtx( graph, i );
        if( ver )
        {
            ver->flags = i<<1;
        }
    }  
}

void _FillAdjMatrix( CvGraph* graph, int** connected, int reverse )
{
    //assume all vertices are marked
    for( int i = 0; i < graph->total; i++ )
    {
        for( int j = 0; j < graph->total; j++ )
        {
            connected[i][j] = 0|reverse;
        } 
        //memset( connected[i], 0, sizeof(int)*graph->total );
        CvGraphVtx* ver = cvGetGraphVtx( graph, i );
        if( ver )
        {
            connected[i][i] = 1;
            for( CvGraphEdge* e = ver->first; e ; e = CV_NEXT_GRAPH_EDGE( e, ver ) )
            {
               CvGraphVtx* v = CV_GET_ADJ_VTX( ver, e );
               connected[i][NUMBER(v)] = 1^reverse;
            }
        }
    }
}


void cvStartFindCliques( CvGraph* graph, CvCliqueFinder* finder, int reverse, int weighted, int weighted_edges )
{
    int i;

    if (weighted)
    {
        finder->weighted = 1;
        finder->best_weight = 0;
        finder->vertex_weights = (float*)malloc( sizeof(float)*(graph->total+1));
        finder->cur_weight = (float*)malloc( sizeof(float)*(graph->total+1));
        finder->cand_weight = (float*)malloc( sizeof(float)*(graph->total+1));

        finder->cur_weight[0] = 0;
        finder->cand_weight[0] = 0;
        for( i = 0 ; i < graph->total; i++ )
        {
            CvGraphWeightedVtx* ver = (CvGraphWeightedVtx*)cvGetGraphVtx( graph, i );
            assert(ver);
            assert(ver->weight>=0);
            finder->vertex_weights[i] = ver->weight;
            finder->cand_weight[0] += ver->weight;             
        }
    }
    else finder->weighted = 0;

    if (weighted_edges)
    {
        finder->weighted_edges = 1;
        //finder->best_weight = 0;
        finder->edge_weights = (float*)malloc( sizeof(float)*(graph->total)*(graph->total));
        //finder->cur_weight = (float*)malloc( sizeof(float)*(graph->total+1));
        //finder->cand_weight = (float*)malloc( sizeof(float)*(graph->total+1));

        //finder->cur_weight[0] = 0;
        //finder->cand_weight[0] = 0;
        memset( finder->edge_weights, 0, sizeof(float)*(graph->total)*(graph->total) );
        for( i = 0 ; i < graph->total; i++ )
        {
            CvGraphVtx* ver1 = cvGetGraphVtx( graph, i );
            if(!ver1) continue;
            for( int j = i ; j < graph->total; j++ )
            {
                CvGraphVtx* ver2 = cvGetGraphVtx( graph, j );
                if(!ver2) continue;
                CvGraphEdge* edge = cvFindGraphEdgeByPtr( graph, ver1, ver2 );
                if( edge )
                {
                    assert( ((CvGraphWeightedEdge*)edge)->weight >= 0 );
                    finder->edge_weights[ i * graph->total + j ] = 
                    finder->edge_weights[ j * graph->total + i ] = ((CvGraphWeightedEdge*)edge)->weight;
                }
            }
        }        
    }
    else finder->weighted_edges = 0;
                               

    //int* Compsub; //current component (vertex stack)
    finder->k = 0; //counter of steps
    int N = finder->N = graph->total;
    finder->current_comp = new int[N];
    finder->All = new int*[N];
    for( i = 0 ; i < finder->N; i++ )
    {
        finder->All[i] = new int[N];
    }

    finder->ne = new int[N+1];
    finder->ce = new int[N+1];
    finder->fixp = new int[N+1]; //node with minimal disconnections
    finder->nod = new int[N+1];
    finder->s = new int[N+1]; //for selected candidate
    
    //form adj matrix
    finder->adj_matr = new int*[N]; //assume filled with 0
    for( i = 0 ; i < N; i++ )
    {
        finder->adj_matr[i] = new int[N];
    }

    //set number to vertices
    _MarkNodes( graph );
    _FillAdjMatrix( graph, finder->adj_matr, reverse );

    //init all arrays
    int k = finder->k = 0; //stack size
    memset( finder->All[k], 0, sizeof(int) * N );
    for( i = 0; i < N; i++ )  finder->All[k][i] = i;
    finder->ne[0] = 0;
    finder->ce[0] = N;

    finder->status = GO;
    finder->best_score = 0;

}   

void cvEndFindCliques( CvCliqueFinder* finder )
{
    int i;
    
    //int* Compsub; //current component (vertex stack)
    delete finder->current_comp;
    for( i = 0 ; i < finder->N; i++ )
    {
        delete finder->All[i];
    }
    delete finder->All;
    
    delete finder->ne;
    delete finder->ce;
    delete finder->fixp; //node with minimal disconnections
    delete finder->nod;
    delete finder->s; //for selected candidate
    
    //delete adj matrix
    for( i = 0 ; i < finder->N; i++ )
    {
        delete finder->adj_matr[i];
    }  
    delete finder->adj_matr;
    
    if(finder->weighted)
    {
        free(finder->vertex_weights);
        free(finder->cur_weight);
        free(finder->cand_weight); 
    }
    if(finder->weighted_edges)
    {
        free(finder->edge_weights);
    }
}

int cvFindNextMaximalClique( CvCliqueFinder* finder ) 
{
    int**  connected = finder->adj_matr;
//    int N = finder->N; //graph size

    // stacks, counters etc/
    int k = finder->k; //stack size
    int* Compsub = finder->current_comp;
    int** All = finder->All;
    
    int* ne = finder->ne;
    int* ce = finder->ce;
    int* fixp = finder->fixp; //node with minimal disconnections
    int* nod = finder->nod;
    int* s = finder->s; //for selected candidate   
    
    //START
    while( k >= 0)
    {
        int* old = All[k];
        switch(finder->status)
        {    
        case GO://Forward step
        /* we have all sets and will choose fixed point */ 
            {   
                //check potential size of clique
                if( (!finder->weighted) && (k + ce[k] - ne[k] < finder->best_score) ) 
                {
                    finder->status  = BACK;
                    break;
                } 
                //check potential weight
                if( finder->weighted && !finder->weighted_edges &&
                    finder->cur_weight[k] + finder->cand_weight[k] < finder->best_weight )
                {
                    finder->status  = BACK;
                    break;
                }

                int minnod = ce[k];
                nod[k] = 0;

                //for every vertex of All determine counter value and choose minimum
                for( int i = 0; i < ce[k] && minnod != 0; i++) 
                {   
                    int p = old[i]; //current point
                    int count = 0;  //counter
                    int pos = 0;

                    /* Count disconnections with candidates */
                    for (int j = ne[k]; j < ce[k] && (count < minnod); j++) 
                    {
                        if ( !connected[p][old[j]] ) 
                        {
                            count++;
                            /* Save position of potential candidate */
                            pos = j;
                        }
                    }
                    
                    /* Test new minimum */
                    if (count < minnod) 
                    {
                        fixp[k] = p;     //set current point as fixed
                        minnod = count;  //new value for minnod
                        if (i < ne[k])      //if current fixed point belongs to 'not'
                        {
                            s[k] = pos;     //s - selected candidate
                        } 
                        else 
                        {
                            s[k] = i;        //selected candidate is fixed point itself
                            /* preincr */
                            nod[k] = 1;      //nod is aux variable, 1 means fixp == s
                        }
                    }
                }//for

                nod[k] = minnod + nod[k];
                finder->status = NEXT;//go to backtrackcycle 
            }
            break;
        case NEXT:
            //here we will look for candidate to translate into not    
            //s[k] now contains index of choosen candidate
            {
                int* new_ = All[k+1];
                if( nod[k] != 0 )
                {
                    //swap selected and first candidate
                    int i, p = old[s[k]];
                    old[s[k]] = old[ne[k]];
                    int sel = old[ne[k]] = p;

                    int newne = 0;
                    //fill new set 'not'
                    for ( i = 0; i < ne[k]; i++) 
                    {
                        if (connected[sel][old[i]]) 
                        {
                            new_[newne] = old[i];
                            newne++;
                            
                        }
                    }
                    //fill new set 'candidate'
                    int newce = newne;
                    i++;//skip selected candidate
                    
                    float candweight = 0;
                    
                    for (; i < ce[k]; i++) 
                    {
                        if (connected[sel][old[i]]) 
                        {
                            new_[newce] = old[i];
                            
                            if( finder->weighted ) 
                                candweight += finder->vertex_weights[old[i]];                            
                            
                            newce++; 
                        }
                    }

                    nod[k]--;

                    //add selected to stack 
                    Compsub[k] = sel;

                    k++;
                    assert( k <= finder->N );
                    if( finder->weighted )
                    {
                        //update weights of current clique and candidates
                        finder->cur_weight[k] = finder->cur_weight[k-1] + finder->vertex_weights[sel]; 
                        finder->cand_weight[k] = candweight;
                    }       
                    if( finder->weighted_edges )
                    {
                        //update total weight by edge weights
                        float added = 0;
                        for( int ind = 0; ind < k-1; ind++ )
                        {
                            added += finder->edge_weights[ Compsub[ind] * finder->N + sel ];
                        }
                        finder->cur_weight[k] += added;
                    }                    
                                        
                    //check if 'not' and 'cand' are both empty
                    if( newce == 0 )
                    {
                        finder->best_score = MAX(finder->best_score, k );

                        if( finder->weighted )
                            finder->best_weight = MAX( finder->best_weight, finder->cur_weight[k] );
                        /*FILE* file  = fopen("cliques.txt", "a" );

                        for (int t=0; t<k; t++)
                        {
                          fprintf(file, "%d ", Compsub[t]);
                        }
                        fprintf(file, "\n");

                        fclose(file);
                        */
                        
                        //output new clique//************************
                        finder->status = BACK;
                        finder->k = k;

                        return CLIQUE_FOUND;

                    }
                    else //check nonempty set of candidates
                    if( newne < newce )
                    {
                        //go further
                        ne[k] = newne;
                        ce[k] = newce;
                        finder->status  = GO;
                        break;
                    }
                    
                }
                else 
                    finder->status  = BACK;

            }
            break;

        case BACK:
            {         
                //decrease stack
                k--;         
                old = All[k];
                if( k < 0 ) break;

                //add to not
                ne[k]++;

                if( nod[k] > 0 )
                {
                    //select next candidate
                    for( s[k] = ne[k]; s[k] < ce[k]; s[k]++ )
                    {
                        if( !connected[fixp[k]][old[s[k]]])
                            break;
                    }
                    assert( s[k] < ce[k] );
                    finder->status = NEXT;
                }
                else
                    finder->status = BACK;

            }
            break;
        case END: assert(0);       

        }
    }//end while

    finder->status = END;
    return CLIQUE_END;
}


                                     

void cvBronKerbosch( CvGraph* graph )
{
    int* Compsub; //current component (vertex stack)
    int k = 0; //counter of steps
    int N = graph->total;
    int i;
    Compsub = new int[N];
    int** All = new int*[N];
    for( i = 0 ; i < N; i++ )
    {
        All[i] = new int[N];
    }

    int* ne = new int[N];
    int* ce = new int[N];
    int* fixp = new int[N]; //node with minimal disconnections
    int* nod = new int[N];
    int* s = new int[N]; //for selected candidate
    
    //form adj matrix
    int** connected = new int*[N]; //assume filled with 0
    for( i = 0 ; i < N; i++ )
    {
        connected[i] = new int[N];
    }



    //set number to vertices
    _MarkNodes( graph );
    _FillAdjMatrix( graph, connected, 0 );

    //init all arrays
    k = 0; //stack size
    memset( All[k], 0, sizeof(int) * N );
    for( i = 0; i < N; i++ )  All[k][i] = i;
    ne[0] = 0;
    ce[0] = N;

    int status = GO;
    int best_score = 0;

    //START
    while( k >= 0)
    {
        int* old = All[k];
        switch(status)
        {    
        case GO://Forward step
        /* we have all sets and will choose fixed point */ 
            {   

                if( k + ce[k] - ne[k] < best_score ) 
                {
                    status  = BACK;
                    break;
                } 

                int minnod = ce[k];
                nod[k] = 0;

                //for every vertex of All determine counter value and choose minimum
                for( int i = 0; i < ce[k] && minnod != 0; i++) 
                {   
                    int p = old[i]; //current point
                    int count = 0;  //counter
                    int pos = 0;

                    /* Count disconnections with candidates */
                    for (int j = ne[k]; j < ce[k] && (count < minnod); j++) 
                    {
                        if ( !connected[p][old[j]] ) 
                        {
                            count++;
                            /* Save position of potential candidate */
                            pos = j;
                        }
                    }
                    
                    /* Test new minimum */
                    if (count < minnod) 
                    {
                        fixp[k] = p;     //set current point as fixed
                        minnod = count;  //new value for minnod
                        if (i < ne[k])      //if current fixed point belongs to 'not'
                        {
                            s[k] = pos;     //s - selected candidate
                        } 
                        else 
                        {
                            s[k] = i;        //selected candidate is fixed point itself
                            /* preincr */
                            nod[k] = 1;      //nod is aux variable, 1 means fixp == s
                        }
                    }
                }//for

                nod[k] = minnod + nod[k];
                status = NEXT;//go to backtrackcycle 
            }
            break;
        case NEXT:
            //here we will look for candidate to translate into not    
            //s[k] now contains index of choosen candidate
            {
                int* new_ = All[k+1];
                if( nod[k] != 0 )
                {
                    //swap selected and first candidate
                    int p = old[s[k]];
                    old[s[k]] = old[ne[k]];
                    int sel = old[ne[k]] = p;

                    int newne = 0;
                    //fill new set 'not'
                    for ( i = 0; i < ne[k]; i++) 
                    {
                        if (connected[sel][old[i]]) 
                        {
                            new_[newne] = old[i];
                            newne++;
                            
                        }
                    }
                    //fill new set 'candidate'
                    int newce = newne;
                    i++;//skip selected candidate
                    for (; i < ce[k]; i++) 
                    {
                        if (connected[sel][old[i]]) 
                        {
                            new_[newce] = old[i];
                            newce++;
                        }
                    }

                    nod[k]--;

                    //add selected to stack 
                    Compsub[k] = sel;
                    k++;

                    //check if 'not' and 'cand' are both empty
                    if( newce == 0 )
                    {
                        best_score = MAX(best_score, k );

                        FILE* file  = fopen("cliques.txt", "a" );

                        for (int t=0; t<k; t++)
                        {
                          fprintf(file, "%d ", Compsub[t]);
                        }
                        fprintf(file, "\n");

                        fclose(file);

                        /*for( int t = 0; t < k; t++ )
                        {
                            printf("%d ", Compsub[t] );
                        }
                        printf("\n"); */

                        //printf("found %d\n", k);

                        //output new clique//************************
                        status = BACK;
                    }
                    else //check nonempty set of candidates
                    if( newne < newce )
                    {
                        //go further
                        ne[k] = newne;
                        ce[k] = newce;
                        status  = GO;
                        break;
                    }
                    
                }
                else 
                    status  = BACK;

            }
            break;

        case BACK:
            {         
                //decrease stack
                k--;         
                old = All[k];
                if( k < 0 ) break;

                //add to not
                ne[k]++;

                if( nod[k] > 0 )
                {
                    //select next candidate
                    for( s[k] = ne[k]; s[k] < ce[k]; s[k]++ )
                    {
                        if( !connected[fixp[k]][old[s[k]]])
                            break;
                    }
                    assert( s[k] < ce[k] );
                    status = NEXT;
                }
                else
                    status = BACK;

            }
            break;
       

        }
    }//end while

}//end cvBronKerbosch

#endif