maxclique.cpp

传感器网络的可靠路由算法

// Clique.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>
#include "MaxClique.h"
#include <assert.h>
#include "link.h"

/* wclique.c exact algorithm for finding one maximum-weight 
   clique in an arbitrary graph,
   10.2.2000, Patric R. J. Ostergard, 
   [e-mail] */

/* compile: gcc wclique.c -o wclique -O2 */

/* usage: wclique infile */

/* infile format: see http://www.tcs.hut.fi/~pat/wclique.html */

#include <stdio.h>
#include <sys/types.h>
#include <stdlib.h>

#define INT_SIZE (8*sizeof(int))
#define TRUE 1
#define FALSE 0
#define MAX_VERTEX 2000 /* maximum number of vertices */
#define MAX_WEIGHT 1000000 /* maximum weight of vertex */


int gVnbr,gEnbr;          /* number of vertices/edges */
double clique[MAX_VERTEX]; /* table for pruning */
int bit[MAX_VERTEX][MAX_VERTEX/INT_SIZE+1];
double node_wt[MAX_VERTEX];

int pos[MAX_VERTEX];    /* reordering function */
int set[MAX_VERTEX];    /* current clique */
int rec[MAX_VERTEX];	/* best clique so far */
double record;		/* weight of best clique */
int rec_level;          /* # of vertices in best clique */

unsigned mask[INT_SIZE];
void graph(FILE* fp) ;           /* reads graph */

int sub(int ct, int* table, int level, double weight,double l_weight, double *wt);
int fileerror(int i);

int is_edge( int a,int b);

int NodeIDMap[MAX_VERTEX] ;
double Threshold;

#define LOCALIZATIN_ENABLEDno
#define COMPLEXITY_THRESHOLD  100

int FindMaxClique(int* cliqueNodes, double* weight, int count, double LQIThreshold){

#ifdef LOCALIZATIN_ENABLED
	return FastMaxClique();  //if the location is known in UDG, MaxClique can be found within ploynomial time.	 
#else
    if(count > COMPLEXITY_THRESHOLD){		
	 return HeuristicMaxClique(); //if the size of the forwarding candiates is large	
	}else{	
	 return MaxClique(cliqueNodes,weight,count,LQIThreshold); //Expoential MaxClique algorithm
	}
#endif
    
}


int FastMaxClique(){assert(false); return 0 ; } //to be done
int HeuristicMaxClique(){assert(false); return 0;}



/*
void main (int argc,char ** argv)
{
  FILE *infile;
  int cliqueNodes[MAX_VERTEX];
  int i;

  // read input 
  if(argc < 2) {   	
    printf("Usage: wclique infile\n");
    exit(1);
  }
  if((infile=fopen(argv[1],"r"))==NULL){
	printf("Opening %s\n", argv[1]);
    fileerror(0);
  }
  // initialize mask 
  mask[0] = 1;
  for(i=1;i<INT_SIZE;i++)
    mask[i] = mask[i-1]<<1;

  // read graph 
  graph(infile);  
  SlowMaxClique(cliqueNodes, node_wt,gVnbr,1.0);
}
*/

int MaxClique(int* cliqueNodes, double* wt, int _Vnbr, double LQIThreshold){
  
  int i,j,p;
  double min_wt,max_nwt,wth;
  int used[MAX_VERTEX];
  double nwt[MAX_VERTEX];
  int count;

  /* initialize mask */
  mask[0] = 1;
  for(i=1;i<INT_SIZE;i++)
    mask[i] = mask[i-1]<<1;

  /* for is_edge() function */
  Threshold = LQIThreshold;
  for(i=0;i<_Vnbr;i++) {
    NodeIDMap[i] = cliqueNodes[i];
  }

  /* order vertices */
  for(i=0;i<_Vnbr;i++) {
    nwt[i] = 0;
    for(j=0;j<_Vnbr;j++)
      if (is_edge(i,j)) nwt[i] += wt[j];
  }
  for(i=0;i<_Vnbr;i++)
    used[i] = FALSE;
  count = 0;
  do {
     min_wt = MAX_WEIGHT+1; max_nwt = -1; 
     for(i=_Vnbr-1;i>=0;i--)
       if((!used[i])&&(wt[i]<min_wt))
         min_wt = wt[i];
     for(i=_Vnbr-1;i>=0;i--) {
       if(used[i]||(wt[i]>min_wt)) continue;
       if(nwt[i]>max_nwt) {
         max_nwt = nwt[i];
         p = i;
       }
     }
     pos[count++] = p;
     used[p] = TRUE;
     for(j=0;j<_Vnbr;j++)
       if((!used[j])&&(j!=p)&&(is_edge(p,j)))
         nwt[j] -= wt[p];
  } while(count<_Vnbr);

  /* main routine */
  record = 1000;
  wth = 1;
  for(i=0;i<_Vnbr;i++) {
     wth *= wt[pos[i]]; //consider production instead of sum
     sub(i,pos,0,1,wth,wt);
     clique[pos[i]] = record;
     printf("level = %3d(%d) best = %2lf\n",i+1,_Vnbr,record);
  }

  for(i=0;i<rec_level;i++) {  
   cliqueNodes[i] = NodeIDMap[rec[i]];  
  }
  

  printf("Record: ");
  for(i=0;i<rec_level;i++) 
    printf ("%d ",rec[i]);
  printf ("\n");
  return rec_level;
}

int sub(int ct, int* table, int level, double weight,double l_weight, double* wt)

{
  register int i,j,k;
  double curr_weight,left_weight;
  int newtable[MAX_VERTEX];
  int *p1,*p2;

  if(ct<=0) { /* 0 or 1 elements left; include these */
    if(ct==0) { 
      set[level++] = table[0];
      weight *= l_weight;
    }
    if(weight < record) {
      record = weight;
      rec_level = level;
      for (i=0;i<level;i++) rec[i] = set[i];
    }
    return 0;
  }
  for(i=ct;i>=0;i--) {
    if((level==0)&&(i<ct)) return 0;
    k = table[i];
    if((level>0)&&(clique[k]>=(record/weight))) return 0;  /* prune */
    set[level] = k;
    curr_weight = weight*wt[k];
    l_weight /= wt[k];
    if(l_weight >=(record/curr_weight)) return 0; /* prune */
    p1 = newtable;
    p2 = table;
    left_weight = 1.0;   
    while (p2<table+i) { 
      j = *p2++;
      if(is_edge(j,k)) {
	 		*p1++ = j;
        left_weight *= wt[j];
      }
    }
    if(left_weight >=(record/curr_weight)) continue;
    sub(p1-newtable-1,newtable,level+1,curr_weight,left_weight,wt);
  }
  return 0;
}

void graph(FILE* fp) 
{
  register int i,j;
  double weight;
  int degree,entry;
 
  if(!fscanf(fp,"%d %d\n",&gVnbr,&gEnbr)){
    fileerror(1); 
  }
  for(i=0;i<gVnbr;i++)     /* empty graph table */
    for(j=0;j<gVnbr/(int)INT_SIZE+1;j++)
      bit[i][j] = 0;
  for(i=0;i<gVnbr;i++) {
    if(!fscanf(fp,"%lf %d",&weight,&degree))
      fileerror(2); 
    node_wt[i] = weight;
    for(j=0;j<degree;j++) {
      if(!fscanf(fp,"%d",&entry))
        fileerror(3);
      bit[i][entry/INT_SIZE] |= mask[entry%INT_SIZE]; /* record edge */
    }
  }
  fclose(fp);
}

int fileerror(int i)
{
  printf("Error in graph file %d\n",i);
  exit(-1);
}

int is_edge(int a,int b){

if( linkquality(NodeIDMap[a], NodeIDMap[b]) < Threshold) return false;
if( linkquality(NodeIDMap[b], NodeIDMap[a]) < Threshold) return false;
return true;

}


bool isClique(int* cliqueNodes, int count , double Threshold){
  
	if(count == 1) return true;

	for( int i = 0 ; i < count ; i++){
		for( int j = i+1 ; j < count ; j++){
		
			if( linkquality(cliqueNodes[i], cliqueNodes[j]) < Threshold ||
				linkquality(cliqueNodes[j], cliqueNodes[i]) < Threshold)
				return false;				
		}		
	}
	return true;
}