Graph implementation adjacency list 2.0

Question

Version 1:

Graph implementation adjacency list 1.0

Please note the following:

1. All edges are directed
2. A user of the class Graph shall never be able to aces an object of type Edge or Vertex
3. Only class Vertex can create an object Edge and only class Graph can create an object Vertex
4. No loops are allowed
5. Maximum one edge at the same direction from a vertex to another vertex

Edge.h

#ifndef EDGE_H
#define EDGE_H
#include <string>
class Edge
{
public:
 class ConstructionToken //Only class Vertex can create an object Edge
 {
 private:
 ConstructionToken();
 friend class Vertex;
 };
 Edge( const Edge &);
 Edge( const ConstructionToken & );
private:
 //weight, etc...
};
#endif /* EDGE_H */

Edge.cpp

#include "Edge.h"
Edge::ConstructionToken::ConstructionToken() = default;
Edge::Edge( const Edge & ) = default;
Edge::Edge( const ConstructionToken & )
{
}

Vertex.h

#ifndef VERTEX_H
#define VERTEX_H
#include <iterator>
#include <map>
#include <vector>
#include "Edge.h"
class Vertex
{
public:
 class ConstructionToken //Only Graph can create an object of type Vertex
 {
 private:
 ConstructionToken() = default;
 friend class Graph;
 };
 Vertex( const ConstructionToken & );
 const std::vector<std::string> copy_edges() const;
 void insert_edge( const std::string & );
 void remove_edge( const std::string & );
private:
 std::map<std::string, Edge> edges;
 //weight, visited, etc...
};
#endif /* VERTEX_H */

Vertex.cpp

#include <vector>
#include <utility>
#include "Vertex.h"
#include "Edge.h"
using edge_pair = std::pair<std::string, Edge>;
Vertex::Vertex( const ConstructionToken & ){}
void
Vertex::insert_edge( const std::string & end_point )
{
 Edge new_edge{ Edge::ConstructionToken{} };
 edge_pair temp( end_point, new_edge );
 edges.insert( temp );
}
void
Vertex::remove_edge( const std::string & edge )
{
 edges.erase( edge ); 
}
const std::vector<std::string>
Vertex::copy_edges() const
{
 std::vector<std::string> keys;
 for( auto& pair : edges )
 {
 keys.push_back( pair.first );
 }
 return keys;
}

Graph.h

#ifndef GRAPH_H
#define GRAPH_H
#include <map>
#include <string>
#include "Vertex.h"
class Graph
{
public:
 Graph() = default;;
 void insert_vertex( std::string);
 void insert_edge( std::string, std::string);
 void remove_edge( std::string, std::string );
 Graph transpose() const;
 Graph merge( const Graph & ) const;
 Graph inverse() const; 
 void print_graph() const;
protected:
 void insert_vertex( std::string, Vertex);
 void insert_edge( std::string, Edge);
private:
 std::map<std::string,Vertex> vertexes;
};
void print_graph( Graph );
#endif /* GRAPH_H */

Graph.cpp

#include <iostream>
#include <map>
#include <string>
#include <utility>
#include "Graph.h"
#include "Vertex.h"
#include "Edge.h"
void
Graph::insert_vertex( std::string name)
{
 //Check constructor for Vertex if not understandable
 Vertex::ConstructionToken c;
 Vertex v{ c };
 insert_vertex( name, v );
}
void
Graph::insert_vertex( std::string name, Vertex v )
{
 std::pair<std::string, Vertex> temp (name, v );
 vertexes.insert( temp );
}
void
Graph::insert_edge( std::string node, std::string new_edge )
{
 if( node == new_edge ) //No loops are allowed
 {
 return;
 }
 //Check that the node excist
 auto it = vertexes.find( node );
 if( it == vertexes.end() )
 {
 return;
 }
 it -> second.insert_edge( new_edge );
}
void
Graph::remove_edge( std::string node, std::string edge )
{
 auto it = vertexes.find( node );
 if( it == vertexes.end() )
 {
 return;
 }
 it -> second.remove_edge( edge ); 
}
Graph
Graph::transpose() const
{
 Graph Graph_T;
 //Vertex
 for( auto& pair : vertexes )
 {
 Graph_T.insert_vertex( pair.first );
 }
 //Edges
 std::vector<std::string> end_points;
 for( auto& pair : vertexes )
 {
 end_points = pair.second.copy_edges();
 for( auto & edge : end_points )
 {
 Graph_T.insert_edge( edge, pair.first );
 }
 }
 return Graph_T; 
}
Graph
Graph::merge( const Graph & G2 ) const
{
 Graph merge_graphs;
 //Merge vertexes
 for( auto& pair : vertexes)
 {
 merge_graphs.insert_vertex( pair.first );
 }
 for( auto& pair : G2.vertexes )
 {
 merge_graphs.insert_vertex( pair.first );
 }
 //Merge edges
 std::vector<std::string> end_points;
 for( auto& pair : vertexes )
 {
 end_points = pair.second.copy_edges();
 for( auto & edge : end_points )
 {
 merge_graphs.insert_edge( pair.first, edge );
 }
 }
 for( auto& pair : G2.vertexes )
 {
 end_points = pair.second.copy_edges();
 for( auto & edge : end_points )
 {
 merge_graphs.insert_edge( pair.first, edge );
 }
 }
 return merge_graphs;
}
Graph
Graph::inverse() const
{
 //Create a Graph temp which is complete
 Graph temp;
 for( auto& pair : vertexes )
 {
 temp.insert_vertex( pair.first );
 }
 for( auto& vertex1 : vertexes )
 {
 for( auto vertex2 : vertexes )
 {
 temp.insert_edge( vertex1.first, vertex2.first ); 
 } 
 }
 //Remove all edges in temp that also are in (*this)
 std::vector<std::string> end_points;
 for( auto& pair : vertexes )
 {
 end_points = pair.second.copy_edges();
 for( auto edge : end_points )
 {
 temp.remove_edge( pair.first, edge );
 } 
 }
 return temp;
}
void
Graph::print_graph() const
{
 std::vector<std::string> end_points;
 for( auto& pair : vertexes )
 {
 end_points = pair.second.copy_edges();
 std::cout << pair.first << " : ";
 for( auto& edge : end_points )
 {
 std::cout << " -> " << edge;
 }
 std::cout << std::endl;
 }
}
void print_graph( Graph G )
{
 G.print_graph();
}

Answer 1

In all, this is a well constructed set of classes. Here are a few things I see that could help you improve it further.

Put everything in your own namespace

Avoid polluting the global namespace by wrapping your headers in your own namespace. This will save headaches later if you attempt to use your classes with some other library.

Pass const reference to free-standing print_graph

The compiler will create a copy of the passed Graph unless you declare it

void print_graph( const Graph& );

Eliminate the spurious semicolon

Within the Graph.h file is this line:

Graph() = default;;

It's not technically an error, but there should only be a single semicolon at the end of that line.

Consider adding other defaults

While it may be useful to specifically point out that constructor for Graph is the default, the default copy and default move constructors are not specifically listed. It's not necessary but it's not obvious to me (or probably other readers of this class) why only one is listed.

Consider deleteing unneeded constructors

The Edge and Vertex classes do not need or use the default constructors, so it may be prudent to explicitly delete them as:

Edge() = delete;

Consider changing print_graph to a stream inserter

The print_graph member function and freestanding function could both be replaced with a more flexible ostream inserter:

friend std::ostream& operator<<(std::ostream& out, const Graph& g)
{
 std::vector<std::string> end_points;
 for( auto& pair : g.vertexes )
 {
 end_points = pair.second.copy_edges();
 out << pair.first << " : ";
 for( auto& edge : end_points )
 {
 out << " -> " << edge;
 }
 out << std::endl;
 }
 return out;
}

• Bojack: Do you have any comments about my choice of data structures? Is it a good choice with respect to speed, etc.?
• Edward: @NiclasJonsson: I generally try to write for clarity and correctness first and then measure to see if the program is already fast enough to meet performance targets. If so, I stop. With that said, the choice of data structures for performance is very much dependent on how you'll be using them. Will you be adding/deleting or is storage and random access more important?