#include<iostream>
#include<string.h>
#include<malloc.h>
using namespace std;
struct metro
{
struct Snode *S_stations;
struct Jnode *J_stations;
struct line *colors;
};
struct line
{
char color[20];
struct line* down;
struct Snode* first_station;
};
struct Snode
{
int S_id;
struct Snode* right;
struct Snode* nextSn;
struct Snode* previousSn;
struct Jnode* nextJn;
struct Jnode* previousJn;
};
struct Sn_station
{
struct Snode *sn;
struct Sn_station* sn_next;
};
/*struct Jn_station
{
struct Jn_station* Jn;
};*/
struct Jnode
{
char Jn_id;
int indegree;
struct Jnode* next;
struct Sn_station *out_next_start;
struct Sn_station *out_next_temp;
struct Sn_station *out_next_last;
struct Sn_station *out_previous_start;
struct Sn_station *out_previous_temp;
struct Sn_station *out_previous_last;
//struct Jn_station* next_jn_list;
//struct Jn_station* previous_jn_list;
};
void create_list();
void create_line(int [],int,struct line*);
struct Snode* connect_to_junction(struct Snode*, struct Snode*,int );
struct Snode* searchSn(int);
struct Jnode* searchJn(char);
void traverse_lineSn(struct Snode*,struct Snode*);
int traverse_bothSn(struct Snode*,struct Snode*);
struct Snode* search_possibleStation(struct Snode*, struct Snode *);
struct metro* root;
struct line* color_start;
struct Snode* S_start;
struct Jnode* J_start;
struct line* color_end;
struct Snode* S_end;
struct Jnode* J_end;
int main()
{
struct line *cl;
int i,src,dest;
char ch;
struct Snode*temp1,*temp2;
int arr_b[10]={1,2,3,4,5,29,6,7,30,8};
int arr_y[12]={9,10,11,30,12,13,31,14,15,32,16,17};
int arr_v[8]={18,29,19,20,31,21,22,23};
int arr_p[7]={24,29,25,26,27,32,28};
create_list();
cl=color_start;
create_line(arr_b,sizeof(arr_b)/sizeof(int),cl);
cl=cl->down;
create_line(arr_y,sizeof(arr_y)/sizeof(int),cl);
cl=cl->down;
create_line(arr_v,sizeof(arr_v)/sizeof(int),cl);
cl=cl->down;
create_line(arr_p,sizeof(arr_p)/sizeof(int),cl);
cout<<"Enter the source station and destination station"<<endl;
cin>>src;
cin>>dest;
temp1=searchSn(src);
temp2=searchSn(dest);
traverse_bothSn(temp1,temp2);
cout<<"Finally Reached";
}
void create_list()
{
struct line* ctemp;
struct Snode* stemp;
struct Jnode* jtemp;
int i;
char ch='A';
for(i=1;i<29;i++)
{
stemp=(struct Snode*)malloc(sizeof(struct Snode));
stemp->S_id=i;
stemp->right=NULL;
stemp->nextSn=NULL;
stemp->previousSn=NULL;
stemp->nextJn=NULL;
stemp->previousJn=NULL;
if(S_start==NULL)
{
S_start=stemp;
S_end=S_start;
}
else
{
S_end->right=stemp;
S_end=stemp;
}
}
for(i=1;i<5;i++)
{
jtemp=(struct Jnode*)malloc(sizeof(struct Jnode));
jtemp->Jn_id=ch;
jtemp->indegree=0;
jtemp->next=NULL;
jtemp->out_next_start=NULL;
jtemp->out_next_last=NULL;
//jtemp->next_jn_list=NULL;
jtemp->out_previous_start=NULL;
jtemp->out_previous_last=NULL;
//jtemp->previous_jn_list=NULL;
if(J_start==NULL)
{
J_start=jtemp;
J_end=J_start;
}
else
{
J_end->next=jtemp;
J_end=jtemp;
}
ch++;
}
for(i=1;i<5;i++)
{
ctemp=(struct line*)malloc(sizeof(struct line));
ctemp->down=NULL;
ctemp->first_station=NULL;
if(i==1)
{
strcpy(ctemp->color,"Blue Line");
}
if(i==2)
{
strcpy(ctemp->color,"Pink Line");
}
if(i==3)
{
strcpy(ctemp->color,"Violet Line");
}
if(i==4)
{
strcpy(ctemp->color,"Yellow Line");
}
if(color_start==NULL)
{
color_start=ctemp;
color_end=color_start;
}
else
{
color_end->down=ctemp;
color_end=ctemp;
}
}
root=(struct metro*)malloc(sizeof(struct metro));
root->colors=color_start;
root->S_stations=S_start;
root->J_stations=J_start;
}
void create_line(int arr[28],int n,struct line *colour)
{
int i=0;
struct Snode*temp1,*temp2,*temp3;
temp1=S_start;
for(i=0;i<n;i++)
{
if(arr[i]<29)
{
while(temp1->S_id<=arr[i])
{
if(temp1->S_id==arr[i])
{
if(colour->first_station==NULL)
{
colour->first_station=temp1;
temp2=temp1;
}
else
{
temp1->previousSn=temp2;
temp2->nextSn=temp1;
temp2=temp1;
}
}
temp1=temp1->right;
}
}
else
{
while(temp1->S_id<=arr[i+1])
{
if(temp1->S_id==arr[i+1])
{
temp3=temp1;
break;
}
temp1=temp1->right;
}
temp2=connect_to_junction(temp2,temp3,arr[i]);
i++;
}
}
}
struct Snode* connect_to_junction(struct Snode* before, struct Snode* after,int join)
{
struct Sn_station * n_station;
struct Sn_station * l_station;
n_station=(struct Sn_station*)malloc(sizeof(struct Sn_station));
l_station=(struct Sn_station*)malloc(sizeof(struct Sn_station));
n_station->sn=after;
n_station->sn_next=NULL;
l_station->sn=before;
l_station->sn_next=NULL;
char ch='A';
int i;
struct Jnode* connecting_station;
for(i=29;i<33;i++)
{
if(join==i)
{
break;
}
ch++;
}
connecting_station=J_start;
while(connecting_station->Jn_id!=ch)
{
connecting_station=connecting_station->next;
}
before->nextJn=connecting_station;
connecting_station->out_next_temp=n_station;
connecting_station->out_previous_temp=l_station;
if(connecting_station->out_next_start==NULL)
{
connecting_station->out_next_start=connecting_station->out_next_last=connecting_station->out_next_temp;
connecting_station->out_previous_start=connecting_station->out_previous_last=connecting_station->out_previous_temp;
}
else
{
connecting_station->out_next_last->sn_next=connecting_station->out_next_temp;
connecting_station->out_previous_last->sn_next=connecting_station->out_previous_temp;
connecting_station->out_next_last=connecting_station->out_next_temp;
connecting_station->out_previous_last=connecting_station->out_previous_temp;
}
connecting_station->out_next_temp=connecting_station->out_next_temp->sn_next;
connecting_station->out_previous_temp=connecting_station->out_previous_temp->sn_next;
connecting_station->indegree=connecting_station->indegree+1;
after->previousJn=connecting_station;
return after;
}
struct Snode* searchSn(int id)
{
struct Snode*temp=S_start;
while(temp->S_id!=id)
{
temp=temp->right;
}
return temp;
}
struct Jnode* searchJn(char id)
{
struct Jnode*temp=J_start;
while(temp->Jn_id!=id)
{
temp=temp->next;
}
return temp;
}
int traverse_bothSn(struct Snode* source,struct Snode* destination)
{
cout<<source->S_id<<"->";
struct Sn_station*check;
if(source==NULL)
{
cout<<"oops";
return 0;
}
if(source->S_id==destination->S_id)
{
return 1;
}
if(source->nextSn)
{
if(traverse_bothSn(source->nextSn,destination))
{
return 1;
}
/*else if(traverse_bothSn(source->previousSn,destination))
{
return 1;
}*/
}
else if(source->nextJn)
{
cout<<source->nextJn->Jn_id<<"->";
// if(source->nextJn->out_next_start)
check=source->nextJn->out_next_start;
while(check!=NULL)
{
if(traverse_bothSn(check->sn,destination))
{
return 1;
}
else
{
check=check->sn_next;
}
}
/*else if(source->nextJn->out_previous_start)
{check=source->nextJn->out_previous_start;
while(check!=NULL)
{
if(traverse_bothSn(check->sn,destination))
{
return 1;
}
else
{
check=check->sn_next;
}
}}*/
}
return 0;
}
Anonymous - 7 months ago