Graph.h

#ifndef _GRAPH_H_
#define _GRAPH_H_

#include <stdexcept>
#inlcude <set>
#include <map>

struct nil {};

template <typename VertexData = nil, typename EdgeData = nil>
class Graph
{
public:
    
    class Vertex
    {
    public:
        
        const std::set<Edge*>& get_edges()
        {
            return edges;
        }
        
        std::set<const Edge*> get_edges() const
        {
            return std::vector<const Edge*>(edges.begin(), edges.end());
        }
        
        void set_data(const VertexData& value)
        {
            data = value;
        }
        
        const VertexData& get_data() const
        {
            return data;
        }
        
    private:    
        VertexData data;
        std::set<Edge*> edges;
        
        Vertex() {}
        ~Vertex() {}
    };
    
    class Edge
    {
    public:
    
        Vertex* get_first_vertex()
        {
            return first_vertex;
        }
        
        const Vertex* get_first_vertex() const
        {
            return first_vertex;
        }
        
        Vertex* get_second_vertex()
        {
            return second_vertex;
        }
        
        const Vertex* get_second_vertex() const
        {
            return second_vertex;
        }
        
        void set_data(const EdgeData& value)
        {
            data = value;
        }
        
        const EdgeData& get_data() const
        {
            return data;
        }
        
    private:    
        EdgeData data;
        Vertex* first_vertex;
        Vertex* second_vertex;
        
        Edge(Vertex* first, Vertex* second)
        {
            first_vertex  = first;
            second_vertex = second;
        }
        
        ~Edge() {}
    };
    
    Graph() {}
    
    Graph(const Graph<VertexData, EdgeData>& orig)
    {
        std::map<Vertex*, Vertex*> vmapping;
        
        for (Vertex* orig_vertex: orig.vertexes)
        {
            Vertex* new_vertex = add_vertex(orig_vertex->data);
            vmapping[orig_vertex] = new_vertex;
        }
        
        for (Edge* orig_edge: orig.edges)
        {
            auto fi = vmapping.find(orig_edge->get_first_vertex());
            if (fi == vmapping.end())
            {
                throw std::logic_error("vertex in edge not on graph");
            }
            
            auto si = vmapping.find(orig_edge->get_second_vertex());
            if (si == vmapping.end())
            {
                throw std::logic_error("vertex in edge not on graph");
            }
            
            add_edge(*fi, *si);
        }        
    }
        
    ~Graph()
    {
        for (Edge* edge: edges)
        {
            delete edge;
        }
        edges.clear();
        
        for (Vertex* vertex: vertexes)
        {
            delete vertex;
        }
        vertexes.clear();
    }
    
    const Graph<VertexData, EdgeData>& operator = (const Graph<VertexData, EdgeData>& orig)
    {
        Graph<VertexData, EdgeData> tmp(orig);
        tmp.swap(*this);
        return *this;
    }
    
    Vertex* add_vertex()
    {
        Vertex* v = new Vertex;
        vertexes.insert(v);
        return v;
    }
    
    Vertex* add_vertex(const VertexData& data)
    {
        Vertex* v = add_vertex();
        v->set_data(data);
        return v;
    }
    
    void remove_vertex(Vertex* vertex)
    {
        if (vertex == NULL)
        {
            throw std::invalid_argument("vertex == NULL");
        }
        
        auto vi = vertexes.find(vertex);
        if (vi == vertexes.end())
        {
            throw std::logic_error("vertex not in this graph");
        }
        
        for (Edge* edge: (*i)->edges)
        {
            auto ei = edges.find(edge);
            if (ei == edges.end())
            {
                throw std::logic_error("vertex edge not in edge list");
            }
            edges.erase(ei);
            delete edge;
        }
        
        delete vertex;
        vertexes.erase(vi);
    }
    
    const std::vector<Vertex*>& get_vertexes()
    {
        return vertexes;
    }
    
    std::vector<const Vertex*> get_vertexes() const
    {
        return vertexes;
    }
    
    Edge* add_edge(Vertex* first, Vertex* second)
    {
        Edge* edge = new Edge(first, second);
        
        first->edges.insert(edge);
        second->edges.insert(edge);
        
        edges.insert(edge);
        return edge;
    }
    
    Edge* add_edge(Vertex* a, Vertex* b, const EdgeData& data)
    {
        Edge* edge = add_edge(first, second);
        edge->set_data(data);
        return edge;
    }
    
    void remove_edge(Edge* edge)
    {
        if (edge == NULL)
        {
            throw std::invalid_argument("edge == NULL");
        }
        
        auto ei = edges.find(edge);
        if (ei == edges.end())
        {
            throw std::logic_error("edge not in this graph");
        }
        
        auto fi = edge->first_vertex->edges.find(edge);
        if (fi == edge->first_vertex->edges.end)
        {
            throw std::logic_error("edge not in first vertex edge list");
        }
        edge->first_vertex->edges.erase(fi);
        
        auto si = edge->second_vertex->edges.find(edge);
        if (si == edge->second_vertex->edges.end)
        {
            throw std::logic_error("edge not in second vertex edge list");
        }
        edge->second_vertex->edges.erase(si);
        
        edges.erase(ei);
        delete edge;
    }
    
    const std::vector<Edge*>& get_edges()
    {
        return edges;
    }
    
    std::vector<const Edge*> get_edges() const
    {
        return edges;
    }
    
    void swap(Graph<VertexData, EdgeData>& other)
    {
        vertexes.swap(other->vertexes);
        edges.swap(other->edges);
    }
    
private:    
    std::set<Vertex*> vertexes;
    std::set<Edge*> edges;
};

#endif