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