X-Git-Url: https://vcs.maemo.org/git/?a=blobdiff_plain;f=src%2Fcvaux%2Fcvclique.cpp;fp=src%2Fcvaux%2Fcvclique.cpp;h=df7f8a947f11f2884c779e51b2c3a9f798d7b122;hb=e4c14cdbdf2fe805e79cd96ded236f57e7b89060;hp=0000000000000000000000000000000000000000;hpb=454138ff8a20f6edb9b65a910101403d8b520643;p=opencv diff --git a/src/cvaux/cvclique.cpp b/src/cvaux/cvclique.cpp new file mode 100644 index 0000000..df7f8a9 --- /dev/null +++ b/src/cvaux/cvclique.cpp @@ -0,0 +1,709 @@ +/*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 +#include +#include + + +#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; tstatus = 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 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 +