DSL_Assignment6

//Graph DFS and BFS traversal
//Pratham Doke 21125 F1s
#include <queue>
#include <stack>

#include <iostream>
#define SIZE 7
using namespace std;

// Queue Data structure;
template <typename T>
class Stack
{
    struct node
    {
        T data;
        node *next;

        node()
        {
            data = '\0';
            next = nullptr;
        }

        node(T x)
        {
            data = x;
            next = nullptr;
        }
    };

    node *head;

public:
    stack()
    {
        head = nullptr;
    }

    int empty()
    {
        if (head == NULL)
        {
            return 0;
        }
        return 1;
    }

    void push(T m)
    {
        if (head == nullptr)
        {
            node *newnode = new node(m);
            head = newnode;
        }
        else
        {
            node *newnode = new node(m);
            newnode->next = head;
            head = newnode;
        }
    }

    T pop()
    {
        if (head == nullptr)
        {
            cout << "\nStack is empty!!!" << endl;
        }
        else
        {
            T val;
            node *temp = head;
            val = temp->data;
            head = temp->next;
            delete temp;
            return val;
        }
    }

    void display()
    {
        node *ptr = head;
        while (ptr != nullptr)
        {
            cout << ptr->data << " ";
            ptr = ptr->next;
        }
    }
};
// Queue Data Structure
template <typename X>
class Queue
{
    class Qnode
    {
        X data;
        Qnode *next;

    public:
        Qnode(X x)
        {
            data = x;
            next = NULL;
        }

        friend class Queue;
    };

    Qnode *front, *rear;
    int cnt;

public:
    Queue()
    {
        cnt = 0;
        front = rear = NULL;
    }

    int empty()
    {
        if (cnt == 0)
        {
            return 0;
        }
        return 1;
    }

    void push(X x)
    {
        Qnode *temp = new Qnode(x);
        if (rear == NULL)
        {
            front = rear = temp;
            cnt++;
        }
        else
        {
            rear->next = temp;
            rear = temp;
            cnt++;
        }
    }

    void pop()
    {
        if (cnt == 0)
        {
            cout << "\nQueue is empty!!!" << endl;
        }
        else
        {
            Qnode *temp = front;
            front = temp->next;
            delete temp;
            cnt--;
        }
    }

    X Front()
    {
        return front->data;
    }

    void display()
    {
        Qnode *temp = front;
        while (temp != nullptr)
        {
            cout << " | " << temp->data << " | ";
            temp = temp->next;
        }
    }
};
// For graph
class node
{
    int data;
    node *next;

public:
    node(int x)
    {
        data = x;
        next = NULL;
    }

    friend class graph;
};

class graph
{
    node *vertex[SIZE];

public:
    graph()
    {
        for (int i = 0; i < SIZE; i++)
        {
            vertex[i] = NULL;
        }
    }

    int check1(node *ptr, int data)
    {
        node *p1 = ptr;
        while (p1 = NULL)
        {
            if (p1->data == data)
            {
                return 0;
            }
            p1 = p1->next;
        }
        return 1;
    }

    void insert(int srs)
    {
        int des, td;
        int cnt = 0;
        if (srs < SIZE)
        {
            cout << "\nHow many points you want to add: ";
            cin >> td;
            while (td != cnt)
            {
                cout << "\nEnter the point: ";
                cin >> des;
                node *point = new node(des);

                if (vertex[srs] == NULL)
                {
                    vertex[srs] = point;
                    cnt++;
                }
                else
                {
                    bool b1 = true;
                    node *p = vertex[srs];
                    while (p->next != NULL)
                    {
                        if (p->data == des)
                        {
                            b1 = false;
                            break;
                        }
                        p = p->next;
                    }
                    if (b1)
                    {
                        p->next = point;
                        cnt++;
                    }
                    else
                    {
                        cout << "\nPoint already exist!!!" << endl;
                        delete point;
                    }
                }
            }
        }
        else
        {
            cout << "\nEnter Valid Vertex!!!" << endl;
        }
    }

    void display()
    {
        for (int i = 0; i < SIZE; i++)
        {
            node *ptr = vertex[i];
            cout << "Vertex: " << i << "-----";
            while (ptr != nullptr)
            {
                cout << " | " << ptr->data << " | "
                     << "---->";
                ptr = ptr->next;
            }
            cout << endl;
        }
    }

    void BFS(int v)
    {
        node *ptr;
        // Queue q;
        queue<int> q;
        int visited[SIZE], w;
        for (int i = 0; i < SIZE; i++)
        {
            visited[i] = 0;
        }
        q.push(v);
        visited[v] = 1;
        cout << "\nVisit: " << v << endl;
        while (!q.empty())
        {
            v = q.front();
            q.pop();
            for (ptr = vertex[v]; ptr != NULL; ptr = ptr->next)
            {
                w = ptr->data;
                if (visited[w] == 0)
                {
                    q.push(w);
                    visited[w] = 1;
                    cout << "\nVisit: " << w << endl;
                }
            }
        }
    }

    void DFS(int v)
    {
        node *ptr;
        int visited[SIZE];
        for (int i = 0; i < SIZE; i++)
        {
            visited[i] = 0;
        }
        int w;
        stack<int> s;
        s.push(v);
        visited[v] = 1;
        // cout << "Top: " << s.top() << endl;
        while (!s.empty())
        {
            w = s.top();
            s.pop();
            cout << "\nVisit: " << w << endl;
            for (ptr = vertex[w]; ptr != NULL; ptr = ptr->next)
            {
                if (visited[ptr->data] == 0)
                {
                    s.push(ptr->data);
                    visited[ptr->data] = 1;
                }
            }
        }
    }
};

int main()
{
    graph g;
    int choice;
    while (1)
    {
        cout << "\n1.To Insert a point .\n2.To Display. \n3.BFS display \n4.DFS display \n5.To Exit!!!" << endl;
        cout << "\nEnter the choice: ";
        cin >> choice;
        if (choice == 1)
        {
            int srs;
            cout << "\nEnter the vertex: ";
            cin >> srs;
            g.insert(srs);
        }
        else if (choice == 2)
        {
            g.display();
        }
        else if (choice == 3)
        {
            int v;
            cout << "\nEnter the start point: ";
            cin >> v;
            g.BFS(v);
        }
        else if (choice == 4)
        {
            int v;
            cout << "\nEnter the start point: ";
            cin >> v;
            g.DFS(v);
        }
        else if (choice == 5)
        {
            break;
        }
    }

    return 0;
}