COIN-OR::LEMON - Graph Library

Changeset 672:029a48052c67 in lemon


Ignore:
Timestamp:
04/26/09 16:44:53 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Modify the interface of MinCostArborescence? + improvements (#267)

  • Rename arborescenceValue() to arborescenceCost().
  • Rename DefXyz? template named paramaters to SetXyz?.
  • Rearrange public functions (for better doc).
  • Doc improvements.
  • Extend the test file with interface checking.
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/min_cost_arborescence.h

    r631 r672  
    3737  /// Default traits class for MinCostArborescence class.
    3838  /// \param GR Digraph type.
    39   /// \param CM Type of cost map.
     39  /// \param CM Type of the 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 meet the \ref concepts::ReadMap "ReadMap" concept.
     49    /// It must conform to 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 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.
     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.
    6465    typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
    6566
     
    6768    ///
    6869    /// This function instantiates a \c ArborescenceMap.
    69     /// \param digraph is the graph, to which we would like to
    70     /// calculate the \c ArborescenceMap.
     70    /// \param digraph The digraph to which we would like to calculate
     71    /// the \c ArborescenceMap.
    7172    static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
    7273      return new ArborescenceMap(digraph);
     
    7576    /// \brief The type of the \c PredMap
    7677    ///
    77     /// The type of the \c PredMap. It is a node map with an arc value type.
     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.
    7881    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    7982
     
    9396  /// \brief Minimum Cost Arborescence algorithm class.
    9497  ///
    95   /// This class provides an efficient implementation of
     98  /// This class provides an efficient implementation of the
    9699  /// Minimum Cost Arborescence algorithm. The arborescence is a tree
    97100  /// which is directed from a given source node of the digraph. One or
    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
     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
    100103  /// given sources and spans all the nodes which are reachable from the
    101104  /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
    102105  ///
    103   /// The algorithm provides also an optimal dual solution, therefore
     106  /// The algorithm also provides an optimal dual solution, therefore
    104107  /// the optimality of the solution can be checked.
    105108  ///
    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
     109  /// \param GR The digraph type the algorithm runs on.
     110  /// \param CM A read-only arc map storing the costs of the
    109111  /// arcs. It is read once for each arc, so the map may involve in
    110   /// relatively time consuming process to compute the arc cost if
     112  /// relatively time consuming process to compute the arc costs if
    111113  /// it is necessary. The default map type is \ref
    112114  /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
     
    114116  /// by the algorithm. The default traits class is
    115117  /// \ref MinCostArborescenceDefaultTraits
    116   /// "MinCostArborescenceDefaultTraits<GR, CM>".  See \ref
    117   /// MinCostArborescenceDefaultTraits for the documentation of a
    118   /// MinCostArborescence traits class.
     118  /// "MinCostArborescenceDefaultTraits<GR, CM>".
    119119#ifndef DOXYGEN
    120   template <typename GR = ListDigraph,
     120  template <typename GR,
    121121            typename CM = typename GR::template ArcMap<int>,
    122122            typename TR =
     
    128128  public:
    129129
    130     /// The traits.
     130    /// \brief The \ref MinCostArborescenceDefaultTraits "traits class"
     131    /// of the algorithm.
    131132    typedef TR Traits;
    132133    /// The type of the underlying digraph.
     
    396397
    397398    template <class T>
    398     struct DefArborescenceMapTraits : public Traits {
     399    struct SetArborescenceMapTraits : public Traits {
    399400      typedef T ArborescenceMap;
    400401      static ArborescenceMap *createArborescenceMap(const Digraph &)
     
    406407
    407408    /// \brief \ref named-templ-param "Named parameter" for
    408     /// setting ArborescenceMap type
     409    /// setting \c ArborescenceMap type
    409410    ///
    410411    /// \ref named-templ-param "Named parameter" for setting
    411     /// ArborescenceMap type
     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.
    412417    template <class T>
    413     struct DefArborescenceMap
     418    struct SetArborescenceMap
    414419      : public MinCostArborescence<Digraph, CostMap,
    415                                    DefArborescenceMapTraits<T> > {
     420                                   SetArborescenceMapTraits<T> > {
    416421    };
    417422
    418423    template <class T>
    419     struct DefPredMapTraits : public Traits {
     424    struct SetPredMapTraits : public Traits {
    420425      typedef T PredMap;
    421426      static PredMap *createPredMap(const Digraph &)
    422427      {
    423428        LEMON_ASSERT(false, "PredMap is not initialized");
     429        return 0; // ignore warnings
    424430      }
    425431    };
    426432
    427433    /// \brief \ref named-templ-param "Named parameter" for
    428     /// setting PredMap type
     434    /// setting \c PredMap type
    429435    ///
    430436    /// \ref named-templ-param "Named parameter" for setting
    431     /// PredMap type
     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.
    432440    template <class T>
    433     struct DefPredMap
    434       : public MinCostArborescence<Digraph, CostMap, DefPredMapTraits<T> > {
     441    struct SetPredMap
     442      : public MinCostArborescence<Digraph, CostMap, SetPredMapTraits<T> > {
    435443    };
    436444
     
    465473    }
    466474
    467     /// \brief Sets the arborescence map.
    468     ///
    469     /// Sets the arborescence map.
     475    /// \brief Sets the predecessor map.
     476    ///
     477    /// Sets the predecessor map.
    470478    /// \return <tt>(*this)</tt>
    471479    MinCostArborescence& predMap(PredMap& m) {
     
    477485      return *this;
    478486    }
    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     /// @}
    632487
    633488    /// \name Execution Control
     
    690545    /// \return The processed node.
    691546    ///
    692     /// \warning The queue must not be empty!
     547    /// \warning The queue must not be empty.
    693548    Node processNextNode() {
    694549      Node node = queue.back();
     
    713568    /// \brief Returns the number of the nodes to be processed.
    714569    ///
    715     /// Returns the number of the nodes to be processed.
     570    /// Returns the number of the nodes to be processed in the priority
     571    /// queue.
    716572    int queueSize() const {
    717573      return queue.size();
     
    755611    /// mca.start();
    756612    /// \endcode
    757     void run(Node node) {
     613    void run(Node s) {
    758614      init();
    759       addSource(node);
     615      addSource(s);
    760616      start();
    761617    }
    762618
    763619    ///@}
     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    /// @}
    764776
    765777  };
     
    770782  ///
    771783  /// Function type interface for MinCostArborescence algorithm.
    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.
     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.
    777790  ///
    778791  /// \sa MinCostArborescence
     
    783796                                              ArborescenceMap& arborescence) {
    784797    typename MinCostArborescence<Digraph, CostMap>
    785       ::template DefArborescenceMap<ArborescenceMap>
     798      ::template SetArborescenceMap<ArborescenceMap>
    786799      ::Create mca(digraph, cost);
    787800    mca.arborescenceMap(arborescence);
    788801    mca.run(source);
    789     return mca.arborescenceValue();
     802    return mca.arborescenceCost();
    790803  }
    791804
  • test/min_cost_arborescence_test.cc

    r522 r672  
    2525#include <lemon/min_cost_arborescence.h>
    2626#include <lemon/lgf_reader.h>
     27#include <lemon/concepts/digraph.h>
    2728
    2829#include "test_tools.h"
     
    7172  "source 0\n";
    7273
     74
     75void 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
    73133int main() {
    74134  typedef SmartDigraph Digraph;
     
    111171      }
    112172      if (mca.arborescence(it)) {
    113         check(sum == cost[it], "INVALID DUAL");
     173        check(sum == cost[it], "Invalid dual solution");
    114174      }
    115       check(sum <= cost[it], "INVALID DUAL");
     175      check(sum <= cost[it], "Invalid dual solution");
    116176    }
    117177  }
    118178
    119179
    120   check(mca.dualValue() == mca.arborescenceValue(), "INVALID DUAL");
    121 
    122   check(mca.reached(source), "INVALID ARBORESCENCE");
     180  check(mca.dualValue() == mca.arborescenceCost(), "Invalid dual solution");
     181
     182  check(mca.reached(source), "Invalid arborescence");
    123183  for (ArcIt a(digraph); a != INVALID; ++a) {
    124184    check(!mca.reached(digraph.source(a)) ||
    125           mca.reached(digraph.target(a)), "INVALID ARBORESCENCE");
     185          mca.reached(digraph.target(a)), "Invalid arborescence");
    126186  }
    127187
     
    131191    for (InArcIt a(digraph, n); a != INVALID; ++a) {
    132192      if (mca.arborescence(a)) {
    133         check(mca.pred(n) == a, "INVALID ARBORESCENCE");
     193        check(mca.pred(n) == a, "Invalid arborescence");
    134194        ++cnt;
    135195      }
    136196    }
    137     check((n == source ? cnt == 0 : cnt == 1), "INVALID ARBORESCENCE");
     197    check((n == source ? cnt == 0 : cnt == 1), "Invalid arborescence");
    138198  }
    139199
    140200  Digraph::ArcMap<bool> arborescence(digraph);
    141   check(mca.arborescenceValue() ==
     201  check(mca.arborescenceCost() ==
    142202        minCostArborescence(digraph, cost, source, arborescence),
    143         "WRONG FUNCTION");
     203        "Wrong result of the function interface");
    144204
    145205  return 0;
Note: See TracChangeset for help on using the changeset viewer.