Copy of struct's 'instance' is added to vector instead of real instance

Question

Hello everyone!

I tried implementing a generic Graph, where each Node has a adjacency list of Nodes that it is connected too. The adjacency list is implemented through a vector. The graph stores its nodes in a vector.

I noticed that eventhough the Adjacency lists of the created node is not empty, the inserted node in the nodes vector of the graph has an empty adjacency list.

I figured that the problem is that some sort of copy of the node is added to the vector instead of the node reference given to the function, but I don't know how to fix it.

#include <iostream>
#include <vector>

using namespace std;

template <typename K>
struct Node{
    K key;
    vector<Node<K>> AdjList;

    Node(K key) : key(key) { }
    ~Node() = default;

    void addNodeToAdjList(Node<K>& node){
        AdjList.push_back(node);
    }
};

template <typename K>
class Graph{
private:
	int NumberOfNodes;
    vector<Node<K>> nodes;

public:
    Graph() : NumberOfNodes(0) { }
    Graph(int N) : NumberOfNodes(N) { }
    ~Graph() = default;

    void addNode(Node<K>& node){
        nodes.push_back(node);
    }
    void addEdge(Node<K>& node1, Node<K>& node2){
        if(!isNodeInGraph(node1))
            addNode(node1);
        if(!isNodeInGraph(node2))
            addNode(node2);
        if(!node1.isNodeInAdjList(node2))
            node1.addNodeToAdjList(node2);
        cout << "The node1 has node2 in AdjList " << node1.AdjList.empty() << endl;
        cout << "Now lets look at the nodes we added to the vector nodes" << endl;
        for(auto n : nodes)
            cout << "This is node " << n.key << " with Adjacency List empty = " << n.AdjList.empty() << endl;
    }
};

Answer 1

Hello,

What happens when you do that:

    addNode( node1 );
    node1.addNodeToAdjList( node2 );

Because nodes is a vector<Node<K>>, that adds a copy of node1 in the nodes vector,
Then the copy of node2 is added to the node1.AdjList, but node1 is not the node just inserted in the nodes vector. So the node in nodes vector still have an empty AdjList!

You write it, you must store reference to nodes in the vectors, not nodes values.

A vector<> cannot store reference, it stores values. You can use in place std::vector<std::reference_wrapper<Node<K>>>.

#include <iostream>   // for std::cout
#include <vector>     // for std::vector<>
#include <functional> // for std::reference_wrapper<>

 template<typename K>
struct Node {
   K  key;
   std::vector<std::reference_wrapper<Node>>  adjList;

   Node( K const& key ) : key{key} { }
   ~Node() = default;

   void  addNodeToAdjList( Node& node ) {
      adjList.push_back( node );
   }
   bool  isNodeInAdjList( Node const& node )const {
      return  std::find( adjList.begin(), adjList.end(), node ) != adjList.end();
   }
   friend bool operator==( Node const& x, Node const& y ) {
      return  &x == &y;
   }
};

 template<typename K>
class Graph {
private:
   std::vector<std::reference_wrapper<Node<K>>>  nodes;

public:
   Graph() = default;
   ~Graph() = default;

   void  addNode( Node<K>& node ) {
      nodes.push_back( node );
   }
   bool  isNodeInGraph(Node<K>const& node)const {
      return  std::find(nodes.begin(),nodes.end(),node) != nodes.end();
   }
   void  addEdge( Node<K>& node1, Node<K>& node2 ) {
      if ( !isNodeInGraph( node1 ) )
         addNode( node1 );
      if ( !isNodeInGraph( node2 ) )
         addNode( node2 );
      if ( !node1.isNodeInAdjList( node2 ) )
         node1.addNodeToAdjList( node2 );
   }
   void  show_nodes()const {
      endl( std::cout << "The node List :" );
      for ( auto const&  rwn  :  nodes ) {
         std::cout << "This is node " << rwn.get().key;
         if ( rwn.get().adjList.empty() )
            endl( std::cout << " adjacency List is empty" );
         else {
            std::cout << " adjacent List : ";
            for ( auto const&  rwn  :  rwn.get().adjList )
               std::cout << "node " << rwn.get().key << ", ";
            endl( std::cout );
         }
      }
   }
};

int  main() {
    using  Type = int;
    Graph<Type>  graph;
    Node<Type>  n1{1}, n2{2}, n3{3}; // Nodes ARE HERE
    graph.addEdge( n1, n2 );
    graph.addEdge( n1, n3 );
    graph.show_nodes(); // the Nodes in graph are effectively n1 n2 n3
}

But the reference_wrapper<> is a reference so implies that all nodes are still alive somewhere to be referenced.
We can use in place std::vector<std::unique_ptr<Node<K>>> in the graph becoming the owner of all nodes, and std::vector<std::reference_wrapper<Node<K>>> staying in the AdjList of Node<K> to have a single owner of each Node.