lemon/howard_mmc.h
changeset 905 de428ebb47ab
parent 864 d3ea191c3412
child 1002 f63ba40a60f4
equal deleted inserted replaced
0:e1b123034949 1:65e10d49f58e
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
   119              typename TR = HowardMmcDefaultTraits<GR, CM> >
   119              typename TR = HowardMmcDefaultTraits<GR, CM> >
   120 #endif
   120 #endif
   121   class HowardMmc
   121   class HowardMmc
   122   {
   122   {
   123   public:
   123   public:
   124   
   124 
   125     /// The type of the digraph
   125     /// The type of the digraph
   126     typedef typename TR::Digraph Digraph;
   126     typedef typename TR::Digraph Digraph;
   127     /// The type of the cost map
   127     /// The type of the cost map
   128     typedef typename TR::CostMap CostMap;
   128     typedef typename TR::CostMap CostMap;
   129     /// The type of the arc costs
   129     /// The type of the arc costs
   150     typedef TR Traits;
   150     typedef TR Traits;
   151 
   151 
   152   private:
   152   private:
   153 
   153 
   154     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   154     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   155   
   155 
   156     // The digraph the algorithm runs on
   156     // The digraph the algorithm runs on
   157     const Digraph &_gr;
   157     const Digraph &_gr;
   158     // The cost of the arcs
   158     // The cost of the arcs
   159     const CostMap &_cost;
   159     const CostMap &_cost;
   160 
   160 
   177     int _comp_num;
   177     int _comp_num;
   178     typename Digraph::template NodeMap<int> _comp;
   178     typename Digraph::template NodeMap<int> _comp;
   179     std::vector<std::vector<Node> > _comp_nodes;
   179     std::vector<std::vector<Node> > _comp_nodes;
   180     std::vector<Node>* _nodes;
   180     std::vector<Node>* _nodes;
   181     typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;
   181     typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;
   182     
   182 
   183     // Queue used for BFS search
   183     // Queue used for BFS search
   184     std::vector<Node> _queue;
   184     std::vector<Node> _queue;
   185     int _qfront, _qback;
   185     int _qfront, _qback;
   186 
   186 
   187     Tolerance _tolerance;
   187     Tolerance _tolerance;
   188   
   188 
   189     // Infinite constant
   189     // Infinite constant
   190     const LargeCost INF;
   190     const LargeCost INF;
   191 
   191 
   192   public:
   192   public:
   193   
   193 
   194     /// \name Named Template Parameters
   194     /// \name Named Template Parameters
   195     /// @{
   195     /// @{
   196 
   196 
   197     template <typename T>
   197     template <typename T>
   198     struct SetLargeCostTraits : public Traits {
   198     struct SetLargeCostTraits : public Traits {
   226     template <typename T>
   226     template <typename T>
   227     struct SetPath
   227     struct SetPath
   228       : public HowardMmc<GR, CM, SetPathTraits<T> > {
   228       : public HowardMmc<GR, CM, SetPathTraits<T> > {
   229       typedef HowardMmc<GR, CM, SetPathTraits<T> > Create;
   229       typedef HowardMmc<GR, CM, SetPathTraits<T> > Create;
   230     };
   230     };
   231     
   231 
   232     /// @}
   232     /// @}
   233 
   233 
   234   protected:
   234   protected:
   235 
   235 
   236     HowardMmc() {}
   236     HowardMmc() {}
   332     /// \return \c true if a directed cycle exists in the digraph.
   332     /// \return \c true if a directed cycle exists in the digraph.
   333     bool findCycleMean() {
   333     bool findCycleMean() {
   334       // Initialize and find strongly connected components
   334       // Initialize and find strongly connected components
   335       init();
   335       init();
   336       findComponents();
   336       findComponents();
   337       
   337 
   338       // Find the minimum cycle mean in the components
   338       // Find the minimum cycle mean in the components
   339       for (int comp = 0; comp < _comp_num; ++comp) {
   339       for (int comp = 0; comp < _comp_num; ++comp) {
   340         // Find the minimum mean cycle in the current component
   340         // Find the minimum mean cycle in the current component
   341         if (!buildPolicyGraph(comp)) continue;
   341         if (!buildPolicyGraph(comp)) continue;
   342         while (true) {
   342         while (true) {
   443       _best_found = false;
   443       _best_found = false;
   444       _best_cost = 0;
   444       _best_cost = 0;
   445       _best_size = 1;
   445       _best_size = 1;
   446       _cycle_path->clear();
   446       _cycle_path->clear();
   447     }
   447     }
   448     
   448 
   449     // Find strongly connected components and initialize _comp_nodes
   449     // Find strongly connected components and initialize _comp_nodes
   450     // and _in_arcs
   450     // and _in_arcs
   451     void findComponents() {
   451     void findComponents() {
   452       _comp_num = stronglyConnectedComponents(_gr, _comp);
   452       _comp_num = stronglyConnectedComponents(_gr, _comp);
   453       _comp_nodes.resize(_comp_num);
   453       _comp_nodes.resize(_comp_num);