Finding Cycle in Directed Graph using BFS

Question

The purpose of this code is to eliminate cycles in directed graph using BFS and this is my task to do: I have a graph and the adjacent list of each node. I want to write a bfs traversal from the start node to end node. Start by node 1 and check its adjacent list. if the checked node was visited previously, remove the edge between node 1 and that node. if no, continue with next node. After each elimination between the nodes, print the graph using printgraph() function to check if the eliminations are right or not. Once a path was found from the Starting Node to the End Node, now look for other paths to End Node by following the rules above. Continue BFS until all the edges that will create cycles are removed. Print final graph and observe that the graph is now similar to a DAG. This is my codes which I was trying to write but it gives me wrong results. Can you help me fix the code?

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
#include <string.h>
enum color { White, Gray, Black };
typedef struct list_node {
    int index;
    int time;
    int distance;
    int cost;
    struct list_node* next;
} list_node;

typedef struct node {
    int data;
    enum color color;
    list_node* head;
} node;

typedef struct graph {
    int nVertices;
    node heads[];
} graph;

typedef struct Edge {
    int source;
    int dest;
    int time;
    int distance;
    int cost;
} Edge;

Edge edgeList[100];  // Maximum 100 edges (change the size accordingly)
int edgeCount = 0;  // Number of edges added

node* new_node(int data) {
    node* z = (node*)malloc(sizeof(node));
    z->data = data;
    z->head = NULL;
    z->color = White;
    return z;
}

list_node* new_list_node(int item_index, int time, int distance, int cost) {
    list_node* z = (list_node*)malloc(sizeof(list_node));
    z->index = item_index;
    z->time = time;
    z->distance = distance;
    z->cost = cost;
    z->next = NULL;
    return z;
}

graph* new_graph(int nVertices) {
    graph* g = (graph*)malloc(sizeof(graph) + (nVertices * sizeof(node)));
    g->nVertices = nVertices;
    int i;
    for (i = 0; i < nVertices; i++) {
        node* z = new_node(-1);
        g->heads[i] = *z;
    }
    return g;
}

void add_node_to_graph(graph* g, int data) {
    node* z = new_node(data);
    int i;
    for (i = 0; i < g->nVertices; i++) {
        if (g->heads[i].data < 0) {
            g->heads[i] = *z;
            break;
        }
    }
}

int in_graph_head_list(graph* g, int data) {
    int i;
    for (i = 0; i < g->nVertices; i++) {
        if (g->heads[i].data == data)
            return 1;
    }
    return 0;
}
void printgraph(graph* g) {
    int i;
    for (i = 0; i < g->nVertices; i++) {
        node* curr_node = &(g->heads[i]);
        printf("Node %d: ", curr_node->data);
        list_node* temp = curr_node->head;
        if (temp == NULL) {
            printf("No adjacent nodes.\n");
        } else {
            while (temp != NULL) {
                int adjacent_vertex = g->heads[temp->index].data;
                printf("%d (T=%d, D=%d, C=%d)", adjacent_vertex, temp->time, temp->distance, temp->cost);
                temp = temp->next;
                if (temp != NULL) {
                    printf(" --> ");
                }
            }
            printf("\n");
        }
    }
}

void AddEdges(graph* g, int source, int dest, int time, int distance, int cost) {
    if (!in_graph_head_list(g, source)) {
        add_node_to_graph(g, source);
    }
    if (!in_graph_head_list(g, dest)) {
        add_node_to_graph(g, dest);
    }
    int i, j;
    for (i = 0; i < g->nVertices; i++) {
        if (g->heads[i].data == source) {
            int indexDest = -1;
            for (j = 0; j < g->nVertices; j++) {
                if (g->heads[j].data == dest) {
                    indexDest = j;
                    break;
                }
            }
            if (indexDest != -1) {
                list_node* n = new_list_node(indexDest, time, distance, cost);
                if (g->heads[i].head == NULL) {
                    g->heads[i].head = n;
                } else {
                    list_node* temp = g->heads[i].head;
                    while (temp->next != NULL) {
                        temp = temp->next;
                    }
                    temp->next = n;
                }
                edgeList[edgeCount].source = source;
                edgeList[edgeCount].dest = dest;
                edgeList[edgeCount].time = time;
                edgeList[edgeCount].distance = distance;
                edgeList[edgeCount].cost = cost;
                edgeCount++;
            }
            break;
        }
    }
}
typedef struct queue_node {
  node *n;
  struct queue_node *next;
}queue_node;

 

struct queue
{
    int count;
    queue_node *front;
    queue_node *rear;
};
typedef struct queue queue;

 

int is_empty_queue(queue *q)
{
  return !(q->count);
}

 

void enqueue(queue *q, node *n)
{
  queue_node *new_queue_node;
  new_queue_node = malloc(sizeof(queue_node));
  new_queue_node->n = n;
  new_queue_node->next = NULL;
  if(!is_empty_queue(q))
  {
    q->rear->next = new_queue_node;
    q->rear = new_queue_node;
  }
  else
  {
    q->front = q->rear = new_queue_node;
  }
  q->count++;
}

 

queue_node* dequeue(queue *q)
{
  queue_node *tmp;
  tmp = q->front;
  q->front = q->front->next;
  q->count--;
  return tmp;
}

 

queue* make_queue()
{
  queue *q;
  q = malloc(sizeof(queue));
  q->count = 0;
  q->front = NULL;
  q->rear = NULL;
  return q;
}

 

void print_queue(queue *q) {
  queue_node *tmp;
  tmp = q->front;
  while(tmp != NULL) {
    printf("%d\t",tmp->n->data);
    tmp = tmp->next;
  }
  printf("\n");
}

 

void bfs(graph* g, int start, int end) {
    // Create a queue for BFS
    int* queue = (int*)malloc(g->nVertices * sizeof(int));
    int front = 0, rear = 0;
    bool* visited = (bool*)malloc(g->nVertices * sizeof(bool));
    memset(visited, false, g->nVertices * sizeof(bool));

    // Mark the start node as visited and enqueue it
    visited[start-1] = true;
    queue[rear++] = start;

    // Traverse the graph using BFS
    while (front < rear) {
        int current = queue[front++];

        // Process the node (print and eliminate edges)
        printf("Processing node %d\n", g->heads[current-1].data);
        list_node* temp = g->heads[current-1].head;
        while (temp != NULL) {
            int neighbor = temp->index;
            if (visited[neighbor-1] || g->heads[neighbor-1].color != White) {
                printf("Eliminating edge from node %d to %d\n", g->heads[current-1].data, g->heads[neighbor-1].data);
                g->heads[current-1].head = temp->next;
                temp = temp->next;
            } else {
                visited[neighbor-1] = true;
                queue[rear++] = neighbor;
                temp = temp->next;
            }
        }
        g->heads[current-1].color = Black;

        // Print the graph after each elimination cycle
        printf("Result of elimination cycle: \n");
        printgraph(g);

        // Check if we reached the end node
        if (g->heads[current-1].data == end) {
            // Delete all edges back to other nodes
            for (int i = 0; i < g->nVertices; i++) {
                if (i != current-1) {
                    list_node* temp = g->heads[i].head;
                    list_node* prev = NULL;
                    while (temp != NULL) {
                        if (temp->index == end) {
                            printf("Eliminating edge from node %d to %d\n", g->heads[i].data, g->heads[temp->index-1].data);
                            if (prev == NULL) {
                                g->heads[i].head = temp->next;
                                temp = temp->next;
                            } else {
                                prev->next = temp->next;
                                temp = temp->next;
                            }
                        } else {
                            prev = temp;
                            temp = temp->next;
                        }
                    }
                }
            }
            break;
        }
    }

    free(queue);
    free(visited);
}


int main(void) {
    graph* g = new_graph(5);
    AddEdges(g, 1, 2, 1, 1, 1);
    AddEdges(g, 1, 3, 1, 1, 1);
    AddEdges(g, 2, 4, 1, 4, 5);
    AddEdges(g, 2, 3, 3, 2, 1);
    AddEdges(g, 2, 1, 2, 1, 3);
    AddEdges(g, 3, 1, 7, 1, 4);
    AddEdges(g, 3, 1, 1, 3, 2);
    AddEdges(g, 3, 4, 4, 3, 1);
    AddEdges(g, 3, 4, 1, 7, 6);
    AddEdges(g, 4, 4, 5, 3, 2);
    AddEdges(g, 4, 3, 1, 1, 1);
    AddEdges(g, 4, 2, 1, 4, 5);
    AddEdges(g, 1, 5, 8, 1, 9);
    AddEdges(g, 1, 5, 1, 8, 4);
    int startNode=1;
    int endNode=4;
    bfs(g, startNode, g->nVertices - 1);
    printf("\nGraph after removing cycles:\n");
    printgraph(g);
    return 0;
}

Answer 1

There are several issues in your code, including the following:

• There is a mix-up of subtracting 1 from 1-based positions to 0-based indexes. You have code that subtracts 1 also from indexes that are already 0-based. For instance, the index member of the list_node struct is always initialised with a 0-based index, yet elsewhere you do things like g->heads[temp->index-1], which obviously addresses the wrong entry.

• The way you eliminate a node from an adjacency list is wrong: it removes all nodes from that list up from its head up to the node you want to remove, as you always update the head member. You should update the previous node's next member in most cases (except when it is the first node).

Here is the correction of the part of the code where you have these mistakes -- comments indicate what the changes are:

void bfs(graph* g, int start, int end) {
    int* queue = malloc(g->nVertices * sizeof(int)); // don't cast
    int front = 0, rear = 0;
    bool* visited = malloc(g->nVertices * sizeof(bool)); // don't cast
    memset(visited, false, g->nVertices * sizeof(bool));
    // Turn `start` into a 0-based index, and get rid of all other -1 in
    // the code below.
    start--; 
    visited[start] = true;
    queue[rear++] = start;

    while (front < rear) {
        int current = queue[front++];
        printf("Processing node %d\n", g->heads[current].data);
        // Track the address of the node pointer that might need updating
        list_node** tempAddr = &g->heads[current].head;
        while (*tempAddr != NULL) {
            int neighbor = (*tempAddr)->index;
            if (visited[neighbor] || g->heads[neighbor].color != White) {
                printf("Eliminating edge from node %d to %d\n", 
                          g->heads[current].data, g->heads[neighbor].data);
                // Don't update head, but the pointer at the address we track:
                *tempAddr = (*tempAddr)->next;
            } else {
                visited[neighbor] = true;
                queue[rear++] = neighbor;
                // Move to the next address with a node pointer
                tempAddr = &((*tempAddr)->next);
            }
        }
        g->heads[current].color = Black;
        // rest of your code...

Answer 2

"Start by node 1 and check its adjacent list. if the checked node was visited previously, remove the edge between node 1 and that node."

Unless every node in the graph has a connection to node 1, this cannot work because the connection to node 1 will usually not exist. There is either something wrong with your algorithm, or your description of it.

More generally: when a cycle is found, by whatever algorithm, there is a difficult question: which link in the cycle should be removed. This depends on exactly what you want to do. Presumably you do not want to risk splitting your graph into two components by deleting a link at random.