Thread: Graph data structure

  1. #1
    Registered User
    Join Date
    Feb 2021
    Posts
    19

    Graph data structure

    I'm trying to code a function that checks if there is an edge between two nodes in directed graph. I found the code for this function in C++ on the internet and rewrote it into C, but i get error, can someone please help me!

    the code in C++
    link to the code : Find the path between given vertices in a directed graph – Techie Delight

    Graph data structure-1-jpg
    Graph data structure-2-jpg
    Graph data structure-3-jpg
    Code:
    The code that I wrote in C
    
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #define SIZE 40
    
    
    struct AdjListNode
    {
        int dest;
        struct AdjListNode* next;
    };
    
    
    
    
    struct AdjList
    {
        struct AdjListNode *head;
    }*Head;
    
    
    
    
    struct Graph
    {
        int V;
        struct AdjList* array;
        int * visited;
    };
    
    
    
    
    struct AdjListNode* newAdjListNode(int dest)
    {
        struct AdjListNode* newNode =
         (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
        newNode->dest = dest;
        newNode->next = NULL;
        return newNode;
    }
    
    
    struct Graph* createGraph(int V)
    {
        struct Graph* graph =
            (struct Graph*) malloc(sizeof(struct Graph));
        graph->V = V;
    
    
        // Create an array of adjacency lists.  Size of
        // array will be V
        graph->array =
          (struct AdjList*) malloc(V * sizeof(struct AdjList));
    
    
        // Initialize each adjacency list as empty by
        // making head as NULL
        int i;
        for (i = 0; i < V; ++i)
            graph->array[i].head = NULL;
    
    
        return graph;
    }
    
    
    int countVertices(struct Graph * graph){
    
    
        return graph->V;
    }
    
    
    int countEdges(struct Graph* graph){
        int v = countVertices(graph);
        struct AdjListNode* node = NULL;
        int sum = 0;
    
    
        for(int i = 0; i < v; i++){
            node = graph->array[i].head;
            while(node != NULL){
                node = node->next;
                sum++;
            }
        }
    
    
        return sum/2;
    }
    
    
    void addEdge(struct Graph* graph, int src, int dest)
    {
        // Add an edge from src to dest.  A new node is
        // added to the adjacency list of src.  The node
        // is added at the beginning
        struct AdjListNode* newNode = newAdjListNode(dest);
        newNode->next = graph->array[src].head;
        graph->array[src].head = newNode;
    
    
    }
    
    
    
    
    void printGraph(struct Graph* graph)
    {
        int v;
        for (v = 0; v < graph->V; ++v)
        {
            struct AdjListNode* pCrawl = graph->array[v].head;
            printf("\n Adjacency list of vertex %d\n head ", v);
            while (pCrawl)
            {
                printf("-> %d", pCrawl->dest);
                pCrawl = pCrawl->next;
            }
            printf("\n");
        }
    }
    
    
    struct queue {
      int items[SIZE];
      int front;
      int rear;
    };
    
    
    
    
    // Create a queue
    struct queue* createQueue() {
      struct queue* q = malloc(sizeof(struct queue));
      q->front = -1;
      q->rear = -1;
      return q;
    }
    
    
    // Check if the queue is empty
    int isEmpty(struct queue* q) {
      if (q->rear == -1)
        return 1;
      else
        return 0;
    }
    
    
    // Adding elements into queue
    void enqueue(struct queue* q, int value) {
      if (q->rear == SIZE - 1)
        printf("\nQueue is Full!!");
      else {
        if (q->front == -1)
          q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
      }
    }
    
    
    // Removing elements from queue
    int dequeue(struct queue* q) {
      int item;
      if (isEmpty(q)) {
        printf("Queue is empty");
        item = -1;
      } else {
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
          printf("Resetting queue ");
          q->front = q->rear = -1;
        }
      }
      return item;
    }
    
    
    
    
    
    
    bool isConnected(struct Graph* graph, int startVertex, int destVertex) {
        struct queue* q = createQueue();
    
    
        graph->visited[startVertex] = 1;
        enqueue(q, startVertex);
    
    
        while (!isEmpty(q)) {
            int currentVertex = dequeue(q);
            printf("Visited %d\n", currentVertex);
            if(currentVertex == destVertex)
                return 1;
            struct AdjListNode* temp = graph->array[currentVertex].head;
    
    
            while(temp){
                int adjVertex = temp->dest;
                if (graph->visited[adjVertex] == 0) {
                graph->visited[adjVertex] = 1;
                enqueue(q, adjVertex);
                }
                temp = temp->next;
            }
        }
        return 1;
    }
    
    
    int main()
    {
        struct Graph* graph = createGraph(4);
        addEdge(graph, 0, 1);
        addEdge(graph, 0, 2);
        addEdge(graph, 0, 3);
        addEdge(graph, 1, 2);
    
    
        int src = 1, dest = 2;
        if(isConnected(graph, src, dest)){
            printf("path exists");
        }
        else
            printf("No path");
        return 0;
    }
    Last edited by Shahiddd; 07-02-2021 at 02:33 PM.

  2. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    You aren't allocating any memory for the visited array.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  3. #3
    Registered User
    Join Date
    Feb 2021
    Posts
    19
    I allocated memory for visited array and now it prints "path exists" all the time, no matter the input.
    this is how i did it:
    Code:
    bool bfs(struct Graph* graph, int startVertex, int destVertex) {
        struct queue* q = createQueue();
    
    
        int v = countVertices(graph);
        graph->visited = (int*)malloc(v * sizeof(int));
    
    
        graph->visited[startVertex] = 1;
        enqueue(q, startVertex);
    
    
        while (!isEmpty(q)) {
            //printQueue(q);
            int currentVertex = q->items[q->front];
            currentVertex = dequeue(q);
            //printf("Visited %d\n", currentVertex);
            if(currentVertex == destVertex)
                return 1;
            struct AdjListNode* temp = graph->array[currentVertex].head;
    
    
            while(temp){
                int adjVertex = temp->dest;
                if (graph->visited[adjVertex] == 0) {
                graph->visited[adjVertex] = 1;
                enqueue(q, adjVertex);
                }
                temp = temp->next;
            }
        }
        return 1;
    }
    What did i do wrong this time?

  4. #4
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Quote Originally Posted by Shahiddd View Post
    I allocated memory for visited array and now it prints "path exists" all the time, no matter the input.
    this is how i did it:
    Code:
    bool bfs(struct Graph* graph, int startVertex, int destVertex) {
        struct queue* q = createQueue();
    
    
        int v = countVertices(graph);
        graph->visited = (int*)malloc(v * sizeof(int));
    
    
        graph->visited[startVertex] = 1;
        enqueue(q, startVertex);
    
    
        while (!isEmpty(q)) {
            //printQueue(q);
            int currentVertex = q->items[q->front];
            currentVertex = dequeue(q);
            //printf("Visited %d\n", currentVertex);
            if(currentVertex == destVertex)
                return 1;
            struct AdjListNode* temp = graph->array[currentVertex].head;
    
    
            while(temp){
                int adjVertex = temp->dest;
                if (graph->visited[adjVertex] == 0) {
                graph->visited[adjVertex] = 1;
                enqueue(q, adjVertex);
                }
                temp = temp->next;
            }
        }
        return 1;
    }
    What did i do wrong this time?
    What is the lifetime of the data?
    Because you appear to delete the data at the top of the function and you never give it a good initial value.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  5. #5
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    All of your return paths return 1.
    Presumably the last one should return 0.
    A little inaccuracy saves tons of explanation. - H.H. Munro

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. graph, curve, plot data
    By carl mckenzie in forum C Programming
    Replies: 1
    Last Post: 04-13-2011, 04:43 PM
  2. Printing a graph with data read in from a file
    By levitylek in forum C Programming
    Replies: 1
    Last Post: 11-17-2010, 05:21 PM
  3. Reading in a file and printing out a graph from the data
    By levitylek in forum C Programming
    Replies: 3
    Last Post: 10-26-2010, 07:32 PM
  4. trying to implement graph(data structure)
    By creeping death in forum C Programming
    Replies: 2
    Last Post: 10-15-2008, 01:10 AM
  5. get the data and plot the graph
    By lwong in forum Windows Programming
    Replies: 3
    Last Post: 01-01-2004, 09:00 AM

Tags for this Thread