Graph and network

[sbrohee]

Hi all,

I have a more philosophical question which I think might help me to better understand the interest of pointers in C++. Indeed, my background is mainly Perl and a bit of Java.

I am currently implementing (as an exercise and because I work in this field) a class to play with graph theory. At the moment, I have three classes : Node, Edge and Graph.

To your opinion, an edge has to be an object like the following code (where the nodes source and target that defines it are pointers to the nodes) or where the nodes are the object really.

class Edge {
  
  public:
    Edge(Node*, Node*);				// constructor (specify only the source and the target nodes
    Edge(Node*, Node*, string, double, string);	// constructor (specify the source and target nodes, the color, the weight and the name)
    
    void setSourceAndTarget(Node*, Node*);	// set the source node and the target node

    // blabla

  private:
    Node *source;			// source node
    Node *target;			// target node
    // blabla

};

I have the same kind of problem with my Graph class. It class contains two set attributes : edgesSet and nodesSet. Do these set have to contain pointers to the edges and nodes or the objects directly!

Thank you for your opinion!

[mike_2000_17]

Well from my understanding, you are sharing the objects between your different objects, i.e. the Graph and Edge objects contain pointers to shared Nodes. In this case, of course storing the objects directly is out of the question, or at least one of the two objects that hold the shared Node, must store it as a pointer, otherwise the instance of Node that is shared will not be the same (i.e. copies of each other).

So you're right to use pointers. But watch out! Typically in a graph architecture, you need to define rules of ownership (i.e. who is responsible for destroying the instance of a Node to which several other objects (Graph, Edge, Node) hold a pointer to). Then, you have to worry about the order of destruction, such that an object which holds a pointer to a Node for which he doesn't have ownership, should not access it after the owner has destroyed it. This can become quite tricky. Then, you have cycles or semi-cycles to worry about as well.

Luckily, Boost Smart Pointers give you a nice trio of smart pointers that can really help in graph-like object hierarchies: shared_ptr, weak_ptr, unique_ptr (all now part of TR1 standard library, i.e. tentative release 1). A shared_ptr is a reference-counted pointer, meaning that it will automatically destroy only when all copies of that shared_ptr are deleted or gone out-of-scope. This can allow you to make sure no pointers to a Node will suddenly point to the freed memory slot of a deleted Node (i.e. shared ownership). The weak_ptr works alongside the shared_ptr as a means to hold a pointer to an object which is not part of the reference-counting but can check if the object was deleted (after the reference count went to zero). weak_ptr allows you to hold a reference to an object in a way that is safe, in terms of knowing if the object was deleted, while not requiring that the object be kept alive for as long as the weak_ptr to it exists (no ownership). Finally, unique_ptr allows you to have a unique ownership of an object in a non-copyable pointer but which can be moved to move the ownership from one object to another (exclusive ownership). These three types of pointers are very safe and make life a lot easier when it comes to object graphs. Also, shared_ptr and weak_ptr can be used in concert to break cycles in the graph, and are semantically very clear.

[sbrohee]

Hi Mike,

Thanks (again, you already saved me yesterday) for your advices. It seems I still have a long road to understand all the subtilties of C++.

About the boost smart pointers, now. You will maybe think my idea are strange, but I don't want to rely on any other library than STL. Indeed, in my field (bioinformatics), lots of wonderful tools cannot be used because they rely on other libraries that might be difficult to install. So, even if my code will be less efficient because of that, I prefer staying independent. At the end of my work, I want people to be able to install my tools in one simple command ... and even if they are not the most efficient graph tool in the world, they will be the easiest to install (... this is my dream).

But ... I think I am already a bit dreaming (I don't even have a working Graph class).

Thanks again for your advices. I will play with these the all afternoon!

[mike_2000_17]

Well... TR1 is part of the C++ standard libraries (and STL). And those smart pointers are part of TR1. So that would not violate your rule of minimizing external dependencies (which I applaud you for, because I think it is paramount to limit external dependencies).

Boost is essentially a cross-platform, peer-reviewed, open-source collection of libraries which is considered as the anti-chamber of the C++ standard library and members of the standard committee and other prominent members of the C++ community are peer-reviewers for it. So if there is any external dependency you can easily live with it's this one.

[sbrohee]

Thanks again!

And now, let's play with all that!