lemon/min_cost_arborescence.h
changeset 598 a3402913cffe
parent 490 7f8560cb9d65
child 581 aa1804409f29
equal deleted inserted replaced
0:8aef6b3a1c9f 1:f0fba3977e39
    33 
    33 
    34 
    34 
    35   /// \brief Default traits class for MinCostArborescence class.
    35   /// \brief Default traits class for MinCostArborescence class.
    36   ///
    36   ///
    37   /// Default traits class for MinCostArborescence class.
    37   /// Default traits class for MinCostArborescence class.
    38   /// \param _Digraph Digraph type.
    38   /// \param GR Digraph type.
    39   /// \param _CostMap Type of cost map.
    39   /// \param CM Type of cost map.
    40   template <class _Digraph, class _CostMap>
    40   template <class GR, class CM>
    41   struct MinCostArborescenceDefaultTraits{
    41   struct MinCostArborescenceDefaultTraits{
    42 
    42 
    43     /// \brief The digraph type the algorithm runs on.
    43     /// \brief The digraph type the algorithm runs on.
    44     typedef _Digraph Digraph;
    44     typedef GR Digraph;
    45 
    45 
    46     /// \brief The type of the map that stores the arc costs.
    46     /// \brief The type of the map that stores the arc costs.
    47     ///
    47     ///
    48     /// The type of the map that stores the arc costs.
    48     /// The type of the map that stores the arc costs.
    49     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    49     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    50     typedef _CostMap CostMap;
    50     typedef CM CostMap;
    51 
    51 
    52     /// \brief The value type of the costs.
    52     /// \brief The value type of the costs.
    53     ///
    53     ///
    54     /// The value type of the costs.
    54     /// The value type of the costs.
    55     typedef typename CostMap::Value Value;
    55     typedef typename CostMap::Value Value;
    61     /// arborescence.  It must meet the \ref concepts::WriteMap
    61     /// arborescence.  It must meet the \ref concepts::WriteMap
    62     /// "WriteMap" concept.  Initially it will be set to false on each
    62     /// "WriteMap" concept.  Initially it will be set to false on each
    63     /// arc. After it will set all arborescence arcs once.
    63     /// arc. After it will set all arborescence arcs once.
    64     typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
    64     typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
    65 
    65 
    66     /// \brief Instantiates a ArborescenceMap.
    66     /// \brief Instantiates a \c ArborescenceMap.
    67     ///
    67     ///
    68     /// This function instantiates a \ref ArborescenceMap.
    68     /// This function instantiates a \c ArborescenceMap.
    69     /// \param digraph is the graph, to which we would like to
    69     /// \param digraph is the graph, to which we would like to
    70     /// calculate the ArborescenceMap.
    70     /// calculate the \c ArborescenceMap.
    71     static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
    71     static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
    72       return new ArborescenceMap(digraph);
    72       return new ArborescenceMap(digraph);
    73     }
    73     }
    74 
    74 
    75     /// \brief The type of the PredMap
    75     /// \brief The type of the \c PredMap
    76     ///
    76     ///
    77     /// The type of the PredMap. It is a node map with an arc value type.
    77     /// The type of the \c PredMap. It is a node map with an arc value type.
    78     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    78     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    79 
    79 
    80     /// \brief Instantiates a PredMap.
    80     /// \brief Instantiates a \c PredMap.
    81     ///
    81     ///
    82     /// This function instantiates a \ref PredMap.
    82     /// This function instantiates a \c PredMap.
    83     /// \param _digraph is the digraph, to which we would like to define the
    83     /// \param digraph The digraph to which we would like to define the
    84     /// PredMap.
    84     /// \c PredMap.
    85     static PredMap *createPredMap(const Digraph &digraph){
    85     static PredMap *createPredMap(const Digraph &digraph){
    86       return new PredMap(digraph);
    86       return new PredMap(digraph);
    87     }
    87     }
    88 
    88 
    89   };
    89   };
    96   /// %MinCostArborescence algorithm. The arborescence is a tree
    96   /// %MinCostArborescence algorithm. The arborescence is a tree
    97   /// which is directed from a given source node of the digraph. One or
    97   /// 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
    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
    99   /// the minimum cost subgraph which are union of arborescences with the
   100   /// given sources and spans all the nodes which are reachable from the
   100   /// given sources and spans all the nodes which are reachable from the
   101   /// sources. The time complexity of the algorithm is \f$ O(n^2+e) \f$.
   101   /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
   102   ///
   102   ///
   103   /// The algorithm provides also an optimal dual solution, therefore
   103   /// The algorithm provides also an optimal dual solution, therefore
   104   /// the optimality of the solution can be checked.
   104   /// the optimality of the solution can be checked.
   105   ///
   105   ///
   106   /// \param _Digraph The digraph type the algorithm runs on. The default value
   106   /// \param GR The digraph type the algorithm runs on. The default value
   107   /// is \ref ListDigraph.
   107   /// is \ref ListDigraph.
   108   /// \param _CostMap This read-only ArcMap determines the costs of the
   108   /// \param CM This read-only ArcMap determines the costs of the
   109   /// arcs. It is read once for each arc, so the map may involve in
   109   /// 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
   110   /// relatively time consuming process to compute the arc cost if
   111   /// it is necessary. The default map type is \ref
   111   /// it is necessary. The default map type is \ref
   112   /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
   112   /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
   113   /// \param _Traits Traits class to set various data types used
   113   /// \param TR Traits class to set various data types used
   114   /// by the algorithm. The default traits class is
   114   /// by the algorithm. The default traits class is
   115   /// \ref MinCostArborescenceDefaultTraits
   115   /// \ref MinCostArborescenceDefaultTraits
   116   /// "MinCostArborescenceDefaultTraits<_Digraph, _CostMap>".  See \ref
   116   /// "MinCostArborescenceDefaultTraits<GR, CM>".  See \ref
   117   /// MinCostArborescenceDefaultTraits for the documentation of a
   117   /// MinCostArborescenceDefaultTraits for the documentation of a
   118   /// MinCostArborescence traits class.
   118   /// MinCostArborescence traits class.
   119   ///
       
   120   /// \author Balazs Dezso
       
   121 #ifndef DOXYGEN
   119 #ifndef DOXYGEN
   122   template <typename _Digraph = ListDigraph,
   120   template <typename GR = ListDigraph,
   123             typename _CostMap = typename _Digraph::template ArcMap<int>,
   121             typename CM = typename GR::template ArcMap<int>,
   124             typename _Traits =
   122             typename TR =
   125             MinCostArborescenceDefaultTraits<_Digraph, _CostMap> >
   123               MinCostArborescenceDefaultTraits<GR, CM> >
   126 #else
   124 #else
   127   template <typename _Digraph, typename _CostMap, typedef _Traits>
   125   template <typename GR, typename CM, typedef TR>
   128 #endif
   126 #endif
   129   class MinCostArborescence {
   127   class MinCostArborescence {
   130   public:
   128   public:
   131 
   129 
   132     /// The traits.
   130     /// The traits.
   133     typedef _Traits Traits;
   131     typedef TR Traits;
   134     /// The type of the underlying digraph.
   132     /// The type of the underlying digraph.
   135     typedef typename Traits::Digraph Digraph;
   133     typedef typename Traits::Digraph Digraph;
   136     /// The type of the map that stores the arc costs.
   134     /// The type of the map that stores the arc costs.
   137     typedef typename Traits::CostMap CostMap;
   135     typedef typename Traits::CostMap CostMap;
   138     ///The type of the costs of the arcs.
   136     ///The type of the costs of the arcs.
   438 
   436 
   439     /// @}
   437     /// @}
   440 
   438 
   441     /// \brief Constructor.
   439     /// \brief Constructor.
   442     ///
   440     ///
   443     /// \param _digraph The digraph the algorithm will run on.
   441     /// \param digraph The digraph the algorithm will run on.
   444     /// \param _cost The cost map used by the algorithm.
   442     /// \param cost The cost map used by the algorithm.
   445     MinCostArborescence(const Digraph& digraph, const CostMap& cost)
   443     MinCostArborescence(const Digraph& digraph, const CostMap& cost)
   446       : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false),
   444       : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false),
   447         _arborescence(0), local_arborescence(false),
   445         _arborescence(0), local_arborescence(false),
   448         _arc_order(0), _node_order(0), _cost_arcs(0),
   446         _arc_order(0), _node_order(0), _cost_arcs(0),
   449         _heap_cross_ref(0), _heap(0) {}
   447         _heap_cross_ref(0), _heap(0) {}
   454     }
   452     }
   455 
   453 
   456     /// \brief Sets the arborescence map.
   454     /// \brief Sets the arborescence map.
   457     ///
   455     ///
   458     /// Sets the arborescence map.
   456     /// Sets the arborescence map.
   459     /// \return \c (*this)
   457     /// \return <tt>(*this)</tt>
   460     MinCostArborescence& arborescenceMap(ArborescenceMap& m) {
   458     MinCostArborescence& arborescenceMap(ArborescenceMap& m) {
   461       if (local_arborescence) {
   459       if (local_arborescence) {
   462         delete _arborescence;
   460         delete _arborescence;
   463       }
   461       }
   464       local_arborescence = false;
   462       local_arborescence = false;
   467     }
   465     }
   468 
   466 
   469     /// \brief Sets the arborescence map.
   467     /// \brief Sets the arborescence map.
   470     ///
   468     ///
   471     /// Sets the arborescence map.
   469     /// Sets the arborescence map.
   472     /// \return \c (*this)
   470     /// \return <tt>(*this)</tt>
   473     MinCostArborescence& predMap(PredMap& m) {
   471     MinCostArborescence& predMap(PredMap& m) {
   474       if (local_pred) {
   472       if (local_pred) {
   475         delete _pred;
   473         delete _pred;
   476       }
   474       }
   477       local_pred = false;
   475       local_pred = false;