moon_fractal_c_1.zip_Measuring_complex network_fractal dimension

#include <stdio.h> #include <stdlib.h> #include <string.h> #include "queue.h" #include <omp.h> #include <concurrent_vector.h> #include <ppl.h> #include <dm_library/data_processing.h> #include <boost/timer.hpp> #include <boost/progress.hpp> #include <dm_library/math/dmath.h> #include <boost/program_options.hpp> #include <queue> #include <dm_library/fractal/fractal_api.h> typedef struct { int *index; size_t len; } _node; typedef struct { _node *nodes; size_t len; } adj_list; void initlist(adj_list *list); void input_adjlist(adj_list *list,int **v,const int edge_num ); void addlist(adj_list *list, const int num); void addnode(_node *node, const int node_num); void print_list(adj_list *list); void load_list(const char *file_name, int **v); int check_max(const char *file_name); void search_bfs(const int start_node , const adj_list *list, int *v); void search_bfs_a(const size_t start_node , const adj_list *list, size_t *v); void gready_box(const adj_list *list , size_t **result_mat, std::vector<size_t> &select_nodes, const size_t max_path); void rs_box(const adj_list *list , size_t **result_mat, std::vector<size_t> &select_nodes, const size_t max_path); void MEMB(const adj_list *list , size_t **result_mat, std::vector<size_t> &select_nodes, const size_t max_path); void find_mat(size_t **mat, const size_t nx,const size_t ny, std::vector<dml::xy_data<size_t> > &out_data); void select_core_num(adj_list *list,std::vector<size_t> &select_nodes); void find_max_dist(const adj_list *list , const std::vector<size_t> &node, size_t &max_dist); bool check_list(const adj_list *list); void prim_mst(const adj_list *list, const size_t num_node, const size_t *nodes, size_t *result_edges, size_t *result_nodes ); struct parameter { int icpu; int mst_interval_num; int mst_repeat_num; std::string input_file; std::string select_nodes_file; std::string config_file; std::string out_result_data_file; std::string out_raw_data_file; std::string method; }; bool obtain_config_file_name(int argc, char *argv[], parameter &param); bool set_parameter(parameter &param); #define TEST_0 int main(int argc, char* argv[]) { //------------------------------------------------ srand((unsigned int)time(NULL)); //----------------------------------------------- parameter param; #ifndef TEST_0 if(obtain_config_file_name(argc,argv,param)==false) return false; if(set_parameter(param)==false) return false; #else param.method="MEMB"; param.icpu=7; param.input_file="cellular.dat"; param.out_result_data_file="cellular+box.txt"; param.out_raw_data_file="cellular+box_raw.txt"; param.mst_interval_num=15; //param.select_nodes_file="core_celluar.txt"; #endif int icpu=param.icpu; //int ttt; int i,j; int **v; int edge_num; char file_name[256];//="cellular.dat"; char save_file_name[256]; size_t **mat; size_t max_path; FILE *iop; adj_list list; omp_set_num_threads(icpu); strcpy(file_name,param.input_file.c_str()); initlist(&list); edge_num=check_max(file_name); v=(int **)realloc(NULL,sizeof(int*)*(edge_num)); for(i=0;i<(edge_num);i++) v[i]=(int *)realloc(NULL,sizeof(int)*2); printf("Loading the input file......\n"); load_list(file_name,v); input_adjlist(&list,v,edge_num); printf("The number of edge :%d\n" ,edge_num); printf("The number of node :%d\n" ,list.len); if(check_list(&list)==false) return 0; for(i=0;i<(edge_num);i++) free(v[i]); free(v); //selecting nodes; std::vector<size_t> nodes; if(param.select_nodes_file.empty()) { nodes.resize(list.len); for(size_t i=0;i<nodes.size();i++) nodes[i]=i; } else { if(dml::load_data(param.select_nodes_file.c_str(),nodes)==false) { std::cout << "Cannot open file : " << param.select_nodes_file << std::endl; return 0; } if(nodes.size()<32) { std::cout << "The number of selected node must be larger than 32\n"; return 0; } size_t temp=nodes[0]; for(size_t i=1;i<nodes.size();i++) temp=std::max(temp,nodes[i]); if(temp>=list.len) { std::cout << "Check the number of node : " << temp << std::endl; return 0; } } //shuffling selected noise. //std::random_shuffle(nodes.begin(),nodes.end()); //MST-------------------------------------------------------- if(param.method==std::string("mst")) { printf("Caculating MST dimension......\n"); //shuffling srand((unsigned int)time(NULL)); std::random_shuffle(nodes.begin(),nodes.end()); dml::create_interval<size_t> interval; interval.set_min_max(32,nodes.size()); interval.set_num_parts(param.mst_interval_num); interval.caculate_log(); dml::create_interval<size_t>::type_data_interval data_interval=interval.get_data_interval(); std::vector<std::vector<size_t> > out_data(data_interval.size()); size_t *p; boost::timer ttimer; std::vector<dml::xy_data<double> > v_xy(data_interval.size()); auto fun=[&](const long int i) { dml::xy_data<double> t_xy; double ave=0; std::vector<double> t_ave(param.mst_repeat_num,0.0); if(data_interval[i]!=list.len) { #pragma omp parallel for schedule (static, 1) for(long int j=0;j<param.mst_repeat_num;j++) { if(j==0) { out_data[i].resize(data_interval[i]-1,0); prim_mst(&list,data_interval[i],nodes.data(), out_data[i].data(),p); dml::average(out_data[i].begin(),out_data[i].end(),t_ave[j]); } else { auto copy_nodes(nodes); std::random_shuffle(copy_nodes.begin(),copy_nodes.end()); std::vector<size_t> tout_data(data_interval[i]-1,0); prim_mst(&list,data_interval[i],copy_nodes.data(), tout_data.data(),p); dml::average(tout_data.begin(),tout_data.end(),t_ave[j]); } } dml::average(t_ave.begin(),t_ave.end(),ave); } else { out_data[i].resize(data_interval[i]-1,1); ave=1.0; } t_xy.x=(double)(data_interval[i]-1); t_xy.y=ave; printf("%d : %lf\n",(int)t_xy.x,t_xy.y); v_xy[i]=t_xy; }; //Concurrency::parallel_for((size_t)0,data_interval.size(),fun); //#pragma omp parallel for schedule (static, 1) for(long int i=0;i<data_interval.size();i++) fun(i); printf("elapsed time : %lf(s)\n",ttimer.elapsed()); //dml::dim_error<double> dim; //dml::fit_dim(v_xy, dim); //std:: cout << "dimension : "<< -1/dim.dim << "\n"; printf("Saving result....\n"); if((iop=fopen(param.out_result_data_file.c_str(),"w+"))==NULL) { printf("Cannot open file %s " ,save_file_name); return 0; } for(i=0;i<v_xy.size();i++) fprintf(iop,"%d %lf\n",(int)v_xy[i].x,v_xy[i].y); fclose(iop); if((iop=fopen(param.out_raw_data_file.c_str(),"w+"))==NULL) { printf("Cannot open file %s " ,save_file_name); return 0; } for(i=0;i<out_data.size();i++) { for(j=0;j<out_data[i].size();j++) fprintf(iop,"%d ",out_data[i][j]); fprintf(iop,"\n"); } fclose(iop); return 1; } //----------------------------------------------------------- //BOX-------------------------------------------------------- if(param.method==std::string("box")) { //find Maximum distance printf("Finding the maximum shortest path......\n"); find_max_dist(&list ,nodes, max_path); mat=(size_t **)realloc(NULL,sizeof(size_t*)*nodes.size()); for(i=0;i<nodes.size();i++) mat[i]=(size_t *)realloc(NULL,sizeof(size_t)*max_path); printf("Caculating box dimension......\n"); gready_box(&list,mat,nodes,max_path); std::vector<dml::xy_data<size_t> > out_data; find_mat(mat,nodes.size(),max_path,out_data); printf("Saving result....\n"); dml::save_data(param.out_result_data_file.c_str(),out_data);