CODEWITHSUNDEEP
c++design-patternsdata-structures
servabat
servabat

Reputation: 376

Circular dependency and graphs

Should circular dependency be avoided on graphs ?

For instance, consideer a graph class embedding an array of vertex objects, each of them having an array of edge objects which point to a vertex.

Here, vertex and edge are circularly dependent. Is this a bad idea ? Should it and how could it be avoided ?

Upvotes: 2

Views: 1681

Answers (1)

lorro
lorro

Reputation: 10880

No, it shouldn't. Graphs that have a non-trivial edge and vertex classes are inherently circular-dependent. If edge is practically empty, you might just store the adjacency matrix (i.e., whether there's an edge between given vertices); if vertex is empty, you might store and edge list that stores vertex number (size_t) instead of pointer. Best practice is to use smart_ptr<> and weak_ptr<> to break the chain. The latter is non-owning, thus:

  • If your graph stores vertices:
    • graph class has vector< smart_ptr< vertex > >
    • vertex class has vector< smart_ptr< edge > > m_out; and optionally vector< weak_ptr< edge > > m_in;
    • edge class has weak_ptr< vertex > m_vertices[2]; (or better yet m_from and m_to)
  • If your graph stores edges:
    • graph class has vector< smart_ptr< edge > >
    • edge class has smart_ptr< vertex > m_from; and weak_ptr< vertex > m_to;
    • vertex class has vector< weak_ptr< edge > > m_out; and optionally vector< weak_ptr< edge > > m_in;

If, for some reason (like widsom of senior :), coding standard, etc.) you cannot use smart_ptr<> and weak_ptr<>, you might use references instead of weak pointers, those are generally considered non-owning. Instead of smart_ptr<> you might either use pointers - or why not have members as long as edge and vertex are not base classes. Stroustrup additionally recommends marking naked pointers that should be deleted on exit using owner<>. If you don't have it, you might define a no-op for it as template<typename T> using owner = T;.

Upvotes: 3

Related Questions