Graph implementation adjacency list 2.0

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