smart_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_SMART_GRAPH_H
00020 #define LEMON_SMART_GRAPH_H
00021 
00025 
00026 #include <vector>
00027 
00028 #include <lemon/invalid.h>
00029 
00030 #include <lemon/bits/clearable_graph_extender.h>
00031 #include <lemon/bits/extendable_graph_extender.h>
00032 #include <lemon/bits/iterable_graph_extender.h>
00033 #include <lemon/bits/alteration_notifier.h>
00034 #include <lemon/bits/default_map.h>
00035 #include <lemon/bits/graph_extender.h>
00036 
00037 #include <lemon/utility.h>
00038 #include <lemon/error.h>
00039 
00040 namespace lemon {
00041 
00042   class SmartGraph;
00044 
00047   class SmartGraphBase {
00048 
00049     friend class SmatGraph;
00050 
00051   protected:
00052     struct NodeT 
00053     {
00054       int first_in,first_out;      
00055       NodeT() : first_in(-1), first_out(-1) {}
00056     };
00057     struct EdgeT 
00058     {
00059       int target, source, next_in, next_out;      
00060       //FIXME: is this necessary?
00061       EdgeT() : next_in(-1), next_out(-1) {}  
00062     };
00063 
00064     std::vector<NodeT> nodes;
00065 
00066     std::vector<EdgeT> edges;
00067     
00068     
00069   public:
00070 
00071     typedef SmartGraphBase Graph;
00072 
00073     class Node;
00074     class Edge;
00075 
00076     
00077   public:
00078 
00079     SmartGraphBase() : nodes(), edges() { }
00080     SmartGraphBase(const SmartGraphBase &_g) 
00081       : nodes(_g.nodes), edges(_g.edges) { }
00082     
00083     typedef True NodeNumTag;
00084     typedef True EdgeNumTag;
00085 
00087     int nodeNum() const { return nodes.size(); }
00089     int edgeNum() const { return edges.size(); }
00090 
00092     
00095     int maxNodeId() const { return nodes.size()-1; }
00097     
00100     int maxEdgeId() const { return edges.size()-1; }
00101 
00102     Node source(Edge e) const { return edges[e.n].source; }
00103     Node target(Edge e) const { return edges[e.n].target; }
00104 
00106     
00113     static int id(Node v) { return v.n; }
00115     
00122     static int id(Edge e) { return e.n; }
00123 
00124     static Node nodeFromId(int id) { return Node(id);}
00125 
00126     static Edge edgeFromId(int id) { return Edge(id);}
00127 
00128     Node addNode() {
00129       Node n; n.n=nodes.size();
00130       nodes.push_back(NodeT()); //FIXME: Hmmm...
00131       return n;
00132     }
00133     
00134     Edge addEdge(Node u, Node v) {
00135       Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
00136       edges[e.n].source=u.n; edges[e.n].target=v.n;
00137       edges[e.n].next_out=nodes[u.n].first_out;
00138       edges[e.n].next_in=nodes[v.n].first_in;
00139       nodes[u.n].first_out=nodes[v.n].first_in=e.n;
00140 
00141       return e;
00142     }
00143 
00144     void clear() {
00145       edges.clear();
00146       nodes.clear();
00147     }
00148 
00149 
00150     class Node {
00151       friend class SmartGraphBase;
00152       friend class SmartGraph;
00153 
00154     protected:
00155       int n;
00156       Node(int nn) {n=nn;}
00157     public:
00158       Node() {}
00159       Node (Invalid) { n=-1; }
00160       bool operator==(const Node i) const {return n==i.n;}
00161       bool operator!=(const Node i) const {return n!=i.n;}
00162       bool operator<(const Node i) const {return n<i.n;}
00163     };
00164     
00165 
00166     class Edge {
00167       friend class SmartGraphBase;
00168       friend class SmartGraph;
00169 
00170     protected:
00171       int n;
00172       Edge(int nn) {n=nn;}
00173     public:
00174       Edge() { }
00175       Edge (Invalid) { n=-1; }
00176       bool operator==(const Edge i) const {return n==i.n;}
00177       bool operator!=(const Edge i) const {return n!=i.n;}
00178       bool operator<(const Edge i) const {return n<i.n;}
00179     };
00180 
00181     void first(Node& node) const {
00182       node.n = nodes.size() - 1;
00183     }
00184 
00185     static void next(Node& node) {
00186       --node.n;
00187     }
00188 
00189     void first(Edge& edge) const {
00190       edge.n = edges.size() - 1;
00191     }
00192 
00193     static void next(Edge& edge) {
00194       --edge.n;
00195     }
00196 
00197     void firstOut(Edge& edge, const Node& node) const {
00198       edge.n = nodes[node.n].first_out;
00199     }
00200 
00201     void nextOut(Edge& edge) const {
00202       edge.n = edges[edge.n].next_out;
00203     }
00204 
00205     void firstIn(Edge& edge, const Node& node) const {
00206       edge.n = nodes[node.n].first_in;
00207     }
00208     
00209     void nextIn(Edge& edge) const {
00210       edge.n = edges[edge.n].next_in;
00211     }
00212 
00213     Node _split(Node n, bool connect = true)
00214     {
00215       Node b = addNode();
00216       nodes[b.n].first_out=nodes[n.n].first_out;
00217       nodes[n.n].first_out=-1;
00218       for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;
00219       if(connect) addEdge(n,b);
00220       return b;
00221     }
00222 
00223   };
00224 
00225   typedef ClearableGraphExtender<
00226     ExtendableGraphExtender<
00227     MappableGraphExtender<
00228     IterableGraphExtender<
00229     AlterableGraphExtender<
00230     GraphExtender<SmartGraphBase> > > > > > ExtendedSmartGraphBase;
00231 
00233 
00235 
00245   class SmartGraph : public ExtendedSmartGraphBase {
00246   public:
00247     
00248     class Snapshot;
00249     friend class Snapshot;
00250 
00251   protected:
00252     void restoreSnapshot(const Snapshot &s)
00253     {
00254       while(s.edge_num<edges.size()) {
00255         Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
00256         nodes[edges.back().target].first_in=edges.back().next_in;
00257         nodes[edges.back().source].first_out=edges.back().next_out;
00258         edges.pop_back();
00259       }
00260       //nodes.resize(s.nodes_num);
00261       while(s.node_num<nodes.size()) {
00262         Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
00263         nodes.pop_back();
00264       }
00265     }    
00266 
00267   public:
00268 
00270     
00284     Node split(Node n, bool connect = true) 
00285     {
00286       Node b = _split(n,connect);
00287       return b;
00288     }
00289   
00290 
00292 
00301     class Snapshot 
00302     {
00303       SmartGraph *g;
00304     protected:
00305       friend class SmartGraph;
00306       unsigned int node_num;
00307       unsigned int edge_num;
00308     public:
00310       
00314       Snapshot() : g(0) {}
00316       
00319       Snapshot(SmartGraph &_g) :g(&_g) {
00320         node_num=g->nodes.size();
00321         edge_num=g->edges.size();
00322       }
00323 
00325 
00331       void save(SmartGraph &_g) 
00332       {
00333         g=&_g;
00334         node_num=g->nodes.size();
00335         edge_num=g->edges.size();
00336       }
00337 
00339       
00347       
00348       void restore()
00349       {
00350         g->restoreSnapshot(*this);
00351       }
00352     };
00353   };
00354 
00355 
00356   /**************** Undirected List Graph ****************/
00357 
00358   typedef ClearableUGraphExtender<
00359     ExtendableUGraphExtender<
00360     MappableUGraphExtender<
00361     IterableUGraphExtender<
00362     AlterableUGraphExtender<
00363     UGraphExtender<SmartGraphBase> > > > > > ExtendedSmartUGraphBase;
00364 
00379   class SmartUGraph : public ExtendedSmartUGraphBase {
00380   };
00381 
00382 
00383   class SmartBpUGraphBase {
00384   public:
00385 
00386     class NodeSetError : public LogicError {
00387       virtual const char* exceptionName() const { 
00388         return "lemon::SmartBpUGraph::NodeSetError";
00389       }
00390     };
00391 
00392   protected:
00393 
00394     struct NodeT {
00395       int first;
00396       NodeT() {}
00397       NodeT(int _first) : first(_first) {}
00398     };
00399 
00400     struct EdgeT {
00401       int aNode, next_out;
00402       int bNode, next_in;
00403     };
00404 
00405     std::vector<NodeT> aNodes;
00406     std::vector<NodeT> bNodes;
00407 
00408     std::vector<EdgeT> edges;
00409 
00410   public:
00411   
00412     class Node {
00413       friend class SmartBpUGraphBase;
00414     protected:
00415       int id;
00416 
00417       Node(int _id) : id(_id) {}
00418     public:
00419       Node() {}
00420       Node(Invalid) { id = -1; }
00421       bool operator==(const Node i) const {return id==i.id;}
00422       bool operator!=(const Node i) const {return id!=i.id;}
00423       bool operator<(const Node i) const {return id<i.id;}
00424     };
00425 
00426     class Edge {
00427       friend class SmartBpUGraphBase;
00428     protected:
00429       int id;
00430 
00431       Edge(int _id) { id = _id;}
00432     public:
00433       Edge() {}
00434       Edge (Invalid) { id = -1; }
00435       bool operator==(const Edge i) const {return id==i.id;}
00436       bool operator!=(const Edge i) const {return id!=i.id;}
00437       bool operator<(const Edge i) const {return id<i.id;}
00438     };
00439 
00440     void firstANode(Node& node) const {
00441       node.id = 2 * aNodes.size() - 2;
00442       if (node.id < 0) node.id = -1; 
00443     }
00444     void nextANode(Node& node) const {
00445       node.id -= 2;
00446       if (node.id < 0) node.id = -1; 
00447     }
00448 
00449     void firstBNode(Node& node) const {
00450       node.id = 2 * bNodes.size() - 1;
00451     }
00452     void nextBNode(Node& node) const {
00453       node.id -= 2;
00454     }
00455 
00456     void first(Node& node) const {
00457       if (aNodes.size() > 0) {
00458         node.id = 2 * aNodes.size() - 2;
00459       } else {
00460         node.id = 2 * bNodes.size() - 1;
00461       }
00462     }
00463     void next(Node& node) const {
00464       node.id -= 2;
00465       if (node.id == -2) {
00466         node.id = 2 * bNodes.size() - 1;
00467       }
00468     }
00469   
00470     void first(Edge& edge) const {
00471       edge.id = edges.size() - 1;
00472     }
00473     void next(Edge& edge) const {
00474       --edge.id;
00475     }
00476 
00477     void firstOut(Edge& edge, const Node& node) const {
00478       LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
00479       edge.id = aNodes[node.id >> 1].first;
00480     }
00481     void nextOut(Edge& edge) const {
00482       edge.id = edges[edge.id].next_out;
00483     }
00484 
00485     void firstIn(Edge& edge, const Node& node) const {
00486       LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
00487       edge.id = bNodes[node.id >> 1].first;
00488     }
00489     void nextIn(Edge& edge) const {
00490       edge.id = edges[edge.id].next_in;
00491     }
00492 
00493     static int id(const Node& node) {
00494       return node.id;
00495     }
00496     static Node nodeFromId(int id) {
00497       return Node(id);
00498     }
00499     int maxNodeId() const {
00500       return aNodes.size() > bNodes.size() ?
00501         aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
00502     }
00503   
00504     static int id(const Edge& edge) {
00505       return edge.id;
00506     }
00507     static Edge edgeFromId(int id) {
00508       return Edge(id);
00509     }
00510     int maxEdgeId() const {
00511       return edges.size();
00512     }
00513   
00514     static int aNodeId(const Node& node) {
00515       return node.id >> 1;
00516     }
00517     static Node fromANodeId(int id, Node) {
00518       return Node(id << 1);
00519     }
00520     int maxANodeId() const {
00521       return aNodes.size();
00522     }
00523 
00524     static int bNodeId(const Node& node) {
00525       return node.id >> 1;
00526     }
00527     static Node fromBNodeId(int id) {
00528       return Node((id << 1) + 1);
00529     }
00530     int maxBNodeId() const {
00531       return bNodes.size();
00532     }
00533 
00534     Node aNode(const Edge& edge) const {
00535       return Node(edges[edge.id].aNode);
00536     }
00537     Node bNode(const Edge& edge) const {
00538       return Node(edges[edge.id].bNode);
00539     }
00540 
00541     static bool aNode(const Node& node) {
00542       return (node.id & 1) == 0;
00543     }
00544 
00545     static bool bNode(const Node& node) {
00546       return (node.id & 1) == 1;
00547     }
00548 
00549     Node addANode() {
00550       NodeT nodeT;
00551       nodeT.first = -1;
00552       aNodes.push_back(nodeT);
00553       return Node(aNodes.size() * 2 - 2);
00554     }
00555 
00556     Node addBNode() {
00557       NodeT nodeT;
00558       nodeT.first = -1;
00559       bNodes.push_back(nodeT);
00560       return Node(bNodes.size() * 2 - 1);
00561     }
00562 
00563     Edge addEdge(const Node& source, const Node& target) {
00564       LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
00565       EdgeT edgeT;
00566       if ((source.id & 1) == 0) {
00567         edgeT.aNode = source.id;
00568         edgeT.bNode = target.id;
00569       } else {
00570         edgeT.aNode = target.id;
00571         edgeT.bNode = source.id;
00572       }
00573       edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
00574       aNodes[edgeT.aNode >> 1].first = edges.size();
00575       edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
00576       bNodes[edgeT.bNode >> 1].first = edges.size();
00577       edges.push_back(edgeT);
00578       return Edge(edges.size() - 1);
00579     }
00580 
00581     void clear() {
00582       aNodes.clear();
00583       bNodes.clear();
00584       edges.clear();
00585     }
00586 
00587   };
00588 
00589 
00590   typedef ClearableBpUGraphExtender<
00591     ExtendableBpUGraphExtender<
00592     MappableBpUGraphExtender<
00593     IterableBpUGraphExtender<
00594     AlterableBpUGraphExtender<
00595     BpUGraphExtender <
00596     SmartBpUGraphBase> > > > > >
00597   ExtendedSmartBpUGraphBase;
00598 
00610   class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
00611 
00612   
00614 } //namespace lemon
00615 
00616 
00617 #endif //LEMON_SMART_GRAPH_H

Generated on Fri Feb 3 18:39:42 2006 for LEMON by  doxygen 1.4.6