RhodeCode

  /// \param CM Type of the cost map.

    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.

    /// arborescence.  It must conform to the \ref concepts::WriteMap

    /// "WriteMap" concept, and its value type must be \c bool

    /// (or convertible). Initially it will be set to \c false on each

    /// arc, then it will be set on each arborescence arc once.

    /// \param digraph The digraph to which we would like to calculate

    /// the \c ArborescenceMap.

    /// The type of the \c PredMap. It must confrom to the

    /// \ref concepts::WriteMap "WriteMap" concept, and its value type

    /// must be the \c Arc type of the digraph.

  /// This class provides an efficient implementation of the

  /// more sources should be given to the algorithm and it will calculate

  /// the minimum cost subgraph that is the union of arborescences with the

  /// The algorithm also provides an optimal dual solution, therefore

  /// \param GR The digraph type the algorithm runs on.

  /// \param CM A read-only arc map storing the costs of the

  /// relatively time consuming process to compute the arc costs if

  /// "MinCostArborescenceDefaultTraits<GR, CM>".

  template <typename GR,

    /// \brief The \ref MinCostArborescenceDefaultTraits "traits class" 

    /// of the algorithm. 

    struct SetArborescenceMapTraits : public Traits {

    /// setting \c ArborescenceMap type

    /// \c ArborescenceMap type.

    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept,

    /// and its value type must be \c bool (or convertible).

    /// Initially it will be set to \c false on each arc,

    /// then it will be set on each arborescence arc once.

    struct SetArborescenceMap

                                   SetArborescenceMapTraits<T> > {

    struct SetPredMapTraits : public Traits {

        return 0; // ignore warnings

    /// setting \c PredMap type

    /// \c PredMap type.

    /// It must meet the \ref concepts::WriteMap "WriteMap" concept, 

    /// and its value type must be the \c Arc type of the digraph.

    struct SetPredMap

      : public MinCostArborescence<Digraph, CostMap, SetPredMapTraits<T> > {

    /// \brief Sets the predecessor map.

    /// Sets the predecessor map.

    /// \warning The queue must not be empty.

    /// Returns the number of the nodes to be processed in the priority

    /// queue.

    void run(Node s) {

      addSource(s);

    /// \name Query Functions

    /// The result of the %MinCostArborescence algorithm can be obtained

    /// using these functions.\n

    /// Either run() or start() must be called before using them.

    /// @{

    /// \brief Returns the cost of the arborescence.

    ///

    /// Returns the cost of the arborescence.

    Value arborescenceCost() const {

      Value sum = 0;

      for (ArcIt it(*_digraph); it != INVALID; ++it) {

        if (arborescence(it)) {

          sum += (*_cost)[it];

        }

      }

      return sum;

    }

    /// \brief Returns \c true if the arc is in the arborescence.

    ///

    /// Returns \c true if the given arc is in the arborescence.

    /// \param arc An arc of the digraph.

    /// \pre \ref run() must be called before using this function.

    bool arborescence(Arc arc) const {

      return (*_pred)[_digraph->target(arc)] == arc;

    }

    /// \brief Returns a const reference to the arborescence map.

    ///

    /// Returns a const reference to the arborescence map.

    /// \pre \ref run() must be called before using this function.

    const ArborescenceMap& arborescenceMap() const {

      return *_arborescence;

    }

    /// \brief Returns the predecessor arc of the given node.

    ///

    /// Returns the predecessor arc of the given node.

    /// \pre \ref run() must be called before using this function.

    Arc pred(Node node) const {

      return (*_pred)[node];

    }

    /// \brief Returns a const reference to the pred map.

    ///

    /// Returns a const reference to the pred map.

    /// \pre \ref run() must be called before using this function.

    const PredMap& predMap() const {

      return *_pred;

    }

    /// \brief Indicates that a node is reachable from the sources.

    ///

    /// Indicates that a node is reachable from the sources.

    bool reached(Node node) const {

      return (*_node_order)[node] != -3;

    }

    /// \brief Indicates that a node is processed.

    ///

    /// Indicates that a node is processed. The arborescence path exists

    /// from the source to the given node.

    bool processed(Node node) const {

      return (*_node_order)[node] == -1;

    }

    /// \brief Returns the number of the dual variables in basis.

    ///

    /// Returns the number of the dual variables in basis.

    int dualNum() const {

      return _dual_variables.size();

    }

    /// \brief Returns the value of the dual solution.

    ///

    /// Returns the value of the dual solution. It should be

    /// equal to the arborescence value.

    Value dualValue() const {

      Value sum = 0;

      for (int i = 0; i < int(_dual_variables.size()); ++i) {

        sum += _dual_variables[i].value;

      }

      return sum;

    }

    /// \brief Returns the number of the nodes in the dual variable.

    ///

    /// Returns the number of the nodes in the dual variable.

    int dualSize(int k) const {

      return _dual_variables[k].end - _dual_variables[k].begin;

    }

    /// \brief Returns the value of the dual variable.

    ///

    /// Returns the the value of the dual variable.

    Value dualValue(int k) const {

      return _dual_variables[k].value;

    }

    /// \brief LEMON iterator for getting a dual variable.

    ///

    /// This class provides a common style LEMON iterator for getting a

    /// dual variable of \ref MinCostArborescence algorithm.

    /// It iterates over a subset of the nodes.

    class DualIt {

    public:

      /// \brief Constructor.

      ///

      /// Constructor for getting the nodeset of the dual variable

      /// of \ref MinCostArborescence algorithm.

      DualIt(const MinCostArborescence& algorithm, int variable)

        : _algorithm(&algorithm)

      {

        _index = _algorithm->_dual_variables[variable].begin;

        _last = _algorithm->_dual_variables[variable].end;

      }

      /// \brief Conversion to \c Node.

      ///

      /// Conversion to \c Node.

      operator Node() const {

        return _algorithm->_dual_node_list[_index];

      }

      /// \brief Increment operator.

      ///

      /// Increment operator.

      DualIt& operator++() {

        ++_index;

        return *this;

      }

      /// \brief Validity checking

      ///

      /// Checks whether the iterator is invalid.

      bool operator==(Invalid) const {

        return _index == _last;

      }

      /// \brief Validity checking

      ///

      /// Checks whether the iterator is valid.

      bool operator!=(Invalid) const {

        return _index != _last;

      }

    private:

      const MinCostArborescence* _algorithm;

      int _index, _last;

    };

    /// @}

  /// \param digraph The digraph the algorithm runs on.

  /// \param cost An arc map storing the costs.

  /// \param source The source node of the arborescence.

  /// \retval arborescence An arc map with \c bool (or convertible) value

  /// type that stores the arborescence.

  /// \return The total cost of the arborescence.

      ::template SetArborescenceMap<ArborescenceMap>

    return mca.arborescenceCost();

#include <lemon/concepts/digraph.h>

void checkMinCostArborescenceCompile()

{

  typedef double VType;

  typedef concepts::Digraph Digraph;

  typedef concepts::ReadMap<Digraph::Arc, VType> CostMap;

  typedef Digraph::Node Node;

  typedef Digraph::Arc Arc;

  typedef concepts::WriteMap<Digraph::Arc, bool> ArbMap;

  typedef concepts::ReadWriteMap<Digraph::Node, Digraph::Arc> PredMap;

  typedef MinCostArborescence<Digraph, CostMap>::

            SetArborescenceMap<ArbMap>::

            SetPredMap<PredMap>::Create MinCostArbType;

  Digraph g;

  Node s, n;

  Arc e;

  VType c;

  bool b;

  int i;

  CostMap cost;

  ArbMap arb;

  PredMap pred;

  MinCostArbType mcarb_test(g, cost);

  const MinCostArbType& const_mcarb_test = mcarb_test;

  mcarb_test

    .arborescenceMap(arb)

    .predMap(pred)

    .run(s);

  mcarb_test.init();

  mcarb_test.addSource(s);

  mcarb_test.start();

  n = mcarb_test.processNextNode();

  b = const_mcarb_test.emptyQueue();

  i = const_mcarb_test.queueSize();

  c = const_mcarb_test.arborescenceCost();

  b = const_mcarb_test.arborescence(e);

  e = const_mcarb_test.pred(n);

  const MinCostArbType::ArborescenceMap &am =

    const_mcarb_test.arborescenceMap();

  const MinCostArbType::PredMap &pm =

    const_mcarb_test.predMap();

  b = const_mcarb_test.reached(n);

  b = const_mcarb_test.processed(n);

  i = const_mcarb_test.dualNum();

  c = const_mcarb_test.dualValue();

  i = const_mcarb_test.dualSize(i);

  c = const_mcarb_test.dualValue(i);

  ignore_unused_variable_warning(am);

  ignore_unused_variable_warning(pm);

}

        check(sum == cost[it], "Invalid dual solution");

      check(sum <= cost[it], "Invalid dual solution");

  check(mca.dualValue() == mca.arborescenceCost(), "Invalid dual solution");

  check(mca.reached(source), "Invalid arborescence");

          mca.reached(digraph.target(a)), "Invalid arborescence");

        check(mca.pred(n) == a, "Invalid arborescence");

    check((n == source ? cnt == 0 : cnt == 1), "Invalid arborescence");

  check(mca.arborescenceCost() ==

        "Wrong result of the function interface");