COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/full_graph.h @ 2175:0975cad06c2b

Last change on this file since 2175:0975cad06c2b was 2162:6831fa007688, checked in by Balazs Dezso, 18 years ago

make public what() in NodeSetError?

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