COIN-OR::LEMON - Graph Library

Changeset 365:a12eef1f82b2 in lemon-1.2 for lemon


Ignore:
Timestamp:
11/06/08 15:16:37 (11 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Rework hypercube graph implementation to be undirected (#57)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/hypercube_graph.h

    r364 r365  
    2020#define HYPERCUBE_GRAPH_H
    2121
    22 #include <iostream>
    2322#include <vector>
    2423#include <lemon/core.h>
    25 #include <lemon/error.h>
    26 
    27 #include <lemon/bits/base_extender.h>
     24#include <lemon/assert.h>
    2825#include <lemon/bits/graph_extender.h>
    2926
    3027///\ingroup graphs
    3128///\file
    32 ///\brief HypercubeDigraph class.
     29///\brief HypercubeGraph class.
    3330
    3431namespace lemon {
    3532
    36   class HypercubeDigraphBase {
     33  class HypercubeGraphBase {
    3734
    3835  public:
    3936
    40     typedef HypercubeDigraphBase Digraph;
     37    typedef HypercubeGraphBase Graph;
    4138
    4239    class Node;
     40    class Edge;
    4341    class Arc;
    4442
    4543  public:
    4644
    47     HypercubeDigraphBase() {}
     45    HypercubeGraphBase() {}
    4846
    4947  protected:
    5048
    5149    void construct(int dim) {
     50      LEMON_ASSERT(dim >= 1, "The number of dimensions must be at least 1.");
    5251      _dim = dim;
    53       _nodeNum = 1 << dim;
     52      _node_num = 1 << dim;
     53      _edge_num = dim * (1 << dim-1);
    5454    }
    5555
     
    5757
    5858    typedef True NodeNumTag;
     59    typedef True EdgeNumTag;
    5960    typedef True ArcNumTag;
    6061
    61     int nodeNum() const { return _nodeNum; }
    62     int arcNum() const { return _nodeNum * _dim; }
    63 
    64     int maxNodeId() const { return nodeNum() - 1; }
    65     int maxArcId() const { return arcNum() - 1; }
    66 
    67     Node source(Arc e) const {
    68       return e.id / _dim;
    69     }
    70 
    71     Node target(Arc e) const {
    72       return (e.id / _dim) ^ (1 << (e.id % _dim));
    73     }
    74 
    75     static int id(Node v) { return v.id; }
    76     static int id(Arc e) { return e.id; }
     62    int nodeNum() const { return _node_num; }
     63    int edgeNum() const { return _edge_num; }
     64    int arcNum() const { return 2 * _edge_num; }
     65
     66    int maxNodeId() const { return _node_num - 1; }
     67    int maxEdgeId() const { return _edge_num - 1; }
     68    int maxArcId() const { return 2 * _edge_num - 1; }
    7769
    7870    static Node nodeFromId(int id) { return Node(id); }
    79 
     71    static Edge edgeFromId(int id) { return Edge(id); }
    8072    static Arc arcFromId(int id) { return Arc(id); }
    8173
     74    static int id(Node node) { return node._id; }
     75    static int id(Edge edge) { return edge._id; }
     76    static int id(Arc arc) { return arc._id; }
     77
     78    Node u(Edge edge) const {
     79      int base = edge._id & ((1 << _dim-1) - 1);
     80      int k = edge._id >> _dim-1;
     81      return ((base >> k) << k+1) | (base & ((1 << k) - 1));
     82    }
     83
     84    Node v(Edge edge) const {
     85      int base = edge._id & ((1 << _dim-1) - 1);
     86      int k = edge._id >> _dim-1;
     87      return ((base >> k) << k+1) | (base & ((1 << k) - 1)) | (1 << k);
     88    }
     89
     90    Node source(Arc arc) const {
     91      return (arc._id & 1) == 1 ? u(arc) : v(arc);
     92    }
     93
     94    Node target(Arc arc) const {
     95      return (arc._id & 1) == 1 ? v(arc) : u(arc);
     96    }
     97
     98    typedef True FindEdgeTag;
     99    typedef True FindArcTag;
     100
     101    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
     102      if (prev != INVALID) return INVALID;
     103      int d = u._id ^ v._id;
     104      int k = 0;
     105      if (d == 0) return INVALID;
     106      for ( ; (d & 1) == 0; d >>= 1) ++k;
     107      if (d >> 1 != 0) return INVALID;
     108      return (k << _dim-1) | ((u._id >> k+1) << k) | (u._id & ((1 << k) - 1));
     109    }
     110
     111    Arc findArc(Node u, Node v, Arc prev = INVALID) const {
     112      Edge edge = findEdge(u, v, prev);
     113      if (edge == INVALID) return INVALID;
     114      int k = edge._id >> _dim-1;
     115      return ((u._id >> k) & 1) == 1 ? edge._id << 1 : (edge._id << 1) | 1;
     116    }
     117
    82118    class Node {
    83       friend class HypercubeDigraphBase;
     119      friend class HypercubeGraphBase;
     120
    84121    protected:
    85       int id;
    86       Node(int _id) { id = _id;}
     122      int _id;
     123      Node(int id) : _id(id) {}
    87124    public:
    88125      Node() {}
    89       Node (Invalid) { id = -1; }
    90       bool operator==(const Node node) const { return id == node.id; }
    91       bool operator!=(const Node node) const { return id != node.id; }
    92       bool operator<(const Node node) const { return id < node.id; }
     126      Node (Invalid) : _id(-1) {}
     127      bool operator==(const Node node) const {return _id == node._id;}
     128      bool operator!=(const Node node) const {return _id != node._id;}
     129      bool operator<(const Node node) const {return _id < node._id;}
    93130    };
    94131
     132    class Edge {
     133      friend class HypercubeGraphBase;
     134      friend class Arc;
     135
     136    protected:
     137      int _id;
     138
     139      Edge(int id) : _id(id) {}
     140
     141    public:
     142      Edge() {}
     143      Edge (Invalid) : _id(-1) {}
     144      bool operator==(const Edge edge) const {return _id == edge._id;}
     145      bool operator!=(const Edge edge) const {return _id != edge._id;}
     146      bool operator<(const Edge edge) const {return _id < edge._id;}
     147    };
     148
    95149    class Arc {
    96       friend class HypercubeDigraphBase;
     150      friend class HypercubeGraphBase;
     151
    97152    protected:
    98       int id;
    99       Arc(int _id) : id(_id) {}
     153      int _id;
     154
     155      Arc(int id) : _id(id) {}
     156
    100157    public:
    101       Arc() { }
    102       Arc (Invalid) { id = -1; }
    103       bool operator==(const Arc arc) const { return id == arc.id; }
    104       bool operator!=(const Arc arc) const { return id != arc.id; }
    105       bool operator<(const Arc arc) const { return id < arc.id; }
     158      Arc() {}
     159      Arc (Invalid) : _id(-1) {}
     160      operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
     161      bool operator==(const Arc arc) const {return _id == arc._id;}
     162      bool operator!=(const Arc arc) const {return _id != arc._id;}
     163      bool operator<(const Arc arc) const {return _id < arc._id;}
    106164    };
    107165
    108166    void first(Node& node) const {
    109       node.id = nodeNum() - 1;
     167      node._id = _node_num - 1;
    110168    }
    111169
    112170    static void next(Node& node) {
    113       --node.id;
     171      --node._id;
     172    }
     173
     174    void first(Edge& edge) const {
     175      edge._id = _edge_num - 1;
     176    }
     177
     178    static void next(Edge& edge) {
     179      --edge._id;
    114180    }
    115181
    116182    void first(Arc& arc) const {
    117       arc.id = arcNum() - 1;
     183      arc._id = 2 * _edge_num - 1;
    118184    }
    119185
    120186    static void next(Arc& arc) {
    121       --arc.id;
     187      --arc._id;
     188    }
     189
     190    void firstInc(Edge& edge, bool& dir, const Node& node) const {
     191      edge._id = node._id >> 1;
     192      dir = (node._id & 1) == 0;
     193    }
     194
     195    void nextInc(Edge& edge, bool& dir) const {
     196      Node n = dir ? u(edge) : v(edge);
     197      int k = (edge._id >> _dim-1) + 1;
     198      if (k < _dim) {
     199        edge._id = (k << _dim-1) |
     200                   ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
     201        dir = ((n._id >> k) & 1) == 0;
     202      } else {
     203        edge._id = -1;
     204        dir = true;
     205      }
    122206    }
    123207
    124208    void firstOut(Arc& arc, const Node& node) const {
    125       arc.id = node.id * _dim;
     209      arc._id = ((node._id >> 1) << 1) | (~node._id & 1);
    126210    }
    127211
    128212    void nextOut(Arc& arc) const {
    129       ++arc.id;
    130       if (arc.id % _dim == 0) arc.id = -1;
     213      Node n = (arc._id & 1) == 1 ? u(arc) : v(arc);
     214      int k = (arc._id >> _dim) + 1;
     215      if (k < _dim) {
     216        arc._id = (k << _dim-1) |
     217                  ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
     218        arc._id = (arc._id << 1) | (~(n._id >> k) & 1);
     219      } else {
     220        arc._id = -1;
     221      }
    131222    }
    132223
    133224    void firstIn(Arc& arc, const Node& node) const {
    134       arc.id = (node.id ^ 1) * _dim;
     225      arc._id = ((node._id >> 1) << 1) | (node._id & 1);
    135226    }
    136227
    137228    void nextIn(Arc& arc) const {
    138       int cnt = arc.id % _dim;
    139       if ((cnt + 1) % _dim == 0) {
    140         arc.id = -1;
     229      Node n = (arc._id & 1) == 1 ? v(arc) : u(arc);
     230      int k = (arc._id >> _dim) + 1;
     231      if (k < _dim) {
     232        arc._id = (k << _dim-1) |
     233                  ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
     234        arc._id = (arc._id << 1) | ((n._id >> k) & 1);
    141235      } else {
    142         arc.id = ((arc.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1;
     236        arc._id = -1;
    143237      }
     238    }
     239
     240    static bool direction(Arc arc) {
     241      return (arc._id & 1) == 1;
     242    }
     243
     244    static Arc direct(Edge edge, bool dir) {
     245      return Arc((edge._id << 1) | (dir ? 1 : 0));
    144246    }
    145247
     
    149251
    150252    bool projection(Node node, int n) const {
    151       return static_cast<bool>(node.id & (1 << n));
     253      return static_cast<bool>(node._id & (1 << n));
     254    }
     255
     256    int dimension(Edge edge) const {
     257      return edge._id >> _dim-1;
    152258    }
    153259
    154260    int dimension(Arc arc) const {
    155       return arc.id % _dim;
     261      return arc._id >> _dim;
    156262    }
    157263
    158264    int index(Node node) const {
    159       return node.id;
     265      return node._id;
    160266    }
    161267
     
    165271
    166272  private:
    167     int _dim, _nodeNum;
     273    int _dim;
     274    int _node_num, _edge_num;
    168275  };
    169276
    170277
    171   typedef DigraphExtender<HypercubeDigraphBase> ExtendedHypercubeDigraphBase;
    172 
    173   /// \ingroup digraphs
     278  typedef GraphExtender<HypercubeGraphBase> ExtendedHypercubeGraphBase;
     279
     280  /// \ingroup graphs
    174281  ///
    175   /// \brief Hypercube digraph class
     282  /// \brief Hypercube graph class
    176283  ///
    177   /// This class implements a special digraph type. The nodes of the
    178   /// digraph are indiced with integers with at most \c dim binary digits.
    179   /// Two nodes are connected in the digraph if the indices differ only
    180   /// on one position in the binary form.
     284  /// This class implements a special graph type. The nodes of the graph
     285  /// are indiced with integers with at most \c dim binary digits.
     286  /// Two nodes are connected in the graph if and only if their indices
     287  /// differ only on one position in the binary form.
    181288  ///
    182   /// \note The type of the \c ids is chosen to \c int because efficiency
    183   /// reasons. Thus the maximum dimension of this implementation is 26.
     289  /// \note The type of the indices is chosen to \c int for efficiency
     290  /// reasons. Thus the maximum dimension of this implementation is 26
     291  /// (assuming that the size of \c int is 32 bit).
    184292  ///
    185   /// The digraph type is fully conform to the \ref concepts::Digraph
    186   /// concept but it does not conform to \ref concepts::Graph.
    187   class HypercubeDigraph : public ExtendedHypercubeDigraphBase {
     293  /// This graph type is fully conform to the \ref concepts::Graph
     294  /// "Graph" concept, and it also has an important extra feature
     295  /// that its maps are real \ref concepts::ReferenceMap
     296  /// "reference map"s.
     297  class HypercubeGraph : public ExtendedHypercubeGraphBase {
    188298  public:
    189299
    190     typedef ExtendedHypercubeDigraphBase Parent;
    191 
    192     /// \brief Construct a hypercube digraph with \c dim dimension.
    193     ///
    194     /// Construct a hypercube digraph with \c dim dimension.
    195     HypercubeDigraph(int dim) { construct(dim); }
    196 
    197     /// \brief Gives back the number of the dimensions.
    198     ///
    199     /// Gives back the number of the dimensions.
     300    typedef ExtendedHypercubeGraphBase Parent;
     301
     302    /// \brief Constructs a hypercube graph with \c dim dimensions.
     303    ///
     304    /// Constructs a hypercube graph with \c dim dimensions.
     305    HypercubeGraph(int dim) { construct(dim); }
     306
     307    /// \brief The number of dimensions.
     308    ///
     309    /// Gives back the number of dimensions.
    200310    int dimension() const {
    201311      return Parent::dimension();
    202312    }
    203313
    204     /// \brief Returns true if the n'th bit of the node is one.
    205     ///
    206     /// Returns true if the n'th bit of the node is one.
     314    /// \brief Returns \c true if the n'th bit of the node is one.
     315    ///
     316    /// Returns \c true if the n'th bit of the node is one.
    207317    bool projection(Node node, int n) const {
    208318      return Parent::projection(node, n);
    209319    }
    210320
    211     /// \brief The dimension id of the arc.
    212     ///
    213     /// It returns the dimension id of the arc. It can
    214     /// be in the \f$ \{0, 1, \dots, dim-1\} \f$ interval.
     321    /// \brief The dimension id of an edge.
     322    ///
     323    /// Gives back the dimension id of the given edge.
     324    /// It is in the [0..dim-1] range.
     325    int dimension(Edge edge) const {
     326      return Parent::dimension(edge);
     327    }
     328
     329    /// \brief The dimension id of an arc.
     330    ///
     331    /// Gives back the dimension id of the given arc.
     332    /// It is in the [0..dim-1] range.
    215333    int dimension(Arc arc) const {
    216334      return Parent::dimension(arc);
    217335    }
    218336
    219     /// \brief Gives back the index of the node.
    220     ///
    221     /// Gives back the index of the node. The lower bits of the
    222     /// integer describes the node.
     337    /// \brief The index of a node.
     338    ///
     339    /// Gives back the index of the given node.
     340    /// The lower bits of the integer describes the node.
    223341    int index(Node node) const {
    224342      return Parent::index(node);
    225343    }
    226344
    227     /// \brief Gives back the node by its index.
    228     ///
    229     /// Gives back the node by its index.
     345    /// \brief Gives back a node by its index.
     346    ///
     347    /// Gives back a node by its index.
    230348    Node operator()(int ix) const {
    231349      return Parent::operator()(ix);
     
    234352    /// \brief Number of nodes.
    235353    int nodeNum() const { return Parent::nodeNum(); }
     354    /// \brief Number of edges.
     355    int edgeNum() const { return Parent::edgeNum(); }
    236356    /// \brief Number of arcs.
    237357    int arcNum() const { return Parent::arcNum(); }
     
    239359    /// \brief Linear combination map.
    240360    ///
    241     /// It makes possible to give back a linear combination
    242     /// for each node. This function works like the \c std::accumulate
    243     /// so it accumulates the \c bf binary function with the \c fv
    244     /// first value. The map accumulates only on that dimensions where
    245     /// the node's index is one. The accumulated values should be
    246     /// given by the \c begin and \c end iterators and the length of this
    247     /// range should be equal to the dimension number of the digraph.
     361    /// This map makes possible to give back a linear combination
     362    /// for each node. It works like the \c std::accumulate function,
     363    /// so it accumulates the \c bf binary function with the \c fv first
     364    /// value. The map accumulates only on that positions (dimensions)
     365    /// where the index of the node is one. The values that have to be
     366    /// accumulated should be given by the \c begin and \c end iterators
     367    /// and the length of this range should be equal to the dimension
     368    /// number of the graph.
    248369    ///
    249370    ///\code
    250371    /// const int DIM = 3;
    251     /// HypercubeDigraph digraph(DIM);
     372    /// HypercubeGraph graph(DIM);
    252373    /// dim2::Point<double> base[DIM];
    253374    /// for (int k = 0; k < DIM; ++k) {
     
    255376    ///   base[k].y = rnd();
    256377    /// }
    257     /// HypercubeDigraph::HyperMap<dim2::Point<double> >
    258     ///   pos(digraph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
     378    /// HypercubeGraph::HyperMap<dim2::Point<double> >
     379    ///   pos(graph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
    259380    ///\endcode
    260381    ///
    261     /// \see HypercubeDigraph
     382    /// \see HypercubeGraph
    262383    template <typename T, typename BF = std::plus<T> >
    263384    class HyperMap {
    264385    public:
    265386
     387      /// \brief The key type of the map
    266388      typedef Node Key;
     389      /// \brief The value type of the map
    267390      typedef T Value;
    268 
    269391
    270392      /// \brief Constructor for HyperMap.
    271393      ///
    272       /// Construct a HyperMap for the given digraph. The accumulated values
    273       /// should be given by the \c begin and \c end iterators and the length
    274       /// of this range should be equal to the dimension number of the digraph.
     394      /// Construct a HyperMap for the given graph. The values that have
     395      /// to be accumulated should be given by the \c begin and \c end
     396      /// iterators and the length of this range should be equal to the
     397      /// dimension number of the graph.
    275398      ///
    276       /// This function accumulates the \c bf binary function with
    277       /// the \c fv first value. The map accumulates only on that dimensions
    278       /// where the node's index is one.
     399      /// This map accumulates the \c bf binary function with the \c fv
     400      /// first value on that positions (dimensions) where the index of
     401      /// the node is one.
    279402      template <typename It>
    280       HyperMap(const Digraph& digraph, It begin, It end,
    281                T fv = 0.0, const BF& bf = BF())
    282         : _graph(digraph), _values(begin, end), _first_value(fv), _bin_func(bf)
     403      HyperMap(const Graph& graph, It begin, It end,
     404               T fv = 0, const BF& bf = BF())
     405        : _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf)
    283406      {
    284         LEMON_ASSERT(_values.size() == digraph.dimension(),
    285                      "Wrong size of dimension");
     407        LEMON_ASSERT(_values.size() == graph.dimension(),
     408                     "Wrong size of range");
    286409      }
    287410
    288       /// \brief Gives back the partial accumulated value.
     411      /// \brief The partial accumulated value.
    289412      ///
    290413      /// Gives back the partial accumulated value.
    291       Value operator[](Key k) const {
     414      Value operator[](const Key& k) const {
    292415        Value val = _first_value;
    293416        int id = _graph.index(k);
     
    304427
    305428    private:
    306       const Digraph& _graph;
     429      const Graph& _graph;
    307430      std::vector<T> _values;
    308431      T _first_value;
Note: See TracChangeset for help on using the changeset viewer.