list_graph.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
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   /**************** Undirected List Graph ****************/
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 } //namespace lemon
00658   
00659 
00660 #endif

Generated on Fri Feb 3 18:38:41 2006 for LEMON by  doxygen 1.4.6