COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/full_graph.h @ 353:37557a46e298

Last change on this file since 353:37557a46e298 was 353:37557a46e298, checked in by Balazs Dezso <deba@…>, 11 years ago

Porting full graphs from svn 3498

  • the FullGraph? is redesigned in implementation
  • some improvemnts in documentation
File size: 15.9 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_FULL_GRAPH_H
20#define LEMON_FULL_GRAPH_H
21
22#include <lemon/math.h>
23
24#include <lemon/core.h>
25#include <lemon/bits/graph_extender.h>
26
27///\ingroup graphs
28///\file
29///\brief FullDigraph and FullGraph classes.
30namespace lemon {
31
32  class FullDigraphBase {
33  public:
34
35    typedef FullDigraphBase Graph;
36
37    class Node;
38    class Arc;
39
40  protected:
41
42    int _node_num;
43    int _arc_num;
44
45    FullDigraphBase() {}
46
47    void construct(int n) { _node_num = n; _arc_num = n * n; }
48
49  public:
50
51    typedef True NodeNumTag;
52    typedef True ArcNumTag;
53
54    Node operator()(int ix) const { return Node(ix); }
55    int index(const Node& node) const { return node._id; }
56
57    Arc arc(const Node& s, const Node& t) const {
58      return Arc(s._id * _node_num + t._id);
59    }
60
61    int nodeNum() const { return _node_num; }
62    int arcNum() const { return _arc_num; }
63
64    int maxNodeId() const { return _node_num - 1; }
65    int maxArcId() const { return _arc_num - 1; }
66
67    Node source(Arc arc) const { return arc._id / _node_num; }
68    Node target(Arc arc) const { return arc._id % _node_num; }
69
70
71    static int id(Node node) { return node._id; }
72    static int id(Arc arc) { return arc._id; }
73
74    static Node nodeFromId(int id) { return Node(id);}
75
76    static Arc arcFromId(int id) { return Arc(id);}
77
78    typedef True FindArcTag;
79
80    Arc findArc(Node s, Node t, Arc prev = INVALID) const {
81      return prev != INVALID ? arc(s, t) : INVALID;
82    }
83
84
85    class Node {
86      friend class FullDigraphBase;
87
88    protected:
89      int _id;
90      Node(int id) : _id(id) {}
91    public:
92      Node() {}
93      Node (Invalid) : _id(-1) {}
94      bool operator==(const Node node) const {return _id == node._id;}
95      bool operator!=(const Node node) const {return _id != node._id;}
96      bool operator<(const Node node) const {return _id < node._id;}
97    };
98
99    class Arc {
100      friend class FullDigraphBase;
101
102    protected:
103      int _id;  // _node_num * source + target;
104
105      Arc(int id) : _id(id) {}
106
107    public:
108      Arc() { }
109      Arc (Invalid) { _id = -1; }
110      bool operator==(const Arc arc) const {return _id == arc._id;}
111      bool operator!=(const Arc arc) const {return _id != arc._id;}
112      bool operator<(const Arc arc) const {return _id < arc._id;}
113    };
114
115    void first(Node& node) const {
116      node._id = _node_num - 1;
117    }
118
119    static void next(Node& node) {
120      --node._id;
121    }
122
123    void first(Arc& arc) const {
124      arc._id = _arc_num - 1;
125    }
126
127    static void next(Arc& arc) {
128      --arc._id;
129    }
130
131    void firstOut(Arc& arc, const Node& node) const {
132      arc._id = (node._id + 1) * _node_num - 1;
133    }
134
135    void nextOut(Arc& arc) const {
136      if (arc._id % _node_num == 0) arc._id = 0;
137      --arc._id;
138    }
139
140    void firstIn(Arc& arc, const Node& node) const {
141      arc._id = _arc_num + node._id - _node_num;
142    }
143
144    void nextIn(Arc& arc) const {
145      arc._id -= _node_num;
146      if (arc._id < 0) arc._id = -1;
147    }
148
149  };
150
151  typedef DigraphExtender<FullDigraphBase> ExtendedFullDigraphBase;
152
153  /// \ingroup graphs
154  ///
155  /// \brief A full digraph class.
156  ///
157  /// This is a simple and fast directed full graph implementation.
158  /// From each node go arcs to each node (including the source node),
159  /// therefore the number of the arcs in the digraph is the square of
160  /// the node number. The digraph is completely static, so you can
161  /// neither add nor delete either arcs or nodes, and it needs just
162  /// constant space in memory.
163  ///
164  /// Thus it conforms to the \ref concepts::Digraph "Digraph" concept
165  /// and it also has an important extra feature that its maps are
166  /// real \ref concepts::ReferenceMap "reference map"s.
167  /// \sa concepts::Digraph.
168  ///
169  /// \sa FullGraph
170  class FullDigraph : public ExtendedFullDigraphBase {
171  public:
172
173    typedef ExtendedFullDigraphBase Parent;
174
175    /// \brief Constructor
176    FullDigraph() { construct(0); }
177
178    /// \brief Constructor
179    ///
180    /// \param n The number of the nodes.
181    FullDigraph(int n) { construct(n); }
182
183    /// \brief Resize the digraph
184    ///
185    /// Resize the digraph. The function will fully destroy and
186    /// rebuild the digraph.  This cause that the maps of the digraph
187    /// will reallocated automatically and the previous values will be
188    /// lost.
189    void resize(int n) {
190      Parent::notifier(Arc()).clear();
191      Parent::notifier(Node()).clear();
192      construct(n);
193      Parent::notifier(Node()).build();
194      Parent::notifier(Arc()).build();
195    }
196
197    /// \brief Returns the node with the given index.
198    ///
199    /// Returns the node with the given index. Because it is a
200    /// static size digraph the node's of the digraph can be indexed
201    /// in the range <tt>[0..nodeNum()-1]</tt> and the index of
202    /// the node can accessed by the \e index() member.
203    Node operator()(int ix) const { return Parent::operator()(ix); }
204
205    /// \brief Returns the index of the node.
206    ///
207    /// Returns the index of the node. Because it is a
208    /// static size digraph the node's of the digraph can be indexed
209    /// in the range <tt>[0..nodeNum()-1]</tt> and the index of
210    /// the node can accessed by the \e index() member.
211    int index(const Node& node) const { return Parent::index(node); }
212
213    /// \brief Returns the arc connects the given nodes.
214    ///
215    /// Returns the arc connects the given nodes.
216    Arc arc(const Node& u, const Node& v) const {
217      return Parent::arc(u, v);
218    }
219
220    /// \brief Number of nodes.
221    int nodeNum() const { return Parent::nodeNum(); }
222    /// \brief Number of arcs.
223    int arcNum() const { return Parent::arcNum(); }
224  };
225
226
227  class FullGraphBase {
228    int _node_num;
229    int _edge_num;
230  public:
231
232    typedef FullGraphBase Graph;
233
234    class Node;
235    class Arc;
236    class Edge;
237
238  protected:
239
240    FullGraphBase() {}
241
242    void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }
243
244    int _uid(int e) const {
245      int u = e / _node_num;
246      int v = e % _node_num;
247      return u < v ? u : _node_num - 2 - u;
248    }
249
250    int _vid(int e) const {
251      int u = e / _node_num;
252      int v = e % _node_num;
253      return u < v ? v : _node_num - 1 - v;
254    }
255
256    void _uvid(int e, int& u, int& v) const {
257      u = e / _node_num;
258      v = e % _node_num;
259      if  (u >= v) {
260        u = _node_num - 2 - u;
261        v = _node_num - 1 - v;
262      }
263    }
264
265    void _stid(int a, int& s, int& t) const {
266      if ((a & 1) == 1) {
267        _uvid(a >> 1, s, t);
268      } else {
269        _uvid(a >> 1, t, s);
270      }
271    }
272
273    int _eid(int u, int v) const {
274      if (u < (_node_num - 1) / 2) {
275        return u * _node_num + v;
276      } else {
277        return (_node_num - 1 - u) * _node_num - v - 1;
278      }
279    }
280
281  public:
282
283
284    Node operator()(int ix) const { return Node(ix); }
285    int index(const Node& node) const { return node._id; }
286
287    Edge edge(const Node& u, const Node& v) const {
288      if (u._id < v._id) {
289        return Edge(_eid(u._id, v._id));
290      } else if (u._id != v._id) {
291        return Edge(_eid(v._id, u._id));
292      } else {
293        return INVALID;
294      }
295    }
296
297    Arc arc(const Node& s, const Node& t) const {
298      if (s._id < t._id) {
299        return Arc((_eid(s._id, t._id) << 1) | 1);
300      } else if (s._id != t._id) {
301        return Arc(_eid(t._id, s._id) << 1);
302      } else {
303        return INVALID;
304      }
305    }
306
307    typedef True NodeNumTag;
308    typedef True EdgeNumTag;
309
310    int nodeNum() const { return _node_num; }
311    int arcNum() const { return 2 * _edge_num; }
312    int edgeNum() const { return _edge_num; }
313
314    static int id(Node node) { return node._id; }
315    static int id(Arc arc) { return arc._id; }
316    static int id(Edge edge) { return edge._id; }
317
318    int maxNodeId() const { return _node_num-1; }
319    int maxArcId() const { return 2 * _edge_num-1; }
320    int maxEdgeId() const { return _edge_num-1; }
321
322    static Node nodeFromId(int id) { return Node(id);}
323    static Arc arcFromId(int id) { return Arc(id);}
324    static Edge edgeFromId(int id) { return Edge(id);}
325
326    Node u(Edge edge) const {
327      return Node(_uid(edge._id));
328    }
329
330    Node v(Edge edge) const {
331      return Node(_vid(edge._id));
332    }
333
334    Node source(Arc arc) const {
335      return Node((arc._id & 1) == 1 ?
336                  _uid(arc._id >> 1) : _vid(arc._id >> 1));
337    }
338
339    Node target(Arc arc) const {
340      return Node((arc._id & 1) == 1 ?
341                  _vid(arc._id >> 1) : _uid(arc._id >> 1));
342    }
343
344    typedef True FindEdgeTag;
345
346    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
347      return prev != INVALID ? INVALID : edge(u, v);
348    }
349
350    Arc findArc(Node s, Node t, Arc prev = INVALID) const {
351      return prev != INVALID ? INVALID : arc(s, t);
352    }
353
354    class Node {
355      friend class FullGraphBase;
356
357    protected:
358      int _id;
359      Node(int id) : _id(id) {}
360    public:
361      Node() {}
362      Node (Invalid) { _id = -1; }
363      bool operator==(const Node node) const {return _id == node._id;}
364      bool operator!=(const Node node) const {return _id != node._id;}
365      bool operator<(const Node node) const {return _id < node._id;}
366    };
367
368    class Edge {
369      friend class FullGraphBase;
370
371    protected:
372      int _id;
373
374      Edge(int id) : _id(id) {}
375
376    public:
377      Edge() { }
378      Edge (Invalid) { _id = -1; }
379
380      bool operator==(const Edge edge) const {return _id == edge._id;}
381      bool operator!=(const Edge edge) const {return _id != edge._id;}
382      bool operator<(const Edge edge) const {return _id < edge._id;}
383    };
384
385    class Arc {
386      friend class FullGraphBase;
387
388    protected:
389      int _id;
390
391      Arc(int id) : _id(id) {}
392
393    public:
394      Arc() { }
395      Arc (Invalid) { _id = -1; }
396
397      operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }
398
399      bool operator==(const Arc arc) const {return _id == arc._id;}
400      bool operator!=(const Arc arc) const {return _id != arc._id;}
401      bool operator<(const Arc arc) const {return _id < arc._id;}
402    };
403
404    static bool direction(Arc arc) {
405      return (arc._id & 1) == 1;
406    }
407
408    static Arc direct(Edge edge, bool dir) {
409      return Arc((edge._id << 1) | (dir ? 1 : 0));
410    }
411
412    void first(Node& node) const {
413      node._id = _node_num - 1;
414    }
415
416    static void next(Node& node) {
417      --node._id;
418    }
419
420    void first(Arc& arc) const {
421      arc._id = (_edge_num << 1) - 1;
422    }
423
424    static void next(Arc& arc) {
425      --arc._id;
426    }
427
428    void first(Edge& edge) const {
429      edge._id = _edge_num - 1;
430    }
431
432    static void next(Edge& edge) {
433      --edge._id;
434    }
435
436    void firstOut(Arc& arc, const Node& node) const {
437      int s = node._id, t = _node_num - 1;
438      if (s < t) {
439        arc._id = (_eid(s, t) << 1) | 1;
440      } else {
441        --t;
442        arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
443      }
444    }
445
446    void nextOut(Arc& arc) const {
447      int s, t;
448      _stid(arc._id, s, t);
449      --t;
450      if (s < t) {
451        arc._id = (_eid(s, t) << 1) | 1;
452      } else {
453        if (s == t) --t;
454        arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
455      }
456    }
457
458    void firstIn(Arc& arc, const Node& node) const {
459      int s = _node_num - 1, t = node._id;
460      if (s > t) {
461        arc._id = (_eid(t, s) << 1);
462      } else {
463        --s;
464        arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
465      }
466    }
467
468    void nextIn(Arc& arc) const {
469      int s, t;
470      _stid(arc._id, s, t);
471      --s;
472      if (s > t) {
473        arc._id = (_eid(t, s) << 1);
474      } else {
475        if (s == t) --s;
476        arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
477      }
478    }
479
480    void firstInc(Edge& edge, bool& dir, const Node& node) const {
481      int u = node._id, v = _node_num - 1;
482      if (u < v) {
483        edge._id = _eid(u, v);
484        dir = true;
485      } else {
486        --v;
487        edge._id = (v != -1 ? _eid(v, u) : -1);
488        dir = false;
489      }
490    }
491
492    void nextInc(Edge& edge, bool& dir) const {
493      int u, v;
494      if (dir) {
495        _uvid(edge._id, u, v);
496        --v;
497        if (u < v) {
498          edge._id = _eid(u, v);
499        } else {
500          --v;
501          edge._id = (v != -1 ? _eid(v, u) : -1);
502          dir = false;
503        }
504      } else {
505        _uvid(edge._id, v, u);
506        --v;
507        edge._id = (v != -1 ? _eid(v, u) : -1);
508      }
509    }
510
511  };
512
513  typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
514
515  /// \ingroup graphs
516  ///
517  /// \brief An undirected full graph class.
518  ///
519  /// This is a simple and fast undirected full graph
520  /// implementation. From each node go edge to each other node,
521  /// therefore the number of edges in the graph is
522  /// <tt>n(n-1)/2</tt>. It is completely static, so you can neither
523  /// add nor delete either edges or nodes, and it needs just constant
524  /// space in memory.
525  ///
526  /// The \e FullDigraph and \e FullGraph classes are very similar,
527  /// but there are two differences. While the \e FullDigraph class is
528  /// conform just to the \ref concepts::Digraph "Digraph" concept,
529  /// this class is conform to the \ref concepts::Graph "Graph"
530  /// concept. In addition, the \e FullGraph class does not contain a
531  /// loop arc from each node as the \e FullDigraph does.
532  ///
533  /// It also has an important extra feature that its maps are real
534  /// \ref concepts::ReferenceMap "reference map"s.
535  ///
536  /// \sa FullDigraph
537  class FullGraph : public ExtendedFullGraphBase {
538  public:
539
540    typedef ExtendedFullGraphBase Parent;
541
542    /// \brief Constructor
543    FullGraph() { construct(0); }
544
545    /// \brief Constructor
546    ///
547    /// \param n The number of the nodes.
548    FullGraph(int n) { construct(n); }
549
550    /// \brief Resize the graph
551    ///
552    /// Resize the graph. The function will fully destroy and rebuild
553    /// the graph.  This cause that the maps of the graph will
554    /// reallocated automatically and the previous values will be
555    /// lost.
556    void resize(int n) {
557      Parent::notifier(Arc()).clear();
558      Parent::notifier(Edge()).clear();
559      Parent::notifier(Node()).clear();
560      construct(n);
561      Parent::notifier(Node()).build();
562      Parent::notifier(Edge()).build();
563      Parent::notifier(Arc()).build();
564    }
565
566    /// \brief Returns the node with the given index.
567    ///
568    /// Returns the node with the given index. Because it is a static
569    /// size graph the node's of the graph can be indexed in the range
570    /// <tt>[0..nodeNum()-1]</tt> and the index of the node can
571    /// accessed by the \e index() member.
572    Node operator()(int ix) const { return Parent::operator()(ix); }
573
574    /// \brief Returns the index of the node.
575    ///
576    /// Returns the index of the node. Because it is a static size
577    /// graph the node's of the graph can be indexed in the range
578    /// <tt>[0..nodeNum()-1]</tt> and the index of the node can
579    /// accessed by the \e index() member.
580    int index(const Node& node) const { return Parent::index(node); }
581
582    /// \brief Number of nodes.
583    int nodeNum() const { return Parent::nodeNum(); }
584    /// \brief Number of arcs.
585    int arcNum() const { return Parent::arcNum(); }
586    /// \brief Number of edges.
587    int edgeNum() const { return Parent::edgeNum(); }
588
589    /// \brief Returns the arc connects the given nodes.
590    ///
591    /// Returns the arc connects the given nodes.
592    Arc arc(const Node& s, const Node& t) const {
593      return Parent::arc(s, t);
594    }
595
596    /// \brief Returns the edge connects the given nodes.
597    ///
598    /// Returns the edge connects the given nodes.
599    Edge edge(const Node& u, const Node& v) const {
600      return Parent::edge(u, v);
601    }
602  };
603
604
605} //namespace lemon
606
607
608#endif //LEMON_FULL_GRAPH_H
Note: See TracBrowser for help on using the repository browser.