#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
#include <algorithm>
#include "tbb/tick_count.h"
#include "tbb/task_scheduler_init.h"
#include "tbb/spin_rw_mutex.h" //todo:??????????
#include "tbb/task.h"
#define MAXN 500
using namespace std;
const size_t ADJSIZE = 26;
const size_t GRAPHSIZE=500;
int n_peptides = 0;
const float low = -7.0, high = -8.5;
float score[MAXN][MAXN];
vector< pair<int,int> >vertices;
// ??????????????????????(26????????)
#define VALIDVEC(char0) (char0>='A' && char0<='Z')
#define MAKEVEC(char0,char1) (size_t(char0-'A')*ADJSIZE+char1-'A')
#define GETVECCHAR0(vec) char(char(vec/ADJSIZE) + 'A')
#define GETVECCHAR1(vec) char(char(vec%ADJSIZE) + 'A')
typedef bitset<GRAPHSIZE> adj_t; //bitset
typedef adj_t graph_t[GRAPHSIZE];//????????
struct vectex_ex_t{ //????????????
size_t tag; // ??????????
adj_t adj; // ??????
};
typedef vector<vectex_ex_t> graph_ex_t;//??????????????????????????????
// ????????????
void graph2graphex(const graph_t &g, graph_ex_t& gex)
{
//cout << vertices.size();
for(size_t i=0; i<vertices.size(); i++){ //changed graph size
//cout << "any " << i << endl;
vectex_ex_t v={
i, g[i]
};
gex.push_back(v);
}
/*for(size_t i =0;i<vertices.size();i++) {
cout << gex[i].tag << ": ";
for(size_t j=0;j<gex[i].adj.size();j++) {
cout << gex[i].adj[j] << " ";
}
cout << endl;
}*/
}
//??????????????
bool interaction(pair<int,int> a, pair<int,int> b) {
if(a.first == b.first || a.first == b.second) return true;
if(a.second == b.first || a.second == b.second) return true;
if(score[a.first][b.first] < low || score[a.first][b.second] < low) return true;
if(score[a.second][b.first] < low || score[a.second][b.second] < low) return true;
return false;
}
bool loadgraph(graph_t &g, adj_t& v,const char* fn)
{
FILE *fin = fopen(fn, "r");
int id1, id2;
float tmpscore;
//int lines=0;
while(fscanf(fin,"P%d,P%d,%f\n",&id1,&id2,&tmpscore ) == 3) {
//lines++;
//cout << id1 << " " << id2 << " " << tmpscore << endl;
id1--;id2--;
score[id1][id2] = score[id2][id1] = tmpscore;
n_peptides = max(n_peptides,max(id1,id2));
}
//cout <<"num of lines " << lines << endl;
n_peptides++;
fclose(fin);
cout << "Number of peptides: " << n_peptides << endl;
for(int i=0;i<n_peptides;i++) {
if(score[i][i]<=high) vertices.push_back(make_pair(i,i));
for(int j=i+1;j<n_peptides;j++) {
if(score[i][j]<= high && score[i][i] >= low && score[j][j] >= low) vertices.push_back(make_pair(i,j));
}
}
cout << "Broj povezava: " << vertices.size() << endl;
/*for (size_t i=0;i<n_peptides;i++) {
for(size_t j=0;j<n_peptides;j++) {
cout << score[i][j] << " ";
}
cout << endl;
}*/
//ADJSIZE = vertices.size();
//GRAPHSIZE=ADJSIZE*ADJSIZE;
for(size_t i=0;i<vertices.size();++i) {
for(size_t j=i+1;j<vertices.size();j++) {
if(interaction(vertices[i],vertices[j])) {
//cout << "juhu" << endl;
g[i].set(j);
g[j].set(i);
}
}
v.set(i);
}
/*ifstream ifstm(fn);
if(!ifstm) return false;
char buf[10];
while(ifstm.getline(buf,10))
{
if(
!VALIDVEC(buf[0]) ||
!VALIDVEC(buf[1]) ||
!VALIDVEC(buf[2]) ||
!VALIDVEC(buf[3])
) continue;
size_t a = MAKEVEC(buf[0], buf[1]);
size_t b = MAKEVEC(buf[2], buf[3]);
if(a!=b)
{
g[a].set(b);
g[b].set(a);
}
v.set(a);
v.set(b);
}*/
return true;
}
//--------------????--------------------
typedef tbb::spin_rw_mutex mutex_t; //??????????
mutex_t g_veMIS_mut; //????g_veMIS??
vectex_ex_t g_veMIS; //??????????,??????tag????????adj??????????????
adj_t g_adjAllVec; //????????????????
void showResult(ostream &os) //??????????????
{
adj_t r = g_veMIS.adj & g_adjAllVec;
for(size_t i=0; i<vertices.size(); i++)
{
if(r.test(i))
os << vertices[i].first << " " << vertices[i].second << endl;
}
}
// ??????????????task
struct do_mis_task : tbb::task{
typedef const vectex_ex_t* iterator;
// begin - ????????????
// end - ????????????
// vec - ??????????????
do_mis_task(iterator begin,
iterator end,
const vectex_ex_t &vec)
:m_vec(vec),m_begin(begin),m_end(end)
{}
// ??????????????????
static void serial_do_mis(iterator begin, iterator end, vectex_ex_t vec)
{
{ // g_veMIS????
mutex_t::scoped_lock lock(g_veMIS_mut, false);
if(vec.tag <= g_veMIS.tag) return; //????????????????????????????
}
for(;
begin!=end &&
(!vec.adj.test(begin->tag) || (vec.adj & begin->adj).none());
++begin); //????????????????(??????????????????????)
if(begin == end){
mutex_t::scoped_lock lock(g_veMIS_mut);
if(vec.tag > g_veMIS.tag) g_veMIS = vec;
return;
}
const vectex_ex_t &curvec = *begin;
//??????????????????
vec.adj.set(curvec.tag,false);
vec.tag--;
serial_do_mis(begin+1, end, vec);
//????????????????????
vec.adj &= (~curvec.adj);//????????????
vec.adj.set(curvec.tag);//????
vec.tag = vec.adj.count();
serial_do_mis(begin+1, end, vec);
}
task* execute(){
for(;
m_begin!=m_end &&
(!m_vec.adj.test(m_begin->tag) || (m_vec.adj & m_begin->adj).none());
++m_begin); //????????????????(??????????????????????)
/* //????????????????????????????????????????
if(m_end - m_begin < 8){
serial_do_mis(m_begin, m_end, m_vec);
return NULL;
}
*/
if(m_end == m_begin){
mutex_t::scoped_lock lock(g_veMIS_mut);
if(m_vec.tag > g_veMIS.tag) g_veMIS = m_vec;
return NULL;
}
size_t g_veMISCount = 0;
{ // ??g_veMIS????????????????????
mutex_t::scoped_lock lock(g_veMIS_mut, false);
g_veMISCount = g_veMIS.tag;
}
// ??????????????????????????????????+1????????????
// ????????this????????????????this????????????
if(m_vec.tag-1 > g_veMISCount)
{
const vectex_ex_t & curvec = *m_begin;
//????????????????????
vectex_ex_t v2 = m_vec;
v2.adj &= (~curvec.adj);
v2.tag = v2.adj.count();
if(v2.tag > g_veMISCount)
{
task* p = parent();
do_mis_task* ptask = new(allocate_additional_child_of(*p)) do_mis_task(m_begin+1, m_end, v2);
p->spawn(*ptask);
}
//??????????????????
m_vec.adj.set(curvec.tag,false);
m_vec.tag--;
m_begin++;
recycle_as_continuation();
return this;
}
return NULL;
}
private:
vectex_ex_t m_vec;
iterator m_begin,m_end;
};
int main(int argc, char* argv[])
{
tbb::tick_count tcBegin = tbb::tick_count::now();
if(argc < 3) {
cout << "mis.exe graphfile outfile" << endl;
return 0;
}
tbb::task_scheduler_init init;
graph_t g;
//cout << "pre funkcije" << endl;
if(!loadgraph(g, g_adjAllVec, argv[1])) return false;
vectex_ex_t tmpVec;//??????????????
tmpVec.adj.set();
tmpVec.tag = vertices.size();
graph_ex_t gex;
graph2graphex(g, gex);
if(gex.empty()){
cerr << "empty file!" << endl;
return 0;
}
//????????
//do_mis_task::serial_do_mis(&gex[0],&gex[0]+gex.size(),tmpVec);
//????????
tbb::task *roottask = new(tbb::task::allocate_root()) tbb::empty_task;
roottask->set_ref_count(2);
tbb::task *firstchild = new(roottask->allocate_child()) do_mis_task(&gex[0],&gex[0]+gex.size(),tmpVec);
roottask->spawn_and_wait_for_all(*firstchild);
roottask->destroy(*roottask);
ofstream of(argv[2]);
if(of)
showResult(of);
else
cerr << "Can not write the result to " << argv[2] << endl;
tbb::tick_count tcEnd = tbb::tick_count::now();
cout << "used time: " << (tcEnd-tcBegin).seconds() << 's' << endl;
return 0;
}