Anonymous Anonymous - 10 days ago
43 0

No description

C++

DS mini Projectnew(3rd sem)

#include<iostream>
#include<string.h>
#include<malloc.h>
#include<stdio.h>
#include<conio.h>
#include<graphics.h>
#include<dos.h>
using namespace std;
float
sum=0,w=0,s,wn,v[8],td=0,e,i,j,n,w1[8],j1[8],arr[8],arr1[8],e1,count,d2,y1
;
float var,a[8][8],d[8],p[8],n1,c,c1,w2;



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";




int gd=DETECT,gm;
clrscr();
void draw(float,float);
void dijkstra(float s,float e,float v1[8],float d1[8],float p1[8],float
a1[8][8],float n);
void ssp();
void path();
void initial();
printf("There are 8 routers in each subnet
");
n=8;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
a[i][j]=32767;
}}
printf("Enter the weight between 0 & 1 : ");
scanf("%f",&a[0][1]);
a[1][0]=a[0][1];
printf("Enter the weight between 0 & 3 : ");
scanf("%f",&a[0][3]);
a[3][0]=a[0][3];
printf("Enter the weight between 1 & 5 : ");
scanf("%f",&a[1][5]);
a[5][1]=a[1][5];
printf("Enter the weight between 1 & 2 : ");
scanf("%f",&a[1][2]);
a[2][1]=a[1][2];
printf("Enter the weight between 2 & 4 : ");
scanf("%f",&a[2][4]);
a[4][2]=a[2][4];
printf("Enter the weight between 2 & 3 : ");
scanf("%f",&a[2][3]);
a[3][2]=a[2][3];
printf("Enter the weight between 3 & 7 : ");
scanf("%f",&a[3][7]);
a[7][3]=a[3][7];
printf("Enter the weight between 4 & 5 : ");
scanf("%f",&a[4][5]);
a[5][4]=a[4][5];
printf("Enter the weight between 4 & 7 : ");
scanf("%f",&a[4][7]);
a[7][4]=a[4][7];
printf("Enter the weight between 5 & 6 : ");
scanf("%f",&a[5][6]);
a[6][5]=a[5][6];
printf("Enter the weight between 6 & 7 : ");
scanf("%f",&a[6][7]);
a[7][6]=a[6][7];
printf("Enter source and destination node from network 1 ");
scanf("%f %f",&s,&e);
clrscr();
initgraph(&gd,&gm,"c:\tc\bgi");
setcolor(WHITE);
fillellipse(20,100,7,7);fillellipse(85,50,7,7);
fillellipse(150,100,7,7);fillellipse(85,150,7,7);
fillellipse(320,100,7,7);fillellipse(385,50,7,7);
fillellipse(450,100,7,7);fillellipse(385,150,7,7);
w1[0]=20;w1[1]=85;w1[2]=150;w1[3]=85;w1[4]=320;
w1[5]=385;w1[6]=450;w1[7]=385;
j1[0]=100;j1[1]=50;j1[2]=100;j1[3]=150;j1[4]=100;j1[5]=50;
j1[6]=100;j1[7]=150;
initial();
setcolor(GREEN);
for(i=0;i<n;i++)
{
v[i]=32767;
d[i]=32767;
p[i]=0;
}
w=s;
d[s]=0;
v[s]=s;
td=0;
dijkstra(s,e,v,d,p,a,n);
path();
c=w1[e];
c1=j1[e];
printf("One more packet ?(Type 1 if yes) ");
scanf("%f",&count);
path();
if(count==1)
ssp();
path();
w=e;
setcolor(GREEN);
count=0;
printf("Enter source and destination node from network 2 ");
scanf("%f %f",&s,&e);
a[0][1]=2;
a[0][3]=6;
a[1][2]=2;
a[1][5]=7;
a[2][3]=1;
a[2][4]=2;
a[4][5]=3;
a[5][6]=3;
a[4][7]=2;
a[6][7]=2;
a[3][7]=4;
a[1][0]=2;
a[3][0]=6;
a[2][1]=2;
a[5][1]=7;
a[3][2]=1;
a[4][2]=2;
a[5][4]=3;
a[6][5]=3;
a[7][4]=2;
a[7][6]=2;
a[7][3]=4;
setcolor(WHITE);
fillellipse(20,400,7,7);fillellipse(85,350,7,7);
fillellipse(150,400,7,7);fillellipse(85,450,7,7);
fillellipse(320,400,7,7);fillellipse(385,350,7,7);
fillellipse(450,400,7,7);fillellipse(385,450,7,7);
w1[0]=20;w1[1]=85;w1[2]=150;w1[3]=85;w1[4]=320;
w1[5]=385;w1[6]=450;w1[7]=385;
j1[0]=400;j1[1]=350;j1[2]=400;j1[3]=450;j1[4]=400;j1[5]=350;
j1[6]=400;j1[7]=450;
initial();
setcolor(GREEN);
for(i=0;i<n;i++)
{
v[i]=32767;
d[i]=32767;
p[i]=0;
}
w=s;
d[s]=0;
v[s]=s;
td=0;
line(c,c1,w1[s],j1[s]);
delay(2000);
dijkstra(s,e,v,d,p,a,n);
path();
if(count==1)
ssp();
path();
getch();

}
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;
}






void dijkstra(float s,float e,float v1[8],float d1[8],float p1[8],float
a1[8][8],float n)
{
while((p1[e])==0)
{
for(i=0;i<n;i++)
{
if((a1[w][i]+td)<d1[i]&&i!=w&&a1[w][i]!=32767)
{
d1[i]=a1[w][i]+td;
d2=d1[i];
v1[i]=w;
}}
sum=32767;
for(i=0;i<n;i++)
{
if(d1[i]<sum&&i!=s&&p1[i]!=1)
{
sum=d1[i];
wn=i;
}}
p1[wn]=1;
td=d1[wn];
w=wn;
}
}
void draw(float w,float v1)
{
float s,x,y;
s=(j1[v1]-j1[w])/(w1[v1]-w1[w]);
if(s<0)
s=s*-1;
x=w1[w];
y=j1[w];
moveto(x,y);
if(x==w1[v1])
{
while(y!=j1[v1])
{
if(y>j1[v1])
{
line(x,y,x,y-1);
delay(10);
y=y-1;
}
else
{
line(x,y,x,y+1);
delay(10);
y=y+1;
}}}
if(y==j1[v1])
{
while(x!=w1[v1])
{
if(x>w1[v1])
{
line(x,y,x-1,y);
delay(10);
x=x-1;
}
else
{
line(x,y,x+1,y);
delay(10);
x=x+1;
}}}
if(x<w1[v1]&&y<j1[v1])
{
while(x!=w1[v1])
{
line(x,y,x+1,y+s);
delay(10);
x=x+1;
y=y+s;
}}
if(x>w1[v1]&&y>j1[v1])
{
while(x!=w1[v1])
{
line(x,y,x-1,y-s);
delay(10);
x=x-1;
y=y-s;
i=i+1;
}}
if(x>w1[v1]&&y<j1[v1])
{
while(x!=w1[v1])
{
line(x,y,x-1,y+s);
delay(10);
x=x-1;
y=y+s;
i=i+1;
}}
if(x<w1[v1]&&y>j1[v1])
{
while(x!=w1[v1])
{
line(x,y,x+1,y-s);
delay(10);
x=x+1;
y=y-s;
i=i+1;
}
}}
void ssp()
{
d2=y1=32767;
setcolor(RED);
e1=e;
for(i=0;i<n;i++)
{
arr1[i]=v[i];
arr[i]=v[i];
}
while(e1!=s)
{
var=a[e1][arr1[e1]]=a[arr1[e1]][e1];
a[e1][arr1[e1]]=a[arr1[e1]][e1]=32767;
for(i=0;i<n;i++)
{
v[i]=32767;
d[i]=32767;
p[i]=0;
}
w=s;d[s]=0;
v[s]=s;
td=0;
dijkstra(s,e,v,d,p,a,n);
if(d2<y1)
{
y1=d2;
for(i=0;i<n;i++)
arr[i]=v[i];
}
a[e1][arr1[e1]]=a[arr1[e1]][e1]=var;
e1=arr1[e1];
}}
void path()
{
while(w!=s)
{
if(count==0)
{
draw(w,v[w]);
w=v[w];
}
else
{
draw(w,arr[w]);
w=arr[w];
}}}
void initial()
{
line(w1[0],j1[0],w1[1],j1[1]);
line(w1[0],j1[0],w1[3],j1[3]);
line(w1[1],j1[1],w1[5],j1[5]);
line(w1[1],j1[1],w1[2],j1[2]);
line(w1[2],j1[2],w1[4],j1[4]);
line(w1[2],j1[2],w1[3],j1[3]);
line(w1[3],j1[3],w1[7],j1[7]);
line(w1[4],j1[4],w1[5],j1[5]);
line(w1[4],j1[4],w1[7],j1[7]);
line(w1[5],j1[5],w1[6],j1[6]);
line(w1[6],j1[6],w1[7],j1[7]);
}