COIN-OR::LEMON - Graph Library

Changeset 1566:12a3101cf3ab in lemon-0.x


Ignore:
Timestamp:
07/18/05 17:08:18 (19 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2065
Message:

UndirFullGraph? class

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/full_graph.h

    r1555 r1566  
    2525#include <lemon/bits/default_map.h>
    2626
     27#include <lemon/bits/undir_graph_extender.h>
     28
    2729#include <lemon/invalid.h>
    2830#include <lemon/utility.h>
     
    3739
    3840  class FullGraphBase {
    39     int NodeNum;
    40     int EdgeNum;
     41    int _nodeNum;
     42    int _edgeNum;
    4143  public:
    4244
     
    5254
    5355    ///Creates a full graph with \c n nodes.
    54     void construct(int n) { NodeNum = n; EdgeNum = n * n; }
     56    void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
    5557    ///
    5658    //    FullGraphBase(const FullGraphBase &_g)
    57     //      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
     59    //      : _nodeNum(_g.nodeNum()), _edgeNum(_nodeNum*_nodeNum) { }
    5860   
    5961    typedef True NodeNumTag;
     
    6163
    6264    ///Number of nodes.
    63     int nodeNum() const { return NodeNum; }
     65    int nodeNum() const { return _nodeNum; }
    6466    ///Number of edges.
    65     int edgeNum() const { return EdgeNum; }
     67    int edgeNum() const { return _edgeNum; }
    6668
    6769    /// Maximum node ID.
     
    6971    /// Maximum node ID.
    7072    ///\sa id(Node)
    71     int maxId(Node = INVALID) const { return NodeNum-1; }
     73    int maxId(Node = INVALID) const { return _nodeNum-1; }
    7274    /// Maximum edge ID.
    7375   
    7476    /// Maximum edge ID.
    7577    ///\sa id(Edge)
    76     int maxId(Edge = INVALID) const { return EdgeNum-1; }
    77 
    78     Node source(Edge e) const { return e.id % NodeNum; }
    79     Node target(Edge e) const { return e.id / NodeNum; }
     78    int maxId(Edge = INVALID) const { return _edgeNum-1; }
     79
     80    Node source(Edge e) const { return e.id % _nodeNum; }
     81    Node target(Edge e) const { return e.id / _nodeNum; }
    8082
    8183
     
    103105   
    104106    static Edge fromId(int id, Edge) { return Edge(id);}
     107
     108    typedef True FindEdgeTag;
    105109
    106110    /// Finds an edge between two nodes.
     
    112116    /// the next edge from \c u to \c v after \c prev.
    113117    /// \return The found edge or INVALID if there is no such an edge.
    114     Edge findEdge(Node u,Node v, Edge prev = INVALID)
    115     {
     118    Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
    116119      return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
    117120    }
     
    138141     
    139142    protected:
    140       int id;  // NodeNum * target + source;
     143      int id;  // _nodeNum * target + source;
    141144
    142145      Edge(int _id) : id(_id) {}
    143146
    144147      Edge(const FullGraphBase& _graph, int source, int target)
    145         : id(_graph.NodeNum * target+source) {}
     148        : id(_graph._nodeNum * target+source) {}
    146149    public:
    147150      Edge() { }
     
    153156
    154157    void first(Node& node) const {
    155       node.id = NodeNum-1;
     158      node.id = _nodeNum-1;
    156159    }
    157160
     
    161164
    162165    void first(Edge& edge) const {
    163       edge.id = EdgeNum-1;
     166      edge.id = _edgeNum-1;
    164167    }
    165168
     
    169172
    170173    void firstOut(Edge& edge, const Node& node) const {
    171       edge.id = EdgeNum + node.id - NodeNum;
     174      edge.id = _edgeNum + node.id - _nodeNum;
    172175    }
    173176
    174177    void nextOut(Edge& edge) const {
    175       edge.id -= NodeNum;
     178      edge.id -= _nodeNum;
    176179      if (edge.id < 0) edge.id = -1;
    177180    }
    178181
    179182    void firstIn(Edge& edge, const Node& node) const {
    180       edge.id = node.id * NodeNum;
     183      edge.id = node.id * _nodeNum;
    181184    }
    182185   
    183186    void nextIn(Edge& edge) const {
    184187      ++edge.id;
    185       if (edge.id % NodeNum == 0) edge.id = -1;
     188      if (edge.id % _nodeNum == 0) edge.id = -1;
    186189    }
    187190
     
    189192
    190193
    191   typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase;
    192   typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase;
    193   typedef DefaultMappableGraphExtender<IterableFullGraphBase> MappableFullGraphBase;
    194 
    195   /// \addtogroup graphs
    196   /// @{
    197 
    198   ///A full graph class.
    199 
    200   ///This is a simple and fast directed full graph implementation.
    201   ///It is completely static, so you can neither add nor delete either
    202   ///edges or nodes.
    203   ///Thus it conforms to
    204   ///the \ref concept::StaticGraph "StaticGraph" concept
    205   ///\sa concept::StaticGraph.
    206   ///
    207   ///\author Alpar Juttner
     194  typedef AlterableGraphExtender<FullGraphBase>
     195  AlterableFullGraphBase;
     196  typedef IterableGraphExtender<AlterableFullGraphBase>
     197  IterableFullGraphBase;
     198  typedef DefaultMappableGraphExtender<IterableFullGraphBase>
     199  MappableFullGraphBase;
     200
     201  /// \ingroup graphs
     202  ///
     203  /// \brief A full graph class.
     204  ///
     205  /// This is a simple and fast directed full graph implementation.
     206  /// It is completely static, so you can neither add nor delete either
     207  /// edges or nodes.
     208  /// Thus it conforms to
     209  /// the \ref concept::StaticGraph "StaticGraph" concept
     210  /// \sa concept::StaticGraph.
     211  ///
     212  /// \author Alpar Juttner
    208213  class FullGraph : public MappableFullGraphBase {
    209214  public:
     
    214219  ///@}
    215220
    216   // Base graph class for UndirFullGraph.
    217221  class UndirFullGraphBase {
    218     int NodeNum;
    219     int EdgeNum;
     222    int _nodeNum;
     223    int _edgeNum;
    220224  public:
    221225
     
    231235
    232236    ///Creates a full graph with \c n nodes.
    233     void construct(int n) { NodeNum = n; EdgeNum = n * (n - 1) / 2; }
     237    void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
    234238    ///
    235239    //    FullGraphBase(const FullGraphBase &_g)
    236     //      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
     240    //      : _nodeNum(_g.nodeNum()), _edgeNum(_nodeNum*_nodeNum) { }
    237241   
    238242    typedef True NodeNumTag;
     
    240244
    241245    ///Number of nodes.
    242     int nodeNum() const { return NodeNum; }
     246    int nodeNum() const { return _nodeNum; }
    243247    ///Number of edges.
    244     int edgeNum() const { return EdgeNum; }
     248    int edgeNum() const { return _edgeNum; }
    245249
    246250    /// Maximum node ID.
     
    248252    /// Maximum node ID.
    249253    ///\sa id(Node)
    250     int maxId(Node = INVALID) const { return NodeNum-1; }
     254    int maxId(Node = INVALID) const { return _nodeNum-1; }
    251255    /// Maximum edge ID.
    252256   
    253257    /// Maximum edge ID.
    254258    ///\sa id(Edge)
    255     int maxId(Edge = INVALID) const { return EdgeNum-1; }
     259    int maxId(Edge = INVALID) const { return _edgeNum-1; }
    256260
    257261    Node source(Edge e) const {
     
    320324     
    321325    protected:
    322       int id;  // NodeNum * target + source;
     326      int id;  // _nodeNum * target + source;
    323327
    324328      Edge(int _id) : id(_id) {}
    325329
    326330      Edge(const UndirFullGraphBase& _graph, int source, int target)
    327         : id(_graph.NodeNum * target+source) {}
     331        : id(_graph._nodeNum * target+source) {}
    328332    public:
    329333      Edge() { }
     
    335339
    336340    void first(Node& node) const {
    337       node.id = NodeNum-1;
     341      node.id = _nodeNum-1;
    338342    }
    339343
     
    343347
    344348    void first(Edge& edge) const {
    345       edge.id = EdgeNum-1;
     349      edge.id = _edgeNum-1;
    346350    }
    347351
     
    370374      int target = e.id - (source) * (source - 1) / 2; ++target;
    371375      ++source;
    372       e.id = source < NodeNum ? source * (source - 1) / 2 + target : -1;
     376      e.id = source < _nodeNum ? source * (source - 1) / 2 + target : -1;
    373377    }
    374378
    375379  };
    376380
    377   /// \addtogroup graphs
    378   /// @{
    379 
    380  
    381   /// \todo UndirFullGraph from the UndirFullGraphBase
    382 
    383 
    384   /// @} 
     381  typedef UndirGraphExtender<UndirFullGraphBase>
     382  UndirUndirFullGraphBase;
     383  typedef AlterableUndirGraphExtender<UndirUndirFullGraphBase>
     384  AlterableUndirFullGraphBase;
     385  typedef IterableUndirGraphExtender<AlterableUndirFullGraphBase>
     386  IterableUndirFullGraphBase;
     387  typedef MappableUndirGraphExtender<IterableUndirFullGraphBase>
     388  MappableUndirFullGraphBase;
     389
     390  /// \ingroup graphs
     391  ///
     392  /// \brief An undirected full graph class.
     393  ///
     394  /// This is a simple and fast directed full graph implementation.
     395  /// It is completely static, so you can neither add nor delete either
     396  /// edges or nodes.
     397  ///
     398  /// The main difference beetween the \e FullGraph and \e UndirFullGraph class
     399  /// is that this class conforms to the undirected graph concept and
     400  /// it does not contain the hook edges.
     401  ///
     402  /// \sa FullGraph
     403  ///
     404  /// \author Balazs Dezso
     405  class UndirFullGraph : public MappableUndirFullGraphBase {
     406  public:
     407    UndirFullGraph(int n) { construct(n); }
     408  };
    385409
    386410} //namespace lemon
Note: See TracChangeset for help on using the changeset viewer.