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; 
}

• glampert: Did you omit a level of indentation pretty much everywhere intentionally, or was that a problem when pasting the code here?
• Bojack: My code is indentended in my editor, but my I pasted it here, the site complaided that it was not four whitespace so I just hitted the spacebar so it was 4 whitespace in the code...Is there a better way?
• glampert: Humm, not that I know of... Which editor are you using? On Vim and Emacs is pretty easy to replace tabs with spaces...

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.

• Bojack: Neighbors should be protected so Graph can use it, but I have some compiling problems with that right now! I guess I am not clear enough with my description! I would like to great graphs with weights so I can implement dijkstra algorithm. I would also like to great graphs with capacity so I can implement different maximum flow algorithms as well. This makes it problematic to store both weights, capacity, etc. in node.
• Bojack: Therefore, I think it is better to create a class Graph_Weight that inherit from class Graph and give that Graph weight instead of the class Node and another class Graph_capacity that have capacity. I am clear with my thoughts?
• gsamaras: @user1991779 I thought it was public, because you have commented protected! Maybe you could make an Edge class as well. However yes, your idea is nice too! :) Should I edit my answer or something or it is good as is? (because I saw that you didn't accept it).
• Bojack: I have made a lot of modifications, I will probably post it tomorrow. I would like to get some more comments on my choice of data structures!
• gsamaras: Don't you think that the new ones should be a new question? Just an idea. I am not sure. :) @user1991779