#include <iostream>
#include <ctime>
#include <malloc.h>
using namespace std;

struct node //the data structure for the nodes that are being explored
{
    int data;
    struct node *next;
};

class stack //the data structure for the queue that is being used to store the nodes that are being searched through
{
    private:
        struct node *top;

    public:
        stack()
        {
            top = NULL;
        }

        void push(int indata) //pushes a node onto the top of the stack
        {
            node *p;
            if((p=(node*)malloc(sizeof(node))) == NULL)
            {
                cout << "Memory Exhausted";
                exit(0);
            }

            p = new node;
            p->data = indata;
            p->next = NULL;
            if(top != NULL)
            {
                p->next = top;
            }
            top = p;
        }

        int pop() //pops a node from the top of the stack
        {
            struct node *temp;
            int value;
            if(top == NULL)
            {
                cout << "\nThe stack is Empty" << endl;
            }

            else
            {
                temp = top;
                top = top->next;
                value = temp->data;
                delete temp;
            }
            return value;
        }

        bool isEmpty() //returns whether the stack is empty
        {
            return (top == NULL);
        }

        void display() //displays the nodes and their order in the stack
        {
            struct node *p = top;

            if(top == NULL)
            {
                cout << "\nNothing to Display\n";
            }

            else
            {
                cout << "\n The contents of stack\n";

                while(p != NULL)
                {
                    cout << p->data << endl;
                    p = p->next;
                }
            }
        }
};

class Graph //the data structure for the graph that contains the nodes and the edges between them
{
    private:
        int n;
        int **A;

    public:
        Graph(int size) //allows for variable creation of graph size
        {
            int i, j;
            if (size < 2)
                n = 2;

            else
                n = size;

            A = new int*[n];

            for (i = 0; i < n; ++i)
                A[i] = new int[n];

            for (i = 0; i < n; ++i)
                for (j = 0; j < n; ++j)
                    A[i][j] = 0;
        }

        ~Graph()
        {
            for (int i = 0; i < n; ++i)
            delete [] A[i];
            delete [] A;
        }

        bool isConnected(int x, int y) //returns whether two nodes are connected to each other
        {
            return (A[x-1][y-1] == 1);
        }

        void addEdge(int x, int y) //adds an edge connecting the two given nodes
        {
           A[x-1][y-1] = A[y-1][x-1] = 1;
        }

        void DFS(int x, int g) //the function used for the Depth-First Search
        {
            stack s;
            bool *explored = new bool[n+1]; //stores explored nodes
            bool found = false; //denotes whether the goal node has been found
            int i;
            for(i = 0; i <= n; i++) //initializes all nodes as unexplored
                explored[i] = false;
            s.push(x); //adds the initial node to the top of the stack
            explored[x] = true;

            cout << "Depth first Search starting from vertex ";
            cout << x << " : " << endl;

            while(!s.isEmpty() && !found)
            {
                int k = s.pop();
                cout << k << " ";

                if(k == g) //stops the search after the goal is found
                {
                    cout << "\n\nGoal found!";
                    found = true;
                }

                else
                {
                    for (i = n; i >= 0 ; i--) //pushes the nodes that are connected to each other, in LIFO order
                        if(isConnected(k, i) && !explored[i])
                        {
                            s.push(i);
                            explored[i] = true;
                        }
                }
            }
            cout << endl;
            delete [] explored;
        }

};

int main()
{
    Graph g(8); //creates a graph with 8 nodes
    g.addEdge(1, 2); //adds edges between nodes (this is modular and can be changed)
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 5);
    g.addEdge(2, 6);
    g.addEdge(4, 7);
    g.addEdge(4, 8);

    clock_t t1;
    t1 = clock();

    g.DFS(1, 4); //both the root5 node and the goal node can be adjusted

    float diff = (double)(clock() - t1)/CLOCKS_PER_SEC; //keeps track of the time taken to execute the search
    cout << endl << "Time taken for DFS: " << diff << endl;

    return 0;
}