2

I have a graph implemented using a struct Node and a struct Edge where:

  • Each Edge has a start and an end Node
  • Each Node maintains a list of Edge objects which start from or end at it

The following is one possible implementation:

struct Node;

struct Edge {
  Node *st;
  Node *en;
  int some_data;
};

const int MAX_EDGES = 100;
struct Node {
  Edge *edges[MAX_EDGES];
  int some_data;
};

While the above structs can represent the graph I have in mind, I would like to do it the "Modern C++" way while satisfying the following requirements:

  1. Avoid pointers
  2. Use an std::vector for Node::edges
  3. Be able to store Node and Edge objects in standard C++ containers

How is this done in Modern C++? Can all of 1-3 be achieved?

4
  • Just as an aside, this really looks more like a linked list, so you should consider std::list instead of std::vector. Mar 4, 2015 at 12:58
  • @Cyber, why? Will edges be inserted at the start or into the middle of a node's list? will list of edges be merged or spliced? What looks linked-list-like? Mar 4, 2015 at 13:00
  • @Cyber for my particular case, I don't need fast insertions. So, std::list and std::vector work out the same for me. Mar 4, 2015 at 13:02
  • I would say: 1. Avoid "naked" or "raw" pointers, since "smart" pointers like std::shared_ptr, std::weak_ptr, etc. are still conceptually pointers.
    – mhcuervo
    Mar 4, 2015 at 13:31

3 Answers 3

8
  1. Avoid pointers

You can use std::shared_ptr and std::weak_ptr for this. Just decide whether you want nodes to own edges, or vice versa. The non-owning type should use weak_ptr (to avoid cycles).

Unless your graph is acyclic you might still need to be careful about ownership cycles.

std::unique_ptr is not an option, because there is not a one-to-one relationship between nodes and edges, so there cannot be a unique owner of any given object.

  1. Use an std::vector for Node::edges

No problem. Make it a std::vector<std::weak_ptr<Edge>> or std::vector<std::shared_ptr<Edge>> (depending whether edges own nodes or vice versa)

  1. Be able to store Node and Edge objects in standard C++ containers

No problem, just ensure your type can be safely moved/copied without leaking or corrupting memory, i.e. has correct copy/move constructors and assignment operators. That will happen automatically if you use smart pointers and std::vector as suggested above.

1

Modern C++ eschews the assignment of dynamic memory to a raw pointer. This is because it is all to easy to forget to delete said pointer. Having said that there is nothing wrong with the use of raw pointers as reference to an object provided you can guarantee that the object's lifetime will be greater than the use of said pointer.

The rules generally are:

  1. Use std::unique_ptr if an object has single owner.
  2. Use raw pointers to reference objects created in 1. provided you can guarantee that the object's lifetime will be greater than the use of your reference.
  3. Use std::shared_ptr for reference counted objects
  4. Use std::weak_ptr to refer to a reference counted object when you do not want to increase the refernce count.

So in your case, if the Edge owns the Nodes then use std::unique_ptr, if not, the keep the raw pointers. In your Node class, if the Node owns the Edges use a std::vector<Edge> otherwise use a std::vector<Edge*> although it might be more efficient to link the your Edges together in their own intrusive linked list.

Having done some work on complex graphs, it might be allocate all your Nodes and Edgees in a vector outside your graph and then only refer to them internally using raw pointers inside the graph. Remember memory allocation is slow so the less you do the faster your algorithm will be.

1
  • An edge is associated with exactly two nodes, so can't really be stored by value in std::vector<Edge> inside a single node. Similarly, more than one edge can be associated with a given node, so you can't have all of those edges owning std::unique_ptr<Node>. If nodes own edges or vice versa then shared_ptr and weak_ptr are possible, otherwise manage all ownership externally to the graph as you suggest. Mar 4, 2015 at 15:43
0
  1. By using std::shared_ptr or std::unique_ptr
  2. I don't think vector is a right choice here since a graph usually is not linear (usually speaking, also ,in most cases you can't linearize it like you can with a heap)
  3. there is no standard 'general-use' container , but you can use templates here for generity

for example, your Element class can look like this:

template <class T>
struct Elem {
  std::shared_ptr<Node> st , en;
  T some_data;
};

speaking of modern C++ , I don't think struct is encouraged here , you ahould encapsulate you data

2
  • 4
    unique_ptr would be hard to get right, since every edge is "owned" by two nodes, or every node can be "owned" by many edges. std::vector is the general-use container, it should be preferred unless you need the element stability / iterator invalidation rules of another container. Mar 4, 2015 at 13:07
  • Are templates a good fit for the problem? He wants to deal with a couple of classes, not abstract the types those classes will contain.
    – user146043
    Mar 4, 2015 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.