--- /dev/null
+/*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
+
projects / opencv / blobdiff