COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/full_graph.h

Last change on this file was 1092:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 6 years ago

Apply unify-sources.sh to the source tree

File size: 29.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-2013
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    static int index(const Node& node) { 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  /// This class provides constant time counting for nodes and arcs.
166  ///
167  /// \note FullDigraph and FullGraph classes are very similar,
168  /// but there are two differences. While this class conforms only
169  /// to the \ref concepts::Digraph "Digraph" concept, FullGraph
170  /// conforms to the \ref concepts::Graph "Graph" concept,
171  /// moreover FullGraph does not contain a loop for each
172  /// node as this class does.
173  ///
174  /// \sa FullGraph
175  class FullDigraph : public ExtendedFullDigraphBase {
176    typedef ExtendedFullDigraphBase Parent;
177
178  public:
179
180    /// \brief Default constructor.
181    ///
182    /// Default constructor. The number of nodes and arcs will be zero.
183    FullDigraph() { construct(0); }
184
185    /// \brief Constructor
186    ///
187    /// Constructor.
188    /// \param n The number of the nodes.
189    FullDigraph(int n) { construct(n); }
190
191    /// \brief Resizes the digraph
192    ///
193    /// This function resizes the digraph. It fully destroys and
194    /// rebuilds the structure, therefore the maps of the digraph will be
195    /// reallocated automatically and the previous values will be lost.
196    void resize(int n) {
197      Parent::notifier(Arc()).clear();
198      Parent::notifier(Node()).clear();
199      construct(n);
200      Parent::notifier(Node()).build();
201      Parent::notifier(Arc()).build();
202    }
203
204    /// \brief Returns the node with the given index.
205    ///
206    /// Returns the node with the given index. Since this structure is
207    /// completely static, the nodes can be indexed with integers from
208    /// the range <tt>[0..nodeNum()-1]</tt>.
209    /// The index of a node is the same as its ID.
210    /// \sa index()
211    Node operator()(int ix) const { return Parent::operator()(ix); }
212
213    /// \brief Returns the index of the given node.
214    ///
215    /// Returns the index of the given node. Since this structure is
216    /// completely static, the nodes can be indexed with integers from
217    /// the range <tt>[0..nodeNum()-1]</tt>.
218    /// The index of a node is the same as its ID.
219    /// \sa operator()()
220    static int index(const Node& node) { return Parent::index(node); }
221
222    /// \brief Returns the arc connecting the given nodes.
223    ///
224    /// Returns the arc connecting the given nodes.
225    Arc arc(Node u, Node v) const {
226      return Parent::arc(u, v);
227    }
228
229    /// \brief Number of nodes.
230    int nodeNum() const { return Parent::nodeNum(); }
231    /// \brief Number of arcs.
232    int arcNum() const { return Parent::arcNum(); }
233  };
234
235
236  class FullGraphBase {
237  public:
238
239    typedef FullGraphBase Graph;
240
241    class Node;
242    class Arc;
243    class Edge;
244
245  protected:
246
247    int _node_num;
248    int _edge_num;
249
250    FullGraphBase() {}
251
252    void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }
253
254    int _uid(int e) const {
255      int u = e / _node_num;
256      int v = e % _node_num;
257      return u < v ? u : _node_num - 2 - u;
258    }
259
260    int _vid(int e) const {
261      int u = e / _node_num;
262      int v = e % _node_num;
263      return u < v ? v : _node_num - 1 - v;
264    }
265
266    void _uvid(int e, int& u, int& v) const {
267      u = e / _node_num;
268      v = e % _node_num;
269      if  (u >= v) {
270        u = _node_num - 2 - u;
271        v = _node_num - 1 - v;
272      }
273    }
274
275    void _stid(int a, int& s, int& t) const {
276      if ((a & 1) == 1) {
277        _uvid(a >> 1, s, t);
278      } else {
279        _uvid(a >> 1, t, s);
280      }
281    }
282
283    int _eid(int u, int v) const {
284      if (u < (_node_num - 1) / 2) {
285        return u * _node_num + v;
286      } else {
287        return (_node_num - 1 - u) * _node_num - v - 1;
288      }
289    }
290
291  public:
292
293    Node operator()(int ix) const { return Node(ix); }
294    static int index(const Node& node) { return node._id; }
295
296    Edge edge(const Node& u, const Node& v) const {
297      if (u._id < v._id) {
298        return Edge(_eid(u._id, v._id));
299      } else if (u._id != v._id) {
300        return Edge(_eid(v._id, u._id));
301      } else {
302        return INVALID;
303      }
304    }
305
306    Arc arc(const Node& s, const Node& t) const {
307      if (s._id < t._id) {
308        return Arc((_eid(s._id, t._id) << 1) | 1);
309      } else if (s._id != t._id) {
310        return Arc(_eid(t._id, s._id) << 1);
311      } else {
312        return INVALID;
313      }
314    }
315
316    typedef True NodeNumTag;
317    typedef True ArcNumTag;
318    typedef True EdgeNumTag;
319
320    int nodeNum() const { return _node_num; }
321    int arcNum() const { return 2 * _edge_num; }
322    int edgeNum() const { return _edge_num; }
323
324    static int id(Node node) { return node._id; }
325    static int id(Arc arc) { return arc._id; }
326    static int id(Edge edge) { return edge._id; }
327
328    int maxNodeId() const { return _node_num-1; }
329    int maxArcId() const { return 2 * _edge_num-1; }
330    int maxEdgeId() const { return _edge_num-1; }
331
332    static Node nodeFromId(int id) { return Node(id);}
333    static Arc arcFromId(int id) { return Arc(id);}
334    static Edge edgeFromId(int id) { return Edge(id);}
335
336    Node u(Edge edge) const {
337      return Node(_uid(edge._id));
338    }
339
340    Node v(Edge edge) const {
341      return Node(_vid(edge._id));
342    }
343
344    Node source(Arc arc) const {
345      return Node((arc._id & 1) == 1 ?
346                  _uid(arc._id >> 1) : _vid(arc._id >> 1));
347    }
348
349    Node target(Arc arc) const {
350      return Node((arc._id & 1) == 1 ?
351                  _vid(arc._id >> 1) : _uid(arc._id >> 1));
352    }
353
354    typedef True FindEdgeTag;
355    typedef True FindArcTag;
356
357    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
358      return prev != INVALID ? INVALID : edge(u, v);
359    }
360
361    Arc findArc(Node s, Node t, Arc prev = INVALID) const {
362      return prev != INVALID ? INVALID : arc(s, t);
363    }
364
365    class Node {
366      friend class FullGraphBase;
367
368    protected:
369      int _id;
370      Node(int id) : _id(id) {}
371    public:
372      Node() {}
373      Node (Invalid) { _id = -1; }
374      bool operator==(const Node node) const {return _id == node._id;}
375      bool operator!=(const Node node) const {return _id != node._id;}
376      bool operator<(const Node node) const {return _id < node._id;}
377    };
378
379    class Edge {
380      friend class FullGraphBase;
381      friend class Arc;
382
383    protected:
384      int _id;
385
386      Edge(int id) : _id(id) {}
387
388    public:
389      Edge() { }
390      Edge (Invalid) { _id = -1; }
391
392      bool operator==(const Edge edge) const {return _id == edge._id;}
393      bool operator!=(const Edge edge) const {return _id != edge._id;}
394      bool operator<(const Edge edge) const {return _id < edge._id;}
395    };
396
397    class Arc {
398      friend class FullGraphBase;
399
400    protected:
401      int _id;
402
403      Arc(int id) : _id(id) {}
404
405    public:
406      Arc() { }
407      Arc (Invalid) { _id = -1; }
408
409      operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }
410
411      bool operator==(const Arc arc) const {return _id == arc._id;}
412      bool operator!=(const Arc arc) const {return _id != arc._id;}
413      bool operator<(const Arc arc) const {return _id < arc._id;}
414    };
415
416    static bool direction(Arc arc) {
417      return (arc._id & 1) == 1;
418    }
419
420    static Arc direct(Edge edge, bool dir) {
421      return Arc((edge._id << 1) | (dir ? 1 : 0));
422    }
423
424    void first(Node& node) const {
425      node._id = _node_num - 1;
426    }
427
428    static void next(Node& node) {
429      --node._id;
430    }
431
432    void first(Arc& arc) const {
433      arc._id = (_edge_num << 1) - 1;
434    }
435
436    static void next(Arc& arc) {
437      --arc._id;
438    }
439
440    void first(Edge& edge) const {
441      edge._id = _edge_num - 1;
442    }
443
444    static void next(Edge& edge) {
445      --edge._id;
446    }
447
448    void firstOut(Arc& arc, const Node& node) const {
449      int s = node._id, t = _node_num - 1;
450      if (s < t) {
451        arc._id = (_eid(s, t) << 1) | 1;
452      } else {
453        --t;
454        arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
455      }
456    }
457
458    void nextOut(Arc& arc) const {
459      int s, t;
460      _stid(arc._id, s, t);
461      --t;
462      if (s < t) {
463        arc._id = (_eid(s, t) << 1) | 1;
464      } else {
465        if (s == t) --t;
466        arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
467      }
468    }
469
470    void firstIn(Arc& arc, const Node& node) const {
471      int s = _node_num - 1, t = node._id;
472      if (s > t) {
473        arc._id = (_eid(t, s) << 1);
474      } else {
475        --s;
476        arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
477      }
478    }
479
480    void nextIn(Arc& arc) const {
481      int s, t;
482      _stid(arc._id, s, t);
483      --s;
484      if (s > t) {
485        arc._id = (_eid(t, s) << 1);
486      } else {
487        if (s == t) --s;
488        arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
489      }
490    }
491
492    void firstInc(Edge& edge, bool& dir, const Node& node) const {
493      int u = node._id, v = _node_num - 1;
494      if (u < v) {
495        edge._id = _eid(u, v);
496        dir = true;
497      } else {
498        --v;
499        edge._id = (v != -1 ? _eid(v, u) : -1);
500        dir = false;
501      }
502    }
503
504    void nextInc(Edge& edge, bool& dir) const {
505      int u, v;
506      if (dir) {
507        _uvid(edge._id, u, v);
508        --v;
509        if (u < v) {
510          edge._id = _eid(u, v);
511        } else {
512          --v;
513          edge._id = (v != -1 ? _eid(v, u) : -1);
514          dir = false;
515        }
516      } else {
517        _uvid(edge._id, v, u);
518        --v;
519        edge._id = (v != -1 ? _eid(v, u) : -1);
520      }
521    }
522
523  };
524
525  typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
526
527  /// \ingroup graphs
528  ///
529  /// \brief An undirected full graph class.
530  ///
531  /// FullGraph is a simple and fast implmenetation of undirected full
532  /// (complete) graphs. It contains an edge between every distinct pair
533  /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>.
534  /// This class is completely static and it needs constant memory space.
535  /// Thus you can neither add nor delete nodes or edges, however
536  /// the structure can be resized using resize().
537  ///
538  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
539  /// Most of its member functions and nested classes are documented
540  /// only in the concept class.
541  ///
542  /// This class provides constant time counting for nodes, edges and arcs.
543  ///
544  /// \note FullDigraph and FullGraph classes are very similar,
545  /// but there are two differences. While FullDigraph
546  /// conforms only to the \ref concepts::Digraph "Digraph" concept,
547  /// this class conforms to the \ref concepts::Graph "Graph" concept,
548  /// moreover this class does not contain a loop for each
549  /// node as FullDigraph does.
550  ///
551  /// \sa FullDigraph
552  class FullGraph : public ExtendedFullGraphBase {
553    typedef ExtendedFullGraphBase Parent;
554
555  public:
556
557    /// \brief Default constructor.
558    ///
559    /// Default constructor. The number of nodes and edges will be zero.
560    FullGraph() { construct(0); }
561
562    /// \brief Constructor
563    ///
564    /// Constructor.
565    /// \param n The number of the nodes.
566    FullGraph(int n) { construct(n); }
567
568    /// \brief Resizes the graph
569    ///
570    /// This function resizes the graph. It fully destroys and
571    /// rebuilds the structure, therefore the maps of the graph will be
572    /// reallocated automatically and the previous values will be lost.
573    void resize(int n) {
574      Parent::notifier(Arc()).clear();
575      Parent::notifier(Edge()).clear();
576      Parent::notifier(Node()).clear();
577      construct(n);
578      Parent::notifier(Node()).build();
579      Parent::notifier(Edge()).build();
580      Parent::notifier(Arc()).build();
581    }
582
583    /// \brief Returns the node with the given index.
584    ///
585    /// Returns the node with the given index. Since this structure is
586    /// completely static, the nodes can be indexed with integers from
587    /// the range <tt>[0..nodeNum()-1]</tt>.
588    /// The index of a node is the same as its ID.
589    /// \sa index()
590    Node operator()(int ix) const { return Parent::operator()(ix); }
591
592    /// \brief Returns the index of the given node.
593    ///
594    /// Returns the index of the given node. Since this structure is
595    /// completely static, the nodes can be indexed with integers from
596    /// the range <tt>[0..nodeNum()-1]</tt>.
597    /// The index of a node is the same as its ID.
598    /// \sa operator()()
599    static int index(const Node& node) { return Parent::index(node); }
600
601    /// \brief Returns the arc connecting the given nodes.
602    ///
603    /// Returns the arc connecting the given nodes.
604    Arc arc(Node s, Node t) const {
605      return Parent::arc(s, t);
606    }
607
608    /// \brief Returns the edge connecting the given nodes.
609    ///
610    /// Returns the edge connecting the given nodes.
611    Edge edge(Node u, Node v) const {
612      return Parent::edge(u, v);
613    }
614
615    /// \brief Number of nodes.
616    int nodeNum() const { return Parent::nodeNum(); }
617    /// \brief Number of arcs.
618    int arcNum() const { return Parent::arcNum(); }
619    /// \brief Number of edges.
620    int edgeNum() const { return Parent::edgeNum(); }
621
622  };
623
624  class FullBpGraphBase {
625
626  protected:
627
628    int _red_num, _blue_num;
629    int _node_num, _edge_num;
630
631  public:
632
633    typedef FullBpGraphBase Graph;
634
635    class Node;
636    class Arc;
637    class Edge;
638
639    class Node {
640      friend class FullBpGraphBase;
641    protected:
642
643      int _id;
644      explicit Node(int id) { _id = id;}
645
646    public:
647      Node() {}
648      Node (Invalid) { _id = -1; }
649      bool operator==(const Node& node) const {return _id == node._id;}
650      bool operator!=(const Node& node) const {return _id != node._id;}
651      bool operator<(const Node& node) const {return _id < node._id;}
652    };
653
654    class RedNode : public Node {
655      friend class FullBpGraphBase;
656    protected:
657
658      explicit RedNode(int pid) : Node(pid) {}
659
660    public:
661      RedNode() {}
662      RedNode(const RedNode& node) : Node(node) {}
663      RedNode(Invalid) : Node(INVALID){}
664    };
665
666    class BlueNode : public Node {
667      friend class FullBpGraphBase;
668    protected:
669
670      explicit BlueNode(int pid) : Node(pid) {}
671
672    public:
673      BlueNode() {}
674      BlueNode(const BlueNode& node) : Node(node) {}
675      BlueNode(Invalid) : Node(INVALID){}
676    };
677
678    class Edge {
679      friend class FullBpGraphBase;
680    protected:
681
682      int _id;
683      explicit Edge(int id) { _id = id;}
684
685    public:
686      Edge() {}
687      Edge (Invalid) { _id = -1; }
688      bool operator==(const Edge& arc) const {return _id == arc._id;}
689      bool operator!=(const Edge& arc) const {return _id != arc._id;}
690      bool operator<(const Edge& arc) const {return _id < arc._id;}
691    };
692
693    class Arc {
694      friend class FullBpGraphBase;
695    protected:
696
697      int _id;
698      explicit Arc(int id) { _id = id;}
699
700    public:
701      operator Edge() const {
702        return _id != -1 ? edgeFromId(_id / 2) : INVALID;
703      }
704
705      Arc() {}
706      Arc (Invalid) { _id = -1; }
707      bool operator==(const Arc& arc) const {return _id == arc._id;}
708      bool operator!=(const Arc& arc) const {return _id != arc._id;}
709      bool operator<(const Arc& arc) const {return _id < arc._id;}
710    };
711
712
713  protected:
714
715    FullBpGraphBase()
716      : _red_num(0), _blue_num(0), _node_num(0), _edge_num(0) {}
717
718    void construct(int redNum, int blueNum) {
719      _red_num = redNum; _blue_num = blueNum;
720      _node_num = redNum + blueNum; _edge_num = redNum * blueNum;
721    }
722
723  public:
724
725    typedef True NodeNumTag;
726    typedef True EdgeNumTag;
727    typedef True ArcNumTag;
728
729    int nodeNum() const { return _node_num; }
730    int redNum() const { return _red_num; }
731    int blueNum() const { return _blue_num; }
732    int edgeNum() const { return _edge_num; }
733    int arcNum() const { return 2 * _edge_num; }
734
735    int maxNodeId() const { return _node_num - 1; }
736    int maxRedId() const { return _red_num - 1; }
737    int maxBlueId() const { return _blue_num - 1; }
738    int maxEdgeId() const { return _edge_num - 1; }
739    int maxArcId() const { return 2 * _edge_num - 1; }
740
741    bool red(Node n) const { return n._id < _red_num; }
742    bool blue(Node n) const { return n._id >= _red_num; }
743
744    static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
745    static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
746
747    Node source(Arc a) const {
748      if (a._id & 1) {
749        return Node((a._id >> 1) % _red_num);
750      } else {
751        return Node((a._id >> 1) / _red_num + _red_num);
752      }
753    }
754    Node target(Arc a) const {
755      if (a._id & 1) {
756        return Node((a._id >> 1) / _red_num + _red_num);
757      } else {
758        return Node((a._id >> 1) % _red_num);
759      }
760    }
761
762    RedNode redNode(Edge e) const {
763      return RedNode(e._id % _red_num);
764    }
765    BlueNode blueNode(Edge e) const {
766      return BlueNode(e._id / _red_num + _red_num);
767    }
768
769    static bool direction(Arc a) {
770      return (a._id & 1) == 1;
771    }
772
773    static Arc direct(Edge e, bool d) {
774      return Arc(e._id * 2 + (d ? 1 : 0));
775    }
776
777    void first(Node& node) const {
778      node._id = _node_num - 1;
779    }
780
781    static void next(Node& node) {
782      --node._id;
783    }
784
785    void first(RedNode& node) const {
786      node._id = _red_num - 1;
787    }
788
789    static void next(RedNode& node) {
790      --node._id;
791    }
792
793    void first(BlueNode& node) const {
794      if (_red_num == _node_num) node._id = -1;
795      else node._id = _node_num - 1;
796    }
797
798    void next(BlueNode& node) const {
799      if (node._id == _red_num) node._id = -1;
800      else --node._id;
801    }
802
803    void first(Arc& arc) const {
804      arc._id = 2 * _edge_num - 1;
805    }
806
807    static void next(Arc& arc) {
808      --arc._id;
809    }
810
811    void first(Edge& arc) const {
812      arc._id = _edge_num - 1;
813    }
814
815    static void next(Edge& arc) {
816      --arc._id;
817    }
818
819    void firstOut(Arc &a, const Node& v) const {
820      if (v._id < _red_num) {
821        a._id = 2 * (v._id + _red_num * (_blue_num - 1)) + 1;
822      } else {
823        a._id = 2 * (_red_num - 1 + _red_num * (v._id - _red_num));
824      }
825    }
826    void nextOut(Arc &a) const {
827      if (a._id & 1) {
828        a._id -= 2 * _red_num;
829        if (a._id < 0) a._id = -1;
830      } else {
831        if (a._id % (2 * _red_num) == 0) a._id = -1;
832        else a._id -= 2;
833      }
834    }
835
836    void firstIn(Arc &a, const Node& v) const {
837      if (v._id < _red_num) {
838        a._id = 2 * (v._id + _red_num * (_blue_num - 1));
839      } else {
840        a._id = 2 * (_red_num - 1 + _red_num * (v._id - _red_num)) + 1;
841      }
842    }
843    void nextIn(Arc &a) const {
844      if (a._id & 1) {
845        if (a._id % (2 * _red_num) == 1) a._id = -1;
846        else a._id -= 2;
847      } else {
848        a._id -= 2 * _red_num;
849        if (a._id < 0) a._id = -1;
850      }
851    }
852
853    void firstInc(Edge &e, bool& d, const Node& v) const {
854      if (v._id < _red_num) {
855        d = true;
856        e._id = v._id + _red_num * (_blue_num - 1);
857      } else {
858        d = false;
859        e._id = _red_num - 1 + _red_num * (v._id - _red_num);
860      }
861    }
862    void nextInc(Edge &e, bool& d) const {
863      if (d) {
864        e._id -= _red_num;
865        if (e._id < 0) e._id = -1;
866      } else {
867        if (e._id % _red_num == 0) e._id = -1;
868        else --e._id;
869      }
870    }
871
872    static int id(const Node& v) { return v._id; }
873    int id(const RedNode& v) const { return v._id; }
874    int id(const BlueNode& v) const { return v._id - _red_num; }
875    static int id(Arc e) { return e._id; }
876    static int id(Edge e) { return e._id; }
877
878    static Node nodeFromId(int id) { return Node(id);}
879    static Arc arcFromId(int id) { return Arc(id);}
880    static Edge edgeFromId(int id) { return Edge(id);}
881
882    bool valid(Node n) const {
883      return n._id >= 0 && n._id < _node_num;
884    }
885    bool valid(Arc a) const {
886      return a._id >= 0 && a._id < 2 * _edge_num;
887    }
888    bool valid(Edge e) const {
889      return e._id >= 0 && e._id < _edge_num;
890    }
891
892    RedNode redNode(int index) const {
893      return RedNode(index);
894    }
895
896    int index(RedNode n) const {
897      return n._id;
898    }
899
900    BlueNode blueNode(int index) const {
901      return BlueNode(index + _red_num);
902    }
903
904    int index(BlueNode n) const {
905      return n._id - _red_num;
906    }
907
908    void clear() {
909      _red_num = 0; _blue_num = 0;
910      _node_num = 0; _edge_num = 0;
911    }
912
913    Edge edge(const Node& u, const Node& v) const {
914      if (u._id < _red_num) {
915        if (v._id < _red_num) {
916          return Edge(-1);
917        } else {
918          return Edge(u._id + _red_num * (v._id - _red_num));
919        }
920      } else {
921        if (v._id < _red_num) {
922          return Edge(v._id + _red_num * (u._id - _red_num));
923        } else {
924          return Edge(-1);
925        }
926      }
927    }
928
929    Arc arc(const Node& u, const Node& v) const {
930      if (u._id < _red_num) {
931        if (v._id < _red_num) {
932          return Arc(-1);
933        } else {
934          return Arc(2 * (u._id + _red_num * (v._id - _red_num)) + 1);
935        }
936      } else {
937        if (v._id < _red_num) {
938          return Arc(2 * (v._id + _red_num * (u._id - _red_num)));
939        } else {
940          return Arc(-1);
941        }
942      }
943    }
944
945    typedef True FindEdgeTag;
946    typedef True FindArcTag;
947
948    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
949      return prev != INVALID ? INVALID : edge(u, v);
950    }
951
952    Arc findArc(Node s, Node t, Arc prev = INVALID) const {
953      return prev != INVALID ? INVALID : arc(s, t);
954    }
955
956  };
957
958  typedef BpGraphExtender<FullBpGraphBase> ExtendedFullBpGraphBase;
959
960  /// \ingroup graphs
961  ///
962  /// \brief An undirected full bipartite graph class.
963  ///
964  /// FullBpGraph is a simple and fast implmenetation of undirected
965  /// full bipartite graphs. It contains an edge between every
966  /// red-blue pairs of nodes, therefore the number of edges is
967  /// <tt>nr*nb</tt>.  This class is completely static and it needs
968  /// constant memory space.  Thus you can neither add nor delete
969  /// nodes or edges, however the structure can be resized using
970  /// resize().
971  ///
972  /// This type fully conforms to the \ref concepts::BpGraph "BpGraph concept".
973  /// Most of its member functions and nested classes are documented
974  /// only in the concept class.
975  ///
976  /// This class provides constant time counting for nodes, edges and arcs.
977  ///
978  /// \sa FullGraph
979  class FullBpGraph : public ExtendedFullBpGraphBase {
980  public:
981
982    typedef ExtendedFullBpGraphBase Parent;
983
984    /// \brief Default constructor.
985    ///
986    /// Default constructor. The number of nodes and edges will be zero.
987    FullBpGraph() { construct(0, 0); }
988
989    /// \brief Constructor
990    ///
991    /// Constructor.
992    /// \param redNum The number of the red nodes.
993    /// \param blueNum The number of the blue nodes.
994    FullBpGraph(int redNum, int blueNum) { construct(redNum, blueNum); }
995
996    /// \brief Resizes the graph
997    ///
998    /// This function resizes the graph. It fully destroys and
999    /// rebuilds the structure, therefore the maps of the graph will be
1000    /// reallocated automatically and the previous values will be lost.
1001    void resize(int redNum, int blueNum) {
1002      Parent::notifier(Arc()).clear();
1003      Parent::notifier(Edge()).clear();
1004      Parent::notifier(Node()).clear();
1005      Parent::notifier(BlueNode()).clear();
1006      Parent::notifier(RedNode()).clear();
1007      construct(redNum, blueNum);
1008      Parent::notifier(RedNode()).build();
1009      Parent::notifier(BlueNode()).build();
1010      Parent::notifier(Node()).build();
1011      Parent::notifier(Edge()).build();
1012      Parent::notifier(Arc()).build();
1013    }
1014
1015    using Parent::redNode;
1016    using Parent::blueNode;
1017
1018    /// \brief Returns the red node with the given index.
1019    ///
1020    /// Returns the red node with the given index. Since this
1021    /// structure is completely static, the red nodes can be indexed
1022    /// with integers from the range <tt>[0..redNum()-1]</tt>.
1023    /// \sa redIndex()
1024    RedNode redNode(int index) const { return Parent::redNode(index); }
1025
1026    /// \brief Returns the index of the given red node.
1027    ///
1028    /// Returns the index of the given red node. Since this structure
1029    /// is completely static, the red nodes can be indexed with
1030    /// integers from the range <tt>[0..redNum()-1]</tt>.
1031    ///
1032    /// \sa operator()()
1033    int index(RedNode node) const { return Parent::index(node); }
1034
1035    /// \brief Returns the blue node with the given index.
1036    ///
1037    /// Returns the blue node with the given index. Since this
1038    /// structure is completely static, the blue nodes can be indexed
1039    /// with integers from the range <tt>[0..blueNum()-1]</tt>.
1040    /// \sa blueIndex()
1041    BlueNode blueNode(int index) const { return Parent::blueNode(index); }
1042
1043    /// \brief Returns the index of the given blue node.
1044    ///
1045    /// Returns the index of the given blue node. Since this structure
1046    /// is completely static, the blue nodes can be indexed with
1047    /// integers from the range <tt>[0..blueNum()-1]</tt>.
1048    ///
1049    /// \sa operator()()
1050    int index(BlueNode node) const { return Parent::index(node); }
1051
1052    /// \brief Returns the edge which connects the given nodes.
1053    ///
1054    /// Returns the edge which connects the given nodes.
1055    Edge edge(const Node& u, const Node& v) const {
1056      return Parent::edge(u, v);
1057    }
1058
1059    /// \brief Returns the arc which connects the given nodes.
1060    ///
1061    /// Returns the arc which connects the given nodes.
1062    Arc arc(const Node& u, const Node& v) const {
1063      return Parent::arc(u, v);
1064    }
1065
1066    /// \brief Number of nodes.
1067    int nodeNum() const { return Parent::nodeNum(); }
1068    /// \brief Number of red nodes.
1069    int redNum() const { return Parent::redNum(); }
1070    /// \brief Number of blue nodes.
1071    int blueNum() const { return Parent::blueNum(); }
1072    /// \brief Number of arcs.
1073    int arcNum() const { return Parent::arcNum(); }
1074    /// \brief Number of edges.
1075    int edgeNum() const { return Parent::edgeNum(); }
1076  };
1077
1078
1079} //namespace lemon
1080
1081
1082#endif //LEMON_FULL_GRAPH_H
Note: See TracBrowser for help on using the repository browser.