COIN-OR::LEMON - Graph Library

source: lemon/lemon/full_graph.h @ 629:7a28e215f715

Last change on this file since 629:7a28e215f715 was 629:7a28e215f715, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Remove notes about reference maps as extra features (#190)

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-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 FullGraph and FullDigraph classes.
28
29namespace lemon {
30
31  class FullDigraphBase {
32  public:
33
34    typedef FullDigraphBase Graph;
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 full digraph class.
152  ///
153  /// This is a simple and fast directed full graph implementation.
154  /// From each node go arcs to each node (including the source node),
155  /// therefore the number of the arcs in the digraph is the square of
156  /// the node number. This digraph type is completely static, so you
157  /// can neither add nor delete either arcs or nodes, and it needs
158  /// constant space in memory.
159  ///
160  /// This class fully conforms to the \ref concepts::Digraph
161  /// "Digraph concept".
162  ///
163  /// The \c FullDigraph and \c FullGraph classes are very similar,
164  /// but there are two differences. While this class conforms only
165  /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
166  /// class conforms to the \ref concepts::Graph "Graph" concept,
167  /// moreover \c FullGraph does not contain a loop arc for each
168  /// node as \c FullDigraph does.
169  ///
170  /// \sa FullGraph
171  class FullDigraph : public ExtendedFullDigraphBase {
172  public:
173
174    typedef ExtendedFullDigraphBase Parent;
175
176    /// \brief Constructor
177    FullDigraph() { construct(0); }
178
179    /// \brief Constructor
180    ///
181    /// Constructor.
182    /// \param n The number of the nodes.
183    FullDigraph(int n) { construct(n); }
184
185    /// \brief Resizes the digraph
186    ///
187    /// Resizes the digraph. The function will fully destroy and
188    /// rebuild the digraph. This cause that the maps of the digraph will
189    /// reallocated automatically and the previous values will be lost.
190    void resize(int n) {
191      Parent::notifier(Arc()).clear();
192      Parent::notifier(Node()).clear();
193      construct(n);
194      Parent::notifier(Node()).build();
195      Parent::notifier(Arc()).build();
196    }
197
198    /// \brief Returns the node with the given index.
199    ///
200    /// Returns the node with the given index. Since it is a static
201    /// digraph its nodes can be indexed with integers from the range
202    /// <tt>[0..nodeNum()-1]</tt>.
203    /// \sa index()
204    Node operator()(int ix) const { return Parent::operator()(ix); }
205
206    /// \brief Returns the index of the given node.
207    ///
208    /// Returns the index of the given node. Since it is a static
209    /// digraph its nodes can be indexed with integers from the range
210    /// <tt>[0..nodeNum()-1]</tt>.
211    /// \sa operator()
212    int index(const Node& node) const { return Parent::index(node); }
213
214    /// \brief Returns the arc connecting the given nodes.
215    ///
216    /// Returns the arc connecting the given nodes.
217    Arc arc(const Node& u, const Node& v) const {
218      return Parent::arc(u, v);
219    }
220
221    /// \brief Number of nodes.
222    int nodeNum() const { return Parent::nodeNum(); }
223    /// \brief Number of arcs.
224    int arcNum() const { return Parent::arcNum(); }
225  };
226
227
228  class FullGraphBase {
229    int _node_num;
230    int _edge_num;
231  public:
232
233    typedef FullGraphBase Graph;
234
235    class Node;
236    class Arc;
237    class Edge;
238
239  protected:
240
241    FullGraphBase() {}
242
243    void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }
244
245    int _uid(int e) const {
246      int u = e / _node_num;
247      int v = e % _node_num;
248      return u < v ? u : _node_num - 2 - u;
249    }
250
251    int _vid(int e) const {
252      int u = e / _node_num;
253      int v = e % _node_num;
254      return u < v ? v : _node_num - 1 - v;
255    }
256
257    void _uvid(int e, int& u, int& v) const {
258      u = e / _node_num;
259      v = e % _node_num;
260      if  (u >= v) {
261        u = _node_num - 2 - u;
262        v = _node_num - 1 - v;
263      }
264    }
265
266    void _stid(int a, int& s, int& t) const {
267      if ((a & 1) == 1) {
268        _uvid(a >> 1, s, t);
269      } else {
270        _uvid(a >> 1, t, s);
271      }
272    }
273
274    int _eid(int u, int v) const {
275      if (u < (_node_num - 1) / 2) {
276        return u * _node_num + v;
277      } else {
278        return (_node_num - 1 - u) * _node_num - v - 1;
279      }
280    }
281
282  public:
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 ArcNumTag;
309    typedef True EdgeNumTag;
310
311    int nodeNum() const { return _node_num; }
312    int arcNum() const { return 2 * _edge_num; }
313    int edgeNum() const { return _edge_num; }
314
315    static int id(Node node) { return node._id; }
316    static int id(Arc arc) { return arc._id; }
317    static int id(Edge edge) { return edge._id; }
318
319    int maxNodeId() const { return _node_num-1; }
320    int maxArcId() const { return 2 * _edge_num-1; }
321    int maxEdgeId() const { return _edge_num-1; }
322
323    static Node nodeFromId(int id) { return Node(id);}
324    static Arc arcFromId(int id) { return Arc(id);}
325    static Edge edgeFromId(int id) { return Edge(id);}
326
327    Node u(Edge edge) const {
328      return Node(_uid(edge._id));
329    }
330
331    Node v(Edge edge) const {
332      return Node(_vid(edge._id));
333    }
334
335    Node source(Arc arc) const {
336      return Node((arc._id & 1) == 1 ?
337                  _uid(arc._id >> 1) : _vid(arc._id >> 1));
338    }
339
340    Node target(Arc arc) const {
341      return Node((arc._id & 1) == 1 ?
342                  _vid(arc._id >> 1) : _uid(arc._id >> 1));
343    }
344
345    typedef True FindEdgeTag;
346    typedef True FindArcTag;
347
348    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
349      return prev != INVALID ? INVALID : edge(u, v);
350    }
351
352    Arc findArc(Node s, Node t, Arc prev = INVALID) const {
353      return prev != INVALID ? INVALID : arc(s, t);
354    }
355
356    class Node {
357      friend class FullGraphBase;
358
359    protected:
360      int _id;
361      Node(int id) : _id(id) {}
362    public:
363      Node() {}
364      Node (Invalid) { _id = -1; }
365      bool operator==(const Node node) const {return _id == node._id;}
366      bool operator!=(const Node node) const {return _id != node._id;}
367      bool operator<(const Node node) const {return _id < node._id;}
368    };
369
370    class Edge {
371      friend class FullGraphBase;
372      friend class Arc;
373
374    protected:
375      int _id;
376
377      Edge(int id) : _id(id) {}
378
379    public:
380      Edge() { }
381      Edge (Invalid) { _id = -1; }
382
383      bool operator==(const Edge edge) const {return _id == edge._id;}
384      bool operator!=(const Edge edge) const {return _id != edge._id;}
385      bool operator<(const Edge edge) const {return _id < edge._id;}
386    };
387
388    class Arc {
389      friend class FullGraphBase;
390
391    protected:
392      int _id;
393
394      Arc(int id) : _id(id) {}
395
396    public:
397      Arc() { }
398      Arc (Invalid) { _id = -1; }
399
400      operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }
401
402      bool operator==(const Arc arc) const {return _id == arc._id;}
403      bool operator!=(const Arc arc) const {return _id != arc._id;}
404      bool operator<(const Arc arc) const {return _id < arc._id;}
405    };
406
407    static bool direction(Arc arc) {
408      return (arc._id & 1) == 1;
409    }
410
411    static Arc direct(Edge edge, bool dir) {
412      return Arc((edge._id << 1) | (dir ? 1 : 0));
413    }
414
415    void first(Node& node) const {
416      node._id = _node_num - 1;
417    }
418
419    static void next(Node& node) {
420      --node._id;
421    }
422
423    void first(Arc& arc) const {
424      arc._id = (_edge_num << 1) - 1;
425    }
426
427    static void next(Arc& arc) {
428      --arc._id;
429    }
430
431    void first(Edge& edge) const {
432      edge._id = _edge_num - 1;
433    }
434
435    static void next(Edge& edge) {
436      --edge._id;
437    }
438
439    void firstOut(Arc& arc, const Node& node) const {
440      int s = node._id, t = _node_num - 1;
441      if (s < t) {
442        arc._id = (_eid(s, t) << 1) | 1;
443      } else {
444        --t;
445        arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
446      }
447    }
448
449    void nextOut(Arc& arc) const {
450      int s, t;
451      _stid(arc._id, s, t);
452      --t;
453      if (s < t) {
454        arc._id = (_eid(s, t) << 1) | 1;
455      } else {
456        if (s == t) --t;
457        arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
458      }
459    }
460
461    void firstIn(Arc& arc, const Node& node) const {
462      int s = _node_num - 1, t = node._id;
463      if (s > t) {
464        arc._id = (_eid(t, s) << 1);
465      } else {
466        --s;
467        arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
468      }
469    }
470
471    void nextIn(Arc& arc) const {
472      int s, t;
473      _stid(arc._id, s, t);
474      --s;
475      if (s > t) {
476        arc._id = (_eid(t, s) << 1);
477      } else {
478        if (s == t) --s;
479        arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
480      }
481    }
482
483    void firstInc(Edge& edge, bool& dir, const Node& node) const {
484      int u = node._id, v = _node_num - 1;
485      if (u < v) {
486        edge._id = _eid(u, v);
487        dir = true;
488      } else {
489        --v;
490        edge._id = (v != -1 ? _eid(v, u) : -1);
491        dir = false;
492      }
493    }
494
495    void nextInc(Edge& edge, bool& dir) const {
496      int u, v;
497      if (dir) {
498        _uvid(edge._id, u, v);
499        --v;
500        if (u < v) {
501          edge._id = _eid(u, v);
502        } else {
503          --v;
504          edge._id = (v != -1 ? _eid(v, u) : -1);
505          dir = false;
506        }
507      } else {
508        _uvid(edge._id, v, u);
509        --v;
510        edge._id = (v != -1 ? _eid(v, u) : -1);
511      }
512    }
513
514  };
515
516  typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
517
518  /// \ingroup graphs
519  ///
520  /// \brief An undirected full graph class.
521  ///
522  /// This is a simple and fast undirected full graph
523  /// implementation. From each node go edge to each other node,
524  /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
525  /// This graph type is completely static, so you can neither
526  /// add nor delete either edges or nodes, and it needs constant
527  /// space in memory.
528  ///
529  /// This class fully conforms to the \ref concepts::Graph "Graph concept".
530  ///
531  /// The \c FullGraph and \c FullDigraph classes are very similar,
532  /// but there are two differences. While the \c FullDigraph class
533  /// conforms only to the \ref concepts::Digraph "Digraph" concept,
534  /// this class conforms to the \ref concepts::Graph "Graph" concept,
535  /// moreover \c FullGraph does not contain a loop arc for each
536  /// node as \c FullDigraph does.
537  ///
538  /// \sa FullDigraph
539  class FullGraph : public ExtendedFullGraphBase {
540  public:
541
542    typedef ExtendedFullGraphBase Parent;
543
544    /// \brief Constructor
545    FullGraph() { construct(0); }
546
547    /// \brief Constructor
548    ///
549    /// Constructor.
550    /// \param n The number of the nodes.
551    FullGraph(int n) { construct(n); }
552
553    /// \brief Resizes the graph
554    ///
555    /// Resizes the graph. The function will fully destroy and
556    /// rebuild the graph. This cause that the maps of the graph will
557    /// reallocated automatically and the previous values will be lost.
558    void resize(int n) {
559      Parent::notifier(Arc()).clear();
560      Parent::notifier(Edge()).clear();
561      Parent::notifier(Node()).clear();
562      construct(n);
563      Parent::notifier(Node()).build();
564      Parent::notifier(Edge()).build();
565      Parent::notifier(Arc()).build();
566    }
567
568    /// \brief Returns the node with the given index.
569    ///
570    /// Returns the node with the given index. Since it is a static
571    /// graph its nodes can be indexed with integers from the range
572    /// <tt>[0..nodeNum()-1]</tt>.
573    /// \sa index()
574    Node operator()(int ix) const { return Parent::operator()(ix); }
575
576    /// \brief Returns the index of the given node.
577    ///
578    /// Returns the index of the given node. Since it is a static
579    /// graph its nodes can be indexed with integers from the range
580    /// <tt>[0..nodeNum()-1]</tt>.
581    /// \sa operator()
582    int index(const Node& node) const { return Parent::index(node); }
583
584    /// \brief Returns the arc connecting the given nodes.
585    ///
586    /// Returns the arc connecting the given nodes.
587    Arc arc(const Node& s, const Node& t) const {
588      return Parent::arc(s, t);
589    }
590
591    /// \brief Returns the edge connects the given nodes.
592    ///
593    /// Returns the edge connects the given nodes.
594    Edge edge(const Node& u, const Node& v) const {
595      return Parent::edge(u, v);
596    }
597
598    /// \brief Number of nodes.
599    int nodeNum() const { return Parent::nodeNum(); }
600    /// \brief Number of arcs.
601    int arcNum() const { return Parent::arcNum(); }
602    /// \brief Number of edges.
603    int edgeNum() const { return Parent::edgeNum(); }
604
605  };
606
607
608} //namespace lemon
609
610
611#endif //LEMON_FULL_GRAPH_H
Note: See TracBrowser for help on using the repository browser.