adds an edge. Invalidates edge iterators for the source node
| 273 | |
| 274 | // adds an edge. Invalidates edge iterators for the source node |
| 275 | EdgeIterator InsertEdge(const NodeIterator from, const NodeIterator to, const EdgeDataT &data) |
| 276 | { |
| 277 | Node &node = node_array[from]; |
| 278 | EdgeIterator one_beyond_last_of_node = node.edges + node.first_edge; |
| 279 | // if we can't write at the end of this nodes edges |
| 280 | // that is: the end is the end of the edge_list, |
| 281 | // or the beginning of the next nodes edges |
| 282 | if (one_beyond_last_of_node == edge_list.size() || !isDummy(one_beyond_last_of_node)) |
| 283 | { |
| 284 | // can we write before this nodes edges? |
| 285 | if (node.first_edge != 0 && isDummy(node.first_edge - 1)) |
| 286 | { |
| 287 | node.first_edge--; |
| 288 | edge_list[node.first_edge] = edge_list[node.first_edge + node.edges]; |
| 289 | } |
| 290 | else |
| 291 | { |
| 292 | // we have to move this nodes edges to the end of the edge_list |
| 293 | EdgeIterator newFirstEdge = (EdgeIterator)edge_list.size(); |
| 294 | unsigned newSize = node.edges * 1.1 + 2; |
| 295 | EdgeIterator requiredCapacity = newSize + edge_list.size(); |
| 296 | EdgeIterator oldCapacity = edge_list.capacity(); |
| 297 | // make sure there is enough space at the end |
| 298 | if (requiredCapacity >= oldCapacity) |
| 299 | { |
| 300 | edge_list.reserve(requiredCapacity * 1.1); |
| 301 | } |
| 302 | edge_list.resize(edge_list.size() + newSize); |
| 303 | // move the edges over and invalidate the old ones |
| 304 | for (const auto i : irange(0u, node.edges)) |
| 305 | { |
| 306 | edge_list[newFirstEdge + i] = edge_list[node.first_edge + i]; |
| 307 | makeDummy(node.first_edge + i); |
| 308 | } |
| 309 | // invalidate until the end of edge_list |
| 310 | for (const auto i : irange(node.edges + 1, newSize)) |
| 311 | { |
| 312 | makeDummy(newFirstEdge + i); |
| 313 | } |
| 314 | node.first_edge = newFirstEdge; |
| 315 | } |
| 316 | } |
| 317 | // get the position for the edge that is to be inserted |
| 318 | // and write it |
| 319 | Edge &edge = edge_list[node.first_edge + node.edges]; |
| 320 | edge.target = to; |
| 321 | edge.data = data; |
| 322 | ++number_of_edges; |
| 323 | ++node.edges; |
| 324 | return EdgeIterator(node.first_edge + node.edges); |
| 325 | } |
| 326 | |
| 327 | // removes an edge. Invalidates edge iterators for the source node |
| 328 | void DeleteEdge(const NodeIterator source, const EdgeIterator e) |