COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/full_graph.h @ 2031:080d51024ac5

Last change on this file since 2031:080d51024ac5 was 2031:080d51024ac5, checked in by Balazs Dezso, 14 years ago

Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.

Some bugfix in the adaptors

New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.

File size: 18.4 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::StaticGraph "StaticGraph" concept
218  /// \sa concept::StaticGraph.
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    Node source(Edge e) const {
308      /// \todo we may do it faster
309      return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
310    }
311
312    Node target(Edge e) const {
313      int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
314      return Node(e.id - (source) * (source - 1) / 2);
315    }
316
317
318    /// \brief Node ID.
319    ///
320    /// The ID of a valid Node is a nonnegative integer not greater than
321    /// \ref maxNodeId(). The range of the ID's is not surely continuous
322    /// and the greatest node ID can be actually less then \ref maxNodeId().
323    ///
324    /// The ID of the \ref INVALID node is -1.
325    /// \return The ID of the node \c v.
326
327    static int id(Node v) { return v.id; }
328
329    /// \brief Edge ID.
330    ///
331    /// The ID of a valid Edge is a nonnegative integer not greater than
332    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
333    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
334    ///
335    /// The ID of the \ref INVALID edge is -1.
336    ///\return The ID of the edge \c e.
337    static int id(Edge e) { return e.id; }
338
339    /// \brief Finds an edge between two nodes.
340    ///
341    /// Finds an edge from node \c u to node \c v.
342    ///
343    /// If \c prev is \ref INVALID (this is the default value), then
344    /// It finds the first edge from \c u to \c v. Otherwise it looks for
345    /// the next edge from \c u to \c v after \c prev.
346    /// \return The found edge or INVALID if there is no such an edge.
347    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
348      if (prev.id != -1 || u.id <= v.id) return Edge(-1);
349      return Edge(u.id * (u.id - 1) / 2 + v.id);
350    }
351
352    typedef True FindEdgeTag;
353   
354     
355    class Node {
356      friend class FullUGraphBase;
357
358    protected:
359      int id;
360      Node(int _id) { id = _id;}
361    public:
362      Node() {}
363      Node (Invalid) { id = -1; }
364      bool operator==(const Node node) const {return id == node.id;}
365      bool operator!=(const Node node) const {return id != node.id;}
366      bool operator<(const Node node) const {return id < node.id;}
367    };
368   
369
370
371    class Edge {
372      friend class FullUGraphBase;
373     
374    protected:
375      int id;  // _nodeNum * target + source;
376
377      Edge(int _id) : id(_id) {}
378
379    public:
380      Edge() { }
381      Edge (Invalid) { id = -1; }
382      bool operator==(const Edge edge) const {return id == edge.id;}
383      bool operator!=(const Edge edge) const {return id != edge.id;}
384      bool operator<(const Edge edge) const {return id < edge.id;}
385    };
386
387    void first(Node& node) const {
388      node.id = _nodeNum - 1;
389    }
390
391    static void next(Node& node) {
392      --node.id;
393    }
394
395    void first(Edge& edge) const {
396      edge.id = _edgeNum - 1;
397    }
398
399    static void next(Edge& edge) {
400      --edge.id;
401    }
402
403    void firstOut(Edge& edge, const Node& node) const {     
404      int src = node.id;
405      int trg = 0;
406      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
407    }
408
409    /// \todo with specialized iterators we can make faster iterating
410    void nextOut(Edge& edge) const {
411      int src = source(edge).id;
412      int trg = target(edge).id;
413      ++trg;
414      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
415    }
416
417    void firstIn(Edge& edge, const Node& node) const {
418      int src = node.id + 1;
419      int trg = node.id;
420      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
421    }
422   
423    void nextIn(Edge& edge) const {
424      int src = source(edge).id;
425      int trg = target(edge).id;
426      ++src;
427      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
428    }
429
430  };
431
432  typedef UGraphExtender<UGraphBaseExtender<FullUGraphBase> >
433  ExtendedFullUGraphBase;
434
435  /// \ingroup graphs
436  ///
437  /// \brief An undirected full graph class.
438  ///
439  /// This is a simple and fast undirected full graph implementation.
440  /// It is completely static, so you can neither add nor delete either
441  /// edges or nodes.
442  ///
443  /// The main difference beetween the \e FullGraph and \e FullUGraph class
444  /// is that this class conforms to the undirected graph concept and
445  /// it does not contain the loop edges.
446  ///
447  /// \sa FullUGraphBase
448  /// \sa FullGraph
449  ///
450  /// \author Balazs Dezso
451  class FullUGraph : public ExtendedFullUGraphBase {
452  public:
453
454    typedef ExtendedFullUGraphBase Parent;
455
456    /// \brief Constructor
457    FullUGraph() { construct(0); }
458
459    /// \brief Constructor
460    FullUGraph(int n) { construct(n); }
461
462    /// \brief Resize the graph
463    ///
464    /// Resize the graph. The function will fully destroy and build the graph.
465    /// This cause that the maps of the graph will reallocated
466    /// automatically and the previous values will be lost.
467    void resize(int n) {
468      Parent::getNotifier(Edge()).clear();
469      Parent::getNotifier(UEdge()).clear();
470      Parent::getNotifier(Node()).clear();
471      construct(n);
472      Parent::getNotifier(Node()).build();
473      Parent::getNotifier(UEdge()).build();
474      Parent::getNotifier(Edge()).build();
475    }
476  };
477
478
479  class FullBpUGraphBase {
480  protected:
481
482    int _aNodeNum;
483    int _bNodeNum;
484
485    int _edgeNum;
486
487  public:
488
489    class NodeSetError : public LogicError {
490      virtual const char* exceptionName() const {
491        return "lemon::FullBpUGraph::NodeSetError";
492      }
493    };
494 
495    class Node {
496      friend class FullBpUGraphBase;
497    protected:
498      int id;
499
500      Node(int _id) : id(_id) {}
501    public:
502      Node() {}
503      Node(Invalid) { id = -1; }
504      bool operator==(const Node i) const {return id==i.id;}
505      bool operator!=(const Node i) const {return id!=i.id;}
506      bool operator<(const Node i) const {return id<i.id;}
507    };
508
509    class Edge {
510      friend class FullBpUGraphBase;
511    protected:
512      int id;
513
514      Edge(int _id) { id = _id;}
515    public:
516      Edge() {}
517      Edge (Invalid) { id = -1; }
518      bool operator==(const Edge i) const {return id==i.id;}
519      bool operator!=(const Edge i) const {return id!=i.id;}
520      bool operator<(const Edge i) const {return id<i.id;}
521    };
522
523    void construct(int aNodeNum, int bNodeNum) {
524      _aNodeNum = aNodeNum;
525      _bNodeNum = bNodeNum;
526      _edgeNum = aNodeNum * bNodeNum;
527    }
528
529    void firstANode(Node& node) const {
530      node.id = 2 * _aNodeNum - 2;
531      if (node.id < 0) node.id = -1;
532    }
533    void nextANode(Node& node) const {
534      node.id -= 2;
535      if (node.id < 0) node.id = -1;
536    }
537
538    void firstBNode(Node& node) const {
539      node.id = 2 * _bNodeNum - 1;
540    }
541    void nextBNode(Node& node) const {
542      node.id -= 2;
543    }
544
545    void first(Node& node) const {
546      if (_aNodeNum > 0) {
547        node.id = 2 * _aNodeNum - 2;
548      } else {
549        node.id = 2 * _bNodeNum - 1;
550      }
551    }
552    void next(Node& node) const {
553      node.id -= 2;
554      if (node.id == -2) {
555        node.id = 2 * _bNodeNum - 1;
556      }
557    }
558 
559    void first(Edge& edge) const {
560      edge.id = _edgeNum - 1;
561    }
562    void next(Edge& edge) const {
563      --edge.id;
564    }
565
566    void firstOut(Edge& edge, const Node& node) const {
567      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
568      edge.id = (node.id >> 1) * _bNodeNum;
569    }
570    void nextOut(Edge& edge) const {
571      ++(edge.id);
572      if (edge.id % _bNodeNum == 0) edge.id = -1;
573    }
574
575    void firstIn(Edge& edge, const Node& node) const {
576      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
577      edge.id = (node.id >> 1);
578    }
579    void nextIn(Edge& edge) const {
580      edge.id += _bNodeNum;
581      if (edge.id >= _edgeNum) edge.id = -1;
582    }
583
584    static int id(const Node& node) {
585      return node.id;
586    }
587    static Node nodeFromId(int id) {
588      return Node(id);
589    }
590    int maxNodeId() const {
591      return _aNodeNum > _bNodeNum ?
592        _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
593    }
594 
595    static int id(const Edge& edge) {
596      return edge.id;
597    }
598    static Edge edgeFromId(int id) {
599      return Edge(id);
600    }
601    int maxEdgeId() const {
602      return _edgeNum - 1;
603    }
604 
605    static int aNodeId(const Node& node) {
606      return node.id >> 1;
607    }
608    static Node fromANodeId(int id) {
609      return Node(id << 1);
610    }
611    int maxANodeId() const {
612      return _aNodeNum;
613    }
614
615    static int bNodeId(const Node& node) {
616      return node.id >> 1;
617    }
618    static Node fromBNodeId(int id) {
619      return Node((id << 1) + 1);
620    }
621    int maxBNodeId() const {
622      return _bNodeNum;
623    }
624
625    Node aNode(const Edge& edge) const {
626      return Node((edge.id / _bNodeNum) << 1);
627    }
628    Node bNode(const Edge& edge) const {
629      return Node(((edge.id % _bNodeNum) << 1) + 1);
630    }
631
632    static bool aNode(const Node& node) {
633      return (node.id & 1) == 0;
634    }
635
636    static bool bNode(const Node& node) {
637      return (node.id & 1) == 1;
638    }
639
640    static Node aNode(int index) {
641      return Node(index << 1);
642    }
643
644    static Node bNode(int index) {
645      return Node((index << 1) + 1);
646    }
647
648    typedef True NodeNumTag;
649    int nodeNum() const { return _aNodeNum + _bNodeNum; }
650    int aNodeNum() const { return _aNodeNum; }
651    int bNodeNum() const { return _bNodeNum; }
652
653    typedef True EdgeNumTag;
654    int edgeNum() const { return _edgeNum; }
655
656  };
657
658
659  typedef BpUGraphExtender< BpUGraphBaseExtender<
660    FullBpUGraphBase> > ExtendedFullBpUGraphBase;
661
662
663  /// \ingroup graphs
664  ///
665  /// \brief An undirected full bipartite graph class.
666  ///
667  /// This is a simple and fast bipartite undirected full graph implementation.
668  /// It is completely static, so you can neither add nor delete either
669  /// edges or nodes.
670  ///
671  /// \sa FullUGraphBase
672  /// \sa FullGraph
673  ///
674  /// \author Balazs Dezso
675  class FullBpUGraph :
676    public ExtendedFullBpUGraphBase {
677  public:
678
679    typedef ExtendedFullBpUGraphBase Parent;
680
681    FullBpUGraph() {
682      Parent::construct(0, 0);
683    }
684
685    FullBpUGraph(int aNodeNum, int bNodeNum) {
686      Parent::construct(aNodeNum, bNodeNum);
687    }
688
689    /// \brief Resize the graph
690    ///
691    void resize(int n, int m) {
692      Parent::getNotifier(Edge()).clear();
693      Parent::getNotifier(UEdge()).clear();
694      Parent::getNotifier(Node()).clear();
695      Parent::getNotifier(ANode()).clear();
696      Parent::getNotifier(BNode()).clear();
697      construct(n, m);
698      Parent::getNotifier(ANode()).build();
699      Parent::getNotifier(BNode()).build();
700      Parent::getNotifier(Node()).build();
701      Parent::getNotifier(UEdge()).build();
702      Parent::getNotifier(Edge()).build();
703    }
704  };
705
706} //namespace lemon
707
708
709#endif //LEMON_FULL_GRAPH_H
Note: See TracBrowser for help on using the repository browser.