Index: routing/graph.h
===================================================================
--- routing/graph.h	(revision f24fc8d239adc6a5e284628165cbb147c3c40449)
+++ routing/graph.h	(revision f24fc8d239adc6a5e284628165cbb147c3c40449)
@@ -0,0 +1,270 @@
+#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); }
+
