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

smart_graph.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/smart_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_SMART_GRAPH_H
00018 #define LEMON_SMART_GRAPH_H
00019 
00023 
00024 #include <vector>
00025 
00026 #include <lemon/invalid.h>
00027 
00028 #include <lemon/clearable_graph_extender.h>
00029 #include <lemon/extendable_graph_extender.h>
00030 #include <lemon/iterable_graph_extender.h>
00031 #include <lemon/alteration_notifier.h>
00032 #include <lemon/default_map.h>
00033 
00034 #include <lemon/undir_graph_extender.h>
00035 
00036 #include <lemon/utility.h>
00037 
00038 namespace lemon {
00039 
00040   class SmartGraph;
00042 
00045   class SmartGraphBase {
00046 
00047     friend class SmatGraph;
00048 
00049   protected:
00050     struct NodeT 
00051     {
00052       int first_in,first_out;      
00053       NodeT() : first_in(-1), first_out(-1) {}
00054     };
00055     struct EdgeT 
00056     {
00057       int target, source, next_in, next_out;      
00058       //FIXME: is this necessary?
00059       EdgeT() : next_in(-1), next_out(-1) {}  
00060     };
00061 
00062     std::vector<NodeT> nodes;
00063 
00064     std::vector<EdgeT> edges;
00065     
00066     
00067   public:
00068 
00069     typedef SmartGraphBase Graph;
00070 
00071     class Node;
00072     class Edge;
00073 
00074     
00075   public:
00076 
00077     SmartGraphBase() : nodes(), edges() { }
00078     SmartGraphBase(const SmartGraphBase &_g) : nodes(_g.nodes), edges(_g.edges) { }
00079     
00080     typedef True NodeNumTag;
00081     typedef True EdgeNumTag;
00082 
00084     int nodeNum() const { return nodes.size(); }
00086     int edgeNum() const { return edges.size(); }
00087 
00089     
00092     int maxId(Node = INVALID) const { return nodes.size()-1; }
00094     
00097     int maxId(Edge = INVALID) const { return edges.size()-1; }
00098 
00099     Node source(Edge e) const { return edges[e.n].source; }
00100     Node target(Edge e) const { return edges[e.n].target; }
00101 
00103     
00110     static int id(Node v) { return v.n; }
00112     
00119     static int id(Edge e) { return e.n; }
00120 
00121     static Node fromId(int id, Node) { return Node(id);}
00122 
00123     static Edge fromId(int id, Edge) { return Edge(id);}
00124 
00125     Node addNode() {
00126       Node n; n.n=nodes.size();
00127       nodes.push_back(NodeT()); //FIXME: Hmmm...
00128       return n;
00129     }
00130     
00131     Edge addEdge(Node u, Node v) {
00132       Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
00133       edges[e.n].source=u.n; edges[e.n].target=v.n;
00134       edges[e.n].next_out=nodes[u.n].first_out;
00135       edges[e.n].next_in=nodes[v.n].first_in;
00136       nodes[u.n].first_out=nodes[v.n].first_in=e.n;
00137 
00138       return e;
00139     }
00140 
00141     void clear() {
00142       edges.clear();
00143       nodes.clear();
00144     }
00145 
00146 
00147     class Node {
00148       friend class SmartGraphBase;
00149       friend class SmartGraph;
00150 
00151     protected:
00152       int n;
00155       Node(int nn) {n=nn;}
00156     public:
00157       Node() {}
00158       Node (Invalid) { n=-1; }
00159       bool operator==(const Node i) const {return n==i.n;}
00160       bool operator!=(const Node i) const {return n!=i.n;}
00161       bool operator<(const Node i) const {return n<i.n;}
00162     };
00163     
00164 
00165     class Edge {
00166       friend class SmartGraphBase;
00167       friend class SmartGraph;
00168 
00169     protected:
00170       int n;
00173       Edge(int nn) {n=nn;}
00174     public:
00175       Edge() { }
00176       Edge (Invalid) { n=-1; }
00177       bool operator==(const Edge i) const {return n==i.n;}
00178       bool operator!=(const Edge i) const {return n!=i.n;}
00179       bool operator<(const Edge i) const {return n<i.n;}
00180     };
00181 
00182     void first(Node& node) const {
00183       node.n = nodes.size() - 1;
00184     }
00185 
00186     static void next(Node& node) {
00187       --node.n;
00188     }
00189 
00190     void first(Edge& edge) const {
00191       edge.n = edges.size() - 1;
00192     }
00193 
00194     static void next(Edge& edge) {
00195       --edge.n;
00196     }
00197 
00198     void firstOut(Edge& edge, const Node& node) const {
00199       edge.n = nodes[node.n].first_out;
00200     }
00201 
00202     void nextOut(Edge& edge) const {
00203       edge.n = edges[edge.n].next_out;
00204     }
00205 
00206     void firstIn(Edge& edge, const Node& node) const {
00207       edge.n = nodes[node.n].first_in;
00208     }
00209     
00210     void nextIn(Edge& edge) const {
00211       edge.n = edges[edge.n].next_in;
00212     }
00213 
00214     Edge _findEdge(Node u,Node v, Edge prev = INVALID) 
00215     {
00216       int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
00217       while(e!=-1 && edges[e].target!=v.n) e = edges[e].next_out;
00218       prev.n=e;
00219       return prev;
00220     }
00221 
00222   };
00223 
00224   typedef AlterableGraphExtender<SmartGraphBase> AlterableSmartGraphBase;
00225   typedef IterableGraphExtender<AlterableSmartGraphBase> IterableSmartGraphBase;
00226   typedef DefaultMappableGraphExtender<IterableSmartGraphBase> MappableSmartGraphBase;
00227   typedef ExtendableGraphExtender<MappableSmartGraphBase> ExtendableSmartGraphBase;
00228   typedef ClearableGraphExtender<ExtendableSmartGraphBase> ClearableSmartGraphBase;
00229 
00232 
00234 
00244   class SmartGraph : public ClearableSmartGraphBase {
00245   public:
00247     
00262     Edge findEdge(Node u,Node v, Edge prev = INVALID) 
00263     {
00264       return _findEdge(u,v,prev);
00265     }
00266     
00267     class SnapShot;
00268     friend class SnapShot;
00269 
00270   protected:
00271     void restoreSnapShot(const SnapShot &s)
00272     {
00273       while(s.edge_num>edges.size()) {
00274         Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
00275         nodes[edges.back().target].first_in=edges.back().next_in;
00276         nodes[edges.back().source].first_out=edges.back().next_out;
00277         edges.pop_back();
00278       }
00279       //nodes.resize(s.nodes_num);
00280       while(s.node_num>nodes.size()) {
00281         Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
00282         nodes.pop_back();
00283       }
00284     }    
00285 
00286   public:
00288 
00297     class SnapShot 
00298     {
00299       SmartGraph *g;
00300     protected:
00301       friend class SmartGraph;
00302       unsigned int node_num;
00303       unsigned int edge_num;
00304     public:
00306       
00310       SnapShot() : g(0) {}
00312       
00315       SnapShot(SmartGraph &_g) :g(&_g) {
00316         node_num=g->nodes.size();
00317         edge_num=g->edges.size();
00318       }
00319 
00321 
00327       void save(SmartGraph &_g) 
00328       {
00329         g=&_g;
00330         node_num=g->nodes.size();
00331         edge_num=g->edges.size();
00332       }
00333 
00335       
00344       
00345       void restore()
00346       {
00347         g->restoreSnapShot(*this);
00348       }
00349     };
00350   };
00351 
00352 
00353   /**************** Undirected List Graph ****************/
00354 
00355   typedef ClearableUndirGraphExtender<
00356     ExtendableUndirGraphExtender<
00357     MappableUndirGraphExtender<
00358     IterableUndirGraphExtender<
00359     AlterableUndirGraphExtender<
00360     UndirGraphExtender<SmartGraphBase> > > > > > UndirSmartGraphBase;
00361 
00363 
00374   class UndirSmartGraph : public UndirSmartGraphBase {
00375   };
00376 
00377   
00379 } //namespace lemon
00380 
00381 
00382 #endif //LEMON_SMART_GRAPH_H

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