lemon/static_graph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 20 Feb 2010 18:39:03 +0100
changeset 839 f3bc4e9b5f3a
parent 779 c160bf9f18ef
child 877 141f9c0db4a3
permissions -rw-r--r--
New heuristics for MCF algorithms (#340)
and some implementation improvements.

- A useful heuristic is added to NetworkSimplex to make the
initial pivots faster.
- A powerful global update heuristic is added to CostScaling
and the implementation is reworked with various improvements.
- Better relabeling in CostScaling to improve numerical stability
and make the code faster.
- A small improvement is made in CapacityScaling for better
delta computation.
- Add notes to the classes about the usage of vector<char> instead
of vector<bool> for efficiency reasons.
     1 /* -*- C++ -*-
     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_STATIC_GRAPH_H
    20 #define LEMON_STATIC_GRAPH_H
    21 
    22 ///\ingroup graphs
    23 ///\file
    24 ///\brief StaticDigraph class.
    25 
    26 #include <lemon/core.h>
    27 #include <lemon/bits/graph_extender.h>
    28 
    29 namespace lemon {
    30 
    31   class StaticDigraphBase {
    32   public:
    33 
    34     StaticDigraphBase() 
    35       : built(false), node_num(0), arc_num(0), 
    36         node_first_out(NULL), node_first_in(NULL),
    37         arc_source(NULL), arc_target(NULL), 
    38         arc_next_in(NULL), arc_next_out(NULL) {}
    39     
    40     ~StaticDigraphBase() {
    41       if (built) {
    42         delete[] node_first_out;
    43         delete[] node_first_in;
    44         delete[] arc_source;
    45         delete[] arc_target;
    46         delete[] arc_next_out;
    47         delete[] arc_next_in;
    48       }
    49     }
    50 
    51     class Node {
    52       friend class StaticDigraphBase;
    53     protected:
    54       int id;
    55       Node(int _id) : id(_id) {}
    56     public:
    57       Node() {}
    58       Node (Invalid) : id(-1) {}
    59       bool operator==(const Node& node) const { return id == node.id; }
    60       bool operator!=(const Node& node) const { return id != node.id; }
    61       bool operator<(const Node& node) const { return id < node.id; }
    62     };
    63 
    64     class Arc {
    65       friend class StaticDigraphBase;      
    66     protected:
    67       int id;
    68       Arc(int _id) : id(_id) {}
    69     public:
    70       Arc() { }
    71       Arc (Invalid) : id(-1) {}
    72       bool operator==(const Arc& arc) const { return id == arc.id; }
    73       bool operator!=(const Arc& arc) const { return id != arc.id; }
    74       bool operator<(const Arc& arc) const { return id < arc.id; }
    75     };
    76 
    77     Node source(const Arc& e) const { return Node(arc_source[e.id]); }
    78     Node target(const Arc& e) const { return Node(arc_target[e.id]); }
    79 
    80     void first(Node& n) const { n.id = node_num - 1; }
    81     static void next(Node& n) { --n.id; }
    82 
    83     void first(Arc& e) const { e.id = arc_num - 1; }
    84     static void next(Arc& e) { --e.id; }
    85 
    86     void firstOut(Arc& e, const Node& n) const { 
    87       e.id = node_first_out[n.id] != node_first_out[n.id + 1] ? 
    88         node_first_out[n.id] : -1;
    89     }
    90     void nextOut(Arc& e) const { e.id = arc_next_out[e.id]; }
    91 
    92     void firstIn(Arc& e, const Node& n) const { e.id = node_first_in[n.id]; }
    93     void nextIn(Arc& e) const { e.id = arc_next_in[e.id]; }
    94 
    95     static int id(const Node& n) { return n.id; }
    96     static Node nodeFromId(int id) { return Node(id); }
    97     int maxNodeId() const { return node_num - 1; }
    98 
    99     static int id(const Arc& e) { return e.id; }
   100     static Arc arcFromId(int id) { return Arc(id); }
   101     int maxArcId() const { return arc_num - 1; }
   102 
   103     typedef True NodeNumTag;
   104     typedef True ArcNumTag;
   105 
   106     int nodeNum() const { return node_num; }
   107     int arcNum() const { return arc_num; }
   108 
   109   private:
   110 
   111     template <typename Digraph, typename NodeRefMap>
   112     class ArcLess {
   113     public:
   114       typedef typename Digraph::Arc Arc;
   115 
   116       ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef) 
   117         : digraph(_graph), nodeRef(_nodeRef) {}
   118       
   119       bool operator()(const Arc& left, const Arc& right) const {
   120 	return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
   121       }
   122     private:
   123       const Digraph& digraph;
   124       const NodeRefMap& nodeRef;
   125     };
   126     
   127   public:
   128 
   129     typedef True BuildTag;
   130     
   131     void clear() {
   132       if (built) {
   133         delete[] node_first_out;
   134         delete[] node_first_in;
   135         delete[] arc_source;
   136         delete[] arc_target;
   137         delete[] arc_next_out;
   138         delete[] arc_next_in;
   139       }
   140       built = false;
   141       node_num = 0;
   142       arc_num = 0;
   143     }
   144     
   145     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
   146     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
   147       typedef typename Digraph::Node GNode;
   148       typedef typename Digraph::Arc GArc;
   149 
   150       built = true;
   151 
   152       node_num = countNodes(digraph);
   153       arc_num = countArcs(digraph);
   154 
   155       node_first_out = new int[node_num + 1];
   156       node_first_in = new int[node_num];
   157 
   158       arc_source = new int[arc_num];
   159       arc_target = new int[arc_num];
   160       arc_next_out = new int[arc_num];
   161       arc_next_in = new int[arc_num];
   162 
   163       int node_index = 0;
   164       for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
   165         nodeRef[n] = Node(node_index);
   166         node_first_in[node_index] = -1;
   167         ++node_index;
   168       }
   169 
   170       ArcLess<Digraph, NodeRefMap> arcLess(digraph, nodeRef);
   171 
   172       int arc_index = 0;
   173       for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
   174         int source = nodeRef[n].id;
   175         std::vector<GArc> arcs;
   176         for (typename Digraph::OutArcIt e(digraph, n); e != INVALID; ++e) {
   177           arcs.push_back(e);
   178         }
   179         if (!arcs.empty()) {
   180           node_first_out[source] = arc_index;
   181           std::sort(arcs.begin(), arcs.end(), arcLess);
   182           for (typename std::vector<GArc>::iterator it = arcs.begin();
   183                it != arcs.end(); ++it) {
   184             int target = nodeRef[digraph.target(*it)].id;
   185             arcRef[*it] = Arc(arc_index);
   186             arc_source[arc_index] = source; 
   187             arc_target[arc_index] = target;
   188             arc_next_in[arc_index] = node_first_in[target];
   189             node_first_in[target] = arc_index;
   190             arc_next_out[arc_index] = arc_index + 1;
   191             ++arc_index;
   192           }
   193           arc_next_out[arc_index - 1] = -1;
   194         } else {
   195           node_first_out[source] = arc_index;
   196         }
   197       }
   198       node_first_out[node_num] = arc_num;
   199     }
   200     
   201     template <typename ArcListIterator>
   202     void build(int n, ArcListIterator first, ArcListIterator last) {
   203       built = true;
   204 
   205       node_num = n;
   206       arc_num = std::distance(first, last);
   207 
   208       node_first_out = new int[node_num + 1];
   209       node_first_in = new int[node_num];
   210 
   211       arc_source = new int[arc_num];
   212       arc_target = new int[arc_num];
   213       arc_next_out = new int[arc_num];
   214       arc_next_in = new int[arc_num];
   215       
   216       for (int i = 0; i != node_num; ++i) {
   217         node_first_in[i] = -1;
   218       }      
   219       
   220       int arc_index = 0;
   221       for (int i = 0; i != node_num; ++i) {
   222         node_first_out[i] = arc_index;
   223         for ( ; first != last && (*first).first == i; ++first) {
   224           int j = (*first).second;
   225           LEMON_ASSERT(j >= 0 && j < node_num,
   226             "Wrong arc list for StaticDigraph::build()");
   227           arc_source[arc_index] = i;
   228           arc_target[arc_index] = j;
   229           arc_next_in[arc_index] = node_first_in[j];
   230           node_first_in[j] = arc_index;
   231           arc_next_out[arc_index] = arc_index + 1;
   232           ++arc_index;
   233         }
   234         if (arc_index > node_first_out[i])
   235           arc_next_out[arc_index - 1] = -1;
   236       }
   237       LEMON_ASSERT(first == last,
   238         "Wrong arc list for StaticDigraph::build()");
   239       node_first_out[node_num] = arc_num;
   240     }
   241 
   242   protected:
   243 
   244     void fastFirstOut(Arc& e, const Node& n) const {
   245       e.id = node_first_out[n.id];
   246     }
   247 
   248     static void fastNextOut(Arc& e) {
   249       ++e.id;
   250     }
   251     void fastLastOut(Arc& e, const Node& n) const {
   252       e.id = node_first_out[n.id + 1];
   253     }
   254 
   255   protected:
   256     bool built;
   257     int node_num;
   258     int arc_num;
   259     int *node_first_out;
   260     int *node_first_in;
   261     int *arc_source;
   262     int *arc_target;
   263     int *arc_next_in;
   264     int *arc_next_out;
   265   };
   266 
   267   typedef DigraphExtender<StaticDigraphBase> ExtendedStaticDigraphBase;
   268 
   269 
   270   /// \ingroup graphs
   271   ///
   272   /// \brief A static directed graph class.
   273   ///
   274   /// \ref StaticDigraph is a highly efficient digraph implementation,
   275   /// but it is fully static.
   276   /// It stores only two \c int values for each node and only four \c int
   277   /// values for each arc. Moreover it provides faster item iteration than
   278   /// \ref ListDigraph and \ref SmartDigraph, especially using \c OutArcIt
   279   /// iterators, since its arcs are stored in an appropriate order.
   280   /// However it only provides build() and clear() functions and does not
   281   /// support any other modification of the digraph.
   282   ///
   283   /// Since this digraph structure is completely static, its nodes and arcs
   284   /// can be indexed with integers from the ranges <tt>[0..nodeNum()-1]</tt>
   285   /// and <tt>[0..arcNum()-1]</tt>, respectively. 
   286   /// The index of an item is the same as its ID, it can be obtained
   287   /// using the corresponding \ref index() or \ref concepts::Digraph::id()
   288   /// "id()" function. A node or arc with a certain index can be obtained
   289   /// using node() or arc().
   290   ///
   291   /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
   292   /// Most of its member functions and nested classes are documented
   293   /// only in the concept class.
   294   ///
   295   /// This class provides constant time counting for nodes and arcs.
   296   ///
   297   /// \sa concepts::Digraph
   298   class StaticDigraph : public ExtendedStaticDigraphBase {
   299   public:
   300 
   301     typedef ExtendedStaticDigraphBase Parent;
   302   
   303   public:
   304   
   305     /// \brief Constructor
   306     ///
   307     /// Default constructor.
   308     StaticDigraph() : Parent() {}
   309 
   310     /// \brief The node with the given index.
   311     ///
   312     /// This function returns the node with the given index.
   313     /// \sa index()
   314     static Node node(int ix) { return Parent::nodeFromId(ix); }
   315 
   316     /// \brief The arc with the given index.
   317     ///
   318     /// This function returns the arc with the given index.
   319     /// \sa index()
   320     static Arc arc(int ix) { return Parent::arcFromId(ix); }
   321 
   322     /// \brief The index of the given node.
   323     ///
   324     /// This function returns the index of the the given node.
   325     /// \sa node()
   326     static int index(Node node) { return Parent::id(node); }
   327 
   328     /// \brief The index of the given arc.
   329     ///
   330     /// This function returns the index of the the given arc.
   331     /// \sa arc()
   332     static int index(Arc arc) { return Parent::id(arc); }
   333 
   334     /// \brief Number of nodes.
   335     ///
   336     /// This function returns the number of nodes.
   337     int nodeNum() const { return node_num; }
   338 
   339     /// \brief Number of arcs.
   340     ///
   341     /// This function returns the number of arcs.
   342     int arcNum() const { return arc_num; }
   343 
   344     /// \brief Build the digraph copying another digraph.
   345     ///
   346     /// This function builds the digraph copying another digraph of any
   347     /// kind. It can be called more than once, but in such case, the whole
   348     /// structure and all maps will be cleared and rebuilt.
   349     ///
   350     /// This method also makes possible to copy a digraph to a StaticDigraph
   351     /// structure using \ref DigraphCopy.
   352     /// 
   353     /// \param digraph An existing digraph to be copied.
   354     /// \param nodeRef The node references will be copied into this map.
   355     /// Its key type must be \c Digraph::Node and its value type must be
   356     /// \c StaticDigraph::Node.
   357     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
   358     /// concept.
   359     /// \param arcRef The arc references will be copied into this map.
   360     /// Its key type must be \c Digraph::Arc and its value type must be
   361     /// \c StaticDigraph::Arc.
   362     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   363     ///
   364     /// \note If you do not need the arc references, then you could use
   365     /// \ref NullMap for the last parameter. However the node references
   366     /// are required by the function itself, thus they must be readable
   367     /// from the map.
   368     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
   369     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
   370       if (built) Parent::clear();
   371       Parent::build(digraph, nodeRef, arcRef);
   372     }
   373   
   374     /// \brief Build the digraph from an arc list.
   375     ///
   376     /// This function builds the digraph from the given arc list.
   377     /// It can be called more than once, but in such case, the whole
   378     /// structure and all maps will be cleared and rebuilt.
   379     ///
   380     /// The list of the arcs must be given in the range <tt>[begin, end)</tt>
   381     /// specified by STL compatible itartors whose \c value_type must be
   382     /// <tt>std::pair<int,int></tt>.
   383     /// Each arc must be specified by a pair of integer indices
   384     /// from the range <tt>[0..n-1]</tt>. <i>The pairs must be in a
   385     /// non-decreasing order with respect to their first values.</i>
   386     /// If the k-th pair in the list is <tt>(i,j)</tt>, then
   387     /// <tt>arc(k-1)</tt> will connect <tt>node(i)</tt> to <tt>node(j)</tt>.
   388     ///
   389     /// \param n The number of nodes.
   390     /// \param begin An iterator pointing to the beginning of the arc list.
   391     /// \param end An iterator pointing to the end of the arc list.
   392     ///
   393     /// For example, a simple digraph can be constructed like this.
   394     /// \code
   395     ///   std::vector<std::pair<int,int> > arcs;
   396     ///   arcs.push_back(std::make_pair(0,1));
   397     ///   arcs.push_back(std::make_pair(0,2));
   398     ///   arcs.push_back(std::make_pair(1,3));
   399     ///   arcs.push_back(std::make_pair(1,2));
   400     ///   arcs.push_back(std::make_pair(3,0));
   401     ///   StaticDigraph gr;
   402     ///   gr.build(4, arcs.begin(), arcs.end());
   403     /// \endcode
   404     template <typename ArcListIterator>
   405     void build(int n, ArcListIterator begin, ArcListIterator end) {
   406       if (built) Parent::clear();
   407       StaticDigraphBase::build(n, begin, end);
   408       notifier(Node()).build();
   409       notifier(Arc()).build();
   410     }
   411 
   412     /// \brief Clear the digraph.
   413     ///
   414     /// This function erases all nodes and arcs from the digraph.
   415     void clear() {
   416       Parent::clear();
   417     }
   418 
   419   protected:
   420 
   421     using Parent::fastFirstOut;
   422     using Parent::fastNextOut;
   423     using Parent::fastLastOut;
   424     
   425   public:
   426 
   427     class OutArcIt : public Arc {
   428     public:
   429 
   430       OutArcIt() { }
   431 
   432       OutArcIt(Invalid i) : Arc(i) { }
   433 
   434       OutArcIt(const StaticDigraph& digraph, const Node& node) {
   435 	digraph.fastFirstOut(*this, node);
   436 	digraph.fastLastOut(last, node);
   437         if (last == *this) *this = INVALID;
   438       }
   439 
   440       OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {
   441         if (arc != INVALID) {
   442           digraph.fastLastOut(last, digraph.source(arc));
   443         }
   444       }
   445 
   446       OutArcIt& operator++() { 
   447         StaticDigraph::fastNextOut(*this);
   448         if (last == *this) *this = INVALID;
   449         return *this; 
   450       }
   451 
   452     private:
   453       Arc last;
   454     };
   455 
   456     Node baseNode(const OutArcIt &arc) const {
   457       return Parent::source(static_cast<const Arc&>(arc));
   458     }
   459 
   460     Node runningNode(const OutArcIt &arc) const {
   461       return Parent::target(static_cast<const Arc&>(arc));
   462     }
   463 
   464     Node baseNode(const InArcIt &arc) const {
   465       return Parent::target(static_cast<const Arc&>(arc));
   466     }
   467 
   468     Node runningNode(const InArcIt &arc) const {
   469       return Parent::source(static_cast<const Arc&>(arc));
   470     }
   471 
   472   };
   473 
   474 }
   475 
   476 #endif