COIN-OR::LEMON - Graph Library

Ignore:
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/min_cost_arborescence.h

    r672 r631  
    3737  /// Default traits class for MinCostArborescence class.
    3838  /// \param GR Digraph type.
    39   /// \param CM Type of the cost map.
     39  /// \param CM Type of cost map.
    4040  template <class GR, class CM>
    4141  struct MinCostArborescenceDefaultTraits{
     
    4747    ///
    4848    /// The type of the map that stores the arc costs.
    49     /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     49    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    5050    typedef CM CostMap;
    5151
     
    5959    ///
    6060    /// The type of the map that stores which arcs are in the
    61     /// arborescence.  It must conform to the \ref concepts::WriteMap
    62     /// "WriteMap" concept, and its value type must be \c bool
    63     /// (or convertible). Initially it will be set to \c false on each
    64     /// arc, then it will be set on each arborescence arc once.
     61    /// arborescence.  It must meet the \ref concepts::WriteMap
     62    /// "WriteMap" concept.  Initially it will be set to false on each
     63    /// arc. After it will set all arborescence arcs once.
    6564    typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
    6665
     
    6867    ///
    6968    /// This function instantiates a \c ArborescenceMap.
    70     /// \param digraph The digraph to which we would like to calculate
    71     /// the \c ArborescenceMap.
     69    /// \param digraph is the graph, to which we would like to
     70    /// calculate the \c ArborescenceMap.
    7271    static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
    7372      return new ArborescenceMap(digraph);
     
    7675    /// \brief The type of the \c PredMap
    7776    ///
    78     /// The type of the \c PredMap. It must confrom to the
    79     /// \ref concepts::WriteMap "WriteMap" concept, and its value type
    80     /// must be the \c Arc type of the digraph.
     77    /// The type of the \c PredMap. It is a node map with an arc value type.
    8178    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    8279
     
    9693  /// \brief Minimum Cost Arborescence algorithm class.
    9794  ///
    98   /// This class provides an efficient implementation of the
     95  /// This class provides an efficient implementation of
    9996  /// Minimum Cost Arborescence algorithm. The arborescence is a tree
    10097  /// which is directed from a given source node of the digraph. One or
    101   /// more sources should be given to the algorithm and it will calculate
    102   /// the minimum cost subgraph that is the union of arborescences with the
     98  /// more sources should be given for the algorithm and it will calculate
     99  /// the minimum cost subgraph which are union of arborescences with the
    103100  /// given sources and spans all the nodes which are reachable from the
    104101  /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
    105102  ///
    106   /// The algorithm also provides an optimal dual solution, therefore
     103  /// The algorithm provides also an optimal dual solution, therefore
    107104  /// the optimality of the solution can be checked.
    108105  ///
    109   /// \param GR The digraph type the algorithm runs on.
    110   /// \param CM A read-only arc map storing the costs of the
     106  /// \param GR The digraph type the algorithm runs on. The default value
     107  /// is \ref ListDigraph.
     108  /// \param CM This read-only ArcMap determines the costs of the
    111109  /// arcs. It is read once for each arc, so the map may involve in
    112   /// relatively time consuming process to compute the arc costs if
     110  /// relatively time consuming process to compute the arc cost if
    113111  /// it is necessary. The default map type is \ref
    114112  /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
     
    116114  /// by the algorithm. The default traits class is
    117115  /// \ref MinCostArborescenceDefaultTraits
    118   /// "MinCostArborescenceDefaultTraits<GR, CM>".
     116  /// "MinCostArborescenceDefaultTraits<GR, CM>".  See \ref
     117  /// MinCostArborescenceDefaultTraits for the documentation of a
     118  /// MinCostArborescence traits class.
    119119#ifndef DOXYGEN
    120   template <typename GR,
     120  template <typename GR = ListDigraph,
    121121            typename CM = typename GR::template ArcMap<int>,
    122122            typename TR =
     
    128128  public:
    129129
    130     /// \brief The \ref MinCostArborescenceDefaultTraits "traits class"
    131     /// of the algorithm.
     130    /// The traits.
    132131    typedef TR Traits;
    133132    /// The type of the underlying digraph.
     
    397396
    398397    template <class T>
    399     struct SetArborescenceMapTraits : public Traits {
     398    struct DefArborescenceMapTraits : public Traits {
    400399      typedef T ArborescenceMap;
    401400      static ArborescenceMap *createArborescenceMap(const Digraph &)
     
    407406
    408407    /// \brief \ref named-templ-param "Named parameter" for
    409     /// setting \c ArborescenceMap type
     408    /// setting ArborescenceMap type
    410409    ///
    411410    /// \ref named-templ-param "Named parameter" for setting
    412     /// \c ArborescenceMap type.
    413     /// It must conform to the \ref concepts::WriteMap "WriteMap" concept,
    414     /// and its value type must be \c bool (or convertible).
    415     /// Initially it will be set to \c false on each arc,
    416     /// then it will be set on each arborescence arc once.
     411    /// ArborescenceMap type
    417412    template <class T>
    418     struct SetArborescenceMap
     413    struct DefArborescenceMap
    419414      : public MinCostArborescence<Digraph, CostMap,
    420                                    SetArborescenceMapTraits<T> > {
     415                                   DefArborescenceMapTraits<T> > {
    421416    };
    422417
    423418    template <class T>
    424     struct SetPredMapTraits : public Traits {
     419    struct DefPredMapTraits : public Traits {
    425420      typedef T PredMap;
    426421      static PredMap *createPredMap(const Digraph &)
    427422      {
    428423        LEMON_ASSERT(false, "PredMap is not initialized");
    429         return 0; // ignore warnings
    430424      }
    431425    };
    432426
    433427    /// \brief \ref named-templ-param "Named parameter" for
    434     /// setting \c PredMap type
     428    /// setting PredMap type
    435429    ///
    436430    /// \ref named-templ-param "Named parameter" for setting
    437     /// \c PredMap type.
    438     /// It must meet the \ref concepts::WriteMap "WriteMap" concept,
    439     /// and its value type must be the \c Arc type of the digraph.
     431    /// PredMap type
    440432    template <class T>
    441     struct SetPredMap
    442       : public MinCostArborescence<Digraph, CostMap, SetPredMapTraits<T> > {
     433    struct DefPredMap
     434      : public MinCostArborescence<Digraph, CostMap, DefPredMapTraits<T> > {
    443435    };
    444436
     
    473465    }
    474466
    475     /// \brief Sets the predecessor map.
    476     ///
    477     /// Sets the predecessor map.
     467    /// \brief Sets the arborescence map.
     468    ///
     469    /// Sets the arborescence map.
    478470    /// \return <tt>(*this)</tt>
    479471    MinCostArborescence& predMap(PredMap& m) {
     
    485477      return *this;
    486478    }
     479
     480    /// \name Query Functions
     481    /// The result of the %MinCostArborescence algorithm can be obtained
     482    /// using these functions.\n
     483    /// Before the use of these functions,
     484    /// either run() or start() must be called.
     485
     486    /// @{
     487
     488    /// \brief Returns a reference to the arborescence map.
     489    ///
     490    /// Returns a reference to the arborescence map.
     491    const ArborescenceMap& arborescenceMap() const {
     492      return *_arborescence;
     493    }
     494
     495    /// \brief Returns true if the arc is in the arborescence.
     496    ///
     497    /// Returns true if the arc is in the arborescence.
     498    /// \param arc The arc of the digraph.
     499    /// \pre \ref run() must be called before using this function.
     500    bool arborescence(Arc arc) const {
     501      return (*_pred)[_digraph->target(arc)] == arc;
     502    }
     503
     504    /// \brief Returns a reference to the pred map.
     505    ///
     506    /// Returns a reference to the pred map.
     507    const PredMap& predMap() const {
     508      return *_pred;
     509    }
     510
     511    /// \brief Returns the predecessor arc of the given node.
     512    ///
     513    /// Returns the predecessor arc of the given node.
     514    Arc pred(Node node) const {
     515      return (*_pred)[node];
     516    }
     517
     518    /// \brief Returns the cost of the arborescence.
     519    ///
     520    /// Returns the cost of the arborescence.
     521    Value arborescenceValue() const {
     522      Value sum = 0;
     523      for (ArcIt it(*_digraph); it != INVALID; ++it) {
     524        if (arborescence(it)) {
     525          sum += (*_cost)[it];
     526        }
     527      }
     528      return sum;
     529    }
     530
     531    /// \brief Indicates that a node is reachable from the sources.
     532    ///
     533    /// Indicates that a node is reachable from the sources.
     534    bool reached(Node node) const {
     535      return (*_node_order)[node] != -3;
     536    }
     537
     538    /// \brief Indicates that a node is processed.
     539    ///
     540    /// Indicates that a node is processed. The arborescence path exists
     541    /// from the source to the given node.
     542    bool processed(Node node) const {
     543      return (*_node_order)[node] == -1;
     544    }
     545
     546    /// \brief Returns the number of the dual variables in basis.
     547    ///
     548    /// Returns the number of the dual variables in basis.
     549    int dualNum() const {
     550      return _dual_variables.size();
     551    }
     552
     553    /// \brief Returns the value of the dual solution.
     554    ///
     555    /// Returns the value of the dual solution. It should be
     556    /// equal to the arborescence value.
     557    Value dualValue() const {
     558      Value sum = 0;
     559      for (int i = 0; i < int(_dual_variables.size()); ++i) {
     560        sum += _dual_variables[i].value;
     561      }
     562      return sum;
     563    }
     564
     565    /// \brief Returns the number of the nodes in the dual variable.
     566    ///
     567    /// Returns the number of the nodes in the dual variable.
     568    int dualSize(int k) const {
     569      return _dual_variables[k].end - _dual_variables[k].begin;
     570    }
     571
     572    /// \brief Returns the value of the dual variable.
     573    ///
     574    /// Returns the the value of the dual variable.
     575    const Value& dualValue(int k) const {
     576      return _dual_variables[k].value;
     577    }
     578
     579    /// \brief Lemon iterator for get a dual variable.
     580    ///
     581    /// Lemon iterator for get a dual variable. This class provides
     582    /// a common style lemon iterator which gives back a subset of
     583    /// the nodes.
     584    class DualIt {
     585    public:
     586
     587      /// \brief Constructor.
     588      ///
     589      /// Constructor for get the nodeset of the variable.
     590      DualIt(const MinCostArborescence& algorithm, int variable)
     591        : _algorithm(&algorithm)
     592      {
     593        _index = _algorithm->_dual_variables[variable].begin;
     594        _last = _algorithm->_dual_variables[variable].end;
     595      }
     596
     597      /// \brief Conversion to node.
     598      ///
     599      /// Conversion to node.
     600      operator Node() const {
     601        return _algorithm->_dual_node_list[_index];
     602      }
     603
     604      /// \brief Increment operator.
     605      ///
     606      /// Increment operator.
     607      DualIt& operator++() {
     608        ++_index;
     609        return *this;
     610      }
     611
     612      /// \brief Validity checking
     613      ///
     614      /// Checks whether the iterator is invalid.
     615      bool operator==(Invalid) const {
     616        return _index == _last;
     617      }
     618
     619      /// \brief Validity checking
     620      ///
     621      /// Checks whether the iterator is valid.
     622      bool operator!=(Invalid) const {
     623        return _index != _last;
     624      }
     625
     626    private:
     627      const MinCostArborescence* _algorithm;
     628      int _index, _last;
     629    };
     630
     631    /// @}
    487632
    488633    /// \name Execution Control
     
    545690    /// \return The processed node.
    546691    ///
    547     /// \warning The queue must not be empty.
     692    /// \warning The queue must not be empty!
    548693    Node processNextNode() {
    549694      Node node = queue.back();
     
    568713    /// \brief Returns the number of the nodes to be processed.
    569714    ///
    570     /// Returns the number of the nodes to be processed in the priority
    571     /// queue.
     715    /// Returns the number of the nodes to be processed.
    572716    int queueSize() const {
    573717      return queue.size();
     
    611755    /// mca.start();
    612756    /// \endcode
    613     void run(Node s) {
     757    void run(Node node) {
    614758      init();
    615       addSource(s);
     759      addSource(node);
    616760      start();
    617761    }
    618762
    619763    ///@}
    620 
    621     /// \name Query Functions
    622     /// The result of the %MinCostArborescence algorithm can be obtained
    623     /// using these functions.\n
    624     /// Either run() or start() must be called before using them.
    625 
    626     /// @{
    627 
    628     /// \brief Returns the cost of the arborescence.
    629     ///
    630     /// Returns the cost of the arborescence.
    631     Value arborescenceCost() const {
    632       Value sum = 0;
    633       for (ArcIt it(*_digraph); it != INVALID; ++it) {
    634         if (arborescence(it)) {
    635           sum += (*_cost)[it];
    636         }
    637       }
    638       return sum;
    639     }
    640 
    641     /// \brief Returns \c true if the arc is in the arborescence.
    642     ///
    643     /// Returns \c true if the given arc is in the arborescence.
    644     /// \param arc An arc of the digraph.
    645     /// \pre \ref run() must be called before using this function.
    646     bool arborescence(Arc arc) const {
    647       return (*_pred)[_digraph->target(arc)] == arc;
    648     }
    649 
    650     /// \brief Returns a const reference to the arborescence map.
    651     ///
    652     /// Returns a const reference to the arborescence map.
    653     /// \pre \ref run() must be called before using this function.
    654     const ArborescenceMap& arborescenceMap() const {
    655       return *_arborescence;
    656     }
    657 
    658     /// \brief Returns the predecessor arc of the given node.
    659     ///
    660     /// Returns the predecessor arc of the given node.
    661     /// \pre \ref run() must be called before using this function.
    662     Arc pred(Node node) const {
    663       return (*_pred)[node];
    664     }
    665 
    666     /// \brief Returns a const reference to the pred map.
    667     ///
    668     /// Returns a const reference to the pred map.
    669     /// \pre \ref run() must be called before using this function.
    670     const PredMap& predMap() const {
    671       return *_pred;
    672     }
    673 
    674     /// \brief Indicates that a node is reachable from the sources.
    675     ///
    676     /// Indicates that a node is reachable from the sources.
    677     bool reached(Node node) const {
    678       return (*_node_order)[node] != -3;
    679     }
    680 
    681     /// \brief Indicates that a node is processed.
    682     ///
    683     /// Indicates that a node is processed. The arborescence path exists
    684     /// from the source to the given node.
    685     bool processed(Node node) const {
    686       return (*_node_order)[node] == -1;
    687     }
    688 
    689     /// \brief Returns the number of the dual variables in basis.
    690     ///
    691     /// Returns the number of the dual variables in basis.
    692     int dualNum() const {
    693       return _dual_variables.size();
    694     }
    695 
    696     /// \brief Returns the value of the dual solution.
    697     ///
    698     /// Returns the value of the dual solution. It should be
    699     /// equal to the arborescence value.
    700     Value dualValue() const {
    701       Value sum = 0;
    702       for (int i = 0; i < int(_dual_variables.size()); ++i) {
    703         sum += _dual_variables[i].value;
    704       }
    705       return sum;
    706     }
    707 
    708     /// \brief Returns the number of the nodes in the dual variable.
    709     ///
    710     /// Returns the number of the nodes in the dual variable.
    711     int dualSize(int k) const {
    712       return _dual_variables[k].end - _dual_variables[k].begin;
    713     }
    714 
    715     /// \brief Returns the value of the dual variable.
    716     ///
    717     /// Returns the the value of the dual variable.
    718     Value dualValue(int k) const {
    719       return _dual_variables[k].value;
    720     }
    721 
    722     /// \brief LEMON iterator for getting a dual variable.
    723     ///
    724     /// This class provides a common style LEMON iterator for getting a
    725     /// dual variable of \ref MinCostArborescence algorithm.
    726     /// It iterates over a subset of the nodes.
    727     class DualIt {
    728     public:
    729 
    730       /// \brief Constructor.
    731       ///
    732       /// Constructor for getting the nodeset of the dual variable
    733       /// of \ref MinCostArborescence algorithm.
    734       DualIt(const MinCostArborescence& algorithm, int variable)
    735         : _algorithm(&algorithm)
    736       {
    737         _index = _algorithm->_dual_variables[variable].begin;
    738         _last = _algorithm->_dual_variables[variable].end;
    739       }
    740 
    741       /// \brief Conversion to \c Node.
    742       ///
    743       /// Conversion to \c Node.
    744       operator Node() const {
    745         return _algorithm->_dual_node_list[_index];
    746       }
    747 
    748       /// \brief Increment operator.
    749       ///
    750       /// Increment operator.
    751       DualIt& operator++() {
    752         ++_index;
    753         return *this;
    754       }
    755 
    756       /// \brief Validity checking
    757       ///
    758       /// Checks whether the iterator is invalid.
    759       bool operator==(Invalid) const {
    760         return _index == _last;
    761       }
    762 
    763       /// \brief Validity checking
    764       ///
    765       /// Checks whether the iterator is valid.
    766       bool operator!=(Invalid) const {
    767         return _index != _last;
    768       }
    769 
    770     private:
    771       const MinCostArborescence* _algorithm;
    772       int _index, _last;
    773     };
    774 
    775     /// @}
    776764
    777765  };
     
    782770  ///
    783771  /// Function type interface for MinCostArborescence algorithm.
    784   /// \param digraph The digraph the algorithm runs on.
    785   /// \param cost An arc map storing the costs.
    786   /// \param source The source node of the arborescence.
    787   /// \retval arborescence An arc map with \c bool (or convertible) value
    788   /// type that stores the arborescence.
    789   /// \return The total cost of the arborescence.
     772  /// \param digraph The Digraph that the algorithm runs on.
     773  /// \param cost The CostMap of the arcs.
     774  /// \param source The source of the arborescence.
     775  /// \retval arborescence The bool ArcMap which stores the arborescence.
     776  /// \return The cost of the arborescence.
    790777  ///
    791778  /// \sa MinCostArborescence
     
    796783                                              ArborescenceMap& arborescence) {
    797784    typename MinCostArborescence<Digraph, CostMap>
    798       ::template SetArborescenceMap<ArborescenceMap>
     785      ::template DefArborescenceMap<ArborescenceMap>
    799786      ::Create mca(digraph, cost);
    800787    mca.arborescenceMap(arborescence);
    801788    mca.run(source);
    802     return mca.arborescenceCost();
     789    return mca.arborescenceValue();
    803790  }
    804791
  • test/min_cost_arborescence_test.cc

    r672 r522  
    2525#include <lemon/min_cost_arborescence.h>
    2626#include <lemon/lgf_reader.h>
    27 #include <lemon/concepts/digraph.h>
    2827
    2928#include "test_tools.h"
     
    7271  "source 0\n";
    7372
    74 
    75 void checkMinCostArborescenceCompile()
    76 {
    77   typedef double VType;
    78   typedef concepts::Digraph Digraph;
    79   typedef concepts::ReadMap<Digraph::Arc, VType> CostMap;
    80   typedef Digraph::Node Node;
    81   typedef Digraph::Arc Arc;
    82   typedef concepts::WriteMap<Digraph::Arc, bool> ArbMap;
    83   typedef concepts::ReadWriteMap<Digraph::Node, Digraph::Arc> PredMap;
    84 
    85   typedef MinCostArborescence<Digraph, CostMap>::
    86             SetArborescenceMap<ArbMap>::
    87             SetPredMap<PredMap>::Create MinCostArbType;
    88 
    89   Digraph g;
    90   Node s, n;
    91   Arc e;
    92   VType c;
    93   bool b;
    94   int i;
    95   CostMap cost;
    96   ArbMap arb;
    97   PredMap pred;
    98 
    99   MinCostArbType mcarb_test(g, cost);
    100   const MinCostArbType& const_mcarb_test = mcarb_test;
    101 
    102   mcarb_test
    103     .arborescenceMap(arb)
    104     .predMap(pred)
    105     .run(s);
    106 
    107   mcarb_test.init();
    108   mcarb_test.addSource(s);
    109   mcarb_test.start();
    110   n = mcarb_test.processNextNode();
    111   b = const_mcarb_test.emptyQueue();
    112   i = const_mcarb_test.queueSize();
    113  
    114   c = const_mcarb_test.arborescenceCost();
    115   b = const_mcarb_test.arborescence(e);
    116   e = const_mcarb_test.pred(n);
    117   const MinCostArbType::ArborescenceMap &am =
    118     const_mcarb_test.arborescenceMap();
    119   const MinCostArbType::PredMap &pm =
    120     const_mcarb_test.predMap();
    121   b = const_mcarb_test.reached(n);
    122   b = const_mcarb_test.processed(n);
    123  
    124   i = const_mcarb_test.dualNum();
    125   c = const_mcarb_test.dualValue();
    126   i = const_mcarb_test.dualSize(i);
    127   c = const_mcarb_test.dualValue(i);
    128  
    129   ignore_unused_variable_warning(am);
    130   ignore_unused_variable_warning(pm);
    131 }
    132 
    13373int main() {
    13474  typedef SmartDigraph Digraph;
     
    171111      }
    172112      if (mca.arborescence(it)) {
    173         check(sum == cost[it], "Invalid dual solution");
     113        check(sum == cost[it], "INVALID DUAL");
    174114      }
    175       check(sum <= cost[it], "Invalid dual solution");
     115      check(sum <= cost[it], "INVALID DUAL");
    176116    }
    177117  }
    178118
    179119
    180   check(mca.dualValue() == mca.arborescenceCost(), "Invalid dual solution");
     120  check(mca.dualValue() == mca.arborescenceValue(), "INVALID DUAL");
    181121
    182   check(mca.reached(source), "Invalid arborescence");
     122  check(mca.reached(source), "INVALID ARBORESCENCE");
    183123  for (ArcIt a(digraph); a != INVALID; ++a) {
    184124    check(!mca.reached(digraph.source(a)) ||
    185           mca.reached(digraph.target(a)), "Invalid arborescence");
     125          mca.reached(digraph.target(a)), "INVALID ARBORESCENCE");
    186126  }
    187127
     
    191131    for (InArcIt a(digraph, n); a != INVALID; ++a) {
    192132      if (mca.arborescence(a)) {
    193         check(mca.pred(n) == a, "Invalid arborescence");
     133        check(mca.pred(n) == a, "INVALID ARBORESCENCE");
    194134        ++cnt;
    195135      }
    196136    }
    197     check((n == source ? cnt == 0 : cnt == 1), "Invalid arborescence");
     137    check((n == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
    198138  }
    199139
    200140  Digraph::ArcMap<bool> arborescence(digraph);
    201   check(mca.arborescenceCost() ==
     141  check(mca.arborescenceValue() ==
    202142        minCostArborescence(digraph, cost, source, arborescence),
    203         "Wrong result of the function interface");
     143        "WRONG FUNCTION");
    204144
    205145  return 0;
Note: See TracChangeset for help on using the changeset viewer.