I'm looking for a code review on the following C++/STL graph implementation:
Edge
#ifndef edge_h
#define edge_h
template <typename T>
class Edge
{
public:
Edge(const T &weight): weight(weight) {} ;
const T& getWeight() { return weight; };
private:
T weight;
};
#endif /* edge_h */
Vertex
#ifndef vertex_hpp
#define vertex_hpp
#include <iterator>
#include <map>
#include <set>
#include "edge.hpp"
template <typename V, typename E>
class Vertex
{
public:
typedef typename std::map<V, Edge<E> >::const_iterator edge_iterator;
Vertex() = default;
const std::set<V> copyEdges() const
{
std::set<V> keys;
for(auto& pair : out_edges)
keys.push_back(pair.first);
return keys;
}
edge_iterator outEdgeItBegin()
{
return out_edges.begin();
}
edge_iterator outEdgeItEnd()
{
return out_edges.end();
}
edge_iterator inEdgeItBegin()
{
return in_edges.begin();
}
edge_iterator inEdgeItEnd()
{
return in_edges.end();
}
void insertSourceEdge(const V &target, const E weight = E(1))
{
Edge<E> e(weight);
if(out_edges.find(target) == out_edges.end()){
out_edges.insert( std::make_pair(target, e) );
}else{
std::string errorMessage = std::string("try to insert a link that already exist");
throw std::invalid_argument(errorMessage);
}
}
void insertTargetEdge(const V &target, const E weight = E(1))
{
Edge<E> e(weight);
if(in_edges.find(target) == in_edges.end()){
in_edges.insert( std::make_pair(target, e) );
}else{
std::string errorMessage = std::string("try to insert a link that already exist");
throw std::invalid_argument(errorMessage);
}
}
void removeOutEdge(V target)
{
if(out_edges.find(target) != out_edges.end()){
out_edges.erase(target);
}else{
std::string errorMessage = std::string("try to remove a link that doesn't exist");
throw std::invalid_argument(errorMessage);
}
}
void removeInEdge(V source)
{
if(in_edges.find(source) != in_edges.end()){
in_edges.erase(source);
}else{
std::string errorMessage = std::string("try to remove a link that doesn't exist");
throw std::invalid_argument(errorMessage);
}
}
private:
std::map<V, Edge<E> > out_edges;
std::map<V, Edge<E> > in_edges;
};
#endif /* vertex_hpp */
Graph
#ifndef graph_hpp
#define graph_hpp
#include <map>
#include <string>
#include <stdexcept>
#include "vertex.hpp"
template <typename V, typename E>
class Graph
{
public:
typedef typename std::map< V, Vertex<V,E> >::const_iterator vertex_iterator;
typedef typename std::map< V, Edge<E> >::const_iterator edge_iterator;
typedef typename std::pair< V, Vertex<V,E> > vertex_t;
Graph(): undirected(true), nb_edge(0) {};
vertex_t insertVertex(V name)
{
Vertex<V, E> v;
insertVertex(name, v);
return std::make_pair(name, v);
}
void insertEdge(vertex_t source, vertex_t target, E weight = E(1)){
insertEdge(source.first, target.first, weight);
}
void insertEdge(V source, V target, E weight = E(1))
{
//No loops are allowed
if( source == target )
{
std::string errorMessage = std::string("self loop not allowed");
throw std::invalid_argument(errorMessage);
}
//Check that the surce node excist
auto source_it = vertexes.find(source);
if( source_it == vertexes.end() )
{
insertVertex(source);
source_it = vertexes.find(source);
}
//Check that the target node excist
auto target_it = vertexes.find(target);
if( target_it == vertexes.end() )
{
insertVertex(target);
target_it = vertexes.find(target);
}
try{
source_it->second.insertSourceEdge(target, weight);
target_it->second.insertTargetEdge(source, weight);
nb_edge++;
}catch(std::exception &e)
{
std::cout << e.what() << std::endl;
}
}
edge_iterator neighborsItBegin(vertex_t node){ return neighborsItBegin(node.first); };
edge_iterator neighborsItBegin(V node)
{
auto it = vertexes.find(node);
if( it == vertexes.end() )
{
std::string errorMessage = std::string("Unknown node id: ") + std::to_string(node);
throw std::invalid_argument(errorMessage);
}
return it->second.outEdgeItBegin();
}
edge_iterator neighborsItEnd(vertex_t node){ return neighborsItEnd(node.first); };
edge_iterator neighborsItEnd(V node)
{
auto it = vertexes.find(node);
if( it == vertexes.end() )
{
std::string errorMessage = std::string("Unknown node id: ") + std::to_string(node);
throw std::invalid_argument(errorMessage);
}
return it->second.outEdgeItEnd();
}
edge_iterator inNeighborsItBegin(vertex_t node) { return inNeighborsItBegin(node.first); };
edge_iterator inNeighborsItBegin(V node)
{
auto it = vertexes.find(node);
if( it == vertexes.end() )
{
std::string errorMessage = std::string("Unknown node id: ") + std::to_string(node);
throw std::invalid_argument(errorMessage);
}
return it->second.inEdgeItBegin();
}
edge_iterator inNeighborsItEnd(vertex_t node) { return inNeighborsItEnd(node.first); };
edge_iterator inNeighborsItEnd(V node)
{
auto it = vertexes.find(node);
if( it == vertexes.end() )
{
std::string errorMessage = std::string("Unknown node id: ") + std::to_string(node);
throw std::invalid_argument(errorMessage);
}
return it->second.inEdgeItEnd();
}
std::size_t inDegree(vertex_t node)
{
return inDegree(node.first);
}
std::size_t inDegree(V node)
{
auto it = vertexes.find(node);
if( it == vertexes.end() )
{
std::string errorMessage = std::string("Unknown node id: ") + std::to_string(node);
throw std::invalid_argument(errorMessage);
}
std::size_t cpt = 0;
for(auto edge_it = it->second.inEdgeItBegin(); edge_it != it->second.inEdgeItEnd(); ++edge_it)
cpt++;
return cpt;
}
std::size_t outDegree(vertex_t node)
{
return outDegree(node.first);
}
std::size_t outDegree(V node)
{
auto it = vertexes.find(node);
if( it == vertexes.end() )
{
std::string errorMessage = std::string("Unknown node id: ") + std::to_string(node);
throw std::invalid_argument(errorMessage);
}
std::size_t cpt = 0;
for(auto edge_it = it->second.outEdgeItBegin(); edge_it != it->second.outEdgeItEnd(); ++edge_it)
cpt++;
return cpt;
}
void removeEdge(vertex_t source, vertex_t target)
{
removeEdge(source.first, target.first);
}
void removeEdge(V source, V target)
{
auto s = vertexes.find(source);
if( s == vertexes.end() )
{
std::string errorMessage = std::string("Unknown node id: ") + std::to_string(source);
throw std::invalid_argument(errorMessage);
}
auto t = vertexes.find(target);
if( t == vertexes.end() )
{
std::string errorMessage = std::string("Unknown node id: ") + std::to_string(target);
throw std::invalid_argument(errorMessage);
}
try{
s->second.removeOutEdge(target);
t->second.removeInEdge(source);
nb_edge--;
}catch(std::exception &e){
std::cout << e.what() << std::endl;
}
}
void removeNode(vertex_t node) { return removeNode(node.first); };
void removeNode(V node)
{
auto s = vertexes.find(node);
if(s == vertexes.end()){
std::string errorMessage = std::string("Unknown node id: ") + std::to_string(node);
throw std::invalid_argument(errorMessage);
}
for(auto it = inNeighborsItBegin(node); it != inNeighborsItEnd(node);){
auto node_src = (it++)->first;
removeEdge(node_src, node);
}
for(auto it = neighborsItBegin(node); it != neighborsItEnd(node);){
auto node_target = (it++)->first;
removeEdge(node, node_target);
}
vertexes.erase(node);
}
std::size_t size()
{
return vertexes.size();
}
std::size_t nbEdge(){ return nb_edge; };
vertex_iterator begin()
{
return vertexes.begin();
}
vertex_iterator end()
{
return vertexes.end();
}
protected:
void insertVertex(V name, Vertex<V,E> v){
this->vertexes.insert( std::make_pair(name, v) );
}
private:
std::map< V, Vertex<V,E> > vertexes;
bool undirected;
std::size_t nb_edge;
};
#endif /* graph_hpp */
Main
int main(int argc, const char * argv[]) {
Graph<int, int> g;
auto v1 = g.insertVertex(1);
auto v2 = g.insertVertex(2);
auto v3 = g.insertVertex(3);
auto v4 = g.insertVertex(4);
g.insertEdge(v1, v2);
g.insertEdge(v2, v1);
g.insertEdge(v1, v3);
g.insertEdge(v3, v1);
g.insertEdge(v1, v4);
g.insertEdge(v4, v1);
g.outDegree(v1);
g.size();
g.nbEdge();
g.removeNode(v1);
}
