ネットワークのランダム化

ネットワークのランダム化1

#include<stdio.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<sstream>
#include<fstream>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<mt.h>

int f_label(int i){
	return (int)log2((double)i);	

}


int main(){

	using namespace std;
	FILE *fp;
	
	std::string index;
	std::string str;
	std::string str2;		    
	std::map<std::string,int> outdegree;
	std::map<std::string,int> indegree;

	std::map<std::string,int> label_out;
	std::map<std::string,int> label_in;

	std::map<std::string,std::set<std::string> > adjency_list;
	std::map<std::string,std::set<std::string> > adjency_list_in;
	std::map<std::pair<int,int>,int> aij;
	std::pair<int,int> k12;
	std::map<int,int> out_num;
	std::map<int,int> in_num;
	std::set<std::string> nodelist;
	std::vector<string> in1;
	std::vector<string> out1;    
	int retuno=0;
	int nodeno;
	int e1;
	int e2;
	string tmp;
	
		
	std::ifstream ifs("test.net");
	//init_genrand(2);	
	
	init_genrand(3);	
	while(ifs && getline(ifs,str)){


		str=strtok(const_cast<char*>(str.c_str())," ");

		str2=(strtok(NULL," "));


		outdegree[str]=outdegree[str]+1;

		indegree[str2]=indegree[str2]+1;
		adjency_list[str].insert(str2);
		
		adjency_list_in[str2].insert(str);

		nodelist.insert(str);
		nodelist.insert(str2);
		out1.push_back(str)	;
		in1.push_back(str2);
		retuno++;
		//cout << retuno<<endl;
	}
	
	nodeno=nodelist.size();
	

	int t;
	int flg;
	string in1_node;
	string in2_node;
	string out1_node;
	string out2_node;	
	cout<<retuno <<"\n";
	for(t=0;t<100*retuno;t++){
		e1=0;
		e2=0;
		flg=1;	
		while(flg==1){
			flg=0;
			e1=genrand_int31()%retuno;	
			e2=genrand_int31()%retuno;

			if(e1==e2){

				flg=1;
			}	
			
			out1_node=out1[e1];
			out2_node=out1[e2];
			in1_node=in1[e1];
			in2_node=in1[e2];
			//cout <<"s" << out1_node <<" "<<out2_node<<" "<<in1_node<<" "<<in2_node<<endl;

			if(out1_node==in2_node){
				flg=1;
			}

			
			if(out2_node==in1_node){
				flg=1;
			}
			
			if(adjency_list[out1_node].find(in2_node)!=adjency_list[out1_node].end()){
				flg=1;
				//cout <<"test" <<out1_node << " " << in2_node <<endl;

			}
			 //*(adjency_list[out2_node].find(in1_node)) ;

			if(adjency_list[out2_node].find(in1_node)!=adjency_list[out2_node].end()){
				flg=1;

//				cout << out2_node << " " << in1_node <<endl;


			}
/*
			if(adjency_list_in[in1_node].find(out2_node)!=adjency_list_in[in1_node].end()){
				flg=1;

//				cout << out2_node << " " << in1_node <<endl;
			}

			if(adjency_list_in[in2_node].find(out1_node)!=adjency_list_in[in2_node].end()){
				flg=1;

//				cout << out1_node << " " << in2_node <<endl;
			}

*/




		}





		adjency_list[out1_node].erase(in1_node);
		adjency_list[out2_node].erase(in2_node);

		adjency_list[out1_node].insert(in2_node);
		adjency_list[out2_node].insert(in1_node);



		
		tmp=in1[e1];
		in1[e1]=in1[e2];
		in1[e2]=tmp;

		
	}
	
		
	for(int i=0;i<retuno;i++){
		cout << out1[i] <<" " << in1[i] << endl;

	}
	
	
}

#include<stdio.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<sstream>
#include<fstream>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<gsl/gsl_rng.h>
#include<gsl/gsl_randist.h>

int f_label(int i){
	return (int)log2((double)i);	

}


int main(){

	using namespace std;
	FILE *fp;
	const gsl_rng_type *T;
	gsl_rng *r;
	int t;
	//gsl_rng_setup();
	T=gsl_rng_default;
	r=gsl_rng_alloc(T);
	gsl_rng_set(r,2);	
	std::string index;
	std::string str;
	std::string str2;		    
	std::string out1_node;
	std::string in1_node;
	std::string out2_node;
	std::string in2_node;
	std::map<std::string,int> outdegree;
	std::map<std::string,int> indegree;

	std::map<std::string,int> label_out;
	std::map<std::string,int> label_in;

	std::map<std::string,int> edge_count;

	std::map<std::string,int> edge_name;
	std::map<std::string,std::set<std::string> > adjency_list;
	std::map<std::string,std::set<std::string> > adjency_list_in;

	std::map<std::string,std::set<std::string> > adjency_listb;
	std::map<std::string,std::set<std::string> > adjency_list_inb;
	std::map<std::pair<int,int>,int> aij;
	std::pair<int,int> k12;
	std::map<int,int> out_num;
	std::map<int,int> in_num;
	std::set<std::string> nodelist;
	std::vector<string> in1;
	std::vector<string> out1;

	std::vector<int> self_loop;

	std::vector<int> du_edge;
	std::vector<std::string> in1b;
	std::vector<std::string> out1b;    
	int retuno=0;
	int nodeno;
	int e1;
	int e2;
	int i,flg;
	string tmp;
	

	std::ifstream ifs("test.net");
	
	while(ifs && getline(ifs,str)){


		str=strtok(const_cast<char*>(str.c_str())," ");

		str2=(strtok(NULL," "));


		outdegree[str]=outdegree[str]+1;

		indegree[str2]=indegree[str2]+1;
		adjency_list[str].insert(str2);
		
		adjency_list_in[str2].insert(str);

		nodelist.insert(str);
		nodelist.insert(str2);
		out1.push_back(str)	;
		in1.push_back(str2);
		retuno++;
		//cout << retuno<<endl;
	}
		
	indexlist=(int*)calloc(retuno,sizeof(int));	
	for(i=0;i<retuno;i++){

		indexlist[i]=i;
	}
	//cout <<retuno << endl;
	nodeno=nodelist.size();
	gsl_ran_shuffle(r,indexlist,retuno,sizeof(int));
	
	for(i=0;i<retuno;i++){

		//printf("%d\n",indexlist[i]);
	}

	for(i=0;i<retuno;i++){

		adjency_listb[out1[i]].insert(in1[indexlist[i]]);
		
		adjency_list_inb[in1[indexlist[i]]].insert(out1[i]);
		in1b.push_back(in1[indexlist[i]]);
		
		out1b.push_back(out1[i]);
	}
	int self1=1;	
	int du=1;
	int j=0;

		
	map<string,int>::iterator it;
	while(self1!=0 && du !=0){
		self1=0;
		du=0;
		//cout << j << endl ;		
		//du_edge.clear();
		//self_loop.clear();

		//edge_count.clear();
		//edge_name.clear();
		for(i=0;i<retuno;i++){
			
			edge_count[in1b[i]+"a"+out1b[i]]=0;

			edge_name[in1b[i]+"a"+out1b[i]]=0;
		

		}

		//cout << "a" <<endl;

		//cout << "b" <<endl;
		
	for(i=0;i<retuno;i++){

		//adjency_listb[out1[i]].insert(in1[indexlist[i]]);
		
		//adjency_list_inb[in1[indexlist[i]]].insert(out1[i]);
		//in1b.push_back(in1[indexlist[i]]);
		
		//out1b.push_back(out1[i]);
		edge_count[in1b[i]+"a"+out1b[i]]=edge_count[in1b[i]+"a"+out1b[i]]+1;

		edge_name[in1b[i]+"a"+out1b[i]]=i;
		
		if(out1b[i]==in1b[i]){
			self_loop.push_back(i);
			++self1;
		}
				
	}
	//cout << "c" << endl;		
	it=edge_count.begin();
	while(it!=edge_count.end()){
		//cout << it->first <<" " << it->second <<endl;	
		
		if(it->second!=1){
			//cout << it->first << endl;
			du_edge.push_back(edge_name[it->first]);
			++du;
		}
			
		++it;
	}

		

	//cout << "d" << endl;
		
	for(t=0;t<du;t++){
		e1=0;
		e2=0;
		flg=1;	

		e1=du_edge.back();
		(du_edge).pop_back();	
		while(flg==1){
			flg=0;
			
			//e1=du_edge.back();
			//(du_edge).pop_back();	
			
			e2=gsl_rng_uniform_int(r,retuno);
			
			if(e1==e2){

				flg=1;
			}	
			
			out1_node=out1b[e1];
			out2_node=out1b[e2];
			in1_node=in1b[e1];
			in2_node=in1b[e2];

			if(out1_node==in2_node){
				flg=1;
			}

			
			if(out2_node==in1_node){
				flg=1;
			}
			
			if(adjency_listb[out1_node].find(in2_node)!=adjency_listb[out1_node].end()){
				flg=1;

			}

			if(adjency_listb[out2_node].find(in1_node)!=adjency_listb[out2_node].end()){
				flg=1;



			}

			if(adjency_list_in[in2_node].find(out1_node)!=adjency_list_in[in2_node].end()){
				flg=1;

			}






		}


		adjency_listb[out1_node].erase(in1_node);
		adjency_listb[out2_node].erase(in2_node);

		adjency_listb[out1_node].insert(in2_node);
		adjency_listb[out2_node].insert(in1_node);



		
		tmp=in1b[e1];
		in1b[e1]=in1b[e2];
		in1b[e2]=tmp;

		
	}

	//cout << "e" << endl;
	for(t=0;t<self1;t++){
		//cout << "e" << t << endl;
		e1=0;
		e2=0;
		flg=1;	

		e1=self_loop.back();
		(self_loop).pop_back();	
		while(flg==1){
			flg=0;
			//e1=self_loop.back();
			//(self_loop).pop_back();	
			e2=gsl_rng_uniform_int(r,retuno);
			
			if(e1==e2){

				flg=1;
			}	
			
			out1_node=out1b[e1];
			out2_node=out1b[e2];
			in1_node=in1b[e1];
			in2_node=in1b[e2];

			if(out1_node==in2_node){
				flg=1;
			}

			
			if(out2_node==in1_node){
				flg=1;
			}
			
			if(adjency_listb[out1_node].find(in2_node)!=adjency_listb[out1_node].end()){
				flg=1;

			}

			if(adjency_listb[out2_node].find(in1_node)!=adjency_listb[out2_node].end()){
				flg=1;



			}

			if(adjency_list_in[in2_node].find(out1_node)!=adjency_list_in[in2_node].end()){
				flg=1;

			}






		}





		adjency_listb[out1_node].erase(in1_node);
		adjency_listb[out2_node].erase(in2_node);

		adjency_listb[out1_node].insert(in2_node);
		adjency_listb[out2_node].insert(in1_node);



		
		tmp=in1b[e1];
		in1b[e1]=in1b[e2];
		in1b[e2]=tmp;

		
			



	}
	
	//cout << "f" << endl;
	j++;
	//cout << j << endl;	

	
	
	}		

	for(int i=0;i<retuno;i++){
		cout << out1b[i] <<" " << in1b[i] << endl;

	}
	
	

	
}

ネットワークのランダム化２

#include<stdio.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<sstream>
#include<fstream>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<gsl/gsl_rng.h>
#include<gsl/gsl_randist.h>

int f_label(int i){
	return (int)log2((double)i);	

}


int main(){

	using namespace std;
	FILE *fp;
	const gsl_rng_type *T;
	gsl_rng *r;
	int t;
	//gsl_rng_setup();
	T=gsl_rng_default;
	r=gsl_rng_alloc(T);
	gsl_rng_set(r,5);	
	std::string index;
	std::string str;
	std::string str2;		    
	std::string out1_node;
	std::string in1_node;
	std::string out2_node;
	std::string in2_node;
	std::map<std::string,int> outdegree;
	std::map<std::string,int> indegree;

	std::map<std::string,int> label_out;
	std::map<std::string,int> label_in;

	std::map<std::string,int> edge_count;

	std::map<std::string,int> edge_name;
	std::map<std::string,std::set<std::string> > adjency_list;
	std::map<std::string,std::set<std::string> > adjency_list_in;

	std::map<std::string,std::set<std::string> > adjency_listb;
	std::map<std::string,std::set<std::string> > adjency_list_inb;
	std::map<std::pair<int,int>,int> aij;
	std::pair<int,int> k12;
	std::map<int,int> out_num;
	std::map<int,int> in_num;
	std::set<std::string> nodelist;
	std::vector<string> in1;
	std::vector<string> out1;

	std::vector<int> self_loop;

	std::vector<int> du_edge;
	std::vector<std::string> in1b;
	std::vector<std::string> out1b;    
	int retuno=0;
	int nodeno;
	int e1;
	int e2;
	int i,flg,self1,du;
	string tmp;
	
	std::ifstream ifs("test.net");
	
	int *indexlist;
	//init_genrand(2);	
	
	//init_genrand(3);	
	while(ifs && getline(ifs,str)){


		str=strtok(const_cast<char*>(str.c_str())," ");

		str2=(strtok(NULL," "));


		outdegree[str]=outdegree[str]+1;

		indegree[str2]=indegree[str2]+1;
		adjency_list[str].insert(str2);
		
		adjency_list_in[str2].insert(str);

		nodelist.insert(str);
		nodelist.insert(str2);
		out1.push_back(str)	;
		in1.push_back(str2);
		retuno++;
		//cout << retuno<<endl;
	}
		
	indexlist=(int*)calloc(retuno,sizeof(int));	
	for(i=0;i<retuno;i++){

		indexlist[i]=i;
	}
	//cout <<retuno << endl;
	nodeno=nodelist.size();
	gsl_ran_shuffle(r,indexlist,retuno,sizeof(int));
	
	for(i=0;i<retuno;i++){

		//printf("%d\n",indexlist[i]);
	}

	for(i=0;i<retuno;i++){

		adjency_listb[out1[i]].insert(in1[indexlist[i]]);
		
		adjency_list_inb[in1[indexlist[i]]].insert(out1[i]);
		in1b.push_back(in1[indexlist[i]]);
		
		out1b.push_back(out1[i]);
	}
	self1=0;	
	du=0;

	for(i=0;i<retuno;i++){

		edge_count[in1b[i]+"a"+out1b[i]]=edge_count[in1b[i]+"a"+out1b[i]]+1;

		edge_name[in1b[i]+"a"+out1b[i]]=i;
		
		if(out1b[i]==in1b[i]){
			self_loop.push_back(i);
			++self1;
			//cout <<"c" << self1 << endl;
		}
				
	}
		
	map<string,int>::iterator it;
	it=edge_count.begin();
	while(it!=edge_count.end()){
		//cout << it->first <<" " << it->second <<endl;	
		
		if(it->second!=1){
			//cout << it->first << endl;
			du_edge.push_back(edge_name[it->first]);
			++du;
		}
			
		++it;
	}
	while(self1!=0 || du !=0){
		//self1=0;
		//du=0;
		//cout << j << endl ;		
		//du_edge.clear();
		//self_loop.clear();

		//edge_count.clear();
		//edge_name.clear();

		//cout << "a" <<endl;

		//cout << "b" <<endl;
		
	//cout << "c" << endl;		

		

	//cout << "d" << endl;
		
	for(t=0;t<du;t++){
		e1=0;
		e2=0;
		flg=1;	

		e1=du_edge.back();
		(du_edge).pop_back();
		
		//cout <<"b"<<e1 <<endl; 
		while(flg==1){
			flg=0;
			
			//e1=du_edge.back();
			//(du_edge).pop_back();	
			
			e2=gsl_rng_uniform_int(r,retuno);
			
			if(e1==e2){

				flg=1;
			}	
			
			out1_node=out1b[e1];
			out2_node=out1b[e2];
			in1_node=in1b[e1];
			in2_node=in1b[e2];

			if(out1_node==in2_node){
				flg=1;
			}

			
			if(out2_node==in1_node){
				flg=1;
			}
			
			if(adjency_listb[out1_node].find(in2_node)!=adjency_listb[out1_node].end()){
				flg=1;

			}

			if(adjency_listb[out2_node].find(in1_node)!=adjency_listb[out2_node].end()){
				flg=1;



			}

//			if(adjency_list_in[in2_node].find(out1_node)!=adjency_list_in[in2_node].end()){
//				flg=1;
//
//			}






		}


		adjency_listb[out1_node].erase(in1_node);
		adjency_listb[out2_node].erase(in2_node);

		adjency_listb[out1_node].insert(in2_node);
		adjency_listb[out2_node].insert(in1_node);



		
		tmp=in1b[e1];
		in1b[e1]=in1b[e2];
		in1b[e2]=tmp;

		
	}

	//cout << "e" << endl;
	for(t=0;t<self1;t++){
		//cout << "e" << t << endl;
		e1=0;
		e2=0;
		flg=1;	

		e1=self_loop.back();
		(self_loop).pop_back();	
		while(flg==1){
			flg=0;
			//e1=self_loop.back();
			//(self_loop).pop_back();	
			e2=gsl_rng_uniform_int(r,retuno);
			//cout << e2 << endl;		
			if(e1==e2){

				flg=1;
			}	
			
			out1_node=out1b[e1];
			out2_node=out1b[e2];
			in1_node=in1b[e1];
			in2_node=in1b[e2];

			if(out1_node==in2_node){
				flg=1;
			}

			
			if(out2_node==in1_node){
				flg=1;
			}
			
			if(adjency_listb[out1_node].find(in2_node)!=adjency_listb[out1_node].end()){
				flg=1;

			}

			if(adjency_listb[out2_node].find(in1_node)!=adjency_listb[out2_node].end()){
				flg=1;



			}
/*
					if(adjency_list_in[in2_node].find(out1_node)!=adjency_list_in[in2_node].end()){
				flg=1;

			}
*/





		}





		adjency_listb[out1_node].erase(in1_node);
		adjency_listb[out2_node].erase(in2_node);

		adjency_listb[out1_node].insert(in2_node);
		adjency_listb[out2_node].insert(in1_node);



		
		tmp=in1b[e1];
		in1b[e1]=in1b[e2];
		in1b[e2]=tmp;

		
			



	}
	
	//cout << "f" << endl;
	//j++;
	//cout << j << endl;	

	self1=0;
	du=0;
	//for(i=0;i<retuno;i++){
			
	//	edge_count[in1b[i]+"a"+out1b[i]]=0;

	//	edge_name[in1b[i]+"a"+out1b[i]]=0;
		

	//}
	edge_count.clear();
	edge_name.clear();
	
	for(i=0;i<retuno;i++){

		edge_count[in1b[i]+"a"+out1b[i]]=edge_count[in1b[i]+"a"+out1b[i]]+1;

		edge_name[in1b[i]+"a"+out1b[i]]=i;
		//cout <<"d" << out1b[i] << "  " << in1b[i]	<< endl;
		if(out1b[i]==in1b[i]){
			self_loop.push_back(i);
			++self1;
			//cout <<"kazoel" << endl;
		}
				
	}

	it=edge_count.begin();
	while(it!=edge_count.end()){
		//cout << it->first <<" " << it->second <<endl;	
		
		if(it->second!=1){
			//cout << it->first << " " << it->second << endl;
			du_edge.push_back(edge_name[it->first]);
			++du;
		}
			
		++it;
	}
		cout <<"a" <<self1 << " " << du<<endl;	
	}		

	for(int i=0;i<retuno;i++){
		cout << out1b[i] <<" " << in1b[i] << endl;

	}
	
	

	
}