C++ - Best convention to resolve templated classes' circular dependencies in header files?

Question

I am writing my own implementation of a templated Graph class in C++ and so I am also implementing templated Vertex and Edge classes. Thus, the implementations have to be inside their respective header file and not inside separate .cpp files. (The top answer here won't work for me)

My Vertex class stores an adjacency list of out-edges as a vector of Edges and the Edge class stores pointers to the source and destination Vertexs as well as the weight of the edge.

Since Edge only stores pointers to Vertex, it is sufficient to forward declare the Vertex class in Edge.h. Then I can #include "Edge.h" at the top of Vertex.h.

Is this the best way to resolve the co-dependencies of the Vertex and Edge classes? The user will have to #include both files in order to use either one (i.e. in Graph.h).

What if users want to use Vertex without having to also explicitly include Edge.h or vice versa? Should I forward declare and #include each inside the other?

Or should I implement them in the same header file?

How, if at all, is this problem addressed in STL?

Here's what I have right now:

Edge.h:

#ifndef _EDGE_H__
#define _EDGE_H__

template <class T> class Vertex;

template <class T>
class Edge
{
private:
    Vertex<T>* _source;
    Vertex<T>* _dest;
    unsigned long long _weight;

...

};
#endif

Vertex.h:

#ifndef _VERTEX_H__
#define _VERTEX_H__
#include "Edge.h"
#include <vector>

template <class T>
class Vertex
{
private:
    std::vector<Edge<T> > _adj;

...

};
#endif

I'm not sure it's the best design to have a vertex own the edges. Rather, I'd probably have the Graph own both. — T.C., Jul 11 '14 at 15:51
Always strive to minimize coupling. As you have already succeeded, you are done. Though it is a valid contention to say that you will need both anyway iff you need either, so separating them is just too much work for no gain... — Deduplicator, Jul 11 '14 at 15:51
Also, don't use `_EDGE_H__` etc. as your include guard macro names. They are reserved. — T.C., Jul 11 '14 at 15:54
@T.C. What would you recommend as a guard instead ? It is more useful when the **do this** instead of only saying **don't do this*. — localhost, Jul 11 '14 at 16:02
@localhost "Use a name that's [not reserved](http://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier/228797#228797)"? — T.C., Jul 11 '14 at 16:14
@T.C. This still does not answer the other part, particularly instead use *this* or "Here is an example, use something like **this**". For example, what would you use as a guard with the code above? — localhost, Jul 11 '14 at 16:17

score 0 · Answer 1 · answered Jul 11 '14 at 16:09

What if users want to use Vertex without having to also explicitly include Edge.h or vice versa?

Since you're essentially talking about designing a Graph class in the first place, there's nothing bad in including both of the headers inside it. The user would then just #include "graph.h" (or whatever you call the file), not really carring about how it's designed on the lower level.

That being said - if you want to keep your class designed the way it is at the moment - your solution is a good idea. However, as mentioned already in the comments, there's no need for a Vertex to own its edges. Maybe you should consider a different structure:

template<typename vertexType, typename edgeType>
class graph{
    std::map<std::pair<vertexType,vertexType>, edgeType>;
};

Keep in mind that with this design, the particular methods will probably be a bit more complex to write (and probably a bit slower). However - you'll end up using far less memory in the process. Depending on what you really want to achieve (either small size or fast work), you may end up using a different graph structure.

My implementation of `Graph` is optimizing for speed over space, so this structure is undesirable. — pdpiech, Jul 11 '14 at 16:13
@pdpiech I don't think the speed will make that much of a difference. I've used that structure in my game engine (pathfinding), and it didn't slow things even a bit (even with 20+ units on the map with 50 nodes). Anyhow - there's no real way to solve the circular dependencies other than what you did. — Paweł Stawarz, Jul 11 '14 at 16:17

score 0 · Accepted Answer · answered Jul 15 '14 at 14:06

I have come up with a compromise for a solution by decoupling the Vertex class from the Edge class as follows.

Edge.h:

#ifndef EDGE_H
#define EDGE_H

template <class T> class Edge
{
private:
    T* _source;
    T* _dest;
    long long _weight;

...

};
#endif

And in Vertex.h the vector becomes std::vector<Edge<Vertex<T> > >. That can be simplified, if desired, with a public typedef Edge<Vertex<T> > Edge in both Vertex.h and Graph.h. Thus the circular dependence is eliminated and each class can be used "separately" without including the other explicitly: now Graph.h depends on Vertex.h which depends on Edge.h.

As a side note to address comments regarding a vertex that owns its out-edges: I am expanding an already complete implementation of a graph class I wrote and the algorithms will be plug-and-play (with minimal changes) only if I keep the same/similar adjacency-list structure.

C++ - Best convention to resolve templated classes' circular dependencies in header files?

2 Answers2