مساله اینه که من یه لیست دارم به اسمMIS که شامل تعدادی عدد هست. باید مقدار هر یک از خونه های این لیست رو به یه ترد بدم تا متدی ( الگوریتم دیکستراست که با صف اولویت پیاده شده) رو اجرا کنه. یه تابع نوشتم به اسم تابع Thread() که مقدار خونه رو از لیست می خونه و در متغیر b از شی ایجاد شده می ریزه و تابع ShorthestPaths رو صدا میزنه تا دیکسترا رو اجرا کنه. مثلا اگه خونه اول لیست توش مقدار 0 هست، تابع Thread مقدار b شی ایجاد شده از کلاس ShortestPath رو 0 میذاره و بعد الگوریتم دیسکترا رو اجرا میکنه( در این حالت کمترین فاصله گره 0 از بقیه گره های گراف محاسبه میشه) و اگه خونه دوم مقدار 3 داشته باشه ، تابع Thread مقدار b شی ایجاد شده از کلاس ShortestPath رو 3 میذاره و بعد الگوریتم دیسکترا رو اجرا میکنه( در این حالت کمترین فاصله گره 3 از بقیه گره های گراف محاسبه میشه) .در انتها هر ترد کمترین فاصله خودش رو تا عددهایی که داخل لیست TreeNode هستند رو بدست میاره و در لیست cmpr که سراسری تعریفش کردم میریزه بعد خاتمه پیدا میکنه.
این کد برنامه است قسمتی هم که از ترد استفاده کردم با قرمز مشخص شده:
// algorithm1.cpp : Defines the entry point for the console application.
//
#include"stdafx.h"
#include"algorithm1.h"
#include<iostream>
#include<conio.h>
#include<fstream>
#include<vector>
#include<string>
#include<list>
#include<queue>
#include<limits>
#include<process.h>
usingnamespace std;
//----------------
#define Max 100
#define p_int pair<int ,int>
#define MP(x,y) make_pair((x),(y))
//----------------
list<int>terminals,MIS,TreeNodes,Min,Opt;
int E,V=5,Des;
//int Check=0;
list<int>::iterator itt, it1;
//vector<int> touch;
vector<pair<int,int>>edges[Max];
vector<pair<pair<int,int>,int>> cmpr;
priority_queue<p_int,vector<p_int>,greater<p_int>>Q;
//----------------
class ShorthestPath
{
public:
list<int> tree;
vector<int> touch;
int b,thread,check,opt[Max];
bool UniquE(vector<pair<int,int>> *edges,int u,int j)
{
for(int i=0;i<edges[u].size();i++)
{
if(j==edges[u][i].first)
returnfalse;
}
returntrue;
}
void change(string s,list<int> &l)
{
int sum=0,x;
int c=s.length();
for(int i=0;i<c;i++)
{
if(s.at(i)!=' ')
sum=0;
while(s.length()!=i && s.at(i)!=' ')
{
x=s.at(i)-48;
sum=sum*10+x;
i++;
}
l.push_back(sum);
}
}
void Init()
{
for(int i=0;i<V;i++)
{
opt[i]=100;
}
check=0;
thread=1;
}
void FindMin(int s)
{
int d,minLen=100;
for(it1=tree.begin();it1!=tree.end();it1++)
{
if(minLen>opt[*it1] && s!=*it1)
{
minLen=opt[*it1];
d=*it1;
}
}
cmpr.push_back(MP(MP(s,d),minLen));
check=1;//reset check variable
}
ShorthestPath()
{
int V,E,i=-1;
list<int>l;
list<int>::iterator it;
string st="";
Init();
ifstream infile;
char ch[100];
infile.open("test.txt",ios::in);
if(!infile.is_open())
{
cout<<"could not open file";exit(1);
}
while(infile.getline(ch,100))
{
i++;
st=ch;
change(st,l);
for(it=l.begin();it!=l.end();it++)
{
if(UniquE(edges,i,*it))edges[i].push_back(MP(*it,1));
if(UniquE(edges,*it,i))edges[*it].push_back(MP(i,1));
}
l.clear();
}
infile.close();
}
void Fin()
{
_endthread();
}
void shorthestpaths()
{
int s=b;
int i, to,u=s,wei;
opt[s] = 0;
touch.assign(V,s);
priority_queue<pair<int,int>>pq;
pair<int,int> temp;
temp.first= s;
temp.second=0;
pq.push(temp);
while(!pq.empty())
{
temp=pq.top();
pq.pop();
int fr=temp.first;
int se=temp.second;
if(se != opt[fr])
continue;
for(int i=0;i<edges[fr].size();i++)
{
to=edges[fr][i].first;
wei=edges[fr][i].second;
if(opt[to] > opt[fr] + wei)
{
opt[to] = opt[fr] + wei;
touch.at(to)=fr;
temp.first=to;
temp.second=opt[to];
pq.push(temp);
}
}
}
if(check==0) FindMin(s);
if(check==1)
{
int tmp=Des;
while(touch.at(tmp)!=s)
{
int t;
t=touch.at(tmp);
TreeNodes.push_back(t);
tmp=t;
}
TreeNodes.push_back(Des);
TreeNodes.sort();TreeNodes.unique();
MIS.remove(Des);
check=0;
}
////// com min //////
if( thread==1) Fin();
}
};
//----------------
void resetMatrix(int **p,int row,int col)
{
for(int i=0;i<row;i++)
for(int j=0;j<col;j++)
p[i][j]=0;
}
void change(string s,list<int> &l)//
{
int sum=0,x;
int c=s.length();
for(int i=0;i<c;i++)
{
if(s.at(i)!=' ')
sum=0;
while(s.length()!=i && s.at(i)!=' ')
{
x=s.at(i)-48;
sum=sum*10+x;
i++;
}
l.push_back(sum);
}
}
void initializationMatrix(int **m,int n)
{
list<int>l;
list<int>::iterator it;
string st="";
ifstream infile ;
char ch[256];
infile.open("test.txt",ios::in);
if(!infile.is_open())
{cout<<"could not open file."; exit(1);}
int j=0;
while(infile.getline(ch,256))
{
st=ch;
change(st,l);
if(l.empty())
cout<<"empty";
for(it=l.begin();it!=l.end();it++)
{
m[j][*it]=1;
/*i++;*/
}
j++;
st.clear();
l.clear();
}
}
void IntersectionNodes(int id,list<int> &l,list<int> &s,int **m,int n)
{
list<int>::iterator it;
it=l.begin();int x=0;
while(it!=l.end())
{
x++;
int flag=0,tflag=0;
for(int j=0;j<n;j++)
{
if(l.size()==0) break;
if(m[id][j]!=0 && *it==j)
{
l.erase(it);it=l.begin();
s.push_back(id);
if(x!=0) x--;
advance(it,x);
flag=1;
s.unique();
}
elseif(id==*it && flag==0)
{
l.erase(it);it=l.begin();
s.push_back(id);
if(x!=0) x--;
advance(it,x);
flag=1;
s.unique();
}
}
if(flag==0) it++;
}
}
void Thread(void *nothing)
{
ShorthestPath sp;
sp.b=*itt;sp.tree=TreeNodes;
sp.shorthestpaths();
}
void Minimal(int&a,int&b)
{
int m=100;
vector<pair<pair<int,int>,int>>::iterator t;
if(cmpr.size()==0){cout<< "bad error";}
for(t=cmpr.begin();t!=cmpr.end();t++)
{
if(m > t->second)
{
m=t->second;
a=t->first.first;
b=t->first.second;
}
}
}
int main()
{
list<int>::iterator it;
int **matrix,n=5,s=0,nodeId,flag=0,d,z,x;
matrix=newint*[n];
for(int i=0;i<n;i++)
matrix[i]=newint[n];
resetMatrix(matrix,n,n);
terminals.push_back(1);terminals.push_back(3);
initializationMatrix(matrix,n);
ShorthestPath p,R;
nodeId=0;
do
{
it=terminals.begin();
if(flag==0)nodeId=0;
else
nodeId=*it;
IntersectionNodes(nodeId,terminals,MIS,matrix,n);
flag=1;
}while(!terminals.empty());
TreeNodes.push_back(0);
////-----------------------
while(!MIS.empty())
{
//-----------------------
for(itt=MIS.begin();itt!=MIS.end();itt++)
{
_beginthread(Thread,0,NULL);
}
//------------------------
Minimal(z,Des);
p.b=z; p.check=1;p.thread=0;p.tree=TreeNodes;
p.shorthestpaths();
}//end while
//----step2
getch();
return 0;
}
این لینک فایلی هست که داده های اولیه از اون خونده میشن:
http://www.upload4files.tk/download.php?file=d8a766a861fccc63be0e4db57443bd6d