Version 1:
Graph implementation adjacency list 1.0
Please note the following:
- All edges are directed
- A user of the class Graph shall never be able to aces an object of type
Edge
orVertex
- Only
class Vertex
can create an objectEdge
and onlyclass Graph
can create an objectVertex
- No loops are allowed
- 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();
}