Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

list_graph.h

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

Generated on Sat Mar 19 10:58:40 2005 for LEMON by  doxygen 1.4.1