Ok, this sounds trivial, but hear me out: GCC is giving me the following error when I try to compile a 7-file C program:

error: unknown type Gnode

(it's for a programming assignment due soon on Dijkstra's Algorithm). I have 7 files on my folder: pa3.c, graph.c, graph.h, pqueue.c, pqueue.h, processes.c, and processes.h, and this error appears for every mention of Gnode in the pqueue and processes files. Graph.h looks like this:

// === GRAPH.H === //
// This file contains all the functions and structs related to graphs

#ifndef __GRAPH__
#define __GRAPH__
#include"pqueue.h"
#include"processes.h"

typedef struct _graphnode {
    
    //char name;

    int distance; // Distance from source node (0 if it IS source node)
    int q_idx; // position in queue
    short weight; // Weight of the individual node. Ideally shouldn't be changed
    int position[2]; // position of the node in graph. Format is {row, col}
    struct _graphnode* prev; // The node that led to this path


} Gnode;

// Creates the Graph as a Matrix
Gnode*** create(char* filename, short* ht, short* width);

// You have just created a graph! Congratulations!
// By creating this graph, you have allocated three different times:
// - Every Row 
// - Every Collumn
// - Every Item 
// It is important that they are freed in the following order:
// Item, Collumn, Row
// As deleting the collumns, will lose you access to the items and deleting the rows will lose you access to the collumns
// so you must not need to access any of the Items before deleting the cols and any of the cols before deleting the rows
void free_graph(Gnode*** graph, short ht, short width);

#endif

the other files look like this (yes, even the comments at the top are there):

// === PQUEUE.C === //
// This file defines the functions declared in pqueue.h

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<string.h>
#include"processes.h" 
#include"graph.h"
#include"pqueue.h"

// Below this line are functions and whatnot

// === PROCESSES.C === //
// This file executes the functions declared in
// - graph.h
// - pqueue.h
// - processes.h
// and defined in 
// - graph.c
// - pqueue.c
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<string.h>
#include"processes.h" 
#include"graph.h"
#include"pqueue.h"

// below this line are functions and whatnot

// === PQUEUE.H ==== //
// This file contains all functions and structs related to the priority queue

#ifndef __PQUEUE__
#define __PQUEUE__
#include"graph.h"
#include"processes.h"

// =================================================
// [function declarations]
// =================================================

#endif

// === PROCESSES.H === //
// This file declares the functions that will be used in processes.c 

#ifndef __PROCESSES__
#define __PROCESSES__
#include"graph.h"
#include"pqueue.h"

// =================================================
// [function declarations]
// =================================================

#endif

(I would like to point out that the "function declarations" and "below this line are functions" comments aren't all that's there. I have actual functions and other things running, but I didn't want to clutter the post)

I've been compiling this with gcc -g -std=c99 -o a.out *.c but a friend suggested I add the -import flag, so I did and I found the following:

running gcc -g -std=c99 -o a.out *.c -import processes.h fixes the issues with the processes files

running gcc -g -std=c99 -o a.out *.c -import pqueue.h fixes the issues with the pqueue files

running either gcc -g -std=c99 -o a.out *.c -import processes.h pqueue.h or gcc -g -std=c99 -o a.out *.c -import processes.h -import pqueue.h (I wasn't sure which would've been correct) doesn't fix both issues. I'm not entirely sure it even fixes the issue for even one of them, but I know it certainly doesn't fix both.

I've also made sure there are no spelling mistakes in Gnode because I've copy-pasted the struct name wherever I found it after I got this error...

It was also suggested to me that Circular imports might be an issue. I tried making sure this wasn't the case (but I might've done it incorrectly, who knows, I'm open to trying this again), but when I ran again with less imports, I got the same errors

One last thing I tried is just importing everything everywhere. This also didn't fix the problem.

Below are the full files (except graph.h, becuase that one was already the full file):

// === PQUEUE.C === //
// This file defines the functions declared in pqueue.h

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<string.h>
#include"processes.h" 
#include"graph.h"
#include"pqueue.h"

PQ* PQ_init(Gnode*** graph_matrix, short ht, short width){
    // Since at the beginning, all Nodes are the same distance from the desired node ("infinity"), they can
    // go in whatever order in the Queue at first. 
    // When we start traversing the graph using BFS, we'll use PQ_updt to make sure everything's in place
    PQ* pq = malloc(sizeof(*pq));
    pq->max_idx = (ht * width) - 1;
    pq->Queue = malloc((pq->max_idx   1)*sizeof(Gnode*));
    int k = 0;

    for(int i = (ht - 1); i > -1; i--){ // We start from the bottom to the top because that way we have the bottom items first, which have weight 0
        for(int j = 0; j < width; j  ){
            graph_matrix[i][j]->q_idx = k;
            pq->Queue[k] = graph_matrix[i][j];
            k  ;
        }
    }

    return pq;
}

void swap(PQ* pq, int idx1, int idx2){
    Gnode* temp = pq->Queue[idx2];
    pq->Queue[idx2] = pq->Queue[idx1];
    pq->Queue[idx1] = temp;
    pq->Queue[idx2]->q_idx = idx2;
    pq->Queue[idx1]->q_idx = idx1;
}

void PQ_updt(PQ* pq, int idx){
    // Just implement upwards heapify starting from the value at idx... not sure how... 
    int i = idx;
    int dist_idx = (pq->Queue[idx])->distance;
    while(i >= 0){
        int idx_parent = (i - 1) / 2;
        int dist_parent = (pq->Queue[idx_parent])->distance;
        if(dist_idx < dist_parent){
            swap(pq, i, idx_parent);
            i = idx_parent;
        }
        else{
            break;
        }
    }
}

void heapify_dn(PQ* pq){
    int max_idx = pq->max_idx; //it's easier to type, OK? 
    // Initializing the main index
    int i = 0;
    // Getting the distances in the different items of the queue because they're annoying to type out
    int dist_top = (pq->Queue[0])->distance;
    while(i <= max_idx){ 
        // As long as I'm inside the heap and my "top" node isn't in the right place ^^^
        // If the left value is smaller than right
        //  switch left and "top" (top is no longer top, but I'm still calling it top)
        //  Update values for left and right based on where top now is 
        //  loop again
        // If the right value is smaller than left
        //  switch right and "top" (top is no longer top, but I'm still calling it top)
        //  Update values for left and right based on where top now is 
        //  loop again   
        int idx_left = (i * 2)   1;
        int idx_right = (i * 2)   2;    
        int dist_l = (pq->Queue[idx_left])->distance;
        int dist_r = (pq->Queue[idx_right])->distance;

        //find smallest child
        Gnode* smallest_child = (dist_l < dist_r) ? pq->Queue[idx_left] : pq->Queue[idx_right]; 
        int potential_new_i = smallest_child->q_idx;
 
        if(pq->Queue[0]->distance > smallest_child->distance){
            swap(pq, pq->Queue[i]->q_idx, smallest_child->q_idx);
            i = potential_new_i; 
        }
        else {
            break;
        }
    }
}

void PQ_dq(PQ* pq){
    // Swap the first and last elements of the queue
    swap(pq, 0, pq->max_idx);
    // Decrease the length of the queue
    pq->max_idx --;
    // Heapify Down
    heapify_dn(pq);
}

// === PROCESSES.C === //
// This file executes the functions declared in
// - graph.h
// - pqueue.h
// and defined in 
// - graph.c
// - pqueue.c
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<string.h>
#include"processes.h" 
#include"graph.h"
#include"pqueue.h"

void updt_dist(Gnode**** a_graph_mtx, int pos[2], int mtx_ht, int mtx_width){
    short curr_wt = (*a_graph_mtx)[pos[0]][pos[1]]->weight; // stores the current weight we'll be adding to the nodes in the graph
    int new_dist = (*a_graph_mtx)[pos[0]][pos[1]]->distance   curr_wt; // stores the distance from the node to all its adjacent nodes
    if(pos[0]){ // If it's not colliding with the top of the graph;
        if(new_dist < ((*a_graph_mtx)[pos[0]-1][pos[1]]->distance)){ // if my new distance is less than the distance at the node right above
            (*a_graph_mtx)[pos[0]-1][pos[1]]->distance = new_dist; // Replace the distance
            (*a_graph_mtx)[pos[0]-1][pos[1]]->prev = (*a_graph_mtx)[pos[0]][pos[1]]; // and say which was the previous node
        } // Otherwise, keep the old distance
    }
    if(pos[1]){ // if it's not colliding with the left of the graph
        if(new_dist < ((*a_graph_mtx)[pos[0]][pos[1]-1]->distance)){ // if my new distance is less than the distance at the node to its left
            (*a_graph_mtx)[pos[0]][pos[1]-1]->distance = new_dist; // replace the distance
            (*a_graph_mtx)[pos[0]][pos[1]-1]->prev = (*a_graph_mtx)[pos[0]][pos[1]]; // and say which was the previous node
        } // Otherwise keep the old one
    }
    if(pos[0] < (mtx_ht-1)){ // if it's not colliding with the bottom of the graph
        if(new_dist < ((*a_graph_mtx)[pos[0] 1][pos[1]]->distance)){ // if my new distance is less than the distance at the node right below it
            (*a_graph_mtx)[pos[0] 1][pos[1]]->distance = new_dist; // replace the distance
            (*a_graph_mtx)[pos[0] 1][pos[1]]->prev = (*a_graph_mtx)[pos[0]][pos[1]]; // and say which was the previous node
        } // otherwise keep the old one
    }
    if(pos[1] < (mtx_width - 1)){ // If it's not colliding with the right of the graph
        if(new_dist < ((*a_graph_mtx)[pos[0]][pos[1] 1]->distance)){ // if my new distance is less than the distance at the node to its right
            (*a_graph_mtx)[pos[0]][pos[1] 1]->distance = new_dist; // replace the distance
            (*a_graph_mtx)[pos[0]][pos[1] 1]->prev = (*a_graph_mtx)[pos[0]][pos[1]]; // and say which was the previous node
        } // otherwise keep the old one
    }

}

Gnode*** dijkstra(Gnode*** graph_mtx, short ht, short width){
/*
//  1. Create the matrix with all my weighted nodes [DONE]
//  2. Assign all bottom nodes as source (distance = 0) [DONE]
//  3. Find the shortest distance between the bottom and each node in the graph actually using Dijsktra's 
//      - While there's any priority queue left [JUST A WHILE LOOP]
//      - Take the first node in the Priority queue, and find the distance to all its adjacent nodes. If the distance is less than
//      whatever is currently there, replace it with the new distance [DONE] (not checked)
//      - Dequeue the node we just checked all the neighbors for and use downwards heapify to move the new top node to the end [In progress...]
//      - Use Upwards heapify to change all nodes that had been changed 
//      - Go back to 3.
//  4. Out of all the top nodes, whichever has the shortest distance from top to bottom will be the chosen one, so we need too get some
//  things from it to save
//      - Gnode->distance = time
//      - We also need to (efficiently) find out how many steps we took from that node to the bottom
//      - Detailed path from start to end
//  5. Then from all the top nodes, we need to find out all their distances (easy) to save alongside the width of the graph
//  6. We also have to save the graph to a file
// !! when adding distances, add the distance of the current node to the next distance, then at the end, add the distance of the last node to the total distance !!
*/
    // Initializing the queue
    PQ* pq = PQ_init(graph_mtx, ht, width); // Remember to free this later... how..? uh... yes! 
    while(pq->max_idx >= 0){ // while there are indexes in the queue
        int zero_row = (pq->Queue[0])->position[0]; // row where the 0th element of the queue is
        int zero_col = (pq->Queue[0])->position[1]; // col where the 0th element of the queue is
        updt_dist(&(graph_mtx), (pq->Queue[0])->position, ht, width); // Update the distances from the node that's at the front of the PQ
        PQ_dq(pq);
        if(zero_row){ // if there was a node adjacent to it above 
            int adj_idx = graph_mtx[zero_row-1][zero_col]->q_idx;
            PQ_updt(pq, adj_idx);
        }
        if(zero_col){ // if there was a node adjacent to its right
            int adj_idx = graph_mtx[zero_row][zero_col-1]->q_idx;
            PQ_updt(pq, adj_idx);
        }
        if(zero_row < (ht-1)){ // if there was a node adjacent to it below
            int adj_idx = graph_mtx[zero_row 1][zero_col]->q_idx;
            PQ_updt(pq, adj_idx);
        }
        if(zero_col < (width-1)){ // if there was a node adjacent to its left
            int adj_idx = graph_mtx[zero_row][zero_col 1]->q_idx;
            PQ_updt(pq, adj_idx);
        }
    }
}

// === GRAPH.H === //
// This file contains all the functions and structs related to graphs

#ifndef __GRAPH__
#define __GRAPH__
#include"pqueue.h"
#include"processes.h"

typedef struct _graphnode {
    
    //char name;

    int distance; // Distance from source node (0 if it IS source node)
    int q_idx; // position in queue
    short weight; // Weight of the individual node. Ideally shouldn't be changed
    int position[2]; // position of the node in graph. Format is {row, col}
    struct _graphnode* prev; // The node that led to this path

} Gnode;

// Creates a Matrix graph
Gnode*** create(char* filename, short* ht, short* width);

// You have just created a graph! Congratulations!
// By creating this graph, you have allocated three different times:
// - Every Row 
// - Every Collumn
// - Every Item MAYBE NOT!! REVISE!!
// It is important that they are freed in the following order:
// Item, Collumn, Row
// As deleting the collumns, will lose you access to the items and deleting the rows will lose you access to the collumns
// so you must not need to access any of the Items before deleting the cols and any of the cols before deleting the rows
void free_graph(Gnode*** graph, short ht, short width);

#endif

// === PQUEUE.H ==== //
// This file contains all functions and structs related to the priority queue

#ifndef __PQUEUE__
#define __PQUEUE__
#include"graph.h"
#include"processes.h"

typedef struct{
    Gnode** Queue;
    int max_idx;
} PQ;

// INITQUEUE; will add all the values to the queue.
// Returns the PQ that was built
PQ* PQ_init(Gnode*** graph_matrix, short ht, short width); 

// DEQUEUE; will implement downwards heapify on the array heap.
void PQ_dq(PQ* pq); 

// UPDATE QUEUE; implements upwards heapify
void PQ_updt(PQ* pq, int idx); 


#endif

#ifndef __PROCESSES__
#define __PROCESSES__
#include"graph.h"
#include"pqueue.h"

// Updates distance using the following parameters:
// ) Gnode**** a_graph_mtx - pointer to a graph matrix that will be modified by address
// ) int pos[2] - the position of the node we're looking at adjacency from
// ) int mtx_ht - how many rows in the matrix (note: not the index of the rows)
// ) int mtx_width - how many collumns in the matrix (note: not the index of the collumns)
void updt_dist(Gnode**** a_graph_mtx, int pos[2], int mtx_ht, int mtx_width);

Gnode*** dijkstra(Gnode*** graph_mtx, short ht, short width);

void save_grid();
void save_times();
void save_path();

#endif

// === GRAPH.C === //
// This file defines the functions declared in graph.h

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<string.h>
#include"processes.h" 
#include"graph.h"
#include"pqueue.h"

Gnode*** create(char* filename, short* ht, short* width){

    FILE* file = fopen(filename, "rb");
    short val;
    Gnode*** graph_matrix; // Matrix to store all the graph nodes to find adjacency

    if(file == NULL){
        graph_matrix = NULL; 
        // FILE IS NULL. POOPY!!!!
    }
    else{
        fread(&val, sizeof(short), 1, file);
        *ht = val;
        fread(&val, sizeof(short), 1, file);
        *width = val;

        graph_matrix = malloc((*ht)*sizeof(Gnode*)); // Allocating Rows
        for(int i = 0; i < (*ht); i  ){
            graph_matrix[i] = malloc((*width)*sizeof(Gnode*)); // Allocating Collumns
        }


        // Making a matrix to later assign adjancent nodes
        for(int j = 0; j < (*ht); j  ){
            for(int k = 0; k < (*width); k  ){
                fread(&val, sizeof(short), 1, file);
                Gnode* new_node = malloc(sizeof(*new_node)); // Not freed yet
                new_node->distance = (j == ((*ht) - 1)) ? 0 : __INT_MAX__;
                new_node->weight = val;
                new_node->position[0] = j;
                new_node->position[1] = k;
                graph_matrix[j][k] = new_node;
            }
        }

        printf("~ Graph Matrix Built! ~");

        // It's later. We're assigning adjacent nodes
        /* NVM. I'm not
        for(int j = 0; j < ht; j  ){
            for(int k = 0; k < width; k  ){
                if(j){
                    graph_matrix[j][k]->adj[0] = graph_matrix[j-1][k];
                }
                if(k){
                    graph_matrix[j][k]->adj[1] = graph_matrix[j][k-1];
                }
                if(j != (ht-1)){
                    graph_matrix[j][k]->adj[2] = graph_matrix[j 1][k];
                }
                if(k != (width-1)){
                    graph_matrix[j][k]->adj[3] = graph_matrix[j][k 1];
                }
            }
        }
        // Maybe not the best idea but I still want to see whaddup

        printf("~ Adjancencies Assigned! ~");
        */

        /* // CODE TO PRINT THE GRAPH
        while(!(feof(file))){
            int counter = 0;
            while(counter < width){
                fread(&val, sizeof(short), 1, file);

                printf("[");
                if(val < 10){
                    printf(" ");
                }
                printf("%d]", val);
                
                counter   ;
            }
            printf("\n");            
        }
        */ // CODE TO PRINT THE GRAPH

        fclose(file);
    }

    return graph_matrix;
}


void free_graph(Gnode*** graph_mtx, short ht, short width){
    // Freeing all nodes separately (might revise)
    int i = 0; // Start looking at the rows
    while(i < ht){ // As long as we have rows
        int j = 0; // Start looking at the cols
        while(j < width){ // And as long as we have collumns
            free(graph_mtx[i][j]); // Free the value of every space in the (row, col) pair
            j   ; // Go to the next col in this row
        }
        i   ; // Go to the next row
    }

    // Freeing all cols
    i = 0; // Start looking at the rows again
    while(i < ht){ // While we still have rows
        free(graph_mtx[i]); // Free the col stored at the row
        i  ; // Look at the next row
    }

    // Freeing the rows
    free(graph_mtx);
}

CodePudding user response：

In the file pqueue.c, the line

#include"processes.h" 

causes compiler to behave as if the entire content of the file processes.h were pasted into the file at that point.

When the compiler processes the included file processes.h, it will encounter the line

#include"graph.h"

as one of the first lines of the file, so the compiler will behave as if the entire content of the file graph.h were pasted into the file at that point.

When the compiler processes the included file graph.h, it will encounter the line

#include"pqueue.h"

as one of the first lines of the file, so the compiler will behave as if the entire content of the file pqueue.h were pasted into the file at that point.

When the compiler processes the included file pqueue.h, it will encounter the lines

#include"graph.h"
#include"processes.h"

as some of the first lines of the file, but these two lines effectively do nothing, due to the include guards that you are using in the header files, which prevent multiple inclusion of the same header file.

When the compiler continues processing the file pqueue.h and reaches the lines

typedef struct{
    Gnode** Queue;
    int max_idx;
} PQ;

it reports an error, because the type Gnode has not yet been defined. That is because that type is defined in the file graph.h, but the compiler has not yet reached that definition, because in the file graph.h, the compiler is still processing the line

#include"pqueue.h"

near the top of the file.

To fix this, you should not use circular references in your #include files. That way, you can ensure that the compiler encounters the definition of Gnode in the file graph.h before it is used.

The lines

#include"pqueue.h"
#include"processes.h"

in the file graph.h should be removed, as they are not necessary.

The line

#include"processes.h"

in the file pqueue.h should also be removed, as it is not necessary.

And the line

#include"pqueue.h"

in the file processes.h should be removed, as it is not necessary.

After removing those #include directives, your header files will no longer have any circular references, so you now have full control of the order in which the header files are processed.

CodePudding user response：

pqueue.h and process.h both require including graph.h to get access to Gnode. But you include both of those files in graph.h, so those get processed before the definition of Gnode.

You should only include what it necessary, so remove the includes of pqueue.h and process.h from graph.h, and have those two files only include graph.h.