lemon/full_graph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Wed, 08 Jul 2009 17:21:30 +0200
changeset 709 0747f332c478
parent 582 7a28e215f715
child 735 853fcddcf282
child 778 a143f19f465b
permissions -rw-r--r--
Improve and unify the documentation of heaps (#299)
and avoid a warning in SimpleBucketHeap::operator[].
     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 FullGraph and FullDigraph 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     int index(const Node& node) const { 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 full digraph class.
   152   ///
   153   /// This is a simple and fast directed full graph implementation.
   154   /// From each node go arcs to each node (including the source node),
   155   /// therefore the number of the arcs in the digraph is the square of
   156   /// the node number. This digraph type is completely static, so you
   157   /// can neither add nor delete either arcs or nodes, and it needs
   158   /// constant space in memory.
   159   ///
   160   /// This class fully conforms to the \ref concepts::Digraph
   161   /// "Digraph concept".
   162   ///
   163   /// The \c FullDigraph and \c FullGraph classes are very similar,
   164   /// but there are two differences. While this class conforms only
   165   /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
   166   /// class conforms to the \ref concepts::Graph "Graph" concept,
   167   /// moreover \c FullGraph does not contain a loop arc for each
   168   /// node as \c FullDigraph does.
   169   ///
   170   /// \sa FullGraph
   171   class FullDigraph : public ExtendedFullDigraphBase {
   172     typedef ExtendedFullDigraphBase Parent;
   173 
   174   public:
   175 
   176     /// \brief Constructor
   177     FullDigraph() { construct(0); }
   178 
   179     /// \brief Constructor
   180     ///
   181     /// Constructor.
   182     /// \param n The number of the nodes.
   183     FullDigraph(int n) { construct(n); }
   184 
   185     /// \brief Resizes the digraph
   186     ///
   187     /// Resizes the digraph. The function will fully destroy and
   188     /// rebuild the digraph. This cause that the maps of the digraph will
   189     /// reallocated automatically and the previous values will be lost.
   190     void resize(int n) {
   191       Parent::notifier(Arc()).clear();
   192       Parent::notifier(Node()).clear();
   193       construct(n);
   194       Parent::notifier(Node()).build();
   195       Parent::notifier(Arc()).build();
   196     }
   197 
   198     /// \brief Returns the node with the given index.
   199     ///
   200     /// Returns the node with the given index. Since it is a static
   201     /// digraph its nodes can be indexed with integers from the range
   202     /// <tt>[0..nodeNum()-1]</tt>.
   203     /// \sa index()
   204     Node operator()(int ix) const { return Parent::operator()(ix); }
   205 
   206     /// \brief Returns the index of the given node.
   207     ///
   208     /// Returns the index of the given node. Since it is a static
   209     /// digraph its nodes can be indexed with integers from the range
   210     /// <tt>[0..nodeNum()-1]</tt>.
   211     /// \sa operator()
   212     int index(const Node& node) const { return Parent::index(node); }
   213 
   214     /// \brief Returns the arc connecting the given nodes.
   215     ///
   216     /// Returns the arc connecting the given nodes.
   217     Arc arc(const Node& u, const Node& v) const {
   218       return Parent::arc(u, v);
   219     }
   220 
   221     /// \brief Number of nodes.
   222     int nodeNum() const { return Parent::nodeNum(); }
   223     /// \brief Number of arcs.
   224     int arcNum() const { return Parent::arcNum(); }
   225   };
   226 
   227 
   228   class FullGraphBase {
   229   public:
   230 
   231     typedef FullGraphBase Graph;
   232 
   233     class Node;
   234     class Arc;
   235     class Edge;
   236 
   237   protected:
   238 
   239     int _node_num;
   240     int _edge_num;
   241 
   242     FullGraphBase() {}
   243 
   244     void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }
   245 
   246     int _uid(int e) const {
   247       int u = e / _node_num;
   248       int v = e % _node_num;
   249       return u < v ? u : _node_num - 2 - u;
   250     }
   251 
   252     int _vid(int e) const {
   253       int u = e / _node_num;
   254       int v = e % _node_num;
   255       return u < v ? v : _node_num - 1 - v;
   256     }
   257 
   258     void _uvid(int e, int& u, int& v) const {
   259       u = e / _node_num;
   260       v = e % _node_num;
   261       if  (u >= v) {
   262         u = _node_num - 2 - u;
   263         v = _node_num - 1 - v;
   264       }
   265     }
   266 
   267     void _stid(int a, int& s, int& t) const {
   268       if ((a & 1) == 1) {
   269         _uvid(a >> 1, s, t);
   270       } else {
   271         _uvid(a >> 1, t, s);
   272       }
   273     }
   274 
   275     int _eid(int u, int v) const {
   276       if (u < (_node_num - 1) / 2) {
   277         return u * _node_num + v;
   278       } else {
   279         return (_node_num - 1 - u) * _node_num - v - 1;
   280       }
   281     }
   282 
   283   public:
   284 
   285     Node operator()(int ix) const { return Node(ix); }
   286     int index(const Node& node) const { return node._id; }
   287 
   288     Edge edge(const Node& u, const Node& v) const {
   289       if (u._id < v._id) {
   290         return Edge(_eid(u._id, v._id));
   291       } else if (u._id != v._id) {
   292         return Edge(_eid(v._id, u._id));
   293       } else {
   294         return INVALID;
   295       }
   296     }
   297 
   298     Arc arc(const Node& s, const Node& t) const {
   299       if (s._id < t._id) {
   300         return Arc((_eid(s._id, t._id) << 1) | 1);
   301       } else if (s._id != t._id) {
   302         return Arc(_eid(t._id, s._id) << 1);
   303       } else {
   304         return INVALID;
   305       }
   306     }
   307 
   308     typedef True NodeNumTag;
   309     typedef True ArcNumTag;
   310     typedef True EdgeNumTag;
   311 
   312     int nodeNum() const { return _node_num; }
   313     int arcNum() const { return 2 * _edge_num; }
   314     int edgeNum() const { return _edge_num; }
   315 
   316     static int id(Node node) { return node._id; }
   317     static int id(Arc arc) { return arc._id; }
   318     static int id(Edge edge) { return edge._id; }
   319 
   320     int maxNodeId() const { return _node_num-1; }
   321     int maxArcId() const { return 2 * _edge_num-1; }
   322     int maxEdgeId() const { return _edge_num-1; }
   323 
   324     static Node nodeFromId(int id) { return Node(id);}
   325     static Arc arcFromId(int id) { return Arc(id);}
   326     static Edge edgeFromId(int id) { return Edge(id);}
   327 
   328     Node u(Edge edge) const {
   329       return Node(_uid(edge._id));
   330     }
   331 
   332     Node v(Edge edge) const {
   333       return Node(_vid(edge._id));
   334     }
   335 
   336     Node source(Arc arc) const {
   337       return Node((arc._id & 1) == 1 ?
   338                   _uid(arc._id >> 1) : _vid(arc._id >> 1));
   339     }
   340 
   341     Node target(Arc arc) const {
   342       return Node((arc._id & 1) == 1 ?
   343                   _vid(arc._id >> 1) : _uid(arc._id >> 1));
   344     }
   345 
   346     typedef True FindEdgeTag;
   347     typedef True FindArcTag;
   348 
   349     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
   350       return prev != INVALID ? INVALID : edge(u, v);
   351     }
   352 
   353     Arc findArc(Node s, Node t, Arc prev = INVALID) const {
   354       return prev != INVALID ? INVALID : arc(s, t);
   355     }
   356 
   357     class Node {
   358       friend class FullGraphBase;
   359 
   360     protected:
   361       int _id;
   362       Node(int id) : _id(id) {}
   363     public:
   364       Node() {}
   365       Node (Invalid) { _id = -1; }
   366       bool operator==(const Node node) const {return _id == node._id;}
   367       bool operator!=(const Node node) const {return _id != node._id;}
   368       bool operator<(const Node node) const {return _id < node._id;}
   369     };
   370 
   371     class Edge {
   372       friend class FullGraphBase;
   373       friend class Arc;
   374 
   375     protected:
   376       int _id;
   377 
   378       Edge(int id) : _id(id) {}
   379 
   380     public:
   381       Edge() { }
   382       Edge (Invalid) { _id = -1; }
   383 
   384       bool operator==(const Edge edge) const {return _id == edge._id;}
   385       bool operator!=(const Edge edge) const {return _id != edge._id;}
   386       bool operator<(const Edge edge) const {return _id < edge._id;}
   387     };
   388 
   389     class Arc {
   390       friend class FullGraphBase;
   391 
   392     protected:
   393       int _id;
   394 
   395       Arc(int id) : _id(id) {}
   396 
   397     public:
   398       Arc() { }
   399       Arc (Invalid) { _id = -1; }
   400 
   401       operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }
   402 
   403       bool operator==(const Arc arc) const {return _id == arc._id;}
   404       bool operator!=(const Arc arc) const {return _id != arc._id;}
   405       bool operator<(const Arc arc) const {return _id < arc._id;}
   406     };
   407 
   408     static bool direction(Arc arc) {
   409       return (arc._id & 1) == 1;
   410     }
   411 
   412     static Arc direct(Edge edge, bool dir) {
   413       return Arc((edge._id << 1) | (dir ? 1 : 0));
   414     }
   415 
   416     void first(Node& node) const {
   417       node._id = _node_num - 1;
   418     }
   419 
   420     static void next(Node& node) {
   421       --node._id;
   422     }
   423 
   424     void first(Arc& arc) const {
   425       arc._id = (_edge_num << 1) - 1;
   426     }
   427 
   428     static void next(Arc& arc) {
   429       --arc._id;
   430     }
   431 
   432     void first(Edge& edge) const {
   433       edge._id = _edge_num - 1;
   434     }
   435 
   436     static void next(Edge& edge) {
   437       --edge._id;
   438     }
   439 
   440     void firstOut(Arc& arc, const Node& node) const {
   441       int s = node._id, t = _node_num - 1;
   442       if (s < t) {
   443         arc._id = (_eid(s, t) << 1) | 1;
   444       } else {
   445         --t;
   446         arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
   447       }
   448     }
   449 
   450     void nextOut(Arc& arc) const {
   451       int s, t;
   452       _stid(arc._id, s, t);
   453       --t;
   454       if (s < t) {
   455         arc._id = (_eid(s, t) << 1) | 1;
   456       } else {
   457         if (s == t) --t;
   458         arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
   459       }
   460     }
   461 
   462     void firstIn(Arc& arc, const Node& node) const {
   463       int s = _node_num - 1, t = node._id;
   464       if (s > t) {
   465         arc._id = (_eid(t, s) << 1);
   466       } else {
   467         --s;
   468         arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
   469       }
   470     }
   471 
   472     void nextIn(Arc& arc) const {
   473       int s, t;
   474       _stid(arc._id, s, t);
   475       --s;
   476       if (s > t) {
   477         arc._id = (_eid(t, s) << 1);
   478       } else {
   479         if (s == t) --s;
   480         arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
   481       }
   482     }
   483 
   484     void firstInc(Edge& edge, bool& dir, const Node& node) const {
   485       int u = node._id, v = _node_num - 1;
   486       if (u < v) {
   487         edge._id = _eid(u, v);
   488         dir = true;
   489       } else {
   490         --v;
   491         edge._id = (v != -1 ? _eid(v, u) : -1);
   492         dir = false;
   493       }
   494     }
   495 
   496     void nextInc(Edge& edge, bool& dir) const {
   497       int u, v;
   498       if (dir) {
   499         _uvid(edge._id, u, v);
   500         --v;
   501         if (u < v) {
   502           edge._id = _eid(u, v);
   503         } else {
   504           --v;
   505           edge._id = (v != -1 ? _eid(v, u) : -1);
   506           dir = false;
   507         }
   508       } else {
   509         _uvid(edge._id, v, u);
   510         --v;
   511         edge._id = (v != -1 ? _eid(v, u) : -1);
   512       }
   513     }
   514 
   515   };
   516 
   517   typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
   518 
   519   /// \ingroup graphs
   520   ///
   521   /// \brief An undirected full graph class.
   522   ///
   523   /// This is a simple and fast undirected full graph
   524   /// implementation. From each node go edge to each other node,
   525   /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
   526   /// This graph type is completely static, so you can neither
   527   /// add nor delete either edges or nodes, and it needs constant
   528   /// space in memory.
   529   ///
   530   /// This class fully conforms to the \ref concepts::Graph "Graph concept".
   531   ///
   532   /// The \c FullGraph and \c FullDigraph classes are very similar,
   533   /// but there are two differences. While the \c FullDigraph class
   534   /// conforms only to the \ref concepts::Digraph "Digraph" concept,
   535   /// this class conforms to the \ref concepts::Graph "Graph" concept,
   536   /// moreover \c FullGraph does not contain a loop arc for each
   537   /// node as \c FullDigraph does.
   538   ///
   539   /// \sa FullDigraph
   540   class FullGraph : public ExtendedFullGraphBase {
   541     typedef ExtendedFullGraphBase Parent;
   542 
   543   public:
   544 
   545     /// \brief Constructor
   546     FullGraph() { construct(0); }
   547 
   548     /// \brief Constructor
   549     ///
   550     /// Constructor.
   551     /// \param n The number of the nodes.
   552     FullGraph(int n) { construct(n); }
   553 
   554     /// \brief Resizes the graph
   555     ///
   556     /// Resizes the graph. The function will fully destroy and
   557     /// rebuild the graph. This cause that the maps of the graph will
   558     /// reallocated automatically and the previous values will be lost.
   559     void resize(int n) {
   560       Parent::notifier(Arc()).clear();
   561       Parent::notifier(Edge()).clear();
   562       Parent::notifier(Node()).clear();
   563       construct(n);
   564       Parent::notifier(Node()).build();
   565       Parent::notifier(Edge()).build();
   566       Parent::notifier(Arc()).build();
   567     }
   568 
   569     /// \brief Returns the node with the given index.
   570     ///
   571     /// Returns the node with the given index. Since it is a static
   572     /// graph its nodes can be indexed with integers from the range
   573     /// <tt>[0..nodeNum()-1]</tt>.
   574     /// \sa index()
   575     Node operator()(int ix) const { return Parent::operator()(ix); }
   576 
   577     /// \brief Returns the index of the given node.
   578     ///
   579     /// Returns the index of the given node. Since it is a static
   580     /// graph its nodes can be indexed with integers from the range
   581     /// <tt>[0..nodeNum()-1]</tt>.
   582     /// \sa operator()
   583     int index(const Node& node) const { return Parent::index(node); }
   584 
   585     /// \brief Returns the arc connecting the given nodes.
   586     ///
   587     /// Returns the arc connecting the given nodes.
   588     Arc arc(const Node& s, const Node& t) const {
   589       return Parent::arc(s, t);
   590     }
   591 
   592     /// \brief Returns the edge connects the given nodes.
   593     ///
   594     /// Returns the edge connects the given nodes.
   595     Edge edge(const Node& u, const Node& v) const {
   596       return Parent::edge(u, v);
   597     }
   598 
   599     /// \brief Number of nodes.
   600     int nodeNum() const { return Parent::nodeNum(); }
   601     /// \brief Number of arcs.
   602     int arcNum() const { return Parent::arcNum(); }
   603     /// \brief Number of edges.
   604     int edgeNum() const { return Parent::edgeNum(); }
   605 
   606   };
   607 
   608 
   609 } //namespace lemon
   610 
   611 
   612 #endif //LEMON_FULL_GRAPH_H