lemon/full_graph.h
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 17 Nov 2008 15:41:15 +0000
changeset 380 d916b8995e22
parent 354 80a4d0742e98
child 360 75cf49ce5390
permissions -rw-r--r--
Rename markToBottom() to dirtyTopButOne() + better doc (#174)
     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-2008
     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 Graph;
    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 conforms to the \ref concepts::Digraph "Digraph" concept
   161   /// and it also has an important extra feature that its maps are
   162   /// real \ref concepts::ReferenceMap "reference map"s.
   163   ///
   164   /// The \c FullDigraph and \c FullGraph classes are very similar,
   165   /// but there are two differences. While this class conforms only
   166   /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
   167   /// class conforms to the \ref concepts::Graph "Graph" concept,
   168   /// moreover \c FullGraph does not contain a loop arc for each
   169   /// node as \c FullDigraph does.
   170   ///
   171   /// \sa FullGraph
   172   class FullDigraph : public ExtendedFullDigraphBase {
   173   public:
   174 
   175     typedef ExtendedFullDigraphBase Parent;
   176 
   177     /// \brief Constructor
   178     FullDigraph() { construct(0); }
   179 
   180     /// \brief Constructor
   181     ///
   182     /// Constructor.
   183     /// \param n The number of the nodes.
   184     FullDigraph(int n) { construct(n); }
   185 
   186     /// \brief Resizes the digraph
   187     ///
   188     /// Resizes the digraph. The function will fully destroy and
   189     /// rebuild the digraph. This cause that the maps of the digraph will
   190     /// reallocated automatically and the previous values will be lost.
   191     void resize(int n) {
   192       Parent::notifier(Arc()).clear();
   193       Parent::notifier(Node()).clear();
   194       construct(n);
   195       Parent::notifier(Node()).build();
   196       Parent::notifier(Arc()).build();
   197     }
   198 
   199     /// \brief Returns the node with the given index.
   200     ///
   201     /// Returns the node with the given index. Since it is a static
   202     /// digraph its nodes can be indexed with integers from the range
   203     /// <tt>[0..nodeNum()-1]</tt>.
   204     /// \sa index()
   205     Node operator()(int ix) const { return Parent::operator()(ix); }
   206 
   207     /// \brief Returns the index of the given node.
   208     ///
   209     /// Returns the index of the given node. Since it is a static
   210     /// digraph its nodes can be indexed with integers from the range
   211     /// <tt>[0..nodeNum()-1]</tt>.
   212     /// \sa operator()
   213     int index(const Node& node) const { return Parent::index(node); }
   214 
   215     /// \brief Returns the arc connecting the given nodes.
   216     ///
   217     /// Returns the arc connecting the given nodes.
   218     Arc arc(const Node& u, const Node& v) const {
   219       return Parent::arc(u, v);
   220     }
   221 
   222     /// \brief Number of nodes.
   223     int nodeNum() const { return Parent::nodeNum(); }
   224     /// \brief Number of arcs.
   225     int arcNum() const { return Parent::arcNum(); }
   226   };
   227 
   228 
   229   class FullGraphBase {
   230     int _node_num;
   231     int _edge_num;
   232   public:
   233 
   234     typedef FullGraphBase Graph;
   235 
   236     class Node;
   237     class Arc;
   238     class Edge;
   239 
   240   protected:
   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 EdgeNumTag;
   310 
   311     int nodeNum() const { return _node_num; }
   312     int arcNum() const { return 2 * _edge_num; }
   313     int edgeNum() const { return _edge_num; }
   314 
   315     static int id(Node node) { return node._id; }
   316     static int id(Arc arc) { return arc._id; }
   317     static int id(Edge edge) { return edge._id; }
   318 
   319     int maxNodeId() const { return _node_num-1; }
   320     int maxArcId() const { return 2 * _edge_num-1; }
   321     int maxEdgeId() const { return _edge_num-1; }
   322 
   323     static Node nodeFromId(int id) { return Node(id);}
   324     static Arc arcFromId(int id) { return Arc(id);}
   325     static Edge edgeFromId(int id) { return Edge(id);}
   326 
   327     Node u(Edge edge) const {
   328       return Node(_uid(edge._id));
   329     }
   330 
   331     Node v(Edge edge) const {
   332       return Node(_vid(edge._id));
   333     }
   334 
   335     Node source(Arc arc) const {
   336       return Node((arc._id & 1) == 1 ?
   337                   _uid(arc._id >> 1) : _vid(arc._id >> 1));
   338     }
   339 
   340     Node target(Arc arc) const {
   341       return Node((arc._id & 1) == 1 ?
   342                   _vid(arc._id >> 1) : _uid(arc._id >> 1));
   343     }
   344 
   345     typedef True FindEdgeTag;
   346 
   347     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
   348       return prev != INVALID ? INVALID : edge(u, v);
   349     }
   350 
   351     Arc findArc(Node s, Node t, Arc prev = INVALID) const {
   352       return prev != INVALID ? INVALID : arc(s, t);
   353     }
   354 
   355     class Node {
   356       friend class FullGraphBase;
   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     class Edge {
   370       friend class FullGraphBase;
   371       friend class Arc;
   372 
   373     protected:
   374       int _id;
   375 
   376       Edge(int id) : _id(id) {}
   377 
   378     public:
   379       Edge() { }
   380       Edge (Invalid) { _id = -1; }
   381 
   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     class Arc {
   388       friend class FullGraphBase;
   389 
   390     protected:
   391       int _id;
   392 
   393       Arc(int id) : _id(id) {}
   394 
   395     public:
   396       Arc() { }
   397       Arc (Invalid) { _id = -1; }
   398 
   399       operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }
   400 
   401       bool operator==(const Arc arc) const {return _id == arc._id;}
   402       bool operator!=(const Arc arc) const {return _id != arc._id;}
   403       bool operator<(const Arc arc) const {return _id < arc._id;}
   404     };
   405 
   406     static bool direction(Arc arc) {
   407       return (arc._id & 1) == 1;
   408     }
   409 
   410     static Arc direct(Edge edge, bool dir) {
   411       return Arc((edge._id << 1) | (dir ? 1 : 0));
   412     }
   413 
   414     void first(Node& node) const {
   415       node._id = _node_num - 1;
   416     }
   417 
   418     static void next(Node& node) {
   419       --node._id;
   420     }
   421 
   422     void first(Arc& arc) const {
   423       arc._id = (_edge_num << 1) - 1;
   424     }
   425 
   426     static void next(Arc& arc) {
   427       --arc._id;
   428     }
   429 
   430     void first(Edge& edge) const {
   431       edge._id = _edge_num - 1;
   432     }
   433 
   434     static void next(Edge& edge) {
   435       --edge._id;
   436     }
   437 
   438     void firstOut(Arc& arc, const Node& node) const {
   439       int s = node._id, t = _node_num - 1;
   440       if (s < t) {
   441         arc._id = (_eid(s, t) << 1) | 1;
   442       } else {
   443         --t;
   444         arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
   445       }
   446     }
   447 
   448     void nextOut(Arc& arc) const {
   449       int s, t;
   450       _stid(arc._id, s, t);
   451       --t;
   452       if (s < t) {
   453         arc._id = (_eid(s, t) << 1) | 1;
   454       } else {
   455         if (s == t) --t;
   456         arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
   457       }
   458     }
   459 
   460     void firstIn(Arc& arc, const Node& node) const {
   461       int s = _node_num - 1, t = node._id;
   462       if (s > t) {
   463         arc._id = (_eid(t, s) << 1);
   464       } else {
   465         --s;
   466         arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
   467       }
   468     }
   469 
   470     void nextIn(Arc& arc) const {
   471       int s, t;
   472       _stid(arc._id, s, t);
   473       --s;
   474       if (s > t) {
   475         arc._id = (_eid(t, s) << 1);
   476       } else {
   477         if (s == t) --s;
   478         arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
   479       }
   480     }
   481 
   482     void firstInc(Edge& edge, bool& dir, const Node& node) const {
   483       int u = node._id, v = _node_num - 1;
   484       if (u < v) {
   485         edge._id = _eid(u, v);
   486         dir = true;
   487       } else {
   488         --v;
   489         edge._id = (v != -1 ? _eid(v, u) : -1);
   490         dir = false;
   491       }
   492     }
   493 
   494     void nextInc(Edge& edge, bool& dir) const {
   495       int u, v;
   496       if (dir) {
   497         _uvid(edge._id, u, v);
   498         --v;
   499         if (u < v) {
   500           edge._id = _eid(u, v);
   501         } else {
   502           --v;
   503           edge._id = (v != -1 ? _eid(v, u) : -1);
   504           dir = false;
   505         }
   506       } else {
   507         _uvid(edge._id, v, u);
   508         --v;
   509         edge._id = (v != -1 ? _eid(v, u) : -1);
   510       }
   511     }
   512 
   513   };
   514 
   515   typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
   516 
   517   /// \ingroup graphs
   518   ///
   519   /// \brief An undirected full graph class.
   520   ///
   521   /// This is a simple and fast undirected full graph
   522   /// implementation. From each node go edge to each other node,
   523   /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
   524   /// This graph type is completely static, so you can neither
   525   /// add nor delete either edges or nodes, and it needs constant
   526   /// space in memory.
   527   ///
   528   /// This class conforms to the \ref concepts::Graph "Graph" concept
   529   /// and it also has an important extra feature that its maps are
   530   /// real \ref concepts::ReferenceMap "reference map"s.
   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   public:
   542 
   543     typedef ExtendedFullGraphBase Parent;
   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