UndirFullGraph class
authordeba
Mon, 18 Jul 2005 15:08:18 +0000
changeset 156612a3101cf3ab
parent 1565 96244ea562a3
child 1567 3ea28f39218b
UndirFullGraph class
lemon/full_graph.h
     1.1 --- a/lemon/full_graph.h	Mon Jul 18 15:07:28 2005 +0000
     1.2 +++ b/lemon/full_graph.h	Mon Jul 18 15:08:18 2005 +0000
     1.3 @@ -24,6 +24,8 @@
     1.4  #include <lemon/bits/alteration_notifier.h>
     1.5  #include <lemon/bits/default_map.h>
     1.6  
     1.7 +#include <lemon/bits/undir_graph_extender.h>
     1.8 +
     1.9  #include <lemon/invalid.h>
    1.10  #include <lemon/utility.h>
    1.11  
    1.12 @@ -36,8 +38,8 @@
    1.13  namespace lemon {
    1.14  
    1.15    class FullGraphBase {
    1.16 -    int NodeNum;
    1.17 -    int EdgeNum;
    1.18 +    int _nodeNum;
    1.19 +    int _edgeNum;
    1.20    public:
    1.21  
    1.22      typedef FullGraphBase Graph;
    1.23 @@ -51,32 +53,32 @@
    1.24  
    1.25  
    1.26      ///Creates a full graph with \c n nodes.
    1.27 -    void construct(int n) { NodeNum = n; EdgeNum = n * n; }
    1.28 +    void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
    1.29      ///
    1.30      //    FullGraphBase(const FullGraphBase &_g)
    1.31 -    //      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
    1.32 +    //      : _nodeNum(_g.nodeNum()), _edgeNum(_nodeNum*_nodeNum) { }
    1.33      
    1.34      typedef True NodeNumTag;
    1.35      typedef True EdgeNumTag;
    1.36  
    1.37      ///Number of nodes.
    1.38 -    int nodeNum() const { return NodeNum; }
    1.39 +    int nodeNum() const { return _nodeNum; }
    1.40      ///Number of edges.
    1.41 -    int edgeNum() const { return EdgeNum; }
    1.42 +    int edgeNum() const { return _edgeNum; }
    1.43  
    1.44      /// Maximum node ID.
    1.45      
    1.46      /// Maximum node ID.
    1.47      ///\sa id(Node)
    1.48 -    int maxId(Node = INVALID) const { return NodeNum-1; }
    1.49 +    int maxId(Node = INVALID) const { return _nodeNum-1; }
    1.50      /// Maximum edge ID.
    1.51      
    1.52      /// Maximum edge ID.
    1.53      ///\sa id(Edge)
    1.54 -    int maxId(Edge = INVALID) const { return EdgeNum-1; }
    1.55 +    int maxId(Edge = INVALID) const { return _edgeNum-1; }
    1.56  
    1.57 -    Node source(Edge e) const { return e.id % NodeNum; }
    1.58 -    Node target(Edge e) const { return e.id / NodeNum; }
    1.59 +    Node source(Edge e) const { return e.id % _nodeNum; }
    1.60 +    Node target(Edge e) const { return e.id / _nodeNum; }
    1.61  
    1.62  
    1.63      /// Node ID.
    1.64 @@ -103,6 +105,8 @@
    1.65      
    1.66      static Edge fromId(int id, Edge) { return Edge(id);}
    1.67  
    1.68 +    typedef True FindEdgeTag;
    1.69 +
    1.70      /// Finds an edge between two nodes.
    1.71      
    1.72      /// Finds an edge from node \c u to node \c v.
    1.73 @@ -111,8 +115,7 @@
    1.74      /// It finds the first edge from \c u to \c v. Otherwise it looks for
    1.75      /// the next edge from \c u to \c v after \c prev.
    1.76      /// \return The found edge or INVALID if there is no such an edge.
    1.77 -    Edge findEdge(Node u,Node v, Edge prev = INVALID) 
    1.78 -    {
    1.79 +    Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
    1.80        return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
    1.81      }
    1.82      
    1.83 @@ -137,12 +140,12 @@
    1.84        friend class FullGraphBase;
    1.85        
    1.86      protected:
    1.87 -      int id;  // NodeNum * target + source;
    1.88 +      int id;  // _nodeNum * target + source;
    1.89  
    1.90        Edge(int _id) : id(_id) {}
    1.91  
    1.92        Edge(const FullGraphBase& _graph, int source, int target) 
    1.93 -	: id(_graph.NodeNum * target+source) {}
    1.94 +	: id(_graph._nodeNum * target+source) {}
    1.95      public:
    1.96        Edge() { }
    1.97        Edge (Invalid) { id = -1; }
    1.98 @@ -152,7 +155,7 @@
    1.99      };
   1.100  
   1.101      void first(Node& node) const {
   1.102 -      node.id = NodeNum-1;
   1.103 +      node.id = _nodeNum-1;
   1.104      }
   1.105  
   1.106      static void next(Node& node) {
   1.107 @@ -160,7 +163,7 @@
   1.108      }
   1.109  
   1.110      void first(Edge& edge) const {
   1.111 -      edge.id = EdgeNum-1;
   1.112 +      edge.id = _edgeNum-1;
   1.113      }
   1.114  
   1.115      static void next(Edge& edge) {
   1.116 @@ -168,43 +171,45 @@
   1.117      }
   1.118  
   1.119      void firstOut(Edge& edge, const Node& node) const {
   1.120 -      edge.id = EdgeNum + node.id - NodeNum;
   1.121 +      edge.id = _edgeNum + node.id - _nodeNum;
   1.122      }
   1.123  
   1.124      void nextOut(Edge& edge) const {
   1.125 -      edge.id -= NodeNum;
   1.126 +      edge.id -= _nodeNum;
   1.127        if (edge.id < 0) edge.id = -1;
   1.128      }
   1.129  
   1.130      void firstIn(Edge& edge, const Node& node) const {
   1.131 -      edge.id = node.id * NodeNum;
   1.132 +      edge.id = node.id * _nodeNum;
   1.133      }
   1.134      
   1.135      void nextIn(Edge& edge) const {
   1.136        ++edge.id;
   1.137 -      if (edge.id % NodeNum == 0) edge.id = -1;
   1.138 +      if (edge.id % _nodeNum == 0) edge.id = -1;
   1.139      }
   1.140  
   1.141    };
   1.142  
   1.143  
   1.144 -  typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase;
   1.145 -  typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase;
   1.146 -  typedef DefaultMappableGraphExtender<IterableFullGraphBase> MappableFullGraphBase;
   1.147 +  typedef AlterableGraphExtender<FullGraphBase> 
   1.148 +  AlterableFullGraphBase;
   1.149 +  typedef IterableGraphExtender<AlterableFullGraphBase> 
   1.150 +  IterableFullGraphBase;
   1.151 +  typedef DefaultMappableGraphExtender<IterableFullGraphBase> 
   1.152 +  MappableFullGraphBase;
   1.153  
   1.154 -  /// \addtogroup graphs
   1.155 -  /// @{
   1.156 -
   1.157 -  ///A full graph class.
   1.158 -
   1.159 -  ///This is a simple and fast directed full graph implementation.
   1.160 -  ///It is completely static, so you can neither add nor delete either
   1.161 -  ///edges or nodes.
   1.162 -  ///Thus it conforms to
   1.163 -  ///the \ref concept::StaticGraph "StaticGraph" concept
   1.164 -  ///\sa concept::StaticGraph.
   1.165 +  /// \ingroup graphs
   1.166    ///
   1.167 -  ///\author Alpar Juttner
   1.168 +  /// \brief A full graph class.
   1.169 +  ///
   1.170 +  /// This is a simple and fast directed full graph implementation.
   1.171 +  /// It is completely static, so you can neither add nor delete either
   1.172 +  /// edges or nodes.
   1.173 +  /// Thus it conforms to
   1.174 +  /// the \ref concept::StaticGraph "StaticGraph" concept
   1.175 +  /// \sa concept::StaticGraph.
   1.176 +  ///
   1.177 +  /// \author Alpar Juttner
   1.178    class FullGraph : public MappableFullGraphBase {
   1.179    public:
   1.180  
   1.181 @@ -213,10 +218,9 @@
   1.182  
   1.183    ///@}
   1.184  
   1.185 -  // Base graph class for UndirFullGraph.
   1.186    class UndirFullGraphBase {
   1.187 -    int NodeNum;
   1.188 -    int EdgeNum;
   1.189 +    int _nodeNum;
   1.190 +    int _edgeNum;
   1.191    public:
   1.192  
   1.193      typedef UndirFullGraphBase Graph;
   1.194 @@ -230,29 +234,29 @@
   1.195  
   1.196  
   1.197      ///Creates a full graph with \c n nodes.
   1.198 -    void construct(int n) { NodeNum = n; EdgeNum = n * (n - 1) / 2; }
   1.199 +    void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
   1.200      ///
   1.201      //    FullGraphBase(const FullGraphBase &_g)
   1.202 -    //      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
   1.203 +    //      : _nodeNum(_g.nodeNum()), _edgeNum(_nodeNum*_nodeNum) { }
   1.204      
   1.205      typedef True NodeNumTag;
   1.206      typedef True EdgeNumTag;
   1.207  
   1.208      ///Number of nodes.
   1.209 -    int nodeNum() const { return NodeNum; }
   1.210 +    int nodeNum() const { return _nodeNum; }
   1.211      ///Number of edges.
   1.212 -    int edgeNum() const { return EdgeNum; }
   1.213 +    int edgeNum() const { return _edgeNum; }
   1.214  
   1.215      /// Maximum node ID.
   1.216      
   1.217      /// Maximum node ID.
   1.218      ///\sa id(Node)
   1.219 -    int maxId(Node = INVALID) const { return NodeNum-1; }
   1.220 +    int maxId(Node = INVALID) const { return _nodeNum-1; }
   1.221      /// Maximum edge ID.
   1.222      
   1.223      /// Maximum edge ID.
   1.224      ///\sa id(Edge)
   1.225 -    int maxId(Edge = INVALID) const { return EdgeNum-1; }
   1.226 +    int maxId(Edge = INVALID) const { return _edgeNum-1; }
   1.227  
   1.228      Node source(Edge e) const { 
   1.229        /// \todo we may do it faster
   1.230 @@ -319,12 +323,12 @@
   1.231        friend class UndirFullGraphBase;
   1.232        
   1.233      protected:
   1.234 -      int id;  // NodeNum * target + source;
   1.235 +      int id;  // _nodeNum * target + source;
   1.236  
   1.237        Edge(int _id) : id(_id) {}
   1.238  
   1.239        Edge(const UndirFullGraphBase& _graph, int source, int target) 
   1.240 -	: id(_graph.NodeNum * target+source) {}
   1.241 +	: id(_graph._nodeNum * target+source) {}
   1.242      public:
   1.243        Edge() { }
   1.244        Edge (Invalid) { id = -1; }
   1.245 @@ -334,7 +338,7 @@
   1.246      };
   1.247  
   1.248      void first(Node& node) const {
   1.249 -      node.id = NodeNum-1;
   1.250 +      node.id = _nodeNum-1;
   1.251      }
   1.252  
   1.253      static void next(Node& node) {
   1.254 @@ -342,7 +346,7 @@
   1.255      }
   1.256  
   1.257      void first(Edge& edge) const {
   1.258 -      edge.id = EdgeNum-1;
   1.259 +      edge.id = _edgeNum-1;
   1.260      }
   1.261  
   1.262      static void next(Edge& edge) {
   1.263 @@ -369,19 +373,39 @@
   1.264        int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
   1.265        int target = e.id - (source) * (source - 1) / 2; ++target;
   1.266        ++source;
   1.267 -      e.id = source < NodeNum ? source * (source - 1) / 2 + target : -1;
   1.268 +      e.id = source < _nodeNum ? source * (source - 1) / 2 + target : -1;
   1.269      }
   1.270  
   1.271    };
   1.272  
   1.273 -  /// \addtogroup graphs
   1.274 -  /// @{
   1.275 +  typedef UndirGraphExtender<UndirFullGraphBase>
   1.276 +  UndirUndirFullGraphBase;
   1.277 +  typedef AlterableUndirGraphExtender<UndirUndirFullGraphBase> 
   1.278 +  AlterableUndirFullGraphBase;
   1.279 +  typedef IterableUndirGraphExtender<AlterableUndirFullGraphBase> 
   1.280 +  IterableUndirFullGraphBase;
   1.281 +  typedef MappableUndirGraphExtender<IterableUndirFullGraphBase> 
   1.282 +  MappableUndirFullGraphBase;
   1.283  
   1.284 -  
   1.285 -  /// \todo UndirFullGraph from the UndirFullGraphBase
   1.286 -
   1.287 -
   1.288 -  /// @}  
   1.289 +  /// \ingroup graphs
   1.290 +  ///
   1.291 +  /// \brief An undirected full graph class.
   1.292 +  ///
   1.293 +  /// This is a simple and fast directed full graph implementation.
   1.294 +  /// It is completely static, so you can neither add nor delete either
   1.295 +  /// edges or nodes.
   1.296 +  ///
   1.297 +  /// The main difference beetween the \e FullGraph and \e UndirFullGraph class
   1.298 +  /// is that this class conforms to the undirected graph concept and
   1.299 +  /// it does not contain the hook edges.
   1.300 +  ///
   1.301 +  /// \sa FullGraph
   1.302 +  ///
   1.303 +  /// \author Balazs Dezso
   1.304 +  class UndirFullGraph : public MappableUndirFullGraphBase {
   1.305 +  public:
   1.306 +    UndirFullGraph(int n) { construct(n); }
   1.307 +  };
   1.308  
   1.309  } //namespace lemon
   1.310