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;
+    }
+
+}
