2
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ Why iteratos are public?? \$\endgroup\$ – amchacon Nov 7 '16 at 20:18
  • \$\begingroup\$ Welcome to Code Review, your first post looks good, hope you get some good answers! A little bit more description, or what you're particularly concerned about would still improve it though. \$\endgroup\$ – ferada Nov 7 '16 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.