fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <bitset>
  4. #include <vector>
  5. #include <algorithm>
  6. #include "tbb/tick_count.h"
  7. #include "tbb/task_scheduler_init.h"
  8. #include "tbb/spin_rw_mutex.h" //todo:??????????
  9. #include "tbb/task.h"
  10. #define MAXN 500
  11.  
  12. using namespace std;
  13.  
  14. const size_t ADJSIZE = 26;
  15. const size_t GRAPHSIZE=500;
  16. int n_peptides = 0;
  17. const float low = -7.0, high = -8.5;
  18.  
  19. float score[MAXN][MAXN];
  20. vector< pair<int,int> >vertices;
  21.  
  22. // ??????????????????????(26????????)
  23. #define VALIDVEC(char0)    (char0>='A' && char0<='Z')
  24. #define MAKEVEC(char0,char1)	(size_t(char0-'A')*ADJSIZE+char1-'A')
  25. #define GETVECCHAR0(vec)		char(char(vec/ADJSIZE) + 'A')
  26. #define GETVECCHAR1(vec)		char(char(vec%ADJSIZE) + 'A')
  27.  
  28. typedef bitset<GRAPHSIZE> adj_t; //bitset
  29. typedef adj_t graph_t[GRAPHSIZE];//????????
  30.  
  31. struct vectex_ex_t{ //????????????
  32. 	size_t tag; // ??????????
  33. 	adj_t adj;  // ??????
  34. };
  35. typedef vector<vectex_ex_t> graph_ex_t;//??????????????????????????????
  36. // ????????????
  37. void graph2graphex(const graph_t &g, graph_ex_t& gex)
  38. {
  39.         //cout << vertices.size();
  40. 	for(size_t i=0; i<vertices.size(); i++){ //changed graph size
  41.             //cout << "any " << i << endl;
  42.             vectex_ex_t v={
  43.                     i, g[i]
  44.                     };
  45.             gex.push_back(v);
  46.         }
  47.  
  48.         /*for(size_t i =0;i<vertices.size();i++) {
  49.             cout << gex[i].tag << ": ";
  50.             for(size_t j=0;j<gex[i].adj.size();j++) {
  51.                 cout << gex[i].adj[j] << " ";
  52.             }
  53.             cout << endl;
  54.         }*/
  55. }
  56.  
  57. //??????????????
  58.  
  59. bool interaction(pair<int,int> a, pair<int,int> b) {
  60.     if(a.first == b.first || a.first == b.second) return true;
  61.     if(a.second == b.first || a.second == b.second) return true;
  62.  
  63.     if(score[a.first][b.first] < low || score[a.first][b.second] < low) return true;
  64.     if(score[a.second][b.first] < low || score[a.second][b.second] < low) return true;
  65.  
  66.     return false;
  67. }
  68.  
  69. bool loadgraph(graph_t &g, adj_t& v,const char* fn)
  70. {
  71. 	FILE *fin = fopen(fn, "r");
  72.         int id1, id2;
  73.         float tmpscore;
  74.         //int lines=0;
  75. 	while(fscanf(fin,"P%d,P%d,%f\n",&id1,&id2,&tmpscore ) == 3) {
  76.             //lines++;
  77.             //cout << id1 << " " << id2 << " " << tmpscore << endl;
  78.             id1--;id2--;
  79.             score[id1][id2] = score[id2][id1] = tmpscore;
  80.             n_peptides = max(n_peptides,max(id1,id2));
  81.         }
  82.         //cout <<"num of lines " << lines << endl;
  83.         n_peptides++;
  84.         fclose(fin);
  85.         cout << "Number of peptides: " << n_peptides << endl;
  86.  
  87.         for(int i=0;i<n_peptides;i++) {
  88.             if(score[i][i]<=high) vertices.push_back(make_pair(i,i));
  89.             for(int j=i+1;j<n_peptides;j++) {
  90.                 if(score[i][j]<= high && score[i][i] >= low && score[j][j] >= low) vertices.push_back(make_pair(i,j));
  91.             }
  92.         }
  93.  
  94.         cout << "Broj povezava: " << vertices.size() << endl;
  95.         /*for (size_t i=0;i<n_peptides;i++) {
  96.             for(size_t j=0;j<n_peptides;j++) {
  97.             
  98.                 cout << score[i][j] << " ";
  99.             }
  100.             cout << endl;
  101.         }*/
  102.  
  103.         //ADJSIZE = vertices.size();
  104.         //GRAPHSIZE=ADJSIZE*ADJSIZE;
  105.  
  106.         for(size_t i=0;i<vertices.size();++i) {
  107.             for(size_t j=i+1;j<vertices.size();j++) {
  108.                 if(interaction(vertices[i],vertices[j])) {
  109.                     //cout << "juhu" << endl;
  110.                     g[i].set(j);
  111.                     g[j].set(i);
  112.  
  113.                 }
  114.             }
  115.             v.set(i);
  116.         }
  117. 	/*ifstream ifstm(fn);
  118. 	if(!ifstm) return false;
  119.  
  120. 	char buf[10];
  121. 	while(ifstm.getline(buf,10))
  122. 	{
  123. 		if(
  124. 			!VALIDVEC(buf[0]) ||
  125. 			!VALIDVEC(buf[1]) ||
  126. 			!VALIDVEC(buf[2]) ||
  127. 			!VALIDVEC(buf[3])
  128. 			) continue; 
  129. 		size_t a = MAKEVEC(buf[0], buf[1]);
  130. 		size_t b = MAKEVEC(buf[2], buf[3]);
  131. 		if(a!=b)
  132. 		{
  133. 			g[a].set(b);
  134. 			g[b].set(a);
  135. 		}
  136. 		v.set(a);
  137. 		v.set(b);
  138. 	}*/
  139. 	return true;
  140. }
  141. //--------------????--------------------
  142. typedef tbb::spin_rw_mutex mutex_t; //??????????
  143.  
  144. mutex_t g_veMIS_mut;   //????g_veMIS??
  145. vectex_ex_t g_veMIS;   //??????????,??????tag????????adj??????????????
  146.  
  147. adj_t g_adjAllVec;   //????????????????
  148.  
  149. void showResult(ostream &os) //??????????????
  150. {
  151. 	adj_t r = g_veMIS.adj & g_adjAllVec;
  152. 	for(size_t i=0; i<vertices.size(); i++)
  153. 	{
  154. 		if(r.test(i))
  155. 			os << vertices[i].first << " " << vertices[i].second << endl;
  156. 	}
  157. }
  158.  
  159. // ??????????????task
  160. struct do_mis_task : tbb::task{
  161.  
  162. 	typedef const vectex_ex_t* iterator;
  163.  
  164. 	// begin - ????????????
  165. 	// end - ????????????
  166. 	// vec - ??????????????
  167. 	do_mis_task(iterator begin,
  168. 		iterator end,
  169. 		const vectex_ex_t &vec)
  170. 		:m_vec(vec),m_begin(begin),m_end(end)
  171. 	{}
  172.  
  173. 	// ??????????????????
  174. 	static void serial_do_mis(iterator begin, iterator end, vectex_ex_t vec)
  175. 	{
  176. 		{ // g_veMIS????
  177. 			mutex_t::scoped_lock lock(g_veMIS_mut, false);
  178. 			if(vec.tag <= g_veMIS.tag) return; //????????????????????????????
  179. 		}
  180.  
  181. 		for(;
  182. 				begin!=end &&
  183. 				(!vec.adj.test(begin->tag) || (vec.adj & begin->adj).none());
  184. 			++begin); //????????????????(??????????????????????)
  185.  
  186. 		if(begin == end){
  187. 			mutex_t::scoped_lock lock(g_veMIS_mut);
  188. 			if(vec.tag > g_veMIS.tag) g_veMIS = vec;
  189. 			return;
  190. 		}
  191.  
  192. 		const vectex_ex_t &curvec = *begin;
  193. 		//??????????????????
  194. 		vec.adj.set(curvec.tag,false);
  195. 		vec.tag--;
  196. 		serial_do_mis(begin+1, end, vec);
  197.  
  198. 		//????????????????????
  199. 		vec.adj &= (~curvec.adj);//????????????
  200. 		vec.adj.set(curvec.tag);//????
  201. 		vec.tag = vec.adj.count();
  202. 		serial_do_mis(begin+1, end, vec);
  203. 	}
  204.  
  205. 	task* execute(){
  206. 		for(;
  207. 			m_begin!=m_end &&
  208. 			(!m_vec.adj.test(m_begin->tag) || (m_vec.adj & m_begin->adj).none());
  209. 		++m_begin); //????????????????(??????????????????????)
  210. 		/*  //????????????????????????????????????????
  211. 		if(m_end - m_begin < 8){
  212. 			serial_do_mis(m_begin, m_end, m_vec);
  213. 			return NULL;
  214. 		}
  215. 		*/
  216. 		if(m_end == m_begin){
  217. 			mutex_t::scoped_lock lock(g_veMIS_mut);
  218. 			if(m_vec.tag > g_veMIS.tag) g_veMIS = m_vec;
  219. 			return NULL;
  220. 		}
  221.  
  222. 		size_t g_veMISCount = 0;
  223. 		{ // ??g_veMIS????????????????????
  224. 			mutex_t::scoped_lock lock(g_veMIS_mut, false);
  225. 			g_veMISCount = g_veMIS.tag;
  226. 		}
  227.  
  228. 		// ??????????????????????????????????+1????????????
  229. 		// ????????this????????????????this????????????
  230. 		if(m_vec.tag-1 > g_veMISCount)
  231. 		{
  232. 			const vectex_ex_t & curvec = *m_begin;
  233.  
  234. 			//????????????????????
  235. 			vectex_ex_t v2 = m_vec;
  236. 			v2.adj &= (~curvec.adj);
  237. 			v2.tag = v2.adj.count();
  238. 			if(v2.tag > g_veMISCount)
  239. 			{
  240. 				task* p = parent();
  241. 				do_mis_task* ptask = new(allocate_additional_child_of(*p)) do_mis_task(m_begin+1, m_end, v2);
  242. 				p->spawn(*ptask);
  243. 			}
  244.  
  245. 			//??????????????????
  246. 			m_vec.adj.set(curvec.tag,false);
  247. 			m_vec.tag--;
  248. 			m_begin++;
  249. 			recycle_as_continuation();
  250. 			return this;
  251. 		}
  252.  
  253. 		return NULL;
  254. 	}
  255. private:
  256. 	vectex_ex_t m_vec;
  257. 	iterator m_begin,m_end;
  258. };
  259.  
  260. int main(int argc, char* argv[])
  261. {
  262. 	tbb::tick_count tcBegin = tbb::tick_count::now();
  263.  
  264. 	if(argc < 3) {
  265. 		cout << "mis.exe graphfile outfile" << endl;
  266. 		return 0;
  267. 	}
  268.  
  269. 	tbb::task_scheduler_init init;
  270.  
  271. 	graph_t g;
  272.  
  273.         //cout << "pre funkcije" << endl;
  274.  
  275. 	if(!loadgraph(g, g_adjAllVec, argv[1])) return false;
  276.  
  277. 	vectex_ex_t tmpVec;//??????????????
  278. 	tmpVec.adj.set();
  279. 	tmpVec.tag = vertices.size();
  280.  
  281. 	graph_ex_t gex;
  282. 	graph2graphex(g, gex);
  283. 	if(gex.empty()){
  284. 		cerr << "empty file!" << endl;
  285. 		return 0;
  286. 	}
  287.  
  288. 	//????????
  289. 	//do_mis_task::serial_do_mis(&gex[0],&gex[0]+gex.size(),tmpVec);
  290.  
  291. 	//????????
  292. 	tbb::task *roottask = new(tbb::task::allocate_root()) tbb::empty_task;
  293. 	roottask->set_ref_count(2);
  294. 	tbb::task *firstchild = new(roottask->allocate_child()) do_mis_task(&gex[0],&gex[0]+gex.size(),tmpVec);
  295. 	roottask->spawn_and_wait_for_all(*firstchild);
  296. 	roottask->destroy(*roottask);
  297.  
  298. 	ofstream of(argv[2]);
  299. 	if(of)
  300. 		showResult(of);
  301. 	else
  302. 		cerr << "Can not write the result to " << argv[2] << endl;
  303.  
  304. 	tbb::tick_count tcEnd = tbb::tick_count::now();
  305. 	cout << "used time: " << (tcEnd-tcBegin).seconds() << 's' << endl;
  306. 	return 0;
  307. }
  308.  
  309.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:6:28: fatal error: tbb/tick_count.h: No such file or directory
 #include "tbb/tick_count.h"
                            ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/gb9K64
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!