GraphAdjM.cpp

#include <iostream>
#include <vector>
using namespace std;

const int Size = 20;

struct Stack
{
    int arr[Size];
    int top = -1;
};

struct Queue
{
    int capacity = Size;
    int front = -1;
    int rear = -1;
    int *data = new int[capacity];
};
// Push Function
void push(Stack &stack, int value)
{
    if (stack.top == Size - 1)
    {
        cout << "Stack Overflow! You cannot push more Elements " << value << endl;
        return;
    }
    stack.arr[++stack.top] = value;
}
// Pop Functon
int pop(Stack &stack)
{
    if (stack.top == -1)
    {
        cout << "Stack Underflow! You cannot pop more elements." << endl;
        return -1;
    }
    return stack.arr[stack.top--];
}
// Display Stack
void displayStack(Stack &stack)
{
    if (stack.top == -1)
    {
        cout << "Stack is empty." << endl;
        return;
    }
    for (int i = 0; i <= stack.top; i++)
    {
        cout << stack.arr[i] << "->";
    }
    cout << endl;
}
// Queue
void EnQueue(Queue &q, int value)
{
    if (q.rear == q.capacity - 1)
    {
        cout << "The Queue is Full" << endl;
        return;
    }
    q.rear++;
    q.data[q.rear] = value;
    if (q.front == -1 || q.front > q.rear) // Queue empty
    {
        q.front = 0;
    }
    // cout<<q.data[q.rear]<<endl;
}
int DeQueue(Queue &q)
{
    if (q.front == -1 || q.front > q.rear) // Queue empty
    {
        return -1;
    }
    int temp = q.data[q.front];
    q.front++;
    if (q.front == -1 || q.front > q.rear)
    {
        q.front = -1;
        q.rear = -1;
    }
    return temp;
}
void displayQueue(Queue &q)
{
    if (q.front == -1 || q.front > q.rear)
    {
        cout << "Queue is empty" << endl;
        return;
    }
    cout << "Queue:  ";
    for (int i = q.front; i <= q.rear; i++)
    {
        cout << q.data[i] << " ";
    }
    cout << endl;
}
void dirAddEdges(vector<vector<int>> &arr)
{
    int connection, edges;
    int Size = arr.size();
    // directed
    for (int i = 0; i < Size; i++)
    {
        cout << "Enter no of edges connected to " << i << " :";
        cin >> edges;
        for (size_t j = 0; j < edges; j++)
        {
            cout << "Enter Edge: ";
            cin >> connection;
            arr[i][connection] = 1;
        }
    }
}
void dirDegree(vector<vector<int>> &arr)
{
    int Size = arr.size();
    // directed
    int indegree;
    int outdegree;
    for (size_t i = 0; i < Size; i++)
    {
        indegree = 0;
        outdegree = 0;
        for (size_t j = 0; j < Size; j++)
        {
            if (arr[i][j] == 1)
            {
                ++indegree;
            }
            else if (arr[j][i] == 1)
            {
                ++outdegree;
            }
        }
        cout << "In-Deg(" << i << ")" << " = " << indegree << endl;
        cout << "Out-Deg(" << i << ")" << " = " << outdegree << endl;
    }
}
void unDirAddEdges(vector<vector<int>> &arr)
{
    int connection, edges;
    int Size = arr.size();
    // directed
    for (int i = 0; i < Size; i++)
    {
        cout << "Enter no of edges connected to " << i << " :";
        cin >> edges;
        for (size_t j = 0; j < edges; j++)
        {
            cout << "Enter Edge: ";
            cin >> connection;
            arr[i][connection] = 1;
            arr[connection][i] = 1;
        }
    }
}
void unDirDegree(vector<vector<int>> &arr)
{
    int Size = arr.size();
    int degree;
    for (size_t i = 0; i < Size; i++)
    {
        degree = 0;
        for (size_t j = 0; j < Size; j++)
        {
            if (arr[i][j] == 1)
            {
                ++degree;
            }
        }
        cout << "Deg(" << i << ")" << " = " << degree << endl;
    }
}
void display(vector<vector<int>> &arr)
{
    int Size = arr.size();
    // display
    for (size_t i = 0; i < Size; i++)
    {
        for (size_t j = 0; j < Size; j++)
        {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
}
void addVertex(vector<vector<int>> &arr)
{
    int size = arr.size();
    // appending a row
    arr.push_back(vector<int>(size, 0));
    // appending a col in each row
    for (size_t i = 0; i < size + 1; i++)
    {
        arr[i].push_back(0);
    }
}
void removeVertex(vector<vector<int>> &arr, int vertex)
{
    int size = arr.size();
    // removing the (vetex)th row
    arr.erase(arr.begin() + vertex);
    // removing the (vertex)th col
    for (size_t i = 0; i < size - 1; i++)
    {
        arr[i].erase(arr[i].begin() + vertex);
    }
}
// void addEdge(vector<vector<int>>& arr,int vertex,int edge){
//     arr[vertex][edge] = 1;
// }
void path(vector<vector<int>> &arr, Stack &stack, int from, int to)
{
    int size = arr.size();
    vector<int> visited(size, 0); // boolean array to check which node has been visited
    int curr = from;
    push(stack, from); // push the initial node in stack
    visited[from] = 1; // mark it as visited
    bool flag = false;
    for (int i = 0; i < size; i++)
    {
        // check for the 1st connecting edge
        if (arr[curr][i] == 1)
        {
            // check whether it has been alrady visited
            if (visited[i] == 0)
            {
                push(stack, i);
                visited[i] = 1;
                // moving to the ith row to find the next '1' in the arr
                curr = i;
                // if we reached the destination edge then break the loop
                if (curr == to)
                {
                    flag = true;
                    break;
                }
                else // reset to 0 and start looking for '1' in that row
                {
                    i = -1;
                }
            }
        }
        // if we reach the last vertex in that row and '1' is not found then backtrack to prev vertex in stack
        else if (i == size - 1 && flag == false && stack.top != -1)
        {
            curr = stack.arr[stack.top - 1]; // move to prev node
            pop(stack);
            // if stack gets empty, means path not found
            if (stack.top == -1)
            {
                break;
            }
            else
            {
                i = curr + 1; // after backtracking move to the next index
            }
        }
    }
    if (flag == true)
    {
        displayStack(stack);
    }
    else
    {
        cout << "Path does not exists" << endl;
    }
}
bool isCyclic(vector<vector<int>> arr, Stack &stack, int vertex)
{
    int size = arr.size();
    int curr = vertex; // starting from the vertex in adj matrix
    push(stack, curr); // push the initial vertex in stack
    bool flag = false;

    for (int i = 0; i < size; i++)
    {
        // check for the 1st connecting edge
        if (arr[curr][i] == 1)
        {
            // if the stack contains only the source vertex, directly push the connecting edge
            if (stack.top == 0)
            {
                push(stack, i);
                curr = i;
                i = -1;
            }
            // check whether it has been alrady visited
            else if (stack.arr[stack.top - 1] != i)
            {
                push(stack, i);
                // moving to the ith row to find the next '1' in the arr
                curr = i;
                // if we reached the destination edge then break the loop
                if (curr == vertex)
                {
                    flag = true;
                    break;
                }
                else // reset to 0 and start looking for '1' in that row
                {
                    i = -1;
                }
            }
        }
        // if we reach the last vertex in that row and '1' is not found then backtrack to prev vertex in stack
        else if (i == size - 1 && flag == false && stack.top != -1)
        {
            // save the curr position so that when we backtrack we start looking forward from that position
            int index = curr;
            curr = stack.arr[stack.top - 1]; // move to prev vertex
            pop(stack);
            // if stack gets empty, means path not found
            if (stack.top == -1)
            {
                break;
            }
            else
            {
                i = index + 1; // after backtracking move to the next index
            }
        }
    }
    //displayStack(stack);
    return flag;
}
void BFS(vector<vector<int>> arr, Queue &q, int start)
{
    int size = arr.size();
    vector<int> visited(size, 0); // boolean array to check which node has been visited
    EnQueue(q, start);            // push starting vertex in the queue
    visited[start] = 1;           // mark it as visited
    while (q.front <= q.rear)
    {
        // deque the vertex and start adding it's connection vertices in the queue
        int curr = DeQueue(q);
        // if Queue gets empty
        if (curr == -1)
        {
            break;
        }
        cout << curr << "->"; // output vertex
        for (int i = 0; i < size; i++)
        {
            if (arr[curr][i] == 1)
            {
                if (visited[i] == 0)
                {
                    EnQueue(q, i);  // store the curr vertex's connections
                    visited[i] = 1; // mark it as visited
                }
            }
        }
    }
}
void DFS(vector<vector<int>> arr, Stack &stack, int start)
{
    int size = arr.size();
    vector<int> visited(size, 0); // boolean array to check which node has been visited
    push(stack, start);           // push starting vertex in the stack
    visited[start] = 1;           // mark it as visited
    while (stack.top != -1)
    {
        // pop the vertex and start adding it's connection vertex in stack
        int curr = stack.arr[stack.top];
        cout << curr << "->"; // output vertex
        bool moved = false;
        for (int i = 0; i < size; i++)
        {
            if (arr[curr][i] == 1)
            {
                if (visited[i] == 0)
                {
                    push(stack, i); // store the curr vertex's connection
                    visited[i] = 1; // mark it as visited
                    moved = true;
                    break;
                }
            }
        }
        if (moved == false)
        {
            pop(stack);
        }
    }
    // displayStack(stack);
}
int main()
{
    int option;
    cout << "1->Directed" << endl;
    cout << "2->Un-Directed" << endl;
    cin >> option;
    int n;
    cout << "Enter number of Vertices: ";
    cin >> n;
    // Initialize 2d-matrix vector of vectors with 0
    vector<vector<int>> arr(n, vector<int>(n, 0));
    int vertex;
    Stack stack;
    bool flag = false; // if cycle exists or not
    Queue q;

    // Directed
    if (option == 1)
    {
        dirAddEdges(arr);
        dirDegree(arr);
        display(arr);
        //addVertex(arr);
        //display(arr);
        path(arr, stack, 0, 6);
        for (size_t i = 0; i < arr.size(); i++)
        {
            flag = isCyclic(arr, stack, i);
            if (flag == true)
            {
                cout << "Graph is Cyclic";
                displayStack(stack);
                cout<<endl;
                break;
            }
        }
        if (!flag)
        {
            cout << "Graph is A-Cyclic" << endl;
        }
        //BFS(arr, q, 0);
        //cout<<endl;
        DFS(arr, stack, 0);
    }
    // Un-directed
    else
    {
        unDirAddEdges(arr);
        unDirDegree(arr);
        display(arr);
        //addVertex(arr);
        //display(arr);
        path(arr, stack, 3, 6);

        for (size_t i = 0; i < arr.size(); i++)
        {
            flag = isCyclic(arr, stack, i);
            if (flag == true)
            {
                cout << "Graph is Cyclic: ";
                displayStack(stack);
                cout<<endl;
                break;
            }
        }
        if (!flag)
        {
            cout << "Graph is A-Cyclic" << endl;
        }
        //BFS(arr, q, 0);
        DFS(arr, stack, 0);
    }

    return 0;
}