COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/full_graph.h @ 1999:2ff283124dfc

Last change on this file since 1999:2ff283124dfc was 1999:2ff283124dfc, checked in by Balazs Dezso, 14 years ago

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

File size: 18.1 KB
RevLine 
[906]1/* -*- C++ -*-
2 *
[1956]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
[1359]7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[906]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 */
[591]18
[921]19#ifndef LEMON_FULL_GRAPH_H
20#define LEMON_FULL_GRAPH_H
[591]21
[983]22#include <cmath>
23
[1999]24#include <lemon/bits/base_extender.h>
[1791]25#include <lemon/bits/graph_extender.h>
[1566]26
[1993]27#include <lemon/bits/invalid.h>
28#include <lemon/bits/utility.h>
[977]29
30
[591]31///\ingroup graphs
32///\file
[1909]33///\brief FullGraph and FullUGraph classes.
[591]34
35
[921]36namespace lemon {
[591]37
[1986]38  /// \brief Base of the FullGrpah.
39  ///
40  /// Base of the FullGrpah.
[946]41  class FullGraphBase {
[1566]42    int _nodeNum;
43    int _edgeNum;
[591]44  public:
[782]45
[946]46    typedef FullGraphBase Graph;
[591]47
48    class Node;
49    class Edge;
[782]50
[591]51  public:
52
[946]53    FullGraphBase() {}
54
55
[591]56    ///Creates a full graph with \c n nodes.
[1566]57    void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
[591]58   
[977]59    typedef True NodeNumTag;
60    typedef True EdgeNumTag;
61
[1986]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
[813]78    ///Number of nodes.
[1566]79    int nodeNum() const { return _nodeNum; }
[813]80    ///Number of edges.
[1566]81    int edgeNum() const { return _edgeNum; }
[591]82
[813]83    /// Maximum node ID.
84   
85    /// Maximum node ID.
86    ///\sa id(Node)
[1791]87    int maxNodeId() const { return _nodeNum-1; }
[813]88    /// Maximum edge ID.
89   
90    /// Maximum edge ID.
91    ///\sa id(Edge)
[1791]92    int maxEdgeId() const { return _edgeNum-1; }
[591]93
[1566]94    Node source(Edge e) const { return e.id % _nodeNum; }
95    Node target(Edge e) const { return e.id / _nodeNum; }
[591]96
97
[813]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.
[946]106
107    static int id(Node v) { return v.id; }
[813]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.
[946]116    static int id(Edge e) { return e.id; }
[591]117
[1791]118    static Node nodeFromId(int id) { return Node(id);}
[1106]119   
[1791]120    static Edge edgeFromId(int id) { return Edge(id);}
[1106]121
[1566]122    typedef True FindEdgeTag;
123
[774]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.
[1566]132    Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
[946]133      return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
[774]134    }
135   
136     
[591]137    class Node {
[946]138      friend class FullGraphBase;
[591]139
140    protected:
[946]141      int id;
[1643]142      Node(int _id) : id(_id) {}
[591]143    public:
144      Node() {}
[1643]145      Node (Invalid) : id(-1) {}
[946]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;}
[591]149    };
150   
[946]151
152
153    class Edge {
154      friend class FullGraphBase;
155     
156    protected:
[1566]157      int id;  // _nodeNum * target + source;
[946]158
159      Edge(int _id) : id(_id) {}
160
[986]161      Edge(const FullGraphBase& _graph, int source, int target)
[1566]162        : id(_graph._nodeNum * target+source) {}
[591]163    public:
[946]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;}
[591]169    };
170
[946]171    void first(Node& node) const {
[1566]172      node.id = _nodeNum-1;
[946]173    }
[591]174
[946]175    static void next(Node& node) {
176      --node.id;
177    }
178
179    void first(Edge& edge) const {
[1566]180      edge.id = _edgeNum-1;
[946]181    }
182
183    static void next(Edge& edge) {
184      --edge.id;
185    }
186
187    void firstOut(Edge& edge, const Node& node) const {
[1566]188      edge.id = _edgeNum + node.id - _nodeNum;
[946]189    }
190
191    void nextOut(Edge& edge) const {
[1566]192      edge.id -= _nodeNum;
[946]193      if (edge.id < 0) edge.id = -1;
194    }
195
196    void firstIn(Edge& edge, const Node& node) const {
[1566]197      edge.id = node.id * _nodeNum;
[946]198    }
[591]199   
[946]200    void nextIn(Edge& edge) const {
201      ++edge.id;
[1566]202      if (edge.id % _nodeNum == 0) edge.id = -1;
[946]203    }
[591]204
205  };
206
[1979]207  typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
[946]208
[1566]209  /// \ingroup graphs
[951]210  ///
[1566]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  ///
[1986]220  /// \sa FullGraphBase
221  /// \sa FullUGraph
222  ///
[1566]223  /// \author Alpar Juttner
[1669]224  class FullGraph : public ExtendedFullGraphBase {
[946]225  public:
226
[1979]227    typedef ExtendedFullGraphBase Parent;
228
229    /// \brief Constructor
[1987]230    FullGraph() { construct(0); }
231
232    /// \brief Constructor
[1979]233    ///
[946]234    FullGraph(int n) { construct(n); }
[1979]235
236    /// \brief Resize the graph
237    ///
[1986]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.
[1979]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    }
[946]248  };
249
[983]250
[1986]251  /// \brief Base of the FullUGrpah.
252  ///
253  /// Base of the FullUGrpah.
[1909]254  class FullUGraphBase {
[1566]255    int _nodeNum;
256    int _edgeNum;
[983]257  public:
258
[1909]259    typedef FullUGraphBase Graph;
[983]260
261    class Node;
262    class Edge;
263
264  public:
265
[1909]266    FullUGraphBase() {}
[983]267
268
269    ///Creates a full graph with \c n nodes.
[1566]270    void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
[1986]271
272    /// \brief Returns the node with the given index.
[983]273    ///
[1986]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
[983]288    typedef True NodeNumTag;
289    typedef True EdgeNumTag;
290
291    ///Number of nodes.
[1566]292    int nodeNum() const { return _nodeNum; }
[983]293    ///Number of edges.
[1566]294    int edgeNum() const { return _edgeNum; }
[983]295
296    /// Maximum node ID.
297   
298    /// Maximum node ID.
299    ///\sa id(Node)
[1791]300    int maxNodeId() const { return _nodeNum-1; }
[983]301    /// Maximum edge ID.
302   
303    /// Maximum edge ID.
304    ///\sa id(Edge)
[1791]305    int maxEdgeId() const { return _edgeNum-1; }
[983]306
[986]307    Node source(Edge e) const {
[983]308      /// \todo we may do it faster
[1643]309      return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
[983]310    }
311
[986]312    Node target(Edge e) const {
313      int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
[1643]314      return Node(e.id - (source) * (source - 1) / 2);
[983]315    }
316
317
[1986]318    /// \brief Node ID.
319    ///
[983]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.
[1986]325    /// \return The ID of the node \c v.
[983]326
327    static int id(Node v) { return v.id; }
[1986]328
329    /// \brief Edge ID.
330    ///
[983]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
[1986]339    /// \brief Finds an edge between two nodes.
340    ///
[983]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.
[1703]347    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
[1986]348      if (prev.id != -1 || u.id <= v.id) return Edge(-1);
[1703]349      return Edge(u.id * (u.id - 1) / 2 + v.id);
[983]350    }
[1703]351
352    typedef True FindEdgeTag;
[983]353   
354     
355    class Node {
[1909]356      friend class FullUGraphBase;
[983]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 {
[1909]372      friend class FullUGraphBase;
[983]373     
374    protected:
[1566]375      int id;  // _nodeNum * target + source;
[983]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 {
[1703]388      node.id = _nodeNum - 1;
[983]389    }
390
391    static void next(Node& node) {
392      --node.id;
393    }
394
395    void first(Edge& edge) const {
[1703]396      edge.id = _edgeNum - 1;
[983]397    }
398
399    static void next(Edge& edge) {
400      --edge.id;
401    }
402
403    void firstOut(Edge& edge, const Node& node) const {     
[1703]404      int src = node.id;
405      int trg = 0;
406      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
[983]407    }
408
409    /// \todo with specialized iterators we can make faster iterating
[1703]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);
[983]415    }
416
417    void firstIn(Edge& edge, const Node& node) const {
[1703]418      int src = node.id + 1;
419      int trg = node.id;
420      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
[983]421    }
422   
[1703]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);
[983]428    }
429
430  };
431
[1979]432  typedef UGraphExtender<UGraphBaseExtender<FullUGraphBase> >
433  ExtendedFullUGraphBase;
[1555]434
[1566]435  /// \ingroup graphs
436  ///
437  /// \brief An undirected full graph class.
438  ///
[1726]439  /// This is a simple and fast undirected full graph implementation.
[1566]440  /// It is completely static, so you can neither add nor delete either
441  /// edges or nodes.
442  ///
[1909]443  /// The main difference beetween the \e FullGraph and \e FullUGraph class
[1566]444  /// is that this class conforms to the undirected graph concept and
[1726]445  /// it does not contain the loop edges.
[1566]446  ///
[1986]447  /// \sa FullUGraphBase
[1566]448  /// \sa FullGraph
449  ///
450  /// \author Balazs Dezso
[1909]451  class FullUGraph : public ExtendedFullUGraphBase {
[1566]452  public:
[1979]453
454    typedef ExtendedFullUGraphBase Parent;
455
456    /// \brief Constructor
[1987]457    FullUGraph() { construct(0); }
458
459    /// \brief Constructor
[1909]460    FullUGraph(int n) { construct(n); }
[1979]461
462    /// \brief Resize the graph
463    ///
[1986]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.
[1979]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    }
[1566]476  };
[591]477
[1820]478
[1910]479  class FullBpUGraphBase {
[1820]480  protected:
481
[1910]482    int _aNodeNum;
483    int _bNodeNum;
[1820]484
485    int _edgeNum;
486
487  public:
488
489    class NodeSetError : public LogicError {
490      virtual const char* exceptionName() const {
[1910]491        return "lemon::FullBpUGraph::NodeSetError";
[1820]492      }
493    };
494 
495    class Node {
[1910]496      friend class FullBpUGraphBase;
[1820]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 {
[1910]510      friend class FullBpUGraphBase;
[1820]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
[1910]523    void construct(int aNodeNum, int bNodeNum) {
524      _aNodeNum = aNodeNum;
525      _bNodeNum = bNodeNum;
526      _edgeNum = aNodeNum * bNodeNum;
[1820]527    }
528
[1910]529    void firstANode(Node& node) const {
530      node.id = 2 * _aNodeNum - 2;
[1820]531      if (node.id < 0) node.id = -1;
532    }
[1910]533    void nextANode(Node& node) const {
[1820]534      node.id -= 2;
535      if (node.id < 0) node.id = -1;
536    }
537
[1910]538    void firstBNode(Node& node) const {
539      node.id = 2 * _bNodeNum - 1;
[1820]540    }
[1910]541    void nextBNode(Node& node) const {
[1820]542      node.id -= 2;
543    }
544
545    void first(Node& node) const {
[1910]546      if (_aNodeNum > 0) {
547        node.id = 2 * _aNodeNum - 2;
[1820]548      } else {
[1910]549        node.id = 2 * _bNodeNum - 1;
[1820]550      }
551    }
552    void next(Node& node) const {
553      node.id -= 2;
554      if (node.id == -2) {
[1910]555        node.id = 2 * _bNodeNum - 1;
[1820]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
[1910]566    void firstOut(Edge& edge, const Node& node) const {
[1820]567      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
[1910]568      edge.id = (node.id >> 1) * _bNodeNum;
[1820]569    }
[1910]570    void nextOut(Edge& edge) const {
[1820]571      ++(edge.id);
[1910]572      if (edge.id % _bNodeNum == 0) edge.id = -1;
[1820]573    }
574
[1910]575    void firstIn(Edge& edge, const Node& node) const {
[1820]576      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
577      edge.id = (node.id >> 1);
578    }
[1910]579    void nextIn(Edge& edge) const {
580      edge.id += _bNodeNum;
[1820]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 {
[1910]591      return _aNodeNum > _bNodeNum ?
592        _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
[1820]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 
[1910]605    static int aNodeId(const Node& node) {
[1820]606      return node.id >> 1;
607    }
[1995]608    static Node fromANodeId(int id) {
[1820]609      return Node(id << 1);
610    }
[1910]611    int maxANodeId() const {
612      return _aNodeNum;
[1820]613    }
614
[1910]615    static int bNodeId(const Node& node) {
[1820]616      return node.id >> 1;
617    }
[1910]618    static Node fromBNodeId(int id) {
[1820]619      return Node((id << 1) + 1);
620    }
[1910]621    int maxBNodeId() const {
622      return _bNodeNum;
[1820]623    }
624
[1910]625    Node aNode(const Edge& edge) const {
626      return Node((edge.id / _bNodeNum) << 1);
[1820]627    }
[1910]628    Node bNode(const Edge& edge) const {
629      return Node(((edge.id % _bNodeNum) << 1) + 1);
[1820]630    }
631
[1910]632    static bool aNode(const Node& node) {
[1820]633      return (node.id & 1) == 0;
634    }
635
[1910]636    static bool bNode(const Node& node) {
[1820]637      return (node.id & 1) == 1;
638    }
639
[1910]640    static Node aNode(int index) {
[1820]641      return Node(index << 1);
642    }
643
[1910]644    static Node bNode(int index) {
[1820]645      return Node((index << 1) + 1);
646    }
647
648  };
649
650
[1979]651  typedef BpUGraphExtender< BpUGraphBaseExtender<
652    FullBpUGraphBase> > ExtendedFullBpUGraphBase;
[1820]653
654
[1910]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  ///
[1986]663  /// \sa FullUGraphBase
[1910]664  /// \sa FullGraph
665  ///
666  /// \author Balazs Dezso
667  class FullBpUGraph :
668    public ExtendedFullBpUGraphBase {
[1820]669  public:
[1979]670
[1910]671    typedef ExtendedFullBpUGraphBase Parent;
[1979]672
[1987]673    FullBpUGraph() {
674      Parent::construct(0, 0);
675    }
676
[1910]677    FullBpUGraph(int aNodeNum, int bNodeNum) {
678      Parent::construct(aNodeNum, bNodeNum);
[1820]679    }
[1987]680
[1979]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();
[1987]687      Parent::getNotifier(ANode()).clear();
688      Parent::getNotifier(BNode()).clear();
[1979]689      construct(n, m);
[1987]690      Parent::getNotifier(ANode()).build();
691      Parent::getNotifier(BNode()).build();
[1979]692      Parent::getNotifier(Node()).build();
693      Parent::getNotifier(UEdge()).build();
694      Parent::getNotifier(Edge()).build();
695    }
[1820]696  };
697
[921]698} //namespace lemon
[591]699
700
[921]701#endif //LEMON_FULL_GRAPH_H
Note: See TracBrowser for help on using the repository browser.