COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/full_graph.h @ 1987:8cd6683382e0

Last change on this file since 1987:8cd6683382e0 was 1987:8cd6683382e0, checked in by Balazs Dezso, 14 years ago

Default constructor which allocates empty graphs

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