41 }; |
41 }; |
42 //Edges are double linked. |
42 //Edges are double linked. |
43 //The free edges are only single linked using the "next_in" field. |
43 //The free edges are only single linked using the "next_in" field. |
44 struct EdgeT |
44 struct EdgeT |
45 { |
45 { |
46 int head, tail; |
46 int target, source; |
47 int prev_in, prev_out; |
47 int prev_in, prev_out; |
48 int next_in, next_out; |
48 int next_in, next_out; |
49 //FIXME: is this necessary? |
49 //FIXME: is this necessary? |
50 // EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {} |
50 // EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {} |
51 }; |
51 }; |
102 int maxNodeId() const { return nodes.size(); } //FIXME: What is this? |
102 int maxNodeId() const { return nodes.size(); } //FIXME: What is this? |
103 ///\bug This function does something different than |
103 ///\bug This function does something different than |
104 ///its name would suggests... |
104 ///its name would suggests... |
105 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? |
105 int maxEdgeId() const { return edges.size(); } //FIXME: What is this? |
106 |
106 |
107 Node tail(Edge e) const { return edges[e.n].tail; } |
107 Node source(Edge e) const { return edges[e.n].source; } |
108 Node head(Edge e) const { return edges[e.n].head; } |
108 Node target(Edge e) const { return edges[e.n].target; } |
109 |
109 |
110 Node aNode(OutEdgeIt e) const { return edges[e.n].tail; } |
110 Node aNode(OutEdgeIt e) const { return edges[e.n].source; } |
111 Node aNode(InEdgeIt e) const { return edges[e.n].head; } |
111 Node aNode(InEdgeIt e) const { return edges[e.n].target; } |
112 |
112 |
113 Node bNode(OutEdgeIt e) const { return edges[e.n].head; } |
113 Node bNode(OutEdgeIt e) const { return edges[e.n].target; } |
114 Node bNode(InEdgeIt e) const { return edges[e.n].tail; } |
114 Node bNode(InEdgeIt e) const { return edges[e.n].source; } |
115 |
115 |
116 NodeIt& first(NodeIt& v) const { |
116 NodeIt& first(NodeIt& v) const { |
117 v=NodeIt(*this); return v; } |
117 v=NodeIt(*this); return v; } |
118 EdgeIt& first(EdgeIt& e) const { |
118 EdgeIt& first(EdgeIt& e) const { |
119 e=EdgeIt(*this); return e; } |
119 e=EdgeIt(*this); return e; } |
149 if(edges[it.n].next_in!=-1) { |
149 if(edges[it.n].next_in!=-1) { |
150 it.n=edges[it.n].next_in; |
150 it.n=edges[it.n].next_in; |
151 } |
151 } |
152 else { |
152 else { |
153 int n; |
153 int n; |
154 for(n=nodes[edges[it.n].head].next; |
154 for(n=nodes[edges[it.n].target].next; |
155 n!=-1 && nodes[n].first_in == -1; |
155 n!=-1 && nodes[n].first_in == -1; |
156 n = nodes[n].next) ; |
156 n = nodes[n].next) ; |
157 it.n = (n==-1)?-1:nodes[n].first_in; |
157 it.n = (n==-1)?-1:nodes[n].first_in; |
158 } |
158 } |
159 return it; |
159 return it; |
205 else { |
205 else { |
206 n = first_free_edge; |
206 n = first_free_edge; |
207 first_free_edge = edges[n].next_in; |
207 first_free_edge = edges[n].next_in; |
208 } |
208 } |
209 |
209 |
210 edges[n].tail = u.n; edges[n].head = v.n; |
210 edges[n].source = u.n; edges[n].target = v.n; |
211 |
211 |
212 edges[n].next_out = nodes[u.n].first_out; |
212 edges[n].next_out = nodes[u.n].first_out; |
213 if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n; |
213 if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n; |
214 edges[n].next_in = nodes[v.n].first_in; |
214 edges[n].next_in = nodes[v.n].first_in; |
215 if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n; |
215 if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n; |
230 |
230 |
231 if(edges[n].next_in!=-1) |
231 if(edges[n].next_in!=-1) |
232 edges[edges[n].next_in].prev_in = edges[n].prev_in; |
232 edges[edges[n].next_in].prev_in = edges[n].prev_in; |
233 if(edges[n].prev_in!=-1) |
233 if(edges[n].prev_in!=-1) |
234 edges[edges[n].prev_in].next_in = edges[n].next_in; |
234 edges[edges[n].prev_in].next_in = edges[n].next_in; |
235 else nodes[edges[n].head].first_in = edges[n].next_in; |
235 else nodes[edges[n].target].first_in = edges[n].next_in; |
236 |
236 |
237 if(edges[n].next_out!=-1) |
237 if(edges[n].next_out!=-1) |
238 edges[edges[n].next_out].prev_out = edges[n].prev_out; |
238 edges[edges[n].next_out].prev_out = edges[n].prev_out; |
239 if(edges[n].prev_out!=-1) |
239 if(edges[n].prev_out!=-1) |
240 edges[edges[n].prev_out].next_out = edges[n].next_out; |
240 edges[edges[n].prev_out].next_out = edges[n].next_out; |
241 else nodes[edges[n].tail].first_out = edges[n].next_out; |
241 else nodes[edges[n].source].first_out = edges[n].next_out; |
242 |
242 |
243 edges[n].next_in = first_free_edge; |
243 edges[n].next_in = first_free_edge; |
244 first_free_edge = n; |
244 first_free_edge = n; |
245 |
245 |
246 //Update dynamic maps |
246 //Update dynamic maps |