00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_SMART_GRAPH_H
00020 #define LEMON_SMART_GRAPH_H
00021
00025
00026 #include <vector>
00027
00028 #include <lemon/invalid.h>
00029
00030 #include <lemon/bits/clearable_graph_extender.h>
00031 #include <lemon/bits/extendable_graph_extender.h>
00032 #include <lemon/bits/iterable_graph_extender.h>
00033 #include <lemon/bits/alteration_notifier.h>
00034 #include <lemon/bits/default_map.h>
00035 #include <lemon/bits/graph_extender.h>
00036
00037 #include <lemon/utility.h>
00038 #include <lemon/error.h>
00039
00040 namespace lemon {
00041
00042 class SmartGraph;
00044
00047 class SmartGraphBase {
00048
00049 friend class SmatGraph;
00050
00051 protected:
00052 struct NodeT
00053 {
00054 int first_in,first_out;
00055 NodeT() : first_in(-1), first_out(-1) {}
00056 };
00057 struct EdgeT
00058 {
00059 int target, source, next_in, next_out;
00060
00061 EdgeT() : next_in(-1), next_out(-1) {}
00062 };
00063
00064 std::vector<NodeT> nodes;
00065
00066 std::vector<EdgeT> edges;
00067
00068
00069 public:
00070
00071 typedef SmartGraphBase Graph;
00072
00073 class Node;
00074 class Edge;
00075
00076
00077 public:
00078
00079 SmartGraphBase() : nodes(), edges() { }
00080 SmartGraphBase(const SmartGraphBase &_g)
00081 : nodes(_g.nodes), edges(_g.edges) { }
00082
00083 typedef True NodeNumTag;
00084 typedef True EdgeNumTag;
00085
00087 int nodeNum() const { return nodes.size(); }
00089 int edgeNum() const { return edges.size(); }
00090
00092
00095 int maxNodeId() const { return nodes.size()-1; }
00097
00100 int maxEdgeId() const { return edges.size()-1; }
00101
00102 Node source(Edge e) const { return edges[e.n].source; }
00103 Node target(Edge e) const { return edges[e.n].target; }
00104
00106
00113 static int id(Node v) { return v.n; }
00115
00122 static int id(Edge e) { return e.n; }
00123
00124 static Node nodeFromId(int id) { return Node(id);}
00125
00126 static Edge edgeFromId(int id) { return Edge(id);}
00127
00128 Node addNode() {
00129 Node n; n.n=nodes.size();
00130 nodes.push_back(NodeT());
00131 return n;
00132 }
00133
00134 Edge addEdge(Node u, Node v) {
00135 Edge e; e.n=edges.size(); edges.push_back(EdgeT());
00136 edges[e.n].source=u.n; edges[e.n].target=v.n;
00137 edges[e.n].next_out=nodes[u.n].first_out;
00138 edges[e.n].next_in=nodes[v.n].first_in;
00139 nodes[u.n].first_out=nodes[v.n].first_in=e.n;
00140
00141 return e;
00142 }
00143
00144 void clear() {
00145 edges.clear();
00146 nodes.clear();
00147 }
00148
00149
00150 class Node {
00151 friend class SmartGraphBase;
00152 friend class SmartGraph;
00153
00154 protected:
00155 int n;
00156 Node(int nn) {n=nn;}
00157 public:
00158 Node() {}
00159 Node (Invalid) { n=-1; }
00160 bool operator==(const Node i) const {return n==i.n;}
00161 bool operator!=(const Node i) const {return n!=i.n;}
00162 bool operator<(const Node i) const {return n<i.n;}
00163 };
00164
00165
00166 class Edge {
00167 friend class SmartGraphBase;
00168 friend class SmartGraph;
00169
00170 protected:
00171 int n;
00172 Edge(int nn) {n=nn;}
00173 public:
00174 Edge() { }
00175 Edge (Invalid) { n=-1; }
00176 bool operator==(const Edge i) const {return n==i.n;}
00177 bool operator!=(const Edge i) const {return n!=i.n;}
00178 bool operator<(const Edge i) const {return n<i.n;}
00179 };
00180
00181 void first(Node& node) const {
00182 node.n = nodes.size() - 1;
00183 }
00184
00185 static void next(Node& node) {
00186 --node.n;
00187 }
00188
00189 void first(Edge& edge) const {
00190 edge.n = edges.size() - 1;
00191 }
00192
00193 static void next(Edge& edge) {
00194 --edge.n;
00195 }
00196
00197 void firstOut(Edge& edge, const Node& node) const {
00198 edge.n = nodes[node.n].first_out;
00199 }
00200
00201 void nextOut(Edge& edge) const {
00202 edge.n = edges[edge.n].next_out;
00203 }
00204
00205 void firstIn(Edge& edge, const Node& node) const {
00206 edge.n = nodes[node.n].first_in;
00207 }
00208
00209 void nextIn(Edge& edge) const {
00210 edge.n = edges[edge.n].next_in;
00211 }
00212
00213 Node _split(Node n, bool connect = true)
00214 {
00215 Node b = addNode();
00216 nodes[b.n].first_out=nodes[n.n].first_out;
00217 nodes[n.n].first_out=-1;
00218 for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;
00219 if(connect) addEdge(n,b);
00220 return b;
00221 }
00222
00223 };
00224
00225 typedef ClearableGraphExtender<
00226 ExtendableGraphExtender<
00227 MappableGraphExtender<
00228 IterableGraphExtender<
00229 AlterableGraphExtender<
00230 GraphExtender<SmartGraphBase> > > > > > ExtendedSmartGraphBase;
00231
00233
00235
00245 class SmartGraph : public ExtendedSmartGraphBase {
00246 public:
00247
00248 class Snapshot;
00249 friend class Snapshot;
00250
00251 protected:
00252 void restoreSnapshot(const Snapshot &s)
00253 {
00254 while(s.edge_num<edges.size()) {
00255 Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
00256 nodes[edges.back().target].first_in=edges.back().next_in;
00257 nodes[edges.back().source].first_out=edges.back().next_out;
00258 edges.pop_back();
00259 }
00260
00261 while(s.node_num<nodes.size()) {
00262 Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
00263 nodes.pop_back();
00264 }
00265 }
00266
00267 public:
00268
00270
00284 Node split(Node n, bool connect = true)
00285 {
00286 Node b = _split(n,connect);
00287 return b;
00288 }
00289
00290
00292
00301 class Snapshot
00302 {
00303 SmartGraph *g;
00304 protected:
00305 friend class SmartGraph;
00306 unsigned int node_num;
00307 unsigned int edge_num;
00308 public:
00310
00314 Snapshot() : g(0) {}
00316
00319 Snapshot(SmartGraph &_g) :g(&_g) {
00320 node_num=g->nodes.size();
00321 edge_num=g->edges.size();
00322 }
00323
00325
00331 void save(SmartGraph &_g)
00332 {
00333 g=&_g;
00334 node_num=g->nodes.size();
00335 edge_num=g->edges.size();
00336 }
00337
00339
00347
00348 void restore()
00349 {
00350 g->restoreSnapshot(*this);
00351 }
00352 };
00353 };
00354
00355
00356
00357
00358 typedef ClearableUGraphExtender<
00359 ExtendableUGraphExtender<
00360 MappableUGraphExtender<
00361 IterableUGraphExtender<
00362 AlterableUGraphExtender<
00363 UGraphExtender<SmartGraphBase> > > > > > ExtendedSmartUGraphBase;
00364
00379 class SmartUGraph : public ExtendedSmartUGraphBase {
00380 };
00381
00382
00383 class SmartBpUGraphBase {
00384 public:
00385
00386 class NodeSetError : public LogicError {
00387 virtual const char* exceptionName() const {
00388 return "lemon::SmartBpUGraph::NodeSetError";
00389 }
00390 };
00391
00392 protected:
00393
00394 struct NodeT {
00395 int first;
00396 NodeT() {}
00397 NodeT(int _first) : first(_first) {}
00398 };
00399
00400 struct EdgeT {
00401 int aNode, next_out;
00402 int bNode, next_in;
00403 };
00404
00405 std::vector<NodeT> aNodes;
00406 std::vector<NodeT> bNodes;
00407
00408 std::vector<EdgeT> edges;
00409
00410 public:
00411
00412 class Node {
00413 friend class SmartBpUGraphBase;
00414 protected:
00415 int id;
00416
00417 Node(int _id) : id(_id) {}
00418 public:
00419 Node() {}
00420 Node(Invalid) { id = -1; }
00421 bool operator==(const Node i) const {return id==i.id;}
00422 bool operator!=(const Node i) const {return id!=i.id;}
00423 bool operator<(const Node i) const {return id<i.id;}
00424 };
00425
00426 class Edge {
00427 friend class SmartBpUGraphBase;
00428 protected:
00429 int id;
00430
00431 Edge(int _id) { id = _id;}
00432 public:
00433 Edge() {}
00434 Edge (Invalid) { id = -1; }
00435 bool operator==(const Edge i) const {return id==i.id;}
00436 bool operator!=(const Edge i) const {return id!=i.id;}
00437 bool operator<(const Edge i) const {return id<i.id;}
00438 };
00439
00440 void firstANode(Node& node) const {
00441 node.id = 2 * aNodes.size() - 2;
00442 if (node.id < 0) node.id = -1;
00443 }
00444 void nextANode(Node& node) const {
00445 node.id -= 2;
00446 if (node.id < 0) node.id = -1;
00447 }
00448
00449 void firstBNode(Node& node) const {
00450 node.id = 2 * bNodes.size() - 1;
00451 }
00452 void nextBNode(Node& node) const {
00453 node.id -= 2;
00454 }
00455
00456 void first(Node& node) const {
00457 if (aNodes.size() > 0) {
00458 node.id = 2 * aNodes.size() - 2;
00459 } else {
00460 node.id = 2 * bNodes.size() - 1;
00461 }
00462 }
00463 void next(Node& node) const {
00464 node.id -= 2;
00465 if (node.id == -2) {
00466 node.id = 2 * bNodes.size() - 1;
00467 }
00468 }
00469
00470 void first(Edge& edge) const {
00471 edge.id = edges.size() - 1;
00472 }
00473 void next(Edge& edge) const {
00474 --edge.id;
00475 }
00476
00477 void firstOut(Edge& edge, const Node& node) const {
00478 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
00479 edge.id = aNodes[node.id >> 1].first;
00480 }
00481 void nextOut(Edge& edge) const {
00482 edge.id = edges[edge.id].next_out;
00483 }
00484
00485 void firstIn(Edge& edge, const Node& node) const {
00486 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
00487 edge.id = bNodes[node.id >> 1].first;
00488 }
00489 void nextIn(Edge& edge) const {
00490 edge.id = edges[edge.id].next_in;
00491 }
00492
00493 static int id(const Node& node) {
00494 return node.id;
00495 }
00496 static Node nodeFromId(int id) {
00497 return Node(id);
00498 }
00499 int maxNodeId() const {
00500 return aNodes.size() > bNodes.size() ?
00501 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
00502 }
00503
00504 static int id(const Edge& edge) {
00505 return edge.id;
00506 }
00507 static Edge edgeFromId(int id) {
00508 return Edge(id);
00509 }
00510 int maxEdgeId() const {
00511 return edges.size();
00512 }
00513
00514 static int aNodeId(const Node& node) {
00515 return node.id >> 1;
00516 }
00517 static Node fromANodeId(int id, Node) {
00518 return Node(id << 1);
00519 }
00520 int maxANodeId() const {
00521 return aNodes.size();
00522 }
00523
00524 static int bNodeId(const Node& node) {
00525 return node.id >> 1;
00526 }
00527 static Node fromBNodeId(int id) {
00528 return Node((id << 1) + 1);
00529 }
00530 int maxBNodeId() const {
00531 return bNodes.size();
00532 }
00533
00534 Node aNode(const Edge& edge) const {
00535 return Node(edges[edge.id].aNode);
00536 }
00537 Node bNode(const Edge& edge) const {
00538 return Node(edges[edge.id].bNode);
00539 }
00540
00541 static bool aNode(const Node& node) {
00542 return (node.id & 1) == 0;
00543 }
00544
00545 static bool bNode(const Node& node) {
00546 return (node.id & 1) == 1;
00547 }
00548
00549 Node addANode() {
00550 NodeT nodeT;
00551 nodeT.first = -1;
00552 aNodes.push_back(nodeT);
00553 return Node(aNodes.size() * 2 - 2);
00554 }
00555
00556 Node addBNode() {
00557 NodeT nodeT;
00558 nodeT.first = -1;
00559 bNodes.push_back(nodeT);
00560 return Node(bNodes.size() * 2 - 1);
00561 }
00562
00563 Edge addEdge(const Node& source, const Node& target) {
00564 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
00565 EdgeT edgeT;
00566 if ((source.id & 1) == 0) {
00567 edgeT.aNode = source.id;
00568 edgeT.bNode = target.id;
00569 } else {
00570 edgeT.aNode = target.id;
00571 edgeT.bNode = source.id;
00572 }
00573 edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
00574 aNodes[edgeT.aNode >> 1].first = edges.size();
00575 edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
00576 bNodes[edgeT.bNode >> 1].first = edges.size();
00577 edges.push_back(edgeT);
00578 return Edge(edges.size() - 1);
00579 }
00580
00581 void clear() {
00582 aNodes.clear();
00583 bNodes.clear();
00584 edges.clear();
00585 }
00586
00587 };
00588
00589
00590 typedef ClearableBpUGraphExtender<
00591 ExtendableBpUGraphExtender<
00592 MappableBpUGraphExtender<
00593 IterableBpUGraphExtender<
00594 AlterableBpUGraphExtender<
00595 BpUGraphExtender <
00596 SmartBpUGraphBase> > > > > >
00597 ExtendedSmartBpUGraphBase;
00598
00610 class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
00611
00612
00614 }
00615
00616
00617 #endif //LEMON_SMART_GRAPH_H