Skip to content

Commit e04bf81

Browse files
githubmsj1githubmsj1
committed
1.push all into stack 2.add possibility 3.40+ worse
1 parent ca04ae1 commit e04bf81

File tree

2 files changed

+189
-49
lines changed

2 files changed

+189
-49
lines changed

‎route.cpp

Lines changed: 180 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -488,6 +488,18 @@ int goThrough(ALGraph* graph,ListD* demand,int src,int des,std::vector<int> &out
488488
{
489489
using namespace std;
490490

491+
//make a const demand visit
492+
vector<int> demandVisitedConst;
493+
UListD* pD=demand->next->next;
494+
while(pD)
495+
{
496+
demandVisitedConst.push_back(pD->data);
497+
pD=pD->next;
498+
}
499+
500+
//initialize a probability class
501+
Probablity demandProb(demandVisitedConst.size());
502+
491503

492504
// clock_t start = clock();
493505

@@ -531,7 +543,14 @@ int goThrough(ALGraph* graph,ListD* demand,int src,int des,std::vector<int> &out
531543
// int autoSize=reflect1.size()/2;
532544
// autoSize=(autoSize==0?1:autoSize);
533545
int randIndex=clock()%reflect1.size();////rand->clock
534-
546+
// printf("\nThe stack now is:\n");
547+
// printf("\n_________________________\n");
548+
// for(unsigned int i=0;i<reflect1.size();i++)
549+
// {
550+
// printf("[%d] pos:%d idx%d\n",i,reflect1[i].stepth,reflect1[i].nodeID);
551+
// }
552+
// printf("\n_________________________\n");
553+
535554
// printf("****%lu\n",clock());
536555
// printf("****%lu\n",reflect1.size());
537556
// pair<int,int>tmp=reflect1[randIndex];//`````````````````edit
@@ -542,15 +561,26 @@ int goThrough(ALGraph* graph,ListD* demand,int src,int des,std::vector<int> &out
542561

543562
//reflect1.erase(reflect1.begin()+randIndex);
544563
// printf("reflect1 size: %lu",reflect1.size());
545-
564+
path.resize(tmp.stepth+1);//rebuild the path
565+
pathEdge.resize(tmp.stepth+1);
546566
// EdgeNode *p=graph->adjList[tmp.second].firstEdge;
547567
// path[tmp.first]=tmp.second;
548568
EdgeNode *p=graph->adjList[tmp.nodeID].firstEdge;
549569
path[tmp.stepth]=tmp.nodeID;
550570
pathEdge[tmp.stepth]=tmp.edgeID;
551571

572+
printf("\nBefore resize\n");
573+
printf("\ntmp.stepth:%d pathsize:%lu\n",tmp.stepth,path.size());
574+
for(unsigned int i=0;i<path.size();i++)
575+
{
576+
printf("%d->",path[i]);
577+
}
578+
579+
552580
//init demanded vex;
553581
vector<int> demandVisited;
582+
vector<int> demandInPath;//extract from path ,have access demand point,don't need to clear
583+
554584
UListD* pD=demand->next->next;
555585
while(pD)
556586
{
@@ -563,9 +593,21 @@ int goThrough(ALGraph* graph,ListD* demand,int src,int des,std::vector<int> &out
563593
visited[i]=false;
564594
}
565595

566-
path.resize(tmp.stepth+1);//rebuild the path
567-
pathEdge.resize(tmp.stepth+1);
568596

597+
598+
599+
600+
601+
printf("\nreflect ind:%d back stepth:%d back node:%d\n",randIndex,tmp.stepth,tmp.nodeID);
602+
printf("\nAfter back PathNode(%lu) is :\n",path.size());
603+
for(unsigned int i=0;i<path.size();i++)
604+
{
605+
printf("%d->",path[i]);
606+
}
607+
// getchar();
608+
609+
610+
//initialize the visited Node and demandNode
569611
for(unsigned int i=0;i<path.size();i++)
570612
{
571613
visited[path[i]]=true;
@@ -575,6 +617,7 @@ int goThrough(ALGraph* graph,ListD* demand,int src,int des,std::vector<int> &out
575617
if(demandVisited[j]==path[i])
576618
{
577619
demandVisited.erase(demandVisited.begin()+j);
620+
demandInPath.push_back(path[i]);
578621
}
579622
}
580623
}
@@ -583,6 +626,14 @@ int goThrough(ALGraph* graph,ListD* demand,int src,int des,std::vector<int> &out
583626

584627
while(path.back()!=des&&p)
585628
{
629+
630+
// printf("\nPath(%lu) is :\n",path.size());
631+
// for(unsigned int i=0;i<path.size();i++)
632+
// {
633+
// printf("%d->",path[i]);
634+
// }
635+
636+
586637
int maxVal=-1;
587638
// int minVal=graph->vexNum+1;//high weight
588639

@@ -616,28 +667,49 @@ int goThrough(ALGraph* graph,ListD* demand,int src,int des,std::vector<int> &out
616667
p=p->next;
617668
}
618669

619-
620670

621-
if(choice==-1)
622-
break;
671+
//judge whether the node is the required node
672+
//if yes judge it if it is the best one
673+
//chose it as the next node if hit probability
674+
//otherwise don't take it
675+
if(choice!=-1)
676+
{
677+
for(unsigned int i=0;i<demandVisited.size();i++)
678+
{
679+
if(demandVisited[i]==choice)
680+
{
681+
demandInPath.push_back(demandVisited[i]);
682+
683+
if(demandProb.chooseOrNot(demandInPath)==false)
684+
{
685+
printf("choose false\n");
686+
choice=-2;
687+
demandInPath.pop_back();
688+
break;
689+
}
690+
else
691+
{
692+
printf("choose true\n");
693+
demandInPath.pop_back();
694+
break;
695+
}
696+
697+
}
698+
}
699+
}
700+
701+
if(choice==des)
702+
{
703+
choice=-1;
704+
}
705+
706+
707+
708+
623709

624-
//random to choose a not best path,but the worst path
625-
// int u=clock()%100;
626-
// if(u>=100)
627-
// {
628-
// choice=choiceBad;
629-
// choiceEdge=choiceEdgeBad;
630-
// // printf("\n!!!!!!!!!!!!!!!!!!!!!!!!!!choose bad(%d)!!!!!!!!!!!!!!!!!!!!!!!\n",u);
631-
// }
632-
// else
633-
// {
634-
// // printf("\n!!!!!!!!!!!!!!!!!!!!!!!!!!choose good(%d)!!!!!!!!!!!!!!!!!!!!!!!\n",u);
635-
// }
636710

637711

638-
visited[choice]=true;
639712

640-
// printf("here???\n");
641713
//push the some biggest node into stack
642714
while(_p)
643715
{
@@ -653,7 +725,7 @@ int goThrough(ALGraph* graph,ListD* demand,int src,int des,std::vector<int> &out
653725
tmp.edgeID=_p->edgeID;
654726
reflect1.push_back(tmp);
655727
}
656-
else if(((float)graph->adjList[_p->adjvex].infoVal)/(float)maxVal>0.1)
728+
else if(((float)graph->adjList[_p->adjvex].infoVal)/(float)maxVal>=0)//>0.1
657729
{
658730
// reflect.push(make_pair(path.size(),_p->adjvex));
659731
// reflect1.push_back(make_pair(path.size(),_p->adjvex));
@@ -666,8 +738,31 @@ int goThrough(ALGraph* graph,ListD* demand,int src,int des,std::vector<int> &out
666738
}
667739
}
668740
_p=_p->next;
741+
669742
}
670743

744+
745+
746+
747+
748+
//break if quit the next step
749+
printf("\nchoice=%d\n",choice);
750+
if(choice==-2)
751+
{
752+
printf("not choose the best\n");
753+
break;
754+
}
755+
if(choice==-1)//can't find the next node,maybe find a loop
756+
{
757+
printf("dead route\n");
758+
// getchar();
759+
demandProb.refresh(demandInPath);
760+
break;
761+
}
762+
visited[choice]=true;
763+
764+
765+
// printf("path.push_back(choice);\n");
671766
// printf("<<<%lu\n",path.size());
672767
path.push_back(choice);
673768
pathEdge.push_back(choiceEdge);
@@ -676,21 +771,23 @@ int goThrough(ALGraph* graph,ListD* demand,int src,int des,std::vector<int> &out
676771
//finalIdex++;
677772
p=graph->adjList[choice].firstEdge;
678773

774+
// printf("for(unsigned int i=0;i<demandVisited.size();i++)\n");
679775
//erase the required node visited
680776
for(unsigned int i=0;i<demandVisited.size();i++)
681777
{
682778
if(demandVisited[i]==choice)
683779
{
684780
demandVisited.erase(demandVisited.begin()+i);
781+
demandInPath.push_back(choice);
685782
}
686783
}
687784

688785
if(demandVisited.size()==0)
689786
{
787+
printf("all demand node are found\n");
690788
satisfied=true;
691789
break;
692790
}
693-
694791
// //accelerate
695792
// int perCost=graph->vexNum/demand->size;
696793
// int predicCost=perCost*(demand->size-demandVisited.size());
@@ -700,6 +797,7 @@ int goThrough(ALGraph* graph,ListD* demand,int src,int des,std::vector<int> &out
700797
// printf("break\n");
701798
// break;
702799
// }
800+
// printf("%d %d\n",path.back(),des);
703801
}
704802

705803
//the demand are found
@@ -740,11 +838,11 @@ int goThrough(ALGraph* graph,ListD* demand,int src,int des,std::vector<int> &out
740838

741839
}
742840

743-
// printf("\nPathNode(%lu) is :\n",path.size());
744-
// for(unsigned int i=0;i<path.size();i++)
745-
// {
746-
// printf("%d->",path[i]);
747-
// }
841+
printf("\nPathNode(%lu) is :\n",path.size());
842+
for(unsigned int i=0;i<path.size();i++)
843+
{
844+
printf("%d->",path[i]);
845+
}
748846

749847
// // // pathEdge.erase(pathEdge.begin());
750848
// printf("\nPathEdge(%lu) is :\n",pathEdge.size());
@@ -753,12 +851,23 @@ int goThrough(ALGraph* graph,ListD* demand,int src,int des,std::vector<int> &out
753851
// printf("%d->",pathEdge[i]);
754852
// }
755853

756-
printf("\nDemand(%lu) is :\n",demandVisited.size());
757-
for(unsigned int i=0;i<demandVisited.size();i++)
758-
{
759-
printf("%d ",demandVisited[i]);
760-
}
761-
printf("\nThe reflect stack sizels: %lu\n",reflect1.size());
854+
855+
// printf("\nDemand(%lu) is :\n",demandVisited.size());
856+
// for(unsigned int i=0;i<demandVisited.size();i++)
857+
// {
858+
// printf("%d ",demandVisited[i]);
859+
// }
860+
861+
// printf("\nDemand Visited(%lu) is :\n",demandInPath.size());
862+
// for(unsigned int i=0;i<demandInPath.size();i++)
863+
// {
864+
// printf("%d ",demandInPath[i]);
865+
// }
866+
867+
printf("\nThe reflect stack size is: %lu\n",reflect1.size());
868+
printf("it is ready to back");
869+
// getchar();
870+
762871

763872
}
764873
// PathNodeLink result;//=(PathNodeLink)malloc(sizeof(PathNode));;
@@ -936,8 +1045,10 @@ Probablity::Probablity(unsigned int _numDemand)
9361045
numDemand=_numDemand;
9371046
// variateRate=20;
9381047
}
1048+
Probablity::~Probablity()
1049+
{}
9391050

940-
int Probablity::refresh(std::vector<int> demandPath)
1051+
int Probablity::refresh(std::vector<int> &demandPath)
9411052
{
9421053
ProbNodeLink p;
9431054
p=head;
@@ -949,12 +1060,16 @@ int Probablity::refresh(std::vector<int> demandPath)
9491060
tmp->child=new std::map<int,ProbNode*>();
9501061
tmp->depth=i+1;
9511062
tmp->val=numDemand*4;
1063+
p->child->insert(std::pair<int,ProbNodeLink>(demandPath[i],tmp));
9521064
}
9531065

9541066
std::map<int,ProbNode*>& pTmp=*(p->child);
9551067
p=pTmp[demandPath[i]];
9561068

9571069
p->val-=p->depth;
1070+
// cout<<"index: "<<demandPath[i]<<" ";
1071+
// cout<<"val: "<<p->val<<" ";
1072+
// cout<<"depth: "<<p->depth<<endl;
9581073
if(p->val<0)
9591074
{
9601075
p->val=0;
@@ -964,7 +1079,7 @@ int Probablity::refresh(std::vector<int> demandPath)
9641079
return 0;
9651080
}
9661081

967-
bool Probablity::chooseOrNot(std::vector<int> demandPath)
1082+
bool Probablity::chooseOrNot(std::vector<int> &demandPath)
9681083
{
9691084
ProbNodeLink p;
9701085
p=head;
@@ -1003,14 +1118,41 @@ bool Probablity::chooseOrNot(std::vector<int> demandPath)
10031118
max=i->second->val;
10041119
maxIdx=i->first;
10051120
}
1121+
// printf("%d\n",i->first);
1122+
}
1123+
1124+
printf("\n*************************************************\n");
1125+
printf("best Idx: %d max pro: %d \n",maxIdx,max);
1126+
printf("demandPath: \n");
1127+
for (unsigned int i=0;i<demandPath.size();i++)
1128+
{
1129+
printf("%d ",demandPath[i]);
10061130
}
10071131

1132+
printf("\nThe vals are: \n");
1133+
for(std::map<int,ProbNodeLink>::iterator i=p->child->begin();i!=p->child->end();i++)
1134+
{
1135+
printf("%d(%d)",i->first,i->second->val);
1136+
// printf("%d\n",i->first);
1137+
}
1138+
1139+
1140+
printf("\n*************************************************\n");
1141+
// getchar();
1142+
1143+
1144+
std::map<int,ProbNodeLink> &tmpchild=*(p->child);
10081145
if(demandPath.back()==maxIdx)
10091146
{
1010-
if(clock()%100>20)
1147+
// getchar();
1148+
if(clock()%100<20&&tmpchild[maxIdx]->val!=(int)numDemand*4)
10111149
{
1012-
return true;
1150+
// getchar();
1151+
printf("\nvariation\n");
1152+
return false;
10131153
}
1154+
return true;
1155+
10141156
}
10151157

10161158
return false;
@@ -1030,8 +1172,6 @@ void search_route(char *topo[5000],unsigned int edge_num, char *demand)
10301172
EdgeLink e;
10311173

10321174

1033-
1034-
10351175
for(unsigned int i=0;i<MAX_NUM;i++)
10361176
{
10371177
graph.adjList[i].firstEdge=NULL;

0 commit comments

Comments
 (0)