source: routing/routing.h @ f0b96ba

// 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);
}