lemon/hypercube_graph.h
changeset 402 235be9d4b6ab
parent 365 a12eef1f82b2
child 440 88ed40ad0d4f
equal deleted inserted replaced
1:4b3b4402ce99 2:1ee0cd860b8b
    48 
    48 
    49     void construct(int dim) {
    49     void construct(int dim) {
    50       LEMON_ASSERT(dim >= 1, "The number of dimensions must be at least 1.");
    50       LEMON_ASSERT(dim >= 1, "The number of dimensions must be at least 1.");
    51       _dim = dim;
    51       _dim = dim;
    52       _node_num = 1 << dim;
    52       _node_num = 1 << dim;
    53       _edge_num = dim * (1 << dim-1);
    53       _edge_num = dim * (1 << (dim-1));
    54     }
    54     }
    55 
    55 
    56   public:
    56   public:
    57 
    57 
    58     typedef True NodeNumTag;
    58     typedef True NodeNumTag;
    74     static int id(Node node) { return node._id; }
    74     static int id(Node node) { return node._id; }
    75     static int id(Edge edge) { return edge._id; }
    75     static int id(Edge edge) { return edge._id; }
    76     static int id(Arc arc) { return arc._id; }
    76     static int id(Arc arc) { return arc._id; }
    77 
    77 
    78     Node u(Edge edge) const {
    78     Node u(Edge edge) const {
    79       int base = edge._id & ((1 << _dim-1) - 1);
    79       int base = edge._id & ((1 << (_dim-1)) - 1);
    80       int k = edge._id >> _dim-1;
    80       int k = edge._id >> (_dim-1);
    81       return ((base >> k) << k+1) | (base & ((1 << k) - 1));
    81       return ((base >> k) << (k+1)) | (base & ((1 << k) - 1));
    82     }
    82     }
    83 
    83 
    84     Node v(Edge edge) const {
    84     Node v(Edge edge) const {
    85       int base = edge._id & ((1 << _dim-1) - 1);
    85       int base = edge._id & ((1 << (_dim-1)) - 1);
    86       int k = edge._id >> _dim-1;
    86       int k = edge._id >> (_dim-1);
    87       return ((base >> k) << k+1) | (base & ((1 << k) - 1)) | (1 << k);
    87       return ((base >> k) << (k+1)) | (base & ((1 << k) - 1)) | (1 << k);
    88     }
    88     }
    89 
    89 
    90     Node source(Arc arc) const {
    90     Node source(Arc arc) const {
    91       return (arc._id & 1) == 1 ? u(arc) : v(arc);
    91       return (arc._id & 1) == 1 ? u(arc) : v(arc);
    92     }
    92     }
   103       int d = u._id ^ v._id;
   103       int d = u._id ^ v._id;
   104       int k = 0;
   104       int k = 0;
   105       if (d == 0) return INVALID;
   105       if (d == 0) return INVALID;
   106       for ( ; (d & 1) == 0; d >>= 1) ++k;
   106       for ( ; (d & 1) == 0; d >>= 1) ++k;
   107       if (d >> 1 != 0) return INVALID;
   107       if (d >> 1 != 0) return INVALID;
   108       return (k << _dim-1) | ((u._id >> k+1) << k) | (u._id & ((1 << k) - 1));
   108       return (k << (_dim-1)) | ((u._id >> (k+1)) << k) |
       
   109         (u._id & ((1 << k) - 1));
   109     }
   110     }
   110 
   111 
   111     Arc findArc(Node u, Node v, Arc prev = INVALID) const {
   112     Arc findArc(Node u, Node v, Arc prev = INVALID) const {
   112       Edge edge = findEdge(u, v, prev);
   113       Edge edge = findEdge(u, v, prev);
   113       if (edge == INVALID) return INVALID;
   114       if (edge == INVALID) return INVALID;
   114       int k = edge._id >> _dim-1;
   115       int k = edge._id >> (_dim-1);
   115       return ((u._id >> k) & 1) == 1 ? edge._id << 1 : (edge._id << 1) | 1;
   116       return ((u._id >> k) & 1) == 1 ? edge._id << 1 : (edge._id << 1) | 1;
   116     }
   117     }
   117 
   118 
   118     class Node {
   119     class Node {
   119       friend class HypercubeGraphBase;
   120       friend class HypercubeGraphBase;
   192       dir = (node._id & 1) == 0;
   193       dir = (node._id & 1) == 0;
   193     }
   194     }
   194 
   195 
   195     void nextInc(Edge& edge, bool& dir) const {
   196     void nextInc(Edge& edge, bool& dir) const {
   196       Node n = dir ? u(edge) : v(edge);
   197       Node n = dir ? u(edge) : v(edge);
   197       int k = (edge._id >> _dim-1) + 1;
   198       int k = (edge._id >> (_dim-1)) + 1;
   198       if (k < _dim) {
   199       if (k < _dim) {
   199         edge._id = (k << _dim-1) |
   200         edge._id = (k << (_dim-1)) |
   200                    ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
   201           ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
   201         dir = ((n._id >> k) & 1) == 0;
   202         dir = ((n._id >> k) & 1) == 0;
   202       } else {
   203       } else {
   203         edge._id = -1;
   204         edge._id = -1;
   204         dir = true;
   205         dir = true;
   205       }
   206       }
   211 
   212 
   212     void nextOut(Arc& arc) const {
   213     void nextOut(Arc& arc) const {
   213       Node n = (arc._id & 1) == 1 ? u(arc) : v(arc);
   214       Node n = (arc._id & 1) == 1 ? u(arc) : v(arc);
   214       int k = (arc._id >> _dim) + 1;
   215       int k = (arc._id >> _dim) + 1;
   215       if (k < _dim) {
   216       if (k < _dim) {
   216         arc._id = (k << _dim-1) |
   217         arc._id = (k << (_dim-1)) |
   217                   ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
   218           ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
   218         arc._id = (arc._id << 1) | (~(n._id >> k) & 1);
   219         arc._id = (arc._id << 1) | (~(n._id >> k) & 1);
   219       } else {
   220       } else {
   220         arc._id = -1;
   221         arc._id = -1;
   221       }
   222       }
   222     }
   223     }
   227 
   228 
   228     void nextIn(Arc& arc) const {
   229     void nextIn(Arc& arc) const {
   229       Node n = (arc._id & 1) == 1 ? v(arc) : u(arc);
   230       Node n = (arc._id & 1) == 1 ? v(arc) : u(arc);
   230       int k = (arc._id >> _dim) + 1;
   231       int k = (arc._id >> _dim) + 1;
   231       if (k < _dim) {
   232       if (k < _dim) {
   232         arc._id = (k << _dim-1) |
   233         arc._id = (k << (_dim-1)) |
   233                   ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
   234           ((n._id >> (k+1)) << k) | (n._id & ((1 << k) - 1));
   234         arc._id = (arc._id << 1) | ((n._id >> k) & 1);
   235         arc._id = (arc._id << 1) | ((n._id >> k) & 1);
   235       } else {
   236       } else {
   236         arc._id = -1;
   237         arc._id = -1;
   237       }
   238       }
   238     }
   239     }
   252     bool projection(Node node, int n) const {
   253     bool projection(Node node, int n) const {
   253       return static_cast<bool>(node._id & (1 << n));
   254       return static_cast<bool>(node._id & (1 << n));
   254     }
   255     }
   255 
   256 
   256     int dimension(Edge edge) const {
   257     int dimension(Edge edge) const {
   257       return edge._id >> _dim-1;
   258       return edge._id >> (_dim-1);
   258     }
   259     }
   259 
   260 
   260     int dimension(Arc arc) const {
   261     int dimension(Arc arc) const {
   261       return arc._id >> _dim;
   262       return arc._id >> _dim;
   262     }
   263     }