COIN-OR::LEMON - Graph Library

source: lemon/lemon/full_graph.h @ 782:853fcddcf282

Last change on this file since 782:853fcddcf282 was 782:853fcddcf282, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Doc improvements, fixes and unifications for graphs (#311)

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