00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_LIST_GRAPH_H
00020 #define LEMON_LIST_GRAPH_H
00021
00025
00026 #include <lemon/bits/erasable_graph_extender.h>
00027 #include <lemon/bits/clearable_graph_extender.h>
00028 #include <lemon/bits/extendable_graph_extender.h>
00029 #include <lemon/bits/iterable_graph_extender.h>
00030 #include <lemon/bits/alteration_notifier.h>
00031 #include <lemon/bits/default_map.h>
00032 #include <lemon/bits/graph_extender.h>
00033
00034 #include <lemon/error.h>
00035
00036 #include <list>
00037
00038 namespace lemon {
00039
00040 class ListGraphBase {
00041
00042 protected:
00043 struct NodeT {
00044 int first_in, first_out;
00045 int prev, next;
00046 };
00047
00048 struct EdgeT {
00049 int target, source;
00050 int prev_in, prev_out;
00051 int next_in, next_out;
00052 };
00053
00054 std::vector<NodeT> nodes;
00055
00056 int first_node;
00057
00058 int first_free_node;
00059
00060 std::vector<EdgeT> edges;
00061
00062 int first_free_edge;
00063
00064 public:
00065
00066 typedef ListGraphBase Graph;
00067
00068 class Node {
00069 friend class ListGraphBase;
00070 protected:
00071
00072 int id;
00073 Node(int pid) { id = pid;}
00074
00075 public:
00076 Node() {}
00077 Node (Invalid) { id = -1; }
00078 bool operator==(const Node& node) const {return id == node.id;}
00079 bool operator!=(const Node& node) const {return id != node.id;}
00080 bool operator<(const Node& node) const {return id < node.id;}
00081 };
00082
00083 class Edge {
00084 friend class ListGraphBase;
00085 protected:
00086
00087 int id;
00088 Edge(int pid) { id = pid;}
00089
00090 public:
00091 Edge() {}
00092 Edge (Invalid) { id = -1; }
00093 bool operator==(const Edge& edge) const {return id == edge.id;}
00094 bool operator!=(const Edge& edge) const {return id != edge.id;}
00095 bool operator<(const Edge& edge) const {return id < edge.id;}
00096 };
00097
00098
00099
00100 ListGraphBase()
00101 : nodes(), first_node(-1),
00102 first_free_node(-1), edges(), first_free_edge(-1) {}
00103
00104
00106
00109 int maxNodeId() const { return nodes.size()-1; }
00110
00112
00115 int maxEdgeId() const { return edges.size()-1; }
00116
00117 Node source(Edge e) const { return edges[e.id].source; }
00118 Node target(Edge e) const { return edges[e.id].target; }
00119
00120
00121 void first(Node& node) const {
00122 node.id = first_node;
00123 }
00124
00125 void next(Node& node) const {
00126 node.id = nodes[node.id].next;
00127 }
00128
00129
00130 void first(Edge& e) const {
00131 int n;
00132 for(n = first_node;
00133 n!=-1 && nodes[n].first_in == -1;
00134 n = nodes[n].next);
00135 e.id = (n == -1) ? -1 : nodes[n].first_in;
00136 }
00137
00138 void next(Edge& edge) const {
00139 if (edges[edge.id].next_in != -1) {
00140 edge.id = edges[edge.id].next_in;
00141 } else {
00142 int n;
00143 for(n = nodes[edges[edge.id].target].next;
00144 n!=-1 && nodes[n].first_in == -1;
00145 n = nodes[n].next);
00146 edge.id = (n == -1) ? -1 : nodes[n].first_in;
00147 }
00148 }
00149
00150 void firstOut(Edge &e, const Node& v) const {
00151 e.id = nodes[v.id].first_out;
00152 }
00153 void nextOut(Edge &e) const {
00154 e.id=edges[e.id].next_out;
00155 }
00156
00157 void firstIn(Edge &e, const Node& v) const {
00158 e.id = nodes[v.id].first_in;
00159 }
00160 void nextIn(Edge &e) const {
00161 e.id=edges[e.id].next_in;
00162 }
00163
00164
00165 static int id(Node v) { return v.id; }
00166 static int id(Edge e) { return e.id; }
00167
00168 static Node nodeFromId(int id) { return Node(id);}
00169 static Edge edgeFromId(int id) { return Edge(id);}
00170
00172
00175 Node addNode() {
00176 int n;
00177
00178 if(first_free_node==-1) {
00179 n = nodes.size();
00180 nodes.push_back(NodeT());
00181 } else {
00182 n = first_free_node;
00183 first_free_node = nodes[n].next;
00184 }
00185
00186 nodes[n].next = first_node;
00187 if(first_node != -1) nodes[first_node].prev = n;
00188 first_node = n;
00189 nodes[n].prev = -1;
00190
00191 nodes[n].first_in = nodes[n].first_out = -1;
00192
00193 return Node(n);
00194 }
00195
00196 Edge addEdge(Node u, Node v) {
00197 int n;
00198
00199 if (first_free_edge == -1) {
00200 n = edges.size();
00201 edges.push_back(EdgeT());
00202 } else {
00203 n = first_free_edge;
00204 first_free_edge = edges[n].next_in;
00205 }
00206
00207 edges[n].source = u.id;
00208 edges[n].target = v.id;
00209
00210 edges[n].next_out = nodes[u.id].first_out;
00211 if(nodes[u.id].first_out != -1) {
00212 edges[nodes[u.id].first_out].prev_out = n;
00213 }
00214
00215 edges[n].next_in = nodes[v.id].first_in;
00216 if(nodes[v.id].first_in != -1) {
00217 edges[nodes[v.id].first_in].prev_in = n;
00218 }
00219
00220 edges[n].prev_in = edges[n].prev_out = -1;
00221
00222 nodes[u.id].first_out = nodes[v.id].first_in = n;
00223
00224 return Edge(n);
00225 }
00226
00227 void erase(const Node& node) {
00228 int n = node.id;
00229
00230 if(nodes[n].next != -1) {
00231 nodes[nodes[n].next].prev = nodes[n].prev;
00232 }
00233
00234 if(nodes[n].prev != -1) {
00235 nodes[nodes[n].prev].next = nodes[n].next;
00236 } else {
00237 first_node = nodes[n].next;
00238 }
00239
00240 nodes[n].next = first_free_node;
00241 first_free_node = n;
00242
00243 }
00244
00245 void erase(const Edge& edge) {
00246 int n = edge.id;
00247
00248 if(edges[n].next_in!=-1) {
00249 edges[edges[n].next_in].prev_in = edges[n].prev_in;
00250 }
00251
00252 if(edges[n].prev_in!=-1) {
00253 edges[edges[n].prev_in].next_in = edges[n].next_in;
00254 } else {
00255 nodes[edges[n].target].first_in = edges[n].next_in;
00256 }
00257
00258
00259 if(edges[n].next_out!=-1) {
00260 edges[edges[n].next_out].prev_out = edges[n].prev_out;
00261 }
00262
00263 if(edges[n].prev_out!=-1) {
00264 edges[edges[n].prev_out].next_out = edges[n].next_out;
00265 } else {
00266 nodes[edges[n].source].first_out = edges[n].next_out;
00267 }
00268
00269 edges[n].next_in = first_free_edge;
00270 first_free_edge = n;
00271
00272 }
00273
00274 void clear() {
00275 edges.clear();
00276 nodes.clear();
00277 first_node = first_free_node = first_free_edge = -1;
00278 }
00279
00280 protected:
00281 void _changeTarget(Edge e, Node n)
00282 {
00283 if(edges[e.id].next_in != -1)
00284 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
00285 if(edges[e.id].prev_in != -1)
00286 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
00287 else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
00288 if (nodes[n.id].first_in != -1) {
00289 edges[nodes[n.id].first_in].prev_in = e.id;
00290 }
00291 edges[e.id].target = n.id;
00292 edges[e.id].prev_in = -1;
00293 edges[e.id].next_in = nodes[n.id].first_in;
00294 nodes[n.id].first_in = e.id;
00295 }
00296 void _changeSource(Edge e, Node n)
00297 {
00298 if(edges[e.id].next_out != -1)
00299 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
00300 if(edges[e.id].prev_out != -1)
00301 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
00302 else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
00303 if (nodes[n.id].first_out != -1) {
00304 edges[nodes[n.id].first_out].prev_out = e.id;
00305 }
00306 edges[e.id].source = n.id;
00307 edges[e.id].prev_out = -1;
00308 edges[e.id].next_out = nodes[n.id].first_out;
00309 nodes[n.id].first_out = e.id;
00310 }
00311
00312 };
00313
00314 typedef ErasableGraphExtender<
00315 ClearableGraphExtender<
00316 ExtendableGraphExtender<
00317 MappableGraphExtender<
00318 IterableGraphExtender<
00319 AlterableGraphExtender<
00320 GraphExtender<ListGraphBase> > > > > > > ExtendedListGraphBase;
00321
00324
00326
00333
00334 class ListGraph : public ExtendedListGraphBase
00335 {
00336 public:
00338
00344 void changeTarget(Edge e, Node n) {
00345 _changeTarget(e,n);
00346 }
00348
00354 void changeSource(Edge e, Node n) {
00355 _changeSource(e,n);
00356 }
00357
00359
00363 void reverseEdge(Edge e) {
00364 Node t=target(e);
00365 _changeTarget(e,source(e));
00366 _changeSource(e,t);
00367 }
00368
00370
00373 void reserveEdge(int n) { edges.reserve(n); };
00374
00376
00388 void contract(Node a, Node b, bool r = true)
00389 {
00390 for(OutEdgeIt e(*this,b);e!=INVALID;) {
00391 OutEdgeIt f=e;
00392 ++f;
00393 if(r && target(e)==a) erase(e);
00394 else changeSource(e,a);
00395 e=f;
00396 }
00397 for(InEdgeIt e(*this,b);e!=INVALID;) {
00398 InEdgeIt f=e;
00399 ++f;
00400 if(r && source(e)==a) erase(e);
00401 else changeTarget(e,a);
00402 e=f;
00403 }
00404 erase(b);
00405 }
00406
00408
00422 Node split(Node n, bool connect = true)
00423 {
00424 Node b = addNode();
00425 for(OutEdgeIt e(*this,n);e!=INVALID;) {
00426 OutEdgeIt f=e;
00427 ++f;
00428 changeSource(e,b);
00429 e=f;
00430 }
00431 if(connect) addEdge(n,b);
00432 return b;
00433 }
00434
00436
00443 Node split(Edge e)
00444 {
00445 Node b = addNode();
00446 addEdge(b,target(e));
00447 changeTarget(e,b);
00448 return b;
00449 }
00450
00452
00460 class Snapshot : protected AlterationNotifier<Node>::ObserverBase,
00461 protected AlterationNotifier<Edge>::ObserverBase
00462 {
00463 public:
00464
00465 class UnsupportedOperation : public LogicError {
00466 public:
00467 virtual const char* exceptionName() const {
00468 return "lemon::ListGraph::Snapshot::UnsupportedOperation";
00469 }
00470 };
00471
00472
00473 protected:
00474
00475 ListGraph *g;
00476 std::list<Node> added_nodes;
00477 std::list<Edge> added_edges;
00478
00479 bool active;
00480 virtual void add(const Node& n) {
00481 added_nodes.push_back(n);
00482 };
00483 virtual void erase(const Node&)
00484 {
00485 throw UnsupportedOperation();
00486 }
00487 virtual void add(const Edge& n) {
00488 added_edges.push_back(n);
00489 };
00490 virtual void erase(const Edge&)
00491 {
00492 throw UnsupportedOperation();
00493 }
00494
00497 virtual void build() {}
00500 virtual void clear() {}
00501
00502 void regist(ListGraph &_g) {
00503 g=&_g;
00504 AlterationNotifier<Node>::ObserverBase::
00505 attach(g->getNotifier(Node()));
00506 AlterationNotifier<Edge>::ObserverBase::
00507 attach(g->getNotifier(Edge()));
00508 }
00509
00510 void deregist() {
00511 AlterationNotifier<Node>::ObserverBase::
00512 detach();
00513 AlterationNotifier<Edge>::ObserverBase::
00514 detach();
00515 g=0;
00516 }
00517
00518 public:
00520
00524 Snapshot() : g(0) {}
00526
00529 Snapshot(ListGraph &_g) {
00530 regist(_g);
00531 }
00534 ~Snapshot()
00535 {
00536 if(g) deregist();
00537 }
00538
00540
00546 void save(ListGraph &_g)
00547 {
00548 if(g!=&_g) {
00549 if(g) deregist();
00550 regist(_g);
00551 }
00552 added_nodes.clear();
00553 added_edges.clear();
00554 }
00555
00557
00561 void restore() {
00562 ListGraph &old_g=*g;
00563 deregist();
00564 while(!added_edges.empty()) {
00565 old_g.erase(added_edges.front());
00566 added_edges.pop_front();
00567 }
00568 while(!added_nodes.empty()) {
00569 old_g.erase(added_nodes.front());
00570 added_nodes.pop_front();
00571 }
00572 }
00573 };
00574
00575 };
00576
00578
00579
00580
00581 typedef ErasableUGraphExtender<
00582 ClearableUGraphExtender<
00583 ExtendableUGraphExtender<
00584 MappableUGraphExtender<
00585 IterableUGraphExtender<
00586 AlterableUGraphExtender<
00587 UGraphExtender<ListGraphBase> > > > > > > ExtendedListUGraphBase;
00588
00591
00593
00604 class ListUGraph : public ExtendedListUGraphBase {
00605 public:
00606 typedef ExtendedListUGraphBase Parent;
00614 void changeTarget(UEdge e, Node n) {
00615 _changeTarget(e,n);
00616 }
00624 void changeSource(UEdge e, Node n) {
00625 _changeSource(e,n);
00626 }
00639 void contract(Node a, Node b, bool r = true) {
00640 for(IncEdgeIt e(*this, b); e!=INVALID;) {
00641 IncEdgeIt f = e; ++f;
00642 if (r && runningNode(e) == a) {
00643 erase(e);
00644 } else if (source(e) == b) {
00645 changeSource(e, a);
00646 } else {
00647 changeTarget(e, a);
00648 }
00649 e = f;
00650 }
00651 erase(b);
00652 }
00653 };
00654
00655
00657 }
00658
00659
00660 #endif