Practical 8. Implement an Algorithm for detecting cycle in given graph G :Accept graph as input from fileAccept graph as input in the form of adjacency list Accept graph as input in the form of adjacency matrix.

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX_NODES 100

// Structure to represent a graph using an adjacency list

typedef struct Node {

    int vertex;

    struct Node* next;

} Node;

// Structure for the adjacency list

typedef struct Graph {

    Node* adjList[MAX_NODES];

    int numVertices;

} Graph;

// Function prototypes

Graph* createGraph(int vertices);

void addEdge(Graph* graph, int src, int dest);

bool isCyclicUtil(Graph* graph, int v, bool visited[], bool* recStack);

bool isCyclicGraph(Graph* graph);

void readGraphFromFile(Graph* graph, const char* filename);

void printAdjacencyList(Graph* graph);

void readAdjacencyMatrix(Graph* graph, int matrix[MAX_NODES][MAX_NODES]);

// Function to create a graph

Graph* createGraph(int vertices) {

    Graph* graph = (Graph*)malloc(sizeof(Graph));

    graph->numVertices = vertices;

    for (int i = 0; i < vertices; i++) {

        graph->adjList[i] = NULL;

    }

    return graph;

}

// Function to add an edge to the graph

void addEdge(Graph* graph, int src, int dest) {

    Node* newNode = (Node*)malloc(sizeof(Node));

    newNode->vertex = dest;

    newNode->next = graph->adjList[src];

    graph->adjList[src] = newNode;

}

// DFS function to check for cycles

bool isCyclicUtil(Graph* graph, int v, bool visited[], bool* recStack) {

    if (!visited[v]) {

        visited[v] = true;

        recStack[v] = true;

        Node* temp = graph->adjList[v];

        while (temp != NULL) {

            if (!visited[temp->vertex] && isCyclicUtil(graph, temp->vertex, visited, recStack)) {

                return true;

            } else if (recStack[temp->vertex]) {

                return true;

            }

            temp = temp->next;

        }

    }

    recStack[v] = false;

    return false;

}

// Function to detect cycles in the graph

bool isCyclicGraph(Graph* graph) {

    bool visited[MAX_NODES] = {false};

    bool recStack[MAX_NODES] = {false};

    for (int i = 0; i < graph->numVertices; i++) {

        if (isCyclicUtil(graph, i, visited, recStack)) {

            return true;

        }

    }

    return false;

}

// Function to read graph from a file

void readGraphFromFile(Graph* graph, const char* filename) {

    FILE* file = fopen(filename, "r");

    if (!file) {

        perror("Unable to open file");

        exit(EXIT_FAILURE);

    }

    int src, dest;

    while (fscanf(file, "%d %d", &src, &dest) != EOF) {

        addEdge(graph, src, dest);

    }

    fclose(file);

}

// Function to print adjacency list

void printAdjacencyList(Graph* graph) {

    for (int i = 0; i < graph->numVertices; i++) {

        printf("%d:", i);

        Node* temp = graph->adjList[i];

        while (temp) {

            printf(" -> %d", temp->vertex);

            temp = temp->next;

        }

        printf("\n");

    }

}

// Function to read adjacency matrix

void readAdjacencyMatrix(Graph* graph, int matrix[MAX_NODES][MAX_NODES]) {

    for (int i = 0; i < graph->numVertices; i++) {

        for (int j = 0; j < graph->numVertices; j++) {

            if (matrix[i][j]) {

                addEdge(graph, i, j);

            }

        }

    }

}

int main() {

    int choice, vertices;

    Graph* graph;

    printf("Choose input method:\n1. Read graph from file\n2. Adjacency list\n3. Adjacency matrix\n");

    scanf("%d", &choice);

    switch (choice) {

        case 1:

            printf("Enter the number of vertices: ");

            scanf("%d", &vertices);

            graph = createGraph(vertices);

            printf("Enter the filename: ");

            char filename[100];

            scanf("%s", filename);

            readGraphFromFile(graph, filename);

            break;

        case 2:

            printf("Enter the number of vertices: ");

            scanf("%d", &vertices);

            graph = createGraph(vertices);

            printf("Enter edges (src dest) terminated by -1 -1:\n");

            int src, dest;

            while (true) {

                scanf("%d %d", &src, &dest);

                if (src == -1 && dest == -1) break;

                addEdge(graph, src, dest);

            }

            break;

        case 3:

            printf("Enter the number of vertices: ");

            scanf("%d", &vertices);

            graph = createGraph(vertices);

            int matrix[MAX_NODES][MAX_NODES];

            printf("Enter adjacency matrix (%d x %d):\n", vertices, vertices);

            for (int i = 0; i < vertices; i++) {

                for (int j = 0; j < vertices; j++) {

                    scanf("%d", &matrix[i][j]);

                }

            }

            readAdjacencyMatrix(graph, matrix);

            break;

        default:

            printf("Invalid choice!\n");

            return 1;

    }

    printAdjacencyList(graph);

    if (isCyclicGraph(graph)) {

        printf("Graph contains a cycle.\n");

    } else {

        printf("Graph does not contain a cycle.\n");

    }

    return 0;

}