full_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_FULL_GRAPH_H
00020 #define LEMON_FULL_GRAPH_H
00021 
00022 #include <cmath>
00023 
00024 
00025 #include <lemon/bits/iterable_graph_extender.h>
00026 #include <lemon/bits/alteration_notifier.h>
00027 #include <lemon/bits/static_map.h>
00028 #include <lemon/bits/graph_extender.h>
00029 
00030 #include <lemon/invalid.h>
00031 #include <lemon/utility.h>
00032 
00033 
00037 
00038 
00039 namespace lemon {
00040 
00041   class FullGraphBase {
00042     int _nodeNum;
00043     int _edgeNum;
00044   public:
00045 
00046     typedef FullGraphBase Graph;
00047 
00048     class Node;
00049     class Edge;
00050 
00051   public:
00052 
00053     FullGraphBase() {}
00054 
00055 
00057     void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
00059     //    FullGraphBase(const FullGraphBase &_g)
00060     //      : _nodeNum(_g.nodeNum()), _edgeNum(_nodeNum*_nodeNum) { }
00061     
00062     typedef True NodeNumTag;
00063     typedef True EdgeNumTag;
00064 
00066     int nodeNum() const { return _nodeNum; }
00068     int edgeNum() const { return _edgeNum; }
00069 
00071     
00074     int maxNodeId() const { return _nodeNum-1; }
00076     
00079     int maxEdgeId() const { return _edgeNum-1; }
00080 
00081     Node source(Edge e) const { return e.id % _nodeNum; }
00082     Node target(Edge e) const { return e.id / _nodeNum; }
00083 
00084 
00086     
00093 
00094     static int id(Node v) { return v.id; }
00096     
00103     static int id(Edge e) { return e.id; }
00104 
00105     static Node nodeFromId(int id) { return Node(id);}
00106     
00107     static Edge edgeFromId(int id) { return Edge(id);}
00108 
00109     typedef True FindEdgeTag;
00110 
00112     
00119     Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
00120       return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
00121     }
00122     
00123       
00124     class Node {
00125       friend class FullGraphBase;
00126 
00127     protected:
00128       int id;
00129       Node(int _id) : id(_id) {}
00130     public:
00131       Node() {}
00132       Node (Invalid) : id(-1) {}
00133       bool operator==(const Node node) const {return id == node.id;}
00134       bool operator!=(const Node node) const {return id != node.id;}
00135       bool operator<(const Node node) const {return id < node.id;}
00136     };
00137     
00138 
00139 
00140     class Edge {
00141       friend class FullGraphBase;
00142       
00143     protected:
00144       int id;  // _nodeNum * target + source;
00145 
00146       Edge(int _id) : id(_id) {}
00147 
00148       Edge(const FullGraphBase& _graph, int source, int target) 
00149         : id(_graph._nodeNum * target+source) {}
00150     public:
00151       Edge() { }
00152       Edge (Invalid) { id = -1; }
00153       bool operator==(const Edge edge) const {return id == edge.id;}
00154       bool operator!=(const Edge edge) const {return id != edge.id;}
00155       bool operator<(const Edge edge) const {return id < edge.id;}
00156     };
00157 
00158     void first(Node& node) const {
00159       node.id = _nodeNum-1;
00160     }
00161 
00162     static void next(Node& node) {
00163       --node.id;
00164     }
00165 
00166     void first(Edge& edge) const {
00167       edge.id = _edgeNum-1;
00168     }
00169 
00170     static void next(Edge& edge) {
00171       --edge.id;
00172     }
00173 
00174     void firstOut(Edge& edge, const Node& node) const {
00175       edge.id = _edgeNum + node.id - _nodeNum;
00176     }
00177 
00178     void nextOut(Edge& edge) const {
00179       edge.id -= _nodeNum;
00180       if (edge.id < 0) edge.id = -1;
00181     }
00182 
00183     void firstIn(Edge& edge, const Node& node) const {
00184       edge.id = node.id * _nodeNum;
00185     }
00186     
00187     void nextIn(Edge& edge) const {
00188       ++edge.id;
00189       if (edge.id % _nodeNum == 0) edge.id = -1;
00190     }
00191 
00192   };
00193 
00194   typedef StaticMappableGraphExtender<
00195     IterableGraphExtender<
00196     AlterableGraphExtender<
00197     GraphExtender<FullGraphBase> > > > ExtendedFullGraphBase;
00198 
00211   class FullGraph : public ExtendedFullGraphBase {
00212   public:
00213 
00214     FullGraph(int n) { construct(n); }
00215   };
00216 
00217 
00218   class FullUGraphBase {
00219     int _nodeNum;
00220     int _edgeNum;
00221   public:
00222 
00223     typedef FullUGraphBase Graph;
00224 
00225     class Node;
00226     class Edge;
00227 
00228   public:
00229 
00230     FullUGraphBase() {}
00231 
00232 
00234     void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
00236     //    FullGraphBase(const FullGraphBase &_g)
00237     //      : _nodeNum(_g.nodeNum()), _edgeNum(_nodeNum*_nodeNum) { }
00238     
00239     typedef True NodeNumTag;
00240     typedef True EdgeNumTag;
00241 
00243     int nodeNum() const { return _nodeNum; }
00245     int edgeNum() const { return _edgeNum; }
00246 
00248     
00251     int maxNodeId() const { return _nodeNum-1; }
00253     
00256     int maxEdgeId() const { return _edgeNum-1; }
00257 
00258     Node source(Edge e) const { 
00260       return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
00261     }
00262 
00263     Node target(Edge e) const { 
00264       int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
00265       return Node(e.id - (source) * (source - 1) / 2);
00266     }
00267 
00268 
00270     
00277 
00278     static int id(Node v) { return v.id; }
00280     
00287     static int id(Edge e) { return e.id; }
00288 
00290     
00297     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
00298       if (prev.id != -1 || u.id <= v.id) return -1;
00299       return Edge(u.id * (u.id - 1) / 2 + v.id);
00300     }
00301 
00302     typedef True FindEdgeTag;
00303     
00304       
00305     class Node {
00306       friend class FullUGraphBase;
00307 
00308     protected:
00309       int id;
00310       Node(int _id) { id = _id;}
00311     public:
00312       Node() {}
00313       Node (Invalid) { id = -1; }
00314       bool operator==(const Node node) const {return id == node.id;}
00315       bool operator!=(const Node node) const {return id != node.id;}
00316       bool operator<(const Node node) const {return id < node.id;}
00317     };
00318     
00319 
00320 
00321     class Edge {
00322       friend class FullUGraphBase;
00323       
00324     protected:
00325       int id;  // _nodeNum * target + source;
00326 
00327       Edge(int _id) : id(_id) {}
00328 
00329     public:
00330       Edge() { }
00331       Edge (Invalid) { id = -1; }
00332       bool operator==(const Edge edge) const {return id == edge.id;}
00333       bool operator!=(const Edge edge) const {return id != edge.id;}
00334       bool operator<(const Edge edge) const {return id < edge.id;}
00335     };
00336 
00337     void first(Node& node) const {
00338       node.id = _nodeNum - 1;
00339     }
00340 
00341     static void next(Node& node) {
00342       --node.id;
00343     }
00344 
00345     void first(Edge& edge) const {
00346       edge.id = _edgeNum - 1;
00347     }
00348 
00349     static void next(Edge& edge) {
00350       --edge.id;
00351     }
00352 
00353     void firstOut(Edge& edge, const Node& node) const {      
00354       int src = node.id;
00355       int trg = 0;
00356       edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
00357     }
00358 
00360     void nextOut(Edge& edge) const {
00361       int src = source(edge).id;
00362       int trg = target(edge).id;
00363       ++trg;
00364       edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
00365     }
00366 
00367     void firstIn(Edge& edge, const Node& node) const {
00368       int src = node.id + 1;
00369       int trg = node.id;
00370       edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
00371     }
00372     
00373     void nextIn(Edge& edge) const {
00374       int src = source(edge).id;
00375       int trg = target(edge).id;
00376       ++src;
00377       edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
00378     }
00379 
00380   };
00381 
00382   typedef StaticMappableUGraphExtender<
00383     IterableUGraphExtender<
00384     AlterableUGraphExtender<
00385     UGraphExtender<FullUGraphBase> > > > ExtendedFullUGraphBase;
00386 
00402   class FullUGraph : public ExtendedFullUGraphBase {
00403   public:
00404     FullUGraph(int n) { construct(n); }
00405   };
00406 
00407 
00408   class FullBpUGraphBase {
00409   protected:
00410 
00411     int _aNodeNum;
00412     int _bNodeNum;
00413 
00414     int _edgeNum;
00415 
00416   public:
00417 
00418     class NodeSetError : public LogicError {
00419       virtual const char* exceptionName() const { 
00420         return "lemon::FullBpUGraph::NodeSetError";
00421       }
00422     };
00423   
00424     class Node {
00425       friend class FullBpUGraphBase;
00426     protected:
00427       int id;
00428 
00429       Node(int _id) : id(_id) {}
00430     public:
00431       Node() {}
00432       Node(Invalid) { id = -1; }
00433       bool operator==(const Node i) const {return id==i.id;}
00434       bool operator!=(const Node i) const {return id!=i.id;}
00435       bool operator<(const Node i) const {return id<i.id;}
00436     };
00437 
00438     class Edge {
00439       friend class FullBpUGraphBase;
00440     protected:
00441       int id;
00442 
00443       Edge(int _id) { id = _id;}
00444     public:
00445       Edge() {}
00446       Edge (Invalid) { id = -1; }
00447       bool operator==(const Edge i) const {return id==i.id;}
00448       bool operator!=(const Edge i) const {return id!=i.id;}
00449       bool operator<(const Edge i) const {return id<i.id;}
00450     };
00451 
00452     void construct(int aNodeNum, int bNodeNum) {
00453       _aNodeNum = aNodeNum;
00454       _bNodeNum = bNodeNum;
00455       _edgeNum = aNodeNum * bNodeNum;
00456     }
00457 
00458     void firstANode(Node& node) const {
00459       node.id = 2 * _aNodeNum - 2;
00460       if (node.id < 0) node.id = -1; 
00461     }
00462     void nextANode(Node& node) const {
00463       node.id -= 2;
00464       if (node.id < 0) node.id = -1; 
00465     }
00466 
00467     void firstBNode(Node& node) const {
00468       node.id = 2 * _bNodeNum - 1;
00469     }
00470     void nextBNode(Node& node) const {
00471       node.id -= 2;
00472     }
00473 
00474     void first(Node& node) const {
00475       if (_aNodeNum > 0) {
00476         node.id = 2 * _aNodeNum - 2;
00477       } else {
00478         node.id = 2 * _bNodeNum - 1;
00479       }
00480     }
00481     void next(Node& node) const {
00482       node.id -= 2;
00483       if (node.id == -2) {
00484         node.id = 2 * _bNodeNum - 1;
00485       }
00486     }
00487   
00488     void first(Edge& edge) const {
00489       edge.id = _edgeNum - 1;
00490     }
00491     void next(Edge& edge) const {
00492       --edge.id;
00493     }
00494 
00495     void firstOut(Edge& edge, const Node& node) const {
00496       LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
00497       edge.id = (node.id >> 1) * _bNodeNum;
00498     }
00499     void nextOut(Edge& edge) const {
00500       ++(edge.id);
00501       if (edge.id % _bNodeNum == 0) edge.id = -1;
00502     }
00503 
00504     void firstIn(Edge& edge, const Node& node) const {
00505       LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
00506       edge.id = (node.id >> 1);
00507     }
00508     void nextIn(Edge& edge) const {
00509       edge.id += _bNodeNum;
00510       if (edge.id >= _edgeNum) edge.id = -1;
00511     }
00512 
00513     static int id(const Node& node) {
00514       return node.id;
00515     }
00516     static Node nodeFromId(int id) {
00517       return Node(id);
00518     }
00519     int maxNodeId() const {
00520       return _aNodeNum > _bNodeNum ? 
00521         _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
00522     }
00523   
00524     static int id(const Edge& edge) {
00525       return edge.id;
00526     }
00527     static Edge edgeFromId(int id) {
00528       return Edge(id);
00529     }
00530     int maxEdgeId() const {
00531       return _edgeNum - 1;
00532     }
00533   
00534     static int aNodeId(const Node& node) {
00535       return node.id >> 1;
00536     }
00537     static Node fromANodeId(int id, Node) {
00538       return Node(id << 1);
00539     }
00540     int maxANodeId() const {
00541       return _aNodeNum;
00542     }
00543 
00544     static int bNodeId(const Node& node) {
00545       return node.id >> 1;
00546     }
00547     static Node fromBNodeId(int id) {
00548       return Node((id << 1) + 1);
00549     }
00550     int maxBNodeId() const {
00551       return _bNodeNum;
00552     }
00553 
00554     Node aNode(const Edge& edge) const {
00555       return Node((edge.id / _bNodeNum) << 1);
00556     }
00557     Node bNode(const Edge& edge) const {
00558       return Node(((edge.id % _bNodeNum) << 1) + 1);
00559     }
00560 
00561     static bool aNode(const Node& node) {
00562       return (node.id & 1) == 0;
00563     }
00564 
00565     static bool bNode(const Node& node) {
00566       return (node.id & 1) == 1;
00567     }
00568 
00569     static Node aNode(int index) {
00570       return Node(index << 1);
00571     }
00572 
00573     static Node bNode(int index) {
00574       return Node((index << 1) + 1);
00575     }
00576 
00577   };
00578 
00579 
00580   typedef StaticMappableBpUGraphExtender<
00581     IterableBpUGraphExtender<
00582     AlterableBpUGraphExtender<
00583     BpUGraphExtender <
00584     FullBpUGraphBase> > > >
00585   ExtendedFullBpUGraphBase;
00586 
00587 
00599   class FullBpUGraph : 
00600     public ExtendedFullBpUGraphBase {
00601   public:
00602     typedef ExtendedFullBpUGraphBase Parent;
00603     FullBpUGraph(int aNodeNum, int bNodeNum) {
00604       Parent::construct(aNodeNum, bNodeNum);
00605     }
00606   };
00607 
00608 } //namespace lemon
00609 
00610 
00611 #endif //LEMON_FULL_GRAPH_H

Generated on Fri Feb 3 18:37:02 2006 for LEMON by  doxygen 1.4.6