Anonymous Anonymous - 4 days ago
29 0

Graphical representation of Delhi metro.

C++

DS mini Project(3rd sem)

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