00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef LEMON_LIST_GRAPH_H
00018 #define LEMON_LIST_GRAPH_H
00019
00023
00024 #include <lemon/erasable_graph_extender.h>
00025 #include <lemon/clearable_graph_extender.h>
00026 #include <lemon/extendable_graph_extender.h>
00027 #include <lemon/iterable_graph_extender.h>
00028 #include <lemon/alteration_notifier.h>
00029 #include <lemon/default_map.h>
00030
00031 #include <lemon/undir_graph_extender.h>
00032
00033 #include <list>
00034
00035 namespace lemon {
00036
00037 class ListGraphBase {
00038
00039 protected:
00040 struct NodeT {
00041 int first_in,first_out;
00042 int prev, next;
00043 };
00044
00045 struct EdgeT {
00046 int target, source;
00047 int prev_in, prev_out;
00048 int next_in, next_out;
00049 };
00050
00051 std::vector<NodeT> nodes;
00052
00053 int first_node;
00054
00055 int first_free_node;
00056
00057 std::vector<EdgeT> edges;
00058
00059 int first_free_edge;
00060
00061 public:
00062
00063 typedef ListGraphBase Graph;
00064
00065 class Node {
00066 friend class ListGraphBase;
00067 protected:
00068
00069 int id;
00070 Node(int pid) { id = pid;}
00071
00072 public:
00073 Node() {}
00074 Node (Invalid) { id = -1; }
00075 bool operator==(const Node& node) const {return id == node.id;}
00076 bool operator!=(const Node& node) const {return id != node.id;}
00077 bool operator<(const Node& node) const {return id < node.id;}
00078 };
00079
00080 class Edge {
00081 friend class ListGraphBase;
00082 protected:
00083
00084 int id;
00085 Edge(int pid) { id = pid;}
00086
00087 public:
00088 Edge() {}
00089 Edge (Invalid) { id = -1; }
00090 bool operator==(const Edge& edge) const {return id == edge.id;}
00091 bool operator!=(const Edge& edge) const {return id != edge.id;}
00092 bool operator<(const Edge& edge) const {return id < edge.id;}
00093 };
00094
00095
00096
00097 ListGraphBase()
00098 : nodes(), first_node(-1),
00099 first_free_node(-1), edges(), first_free_edge(-1) {}
00100
00101
00103
00106 int maxId(Node = INVALID) const { return nodes.size()-1; }
00107
00109
00112 int maxId(Edge = INVALID) const { return edges.size()-1; }
00113
00114 Node source(Edge e) const { return edges[e.id].source; }
00115 Node target(Edge e) const { return edges[e.id].target; }
00116
00117
00118 void first(Node& node) const {
00119 node.id = first_node;
00120 }
00121
00122 void next(Node& node) const {
00123 node.id = nodes[node.id].next;
00124 }
00125
00126
00127 void first(Edge& e) const {
00128 int n;
00129 for(n = first_node;
00130 n!=-1 && nodes[n].first_in == -1;
00131 n = nodes[n].next);
00132 e.id = (n == -1) ? -1 : nodes[n].first_in;
00133 }
00134
00135 void next(Edge& edge) const {
00136 if (edges[edge.id].next_in != -1) {
00137 edge.id = edges[edge.id].next_in;
00138 } else {
00139 int n;
00140 for(n = nodes[edges[edge.id].target].next;
00141 n!=-1 && nodes[n].first_in == -1;
00142 n = nodes[n].next);
00143 edge.id = (n == -1) ? -1 : nodes[n].first_in;
00144 }
00145 }
00146
00147 void firstOut(Edge &e, const Node& v) const {
00148 e.id = nodes[v.id].first_out;
00149 }
00150 void nextOut(Edge &e) const {
00151 e.id=edges[e.id].next_out;
00152 }
00153
00154 void firstIn(Edge &e, const Node& v) const {
00155 e.id = nodes[v.id].first_in;
00156 }
00157 void nextIn(Edge &e) const {
00158 e.id=edges[e.id].next_in;
00159 }
00160
00161
00162 static int id(Node v) { return v.id; }
00163 static int id(Edge e) { return e.id; }
00164
00165 static Node fromId(int id, Node) { return Node(id);}
00166 static Edge fromId(int id, Edge) { return Edge(id);}
00167
00169
00172 Node addNode() {
00173 int n;
00174
00175 if(first_free_node==-1) {
00176 n = nodes.size();
00177 nodes.push_back(NodeT());
00178 } else {
00179 n = first_free_node;
00180 first_free_node = nodes[n].next;
00181 }
00182
00183 nodes[n].next = first_node;
00184 if(first_node != -1) nodes[first_node].prev = n;
00185 first_node = n;
00186 nodes[n].prev = -1;
00187
00188 nodes[n].first_in = nodes[n].first_out = -1;
00189
00190 return Node(n);
00191 }
00192
00193 Edge addEdge(Node u, Node v) {
00194 int n;
00195
00196 if (first_free_edge == -1) {
00197 n = edges.size();
00198 edges.push_back(EdgeT());
00199 } else {
00200 n = first_free_edge;
00201 first_free_edge = edges[n].next_in;
00202 }
00203
00204 edges[n].source = u.id;
00205 edges[n].target = v.id;
00206
00207 edges[n].next_out = nodes[u.id].first_out;
00208 if(nodes[u.id].first_out != -1) {
00209 edges[nodes[u.id].first_out].prev_out = n;
00210 }
00211
00212 edges[n].next_in = nodes[v.id].first_in;
00213 if(nodes[v.id].first_in != -1) {
00214 edges[nodes[v.id].first_in].prev_in = n;
00215 }
00216
00217 edges[n].prev_in = edges[n].prev_out = -1;
00218
00219 nodes[u.id].first_out = nodes[v.id].first_in = n;
00220
00221 return Edge(n);
00222 }
00223
00224 void erase(const Node& node) {
00225 int n = node.id;
00226
00227 if(nodes[n].next != -1) {
00228 nodes[nodes[n].next].prev = nodes[n].prev;
00229 }
00230
00231 if(nodes[n].prev != -1) {
00232 nodes[nodes[n].prev].next = nodes[n].next;
00233 } else {
00234 first_node = nodes[n].next;
00235 }
00236
00237 nodes[n].next = first_free_node;
00238 first_free_node = n;
00239
00240 }
00241
00242 void erase(const Edge& edge) {
00243 int n = edge.id;
00244
00245 if(edges[n].next_in!=-1) {
00246 edges[edges[n].next_in].prev_in = edges[n].prev_in;
00247 }
00248
00249 if(edges[n].prev_in!=-1) {
00250 edges[edges[n].prev_in].next_in = edges[n].next_in;
00251 } else {
00252 nodes[edges[n].target].first_in = edges[n].next_in;
00253 }
00254
00255
00256 if(edges[n].next_out!=-1) {
00257 edges[edges[n].next_out].prev_out = edges[n].prev_out;
00258 }
00259
00260 if(edges[n].prev_out!=-1) {
00261 edges[edges[n].prev_out].next_out = edges[n].next_out;
00262 } else {
00263 nodes[edges[n].source].first_out = edges[n].next_out;
00264 }
00265
00266 edges[n].next_in = first_free_edge;
00267 first_free_edge = n;
00268
00269 }
00270
00271 void clear() {
00272 edges.clear();
00273 nodes.clear();
00274 first_node = first_free_node = first_free_edge = -1;
00275 }
00276
00277 protected:
00278 void _moveTarget(Edge e, Node n)
00279 {
00280 if(edges[e.id].next_in != -1)
00281 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
00282 if(edges[e.id].prev_in != -1)
00283 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
00284 else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
00285 edges[e.id].target = n.id;
00286 edges[e.id].prev_in = -1;
00287 edges[e.id].next_in = nodes[n.id].first_in;
00288 nodes[n.id].first_in = e.id;
00289 }
00290 void _moveSource(Edge e, Node n)
00291 {
00292 if(edges[e.id].next_out != -1)
00293 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
00294 if(edges[e.id].prev_out != -1)
00295 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
00296 else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
00297 edges[e.id].source = n.id;
00298 edges[e.id].prev_out = -1;
00299 edges[e.id].next_out = nodes[n.id].first_out;
00300 nodes[n.id].first_out = e.id;
00301 }
00302
00303 };
00304
00305 typedef AlterableGraphExtender<ListGraphBase> AlterableListGraphBase;
00306 typedef IterableGraphExtender<AlterableListGraphBase> IterableListGraphBase;
00307 typedef DefaultMappableGraphExtender<IterableListGraphBase> MappableListGraphBase;
00308 typedef ExtendableGraphExtender<MappableListGraphBase> ExtendableListGraphBase;
00309 typedef ClearableGraphExtender<ExtendableListGraphBase> ClearableListGraphBase;
00310 typedef ErasableGraphExtender<ClearableListGraphBase> ErasableListGraphBase;
00311
00314
00316
00323
00324 class ListGraph : public ErasableListGraphBase
00325 {
00326 public:
00328
00334 void moveTarget(Edge e, Node n) { _moveTarget(e,n); }
00336
00342 void moveSource(Edge e, Node n) { _moveSource(e,n); }
00343
00345
00349 void reverseEdge(Edge e) {
00350 Node t=target(e);
00351 _moveTarget(e,source(e));
00352 _moveSource(e,t);
00353 }
00354
00356
00359 void reserveEdge(int n) { edges.reserve(n); };
00360
00362
00374 void contract(Node a,Node b,bool r=true)
00375 {
00376 for(OutEdgeIt e(*this,b);e!=INVALID;) {
00377 OutEdgeIt f=e;
00378 ++f;
00379 if(r && target(e)==a) erase(e);
00380 else moveSource(e,b);
00381 e=f;
00382 }
00383 for(InEdgeIt e(*this,b);e!=INVALID;) {
00384 InEdgeIt f=e;
00385 ++f;
00386 if(r && source(e)==a) erase(e);
00387 else moveTarget(e,b);
00388 e=f;
00389 }
00390 erase(b);
00391 }
00392
00393
00395
00404 class SnapShot : protected AlterationNotifier<Node>::ObserverBase,
00405 protected AlterationNotifier<Edge>::ObserverBase
00406 {
00407 protected:
00408
00409 ListGraph *g;
00410 std::list<Node> added_nodes;
00411 std::list<Edge> added_edges;
00412
00413 bool active;
00414 virtual void add(const Node& n) {
00415 added_nodes.push_back(n);
00416 };
00419 virtual void erase(const Node&)
00420 {
00421 exit(1);
00422 }
00423 virtual void add(const Edge& n) {
00424 added_edges.push_back(n);
00425 };
00428 virtual void erase(const Edge&)
00429 {
00430 exit(1);
00431 }
00432
00433 void regist(ListGraph &_g) {
00434 g=&_g;
00435 AlterationNotifier<Node>::ObserverBase::
00436 attach(g->getNotifier(Node()));
00437 AlterationNotifier<Edge>::ObserverBase::
00438 attach(g->getNotifier(Edge()));
00439 }
00440
00441 void deregist() {
00442 AlterationNotifier<Node>::ObserverBase::
00443 detach();
00444 AlterationNotifier<Edge>::ObserverBase::
00445 detach();
00446 g=0;
00447 }
00448
00449 public:
00451
00455 SnapShot() : g(0) {}
00457
00460 SnapShot(ListGraph &_g) {
00461 regist(_g);
00462 }
00465 ~SnapShot()
00466 {
00467 if(g) deregist();
00468 }
00469
00471
00477 void save(ListGraph &_g)
00478 {
00479 if(g!=&_g) {
00480 if(g) deregist();
00481 regist(_g);
00482 }
00483 added_nodes.clear();
00484 added_edges.clear();
00485 }
00486
00488
00492 void restore() {
00493 deregist();
00494 while(!added_edges.empty()) {
00495 g->erase(added_edges.front());
00496 added_edges.pop_front();
00497 }
00498 while(!added_nodes.empty()) {
00499 g->erase(added_nodes.front());
00500 added_nodes.pop_front();
00501 }
00502 }
00503 };
00504
00505 };
00506
00507
00508
00509
00510 typedef ErasableUndirGraphExtender<
00511 ClearableUndirGraphExtender<
00512 ExtendableUndirGraphExtender<
00513 MappableUndirGraphExtender<
00514 IterableUndirGraphExtender<
00515 AlterableUndirGraphExtender<
00516 UndirGraphExtender<ListGraphBase> > > > > > > ErasableUndirListGraphBase;
00517
00519
00530 class UndirListGraph : public ErasableUndirListGraphBase {
00531 };
00532
00533
00535 }
00536
00537
00538 #endif