COIN-OR::LEMON - Graph Library

Changeset 2115:4cd528a30ec1 in lemon-0.x for lemon/full_graph.h


Ignore:
Timestamp:
06/30/06 14:14:36 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2821
Message:

Splitted graph files

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/full_graph.h

    r2111 r2115  
    2222#include <cmath>
    2323
    24 #include <lemon/bits/base_extender.h>
    2524#include <lemon/bits/graph_extender.h>
    2625
     
    3130///\ingroup graphs
    3231///\file
    33 ///\brief FullGraph and FullUGraph classes.
     32///\brief FullGraph class.
    3433
    3534
     
    248247  };
    249248
    250 
    251   /// \brief Base of the FullUGrpah.
    252   ///
    253   /// Base of the FullUGrpah.
    254   class FullUGraphBase {
    255     int _nodeNum;
    256     int _edgeNum;
    257   public:
    258 
    259     typedef FullUGraphBase Graph;
    260 
    261     class Node;
    262     class Edge;
    263 
    264   public:
    265 
    266     FullUGraphBase() {}
    267 
    268 
    269     ///Creates a full graph with \c n nodes.
    270     void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
    271 
    272     /// \brief Returns the node with the given index.
    273     ///
    274     /// Returns the node with the given index. Because it is a
    275     /// static size graph the node's of the graph can be indiced
    276     /// by the range from 0 to \e nodeNum()-1 and the index of
    277     /// the node can accessed by the \e index() member.
    278     Node operator()(int index) const { return Node(index); }
    279 
    280     /// \brief Returns the index of the node.
    281     ///
    282     /// Returns the index of the node. Because it is a
    283     /// static size graph the node's of the graph can be indiced
    284     /// by the range from 0 to \e nodeNum()-1 and the index of
    285     /// the node can accessed by the \e index() member.
    286     int index(const Node& node) const { return node.id; }
    287 
    288     typedef True NodeNumTag;
    289     typedef True EdgeNumTag;
    290 
    291     ///Number of nodes.
    292     int nodeNum() const { return _nodeNum; }
    293     ///Number of edges.
    294     int edgeNum() const { return _edgeNum; }
    295 
    296     /// Maximum node ID.
    297    
    298     /// Maximum node ID.
    299     ///\sa id(Node)
    300     int maxNodeId() const { return _nodeNum-1; }
    301     /// Maximum edge ID.
    302    
    303     /// Maximum edge ID.
    304     ///\sa id(Edge)
    305     int maxEdgeId() const { return _edgeNum-1; }
    306 
    307     /// \brief Returns the node from its \c id.
    308     ///
    309     /// Returns the node from its \c id. If there is not node
    310     /// with the given id the effect of the function is undefinied.
    311     static Node nodeFromId(int id) { return Node(id);}
    312 
    313     /// \brief Returns the edge from its \c id.
    314     ///
    315     /// Returns the edge from its \c id. If there is not edge
    316     /// with the given id the effect of the function is undefinied.
    317     static Edge edgeFromId(int id) { return Edge(id);}
    318 
    319     Node source(Edge e) const {
    320       /// \todo we may do it faster
    321       return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
    322     }
    323 
    324     Node target(Edge e) const {
    325       int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
    326       return Node(e.id - (source) * (source - 1) / 2);
    327     }
    328 
    329 
    330     /// \brief Node ID.
    331     ///
    332     /// The ID of a valid Node is a nonnegative integer not greater than
    333     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    334     /// and the greatest node ID can be actually less then \ref maxNodeId().
    335     ///
    336     /// The ID of the \ref INVALID node is -1.
    337     /// \return The ID of the node \c v.
    338 
    339     static int id(Node v) { return v.id; }
    340 
    341     /// \brief Edge ID.
    342     ///
    343     /// The ID of a valid Edge is a nonnegative integer not greater than
    344     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    345     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    346     ///
    347     /// The ID of the \ref INVALID edge is -1.
    348     ///\return The ID of the edge \c e.
    349     static int id(Edge e) { return e.id; }
    350 
    351     /// \brief Finds an edge between two nodes.
    352     ///
    353     /// Finds an edge from node \c u to node \c v.
    354     ///
    355     /// If \c prev is \ref INVALID (this is the default value), then
    356     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    357     /// the next edge from \c u to \c v after \c prev.
    358     /// \return The found edge or INVALID if there is no such an edge.
    359     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
    360       if (prev.id != -1 || u.id <= v.id) return Edge(-1);
    361       return Edge(u.id * (u.id - 1) / 2 + v.id);
    362     }
    363 
    364     typedef True FindEdgeTag;
    365    
    366      
    367     class Node {
    368       friend class FullUGraphBase;
    369 
    370     protected:
    371       int id;
    372       Node(int _id) { id = _id;}
    373     public:
    374       Node() {}
    375       Node (Invalid) { id = -1; }
    376       bool operator==(const Node node) const {return id == node.id;}
    377       bool operator!=(const Node node) const {return id != node.id;}
    378       bool operator<(const Node node) const {return id < node.id;}
    379     };
    380    
    381 
    382 
    383     class Edge {
    384       friend class FullUGraphBase;
    385      
    386     protected:
    387       int id;  // _nodeNum * target + source;
    388 
    389       Edge(int _id) : id(_id) {}
    390 
    391     public:
    392       Edge() { }
    393       Edge (Invalid) { id = -1; }
    394       bool operator==(const Edge edge) const {return id == edge.id;}
    395       bool operator!=(const Edge edge) const {return id != edge.id;}
    396       bool operator<(const Edge edge) const {return id < edge.id;}
    397     };
    398 
    399     void first(Node& node) const {
    400       node.id = _nodeNum - 1;
    401     }
    402 
    403     static void next(Node& node) {
    404       --node.id;
    405     }
    406 
    407     void first(Edge& edge) const {
    408       edge.id = _edgeNum - 1;
    409     }
    410 
    411     static void next(Edge& edge) {
    412       --edge.id;
    413     }
    414 
    415     void firstOut(Edge& edge, const Node& node) const {     
    416       int src = node.id;
    417       int trg = 0;
    418       edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
    419     }
    420 
    421     /// \todo with specialized iterators we can make faster iterating
    422     void nextOut(Edge& edge) const {
    423       int src = source(edge).id;
    424       int trg = target(edge).id;
    425       ++trg;
    426       edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
    427     }
    428 
    429     void firstIn(Edge& edge, const Node& node) const {
    430       int src = node.id + 1;
    431       int trg = node.id;
    432       edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
    433     }
    434    
    435     void nextIn(Edge& edge) const {
    436       int src = source(edge).id;
    437       int trg = target(edge).id;
    438       ++src;
    439       edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
    440     }
    441 
    442   };
    443 
    444   typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> >
    445   ExtendedFullUGraphBase;
    446 
    447   /// \ingroup graphs
    448   ///
    449   /// \brief An undirected full graph class.
    450   ///
    451   /// This is a simple and fast undirected full graph implementation.
    452   /// It is completely static, so you can neither add nor delete either
    453   /// edges or nodes.
    454   ///
    455   /// The main difference beetween the \e FullGraph and \e FullUGraph class
    456   /// is that this class conforms to the undirected graph concept and
    457   /// it does not contain the loop edges.
    458   ///
    459   /// \sa FullUGraphBase
    460   /// \sa FullGraph
    461   ///
    462   /// \author Balazs Dezso
    463   class FullUGraph : public ExtendedFullUGraphBase {
    464   public:
    465 
    466     typedef ExtendedFullUGraphBase Parent;
    467 
    468     /// \brief Constructor
    469     FullUGraph() { construct(0); }
    470 
    471     /// \brief Constructor
    472     FullUGraph(int n) { construct(n); }
    473 
    474     /// \brief Resize the graph
    475     ///
    476     /// Resize the graph. The function will fully destroy and build the graph.
    477     /// This cause that the maps of the graph will reallocated
    478     /// automatically and the previous values will be lost.
    479     void resize(int n) {
    480       Parent::getNotifier(Edge()).clear();
    481       Parent::getNotifier(UEdge()).clear();
    482       Parent::getNotifier(Node()).clear();
    483       construct(n);
    484       Parent::getNotifier(Node()).build();
    485       Parent::getNotifier(UEdge()).build();
    486       Parent::getNotifier(Edge()).build();
    487     }
    488   };
    489 
    490 
    491   class FullBpUGraphBase {
    492   protected:
    493 
    494     int _aNodeNum;
    495     int _bNodeNum;
    496 
    497     int _edgeNum;
    498 
    499   public:
    500 
    501     class NodeSetError : public LogicError {
    502       virtual const char* exceptionName() const {
    503         return "lemon::FullBpUGraph::NodeSetError";
    504       }
    505     };
    506  
    507     class Node {
    508       friend class FullBpUGraphBase;
    509     protected:
    510       int id;
    511 
    512       Node(int _id) : id(_id) {}
    513     public:
    514       Node() {}
    515       Node(Invalid) { id = -1; }
    516       bool operator==(const Node i) const {return id==i.id;}
    517       bool operator!=(const Node i) const {return id!=i.id;}
    518       bool operator<(const Node i) const {return id<i.id;}
    519     };
    520 
    521     class UEdge {
    522       friend class FullBpUGraphBase;
    523     protected:
    524       int id;
    525 
    526       UEdge(int _id) { id = _id;}
    527     public:
    528       UEdge() {}
    529       UEdge (Invalid) { id = -1; }
    530       bool operator==(const UEdge i) const {return id==i.id;}
    531       bool operator!=(const UEdge i) const {return id!=i.id;}
    532       bool operator<(const UEdge i) const {return id<i.id;}
    533     };
    534 
    535     void construct(int aNodeNum, int bNodeNum) {
    536       _aNodeNum = aNodeNum;
    537       _bNodeNum = bNodeNum;
    538       _edgeNum = aNodeNum * bNodeNum;
    539     }
    540 
    541     void firstANode(Node& node) const {
    542       node.id = 2 * _aNodeNum - 2;
    543       if (node.id < 0) node.id = -1;
    544     }
    545     void nextANode(Node& node) const {
    546       node.id -= 2;
    547       if (node.id < 0) node.id = -1;
    548     }
    549 
    550     void firstBNode(Node& node) const {
    551       node.id = 2 * _bNodeNum - 1;
    552     }
    553     void nextBNode(Node& node) const {
    554       node.id -= 2;
    555     }
    556 
    557     void first(Node& node) const {
    558       if (_aNodeNum > 0) {
    559         node.id = 2 * _aNodeNum - 2;
    560       } else {
    561         node.id = 2 * _bNodeNum - 1;
    562       }
    563     }
    564     void next(Node& node) const {
    565       node.id -= 2;
    566       if (node.id == -2) {
    567         node.id = 2 * _bNodeNum - 1;
    568       }
    569     }
    570  
    571     void first(UEdge& edge) const {
    572       edge.id = _edgeNum - 1;
    573     }
    574     void next(UEdge& edge) const {
    575       --edge.id;
    576     }
    577 
    578     void firstFromANode(UEdge& edge, const Node& node) const {
    579       LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
    580       edge.id = (node.id >> 1) * _bNodeNum;
    581     }
    582     void nextFromANode(UEdge& edge) const {
    583       ++(edge.id);
    584       if (edge.id % _bNodeNum == 0) edge.id = -1;
    585     }
    586 
    587     void firstFromBNode(UEdge& edge, const Node& node) const {
    588       LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
    589       edge.id = (node.id >> 1);
    590     }
    591     void nextFromBNode(UEdge& edge) const {
    592       edge.id += _bNodeNum;
    593       if (edge.id >= _edgeNum) edge.id = -1;
    594     }
    595 
    596     static int id(const Node& node) {
    597       return node.id;
    598     }
    599     static Node nodeFromId(int id) {
    600       return Node(id);
    601     }
    602     int maxNodeId() const {
    603       return _aNodeNum > _bNodeNum ?
    604         _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
    605     }
    606  
    607     static int id(const UEdge& edge) {
    608       return edge.id;
    609     }
    610     static UEdge uEdgeFromId(int id) {
    611       return UEdge(id);
    612     }
    613     int maxUEdgeId() const {
    614       return _edgeNum - 1;
    615     }
    616  
    617     static int aNodeId(const Node& node) {
    618       return node.id >> 1;
    619     }
    620     static Node fromANodeId(int id) {
    621       return Node(id << 1);
    622     }
    623     int maxANodeId() const {
    624       return _aNodeNum;
    625     }
    626 
    627     static int bNodeId(const Node& node) {
    628       return node.id >> 1;
    629     }
    630     static Node fromBNodeId(int id) {
    631       return Node((id << 1) + 1);
    632     }
    633     int maxBNodeId() const {
    634       return _bNodeNum;
    635     }
    636 
    637     Node aNode(const UEdge& edge) const {
    638       return Node((edge.id / _bNodeNum) << 1);
    639     }
    640     Node bNode(const UEdge& edge) const {
    641       return Node(((edge.id % _bNodeNum) << 1) + 1);
    642     }
    643 
    644     static bool aNode(const Node& node) {
    645       return (node.id & 1) == 0;
    646     }
    647 
    648     static bool bNode(const Node& node) {
    649       return (node.id & 1) == 1;
    650     }
    651 
    652     static Node aNode(int index) {
    653       return Node(index << 1);
    654     }
    655 
    656     static Node bNode(int index) {
    657       return Node((index << 1) + 1);
    658     }
    659 
    660     typedef True NodeNumTag;
    661     int nodeNum() const { return _aNodeNum + _bNodeNum; }
    662     int aNodeNum() const { return _aNodeNum; }
    663     int bNodeNum() const { return _bNodeNum; }
    664 
    665     typedef True EdgeNumTag;
    666     int uEdgeNum() const { return _edgeNum; }
    667 
    668   };
    669 
    670 
    671   typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
    672 
    673 
    674   /// \ingroup graphs
    675   ///
    676   /// \brief An undirected full bipartite graph class.
    677   ///
    678   /// This is a simple and fast bipartite undirected full graph implementation.
    679   /// It is completely static, so you can neither add nor delete either
    680   /// edges or nodes.
    681   ///
    682   /// \sa FullUGraphBase
    683   /// \sa FullGraph
    684   ///
    685   /// \author Balazs Dezso
    686   class FullBpUGraph :
    687     public ExtendedFullBpUGraphBase {
    688   public:
    689 
    690     typedef ExtendedFullBpUGraphBase Parent;
    691 
    692     FullBpUGraph() {
    693       Parent::construct(0, 0);
    694     }
    695 
    696     FullBpUGraph(int aNodeNum, int bNodeNum) {
    697       Parent::construct(aNodeNum, bNodeNum);
    698     }
    699 
    700     /// \brief Resize the graph
    701     ///
    702     void resize(int n, int m) {
    703       Parent::getNotifier(Edge()).clear();
    704       Parent::getNotifier(UEdge()).clear();
    705       Parent::getNotifier(Node()).clear();
    706       Parent::getNotifier(ANode()).clear();
    707       Parent::getNotifier(BNode()).clear();
    708       construct(n, m);
    709       Parent::getNotifier(ANode()).build();
    710       Parent::getNotifier(BNode()).build();
    711       Parent::getNotifier(Node()).build();
    712       Parent::getNotifier(UEdge()).build();
    713       Parent::getNotifier(Edge()).build();
    714     }
    715   };
    716 
    717249} //namespace lemon
    718250
Note: See TracChangeset for help on using the changeset viewer.