AdjacencyListAllOp

#include<stdio.h>
#include<stdlib.h>
struct edge;
struct vertex
{
        int info;
        struct vertex * next_vertex;//next vertex in link list of vertices
        struct edge * first_edge; //first edge of adjacency list of this vertex
};

struct edge
{
        struct vertex * dest_vertex; // destination vertex of the edge
        struct edge * next_edge; // next edge of adjacency list
};
struct vertex * start = NULL;

/*Declaration of all SEVEN function being used in this code*/
struct vertex * findvertex(int);
void InsertVertex(int);
void InsertEdge(int, int);
void DeleteVertex(int);
void DeleteEdge(int, int);
void DeleteIncomingEdges(int);
void Display();


int main()
{   int choice,origin,destination,u;
    while(1)
        {   printf("1.Insert a vetex: \n");
            printf("2.Insert an edge:  \n");
            printf("3.Delete a vetex: \n");
            printf("4.Delete an edge: \n");
            printf("5.Display \n");
            printf("6.Exit\n");

            printf("Enter your choice: \n");
            scanf("%d",&choice);

            switch(choice)
                {   case 1: printf("Enter a vertex to be inserted: ");
                            scanf("%d",&u);
                            InsertVertex(u);
                            break;
                    case 2: printf("Enter an edge to be inserted: ");
                            scanf("%d %d",&origin,&destination);
                            InsertEdge(origin,destination);
                            break;
                    case 3: printf("Enter a vertex to be deleted: ");
                            scanf("%d",&u);
                            //call a fun to delete all incoming edges on this vertex
                            DeleteIncomingEdges(u);
                            //now call a fun to delete vertex from vertex list
                            DeleteVertex(u);
                            break;
                    case 4: printf("Enter an edge to be deleted: ");
                            scanf("%d %d",&origin,&destination);
                            DeleteEdge(origin,destination);
                            break;
                    case 5: Display();
                            break;
                    case 6: exit(1);
                    default: printf("Wrong choice: \n");
                                break;
                }//switch
        }//while
}//main

void InsertVertex(int u)
    {   struct vertex *tmp, *ptr;
        tmp = malloc(sizeof(struct vertex));//creating a node of same struct size (same memory size)
        tmp->info = u;
        tmp->first_edge = NULL;
        tmp->next_vertex = NULL;
        if(start == NULL)
            {   start = tmp;
                return;
            }
        ptr = start; // we do that so that while traversing start does not changes
        while(ptr->next_vertex != NULL)
                ptr = ptr->next_vertex;
        ptr->next_vertex=tmp;

    }//end of insertvertex


void DeleteVertex(int u)
    {       struct vertex *tmp, *ptr;
            struct edge *p, *temporary;
            /*tmp will point to the node we have to delete*/
            if(start == NULL)
                {   printf("No vertices to be deleted: \n");
                    return;
                }
        /*If vertex to be deleted is start itself or we can say the first vertex in list*/
            if(start->info == u)
                {   tmp = start;//tmp is pointing to start because it has to be deleted
                    start = start->next_vertex;
                }
            /*if vertex to be deleted is in between or last*/
            else
                {   /*first we need to traverse to find the vertex to be deletd*/
                    ptr = start; //while traversing start should not be changed
                    while(ptr->next_vertex != NULL)
                        {   /*we will traveerse up to the node just before the desired node (node to be deleted)*/
                            if(ptr->next_vertex->info == u)
                                break;
                            /*keep traversing untill we found the if condition */
                            ptr = ptr->next_vertex;
                        }
                    /*if we did not find the desired node*/
                    if(ptr->next_vertex == NULL)
                        {   printf("Vertex not found: \n");
                            return;
                        }
                    /*if vertex found*/
                    else
                        {   tmp = ptr->next_vertex;//ptr->nextvertex is the desired one
                            ptr->next_vertex = tmp->next_vertex;
                        }
                }
            /*we have found the desired vertex but before deliting it we need to free all edges going from  it*/
            p = tmp->first_edge;//p is a struct edge pointer
            while(p!= NULL)
                {   temporary = p;
                    p = p->next_edge;
                    free(temporary);
                }
            /*finally we can free tmp which is a pointer to the node to be deleted*/
                free(tmp);
    }//end of deletevertex

void InsertEdge(int origin, int destination)
    {       struct vertex *locu, *locv;
            struct edge *ptr, *tmp;
            locu = findvertex(origin);
            locv = findvertex(destination);
            /*first check both vertex are present or not*/
            if(locu == NULL)
                {   printf("Start vertex does not found, first insert %d vertex:  ", origin);
                    return;
                }
            if(locv == NULL)
                {   printf("Destination vertex doesnot found, first insert %d vertex: ",destination);
                    return;
                }

            /*tmp will point to the edge to be inserted*/

            tmp = malloc(sizeof(struct edge));
            tmp->dest_vertex = locv;
            tmp->next_edge = NULL;

            /*if origin vertex does not have any first edge*/

            if(locu->first_edge== NULL)
                {   locu->first_edge = tmp;
                    return;
                }
            ptr = locu->first_edge;

            /*Now start traversing in edges*/

            while(ptr->next_edge != NULL)
                ptr = ptr->next_edge;
            ptr->next_edge = tmp;

    }//end of insert edge

struct vertex * findvertex(int u)
    {   struct vertex *ptr, *loc;
        ptr = start;
        while(ptr != NULL)
            {   if(ptr->info == u)
                {   loc = ptr;
                    return loc;
                }
                ptr = ptr->next_vertex;
            }
            /*if no such vertex found*/
            loc = NULL;
            return loc;
    }//end of find vertex

void DeleteEdge(int origin, int destination)
    {   struct vertex *locu;
        struct edge *tmp, *ptr;
        locu = findvertex(origin);

        /*cheking whether origin vertex of the edge present or not*/

        if (locu == NULL)
            {   printf("Start vertex does not present:  \n");
                return;
            }
        /*Checking whether first edge present or not*/\

        if(locu->first_edge == NULL)
            {   printf("edge not present:  \n");
                return;
            }
        /*cheking if first edge is the 'edge' to be deleted*/

        if(locu->first_edge->dest_vertex->info == destination)
            {   tmp = locu->first_edge;
                locu->first_edge = tmp->next_edge;
                free(tmp);
                return;
            }
        /*If required edge is not the firtedge then traverse to find it*/
        ptr = locu->first_edge;
        while(ptr->next_edge != NULL)
            {   if(ptr->next_edge->dest_vertex->info == destination)
                    {   tmp = ptr->next_edge;
                        ptr->next_edge = tmp->next_edge;
                        free(tmp);
                        return;
                    }
                ptr = ptr->next_edge;
            }
        printf("Edge not present in the graph:\n");

    }//end of delete edge


void DeleteIncomingEdges(int u)
    {   struct vertex *ptr;
        struct edge *tmp, *p;
        ptr = start;
        while(ptr!=NULL)// pay attention to it here can't be ptr->next_vertex != NULL
            {   /*keep traversing untill you found a vertex with edge*/
                if(ptr->first_edge == NULL)
                    {   ptr = ptr->next_vertex;
                        continue;
                    }
                /*when found a vertex with edge then check whether it's first edge is the edge to be deleted:*/
                if(ptr->first_edge->dest_vertex->info == u)
                    {   tmp = ptr->first_edge;
                        ptr->first_edge = tmp->next_edge;
                        free(tmp);
                        continue; /*now search in other edgelist*/
                    }
                /*if the desiredlist is not the first list then traverse in edge list to find that one*/

                p = ptr->first_edge;
                while(p->next_edge != NULL)
                    {   /*checking for each edges whether it is desired edges or not*/
                        if(p->next_edge->dest_vertex->info == u)
                            {   tmp = p->next_edge;
                                p->next_edge = tmp->next_edge;
                                free(tmp);
                                continue;
                            }
                        p = p->next_edge;
                    }
                ptr = ptr->next_vertex;
            }
    }// end of delete incoming edges


void Display()
    {   struct vertex *ptr;
        struct edge *p;
        ptr = start;
            printf("\n\n");
        while(ptr != NULL)
            {   printf("%d ->",ptr->info);
                /*Now traverse through edges*/
                p = ptr->first_edge;
                while(p != NULL)
                    {   printf(" %d",p->dest_vertex->info);
                        p = p->next_edge;
                    }
                printf("\n");
                ptr = ptr->next_vertex;
            }
            printf("\n\n");
    }//end of display