C circular dependency

Question

I have this problem with circular dependency in C, I looked around the other questions about this topic but really couldn't find the answer.

I have this first struct named vertex:

#ifndef MapTest_vertex_h
#define MapTest_vertex_h

#include "edgelist.h" //includes edgelist because it's needed

typedef struct 
{
    char* name;
    float x, y;
    edgelist* edges;
} vertex;

#endif

The second struct is the edgelist which is included by the vertex.

#ifndef edgelist_h
#define edgelist_h

#include "edge.h" //include edge, because its needed

typedef struct _edgelist
{
    edge** edges; 
    int capacity, size;
} edgelist;

//...

#endif

And then the last struct, the one where the problem raises, the edge struct gets included by the edgelist above.

#ifndef MapTest_edge_h
#define MapTest_edge_h

#include "vertex.h" //needs to be included because it will be unkown otherwise

typedef struct 
{
    float weight;
    vertex* destination;
    int found; 
} edge;

#endif

I tried everything I could, forward declaring, using #ifndef, #define etc. but couldn't find the answer.

How can I resolve this circular dependency problem?

Solution 1

Seems like you shouldn't need to include anything in any of the files. A forward declaration of the relevant types should be sufficient:

#ifndef MapTest_vertex_h
#define MapTest_vertex_h

struct edgelist;

typedef struct
{
    char* name;
    float x, y;
    edgelist* edges;    // C++ only - not C
} vertex;

#endif

etc. In C coding, you have to write:

struct edgelist;

typedef struct
{
    char* name;
    float x, y;
    struct edgelist* edges;
} vertex;

Solution 2

This kind of dependency is broken using a forward declaration. Instead of including a file with the full definition of the struct, there are two alternatives:

1.

typedef struct 
{
    char* name;
    float x, y;
    struct _edgelist* edges; /* add "struct" here (elaborated type specifier) */
} vertex;

2.

struct __edgelist; /* better form: forward declaration */

typedef struct 
{
    char* name;
    float x, y;
    struct _edgelist* edges; /* still need to add "struct" here */
} vertex;

Solution 3

I'm assuming a vertex needs to know what edges connect to it, and an edge needs to know what vertices it connects to.

If it were up to me, I'd create separate data types to associate vertices and edges:

struct vertex {
  char *name;
  float x, y;
};

// edgelist as before

struct edge {
  float weight;
  int found;
};

// New struct to map edges and vertices

struct vertexEdge { // you can probably come up with a better name
  struct vertex *v;
  struct edgelist *edges;
};

// New struct to map vertices and edges

struct edgeVertext {
{
  struct edge *e;
  struct vertex *vertices;
};

I'm running about 10-12 hours behind on sleep for the week, so I'm pretty sure there's a better way to design the mapping types (probably in a way that doesn't require more than one type), but this is the general approach I'd take.

Comments

[Jonathan Leffler]

Note that symbols starting with an underscore followed by either another underscore or a capital letter are unconditionally reserved for use by 'the implementation'. In general, avoid creating names starting with an underscore.