Index: routing/routing.h
===================================================================
--- routing/routing.h	(revision f24fc8d239adc6a5e284628165cbb147c3c40449)
+++ routing/routing.h	(revision f24fc8d239adc6a5e284628165cbb147c3c40449)
@@ -0,0 +1,222 @@
+
+// This computes the all paris shortest paths between the various nodes in the
+// graph.  It can be used to induce a graph from another (that is, to remove
+// edges not used by the shortest paths)
+class routing {
+    public:
+        typedef vector<graph::node *> idx_to_node_t;
+        typedef vector<string> idx_to_node_name_t;
+        typedef map<string, int> node_name_to_idx_t;
+        typedef enum {SHORT, LONG, NONE} output_format;
+
+    protected:
+        const graph& g;		    // The graph to route in
+        int size;		    // The graph size (number of nodes)
+        int **cost;		    // The cost of the path from node i to j
+        int **path;		    // The next hop from i to j (an index)
+        idx_to_node_t idx_to_node;  // Map from the index to the node in g
+        idx_to_node_name_t idx_to_node_name;// map from index to name in g
+        node_name_to_idx_t node_name_to_idx;// Map from name to idx
+	static const int infinity = 1000000;
+
+	// Print the path from from to to into str, recursively as nodenames
+	// separated by slashes.
+        void pathstring(int from, int to, ostringstream& str) const {
+            if (path[from][to] !=-1) {
+                pathstring(from, path[from][to], str);
+                str << idx_to_node_name[path[from][to]] << "/";
+                pathstring(path[from][to], to, str);
+            }
+        }
+
+	// Print the path from from to to into str, recursively as indices
+	// separated by slashes.
+        void path_ints(int from, int to, ostringstream& str) const {
+
+            if (path[from][to] !=-1) {
+                path_ints(from, path[from][to], str);
+                str << path[from][to] << "/";
+                path_ints(path[from][to], to, str);
+            }
+        }
+
+	// Put the path from from to to into v in order, as indices
+        void path_ints_deque(int from, int to, deque<int>& v) const {
+            if (path[from][to] != -1) {
+                path_ints_deque(from, path[from][to], v);
+                v.push_back(path[from][to]);
+                path_ints_deque(path[from][to], to, v);
+            }
+        }
+
+	int next_hop(int src, int dest) const {
+	    // Find the next hop between src and dest.  The path member stores
+	    // this, but in an unusual way.  path[i][j] is a node
+	    // through which the shortest path between i and j passes, but may
+	    // not be adjacent to i (or j).  This member recursively asks for
+	    // the path until it finds a node adjacent to src in the graph.
+	    if (path[src][dest] == dest || path[src][dest] == -1) return dest;
+	    else return next_hop(src, path[src][dest]);
+	}
+
+    public:
+	// The initializer does the all pairs shortest path calculation
+	// (Floyd's algorithm).  This is n^3 in size of the graph, so don't
+	// make a routing object until/unless you need one.  If debug is set,
+	// the number of times through the outer loop is printed to it.
+        routing(const graph& gg, ostream *debug=0) :
+            g(gg), size(g.size()), 
+            cost(new int *[size]), path(new int *[size]), idx_to_node(size),
+            idx_to_node_name(size), node_name_to_idx() {
+                int i=0;    // Scratch
+
+		// Walk g and create indices
+                for (graph::nodemap_t::const_iterator ni = g.begin();
+                        ni != g.end(); ni++) {
+                    node_name_to_idx[(*ni).second->get_name()] = i;
+                    idx_to_node[i] = (*ni).second;
+                    idx_to_node_name[i] = (*ni).second->get_name();
+                    i++;
+                }
+
+		// Now initialize the path and cost matrices.
+                for (i = 0; i < size; i++) {
+                    graph::node *n = idx_to_node[i];
+                    int *row = new int[size];
+                    int *irow = new int[size];
+
+                    for (int j = 0; j < size; j++) {
+                        row[j] = infinity;
+                        irow[j] = -1;       // Direct link
+                    }
+
+		    // Fill in real valies for edges.
+                    for (set<graph::edge>::iterator ei = n->begin(); 
+                            ei != n->end(); ei ++) {
+                        string nn = (*ei).get_node_name();
+
+                        row[node_name_to_idx[nn]] = (*ei).get_wt();
+                        row[i] = 0.0;
+                    }
+                    cost[i] = row;
+                    path[i] = irow;
+                }
+
+		// Here's Floyd's algorithm. 
+                for (int k = 0; k < size; k++)  {
+                    if (debug) *debug << k << '\r';
+                    for (int i = 0; i< size; i++) 
+                        for (int j = 0; j < size; j++ ) 
+                            if (cost[i][j] > cost[i][k] + cost[k][j]) {
+                                cost[i][j] = cost[i][k] + cost[k][j];
+                                path[i][j] = k;
+                            }
+                }
+                if (debug) *debug << endl;
+            }
+
+	int path_cost(const string& src, const string& dest) const {
+	    //Return the cost of the computed path between src and dest.  There
+	    //are similar const issues as beloe in next_hop.
+	    node_name_to_idx_t::const_iterator f = node_name_to_idx.find(src);
+	    node_name_to_idx_t::const_iterator t = node_name_to_idx.find(dest);
+
+	    if ( f != node_name_to_idx.end() && t != node_name_to_idx.end())
+		return cost[(*f).second][(*t).second];
+	    else 
+		return infinity;
+	}
+
+	string next_hop(const string& src, const string& dest) const {
+	    // Convert the requests to ints and use the internal next hop.
+	    // The use of find and iterators is to avoid the potential side
+	    // effects of the more straightforward node_name_to_idx[src]
+	    // syntax.
+	    node_name_to_idx_t::const_iterator f = node_name_to_idx.find(src);
+	    node_name_to_idx_t::const_iterator t = node_name_to_idx.find(dest);
+	    int d = next_hop((*f).second, (*t).second);
+
+	    return idx_to_node_name[d];
+	}
+
+	// Print results
+        ostream& print(ostream& f, output_format fmt=SHORT) const {
+            if ( fmt == SHORT ) 
+                for (int i = 0; i < size; i++)
+                    f << i << ":" << idx_to_node_name[i] << endl;
+            for (int i = 0; i < size; i++) {
+                for (int j = 0; j < size; j++) {
+                    ostringstream s;
+                    if (fmt == LONG) {
+                       pathstring(i, j, s);
+                       f << idx_to_node_name[i] << "->" 
+                            << idx_to_node_name[j] << ":" 
+                            << cost[i][j] << ":"
+                            << idx_to_node_name[i] << "/"  << s.str() 
+                            << idx_to_node_name[j] << endl;
+                    }
+                    else if ( fmt == SHORT) {
+                       path_ints(i, j, s);
+                       f << i << "->" << j << ":"<< cost[i][j] << ":" 
+                            << i << "/" << s.str() << j << endl;
+                    }
+                }
+            }
+            return f;
+        }
+
+        static string null_map(const string& s) { return s; }
+
+	// form a graph in induced that is g without any edges not in the all
+	// pairs shortest path graph.  If inducing_dest is set, eliminate all
+	// edges that are not on a shortest path from some node to that node.
+	// Additionally, if newnode is passed in, apply it to rename all nodes
+	// in the new graph.
+        void induce(graph &induced, string *inducing_dest=0, 
+                string (*newnode)(const string&)=null_map) const {
+            int ind_idx = -1;	// The index of the inducing node
+
+	    // Make sure the inducing dest is there and set ind_idx
+            if (inducing_dest ) {
+                node_name_to_idx_t::const_iterator i = 
+                    node_name_to_idx.find(*inducing_dest);
+
+                if (i != node_name_to_idx.end()) ind_idx = (*i).second;
+                else throw runtime_error("No such dest ");
+            }
+
+	    // Insert all the nodes into induced using the side effects of
+	    // get_node.  This also maps the nodenames.
+            for (int i = 0; i < size; i++) 
+                induced.get_node(newnode(idx_to_node_name[i]));
+
+	    // Now  add the edges along each shortest path.
+            for (int i =0; i< size; i++) {
+                int jinit = ind_idx != -1 ? ind_idx : 0;
+                int jlim = inducing_dest ? jinit + 1: size;
+
+                for (int j = jinit; j< jlim; j++) {
+                    deque<int> v;
+                    if ( i == j ) continue;
+		    if (cost[i][j] >= infinity) continue;
+                    path_ints_deque(i, j, v);
+                    v.push_back(j);
+                    int ii = i;
+                    while (v.size()) {
+                        graph::node *n = 
+                            induced.get_node(newnode(idx_to_node_name[ii]));
+                        int jj = v.front();
+
+                        v.pop_front();
+                        n->add_edge(newnode(idx_to_node_name[jj]));
+                        ii = jj;
+                    }
+                }
+            }
+        }
+};
+
+static inline ostream& operator<<(ostream& f, const routing& r) {
+    return r.print(f);
+}
+
