lemon/full_graph.h
author ladanyi
Wed, 21 Jun 2006 08:35:23 +0000
changeset 2103 a979fcdda073
parent 2061 7ab148f53d66
child 2111 ea1fa1bc3f6d
permissions -rw-r--r--
Exclude the gui from the build.
     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 
    36 namespace 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     /// \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       virtual const char* exceptionName() const { 
   503 	return "lemon::FullBpUGraph::NodeSetError";
   504       }
   505     };
   506   
   507     class Node {
   508       friend class FullBpUGraphBase;
   509     protected:
   510       int id;
   511 
   512       Node(int _id) : id(_id) {}
   513     public:
   514       Node() {}
   515       Node(Invalid) { id = -1; }
   516       bool operator==(const Node i) const {return id==i.id;}
   517       bool operator!=(const Node i) const {return id!=i.id;}
   518       bool operator<(const Node i) const {return id<i.id;}
   519     };
   520 
   521     class UEdge {
   522       friend class FullBpUGraphBase;
   523     protected:
   524       int id;
   525 
   526       UEdge(int _id) { id = _id;}
   527     public:
   528       UEdge() {}
   529       UEdge (Invalid) { id = -1; }
   530       bool operator==(const UEdge i) const {return id==i.id;}
   531       bool operator!=(const UEdge i) const {return id!=i.id;}
   532       bool operator<(const UEdge i) const {return id<i.id;}
   533     };
   534 
   535     void construct(int aNodeNum, int bNodeNum) {
   536       _aNodeNum = aNodeNum;
   537       _bNodeNum = bNodeNum;
   538       _edgeNum = aNodeNum * bNodeNum;
   539     }
   540 
   541     void firstANode(Node& node) const {
   542       node.id = 2 * _aNodeNum - 2;
   543       if (node.id < 0) node.id = -1; 
   544     }
   545     void nextANode(Node& node) const {
   546       node.id -= 2;
   547       if (node.id < 0) node.id = -1; 
   548     }
   549 
   550     void firstBNode(Node& node) const {
   551       node.id = 2 * _bNodeNum - 1;
   552     }
   553     void nextBNode(Node& node) const {
   554       node.id -= 2;
   555     }
   556 
   557     void first(Node& node) const {
   558       if (_aNodeNum > 0) {
   559 	node.id = 2 * _aNodeNum - 2;
   560       } else {
   561 	node.id = 2 * _bNodeNum - 1;
   562       }
   563     }
   564     void next(Node& node) const {
   565       node.id -= 2;
   566       if (node.id == -2) {
   567 	node.id = 2 * _bNodeNum - 1;
   568       }
   569     }
   570   
   571     void first(UEdge& edge) const {
   572       edge.id = _edgeNum - 1;
   573     }
   574     void next(UEdge& edge) const {
   575       --edge.id;
   576     }
   577 
   578     void firstFromANode(UEdge& edge, const Node& node) const {
   579       LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
   580       edge.id = (node.id >> 1) * _bNodeNum;
   581     }
   582     void nextFromANode(UEdge& edge) const {
   583       ++(edge.id);
   584       if (edge.id % _bNodeNum == 0) edge.id = -1;
   585     }
   586 
   587     void firstFromBNode(UEdge& edge, const Node& node) const {
   588       LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
   589       edge.id = (node.id >> 1);
   590     }
   591     void nextFromBNode(UEdge& edge) const {
   592       edge.id += _bNodeNum;
   593       if (edge.id >= _edgeNum) edge.id = -1;
   594     }
   595 
   596     static int id(const Node& node) {
   597       return node.id;
   598     }
   599     static Node nodeFromId(int id) {
   600       return Node(id);
   601     }
   602     int maxNodeId() const {
   603       return _aNodeNum > _bNodeNum ? 
   604 	_aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
   605     }
   606   
   607     static int id(const UEdge& edge) {
   608       return edge.id;
   609     }
   610     static UEdge uEdgeFromId(int id) {
   611       return UEdge(id);
   612     }
   613     int maxUEdgeId() const {
   614       return _edgeNum - 1;
   615     }
   616   
   617     static int aNodeId(const Node& node) {
   618       return node.id >> 1;
   619     }
   620     static Node fromANodeId(int id) {
   621       return Node(id << 1);
   622     }
   623     int maxANodeId() const {
   624       return _aNodeNum;
   625     }
   626 
   627     static int bNodeId(const Node& node) {
   628       return node.id >> 1;
   629     }
   630     static Node fromBNodeId(int id) {
   631       return Node((id << 1) + 1);
   632     }
   633     int maxBNodeId() const {
   634       return _bNodeNum;
   635     }
   636 
   637     Node aNode(const UEdge& edge) const {
   638       return Node((edge.id / _bNodeNum) << 1);
   639     }
   640     Node bNode(const UEdge& edge) const {
   641       return Node(((edge.id % _bNodeNum) << 1) + 1);
   642     }
   643 
   644     static bool aNode(const Node& node) {
   645       return (node.id & 1) == 0;
   646     }
   647 
   648     static bool bNode(const Node& node) {
   649       return (node.id & 1) == 1;
   650     }
   651 
   652     static Node aNode(int index) {
   653       return Node(index << 1);
   654     }
   655 
   656     static Node bNode(int index) {
   657       return Node((index << 1) + 1);
   658     }
   659 
   660     typedef True NodeNumTag;
   661     int nodeNum() const { return _aNodeNum + _bNodeNum; }
   662     int aNodeNum() const { return _aNodeNum; }
   663     int bNodeNum() const { return _bNodeNum; }
   664 
   665     typedef True EdgeNumTag;
   666     int uEdgeNum() const { return _edgeNum; }
   667 
   668   };
   669 
   670 
   671   typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
   672 
   673 
   674   /// \ingroup graphs
   675   ///
   676   /// \brief An undirected full bipartite graph class.
   677   ///
   678   /// This is a simple and fast bipartite undirected full graph implementation.
   679   /// It is completely static, so you can neither add nor delete either
   680   /// edges or nodes.
   681   ///
   682   /// \sa FullUGraphBase
   683   /// \sa FullGraph
   684   ///
   685   /// \author Balazs Dezso
   686   class FullBpUGraph : 
   687     public ExtendedFullBpUGraphBase {
   688   public:
   689 
   690     typedef ExtendedFullBpUGraphBase Parent;
   691 
   692     FullBpUGraph() {
   693       Parent::construct(0, 0);
   694     }
   695 
   696     FullBpUGraph(int aNodeNum, int bNodeNum) {
   697       Parent::construct(aNodeNum, bNodeNum);
   698     }
   699 
   700     /// \brief Resize the graph
   701     ///
   702     void resize(int n, int m) {
   703       Parent::getNotifier(Edge()).clear();
   704       Parent::getNotifier(UEdge()).clear();
   705       Parent::getNotifier(Node()).clear();
   706       Parent::getNotifier(ANode()).clear();
   707       Parent::getNotifier(BNode()).clear();
   708       construct(n, m);
   709       Parent::getNotifier(ANode()).build();
   710       Parent::getNotifier(BNode()).build();
   711       Parent::getNotifier(Node()).build();
   712       Parent::getNotifier(UEdge()).build();
   713       Parent::getNotifier(Edge()).build();
   714     }
   715   };
   716 
   717 } //namespace lemon
   718 
   719 
   720 #endif //LEMON_FULL_GRAPH_H