#include <map>
#include <stdexcept>
using namespace std;

// The full graph
class graph {
    public:
        class node;		    // fwd declaration
	// Maps for going from name to node and for finding named subgraphs
        typedef map<string, node *> nodemap_t;
        typedef map<string, nodemap_t> subgraph_t;
	// The nodes and subgraphs of this graph
        nodemap_t nodes;
        subgraph_t subgraphs;


    public:
	// An edge in a graph.  Accessors, etc. are straightforward
        class edge {
            protected:
                string dest_name;	// The destination node's name
                unsigned int dst_ip;	// Destination IP (if any)
                int wt;			// Edge weight
            public:

            edge(const string& n, int w=0, unsigned int dip=0):
                dest_name(n), dst_ip(dip), wt(w) { }
            edge(const edge& e) :
                dest_name(e.dest_name), dst_ip(e.dst_ip), wt(e.wt) { }

            bool operator<(const edge& e) const {
                return dest_name < e.dest_name;
            }

            edge& operator=(const edge& e) {
                dest_name = e.dest_name;
                dst_ip = e.dst_ip;
                wt = e.wt;
                return *this;
            }

            string get_node_name() const { return dest_name; }
            void set_node_name(const string& n) { dest_name = n; }
            int get_wt() const { return wt; }
            void set_wt(int w) { wt = w; }
            unsigned int get_dst_ip() const { return dst_ip; }
            void set_dst_ip(unsigned int i) { dst_ip = i; }
            ostream& print(ostream& f) const {
                f << dest_name;
                return f;
            }
        };

	// Graph nodes
        class node {
            public:
                typedef set<edge> edgeset_t;
            protected:
                string name;	    // Node name
                edgeset_t edges;    // edges (outgoing)
            public:
                node(const string& n): name(n), edges() { }
                node(const node& n) : name(n.name), edges(n.edges) { }
                void add_edge(const edge& e) {
                    edges.insert(e);
                }
                void add_edge(const string& en, int wt=0.0, int dip =0) {
                    add_edge(edge(en, wt, dip));
                }
		// Degree and size are the same
                int degree() const { return edges.size(); }
                int size() const { return edges.size(); }
                string get_name() const { return name; }
                void set_name(const string& n) { name = n ; }

		// Notice that these return copies.  Call replace_edge to
		// change the edge.
                edge get_edge(const edge& e) const {
                    set<edge>::iterator i = edges.find(e);
                    if ( i != edges.end() ) 
                        return *i;
                    else
                        throw runtime_error("No such edge");
                }

                edge get_edge(const string& s) const {
                    return get_edge(edge(s));
                }

                void replace_edge(const edge& e) {
                    remove_edge(e);
                    add_edge(e);
                }

                void remove_edge(const edge& e) {
                    set<edge>::iterator i = edges.find(e);
                    if ( i != edges.end()) edges.erase(i);
                    else throw runtime_error("No such edge (replace)");
                }

                void remove_edge(const string& n) {
                    remove_edge(edge(n));
                }


                edgeset_t::iterator begin() { return edges.begin(); }
                edgeset_t::iterator end() { return edges.end();}
                edgeset_t::const_iterator begin() const {
                    return edges.begin();
                }
                edgeset_t::const_iterator end() const {
                    return edges.end();
                }
        };

    // Graph operations
    protected:
        static void remove_node_from_nodemap(nodemap_t& nm, const string& n) {
            if (nm.count(n) > 0) nm.erase(n);
        }

        static string null_map(const string& s) { return s; }

    public:
        graph() : nodes() { }
	// Copy constructor
        graph(const graph& g) : nodes() { 
            for (nodemap_t::const_iterator i = g.begin(); i != g.end(); i++) {
                node *m = (*i).second;
                node *n = get_node((*i).first);
                for (node::edgeset_t::iterator j = m->begin(); 
                            j != m->end(); j++) 
                    n->add_edge(*j);
            }
        }
        int size() const { return nodes.size(); }
	// Return the node with the given name, creating it if it doesn't
	// exist.
        node *get_node(const string& n) {
            if ( nodes.count(n) > 0) 
                return nodes[n];
            else {
                node *nd = new node(n);
                nodes[n]  = nd;
                return nd;
            }
            return 0;
        }

	// You can't add nodes to a const graph, so return 0 if no such node.
        node* get_node(const string& n) const {
            nodemap_t::const_iterator i = nodes.find(n);

            if ( i != nodes.end()) return (*i).second;
            else return 0;
        }

        void remove_node(const string& n) {
            remove_node_from_nodemap(nodes, n);
            for (subgraph_t::iterator i = subgraphs.begin(); 
                    i != subgraphs.end(); i++) {
                nodemap_t& nm = (*i).second;

                remove_node_from_nodemap(nm, n);
            }
        }

	// Remove any edges that point to removed nodes.
        void fix_edges() {
            for (nodemap_t::iterator i= nodes.begin(); i!= nodes.end(); i++) {
                node *n = (*i).second;

                for (node::edgeset_t::iterator j=n->begin();
			j != n->end(); j++) {
                    if (!nodes.count((*j).get_node_name()))
                        n->remove_edge((*j));
                }
            }
        }

        /*
         * Make sure that all edges have a reverse edge.
         */
        void make_undirected() {
            for (graph::nodemap_t::const_iterator i = begin(); 
                    i != end(); i++) {
                string from = (*i).first;
                for (graph::node::edgeset_t::iterator j = (*i).second->begin();
                        j != (*i).second->end(); j++) {
                    if (from  == (*j).get_node_name()) continue;
                    if (!has_edge((*j).get_node_name(), from)) {
                            string to = (*j).get_node_name();
                            graph::node *n = get_node(to);
                            graph::edge e = (*i).second->get_edge(to);

                            e.set_node_name(from);
                            n->add_edge(e);
                    }
                }
            }
        }

	// Create a new graph with map applied to each node name.  Without
	// passing a map in, this just copies the graph.
        void map_graph(graph &g, string (*map)(const string&)=null_map) const {
            for (nodemap_t::const_iterator i= begin();
                    i != end(); i++) 
                g.get_node(map((*i).first));

            for (nodemap_t::const_iterator i= begin();
                    i != end(); i++) 
                for (node::edgeset_t::iterator j = (*i).second->begin();
                        j != (*i).second->end(); j++) {
                    node *n = g.get_node(map((*i).first));
                    edge e = *j;

                    e.set_node_name(map(e.get_node_name()));
                    n->add_edge(e);
                }
        }

	// True if there's an edge between nodes named f and t.
        bool has_edge(const string& f, const string& t) const {
            node *n = get_node(f);

            if (n) {
                try {
                    n->get_edge(t);
                    return true;
                }
                catch (exception& e) {
                    return false;
                }
            }
            else return false;
        }


	// Add n to the named subgraph
        void add_to_subgraph(node *n, const string& sg) {
            subgraphs[sg][n->get_name()] = n;
        }

	// For walking through the list of nodes.
        nodemap_t::const_iterator begin() const {
            return nodes.begin();
        }

        nodemap_t::const_iterator end() const {
            return nodes.end();
        }

	ostream& print(ostream& f)  const {
	    for (nodemap_t::const_iterator i = begin(); i != end(); i++) {
		node *n = (*i).second;
		f << n->get_name() << ":";
		copy(n->begin(), n->end(), 
			ostream_iterator<graph::edge>(f, ":"));
		f << endl;
	    }
	    return f;
	}
};

static inline ostream& operator<<(ostream& f, const graph::edge& e) {
    return e.print(f);
}

inline ostream& operator<<(ostream& f, const graph& g) { return g.print(f); }