lemon/full_graph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 19 Feb 2010 14:08:32 +0100
changeset 844 a6eb9698c321
parent 780 580af8cf2f6a
child 877 141f9c0db4a3
permissions -rw-r--r--
Support tolerance technique for BellmanFord (#51)

A new operation traits class BellmanFordToleranceOperationTraits
is introduced, which uses the tolerance technique in its less()
function. This class can be used with the SetOperationTraits
named template parameter.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     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 <lemon/core.h>
    23 #include <lemon/bits/graph_extender.h>
    24 
    25 ///\ingroup graphs
    26 ///\file
    27 ///\brief FullDigraph and FullGraph classes.
    28 
    29 namespace lemon {
    30 
    31   class FullDigraphBase {
    32   public:
    33 
    34     typedef FullDigraphBase Digraph;
    35 
    36     class Node;
    37     class Arc;
    38 
    39   protected:
    40 
    41     int _node_num;
    42     int _arc_num;
    43 
    44     FullDigraphBase() {}
    45 
    46     void construct(int n) { _node_num = n; _arc_num = n * n; }
    47 
    48   public:
    49 
    50     typedef True NodeNumTag;
    51     typedef True ArcNumTag;
    52 
    53     Node operator()(int ix) const { return Node(ix); }
    54     static int index(const Node& node) { return node._id; }
    55 
    56     Arc arc(const Node& s, const Node& t) const {
    57       return Arc(s._id * _node_num + t._id);
    58     }
    59 
    60     int nodeNum() const { return _node_num; }
    61     int arcNum() const { return _arc_num; }
    62 
    63     int maxNodeId() const { return _node_num - 1; }
    64     int maxArcId() const { return _arc_num - 1; }
    65 
    66     Node source(Arc arc) const { return arc._id / _node_num; }
    67     Node target(Arc arc) const { return arc._id % _node_num; }
    68 
    69     static int id(Node node) { return node._id; }
    70     static int id(Arc arc) { return arc._id; }
    71 
    72     static Node nodeFromId(int id) { return Node(id);}
    73     static Arc arcFromId(int id) { return Arc(id);}
    74 
    75     typedef True FindArcTag;
    76 
    77     Arc findArc(Node s, Node t, Arc prev = INVALID) const {
    78       return prev == INVALID ? arc(s, t) : INVALID;
    79     }
    80 
    81     class Node {
    82       friend class FullDigraphBase;
    83 
    84     protected:
    85       int _id;
    86       Node(int id) : _id(id) {}
    87     public:
    88       Node() {}
    89       Node (Invalid) : _id(-1) {}
    90       bool operator==(const Node node) const {return _id == node._id;}
    91       bool operator!=(const Node node) const {return _id != node._id;}
    92       bool operator<(const Node node) const {return _id < node._id;}
    93     };
    94 
    95     class Arc {
    96       friend class FullDigraphBase;
    97 
    98     protected:
    99       int _id;  // _node_num * source + target;
   100 
   101       Arc(int id) : _id(id) {}
   102 
   103     public:
   104       Arc() { }
   105       Arc (Invalid) { _id = -1; }
   106       bool operator==(const Arc arc) const {return _id == arc._id;}
   107       bool operator!=(const Arc arc) const {return _id != arc._id;}
   108       bool operator<(const Arc arc) const {return _id < arc._id;}
   109     };
   110 
   111     void first(Node& node) const {
   112       node._id = _node_num - 1;
   113     }
   114 
   115     static void next(Node& node) {
   116       --node._id;
   117     }
   118 
   119     void first(Arc& arc) const {
   120       arc._id = _arc_num - 1;
   121     }
   122 
   123     static void next(Arc& arc) {
   124       --arc._id;
   125     }
   126 
   127     void firstOut(Arc& arc, const Node& node) const {
   128       arc._id = (node._id + 1) * _node_num - 1;
   129     }
   130 
   131     void nextOut(Arc& arc) const {
   132       if (arc._id % _node_num == 0) arc._id = 0;
   133       --arc._id;
   134     }
   135 
   136     void firstIn(Arc& arc, const Node& node) const {
   137       arc._id = _arc_num + node._id - _node_num;
   138     }
   139 
   140     void nextIn(Arc& arc) const {
   141       arc._id -= _node_num;
   142       if (arc._id < 0) arc._id = -1;
   143     }
   144 
   145   };
   146 
   147   typedef DigraphExtender<FullDigraphBase> ExtendedFullDigraphBase;
   148 
   149   /// \ingroup graphs
   150   ///
   151   /// \brief A directed full graph class.
   152   ///
   153   /// FullDigraph is a simple and fast implmenetation of directed full
   154   /// (complete) graphs. It contains an arc from each node to each node
   155   /// (including a loop for each node), therefore the number of arcs
   156   /// is the square of the number of nodes.
   157   /// This class is completely static and it needs constant memory space.
   158   /// Thus you can neither add nor delete nodes or arcs, however
   159   /// the structure can be resized using resize().
   160   ///
   161   /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
   162   /// Most of its member functions and nested classes are documented
   163   /// only in the concept class.
   164   ///
   165   /// This class provides constant time counting for nodes and arcs.
   166   ///
   167   /// \note FullDigraph and FullGraph classes are very similar,
   168   /// but there are two differences. While this class conforms only
   169   /// to the \ref concepts::Digraph "Digraph" concept, FullGraph
   170   /// conforms to the \ref concepts::Graph "Graph" concept,
   171   /// moreover FullGraph does not contain a loop for each
   172   /// node as this class does.
   173   ///
   174   /// \sa FullGraph
   175   class FullDigraph : public ExtendedFullDigraphBase {
   176     typedef ExtendedFullDigraphBase Parent;
   177 
   178   public:
   179 
   180     /// \brief Default constructor.
   181     ///
   182     /// Default constructor. The number of nodes and arcs will be zero.
   183     FullDigraph() { construct(0); }
   184 
   185     /// \brief Constructor
   186     ///
   187     /// Constructor.
   188     /// \param n The number of the nodes.
   189     FullDigraph(int n) { construct(n); }
   190 
   191     /// \brief Resizes the digraph
   192     ///
   193     /// This function resizes the digraph. It fully destroys and
   194     /// rebuilds the structure, therefore the maps of the digraph will be
   195     /// reallocated automatically and the previous values will be lost.
   196     void resize(int n) {
   197       Parent::notifier(Arc()).clear();
   198       Parent::notifier(Node()).clear();
   199       construct(n);
   200       Parent::notifier(Node()).build();
   201       Parent::notifier(Arc()).build();
   202     }
   203 
   204     /// \brief Returns the node with the given index.
   205     ///
   206     /// Returns the node with the given index. Since this structure is 
   207     /// completely static, the nodes can be indexed with integers from
   208     /// the range <tt>[0..nodeNum()-1]</tt>.
   209     /// The index of a node is the same as its ID.
   210     /// \sa index()
   211     Node operator()(int ix) const { return Parent::operator()(ix); }
   212 
   213     /// \brief Returns the index of the given node.
   214     ///
   215     /// Returns the index of the given node. Since this structure is 
   216     /// completely static, the nodes can be indexed with integers from
   217     /// the range <tt>[0..nodeNum()-1]</tt>.
   218     /// The index of a node is the same as its ID.
   219     /// \sa operator()()
   220     static int index(const Node& node) { return Parent::index(node); }
   221 
   222     /// \brief Returns the arc connecting the given nodes.
   223     ///
   224     /// Returns the arc connecting the given nodes.
   225     Arc arc(Node u, Node v) const {
   226       return Parent::arc(u, v);
   227     }
   228 
   229     /// \brief Number of nodes.
   230     int nodeNum() const { return Parent::nodeNum(); }
   231     /// \brief Number of arcs.
   232     int arcNum() const { return Parent::arcNum(); }
   233   };
   234 
   235 
   236   class FullGraphBase {
   237   public:
   238 
   239     typedef FullGraphBase Graph;
   240 
   241     class Node;
   242     class Arc;
   243     class Edge;
   244 
   245   protected:
   246 
   247     int _node_num;
   248     int _edge_num;
   249 
   250     FullGraphBase() {}
   251 
   252     void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }
   253 
   254     int _uid(int e) const {
   255       int u = e / _node_num;
   256       int v = e % _node_num;
   257       return u < v ? u : _node_num - 2 - u;
   258     }
   259 
   260     int _vid(int e) const {
   261       int u = e / _node_num;
   262       int v = e % _node_num;
   263       return u < v ? v : _node_num - 1 - v;
   264     }
   265 
   266     void _uvid(int e, int& u, int& v) const {
   267       u = e / _node_num;
   268       v = e % _node_num;
   269       if  (u >= v) {
   270         u = _node_num - 2 - u;
   271         v = _node_num - 1 - v;
   272       }
   273     }
   274 
   275     void _stid(int a, int& s, int& t) const {
   276       if ((a & 1) == 1) {
   277         _uvid(a >> 1, s, t);
   278       } else {
   279         _uvid(a >> 1, t, s);
   280       }
   281     }
   282 
   283     int _eid(int u, int v) const {
   284       if (u < (_node_num - 1) / 2) {
   285         return u * _node_num + v;
   286       } else {
   287         return (_node_num - 1 - u) * _node_num - v - 1;
   288       }
   289     }
   290 
   291   public:
   292 
   293     Node operator()(int ix) const { return Node(ix); }
   294     static int index(const Node& node) { return node._id; }
   295 
   296     Edge edge(const Node& u, const Node& v) const {
   297       if (u._id < v._id) {
   298         return Edge(_eid(u._id, v._id));
   299       } else if (u._id != v._id) {
   300         return Edge(_eid(v._id, u._id));
   301       } else {
   302         return INVALID;
   303       }
   304     }
   305 
   306     Arc arc(const Node& s, const Node& t) const {
   307       if (s._id < t._id) {
   308         return Arc((_eid(s._id, t._id) << 1) | 1);
   309       } else if (s._id != t._id) {
   310         return Arc(_eid(t._id, s._id) << 1);
   311       } else {
   312         return INVALID;
   313       }
   314     }
   315 
   316     typedef True NodeNumTag;
   317     typedef True ArcNumTag;
   318     typedef True EdgeNumTag;
   319 
   320     int nodeNum() const { return _node_num; }
   321     int arcNum() const { return 2 * _edge_num; }
   322     int edgeNum() const { return _edge_num; }
   323 
   324     static int id(Node node) { return node._id; }
   325     static int id(Arc arc) { return arc._id; }
   326     static int id(Edge edge) { return edge._id; }
   327 
   328     int maxNodeId() const { return _node_num-1; }
   329     int maxArcId() const { return 2 * _edge_num-1; }
   330     int maxEdgeId() const { return _edge_num-1; }
   331 
   332     static Node nodeFromId(int id) { return Node(id);}
   333     static Arc arcFromId(int id) { return Arc(id);}
   334     static Edge edgeFromId(int id) { return Edge(id);}
   335 
   336     Node u(Edge edge) const {
   337       return Node(_uid(edge._id));
   338     }
   339 
   340     Node v(Edge edge) const {
   341       return Node(_vid(edge._id));
   342     }
   343 
   344     Node source(Arc arc) const {
   345       return Node((arc._id & 1) == 1 ?
   346                   _uid(arc._id >> 1) : _vid(arc._id >> 1));
   347     }
   348 
   349     Node target(Arc arc) const {
   350       return Node((arc._id & 1) == 1 ?
   351                   _vid(arc._id >> 1) : _uid(arc._id >> 1));
   352     }
   353 
   354     typedef True FindEdgeTag;
   355     typedef True FindArcTag;
   356 
   357     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
   358       return prev != INVALID ? INVALID : edge(u, v);
   359     }
   360 
   361     Arc findArc(Node s, Node t, Arc prev = INVALID) const {
   362       return prev != INVALID ? INVALID : arc(s, t);
   363     }
   364 
   365     class Node {
   366       friend class FullGraphBase;
   367 
   368     protected:
   369       int _id;
   370       Node(int id) : _id(id) {}
   371     public:
   372       Node() {}
   373       Node (Invalid) { _id = -1; }
   374       bool operator==(const Node node) const {return _id == node._id;}
   375       bool operator!=(const Node node) const {return _id != node._id;}
   376       bool operator<(const Node node) const {return _id < node._id;}
   377     };
   378 
   379     class Edge {
   380       friend class FullGraphBase;
   381       friend class Arc;
   382 
   383     protected:
   384       int _id;
   385 
   386       Edge(int id) : _id(id) {}
   387 
   388     public:
   389       Edge() { }
   390       Edge (Invalid) { _id = -1; }
   391 
   392       bool operator==(const Edge edge) const {return _id == edge._id;}
   393       bool operator!=(const Edge edge) const {return _id != edge._id;}
   394       bool operator<(const Edge edge) const {return _id < edge._id;}
   395     };
   396 
   397     class Arc {
   398       friend class FullGraphBase;
   399 
   400     protected:
   401       int _id;
   402 
   403       Arc(int id) : _id(id) {}
   404 
   405     public:
   406       Arc() { }
   407       Arc (Invalid) { _id = -1; }
   408 
   409       operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }
   410 
   411       bool operator==(const Arc arc) const {return _id == arc._id;}
   412       bool operator!=(const Arc arc) const {return _id != arc._id;}
   413       bool operator<(const Arc arc) const {return _id < arc._id;}
   414     };
   415 
   416     static bool direction(Arc arc) {
   417       return (arc._id & 1) == 1;
   418     }
   419 
   420     static Arc direct(Edge edge, bool dir) {
   421       return Arc((edge._id << 1) | (dir ? 1 : 0));
   422     }
   423 
   424     void first(Node& node) const {
   425       node._id = _node_num - 1;
   426     }
   427 
   428     static void next(Node& node) {
   429       --node._id;
   430     }
   431 
   432     void first(Arc& arc) const {
   433       arc._id = (_edge_num << 1) - 1;
   434     }
   435 
   436     static void next(Arc& arc) {
   437       --arc._id;
   438     }
   439 
   440     void first(Edge& edge) const {
   441       edge._id = _edge_num - 1;
   442     }
   443 
   444     static void next(Edge& edge) {
   445       --edge._id;
   446     }
   447 
   448     void firstOut(Arc& arc, const Node& node) const {
   449       int s = node._id, t = _node_num - 1;
   450       if (s < t) {
   451         arc._id = (_eid(s, t) << 1) | 1;
   452       } else {
   453         --t;
   454         arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
   455       }
   456     }
   457 
   458     void nextOut(Arc& arc) const {
   459       int s, t;
   460       _stid(arc._id, s, t);
   461       --t;
   462       if (s < t) {
   463         arc._id = (_eid(s, t) << 1) | 1;
   464       } else {
   465         if (s == t) --t;
   466         arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
   467       }
   468     }
   469 
   470     void firstIn(Arc& arc, const Node& node) const {
   471       int s = _node_num - 1, t = node._id;
   472       if (s > t) {
   473         arc._id = (_eid(t, s) << 1);
   474       } else {
   475         --s;
   476         arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
   477       }
   478     }
   479 
   480     void nextIn(Arc& arc) const {
   481       int s, t;
   482       _stid(arc._id, s, t);
   483       --s;
   484       if (s > t) {
   485         arc._id = (_eid(t, s) << 1);
   486       } else {
   487         if (s == t) --s;
   488         arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
   489       }
   490     }
   491 
   492     void firstInc(Edge& edge, bool& dir, const Node& node) const {
   493       int u = node._id, v = _node_num - 1;
   494       if (u < v) {
   495         edge._id = _eid(u, v);
   496         dir = true;
   497       } else {
   498         --v;
   499         edge._id = (v != -1 ? _eid(v, u) : -1);
   500         dir = false;
   501       }
   502     }
   503 
   504     void nextInc(Edge& edge, bool& dir) const {
   505       int u, v;
   506       if (dir) {
   507         _uvid(edge._id, u, v);
   508         --v;
   509         if (u < v) {
   510           edge._id = _eid(u, v);
   511         } else {
   512           --v;
   513           edge._id = (v != -1 ? _eid(v, u) : -1);
   514           dir = false;
   515         }
   516       } else {
   517         _uvid(edge._id, v, u);
   518         --v;
   519         edge._id = (v != -1 ? _eid(v, u) : -1);
   520       }
   521     }
   522 
   523   };
   524 
   525   typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
   526 
   527   /// \ingroup graphs
   528   ///
   529   /// \brief An undirected full graph class.
   530   ///
   531   /// FullGraph is a simple and fast implmenetation of undirected full
   532   /// (complete) graphs. It contains an edge between every distinct pair
   533   /// of nodes, therefore the number of edges is <tt>n(n-1)/2</tt>.
   534   /// This class is completely static and it needs constant memory space.
   535   /// Thus you can neither add nor delete nodes or edges, however
   536   /// the structure can be resized using resize().
   537   ///
   538   /// This type fully conforms to the \ref concepts::Graph "Graph concept".
   539   /// Most of its member functions and nested classes are documented
   540   /// only in the concept class.
   541   ///
   542   /// This class provides constant time counting for nodes, edges and arcs.
   543   ///
   544   /// \note FullDigraph and FullGraph classes are very similar,
   545   /// but there are two differences. While FullDigraph
   546   /// conforms only to the \ref concepts::Digraph "Digraph" concept,
   547   /// this class conforms to the \ref concepts::Graph "Graph" concept,
   548   /// moreover this class does not contain a loop for each
   549   /// node as FullDigraph does.
   550   ///
   551   /// \sa FullDigraph
   552   class FullGraph : public ExtendedFullGraphBase {
   553     typedef ExtendedFullGraphBase Parent;
   554 
   555   public:
   556 
   557     /// \brief Default constructor.
   558     ///
   559     /// Default constructor. The number of nodes and edges will be zero.
   560     FullGraph() { construct(0); }
   561 
   562     /// \brief Constructor
   563     ///
   564     /// Constructor.
   565     /// \param n The number of the nodes.
   566     FullGraph(int n) { construct(n); }
   567 
   568     /// \brief Resizes the graph
   569     ///
   570     /// This function resizes the graph. It fully destroys and
   571     /// rebuilds the structure, therefore the maps of the graph will be
   572     /// reallocated automatically and the previous values will be lost.
   573     void resize(int n) {
   574       Parent::notifier(Arc()).clear();
   575       Parent::notifier(Edge()).clear();
   576       Parent::notifier(Node()).clear();
   577       construct(n);
   578       Parent::notifier(Node()).build();
   579       Parent::notifier(Edge()).build();
   580       Parent::notifier(Arc()).build();
   581     }
   582 
   583     /// \brief Returns the node with the given index.
   584     ///
   585     /// Returns the node with the given index. Since this structure is 
   586     /// completely static, the nodes can be indexed with integers from
   587     /// the range <tt>[0..nodeNum()-1]</tt>.
   588     /// The index of a node is the same as its ID.
   589     /// \sa index()
   590     Node operator()(int ix) const { return Parent::operator()(ix); }
   591 
   592     /// \brief Returns the index of the given node.
   593     ///
   594     /// Returns the index of the given node. Since this structure is 
   595     /// completely static, the nodes can be indexed with integers from
   596     /// the range <tt>[0..nodeNum()-1]</tt>.
   597     /// The index of a node is the same as its ID.
   598     /// \sa operator()()
   599     static int index(const Node& node) { return Parent::index(node); }
   600 
   601     /// \brief Returns the arc connecting the given nodes.
   602     ///
   603     /// Returns the arc connecting the given nodes.
   604     Arc arc(Node s, Node t) const {
   605       return Parent::arc(s, t);
   606     }
   607 
   608     /// \brief Returns the edge connecting the given nodes.
   609     ///
   610     /// Returns the edge connecting the given nodes.
   611     Edge edge(Node u, Node v) const {
   612       return Parent::edge(u, v);
   613     }
   614 
   615     /// \brief Number of nodes.
   616     int nodeNum() const { return Parent::nodeNum(); }
   617     /// \brief Number of arcs.
   618     int arcNum() const { return Parent::arcNum(); }
   619     /// \brief Number of edges.
   620     int edgeNum() const { return Parent::edgeNum(); }
   621 
   622   };
   623 
   624 
   625 } //namespace lemon
   626 
   627 
   628 #endif //LEMON_FULL_GRAPH_H