/*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