COIN-OR::LEMON - Graph Library

source: lemon/lemon/full_graph.h @ 567:42d4b889903a

Last change on this file since 567:42d4b889903a was 463:88ed40ad0d4f, checked in by Alpar Juttner <alpar@…>, 16 years ago

Happy New Year again

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