GraphAdjList.cpp

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

struct Vertex
{
    char data;
    void *start;
    Vertex *next_vertex;
    bool visited;
} *VList = NULL;
struct Adj
{
    Vertex *ref_vertex;
    Adj *next_adj;
};
const int Size = 50;

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

struct Queue
{
    int capacity = Size;
    int front = -1;
    int rear = -1;
    Vertex **vertices = new Vertex *[capacity];
};

// Push Function
void push(Stack &stack, Vertex *value)
{
    if (stack.top == Size - 1)
    {
        cout << "Stack Overflow! You cannot push more Elements " << value << endl;
        return;
    }
    stack.arr[++stack.top] = value;
}
// Pop Functon
Vertex *pop(Stack &stack)
{
    if (stack.top == -1)
    {
        return (Vertex *)NULL;
    }
    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]->data << "->";
    }
    cout << endl;
}
// Queue
void EnQueue(Queue &q, Vertex *value)
{
    if (q.rear == q.capacity - 1)
    {
        cout << "The Queue is Full" << endl;
        return;
    }
    q.rear++;
    q.vertices[q.rear] = value;
    if (q.front == -1 || q.front > q.rear) // Queue empty
    {
        q.front = 0;
    }
    // cout<<q.data[q.rear]<<endl;
}
Vertex *DeQueue(Queue &q)
{
    if (q.front == -1 || q.front > q.rear) // Queue empty
    {
        return (Vertex *)NULL;
    }
    Vertex *temp = q.vertices[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.vertices[i]->data << " ";
    }
    cout << endl;
}
void addVertex(char value)
{
    Vertex *curr = VList;
    Vertex *newVertex = new Vertex();
    newVertex->data = value;
    newVertex->visited = false;
    newVertex->next_vertex = NULL;
    if (VList == NULL)
    {
        VList = newVertex;
    }
    else
    {
        while (curr->next_vertex != NULL)
        {
            curr = curr->next_vertex;
        }
        curr->next_vertex = newVertex;
    }
}
Vertex *findVertex(char vertex)
{
    Vertex *curr = VList;
    while (curr != NULL)
    {
        if (curr->data == vertex)
        {
            break;
        }
        curr = curr->next_vertex;
    }
    return curr;
}
void addAdj(Vertex *v, char value)
{
    if (v != NULL)
    {
        Adj *newAdj = new Adj();
        newAdj->ref_vertex = findVertex(value);
        newAdj->next_adj = NULL;
        //&v->start: Get the address of start, which is a void*
        // Cast that address to Adj** — saying “treat this as a pointer to an Adj*
        //*(Adj**): Dereference that to get the actual Adj*
        // Adj*& curr: Create a reference to that Adj*, so changing curr will change v->start
        if (v->start == NULL)
        {
            v->start = newAdj;
        }
        else
        {
            Adj *curr = (Adj *)(v->start);
            while (curr->next_adj != NULL)
            {
                curr = curr->next_adj;
            }
            curr->next_adj = newAdj;
        }
    }
}
void UnDirDegree()
{
    Vertex *v = VList;
    int degree;
    while (v != NULL)
    {
        Adj *&adj = *(Adj **)(&v->start);
        degree = 0;
        while (adj != NULL)
        {
            degree++;
            adj = adj->next_adj;
        }
        cout << "Deg(" << v->data << ") = " << degree << endl;
        v = v->next_vertex;
    }
}
void DirDegree(Vertex *v)
{
    int indegree = 0;
    int outdegree = 0;
    if (v != NULL)
    {
        Adj *adj = (Adj *)v->start;
        while (adj != NULL)
        {
            outdegree++;
            adj = adj->next_adj;
        }
        cout << "Out-Deg(" << v->data << ") = " << outdegree << endl;

        Vertex *curr = VList;
        while (curr != NULL)
        {
            Adj *adj2 = (Adj *)curr->start;
            while (adj2 != NULL)
            {
                if (adj2->ref_vertex == v)
                {
                    indegree++;
                    break;
                }
                adj2 = adj2->next_adj;
            }
            curr = curr->next_vertex;
        }
        cout << "In-Deg(" << v->data << ") = " << indegree << endl;
    }
}
void displayAdj(Vertex *v)
{
    if (v != NULL)
    {
        Adj *curr = (Adj *)v->start;
        cout << v->data << ": ";
        while (curr != NULL)
        {
            cout << curr->ref_vertex->data << "->";
            curr = curr->next_adj;
        }
        cout << "NULL";
        cout << endl;
    }
}
void displayVertices()
{
    Vertex *curr = VList;
    while (curr != NULL)
    {
        cout << curr->data << "->";
        curr = curr->next_vertex;
    }
    cout << "NULL";
}
void BFS(Queue &q, Vertex *v)
{
    EnQueue(q, v);     // push starting vertex in the queue
    v->visited = true; // starting node marked as visited
    while (q.front <= q.rear)
    {
        // deque the vertex and start adding it's connection vertices in the queue
        Vertex *curr = DeQueue(q);
        if (curr == NULL) // if Queue gets empty
        {
            break;
        }
        cout << curr->data << "->"; // output vertex
        Adj *temp = (Adj *)curr->start;
        while (temp != NULL)
        {
            if (temp->ref_vertex->visited == false)
            {
                EnQueue(q, temp->ref_vertex);     // store the curr vertex's connections
                temp->ref_vertex->visited = true; // mark it as visited
            }
            temp = temp->next_adj;
        }
    }
}
void DFS(Stack &stack, Vertex *v)
{
    push(stack, v);    // push starting vertex in the queue
    v->visited = true; // starting node marked as visited

    while (stack.top != -1)
    {
        // pop the vertex and start adding it's connection vertices in the stack
        Vertex *curr = stack.arr[stack.top];
        if (curr->visited == false)
        {
            cout << curr->data << "->"; // output vertex
        }
        Adj *temp = (Adj *)curr->start;
        bool moved = false;
        while (temp != NULL)
        {
            if (temp->ref_vertex != NULL && temp->ref_vertex->visited == false)
            {
                push(stack, temp->ref_vertex);    // store the curr vertex's connections
                temp->ref_vertex->visited = true; // mark it as visited
                moved = true;
                break;
            }
            temp = temp->next_adj;
        }
        if (moved == false)
        {
            pop(stack);
        }
    }
}
bool isCyclic(Vertex *v, Stack &stack)
{
    push(stack, v);
    Vertex *curr = stack.arr[stack.top];
    Adj *adj = (Adj *)curr->start;
    Adj* temp;
    while (adj != NULL)
    {
        temp = adj;
        bool moved = false;
        // if the stack contains only the source vertex, directly push the connecting edge
        if (stack.top == 0)
        {
            push(stack, temp->ref_vertex);
            moved = true;
            curr = stack.arr[stack.top];
            adj = (Adj *)curr->start;
        }
        else if (temp->ref_vertex != NULL && stack.arr[stack.top - 1] != temp->ref_vertex)
        {
            push(stack, temp->ref_vertex);    // store the curr vertex's connections
            moved = true;
            if (temp->ref_vertex == v)
            {
                displayStack(stack);
                return true;
            }
            curr = stack.arr[stack.top];
            adj = (Adj *)curr->start;
        }
        else{
            adj = adj->next_adj;
        }
    }
    displayStack(stack);
    return false;
}
int main(int argc, char const *argv[])
{
    char data;
    int edges;
    int option;
    cout << "1->Un-Directed" << endl;
    cout << "2->Directed" << endl;
    cin >> option;
    int n;
    cout << "Enter number of Vertices: ";
    cin >> n;

    Queue q;
    Stack stack;

    for (int i = 0; i < n; i++)
    {
        cout << "Enter the vetex's data: ";
        cin >> data;
        if (data >= 'A' && data <= 'Z')
        {
            addVertex(data);
        }
    }
    displayVertices();
    cout << endl;
    // Un-Directed
    if (option == 1)
    {
        Vertex *v = VList;
        while (v != NULL)
        {
            cout << "Enter number of vertices that " << v->data << " points to: ";
            cin >> edges;
            if (edges > 0)
            {
                for (size_t i = 0; i < edges; i++)
                {
                    cout << "Enter the vertex adjacent to " << v->data << ": ";
                    cin >> data;
                    if (data >= 'A' && data <= 'Z')
                    {
                        addAdj(v, data);
                        Vertex *temp = findVertex(data);
                        addAdj(temp, v->data);
                    }
                }
            }
            v = v->next_vertex;
        }
        v = VList;
        while (v != NULL)
        {
            displayAdj(v);
            v = v->next_vertex;
        }
        v = VList;
        cout << "BFS: ";
        BFS(q, v);

        cout << endl;
        // reset all visited
        Vertex *temp = VList;
        while (temp != NULL)
        {
            temp->visited = false;
            temp = temp->next_vertex;
        }

        v = VList;
        cout<<"Cyclic ?: "<<isCyclic(v,stack);
        // cout << "DFS: ";
        // DFS(stack, v);
    }
    // Directed
    else
    {
        Vertex *v = VList;
        while (v != NULL)
        {
            cout << "Enter number of vertices that " << v->data << " points to: ";
            cin >> edges;
            if (edges > 0)
            {
                for (int i = 0; i < edges; i++)
                {
                    cout << "Enter the vertex adjacent to " << v->data << ": ";
                    cin >> data;
                    if (data >= 'A' && data <= 'Z')
                    {
                        addAdj(v, data); // Only one direction
                    }
                }
            }
            v = v->next_vertex;
        }
        v = VList;
        while (v != NULL)
        {
            displayAdj(v);
            // DirDegree(v);
            v = v->next_vertex;
        }
        v = VList;
        cout << "BFS: ";
        BFS(q, v);

        cout << endl;
        // reset all visited
        Vertex *temp = VList;
        while (temp != NULL)
        {
            temp->visited = false;
            temp = temp->next_vertex;
        }

        v = VList;
        cout << "DFS: ";
        DFS(stack, v);
    }
    return 0;
}