source: routing/graph.h @ e8f2d4c

Last change on this file since e8f2d4c was f24fc8d, checked in by Ted Faber <faber@…>, 12 years ago

Routing under here, too

  • Property mode set to 100644
File size: 8.8 KB
Line 
1#include <map>
2#include <stdexcept>
3using namespace std;
4
5// The full graph
6class graph {
7    public:
8        class node;                 // fwd declaration
9        // Maps for going from name to node and for finding named subgraphs
10        typedef map<string, node *> nodemap_t;
11        typedef map<string, nodemap_t> subgraph_t;
12        // The nodes and subgraphs of this graph
13        nodemap_t nodes;
14        subgraph_t subgraphs;
15
16
17    public:
18        // An edge in a graph.  Accessors, etc. are straightforward
19        class edge {
20            protected:
21                string dest_name;       // The destination node's name
22                unsigned int dst_ip;    // Destination IP (if any)
23                int wt;                 // Edge weight
24            public:
25
26            edge(const string& n, int w=0, unsigned int dip=0):
27                dest_name(n), dst_ip(dip), wt(w) { }
28            edge(const edge& e) :
29                dest_name(e.dest_name), dst_ip(e.dst_ip), wt(e.wt) { }
30
31            bool operator<(const edge& e) const {
32                return dest_name < e.dest_name;
33            }
34
35            edge& operator=(const edge& e) {
36                dest_name = e.dest_name;
37                dst_ip = e.dst_ip;
38                wt = e.wt;
39                return *this;
40            }
41
42            string get_node_name() const { return dest_name; }
43            void set_node_name(const string& n) { dest_name = n; }
44            int get_wt() const { return wt; }
45            void set_wt(int w) { wt = w; }
46            unsigned int get_dst_ip() const { return dst_ip; }
47            void set_dst_ip(unsigned int i) { dst_ip = i; }
48            ostream& print(ostream& f) const {
49                f << dest_name;
50                return f;
51            }
52        };
53
54        // Graph nodes
55        class node {
56            public:
57                typedef set<edge> edgeset_t;
58            protected:
59                string name;        // Node name
60                edgeset_t edges;    // edges (outgoing)
61            public:
62                node(const string& n): name(n), edges() { }
63                node(const node& n) : name(n.name), edges(n.edges) { }
64                void add_edge(const edge& e) {
65                    edges.insert(e);
66                }
67                void add_edge(const string& en, int wt=0.0, int dip =0) {
68                    add_edge(edge(en, wt, dip));
69                }
70                // Degree and size are the same
71                int degree() const { return edges.size(); }
72                int size() const { return edges.size(); }
73                string get_name() const { return name; }
74                void set_name(const string& n) { name = n ; }
75
76                // Notice that these return copies.  Call replace_edge to
77                // change the edge.
78                edge get_edge(const edge& e) const {
79                    set<edge>::iterator i = edges.find(e);
80                    if ( i != edges.end() ) 
81                        return *i;
82                    else
83                        throw runtime_error("No such edge");
84                }
85
86                edge get_edge(const string& s) const {
87                    return get_edge(edge(s));
88                }
89
90                void replace_edge(const edge& e) {
91                    remove_edge(e);
92                    add_edge(e);
93                }
94
95                void remove_edge(const edge& e) {
96                    set<edge>::iterator i = edges.find(e);
97                    if ( i != edges.end()) edges.erase(i);
98                    else throw runtime_error("No such edge (replace)");
99                }
100
101                void remove_edge(const string& n) {
102                    remove_edge(edge(n));
103                }
104
105
106                edgeset_t::iterator begin() { return edges.begin(); }
107                edgeset_t::iterator end() { return edges.end();}
108                edgeset_t::const_iterator begin() const {
109                    return edges.begin();
110                }
111                edgeset_t::const_iterator end() const {
112                    return edges.end();
113                }
114        };
115
116    // Graph operations
117    protected:
118        static void remove_node_from_nodemap(nodemap_t& nm, const string& n) {
119            if (nm.count(n) > 0) nm.erase(n);
120        }
121
122        static string null_map(const string& s) { return s; }
123
124    public:
125        graph() : nodes() { }
126        // Copy constructor
127        graph(const graph& g) : nodes() { 
128            for (nodemap_t::const_iterator i = g.begin(); i != g.end(); i++) {
129                node *m = (*i).second;
130                node *n = get_node((*i).first);
131                for (node::edgeset_t::iterator j = m->begin(); 
132                            j != m->end(); j++) 
133                    n->add_edge(*j);
134            }
135        }
136        int size() const { return nodes.size(); }
137        // Return the node with the given name, creating it if it doesn't
138        // exist.
139        node *get_node(const string& n) {
140            if ( nodes.count(n) > 0) 
141                return nodes[n];
142            else {
143                node *nd = new node(n);
144                nodes[n]  = nd;
145                return nd;
146            }
147            return 0;
148        }
149
150        // You can't add nodes to a const graph, so return 0 if no such node.
151        node* get_node(const string& n) const {
152            nodemap_t::const_iterator i = nodes.find(n);
153
154            if ( i != nodes.end()) return (*i).second;
155            else return 0;
156        }
157
158        void remove_node(const string& n) {
159            remove_node_from_nodemap(nodes, n);
160            for (subgraph_t::iterator i = subgraphs.begin(); 
161                    i != subgraphs.end(); i++) {
162                nodemap_t& nm = (*i).second;
163
164                remove_node_from_nodemap(nm, n);
165            }
166        }
167
168        // Remove any edges that point to removed nodes.
169        void fix_edges() {
170            for (nodemap_t::iterator i= nodes.begin(); i!= nodes.end(); i++) {
171                node *n = (*i).second;
172
173                for (node::edgeset_t::iterator j=n->begin();
174                        j != n->end(); j++) {
175                    if (!nodes.count((*j).get_node_name()))
176                        n->remove_edge((*j));
177                }
178            }
179        }
180
181        /*
182         * Make sure that all edges have a reverse edge.
183         */
184        void make_undirected() {
185            for (graph::nodemap_t::const_iterator i = begin(); 
186                    i != end(); i++) {
187                string from = (*i).first;
188                for (graph::node::edgeset_t::iterator j = (*i).second->begin();
189                        j != (*i).second->end(); j++) {
190                    if (from  == (*j).get_node_name()) continue;
191                    if (!has_edge((*j).get_node_name(), from)) {
192                            string to = (*j).get_node_name();
193                            graph::node *n = get_node(to);
194                            graph::edge e = (*i).second->get_edge(to);
195
196                            e.set_node_name(from);
197                            n->add_edge(e);
198                    }
199                }
200            }
201        }
202
203        // Create a new graph with map applied to each node name.  Without
204        // passing a map in, this just copies the graph.
205        void map_graph(graph &g, string (*map)(const string&)=null_map) const {
206            for (nodemap_t::const_iterator i= begin();
207                    i != end(); i++) 
208                g.get_node(map((*i).first));
209
210            for (nodemap_t::const_iterator i= begin();
211                    i != end(); i++) 
212                for (node::edgeset_t::iterator j = (*i).second->begin();
213                        j != (*i).second->end(); j++) {
214                    node *n = g.get_node(map((*i).first));
215                    edge e = *j;
216
217                    e.set_node_name(map(e.get_node_name()));
218                    n->add_edge(e);
219                }
220        }
221
222        // True if there's an edge between nodes named f and t.
223        bool has_edge(const string& f, const string& t) const {
224            node *n = get_node(f);
225
226            if (n) {
227                try {
228                    n->get_edge(t);
229                    return true;
230                }
231                catch (exception& e) {
232                    return false;
233                }
234            }
235            else return false;
236        }
237
238
239        // Add n to the named subgraph
240        void add_to_subgraph(node *n, const string& sg) {
241            subgraphs[sg][n->get_name()] = n;
242        }
243
244        // For walking through the list of nodes.
245        nodemap_t::const_iterator begin() const {
246            return nodes.begin();
247        }
248
249        nodemap_t::const_iterator end() const {
250            return nodes.end();
251        }
252
253        ostream& print(ostream& f)  const {
254            for (nodemap_t::const_iterator i = begin(); i != end(); i++) {
255                node *n = (*i).second;
256                f << n->get_name() << ":";
257                copy(n->begin(), n->end(), 
258                        ostream_iterator<graph::edge>(f, ":"));
259                f << endl;
260            }
261            return f;
262        }
263};
264
265static inline ostream& operator<<(ostream& f, const graph::edge& e) {
266    return e.print(f);
267}
268
269inline ostream& operator<<(ostream& f, const graph& g) { return g.print(f); }
270
Note: See TracBrowser for help on using the repository browser.