Index: routing/Makefile
===================================================================
--- routing/Makefile	(revision f24fc8d239adc6a5e284628165cbb147c3c40449)
+++ routing/Makefile	(revision f24fc8d239adc6a5e284628165cbb147c3c40449)
@@ -0,0 +1,23 @@
+ALL=routing collapse_route
+
+all: ${ALL}
+
+# pmake
+.NULL:  .out
+
+.o.out:
+	${CXX} ${CXXFLAGS} ${LDFLAGS} -o $@ $> ${LDLIBS}
+
+# gmake
+CXXFLAGS?=-O2
+.o:
+	${CXX} ${CXXFLAGS} ${LDFLAGS} -o $@ $^ ${LDLIBS}
+
+routing.o: routing.cc routing.h graph.h route_table.h
+collapse_route.o:	collapse_route.cc route_table.h net.h
+
+routing:	routing.o
+collapse_route: collapse_route.o
+
+clean:
+	rm -f ${ALL} *.o
Index: routing/collapse_route.cc
===================================================================
--- routing/collapse_route.cc	(revision f24fc8d239adc6a5e284628165cbb147c3c40449)
+++ routing/collapse_route.cc	(revision f24fc8d239adc6a5e284628165cbb147c3c40449)
@@ -0,0 +1,36 @@
+#include <cstdlib>
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <iomanip>
+
+#include <algorithm>
+#include <vector>
+#include <set>
+#include <map>
+
+#include "net.h"
+#include "route_table.h"
+
+using namespace std;
+
+int main(int argc, char **argv) {
+    string line;
+    route_table rt;
+
+    if (argc < 2) {
+	cerr << "Usage: collapse_route file" << endl;
+	exit(20);
+    }
+
+    ifstream inp(argv[1]);
+    while ( getline(inp, line, '\n')) {
+	Net dest_net(line);
+	Host next_hop(line.substr(line.find(' ')));
+
+	rt.insert(dest_net, next_hop);
+    }
+
+    rt.collapse();
+    cout << rt;
+}
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); }
+
Index: routing/net.h
===================================================================
--- routing/net.h	(revision f24fc8d239adc6a5e284628165cbb147c3c40449)
+++ routing/net.h	(revision f24fc8d239adc6a5e284628165cbb147c3c40449)
@@ -0,0 +1,97 @@
+#ifndef NET_H
+#define NET_H
+
+#include <cstdlib>
+#include <iostream>
+#include <string>
+
+class Net {
+    // A network. It has a mask and an address.  The mask is the mask size in
+    // consecutive bits: net= 10.0.0.0 mask =8 means 0xa000000000 network and
+    // 0xff000000 mask.  Masked bits are always 0 in net.
+    protected:
+	int net;    // Network 
+	int mask;   // Mask
+	// Clear the net to the mask.
+	void normalize() { net &= 0xffffffff & (0xffffffff << (32 - mask)); }
+    public:
+	Net(const Net& n) : net(n.net), mask(n.mask) { normalize(); }
+	// m is the number of consecutive 1 bits in the mask.
+	Net(int n, int m) : net(n), mask(m) { normalize(); }
+
+	// Parse a string of the form n.n.n.n/m
+	Net(const std::string& s) : net(0), mask(0) {
+	    std::string::size_type mi = s.find("/");
+
+	    if ( mi != std::string::npos ) mask = atoi(s.substr(mi+1).c_str());
+	    else mask = 32;
+
+	    std::string::size_type p = 0;
+	    for (int i = 24; i >= 0; i -= 8 ) {
+		int x = atoi(s.substr(p).c_str());
+		net |= (x) << i;
+		
+		if ( (p = s.find(".", p)) != std::string::npos) p++;
+	    }
+	    normalize();
+	}
+
+	// Accessors
+	int get_net() const { return net; }
+	void set_net(int n) { net = n; normalize(); }
+	int get_mask() const { return mask; }
+	void set_mask(int m) { mask = m; normalize(); }
+
+	// Output in n.n.n.n/m format.
+	std::ostream& print(std::ostream& f) const {
+	    f << ( (net & 0xff000000) >> 24) << ".";
+	    f << ( (net & 0x00ff0000) >> 16) << ".";
+	    f << ( (net & 0x0000ff00) >>  8) << ".";
+	    f << ( (net & 0x000000ff));
+	    f << "/" << mask;
+	    return f;
+	}
+
+	// True if the given net is inside this net using this net's mask
+	bool inside(const Net& n) const {
+	    Net tn = Net(net, n.mask);
+	    return (tn.net ^ n.net) == 0;
+	}
+
+	// Standard operators
+	bool operator==(const Net& n) const {
+	    return net == n.net && mask == n.mask;
+	}
+
+	bool operator<(const Net& n) const {
+	    return mask < n.mask || ( (mask == n.mask) && (net < n.net));
+	}
+};
+
+// Convenient << defintion for output
+inline std::ostream& operator<<(std::ostream& f, const Net& n) {
+    return n.print(f);
+}
+
+// A Net specialized to have a 32 bit mask and print without the /
+class Host : public Net {
+    public:
+	Host(const Host& h) : Net(h) { }
+	Host(int h) : Net(h, 32) { }
+	Host(const std::string& s) : Net(s) { }
+
+	std::ostream& print(std::ostream& f) const {
+	    f << ( (net & 0xff000000) >> 24) << ".";
+	    f << ( (net & 0x00ff0000) >> 16) << ".";
+	    f << ( (net & 0x0000ff00) >>  8) << ".";
+	    f << ( (net & 0x000000ff));
+	    return f;
+	}
+};
+
+// Convenient << defintion for output
+inline std::ostream& operator<<(std::ostream& f, const Host& n) { 
+    return n.print(f);
+}
+
+#endif
Index: routing/route_table.h
===================================================================
--- routing/route_table.h	(revision f24fc8d239adc6a5e284628165cbb147c3c40449)
+++ routing/route_table.h	(revision f24fc8d239adc6a5e284628165cbb147c3c40449)
@@ -0,0 +1,186 @@
+#ifndef ROUTE_TABLE_H
+#define ROUTE_TABLE_H
+
+#include "net.h"
+#include <vector>
+#include <set>
+#include <map>
+
+#include <algorithm>
+#include <functional>
+#include <ext/functional>
+
+using __gnu_cxx::compose1;
+
+class route_table {
+    protected:
+	typedef std::set<Net> net_set_t;
+	typedef std::map<Net, Host> net_map_t;
+	typedef std::map<Host, net_set_t> route_map_t;
+	route_map_t rm;
+	net_map_t nm;
+	net_set_t empty;
+	// Helper functor that just returns the first member of a
+	// pair
+	template <class p>
+	    class select1st {
+		public:
+		typename p::first_type operator()(p x) const { return x.first; }
+	    };
+
+	class contains : public std::unary_function<Net, bool> {
+	    protected:
+		const Net& container;   // Net that may contain test values
+	    public:
+		contains(const Net& c) : container(c) { }
+		bool operator()(const Net& n) const {
+		    return n.inside(container);
+		}
+	};
+
+	class set_remover : public std::unary_function<Net, void> {
+	    protected:
+		net_set_t& s;
+	    public:
+		set_remover(net_set_t& ss) : s(ss) { }
+		void operator()(const Net& n) { s.erase(n); }
+	};
+
+    public:
+	route_table() : rm(), nm(), empty() { }
+	void insert(const Net& dest, const Host& gw) {
+	    net_map_t::iterator n = nm.find(dest);
+
+	    if ( n == nm.end() || gw < (*n).second) {
+		// never seen this network before, insert it, or it's a
+		// duplicate and the next hop is a lower IP address than the
+		// last attempted insert.  Keep the lower GW for consistency
+		// (Remove any dupes, though)
+		if (gw <  (*n).second) {
+		    remove(dest, (*n).second);
+		}
+
+		route_map_t::iterator r = rm.find(gw);
+
+		if ( r != rm.end()) {
+		    (*r).second.insert(dest);
+		}
+		else { 
+		    rm[gw] = net_set_t();
+		    rm[gw].insert(dest);
+		}
+		nm.insert(net_map_t::value_type(dest, gw));
+	    }
+	}
+	const net_set_t& get(const Host& gw) const { 
+	    route_map_t::const_iterator r = rm.find(gw);
+
+	    if ( r != rm.end()) return (*r).second;
+	    else return empty;
+	}
+
+	void remove(const Net& dest, const Host& gw) {
+	    route_map_t::iterator r = rm.find(gw);
+
+	    if ( r != rm.end()) {
+		(*r).second.erase(dest);
+		// Remove the entry from the netmap
+		nm.erase(dest);
+		// If this gateway has no destinations, remove it from the map
+		// all togther.
+		if ((*r).second.empty()) 
+		    rm.erase(gw);
+	    }
+	}
+
+	std::ostream& print(std::ostream& f) const {
+	    for (route_map_t::const_iterator i = rm.begin(); i != rm.end(); i++)
+		for (net_set_t::const_iterator j = (*i).second.begin();
+			j != (*i).second.end(); j++)
+		    f << (*j) << " " << (*i).first << std::endl;
+	    return f;
+	}
+
+	bool collision(const Net& tryit, const Host& out) const {
+	    // Return true if there is a routing in rm that would be dirsupted
+	    // by adding the net in tryit to the out gateway.  That is, if any
+	    // destination network on another interface is inside tryit, return
+	    // false.
+	    for (route_map_t::const_iterator r = rm.begin(); 
+		    r != rm.end(); r++) {
+		if ((*r).first == out) continue;
+		for (net_set_t::const_iterator n = (*r).second.begin(); 
+			n != (*r).second.end(); n++) {
+		    if ((*n).inside(tryit)) return true;
+		}
+	    }
+	    return false;
+	}
+
+
+	void collapse() {
+	    // Try to make rm as small as possible by expanding each
+	    // destination network until it either conflicts with a destination
+	    // network on another gateway or is a /8.
+	    std::vector<Host> gateways;
+
+	    transform(rm.begin(), rm.end(), back_inserter(gateways), 
+		    select1st<route_map_t::value_type>());
+
+	    for (std::vector<Host>::const_iterator gw = gateways.begin(); 
+		    gw != gateways.end(); gw++) {
+		// Try to expand all the destinations on gw.  Copy them into
+		// candidates for expansion and try all the candidates.
+		net_set_t candidates = get(*gw);
+
+		while (! candidates.empty()) {
+
+		    // Pop a value from the set.
+		    Net tryit = *candidates.begin();
+		    candidates.erase(tryit);
+
+		    // While it grows, try to expand it and remove any networks
+		    // it expands over.
+		    bool growing = true;
+		    while (growing && tryit.get_mask() > 8) {
+			tryit.set_mask(tryit.get_mask() - 1);
+
+			if ( collision(tryit, *gw) ) {
+			    growing = false; 
+			}
+			else {
+			    // Successfully got bigger.  Remove nets inside the
+			    // new new from the routing table and candidate
+			    // set, and insert the larger net into the table.
+			    std::vector<Net> to_remove;
+
+			    // Collect the Nets to remove
+			    std::remove_copy_if(get(*gw).begin(), 
+				    get(*gw).end(),
+				    std::back_inserter(to_remove),
+				    compose1(std::logical_not<bool>(),
+					contains(tryit)));
+			    // Remove 'em - calling remove makes sure the
+			    // internal route_table data structures stay in
+			    // sync.  This has been a bug source in the past.
+			    for (std::vector<Net>::const_iterator tr = 
+				    to_remove.begin(); 
+				    tr != to_remove.end(); tr++) {
+				remove(*tr, *gw);
+				candidates.erase(*tr);
+			    }
+			    // New bigger candidate gots into the route_table
+			    // here.
+			    insert(tryit, *gw);
+			}
+		    }
+		}
+	    }
+	}
+};
+
+inline std::ostream& operator<<(std::ostream& f, const route_table& rt ) {
+    return rt.print(f);
+}
+
+#endif
Index: routing/routing.cc
===================================================================
--- routing/routing.cc	(revision f24fc8d239adc6a5e284628165cbb147c3c40449)
+++ routing/routing.cc	(revision f24fc8d239adc6a5e284628165cbb147c3c40449)
@@ -0,0 +1,399 @@
+#include <iostream>
+#include <fstream>
+#include <sstream>
+#include <string>
+#include <vector>
+#include <set>
+#include <map>
+#include <deque>
+#include <iterator>
+
+#include <getopt.h>
+
+#include "graph.h"
+#include "routing.h"
+
+#include "net.h"
+#include "route_table.h"
+
+typedef set<string> addr_set_t;
+typedef map<string, string> addr_map_t;
+typedef map<string, set<string> > addr_set_map_t;
+
+using namespace std;
+
+// Functor called by a for_each to remove a node (address) from the graph
+class node_remover : public unary_function<string, void> {
+    protected:
+	graph &g;
+    public:
+	node_remover(graph& gg) : g(gg) { }
+	void operator()(const string &s) { g.remove_node(s); }
+};
+
+// Functor called by for_each to remove a node (leaf) from the given set.
+class leaf_remover : public unary_function<string, void> {
+    protected:
+	addr_set_t &l;
+    public:
+	leaf_remover(addr_set_t& ll) : l(ll) { }
+	void operator()(const string &s) { l.erase(s); }
+};
+
+// Functor called by for_each to print a node's forwarding table to a file with
+// the name of the node (a parameter) in the outdir specified at object
+// creation time.  Also in the object are sets of destination objects, a map
+// from node name to addresses, and the map from interfaces to leaf nodes.  The
+// full routing matrix is also a parameter at creation time.
+class node_writer : public unary_function<string, void> {
+    protected:
+	addr_set_t& addrs;	    // All destination addresses
+	addr_set_map_t& node_addrs; // Node name to address set map
+	addr_set_map_t& children;   // Leaf nodes attached to an interface
+	routing& r;		    // The routing
+	const string& outdir;	    // The output directory
+	bool compress;		    // True if we are compressing tables
+	ostream *verbose;	    // Pointer to verbouse output stream
+	mutable int num;	    // Number of calls to this functor
+    public:
+	node_writer(addr_set_t& a, addr_set_map_t& na, addr_set_map_t& c,
+	    routing& rr, const string& od, bool cm, ostream *v) : 
+	    addrs(a), node_addrs(na), children(c), r(rr), outdir(od),
+	    compress(cm), verbose(v), num(0) { }
+
+	void operator()(const string &n) const {
+	    string out_fn = outdir + "/" + n ;	    // destination filename
+	    ofstream out(out_fn.c_str());	    // output stream
+	    addr_set_t& my_addrs = node_addrs[n];   // this node's addresses
+	    route_table rt;			    // The routes to compress
+
+	    // Build the route table
+	    for (addr_set_t::const_iterator d = addrs.begin(); 
+		    d != addrs.end(); 
+		    d++) {
+		// Find the best route to each destination.  Because a node may
+		// have multiple addresses, we have to check each outgoing
+		// interface and pick the shortest.
+		string src;	// outgoing interface of best route
+		int best = 0;	// length of best route
+		string nh;	// The next hop IP address for shortest route
+
+		for (addr_set_t::const_iterator i = my_addrs.begin(); 
+			i != my_addrs.end(); i++) {
+		    if (src.empty() || r.path_cost(*i, *d) < best ) { 
+			src = *i;
+			best = r.path_cost(*i, *d);
+		    }
+		}
+
+		// Ignore single hop paths unless not compressing.
+		if (r.path_cost(src, *d) > 1 || !compress) {
+		    nh = r.next_hop(src, *d);
+
+		    if ( !nh.empty() ) {
+			// Insert the nodes as the /24 containing them
+			Net n(*d);
+			n.set_mask(24);
+			rt.insert(n, Host(nh));
+		    }
+		}
+		else nh = *d;
+
+		// Output children of the destination unless they are this
+		// node's children and we are compressing.
+		if ( my_addrs.count(*d) == 0 || !compress) {
+		    addr_set_map_t::iterator c = children.find(*d);
+
+		    if ( c != children.end()) {
+			Host gw = Host(nh);
+			for (addr_set_t::const_iterator i = (*c).second.begin();
+				i != (*c).second.end(); i++) 
+			    rt.insert(Net(*i), gw);
+		    }
+		}
+
+	    }
+	    // Collapse the route map (if we're compressing) and print it
+	    if (compress) rt.collapse();
+	    out << rt;
+	    if (verbose && ++num % 10 == 0)
+		*verbose << num << '\r';
+	}
+};
+
+// Functor to output a leaf node's routing table.  The table has the same name
+// as the node and is output into outdir.  The parent_addr map (node to parent
+// address) is passed in.
+class leaf_writer : public unary_function<string, void> {
+    protected:
+	addr_map_t& parent_addr;    // Parent address map
+	addr_set_t& addrs;	    // All destination addresses
+	addr_set_map_t& children;   // Leaf nodes attached to an interface
+	const string& outdir;	    // The output directory
+	bool compress;		    // Compress routing tables
+	ostream *verbose;	    // Verbose output
+	mutable int num;	    // Number of calls on this functor
+    public:
+	leaf_writer(addr_map_t& pa, addr_set_t& a, addr_set_map_t& c, 
+		const string& od, bool cm, ostream *v ) :
+	    parent_addr(pa), addrs(a), children(c), outdir(od), compress(cm),
+	    verbose(v), num(0) { }
+	void operator()(const string &n) const {
+	    string out_fn = outdir + "/" + n;
+	    ofstream out(out_fn.c_str());
+
+	    // Compressed leaves have a single default route
+	    if (compress) 
+		out << "10.0.0.0/8 " << parent_addr[n] << endl;
+	    else {
+		// For uncompressed leaves, all thr routes go to the parent,
+		// but we have to enumerate them as all addresses and the
+		// children of any address with leaves.
+		string my_parent = parent_addr[n];
+
+		out << my_parent << "/32 " << my_parent << endl;
+		for (addr_set_t::const_iterator d = addrs.begin(); 
+			d != addrs.end(); d++) {
+		    out << *d << "/32 " << my_parent << endl;
+
+		    addr_set_map_t::iterator c = children.find(*d);
+		    
+		    if ( c != children.end() ) {
+			for (addr_set_t::const_iterator i = (*c).second.begin();
+				i != (*c).second.end(); i++) 
+			    out << *i << "/32 " << my_parent << endl;
+		    }
+		}
+	    }
+	    if (verbose && ++num % 10 == 0) 
+		*verbose << num << '\r';
+	}
+};
+
+
+void parse_graph_description(graph& g, addr_set_t& nodes, addr_set_t& addrs,
+	addr_set_t& leaves, addr_map_t& leaf_addr, addr_set_map_t& node_addrs,
+	istream *in=0) {
+    // Create the basic data structures from the input format.  The input is a
+    // series of lines of the form:
+    // node: addr,addr,addr
+    // or
+    // addr: addr,addr,addr
+    //
+    // The first line lists a node's interfaces and the second the
+    // interconnections between addresses.  The nodes are captured in nodes and
+    // leaves (a potential leaf is in both, nodes with multiple interfaces are
+    // only in nodes).  Addrs is all addresses, leaf_add maps a leaf node to
+    // its only address, node_addrs maps each node or leaf to its address(es).
+    // g is the grahp of address interconnections.
+    string line;    // Currnet line
+    if (!in ) in = &cin;
+
+    while (getline(*in, line, '\n')) {
+	string::size_type p = line.find(':');	// String offsets for parsing
+	string::size_type q;			// String offsets for parsing
+	string name;				// Node name
+	string ename;				// Edge name (an address)
+	graph::node *node = 0;			// Curren graph node (address)
+	bool make_node;				// True if this is a node
+	addr_set_t my_addrs;			// Current set of node addrs
+
+	if (p != string::npos) {
+	    name = line.substr(0, p);
+	    if (name.find_first_not_of("0123456789.") != string::npos) {
+		make_node = true;
+	    }
+	    else {
+		node = g.get_node(name);
+		addrs.insert(name);
+		make_node = false;
+	    }
+	}
+	else continue;
+	p += 2;
+	while ( (q = line.find(',', p)) != string::npos) {
+	    ename = line.substr(p, q-p);
+	    if (make_node) {
+		my_addrs.insert(ename);
+	    }
+	    else {
+		g.get_node(ename);
+		node->add_edge(ename, 1.0);
+	    }
+	    p = q+1;
+	}
+	ename = line.substr(p);
+	if (make_node) {
+	    my_addrs.insert(ename);
+
+	    nodes.insert(name);
+	    node_addrs[name] = my_addrs;
+	    if (my_addrs.size() == 1) {
+		// Potential leaf node.  No need to cross connect, but we do
+		// need to list it and its interfaces as leaves.  We won't know
+		// if it is a leaf node until we find out if it is on a lan.
+		leaves.insert(name);
+		leaf_addr[name] = ename;
+	    }
+	    else {
+		// Not a leaf.  Add it to nodes and interconnect its interfaces.
+		for (addr_set_t::const_iterator i = node_addrs[name].begin();
+			i != node_addrs[name].end(); i ++) {
+		    for (addr_set_t::const_iterator j =node_addrs[name].begin();
+			    j != node_addrs[name].end(); j ++) {
+			if ( *i != *j && !g.has_edge(*i, *j)) {
+			    graph::node *a = g.get_node(*i);
+			    g.get_node(*j);
+			    a->add_edge(*j, 1.0);
+			}
+		    }
+		}
+	    }
+	}
+	else {
+	    g.get_node(ename);
+	    node->add_edge(ename, 1.0);
+	}
+    }
+}
+
+void trim_leaves(graph &g, addr_set_t& nodes, addr_set_t& leaves, 
+	addr_map_t& leaf_addr, addr_set_t& addrs, addr_map_t& parent_addr, 
+	addr_set_map_t& children) {
+    // Leaves is the set of nodes that may be leaves - nodes connected to one
+    // node.  Walk that set, eliminate false positives, and for the real leaves
+    // remove them from the node set, the addr_set and set their parent_addr
+    // (the upstream interface), and add the leaf to the parent interface's
+    // children map.
+
+    addr_set_t graph_remove;	// nodes to remove from the graph
+    addr_set_t leaf_remove;	// leaves to remove from the leaves set.
+
+    for (addr_set_t::const_iterator l = leaves.begin(); l != leaves.end(); 
+	    l++) {
+	string la = leaf_addr[*l];	    // leaf address
+	graph::node *ln = g.get_node(la);   // leaf address node
+	if (ln-> degree() == 1 ) {
+	    graph::edge e = *ln->begin();	    // edge
+	    string pa = e.get_node_name();	    // parent address
+	    addr_set_map_t::iterator c = children.find(pa); // children entry 
+
+	    parent_addr[*l] = pa;
+	    if (c != children.end() ) 
+		(*c).second.insert(la);
+	    else {
+		children[pa] = addr_set_t();
+		children[pa].insert(la);
+	    }
+	    // This is a confirmed leaf, so get it out of nodes.
+	    nodes.erase(*l);
+	    // NB cannot remove parent address as it may be a destination from
+	    // other palces in the net.
+	    graph_remove.insert(la);
+	    addrs.erase(la);
+	}
+	else {
+	    // Not a leaf after all, leave it in nodes and remove it from
+	    // leaves.
+	    leaf_remove.insert(*l);
+	}
+
+    }
+    // Clean up the data structures we've been pulling things from.
+    for_each(graph_remove.begin(), graph_remove.end(), node_remover(g));
+    for_each(leaf_remove.begin(), leaf_remove.end(), leaf_remover(leaves));
+    g.fix_edges();
+}
+enum { OUTPUT_OPT='o', DEBUG_OPT='d', NOCOMPRESS_OPT='C', INPUT_OPT='f'};
+struct option opts[] = {
+    { "output", required_argument, 0, OUTPUT_OPT}, 
+    { "input", required_argument, 0, INPUT_OPT}, 
+    { "debug", no_argument, 0, DEBUG_OPT}, 
+    { "uncompressed", required_argument, 0, NOCOMPRESS_OPT}, 
+};
+
+void fatal(const string& my_name) {
+    cerr << "Usage: " << my_name << 
+	": [options] [outputdir [filename]]" << endl;
+    exit(20);
+}
+
+
+int main(int argc, char**argv) {
+    addr_set_t nodes;		// Set of nodenames (not addresses)
+    addr_set_t addrs;		// All valid destination addresses
+    addr_set_t leaves;		// Leaf nodes
+    addr_map_t parent_addr;	// Map from leaf address to parent address
+    addr_map_t leaf_addr;	// Map from leaf node name to leaf address
+    addr_set_map_t node_addrs;	// Map from each node to its addresses
+    addr_set_map_t children;	// Map from a parent addess to its 
+				// leaf children
+    graph g;			// Graph represention
+    string my_name = argv[0];	// The name of the program
+    string outdir;		// Output directory
+    string uncompressed_dir;	// Output for uncompressed routing tables
+    int fl;			// Option parsing
+    bool debug=false;		// True for debugging output
+    ifstream *inf = 0;		// Input file, if any
+
+    while (( fl = getopt_long(argc, argv, "o:dC:", opts, 0)) != -1) {
+	switch (fl) {
+	    case DEBUG_OPT:
+		debug = true;
+		break;
+	    case OUTPUT_OPT:
+		outdir = optarg;
+		break;
+	    case INPUT_OPT:
+		if (!(inf = new ifstream(optarg))) {
+		    cerr << "Cannot open " << optarg << endl;
+		    fatal(my_name);
+		}
+		break;
+	    case NOCOMPRESS_OPT:
+		uncompressed_dir=optarg;
+		break;
+	}
+    }
+    argc -= optind;
+    argv += optind;
+    if (argc > 0 && outdir.empty()) {
+	outdir = argv[0];
+	argc--; argv++;
+    }
+    if (argc > 0 && !inf) {
+	if (!(inf = new ifstream(optarg))) {
+	    cerr << "Cannot open " << optarg << endl;
+	    fatal(my_name);
+	}
+	argc--; argv++;
+    }
+
+    if (outdir.empty()) fatal(my_name);
+
+    parse_graph_description(g, nodes, addrs, leaves, leaf_addr, node_addrs,inf);
+    trim_leaves(g, nodes, leaves, leaf_addr, addrs, parent_addr, children);
+
+    routing r = routing(g, debug ? &cerr: 0);
+
+    for_each(nodes.begin(), nodes.end(), 
+	    node_writer(addrs, node_addrs, children, r, outdir, true,
+		debug ? &cerr : 0));
+    if (debug) cerr << endl;
+    for_each(leaves.begin(), leaves.end(), 
+	    leaf_writer(parent_addr, addrs, children, outdir, true,
+		debug ? &cerr : 0));
+    if (debug) cerr << endl;
+
+    if (!uncompressed_dir.empty()) {
+	for_each(nodes.begin(), nodes.end(), 
+		node_writer(addrs, node_addrs, children, r, 
+		    uncompressed_dir, false, debug ? &cerr : 0));
+	if (debug) cerr << endl;
+	for_each(leaves.begin(), leaves.end(), 
+		leaf_writer(parent_addr, addrs, children, 
+		    uncompressed_dir, false, debug ? &cerr : 0));
+	if (debug) cerr << endl;
+    }
+
+}
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);
+}
+
