Graph implementation adjacency list 1.0

Question

Please note the following:

1. All edges are directed
2. Removal of edges/nodges is not implemented yet
3. A user of the class Graph can never (hopefully) access a Node directly
4. If one tries to add an edge to a node that does not exist, insert_edge() will do nothing.
5. A Vertex cannot point to another vertex with several edges.
6. While the base class Graph works perfectly, I would like to create more advance graphs that could be used for maximum flow algorithm, weighted graphed etc. by creating new classes and inherit functions from Graph. But this seems impossible by the current implementation. It seems that the only way for a smooth solution for this right now is to add more data members to Node (int weight for example). Any idea on what I can do for making this possible with inheriting from Graph instead?

class Node
{
public:


std::string get_name()const;

//protected:
Node() = default;

Node( const std::string & n )
: name(n)
{}

std::vector<Node*> neighbours;
private:
std::string name;
};

class Graph : public Node 
{
public:
void insert_node( std::string);
void insert_edge( std::string, std::string); 
void print_node( const std::string) const;
void print_graph() const;

protected:
void insert_edge( Node*, Node*);
Node* get_node( std::string ) const;
bool is_node( Node * );   

private:
std::vector<Node*> list;
};

std::string
Node::get_name() const
{
return name;
}

void
Graph::insert_node( std::string name)
{
for( auto& node  : list  )
{
  if( name == node -> get_name() )
  {
     return;
  }
}

Node *temp = new Node(name);
list.push_back ( temp );
}

void 
Graph::insert_edge( Node *n, Node *new_edge ) 
{
if( n == nullptr || new_edge == nullptr )
{
  return;
}

if( !is_node( n ) )
{
  return;
}

for( auto& node : list )
{
  if( n -> get_name() == node -> get_name() )
  {
     for( auto& current_edges : node -> neighbours )
     {
        if( current_edges -> get_name() == new_edge -> get_name() )
        {
           return;
        }
     } 
     node -> neighbours.push_back( new_edge );
  }
}
}

void
Graph::insert_edge( std::string n, std::string new_edge)
{
Node* temp1 = get_node( n );
Node* temp2 = get_node( new_edge );
insert_edge( temp1, temp2 );
}

Node*
Graph::get_node( std::string name ) const
{
   for( auto& node : list )
{
  if( name == node -> get_name() )
  {
     return node;
  }
}
return nullptr;
}

void
Graph::print_node( std::string name ) const
{  
std::cout << name << " : ";
for( auto&  node : list )
{
if(name == node -> get_name() )
  {
     for( auto& edge : node -> neighbours )
     {
        std::cout << " -> " << edge -> get_name();
     }
     std::cout << std::endl;
     break;
  }
}
}

void
Graph::print_graph() const
{
for( auto&  node : list )
{
  std::cout << node -> get_name() << " : ";
  for( auto& edge : node -> neighbours )
  {
   std::cout << " -> " << edge -> get_name();
  }
  std::cout << std::endl;
}
}

bool
Graph::is_node( Node *n )
{
for( auto& node : list )
{
  if( node -> get_name() == n -> get_name() )
  {
     return true;
  }
}
return false; 
}

Answer 1

I don't like that std::vector<Node*> neighbours; is a data member with public scope in Node. I would suggest doing it private and provide a getter for it, or provide a Node::push_back(), etc.

As for you question of adding a data member weight in Graph, I think that's not very nice, since - in my mind - weight is an attribute every node has, thus it should be a data member of Node.