Graph Class

#ifndef GRAPH_H_
#define GRAPH_H_

#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <sstream>
#include <string>
#include <assert.h>

//#include "tbb/"

using namespace std;

namespace jst {

    namespace graph {

    template<typename vertex_type, typename weight_type>
    class Graph {

    public:

        typedef pair<vertex_type, weight_type>  wedge;
        typedef map<vertex_type, weight_type> edge_map;
        typedef pair<edge_map, edge_map> in_out_set;
        typedef map<vertex_type, in_out_set> graph;

        typedef set<vertex_type> vertex_set;
        typedef pair<vertex_type, vertex_type> edge;
        typedef set<edge> edge_set;

        typedef typename graph::const_iterator const_iterator;
        typedef typename graph::iterator iterator;

        Graph(): graph_() {}

        ~Graph() {}

        void add(vertex_type u) {
            graph_[u];
        }

        const_iterator begin() {
            return(graph_.begin());
        }

        void connect(const vertex_type u, const vertex_type v, weight_type w) {
            if(!contains(u))
                add(u);
            if(!contains(v))
                add(v);
            graph_[u].second.insert(wedge(v,w));
            graph_[v].first.insert(wedge(u,w));
        }

        void clear() {
            graph_.clear();
            assert(graph_.size() == 0);
        }

        void clearEdges() {
            for(iterator i = graph_.begin(); i != graph_.end(); ++i) {
                i->second.first.clear();
                i->second.second.clear();
            }
        }

        bool contains(const vertex_type u) const {
            return (find(u) != graph_.end());
        }

        void disconnect(const vertex_type u, const vertex_type v) {
            assert(contains(u) && contains(v));
            graph_[u].second.clear();
            graph_[v].first.clear();
        }

        void disconnect(const vertex_type u, const vertex_set V) {
            for(typename vertex_set::const_iterator i = V.begin(); i != V.end(); ++i) {
                disconnect(u, *i);
            }
        }

        void disconnect(const vertex_set U, const vertex_type v) {
            for(typename vertex_set::const_iterator i = U.begin(); i != U.end(); ++i) {
                disconnect(*i, v);
            }
        }

        void disconnectAll(const vertex_type u) {
            disconnect(inNeighbourhood(u), u);
            disconnect(u, outNeighbourhood(u));
        }

        edge_set edgeSet() {
            edge_set E;
            for(const_iterator i = begin(); i != end(); ++i) {
                vertex_set V = outNeighbourhood(i->first);
                for (typename vertex_set::const_iterator j = V.begin(); j != V.end(); ++j) {
                    E.insert(edge(i->first, *j));
                }
            }
            return(E);
        }

        const_iterator end() {
            return(graph_.end());
        }

        const_iterator find(const vertex_type u) const {
            return(graph_.find(u));
        }

        int inDegree(const vertex_type u) {
            assert(contains(u));
            return(graph_[u].first.size());
        }

        vertex_set inNeighbourhood(const vertex_type u) {
            assert(contains(u));
            vertex_set V;
            for(typename edge_map::const_iterator i = graph_[u].first.begin(); i != graph_[u].first.end(); ++i) {
                V.insert(i->first);
            }
            return(V);

        }

        int outDegree(const vertex_type u) {
            assert(contains(u));
            return(graph_[u].second.size());
        }

        vertex_set outNeighbourhood(const vertex_type u) {
            assert(contains(u));
            vertex_set V;
            for(typename edge_map::const_iterator i = graph_[u].second.begin(); i != graph_[u].second.end(); ++i) {
                V.insert(i->first);
            }
            return(V);
        }

        void remove (vertex_type u) {
            disconnectAll(u);
            graph_.erase(u);
        }

        vertex_set topologicalVertexSet() {
            vertex_set V;

            return(V);
        }

        vertex_set vertexSet() {
            vertex_set V;
            for(const_iterator i = begin(); i != end(); ++i) {
                V.insert(i->first);
            }
            return(V);
        }

        string toString(const vertex_set V) const {
            stringstream ss;
            ss << "{ ";
            for (typename vertex_set::const_iterator i = V.begin(); i != V.end(); ++i) {
                ss << *i << " ";
            }
            ss << "}";
            return(ss.str());
        }

        string toString(const edge_set E) const {
            stringstream ss;
            ss << "{ ";
            for (typename edge_set::const_iterator i = E.begin(); i != E.end(); ++i) {
                ss << "{" << i->first << "->" << i->second << "} ";
            }
            ss << "}";
            return(ss.str());
        }


    private:

        graph graph_;

    };

    }

}

#endif /* GRAPH_H_ */