1.1 --- a/lemon/list_graph.h Sun Nov 14 22:48:32 2010 +0100
1.2 +++ b/lemon/list_graph.h Mon Nov 15 09:46:08 2010 +0100
1.3 @@ -1599,6 +1599,885 @@
1.4 };
1.5
1.6 /// @}
1.7 +
1.8 + class ListBpGraphBase {
1.9 +
1.10 + protected:
1.11 +
1.12 + struct NodeT {
1.13 + int first_out;
1.14 + int prev, next;
1.15 + int partition_prev, partition_next;
1.16 + int partition_index;
1.17 + bool red;
1.18 + };
1.19 +
1.20 + struct ArcT {
1.21 + int target;
1.22 + int prev_out, next_out;
1.23 + };
1.24 +
1.25 + std::vector<NodeT> nodes;
1.26 +
1.27 + int first_node, first_red, first_blue;
1.28 + int max_red, max_blue;
1.29 +
1.30 + int first_free_red, first_free_blue;
1.31 +
1.32 + std::vector<ArcT> arcs;
1.33 +
1.34 + int first_free_arc;
1.35 +
1.36 + public:
1.37 +
1.38 + typedef ListBpGraphBase BpGraph;
1.39 +
1.40 + class Node {
1.41 + friend class ListBpGraphBase;
1.42 + protected:
1.43 +
1.44 + int id;
1.45 + explicit Node(int pid) { id = pid;}
1.46 +
1.47 + public:
1.48 + Node() {}
1.49 + Node (Invalid) { id = -1; }
1.50 + bool operator==(const Node& node) const {return id == node.id;}
1.51 + bool operator!=(const Node& node) const {return id != node.id;}
1.52 + bool operator<(const Node& node) const {return id < node.id;}
1.53 + };
1.54 +
1.55 + class Edge {
1.56 + friend class ListBpGraphBase;
1.57 + protected:
1.58 +
1.59 + int id;
1.60 + explicit Edge(int pid) { id = pid;}
1.61 +
1.62 + public:
1.63 + Edge() {}
1.64 + Edge (Invalid) { id = -1; }
1.65 + bool operator==(const Edge& edge) const {return id == edge.id;}
1.66 + bool operator!=(const Edge& edge) const {return id != edge.id;}
1.67 + bool operator<(const Edge& edge) const {return id < edge.id;}
1.68 + };
1.69 +
1.70 + class Arc {
1.71 + friend class ListBpGraphBase;
1.72 + protected:
1.73 +
1.74 + int id;
1.75 + explicit Arc(int pid) { id = pid;}
1.76 +
1.77 + public:
1.78 + operator Edge() const {
1.79 + return id != -1 ? edgeFromId(id / 2) : INVALID;
1.80 + }
1.81 +
1.82 + Arc() {}
1.83 + Arc (Invalid) { id = -1; }
1.84 + bool operator==(const Arc& arc) const {return id == arc.id;}
1.85 + bool operator!=(const Arc& arc) const {return id != arc.id;}
1.86 + bool operator<(const Arc& arc) const {return id < arc.id;}
1.87 + };
1.88 +
1.89 + ListBpGraphBase()
1.90 + : nodes(), first_node(-1),
1.91 + first_red(-1), first_blue(-1),
1.92 + max_red(-1), max_blue(-1),
1.93 + first_free_red(-1), first_free_blue(-1),
1.94 + arcs(), first_free_arc(-1) {}
1.95 +
1.96 +
1.97 + bool red(Node n) const { return nodes[n.id].red; }
1.98 + bool blue(Node n) const { return !nodes[n.id].red; }
1.99 +
1.100 + int maxNodeId() const { return nodes.size()-1; }
1.101 + int maxRedId() const { return max_red; }
1.102 + int maxBlueId() const { return max_blue; }
1.103 + int maxEdgeId() const { return arcs.size() / 2 - 1; }
1.104 + int maxArcId() const { return arcs.size()-1; }
1.105 +
1.106 + Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
1.107 + Node target(Arc e) const { return Node(arcs[e.id].target); }
1.108 +
1.109 + Node redNode(Edge e) const { return Node(arcs[2 * e.id].target); }
1.110 + Node blueNode(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
1.111 +
1.112 + static bool direction(Arc e) {
1.113 + return (e.id & 1) == 1;
1.114 + }
1.115 +
1.116 + static Arc direct(Edge e, bool d) {
1.117 + return Arc(e.id * 2 + (d ? 1 : 0));
1.118 + }
1.119 +
1.120 + void first(Node& node) const {
1.121 + node.id = first_node;
1.122 + }
1.123 +
1.124 + void next(Node& node) const {
1.125 + node.id = nodes[node.id].next;
1.126 + }
1.127 +
1.128 + void firstRed(Node& node) const {
1.129 + node.id = first_red;
1.130 + }
1.131 +
1.132 + void nextRed(Node& node) const {
1.133 + node.id = nodes[node.id].partition_next;
1.134 + }
1.135 +
1.136 + void firstBlue(Node& node) const {
1.137 + node.id = first_blue;
1.138 + }
1.139 +
1.140 + void nextBlue(Node& node) const {
1.141 + node.id = nodes[node.id].partition_next;
1.142 + }
1.143 +
1.144 + void first(Arc& e) const {
1.145 + int n = first_node;
1.146 + while (n != -1 && nodes[n].first_out == -1) {
1.147 + n = nodes[n].next;
1.148 + }
1.149 + e.id = (n == -1) ? -1 : nodes[n].first_out;
1.150 + }
1.151 +
1.152 + void next(Arc& e) const {
1.153 + if (arcs[e.id].next_out != -1) {
1.154 + e.id = arcs[e.id].next_out;
1.155 + } else {
1.156 + int n = nodes[arcs[e.id ^ 1].target].next;
1.157 + while(n != -1 && nodes[n].first_out == -1) {
1.158 + n = nodes[n].next;
1.159 + }
1.160 + e.id = (n == -1) ? -1 : nodes[n].first_out;
1.161 + }
1.162 + }
1.163 +
1.164 + void first(Edge& e) const {
1.165 + int n = first_node;
1.166 + while (n != -1) {
1.167 + e.id = nodes[n].first_out;
1.168 + while ((e.id & 1) != 1) {
1.169 + e.id = arcs[e.id].next_out;
1.170 + }
1.171 + if (e.id != -1) {
1.172 + e.id /= 2;
1.173 + return;
1.174 + }
1.175 + n = nodes[n].next;
1.176 + }
1.177 + e.id = -1;
1.178 + }
1.179 +
1.180 + void next(Edge& e) const {
1.181 + int n = arcs[e.id * 2].target;
1.182 + e.id = arcs[(e.id * 2) | 1].next_out;
1.183 + while ((e.id & 1) != 1) {
1.184 + e.id = arcs[e.id].next_out;
1.185 + }
1.186 + if (e.id != -1) {
1.187 + e.id /= 2;
1.188 + return;
1.189 + }
1.190 + n = nodes[n].next;
1.191 + while (n != -1) {
1.192 + e.id = nodes[n].first_out;
1.193 + while ((e.id & 1) != 1) {
1.194 + e.id = arcs[e.id].next_out;
1.195 + }
1.196 + if (e.id != -1) {
1.197 + e.id /= 2;
1.198 + return;
1.199 + }
1.200 + n = nodes[n].next;
1.201 + }
1.202 + e.id = -1;
1.203 + }
1.204 +
1.205 + void firstOut(Arc &e, const Node& v) const {
1.206 + e.id = nodes[v.id].first_out;
1.207 + }
1.208 + void nextOut(Arc &e) const {
1.209 + e.id = arcs[e.id].next_out;
1.210 + }
1.211 +
1.212 + void firstIn(Arc &e, const Node& v) const {
1.213 + e.id = ((nodes[v.id].first_out) ^ 1);
1.214 + if (e.id == -2) e.id = -1;
1.215 + }
1.216 + void nextIn(Arc &e) const {
1.217 + e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
1.218 + if (e.id == -2) e.id = -1;
1.219 + }
1.220 +
1.221 + void firstInc(Edge &e, bool& d, const Node& v) const {
1.222 + int a = nodes[v.id].first_out;
1.223 + if (a != -1 ) {
1.224 + e.id = a / 2;
1.225 + d = ((a & 1) == 1);
1.226 + } else {
1.227 + e.id = -1;
1.228 + d = true;
1.229 + }
1.230 + }
1.231 + void nextInc(Edge &e, bool& d) const {
1.232 + int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
1.233 + if (a != -1 ) {
1.234 + e.id = a / 2;
1.235 + d = ((a & 1) == 1);
1.236 + } else {
1.237 + e.id = -1;
1.238 + d = true;
1.239 + }
1.240 + }
1.241 +
1.242 + static int id(Node v) { return v.id; }
1.243 + int redId(Node v) const {
1.244 + LEMON_DEBUG(nodes[v.id].red, "Node has to be red");
1.245 + return nodes[v.id].partition_index;
1.246 + }
1.247 + int blueId(Node v) const {
1.248 + LEMON_DEBUG(!nodes[v.id].red, "Node has to be blue");
1.249 + return nodes[v.id].partition_index;
1.250 + }
1.251 + static int id(Arc e) { return e.id; }
1.252 + static int id(Edge e) { return e.id; }
1.253 +
1.254 + static Node nodeFromId(int id) { return Node(id);}
1.255 + static Arc arcFromId(int id) { return Arc(id);}
1.256 + static Edge edgeFromId(int id) { return Edge(id);}
1.257 +
1.258 + bool valid(Node n) const {
1.259 + return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
1.260 + nodes[n.id].prev != -2;
1.261 + }
1.262 +
1.263 + bool valid(Arc a) const {
1.264 + return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
1.265 + arcs[a.id].prev_out != -2;
1.266 + }
1.267 +
1.268 + bool valid(Edge e) const {
1.269 + return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
1.270 + arcs[2 * e.id].prev_out != -2;
1.271 + }
1.272 +
1.273 + Node addRedNode() {
1.274 + int n;
1.275 +
1.276 + if(first_free_red==-1) {
1.277 + n = nodes.size();
1.278 + nodes.push_back(NodeT());
1.279 + nodes[n].partition_index = ++max_red;
1.280 + nodes[n].red = true;
1.281 + } else {
1.282 + n = first_free_red;
1.283 + first_free_red = nodes[n].next;
1.284 + }
1.285 +
1.286 + nodes[n].next = first_node;
1.287 + if (first_node != -1) nodes[first_node].prev = n;
1.288 + first_node = n;
1.289 + nodes[n].prev = -1;
1.290 +
1.291 + nodes[n].partition_next = first_red;
1.292 + if (first_red != -1) nodes[first_red].partition_prev = n;
1.293 + first_red = n;
1.294 + nodes[n].partition_prev = -1;
1.295 +
1.296 + nodes[n].first_out = -1;
1.297 +
1.298 + return Node(n);
1.299 + }
1.300 +
1.301 + Node addBlueNode() {
1.302 + int n;
1.303 +
1.304 + if(first_free_blue==-1) {
1.305 + n = nodes.size();
1.306 + nodes.push_back(NodeT());
1.307 + nodes[n].partition_index = ++max_blue;
1.308 + nodes[n].red = false;
1.309 + } else {
1.310 + n = first_free_blue;
1.311 + first_free_blue = nodes[n].next;
1.312 + }
1.313 +
1.314 + nodes[n].next = first_node;
1.315 + if (first_node != -1) nodes[first_node].prev = n;
1.316 + first_node = n;
1.317 + nodes[n].prev = -1;
1.318 +
1.319 + nodes[n].partition_next = first_blue;
1.320 + if (first_blue != -1) nodes[first_blue].partition_prev = n;
1.321 + first_blue = n;
1.322 + nodes[n].partition_prev = -1;
1.323 +
1.324 + nodes[n].first_out = -1;
1.325 +
1.326 + return Node(n);
1.327 + }
1.328 +
1.329 + Edge addEdge(Node u, Node v) {
1.330 + int n;
1.331 +
1.332 + if (first_free_arc == -1) {
1.333 + n = arcs.size();
1.334 + arcs.push_back(ArcT());
1.335 + arcs.push_back(ArcT());
1.336 + } else {
1.337 + n = first_free_arc;
1.338 + first_free_arc = arcs[n].next_out;
1.339 + }
1.340 +
1.341 + arcs[n].target = u.id;
1.342 + arcs[n | 1].target = v.id;
1.343 +
1.344 + arcs[n].next_out = nodes[v.id].first_out;
1.345 + if (nodes[v.id].first_out != -1) {
1.346 + arcs[nodes[v.id].first_out].prev_out = n;
1.347 + }
1.348 + arcs[n].prev_out = -1;
1.349 + nodes[v.id].first_out = n;
1.350 +
1.351 + arcs[n | 1].next_out = nodes[u.id].first_out;
1.352 + if (nodes[u.id].first_out != -1) {
1.353 + arcs[nodes[u.id].first_out].prev_out = (n | 1);
1.354 + }
1.355 + arcs[n | 1].prev_out = -1;
1.356 + nodes[u.id].first_out = (n | 1);
1.357 +
1.358 + return Edge(n / 2);
1.359 + }
1.360 +
1.361 + void erase(const Node& node) {
1.362 + int n = node.id;
1.363 +
1.364 + if(nodes[n].next != -1) {
1.365 + nodes[nodes[n].next].prev = nodes[n].prev;
1.366 + }
1.367 +
1.368 + if(nodes[n].prev != -1) {
1.369 + nodes[nodes[n].prev].next = nodes[n].next;
1.370 + } else {
1.371 + first_node = nodes[n].next;
1.372 + }
1.373 +
1.374 + if (nodes[n].partition_next != -1) {
1.375 + nodes[nodes[n].partition_next].partition_prev = nodes[n].partition_prev;
1.376 + }
1.377 +
1.378 + if (nodes[n].partition_prev != -1) {
1.379 + nodes[nodes[n].partition_prev].partition_next = nodes[n].partition_next;
1.380 + } else {
1.381 + if (nodes[n].red) {
1.382 + first_red = nodes[n].partition_next;
1.383 + } else {
1.384 + first_blue = nodes[n].partition_next;
1.385 + }
1.386 + }
1.387 +
1.388 + if (nodes[n].red) {
1.389 + nodes[n].next = first_free_red;
1.390 + first_free_red = n;
1.391 + } else {
1.392 + nodes[n].next = first_free_blue;
1.393 + first_free_blue = n;
1.394 + }
1.395 + nodes[n].prev = -2;
1.396 + }
1.397 +
1.398 + void erase(const Edge& edge) {
1.399 + int n = edge.id * 2;
1.400 +
1.401 + if (arcs[n].next_out != -1) {
1.402 + arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1.403 + }
1.404 +
1.405 + if (arcs[n].prev_out != -1) {
1.406 + arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1.407 + } else {
1.408 + nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
1.409 + }
1.410 +
1.411 + if (arcs[n | 1].next_out != -1) {
1.412 + arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
1.413 + }
1.414 +
1.415 + if (arcs[n | 1].prev_out != -1) {
1.416 + arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
1.417 + } else {
1.418 + nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
1.419 + }
1.420 +
1.421 + arcs[n].next_out = first_free_arc;
1.422 + first_free_arc = n;
1.423 + arcs[n].prev_out = -2;
1.424 + arcs[n | 1].prev_out = -2;
1.425 +
1.426 + }
1.427 +
1.428 + void clear() {
1.429 + arcs.clear();
1.430 + nodes.clear();
1.431 + first_node = first_free_arc = first_red = first_blue =
1.432 + max_red = max_blue = first_free_red = first_free_blue = -1;
1.433 + }
1.434 +
1.435 + protected:
1.436 +
1.437 + void changeRed(Edge e, Node n) {
1.438 + LEMON_DEBUG(nodes[n].red, "Node has to be red");
1.439 + if(arcs[(2 * e.id) | 1].next_out != -1) {
1.440 + arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
1.441 + arcs[(2 * e.id) | 1].prev_out;
1.442 + }
1.443 + if(arcs[(2 * e.id) | 1].prev_out != -1) {
1.444 + arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
1.445 + arcs[(2 * e.id) | 1].next_out;
1.446 + } else {
1.447 + nodes[arcs[2 * e.id].target].first_out =
1.448 + arcs[(2 * e.id) | 1].next_out;
1.449 + }
1.450 +
1.451 + if (nodes[n.id].first_out != -1) {
1.452 + arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
1.453 + }
1.454 + arcs[2 * e.id].target = n.id;
1.455 + arcs[(2 * e.id) | 1].prev_out = -1;
1.456 + arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
1.457 + nodes[n.id].first_out = ((2 * e.id) | 1);
1.458 + }
1.459 +
1.460 + void changeBlue(Edge e, Node n) {
1.461 + LEMON_DEBUG(nodes[n].red, "Node has to be blue");
1.462 + if(arcs[2 * e.id].next_out != -1) {
1.463 + arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
1.464 + }
1.465 + if(arcs[2 * e.id].prev_out != -1) {
1.466 + arcs[arcs[2 * e.id].prev_out].next_out =
1.467 + arcs[2 * e.id].next_out;
1.468 + } else {
1.469 + nodes[arcs[(2 * e.id) | 1].target].first_out =
1.470 + arcs[2 * e.id].next_out;
1.471 + }
1.472 +
1.473 + if (nodes[n.id].first_out != -1) {
1.474 + arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
1.475 + }
1.476 + arcs[(2 * e.id) | 1].target = n.id;
1.477 + arcs[2 * e.id].prev_out = -1;
1.478 + arcs[2 * e.id].next_out = nodes[n.id].first_out;
1.479 + nodes[n.id].first_out = 2 * e.id;
1.480 + }
1.481 +
1.482 + };
1.483 +
1.484 + typedef BpGraphExtender<ListBpGraphBase> ExtendedListBpGraphBase;
1.485 +
1.486 +
1.487 + /// \addtogroup graphs
1.488 + /// @{
1.489 +
1.490 + ///A general undirected graph structure.
1.491 +
1.492 + ///\ref ListBpGraph is a versatile and fast undirected graph
1.493 + ///implementation based on linked lists that are stored in
1.494 + ///\c std::vector structures.
1.495 + ///
1.496 + ///This type fully conforms to the \ref concepts::BpGraph "BpGraph concept"
1.497 + ///and it also provides several useful additional functionalities.
1.498 + ///Most of its member functions and nested classes are documented
1.499 + ///only in the concept class.
1.500 + ///
1.501 + ///This class provides only linear time counting for nodes, edges and arcs.
1.502 + ///
1.503 + ///\sa concepts::BpGraph
1.504 + ///\sa ListDigraph
1.505 + class ListBpGraph : public ExtendedListBpGraphBase {
1.506 + typedef ExtendedListBpGraphBase Parent;
1.507 +
1.508 + private:
1.509 + /// BpGraphs are \e not copy constructible. Use BpGraphCopy instead.
1.510 + ListBpGraph(const ListBpGraph &) :ExtendedListBpGraphBase() {};
1.511 + /// \brief Assignment of a graph to another one is \e not allowed.
1.512 + /// Use BpGraphCopy instead.
1.513 + void operator=(const ListBpGraph &) {}
1.514 + public:
1.515 + /// Constructor
1.516 +
1.517 + /// Constructor.
1.518 + ///
1.519 + ListBpGraph() {}
1.520 +
1.521 + typedef Parent::OutArcIt IncEdgeIt;
1.522 +
1.523 + /// \brief Add a new red node to the graph.
1.524 + ///
1.525 + /// This function adds a red new node to the graph.
1.526 + /// \return The new node.
1.527 + Node addRedNode() { return Parent::addRedNode(); }
1.528 +
1.529 + /// \brief Add a new blue node to the graph.
1.530 + ///
1.531 + /// This function adds a blue new node to the graph.
1.532 + /// \return The new node.
1.533 + Node addBlueNode() { return Parent::addBlueNode(); }
1.534 +
1.535 + /// \brief Add a new edge to the graph.
1.536 + ///
1.537 + /// This function adds a new edge to the graph between nodes
1.538 + /// \c u and \c v with inherent orientation from node \c u to
1.539 + /// node \c v.
1.540 + /// \return The new edge.
1.541 + Edge addEdge(Node u, Node v) {
1.542 + return Parent::addEdge(u, v);
1.543 + }
1.544 +
1.545 + ///\brief Erase a node from the graph.
1.546 + ///
1.547 + /// This function erases the given node along with its incident arcs
1.548 + /// from the graph.
1.549 + ///
1.550 + /// \note All iterators referencing the removed node or the incident
1.551 + /// edges are invalidated, of course.
1.552 + void erase(Node n) { Parent::erase(n); }
1.553 +
1.554 + ///\brief Erase an edge from the graph.
1.555 + ///
1.556 + /// This function erases the given edge from the graph.
1.557 + ///
1.558 + /// \note All iterators referencing the removed edge are invalidated,
1.559 + /// of course.
1.560 + void erase(Edge e) { Parent::erase(e); }
1.561 + /// Node validity check
1.562 +
1.563 + /// This function gives back \c true if the given node is valid,
1.564 + /// i.e. it is a real node of the graph.
1.565 + ///
1.566 + /// \warning A removed node could become valid again if new nodes are
1.567 + /// added to the graph.
1.568 + bool valid(Node n) const { return Parent::valid(n); }
1.569 + /// Edge validity check
1.570 +
1.571 + /// This function gives back \c true if the given edge is valid,
1.572 + /// i.e. it is a real edge of the graph.
1.573 + ///
1.574 + /// \warning A removed edge could become valid again if new edges are
1.575 + /// added to the graph.
1.576 + bool valid(Edge e) const { return Parent::valid(e); }
1.577 + /// Arc validity check
1.578 +
1.579 + /// This function gives back \c true if the given arc is valid,
1.580 + /// i.e. it is a real arc of the graph.
1.581 + ///
1.582 + /// \warning A removed arc could become valid again if new edges are
1.583 + /// added to the graph.
1.584 + bool valid(Arc a) const { return Parent::valid(a); }
1.585 +
1.586 + /// \brief Change the red node of an edge.
1.587 + ///
1.588 + /// This function changes the red node of the given edge \c e to \c n.
1.589 + ///
1.590 + ///\note \c EdgeIt and \c ArcIt iterators referencing the
1.591 + ///changed edge are invalidated and all other iterators whose
1.592 + ///base node is the changed node are also invalidated.
1.593 + ///
1.594 + ///\warning This functionality cannot be used together with the
1.595 + ///Snapshot feature.
1.596 + void changeRed(Edge e, Node n) {
1.597 + Parent::changeRed(e,n);
1.598 + }
1.599 + /// \brief Change the blue node of an edge.
1.600 + ///
1.601 + /// This function changes the blue node of the given edge \c e to \c n.
1.602 + ///
1.603 + ///\note \c EdgeIt iterators referencing the changed edge remain
1.604 + ///valid, but \c ArcIt iterators referencing the changed edge and
1.605 + ///all other iterators whose base node is the changed node are also
1.606 + ///invalidated.
1.607 + ///
1.608 + ///\warning This functionality cannot be used together with the
1.609 + ///Snapshot feature.
1.610 + void changeBlue(Edge e, Node n) {
1.611 + Parent::changeBlue(e,n);
1.612 + }
1.613 +
1.614 + ///Clear the graph.
1.615 +
1.616 + ///This function erases all nodes and arcs from the graph.
1.617 + ///
1.618 + ///\note All iterators of the graph are invalidated, of course.
1.619 + void clear() {
1.620 + Parent::clear();
1.621 + }
1.622 +
1.623 + /// Reserve memory for nodes.
1.624 +
1.625 + /// Using this function, it is possible to avoid superfluous memory
1.626 + /// allocation: if you know that the graph you want to build will
1.627 + /// be large (e.g. it will contain millions of nodes and/or edges),
1.628 + /// then it is worth reserving space for this amount before starting
1.629 + /// to build the graph.
1.630 + /// \sa reserveEdge()
1.631 + void reserveNode(int n) { nodes.reserve(n); };
1.632 +
1.633 + /// Reserve memory for edges.
1.634 +
1.635 + /// Using this function, it is possible to avoid superfluous memory
1.636 + /// allocation: if you know that the graph you want to build will
1.637 + /// be large (e.g. it will contain millions of nodes and/or edges),
1.638 + /// then it is worth reserving space for this amount before starting
1.639 + /// to build the graph.
1.640 + /// \sa reserveNode()
1.641 + void reserveEdge(int m) { arcs.reserve(2 * m); };
1.642 +
1.643 + /// \brief Class to make a snapshot of the graph and restore
1.644 + /// it later.
1.645 + ///
1.646 + /// Class to make a snapshot of the graph and restore it later.
1.647 + ///
1.648 + /// The newly added nodes and edges can be removed
1.649 + /// using the restore() function.
1.650 + ///
1.651 + /// \note After a state is restored, you cannot restore a later state,
1.652 + /// i.e. you cannot add the removed nodes and edges again using
1.653 + /// another Snapshot instance.
1.654 + ///
1.655 + /// \warning Node and edge deletions and other modifications
1.656 + /// (e.g. changing the end-nodes of edges or contracting nodes)
1.657 + /// cannot be restored. These events invalidate the snapshot.
1.658 + /// However, the edges and nodes that were added to the graph after
1.659 + /// making the current snapshot can be removed without invalidating it.
1.660 + class Snapshot {
1.661 + protected:
1.662 +
1.663 + typedef Parent::NodeNotifier NodeNotifier;
1.664 +
1.665 + class NodeObserverProxy : public NodeNotifier::ObserverBase {
1.666 + public:
1.667 +
1.668 + NodeObserverProxy(Snapshot& _snapshot)
1.669 + : snapshot(_snapshot) {}
1.670 +
1.671 + using NodeNotifier::ObserverBase::attach;
1.672 + using NodeNotifier::ObserverBase::detach;
1.673 + using NodeNotifier::ObserverBase::attached;
1.674 +
1.675 + protected:
1.676 +
1.677 + virtual void add(const Node& node) {
1.678 + snapshot.addNode(node);
1.679 + }
1.680 + virtual void add(const std::vector<Node>& nodes) {
1.681 + for (int i = nodes.size() - 1; i >= 0; ++i) {
1.682 + snapshot.addNode(nodes[i]);
1.683 + }
1.684 + }
1.685 + virtual void erase(const Node& node) {
1.686 + snapshot.eraseNode(node);
1.687 + }
1.688 + virtual void erase(const std::vector<Node>& nodes) {
1.689 + for (int i = 0; i < int(nodes.size()); ++i) {
1.690 + snapshot.eraseNode(nodes[i]);
1.691 + }
1.692 + }
1.693 + virtual void build() {
1.694 + Node node;
1.695 + std::vector<Node> nodes;
1.696 + for (notifier()->first(node); node != INVALID;
1.697 + notifier()->next(node)) {
1.698 + nodes.push_back(node);
1.699 + }
1.700 + for (int i = nodes.size() - 1; i >= 0; --i) {
1.701 + snapshot.addNode(nodes[i]);
1.702 + }
1.703 + }
1.704 + virtual void clear() {
1.705 + Node node;
1.706 + for (notifier()->first(node); node != INVALID;
1.707 + notifier()->next(node)) {
1.708 + snapshot.eraseNode(node);
1.709 + }
1.710 + }
1.711 +
1.712 + Snapshot& snapshot;
1.713 + };
1.714 +
1.715 + class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
1.716 + public:
1.717 +
1.718 + EdgeObserverProxy(Snapshot& _snapshot)
1.719 + : snapshot(_snapshot) {}
1.720 +
1.721 + using EdgeNotifier::ObserverBase::attach;
1.722 + using EdgeNotifier::ObserverBase::detach;
1.723 + using EdgeNotifier::ObserverBase::attached;
1.724 +
1.725 + protected:
1.726 +
1.727 + virtual void add(const Edge& edge) {
1.728 + snapshot.addEdge(edge);
1.729 + }
1.730 + virtual void add(const std::vector<Edge>& edges) {
1.731 + for (int i = edges.size() - 1; i >= 0; ++i) {
1.732 + snapshot.addEdge(edges[i]);
1.733 + }
1.734 + }
1.735 + virtual void erase(const Edge& edge) {
1.736 + snapshot.eraseEdge(edge);
1.737 + }
1.738 + virtual void erase(const std::vector<Edge>& edges) {
1.739 + for (int i = 0; i < int(edges.size()); ++i) {
1.740 + snapshot.eraseEdge(edges[i]);
1.741 + }
1.742 + }
1.743 + virtual void build() {
1.744 + Edge edge;
1.745 + std::vector<Edge> edges;
1.746 + for (notifier()->first(edge); edge != INVALID;
1.747 + notifier()->next(edge)) {
1.748 + edges.push_back(edge);
1.749 + }
1.750 + for (int i = edges.size() - 1; i >= 0; --i) {
1.751 + snapshot.addEdge(edges[i]);
1.752 + }
1.753 + }
1.754 + virtual void clear() {
1.755 + Edge edge;
1.756 + for (notifier()->first(edge); edge != INVALID;
1.757 + notifier()->next(edge)) {
1.758 + snapshot.eraseEdge(edge);
1.759 + }
1.760 + }
1.761 +
1.762 + Snapshot& snapshot;
1.763 + };
1.764 +
1.765 + ListBpGraph *graph;
1.766 +
1.767 + NodeObserverProxy node_observer_proxy;
1.768 + EdgeObserverProxy edge_observer_proxy;
1.769 +
1.770 + std::list<Node> added_nodes;
1.771 + std::list<Edge> added_edges;
1.772 +
1.773 +
1.774 + void addNode(const Node& node) {
1.775 + added_nodes.push_front(node);
1.776 + }
1.777 + void eraseNode(const Node& node) {
1.778 + std::list<Node>::iterator it =
1.779 + std::find(added_nodes.begin(), added_nodes.end(), node);
1.780 + if (it == added_nodes.end()) {
1.781 + clear();
1.782 + edge_observer_proxy.detach();
1.783 + throw NodeNotifier::ImmediateDetach();
1.784 + } else {
1.785 + added_nodes.erase(it);
1.786 + }
1.787 + }
1.788 +
1.789 + void addEdge(const Edge& edge) {
1.790 + added_edges.push_front(edge);
1.791 + }
1.792 + void eraseEdge(const Edge& edge) {
1.793 + std::list<Edge>::iterator it =
1.794 + std::find(added_edges.begin(), added_edges.end(), edge);
1.795 + if (it == added_edges.end()) {
1.796 + clear();
1.797 + node_observer_proxy.detach();
1.798 + throw EdgeNotifier::ImmediateDetach();
1.799 + } else {
1.800 + added_edges.erase(it);
1.801 + }
1.802 + }
1.803 +
1.804 + void attach(ListBpGraph &_graph) {
1.805 + graph = &_graph;
1.806 + node_observer_proxy.attach(graph->notifier(Node()));
1.807 + edge_observer_proxy.attach(graph->notifier(Edge()));
1.808 + }
1.809 +
1.810 + void detach() {
1.811 + node_observer_proxy.detach();
1.812 + edge_observer_proxy.detach();
1.813 + }
1.814 +
1.815 + bool attached() const {
1.816 + return node_observer_proxy.attached();
1.817 + }
1.818 +
1.819 + void clear() {
1.820 + added_nodes.clear();
1.821 + added_edges.clear();
1.822 + }
1.823 +
1.824 + public:
1.825 +
1.826 + /// \brief Default constructor.
1.827 + ///
1.828 + /// Default constructor.
1.829 + /// You have to call save() to actually make a snapshot.
1.830 + Snapshot()
1.831 + : graph(0), node_observer_proxy(*this),
1.832 + edge_observer_proxy(*this) {}
1.833 +
1.834 + /// \brief Constructor that immediately makes a snapshot.
1.835 + ///
1.836 + /// This constructor immediately makes a snapshot of the given graph.
1.837 + Snapshot(ListBpGraph &gr)
1.838 + : node_observer_proxy(*this),
1.839 + edge_observer_proxy(*this) {
1.840 + attach(gr);
1.841 + }
1.842 +
1.843 + /// \brief Make a snapshot.
1.844 + ///
1.845 + /// This function makes a snapshot of the given graph.
1.846 + /// It can be called more than once. In case of a repeated
1.847 + /// call, the previous snapshot gets lost.
1.848 + void save(ListBpGraph &gr) {
1.849 + if (attached()) {
1.850 + detach();
1.851 + clear();
1.852 + }
1.853 + attach(gr);
1.854 + }
1.855 +
1.856 + /// \brief Undo the changes until the last snapshot.
1.857 + ///
1.858 + /// This function undos the changes until the last snapshot
1.859 + /// created by save() or Snapshot(ListBpGraph&).
1.860 + ///
1.861 + /// \warning This method invalidates the snapshot, i.e. repeated
1.862 + /// restoring is not supported unless you call save() again.
1.863 + void restore() {
1.864 + detach();
1.865 + for(std::list<Edge>::iterator it = added_edges.begin();
1.866 + it != added_edges.end(); ++it) {
1.867 + graph->erase(*it);
1.868 + }
1.869 + for(std::list<Node>::iterator it = added_nodes.begin();
1.870 + it != added_nodes.end(); ++it) {
1.871 + graph->erase(*it);
1.872 + }
1.873 + clear();
1.874 + }
1.875 +
1.876 + /// \brief Returns \c true if the snapshot is valid.
1.877 + ///
1.878 + /// This function returns \c true if the snapshot is valid.
1.879 + bool valid() const {
1.880 + return attached();
1.881 + }
1.882 + };
1.883 + };
1.884 +
1.885 + /// @}
1.886 } //namespace lemon
1.887
1.888
2.1 --- a/lemon/smart_graph.h Sun Nov 14 22:48:32 2010 +0100
2.2 +++ b/lemon/smart_graph.h Mon Nov 15 09:46:08 2010 +0100
2.3 @@ -1016,7 +1016,7 @@
2.4 return nodes[v._id].partition_index;
2.5 }
2.6 int blueId(Node v) const {
2.7 - LEMON_DEBUG(nodes[v._id].red, "Node has to be blue");
2.8 + LEMON_DEBUG(!nodes[v._id].red, "Node has to be blue");
2.9 return nodes[v._id].partition_index;
2.10 }
2.11 static int id(Arc e) { return e._id; }
3.1 --- a/test/bpgraph_test.cc Sun Nov 14 22:48:32 2010 +0100
3.2 +++ b/test/bpgraph_test.cc Mon Nov 15 09:46:08 2010 +0100
3.3 @@ -17,7 +17,7 @@
3.4 */
3.5
3.6 #include <lemon/concepts/bpgraph.h>
3.7 -//#include <lemon/list_graph.h>
3.8 +#include <lemon/list_graph.h>
3.9 #include <lemon/smart_graph.h>
3.10 #include <lemon/full_graph.h>
3.11
3.12 @@ -107,11 +107,108 @@
3.13 checkGraphEdgeMap(G);
3.14 }
3.15
3.16 -template <class Graph>
3.17 +template <class BpGraph>
3.18 +void checkBpGraphErase() {
3.19 + TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
3.20 +
3.21 + BpGraph G;
3.22 + Node
3.23 + n1 = G.addRedNode(), n2 = G.addBlueNode(),
3.24 + n3 = G.addBlueNode(), n4 = G.addRedNode();
3.25 + Edge
3.26 + e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
3.27 + e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);
3.28 +
3.29 + // Check edge deletion
3.30 + G.erase(e2);
3.31 +
3.32 + checkGraphNodeList(G, 4);
3.33 + checkGraphRedNodeList(G, 2);
3.34 + checkGraphBlueNodeList(G, 2);
3.35 + checkGraphEdgeList(G, 3);
3.36 + checkGraphArcList(G, 6);
3.37 +
3.38 + checkGraphIncEdgeArcLists(G, n1, 1);
3.39 + checkGraphIncEdgeArcLists(G, n2, 2);
3.40 + checkGraphIncEdgeArcLists(G, n3, 1);
3.41 + checkGraphIncEdgeArcLists(G, n4, 2);
3.42 +
3.43 + checkGraphConEdgeList(G, 3);
3.44 + checkGraphConArcList(G, 6);
3.45 +
3.46 + // Check node deletion
3.47 + G.erase(n3);
3.48 +
3.49 + checkGraphNodeList(G, 3);
3.50 + checkGraphRedNodeList(G, 2);
3.51 + checkGraphBlueNodeList(G, 1);
3.52 + checkGraphEdgeList(G, 2);
3.53 + checkGraphArcList(G, 4);
3.54 +
3.55 + checkGraphIncEdgeArcLists(G, n1, 1);
3.56 + checkGraphIncEdgeArcLists(G, n2, 2);
3.57 + checkGraphIncEdgeArcLists(G, n4, 1);
3.58 +
3.59 + checkGraphConEdgeList(G, 2);
3.60 + checkGraphConArcList(G, 4);
3.61 +
3.62 +}
3.63 +
3.64 +template <class BpGraph>
3.65 +void checkBpGraphAlter() {
3.66 + TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
3.67 +
3.68 + BpGraph G;
3.69 + Node
3.70 + n1 = G.addRedNode(), n2 = G.addBlueNode(),
3.71 + n3 = G.addBlueNode(), n4 = G.addRedNode();
3.72 + Edge
3.73 + e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
3.74 + e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);
3.75 +
3.76 + G.changeRed(e2, n4);
3.77 + check(G.redNode(e2) == n4, "Wrong red node");
3.78 + check(G.blueNode(e2) == n3, "Wrong blue node");
3.79 +
3.80 + checkGraphNodeList(G, 4);
3.81 + checkGraphRedNodeList(G, 2);
3.82 + checkGraphBlueNodeList(G, 2);
3.83 + checkGraphEdgeList(G, 4);
3.84 + checkGraphArcList(G, 8);
3.85 +
3.86 + checkGraphIncEdgeArcLists(G, n1, 1);
3.87 + checkGraphIncEdgeArcLists(G, n2, 2);
3.88 + checkGraphIncEdgeArcLists(G, n3, 2);
3.89 + checkGraphIncEdgeArcLists(G, n4, 3);
3.90 +
3.91 + checkGraphConEdgeList(G, 4);
3.92 + checkGraphConArcList(G, 8);
3.93 +
3.94 + G.changeBlue(e2, n2);
3.95 + check(G.redNode(e2) == n4, "Wrong red node");
3.96 + check(G.blueNode(e2) == n2, "Wrong blue node");
3.97 +
3.98 + checkGraphNodeList(G, 4);
3.99 + checkGraphRedNodeList(G, 2);
3.100 + checkGraphBlueNodeList(G, 2);
3.101 + checkGraphEdgeList(G, 4);
3.102 + checkGraphArcList(G, 8);
3.103 +
3.104 + checkGraphIncEdgeArcLists(G, n1, 1);
3.105 + checkGraphIncEdgeArcLists(G, n2, 3);
3.106 + checkGraphIncEdgeArcLists(G, n3, 1);
3.107 + checkGraphIncEdgeArcLists(G, n4, 3);
3.108 +
3.109 + checkGraphConEdgeList(G, 4);
3.110 + checkGraphConArcList(G, 8);
3.111 +}
3.112 +
3.113 +
3.114 +template <class BpGraph>
3.115 void checkBpGraphSnapshot() {
3.116 - TEMPLATE_BPGRAPH_TYPEDEFS(Graph);
3.117 + TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
3.118
3.119 - Graph G;
3.120 + BpGraph G;
3.121 Node
3.122 n1 = G.addRedNode(),
3.123 n2 = G.addBlueNode(),
3.124 @@ -126,7 +223,7 @@
3.125 checkGraphEdgeList(G, 2);
3.126 checkGraphArcList(G, 4);
3.127
3.128 - typename Graph::Snapshot snapshot(G);
3.129 + typename BpGraph::Snapshot snapshot(G);
3.130
3.131 Node n4 = G.addRedNode();
3.132 G.addEdge(n4, n2);
3.133 @@ -190,10 +287,10 @@
3.134 checkGraphArcList(G, 4);
3.135 }
3.136
3.137 -template <typename Graph>
3.138 +template <typename BpGraph>
3.139 void checkBpGraphValidity() {
3.140 - TEMPLATE_GRAPH_TYPEDEFS(Graph);
3.141 - Graph g;
3.142 + TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
3.143 + BpGraph g;
3.144
3.145 Node
3.146 n1 = g.addRedNode(),
3.147 @@ -325,6 +422,13 @@
3.148 }
3.149
3.150 void checkGraphs() {
3.151 + { // Checking ListGraph
3.152 + checkBpGraphBuild<ListBpGraph>();
3.153 + checkBpGraphErase<ListBpGraph>();
3.154 + checkBpGraphAlter<ListBpGraph>();
3.155 + checkBpGraphSnapshot<ListBpGraph>();
3.156 + checkBpGraphValidity<ListBpGraph>();
3.157 + }
3.158 { // Checking SmartGraph
3.159 checkBpGraphBuild<SmartBpGraph>();
3.160 checkBpGraphSnapshot<SmartBpGraph>();