COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/full_graph.h @ 2011:1a1bffa615b8

Last change on this file since 2011:1a1bffa615b8 was 1999:2ff283124dfc, checked in by Balazs Dezso, 18 years ago

Clarifing alteration observing system
It is directly connected now to a container

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#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  };
649
650
651  typedef BpUGraphExtender< BpUGraphBaseExtender<
652    FullBpUGraphBase> > ExtendedFullBpUGraphBase;
653
654
655  /// \ingroup graphs
656  ///
657  /// \brief An undirected full bipartite graph class.
658  ///
659  /// This is a simple and fast bipartite undirected full graph implementation.
660  /// It is completely static, so you can neither add nor delete either
661  /// edges or nodes.
662  ///
663  /// \sa FullUGraphBase
664  /// \sa FullGraph
665  ///
666  /// \author Balazs Dezso
667  class FullBpUGraph :
668    public ExtendedFullBpUGraphBase {
669  public:
670
671    typedef ExtendedFullBpUGraphBase Parent;
672
673    FullBpUGraph() {
674      Parent::construct(0, 0);
675    }
676
677    FullBpUGraph(int aNodeNum, int bNodeNum) {
678      Parent::construct(aNodeNum, bNodeNum);
679    }
680
681    /// \brief Resize the graph
682    ///
683    void resize(int n, int m) {
684      Parent::getNotifier(Edge()).clear();
685      Parent::getNotifier(UEdge()).clear();
686      Parent::getNotifier(Node()).clear();
687      Parent::getNotifier(ANode()).clear();
688      Parent::getNotifier(BNode()).clear();
689      construct(n, m);
690      Parent::getNotifier(ANode()).build();
691      Parent::getNotifier(BNode()).build();
692      Parent::getNotifier(Node()).build();
693      Parent::getNotifier(UEdge()).build();
694      Parent::getNotifier(Edge()).build();
695    }
696  };
697
698} //namespace lemon
699
700
701#endif //LEMON_FULL_GRAPH_H
Note: See TracBrowser for help on using the repository browser.