COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/full_graph.h @ 1993:2115143eceea

Last change on this file since 1993:2115143eceea was 1993:2115143eceea, checked in by Balazs Dezso, 14 years ago

utility, invalid and traits moved to bits

File size: 18.1 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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 <cmath>
23
24
25#include <lemon/bits/graph_extender.h>
26
27
28#include <lemon/bits/invalid.h>
29#include <lemon/bits/utility.h>
30
31
32///\ingroup graphs
33///\file
34///\brief FullGraph and FullUGraph classes.
35
36
37namespace lemon {
38
39  /// \brief Base of the FullGrpah.
40  ///
41  /// Base of the FullGrpah.
42  class FullGraphBase {
43    int _nodeNum;
44    int _edgeNum;
45  public:
46
47    typedef FullGraphBase Graph;
48
49    class Node;
50    class Edge;
51
52  public:
53
54    FullGraphBase() {}
55
56
57    ///Creates a full graph with \c n nodes.
58    void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
59   
60    typedef True NodeNumTag;
61    typedef True EdgeNumTag;
62
63    /// \brief Returns the node with the given index.
64    ///
65    /// Returns the node with the given index. Because it is a
66    /// static size graph the node's of the graph can be indiced
67    /// by the range from 0 to \e nodeNum()-1 and the index of
68    /// the node can accessed by the \e index() member.
69    Node operator()(int index) const { return Node(index); }
70
71    /// \brief Returns the index of the node.
72    ///
73    /// Returns the index of the node. Because it is a
74    /// static size graph the node's of the graph can be indiced
75    /// by the range from 0 to \e nodeNum()-1 and the index of
76    /// the node can accessed by the \e index() member.
77    int index(const Node& node) const { return node.id; }
78
79    ///Number of nodes.
80    int nodeNum() const { return _nodeNum; }
81    ///Number of edges.
82    int edgeNum() const { return _edgeNum; }
83
84    /// Maximum node ID.
85   
86    /// Maximum node ID.
87    ///\sa id(Node)
88    int maxNodeId() const { return _nodeNum-1; }
89    /// Maximum edge ID.
90   
91    /// Maximum edge ID.
92    ///\sa id(Edge)
93    int maxEdgeId() const { return _edgeNum-1; }
94
95    Node source(Edge e) const { return e.id % _nodeNum; }
96    Node target(Edge e) const { return e.id / _nodeNum; }
97
98
99    /// Node ID.
100   
101    /// The ID of a valid Node is a nonnegative integer not greater than
102    /// \ref maxNodeId(). The range of the ID's is not surely continuous
103    /// and the greatest node ID can be actually less then \ref maxNodeId().
104    ///
105    /// The ID of the \ref INVALID node is -1.
106    ///\return The ID of the node \c v.
107
108    static int id(Node v) { return v.id; }
109    /// Edge ID.
110   
111    /// The ID of a valid Edge is a nonnegative integer not greater than
112    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
113    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
114    ///
115    /// The ID of the \ref INVALID edge is -1.
116    ///\return The ID of the edge \c e.
117    static int id(Edge e) { return e.id; }
118
119    static Node nodeFromId(int id) { return Node(id);}
120   
121    static Edge edgeFromId(int id) { return Edge(id);}
122
123    typedef True FindEdgeTag;
124
125    /// Finds an edge between two nodes.
126   
127    /// Finds an edge from node \c u to node \c v.
128    ///
129    /// If \c prev is \ref INVALID (this is the default value), then
130    /// It finds the first edge from \c u to \c v. Otherwise it looks for
131    /// the next edge from \c u to \c v after \c prev.
132    /// \return The found edge or INVALID if there is no such an edge.
133    Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
134      return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
135    }
136   
137     
138    class Node {
139      friend class FullGraphBase;
140
141    protected:
142      int id;
143      Node(int _id) : id(_id) {}
144    public:
145      Node() {}
146      Node (Invalid) : id(-1) {}
147      bool operator==(const Node node) const {return id == node.id;}
148      bool operator!=(const Node node) const {return id != node.id;}
149      bool operator<(const Node node) const {return id < node.id;}
150    };
151   
152
153
154    class Edge {
155      friend class FullGraphBase;
156     
157    protected:
158      int id;  // _nodeNum * target + source;
159
160      Edge(int _id) : id(_id) {}
161
162      Edge(const FullGraphBase& _graph, int source, int target)
163        : id(_graph._nodeNum * target+source) {}
164    public:
165      Edge() { }
166      Edge (Invalid) { id = -1; }
167      bool operator==(const Edge edge) const {return id == edge.id;}
168      bool operator!=(const Edge edge) const {return id != edge.id;}
169      bool operator<(const Edge edge) const {return id < edge.id;}
170    };
171
172    void first(Node& node) const {
173      node.id = _nodeNum-1;
174    }
175
176    static void next(Node& node) {
177      --node.id;
178    }
179
180    void first(Edge& edge) const {
181      edge.id = _edgeNum-1;
182    }
183
184    static void next(Edge& edge) {
185      --edge.id;
186    }
187
188    void firstOut(Edge& edge, const Node& node) const {
189      edge.id = _edgeNum + node.id - _nodeNum;
190    }
191
192    void nextOut(Edge& edge) const {
193      edge.id -= _nodeNum;
194      if (edge.id < 0) edge.id = -1;
195    }
196
197    void firstIn(Edge& edge, const Node& node) const {
198      edge.id = node.id * _nodeNum;
199    }
200   
201    void nextIn(Edge& edge) const {
202      ++edge.id;
203      if (edge.id % _nodeNum == 0) edge.id = -1;
204    }
205
206  };
207
208  typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
209
210  /// \ingroup graphs
211  ///
212  /// \brief A full graph class.
213  ///
214  /// This is a simple and fast directed full graph implementation.
215  /// It is completely static, so you can neither add nor delete either
216  /// edges or nodes.
217  /// Thus it conforms to
218  /// the \ref concept::StaticGraph "StaticGraph" concept
219  /// \sa concept::StaticGraph.
220  ///
221  /// \sa FullGraphBase
222  /// \sa FullUGraph
223  ///
224  /// \author Alpar Juttner
225  class FullGraph : public ExtendedFullGraphBase {
226  public:
227
228    typedef ExtendedFullGraphBase Parent;
229
230    /// \brief Constructor
231    FullGraph() { construct(0); }
232
233    /// \brief Constructor
234    ///
235    FullGraph(int n) { construct(n); }
236
237    /// \brief Resize the graph
238    ///
239    /// Resize the graph. The function will fully destroy and build the graph.
240    /// This cause that the maps of the graph will reallocated
241    /// automatically and the previous values will be lost.
242    void resize(int n) {
243      Parent::getNotifier(Edge()).clear();
244      Parent::getNotifier(Node()).clear();
245      construct(n);
246      Parent::getNotifier(Node()).build();
247      Parent::getNotifier(Edge()).build();
248    }
249  };
250
251
252  /// \brief Base of the FullUGrpah.
253  ///
254  /// Base of the FullUGrpah.
255  class FullUGraphBase {
256    int _nodeNum;
257    int _edgeNum;
258  public:
259
260    typedef FullUGraphBase Graph;
261
262    class Node;
263    class Edge;
264
265  public:
266
267    FullUGraphBase() {}
268
269
270    ///Creates a full graph with \c n nodes.
271    void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
272
273    /// \brief Returns the node with the given index.
274    ///
275    /// Returns the node with the given index. Because it is a
276    /// static size graph the node's of the graph can be indiced
277    /// by the range from 0 to \e nodeNum()-1 and the index of
278    /// the node can accessed by the \e index() member.
279    Node operator()(int index) const { return Node(index); }
280
281    /// \brief Returns the index of the node.
282    ///
283    /// Returns the index of the node. Because it is a
284    /// static size graph the node's of the graph can be indiced
285    /// by the range from 0 to \e nodeNum()-1 and the index of
286    /// the node can accessed by the \e index() member.
287    int index(const Node& node) const { return node.id; }
288
289    typedef True NodeNumTag;
290    typedef True EdgeNumTag;
291
292    ///Number of nodes.
293    int nodeNum() const { return _nodeNum; }
294    ///Number of edges.
295    int edgeNum() const { return _edgeNum; }
296
297    /// Maximum node ID.
298   
299    /// Maximum node ID.
300    ///\sa id(Node)
301    int maxNodeId() const { return _nodeNum-1; }
302    /// Maximum edge ID.
303   
304    /// Maximum edge ID.
305    ///\sa id(Edge)
306    int maxEdgeId() const { return _edgeNum-1; }
307
308    Node source(Edge e) const {
309      /// \todo we may do it faster
310      return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
311    }
312
313    Node target(Edge e) const {
314      int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
315      return Node(e.id - (source) * (source - 1) / 2);
316    }
317
318
319    /// \brief Node ID.
320    ///
321    /// The ID of a valid Node is a nonnegative integer not greater than
322    /// \ref maxNodeId(). The range of the ID's is not surely continuous
323    /// and the greatest node ID can be actually less then \ref maxNodeId().
324    ///
325    /// The ID of the \ref INVALID node is -1.
326    /// \return The ID of the node \c v.
327
328    static int id(Node v) { return v.id; }
329
330    /// \brief Edge ID.
331    ///
332    /// The ID of a valid Edge is a nonnegative integer not greater than
333    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
334    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
335    ///
336    /// The ID of the \ref INVALID edge is -1.
337    ///\return The ID of the edge \c e.
338    static int id(Edge e) { return e.id; }
339
340    /// \brief Finds an edge between two nodes.
341    ///
342    /// Finds an edge from node \c u to node \c v.
343    ///
344    /// If \c prev is \ref INVALID (this is the default value), then
345    /// It finds the first edge from \c u to \c v. Otherwise it looks for
346    /// the next edge from \c u to \c v after \c prev.
347    /// \return The found edge or INVALID if there is no such an edge.
348    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
349      if (prev.id != -1 || u.id <= v.id) return Edge(-1);
350      return Edge(u.id * (u.id - 1) / 2 + v.id);
351    }
352
353    typedef True FindEdgeTag;
354   
355     
356    class Node {
357      friend class FullUGraphBase;
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
371
372    class Edge {
373      friend class FullUGraphBase;
374     
375    protected:
376      int id;  // _nodeNum * target + source;
377
378      Edge(int _id) : id(_id) {}
379
380    public:
381      Edge() { }
382      Edge (Invalid) { id = -1; }
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    void first(Node& node) const {
389      node.id = _nodeNum - 1;
390    }
391
392    static void next(Node& node) {
393      --node.id;
394    }
395
396    void first(Edge& edge) const {
397      edge.id = _edgeNum - 1;
398    }
399
400    static void next(Edge& edge) {
401      --edge.id;
402    }
403
404    void firstOut(Edge& edge, const Node& node) const {     
405      int src = node.id;
406      int trg = 0;
407      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
408    }
409
410    /// \todo with specialized iterators we can make faster iterating
411    void nextOut(Edge& edge) const {
412      int src = source(edge).id;
413      int trg = target(edge).id;
414      ++trg;
415      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
416    }
417
418    void firstIn(Edge& edge, const Node& node) const {
419      int src = node.id + 1;
420      int trg = node.id;
421      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
422    }
423   
424    void nextIn(Edge& edge) const {
425      int src = source(edge).id;
426      int trg = target(edge).id;
427      ++src;
428      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
429    }
430
431  };
432
433  typedef UGraphExtender<UGraphBaseExtender<FullUGraphBase> >
434  ExtendedFullUGraphBase;
435
436  /// \ingroup graphs
437  ///
438  /// \brief An undirected full graph class.
439  ///
440  /// This is a simple and fast undirected full graph implementation.
441  /// It is completely static, so you can neither add nor delete either
442  /// edges or nodes.
443  ///
444  /// The main difference beetween the \e FullGraph and \e FullUGraph class
445  /// is that this class conforms to the undirected graph concept and
446  /// it does not contain the loop edges.
447  ///
448  /// \sa FullUGraphBase
449  /// \sa FullGraph
450  ///
451  /// \author Balazs Dezso
452  class FullUGraph : public ExtendedFullUGraphBase {
453  public:
454
455    typedef ExtendedFullUGraphBase Parent;
456
457    /// \brief Constructor
458    FullUGraph() { construct(0); }
459
460    /// \brief Constructor
461    FullUGraph(int n) { construct(n); }
462
463    /// \brief Resize the graph
464    ///
465    /// Resize the graph. The function will fully destroy and build the graph.
466    /// This cause that the maps of the graph will reallocated
467    /// automatically and the previous values will be lost.
468    void resize(int n) {
469      Parent::getNotifier(Edge()).clear();
470      Parent::getNotifier(UEdge()).clear();
471      Parent::getNotifier(Node()).clear();
472      construct(n);
473      Parent::getNotifier(Node()).build();
474      Parent::getNotifier(UEdge()).build();
475      Parent::getNotifier(Edge()).build();
476    }
477  };
478
479
480  class FullBpUGraphBase {
481  protected:
482
483    int _aNodeNum;
484    int _bNodeNum;
485
486    int _edgeNum;
487
488  public:
489
490    class NodeSetError : public LogicError {
491      virtual const char* exceptionName() const {
492        return "lemon::FullBpUGraph::NodeSetError";
493      }
494    };
495 
496    class Node {
497      friend class FullBpUGraphBase;
498    protected:
499      int id;
500
501      Node(int _id) : id(_id) {}
502    public:
503      Node() {}
504      Node(Invalid) { id = -1; }
505      bool operator==(const Node i) const {return id==i.id;}
506      bool operator!=(const Node i) const {return id!=i.id;}
507      bool operator<(const Node i) const {return id<i.id;}
508    };
509
510    class Edge {
511      friend class FullBpUGraphBase;
512    protected:
513      int id;
514
515      Edge(int _id) { id = _id;}
516    public:
517      Edge() {}
518      Edge (Invalid) { id = -1; }
519      bool operator==(const Edge i) const {return id==i.id;}
520      bool operator!=(const Edge i) const {return id!=i.id;}
521      bool operator<(const Edge i) const {return id<i.id;}
522    };
523
524    void construct(int aNodeNum, int bNodeNum) {
525      _aNodeNum = aNodeNum;
526      _bNodeNum = bNodeNum;
527      _edgeNum = aNodeNum * bNodeNum;
528    }
529
530    void firstANode(Node& node) const {
531      node.id = 2 * _aNodeNum - 2;
532      if (node.id < 0) node.id = -1;
533    }
534    void nextANode(Node& node) const {
535      node.id -= 2;
536      if (node.id < 0) node.id = -1;
537    }
538
539    void firstBNode(Node& node) const {
540      node.id = 2 * _bNodeNum - 1;
541    }
542    void nextBNode(Node& node) const {
543      node.id -= 2;
544    }
545
546    void first(Node& node) const {
547      if (_aNodeNum > 0) {
548        node.id = 2 * _aNodeNum - 2;
549      } else {
550        node.id = 2 * _bNodeNum - 1;
551      }
552    }
553    void next(Node& node) const {
554      node.id -= 2;
555      if (node.id == -2) {
556        node.id = 2 * _bNodeNum - 1;
557      }
558    }
559 
560    void first(Edge& edge) const {
561      edge.id = _edgeNum - 1;
562    }
563    void next(Edge& edge) const {
564      --edge.id;
565    }
566
567    void firstOut(Edge& edge, const Node& node) const {
568      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
569      edge.id = (node.id >> 1) * _bNodeNum;
570    }
571    void nextOut(Edge& edge) const {
572      ++(edge.id);
573      if (edge.id % _bNodeNum == 0) edge.id = -1;
574    }
575
576    void firstIn(Edge& edge, const Node& node) const {
577      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
578      edge.id = (node.id >> 1);
579    }
580    void nextIn(Edge& edge) const {
581      edge.id += _bNodeNum;
582      if (edge.id >= _edgeNum) edge.id = -1;
583    }
584
585    static int id(const Node& node) {
586      return node.id;
587    }
588    static Node nodeFromId(int id) {
589      return Node(id);
590    }
591    int maxNodeId() const {
592      return _aNodeNum > _bNodeNum ?
593        _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
594    }
595 
596    static int id(const Edge& edge) {
597      return edge.id;
598    }
599    static Edge edgeFromId(int id) {
600      return Edge(id);
601    }
602    int maxEdgeId() const {
603      return _edgeNum - 1;
604    }
605 
606    static int aNodeId(const Node& node) {
607      return node.id >> 1;
608    }
609    static Node fromANodeId(int id, Node) {
610      return Node(id << 1);
611    }
612    int maxANodeId() const {
613      return _aNodeNum;
614    }
615
616    static int bNodeId(const Node& node) {
617      return node.id >> 1;
618    }
619    static Node fromBNodeId(int id) {
620      return Node((id << 1) + 1);
621    }
622    int maxBNodeId() const {
623      return _bNodeNum;
624    }
625
626    Node aNode(const Edge& edge) const {
627      return Node((edge.id / _bNodeNum) << 1);
628    }
629    Node bNode(const Edge& edge) const {
630      return Node(((edge.id % _bNodeNum) << 1) + 1);
631    }
632
633    static bool aNode(const Node& node) {
634      return (node.id & 1) == 0;
635    }
636
637    static bool bNode(const Node& node) {
638      return (node.id & 1) == 1;
639    }
640
641    static Node aNode(int index) {
642      return Node(index << 1);
643    }
644
645    static Node bNode(int index) {
646      return Node((index << 1) + 1);
647    }
648
649  };
650
651
652  typedef BpUGraphExtender< BpUGraphBaseExtender<
653    FullBpUGraphBase> > ExtendedFullBpUGraphBase;
654
655
656  /// \ingroup graphs
657  ///
658  /// \brief An undirected full bipartite graph class.
659  ///
660  /// This is a simple and fast bipartite undirected full graph implementation.
661  /// It is completely static, so you can neither add nor delete either
662  /// edges or nodes.
663  ///
664  /// \sa FullUGraphBase
665  /// \sa FullGraph
666  ///
667  /// \author Balazs Dezso
668  class FullBpUGraph :
669    public ExtendedFullBpUGraphBase {
670  public:
671
672    typedef ExtendedFullBpUGraphBase Parent;
673
674    FullBpUGraph() {
675      Parent::construct(0, 0);
676    }
677
678    FullBpUGraph(int aNodeNum, int bNodeNum) {
679      Parent::construct(aNodeNum, bNodeNum);
680    }
681
682    /// \brief Resize the graph
683    ///
684    void resize(int n, int m) {
685      Parent::getNotifier(Edge()).clear();
686      Parent::getNotifier(UEdge()).clear();
687      Parent::getNotifier(Node()).clear();
688      Parent::getNotifier(ANode()).clear();
689      Parent::getNotifier(BNode()).clear();
690      construct(n, m);
691      Parent::getNotifier(ANode()).build();
692      Parent::getNotifier(BNode()).build();
693      Parent::getNotifier(Node()).build();
694      Parent::getNotifier(UEdge()).build();
695      Parent::getNotifier(Edge()).build();
696    }
697  };
698
699} //namespace lemon
700
701
702#endif //LEMON_FULL_GRAPH_H
Note: See TracBrowser for help on using the repository browser.