lemon/full_graph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 09:58:50 +0200
changeset 594 d657c71db7db
parent 440 88ed40ad0d4f
child 617 4137ef9aacc6
permissions -rw-r--r--
Rename max_matching.h to matching.h (#265)
     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 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 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   public:
   173 
   174     typedef ExtendedFullDigraphBase Parent;
   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     int _node_num;
   230     int _edge_num;
   231   public:
   232 
   233     typedef FullGraphBase Graph;
   234 
   235     class Node;
   236     class Arc;
   237     class Edge;
   238 
   239   protected:
   240 
   241     FullGraphBase() {}
   242 
   243     void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }
   244 
   245     int _uid(int e) const {
   246       int u = e / _node_num;
   247       int v = e % _node_num;
   248       return u < v ? u : _node_num - 2 - u;
   249     }
   250 
   251     int _vid(int e) const {
   252       int u = e / _node_num;
   253       int v = e % _node_num;
   254       return u < v ? v : _node_num - 1 - v;
   255     }
   256 
   257     void _uvid(int e, int& u, int& v) const {
   258       u = e / _node_num;
   259       v = e % _node_num;
   260       if  (u >= v) {
   261         u = _node_num - 2 - u;
   262         v = _node_num - 1 - v;
   263       }
   264     }
   265 
   266     void _stid(int a, int& s, int& t) const {
   267       if ((a & 1) == 1) {
   268         _uvid(a >> 1, s, t);
   269       } else {
   270         _uvid(a >> 1, t, s);
   271       }
   272     }
   273 
   274     int _eid(int u, int v) const {
   275       if (u < (_node_num - 1) / 2) {
   276         return u * _node_num + v;
   277       } else {
   278         return (_node_num - 1 - u) * _node_num - v - 1;
   279       }
   280     }
   281 
   282   public:
   283 
   284     Node operator()(int ix) const { return Node(ix); }
   285     int index(const Node& node) const { return node._id; }
   286 
   287     Edge edge(const Node& u, const Node& v) const {
   288       if (u._id < v._id) {
   289         return Edge(_eid(u._id, v._id));
   290       } else if (u._id != v._id) {
   291         return Edge(_eid(v._id, u._id));
   292       } else {
   293         return INVALID;
   294       }
   295     }
   296 
   297     Arc arc(const Node& s, const Node& t) const {
   298       if (s._id < t._id) {
   299         return Arc((_eid(s._id, t._id) << 1) | 1);
   300       } else if (s._id != t._id) {
   301         return Arc(_eid(t._id, s._id) << 1);
   302       } else {
   303         return INVALID;
   304       }
   305     }
   306 
   307     typedef True NodeNumTag;
   308     typedef True ArcNumTag;
   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     typedef True FindArcTag;
   347 
   348     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
   349       return prev != INVALID ? INVALID : edge(u, v);
   350     }
   351 
   352     Arc findArc(Node s, Node t, Arc prev = INVALID) const {
   353       return prev != INVALID ? INVALID : arc(s, t);
   354     }
   355 
   356     class Node {
   357       friend class FullGraphBase;
   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     class Edge {
   371       friend class FullGraphBase;
   372       friend class Arc;
   373 
   374     protected:
   375       int _id;
   376 
   377       Edge(int id) : _id(id) {}
   378 
   379     public:
   380       Edge() { }
   381       Edge (Invalid) { _id = -1; }
   382 
   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     class Arc {
   389       friend class FullGraphBase;
   390 
   391     protected:
   392       int _id;
   393 
   394       Arc(int id) : _id(id) {}
   395 
   396     public:
   397       Arc() { }
   398       Arc (Invalid) { _id = -1; }
   399 
   400       operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }
   401 
   402       bool operator==(const Arc arc) const {return _id == arc._id;}
   403       bool operator!=(const Arc arc) const {return _id != arc._id;}
   404       bool operator<(const Arc arc) const {return _id < arc._id;}
   405     };
   406 
   407     static bool direction(Arc arc) {
   408       return (arc._id & 1) == 1;
   409     }
   410 
   411     static Arc direct(Edge edge, bool dir) {
   412       return Arc((edge._id << 1) | (dir ? 1 : 0));
   413     }
   414 
   415     void first(Node& node) const {
   416       node._id = _node_num - 1;
   417     }
   418 
   419     static void next(Node& node) {
   420       --node._id;
   421     }
   422 
   423     void first(Arc& arc) const {
   424       arc._id = (_edge_num << 1) - 1;
   425     }
   426 
   427     static void next(Arc& arc) {
   428       --arc._id;
   429     }
   430 
   431     void first(Edge& edge) const {
   432       edge._id = _edge_num - 1;
   433     }
   434 
   435     static void next(Edge& edge) {
   436       --edge._id;
   437     }
   438 
   439     void firstOut(Arc& arc, const Node& node) const {
   440       int s = node._id, t = _node_num - 1;
   441       if (s < t) {
   442         arc._id = (_eid(s, t) << 1) | 1;
   443       } else {
   444         --t;
   445         arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
   446       }
   447     }
   448 
   449     void nextOut(Arc& arc) const {
   450       int s, t;
   451       _stid(arc._id, s, t);
   452       --t;
   453       if (s < t) {
   454         arc._id = (_eid(s, t) << 1) | 1;
   455       } else {
   456         if (s == t) --t;
   457         arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
   458       }
   459     }
   460 
   461     void firstIn(Arc& arc, const Node& node) const {
   462       int s = _node_num - 1, t = node._id;
   463       if (s > t) {
   464         arc._id = (_eid(t, s) << 1);
   465       } else {
   466         --s;
   467         arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
   468       }
   469     }
   470 
   471     void nextIn(Arc& arc) const {
   472       int s, t;
   473       _stid(arc._id, s, t);
   474       --s;
   475       if (s > t) {
   476         arc._id = (_eid(t, s) << 1);
   477       } else {
   478         if (s == t) --s;
   479         arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
   480       }
   481     }
   482 
   483     void firstInc(Edge& edge, bool& dir, const Node& node) const {
   484       int u = node._id, v = _node_num - 1;
   485       if (u < v) {
   486         edge._id = _eid(u, v);
   487         dir = true;
   488       } else {
   489         --v;
   490         edge._id = (v != -1 ? _eid(v, u) : -1);
   491         dir = false;
   492       }
   493     }
   494 
   495     void nextInc(Edge& edge, bool& dir) const {
   496       int u, v;
   497       if (dir) {
   498         _uvid(edge._id, u, v);
   499         --v;
   500         if (u < v) {
   501           edge._id = _eid(u, v);
   502         } else {
   503           --v;
   504           edge._id = (v != -1 ? _eid(v, u) : -1);
   505           dir = false;
   506         }
   507       } else {
   508         _uvid(edge._id, v, u);
   509         --v;
   510         edge._id = (v != -1 ? _eid(v, u) : -1);
   511       }
   512     }
   513 
   514   };
   515 
   516   typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
   517 
   518   /// \ingroup graphs
   519   ///
   520   /// \brief An undirected full graph class.
   521   ///
   522   /// This is a simple and fast undirected full graph
   523   /// implementation. From each node go edge to each other node,
   524   /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
   525   /// This graph type is completely static, so you can neither
   526   /// add nor delete either edges or nodes, and it needs constant
   527   /// space in memory.
   528   ///
   529   /// This class fully conforms to the \ref concepts::Graph "Graph concept".
   530   ///
   531   /// The \c FullGraph and \c FullDigraph classes are very similar,
   532   /// but there are two differences. While the \c FullDigraph class
   533   /// conforms only to the \ref concepts::Digraph "Digraph" concept,
   534   /// this class conforms to the \ref concepts::Graph "Graph" concept,
   535   /// moreover \c FullGraph does not contain a loop arc for each
   536   /// node as \c FullDigraph does.
   537   ///
   538   /// \sa FullDigraph
   539   class FullGraph : public ExtendedFullGraphBase {
   540   public:
   541 
   542     typedef ExtendedFullGraphBase Parent;
   543 
   544     /// \brief Constructor
   545     FullGraph() { construct(0); }
   546 
   547     /// \brief Constructor
   548     ///
   549     /// Constructor.
   550     /// \param n The number of the nodes.
   551     FullGraph(int n) { construct(n); }
   552 
   553     /// \brief Resizes the graph
   554     ///
   555     /// Resizes the graph. The function will fully destroy and
   556     /// rebuild the graph. This cause that the maps of the graph will
   557     /// reallocated automatically and the previous values will be lost.
   558     void resize(int n) {
   559       Parent::notifier(Arc()).clear();
   560       Parent::notifier(Edge()).clear();
   561       Parent::notifier(Node()).clear();
   562       construct(n);
   563       Parent::notifier(Node()).build();
   564       Parent::notifier(Edge()).build();
   565       Parent::notifier(Arc()).build();
   566     }
   567 
   568     /// \brief Returns the node with the given index.
   569     ///
   570     /// Returns the node with the given index. Since it is a static
   571     /// graph its nodes can be indexed with integers from the range
   572     /// <tt>[0..nodeNum()-1]</tt>.
   573     /// \sa index()
   574     Node operator()(int ix) const { return Parent::operator()(ix); }
   575 
   576     /// \brief Returns the index of the given node.
   577     ///
   578     /// Returns the index of the given node. Since it is a static
   579     /// graph its nodes can be indexed with integers from the range
   580     /// <tt>[0..nodeNum()-1]</tt>.
   581     /// \sa operator()
   582     int index(const Node& node) const { return Parent::index(node); }
   583 
   584     /// \brief Returns the arc connecting the given nodes.
   585     ///
   586     /// Returns the arc connecting the given nodes.
   587     Arc arc(const Node& s, const Node& t) const {
   588       return Parent::arc(s, t);
   589     }
   590 
   591     /// \brief Returns the edge connects the given nodes.
   592     ///
   593     /// Returns the edge connects the given nodes.
   594     Edge edge(const Node& u, const Node& v) const {
   595       return Parent::edge(u, v);
   596     }
   597 
   598     /// \brief Number of nodes.
   599     int nodeNum() const { return Parent::nodeNum(); }
   600     /// \brief Number of arcs.
   601     int arcNum() const { return Parent::arcNum(); }
   602     /// \brief Number of edges.
   603     int edgeNum() const { return Parent::edgeNum(); }
   604 
   605   };
   606 
   607 
   608 } //namespace lemon
   609 
   610 
   611 #endif //LEMON_FULL_GRAPH_H