ceph/src/boost/boost/graph/howard_cycle_ratio.hpp

   1 // Copyright (C) 2006-2009 Dmitry Bufistov and Andrey Parfenov
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #ifndef BOOST_GRAPH_CYCLE_RATIO_HOWARD_HPP
   8 #define BOOST_GRAPH_CYCLE_RATIO_HOWARD_HPP
   9
  10 #include <vector>
  11 #include <list>
  12 #include <algorithm>
  13 #include <functional>
  14 #include <limits>
  15
  16 #include <boost/bind/bind.hpp>
  17 #include <boost/tuple/tuple.hpp>
  18 #include <boost/type_traits/is_same.hpp>
  19 #include <boost/type_traits/remove_const.hpp>
  20 #include <boost/concept_check.hpp>
  21 #include <boost/pending/queue.hpp>
  22 #include <boost/property_map/property_map.hpp>
  23 #include <boost/graph/graph_traits.hpp>
  24 #include <boost/graph/graph_concepts.hpp>
  25 #include <boost/concept/assert.hpp>
  26 #include <boost/algorithm/minmax_element.hpp>
  27
  28 /** @file howard_cycle_ratio.hpp
  29  * @brief The implementation of the maximum/minimum cycle ratio/mean algorithm.
  30  * @author Dmitry Bufistov
  31  * @author Andrey Parfenov
  32  */
  33
  34 namespace boost
  35 {
  36
  37 /**
  38  * The mcr_float is like numeric_limits, but only for floating point types
  39  * and only defines infinity() and epsilon(). This class is primarily used
  40  * to encapsulate a less-precise epsilon than natively supported by the
  41  * floating point type.
  42  */
  43 template < typename Float = double > struct mcr_float
  44 {
  45     typedef Float value_type;
  46
  47     static Float infinity()
  48     {
  49         return std::numeric_limits< value_type >::infinity();
  50     }
  51
  52     static Float epsilon() { return Float(-0.005); }
  53 };
  54
  55 namespace detail
  56 {
  57
  58     template < typename FloatTraits > struct min_comparator_props
  59     {
  60         typedef std::greater< typename FloatTraits::value_type > comparator;
  61         static const int multiplier = 1;
  62     };
  63
  64     template < typename FloatTraits > struct max_comparator_props
  65     {
  66         typedef std::less< typename FloatTraits::value_type > comparator;
  67         static const int multiplier = -1;
  68     };
  69
  70     template < typename FloatTraits, typename ComparatorProps >
  71     struct float_wrapper
  72     {
  73         typedef typename FloatTraits::value_type value_type;
  74         typedef ComparatorProps comparator_props_t;
  75         typedef typename ComparatorProps::comparator comparator;
  76
  77         static value_type infinity()
  78         {
  79             return FloatTraits::infinity() * ComparatorProps::multiplier;
  80         }
  81
  82         static value_type epsilon()
  83         {
  84             return FloatTraits::epsilon() * ComparatorProps::multiplier;
  85         }
  86     };
  87
  88     /*! @class mcr_howard
  89      * @brief Calculates optimum (maximum/minimum) cycle ratio of a directed
  90      * graph. Uses  Howard's iteration policy algorithm. </br>(It is described
  91      * in the paper "Experimental Analysis of the Fastest Optimum Cycle Ratio
  92      * and Mean Algorithm" by Ali Dasdan).
  93      */
  94     template < typename FloatTraits, typename Graph, typename VertexIndexMap,
  95         typename EdgeWeight1, typename EdgeWeight2 >
  96     class mcr_howard
  97     {
  98     public:
  99         typedef typename FloatTraits::value_type float_t;
 100         typedef typename FloatTraits::comparator_props_t cmp_props_t;
 101         typedef typename FloatTraits::comparator comparator_t;
 102         typedef enum
 103         {
 104             my_white = 0,
 105             my_black
 106         } my_color_type;
 107         typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
 108         typedef typename graph_traits< Graph >::edge_descriptor edge_t;
 109         typedef typename graph_traits< Graph >::vertices_size_type vn_t;
 110         typedef std::vector< float_t > vp_t;
 111         typedef typename boost::iterator_property_map< typename vp_t::iterator,
 112             VertexIndexMap >
 113             distance_map_t; // V -> float_t
 114
 115         typedef typename std::vector< edge_t > ve_t;
 116         typedef std::vector< my_color_type > vcol_t;
 117         typedef
 118             typename ::boost::iterator_property_map< typename ve_t::iterator,
 119                 VertexIndexMap >
 120                 policy_t; // Vertex -> Edge
 121         typedef
 122             typename ::boost::iterator_property_map< typename vcol_t::iterator,
 123                 VertexIndexMap >
 124                 color_map_t;
 125
 126         typedef typename std::list< vertex_t >
 127             pinel_t; // The in_edges list of the policy graph
 128         typedef typename std::vector< pinel_t > inedges1_t;
 129         typedef typename ::boost::iterator_property_map<
 130             typename inedges1_t::iterator, VertexIndexMap >
 131             inedges_t;
 132         typedef typename std::vector< edge_t > critical_cycle_t;
 133
 134         // Bad  vertex flag. If true, then the vertex is "bad".
 135         // Vertex is "bad" if its out_degree is equal to zero.
 136         typedef
 137             typename boost::iterator_property_map< std::vector< int >::iterator,
 138                 VertexIndexMap >
 139                 badv_t;
 140
 141         /*!
 142          * Constructor
 143          * \param g = (V, E) - a directed multigraph.
 144          * \param vim  Vertex Index Map. Read property Map: V -> [0,
 145          * num_vertices(g)). \param ewm  edge weight map. Read property map: E
 146          * -> R \param ew2m  edge weight map. Read property map: E -> R+ \param
 147          * infty A big enough value to guaranty that there exist a cycle with
 148          *  better ratio.
 149          * \param cmp The compare operator for float_ts.
 150          */
 151         mcr_howard(const Graph& g, VertexIndexMap vim, EdgeWeight1 ewm,
 152             EdgeWeight2 ew2m)
 153         : m_g(g)
 154         , m_vim(vim)
 155         , m_ew1m(ewm)
 156         , m_ew2m(ew2m)
 157         , m_bound(mcr_bound())
 158         , m_cr(m_bound)
 159         , m_V(num_vertices(m_g))
 160         , m_dis(m_V, 0)
 161         , m_dm(m_dis.begin(), m_vim)
 162         , m_policyc(m_V)
 163         , m_policy(m_policyc.begin(), m_vim)
 164         , m_inelc(m_V)
 165         , m_inel(m_inelc.begin(), m_vim)
 166         , m_badvc(m_V, false)
 167         , m_badv(m_badvc.begin(), m_vim)
 168         , m_colcv(m_V)
 169         , m_col_bfs(m_V)
 170         {
 171         }
 172
 173         /*!
 174          * \return maximum/minimum_{for all cycles C}
 175          *         [sum_{e in C} w1(e)] / [sum_{e in C} w2(e)],
 176          * or FloatTraits::infinity() if graph has no cycles.
 177          */
 178         float_t ocr_howard()
 179         {
 180             construct_policy_graph();
 181             int k = 0;
 182             float_t mcr = 0;
 183             do
 184             {
 185                 mcr = policy_mcr();
 186                 ++k;
 187             } while (
 188                 try_improve_policy(mcr) && k < 100); // To avoid infinite loop
 189
 190             const float_t eps_ = -0.00000001 * cmp_props_t::multiplier;
 191             if (m_cmp(mcr, m_bound + eps_))
 192             {
 193                 return FloatTraits::infinity();
 194             }
 195             else
 196             {
 197                 return mcr;
 198             }
 199         }
 200         virtual ~mcr_howard() {}
 201
 202     protected:
 203         virtual void store_critical_edge(edge_t, critical_cycle_t&) {}
 204         virtual void store_critical_cycle(critical_cycle_t&) {}
 205
 206     private:
 207         /*!
 208          * \return lower/upper bound for the maximal/minimal cycle ratio
 209          */
 210         float_t mcr_bound()
 211         {
 212             typename graph_traits< Graph >::vertex_iterator vi, vie;
 213             typename graph_traits< Graph >::out_edge_iterator oei, oeie;
 214             float_t cz = (std::numeric_limits< float_t >::max)(); // Closest to
 215                                                                   // zero value
 216             float_t s = 0;
 217             const float_t eps_ = std::numeric_limits< float_t >::epsilon();
 218             for (boost::tie(vi, vie) = vertices(m_g); vi != vie; ++vi)
 219             {
 220                 for (boost::tie(oei, oeie) = out_edges(*vi, m_g); oei != oeie;
 221                      ++oei)
 222                 {
 223                     s += std::abs(m_ew1m[*oei]);
 224                     float_t a = std::abs(m_ew2m[*oei]);
 225                     if (a > eps_ && a < cz)
 226                     {
 227                         cz = a;
 228                     }
 229                 }
 230             }
 231             return cmp_props_t::multiplier * (s / cz);
 232         }
 233
 234         /*!
 235          *  Constructs an arbitrary policy graph.
 236          */
 237         void construct_policy_graph()
 238         {
 239             m_sink = graph_traits< Graph >().null_vertex();
 240             typename graph_traits< Graph >::vertex_iterator vi, vie;
 241             typename graph_traits< Graph >::out_edge_iterator oei, oeie;
 242             for (boost::tie(vi, vie) = vertices(m_g); vi != vie; ++vi)
 243             {
 244                 using namespace boost::placeholders;
 245
 246                 boost::tie(oei, oeie) = out_edges(*vi, m_g);
 247                 typename graph_traits< Graph >::out_edge_iterator mei
 248                     = boost::first_max_element(oei, oeie,
 249                         boost::bind(m_cmp,
 250                             boost::bind(&EdgeWeight1::operator[], m_ew1m, _1),
 251                             boost::bind(&EdgeWeight1::operator[], m_ew1m, _2)));
 252                 if (mei == oeie)
 253                 {
 254                     if (m_sink == graph_traits< Graph >().null_vertex())
 255                     {
 256                         m_sink = *vi;
 257                     }
 258                     m_badv[*vi] = true;
 259                     m_inel[m_sink].push_back(*vi);
 260                 }
 261                 else
 262                 {
 263                     m_inel[target(*mei, m_g)].push_back(*vi);
 264                     m_policy[*vi] = *mei;
 265                 }
 266             }
 267         }
 268         /*! Sets the distance value for all vertices "v" such that there is
 269          * a path from "v" to "sv". It does "inverse" breadth first visit of the
 270          * policy graph, starting from the vertex "sv".
 271          */
 272         void mcr_bfv(vertex_t sv, float_t cr, color_map_t c)
 273         {
 274             boost::queue< vertex_t > Q;
 275             c[sv] = my_black;
 276             Q.push(sv);
 277             while (!Q.empty())
 278             {
 279                 vertex_t v = Q.top();
 280                 Q.pop();
 281                 for (typename pinel_t::const_iterator itr = m_inel[v].begin();
 282                      itr != m_inel[v].end(); ++itr)
 283                 // For all in_edges of the policy graph
 284                 {
 285                     if (*itr != sv)
 286                     {
 287                         if (m_badv[*itr])
 288                         {
 289                             m_dm[*itr] = m_dm[v] + m_bound - cr;
 290                         }
 291                         else
 292                         {
 293                             m_dm[*itr] = m_dm[v] + m_ew1m[m_policy[*itr]]
 294                                 - m_ew2m[m_policy[*itr]] * cr;
 295                         }
 296                         c[*itr] = my_black;
 297                         Q.push(*itr);
 298                     }
 299                 }
 300             }
 301         }
 302
 303         /*!
 304          * \param sv an arbitrary (undiscovered) vertex of the policy graph.
 305          * \return a vertex in the policy graph that belongs to a cycle.
 306          * Performs a depth first visit until a cycle edge is found.
 307          */
 308         vertex_t find_cycle_vertex(vertex_t sv)
 309         {
 310             vertex_t gv = sv;
 311             std::fill(m_colcv.begin(), m_colcv.end(), my_white);
 312             color_map_t cm(m_colcv.begin(), m_vim);
 313             do
 314             {
 315                 cm[gv] = my_black;
 316                 if (!m_badv[gv])
 317                 {
 318                     gv = target(m_policy[gv], m_g);
 319                 }
 320                 else
 321                 {
 322                     gv = m_sink;
 323                 }
 324             } while (cm[gv] != my_black);
 325             return gv;
 326         }
 327
 328         /*!
 329          * \param sv - vertex that belongs to a cycle in the policy graph.
 330          */
 331         float_t cycle_ratio(vertex_t sv)
 332         {
 333             if (sv == m_sink)
 334                 return m_bound;
 335             std::pair< float_t, float_t > sums_(float_t(0), float_t(0));
 336             vertex_t v = sv;
 337             critical_cycle_t cc;
 338             do
 339             {
 340                 store_critical_edge(m_policy[v], cc);
 341                 sums_.first += m_ew1m[m_policy[v]];
 342                 sums_.second += m_ew2m[m_policy[v]];
 343                 v = target(m_policy[v], m_g);
 344             } while (v != sv);
 345             float_t cr = sums_.first / sums_.second;
 346             if (m_cmp(m_cr, cr))
 347             {
 348                 m_cr = cr;
 349                 store_critical_cycle(cc);
 350             }
 351             return cr;
 352         }
 353
 354         /*!
 355          *  Finds the optimal cycle ratio of the policy graph
 356          */
 357         float_t policy_mcr()
 358         {
 359             using namespace boost::placeholders;
 360
 361             std::fill(m_col_bfs.begin(), m_col_bfs.end(), my_white);
 362             color_map_t vcm_ = color_map_t(m_col_bfs.begin(), m_vim);
 363             typename graph_traits< Graph >::vertex_iterator uv_itr, vie;
 364             boost::tie(uv_itr, vie) = vertices(m_g);
 365             float_t mcr = m_bound;
 366             while ((uv_itr = std::find_if(uv_itr, vie,
 367                         boost::bind(std::equal_to< my_color_type >(), my_white,
 368                             boost::bind(&color_map_t::operator[], vcm_, _1))))
 369                 != vie)
 370             /// While there are undiscovered vertices
 371             {
 372                 vertex_t gv = find_cycle_vertex(*uv_itr);
 373                 float_t cr = cycle_ratio(gv);
 374                 mcr_bfv(gv, cr, vcm_);
 375                 if (m_cmp(mcr, cr))
 376                     mcr = cr;
 377                 ++uv_itr;
 378             }
 379             return mcr;
 380         }
 381
 382         /*!
 383          * Changes the edge m_policy[s] to the new_edge.
 384          */
 385         void improve_policy(vertex_t s, edge_t new_edge)
 386         {
 387             vertex_t t = target(m_policy[s], m_g);
 388             typename property_traits< VertexIndexMap >::value_type ti
 389                 = m_vim[t];
 390             m_inelc[ti].erase(
 391                 std::find(m_inelc[ti].begin(), m_inelc[ti].end(), s));
 392             m_policy[s] = new_edge;
 393             t = target(new_edge, m_g);
 394             m_inel[t].push_back(s); /// Maintain in_edge list
 395         }
 396
 397         /*!
 398          * A negative cycle detector.
 399          */
 400         bool try_improve_policy(float_t cr)
 401         {
 402             bool improved = false;
 403             typename graph_traits< Graph >::vertex_iterator vi, vie;
 404             typename graph_traits< Graph >::out_edge_iterator oei, oeie;
 405             const float_t eps_ = FloatTraits::epsilon();
 406             for (boost::tie(vi, vie) = vertices(m_g); vi != vie; ++vi)
 407             {
 408                 if (!m_badv[*vi])
 409                 {
 410                     for (boost::tie(oei, oeie) = out_edges(*vi, m_g);
 411                          oei != oeie; ++oei)
 412                     {
 413                         vertex_t t = target(*oei, m_g);
 414                         // Current distance from *vi to some vertex
 415                         float_t dis_
 416                             = m_ew1m[*oei] - m_ew2m[*oei] * cr + m_dm[t];
 417                         if (m_cmp(m_dm[*vi] + eps_, dis_))
 418                         {
 419                             improve_policy(*vi, *oei);
 420                             m_dm[*vi] = dis_;
 421                             improved = true;
 422                         }
 423                     }
 424                 }
 425                 else
 426                 {
 427                     float_t dis_ = m_bound - cr + m_dm[m_sink];
 428                     if (m_cmp(m_dm[*vi] + eps_, dis_))
 429                     {
 430                         m_dm[*vi] = dis_;
 431                     }
 432                 }
 433             }
 434             return improved;
 435         }
 436
 437     private:
 438         const Graph& m_g;
 439         VertexIndexMap m_vim;
 440         EdgeWeight1 m_ew1m;
 441         EdgeWeight2 m_ew2m;
 442         comparator_t m_cmp;
 443         float_t m_bound; //> The lower/upper bound to the maximal/minimal cycle
 444                          // ratio
 445         float_t m_cr; //>The best cycle ratio that has been found so far
 446
 447         vn_t m_V; //>The number of the vertices in the graph
 448         vp_t m_dis; //>Container for the distance map
 449         distance_map_t m_dm; //>Distance map
 450
 451         ve_t m_policyc; //>Container for the policy graph
 452         policy_t m_policy; //>The interface for the policy graph
 453
 454         inedges1_t m_inelc; //>Container fot in edges list
 455         inedges_t m_inel; //>Policy graph, input edges list
 456
 457         std::vector< int > m_badvc;
 458         badv_t m_badv; // Marks "bad" vertices
 459
 460         vcol_t m_colcv, m_col_bfs; // Color maps
 461         vertex_t m_sink; // To convert any graph to "good"
 462     };
 463
 464     /*! \class mcr_howard1
 465      * \brief Finds optimum cycle raio and a critical cycle
 466      */
 467     template < typename FloatTraits, typename Graph, typename VertexIndexMap,
 468         typename EdgeWeight1, typename EdgeWeight2 >
 469     class mcr_howard1 : public mcr_howard< FloatTraits, Graph, VertexIndexMap,
 470                             EdgeWeight1, EdgeWeight2 >
 471     {
 472     public:
 473         typedef mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1,
 474             EdgeWeight2 >
 475             inhr_t;
 476         mcr_howard1(const Graph& g, VertexIndexMap vim, EdgeWeight1 ewm,
 477             EdgeWeight2 ew2m)
 478         : inhr_t(g, vim, ewm, ew2m)
 479         {
 480         }
 481
 482         void get_critical_cycle(typename inhr_t::critical_cycle_t& cc)
 483         {
 484             return cc.swap(m_cc);
 485         }
 486
 487     protected:
 488         void store_critical_edge(
 489             typename inhr_t::edge_t ed, typename inhr_t::critical_cycle_t& cc)
 490         {
 491             cc.push_back(ed);
 492         }
 493
 494         void store_critical_cycle(typename inhr_t::critical_cycle_t& cc)
 495         {
 496             m_cc.swap(cc);
 497         }
 498
 499     private:
 500         typename inhr_t::critical_cycle_t m_cc; // Critical cycle
 501     };
 502
 503     /*!
 504      * \param g a directed multigraph.
 505      * \param vim Vertex Index Map. A map V->[0, num_vertices(g))
 506      * \param ewm Edge weight1 map.
 507      * \param ew2m Edge weight2 map.
 508      * \param pcc  pointer to the critical edges list.
 509      * \return Optimum cycle ratio of g or FloatTraits::infinity() if g has no
 510      * cycles.
 511      */
 512     template < typename FT, typename TG, typename TVIM, typename TEW1,
 513         typename TEW2, typename EV >
 514     typename FT::value_type optimum_cycle_ratio(
 515         const TG& g, TVIM vim, TEW1 ewm, TEW2 ew2m, EV* pcc)
 516     {
 517         typedef typename graph_traits< TG >::directed_category DirCat;
 518         BOOST_STATIC_ASSERT(
 519             (is_convertible< DirCat*, directed_tag* >::value == true));
 520         BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< TG >));
 521         BOOST_CONCEPT_ASSERT((VertexListGraphConcept< TG >));
 522         typedef typename graph_traits< TG >::vertex_descriptor Vertex;
 523         BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< TVIM, Vertex >));
 524         typedef typename graph_traits< TG >::edge_descriptor Edge;
 525         BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< TEW1, Edge >));
 526         BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< TEW2, Edge >));
 527
 528         if (pcc == 0)
 529         {
 530             return detail::mcr_howard< FT, TG, TVIM, TEW1, TEW2 >(
 531                 g, vim, ewm, ew2m)
 532                 .ocr_howard();
 533         }
 534
 535         detail::mcr_howard1< FT, TG, TVIM, TEW1, TEW2 > obj(g, vim, ewm, ew2m);
 536         double ocr = obj.ocr_howard();
 537         obj.get_critical_cycle(*pcc);
 538         return ocr;
 539     }
 540 } // namespace detail
 541
 542 // Algorithms
 543 // Maximum Cycle Ratio
 544
 545 template < typename FloatTraits, typename Graph, typename VertexIndexMap,
 546     typename EdgeWeight1Map, typename EdgeWeight2Map >
 547 inline typename FloatTraits::value_type maximum_cycle_ratio(const Graph& g,
 548     VertexIndexMap vim, EdgeWeight1Map ew1m, EdgeWeight2Map ew2m,
 549     std::vector< typename graph_traits< Graph >::edge_descriptor >* pcc = 0,
 550     FloatTraits = FloatTraits())
 551 {
 552     typedef detail::float_wrapper< FloatTraits,
 553         detail::max_comparator_props< FloatTraits > >
 554         Traits;
 555     return detail::optimum_cycle_ratio< Traits >(g, vim, ew1m, ew2m, pcc);
 556 }
 557
 558 template < typename Graph, typename VertexIndexMap, typename EdgeWeight1Map,
 559     typename EdgeWeight2Map >
 560 inline double maximum_cycle_ratio(const Graph& g, VertexIndexMap vim,
 561     EdgeWeight1Map ew1m, EdgeWeight2Map ew2m,
 562     std::vector< typename graph_traits< Graph >::edge_descriptor >* pcc = 0)
 563 {
 564     return maximum_cycle_ratio(g, vim, ew1m, ew2m, pcc, mcr_float<>());
 565 }
 566
 567 // Minimum Cycle Ratio
 568
 569 template < typename FloatTraits, typename Graph, typename VertexIndexMap,
 570     typename EdgeWeight1Map, typename EdgeWeight2Map >
 571 typename FloatTraits::value_type minimum_cycle_ratio(const Graph& g,
 572     VertexIndexMap vim, EdgeWeight1Map ew1m, EdgeWeight2Map ew2m,
 573     std::vector< typename graph_traits< Graph >::edge_descriptor >* pcc = 0,
 574     FloatTraits = FloatTraits())
 575 {
 576     typedef detail::float_wrapper< FloatTraits,
 577         detail::min_comparator_props< FloatTraits > >
 578         Traits;
 579     return detail::optimum_cycle_ratio< Traits >(g, vim, ew1m, ew2m, pcc);
 580 }
 581
 582 template < typename Graph, typename VertexIndexMap, typename EdgeWeight1Map,
 583     typename EdgeWeight2Map >
 584 inline double minimum_cycle_ratio(const Graph& g, VertexIndexMap vim,
 585     EdgeWeight1Map ew1m, EdgeWeight2Map ew2m,
 586     std::vector< typename graph_traits< Graph >::edge_descriptor >* pcc = 0)
 587 {
 588     return minimum_cycle_ratio(g, vim, ew1m, ew2m, pcc, mcr_float<>());
 589 }
 590
 591 // Maximum Cycle Mean
 592
 593 template < typename FloatTraits, typename Graph, typename VertexIndexMap,
 594     typename EdgeWeightMap, typename EdgeIndexMap >
 595 inline typename FloatTraits::value_type maximum_cycle_mean(const Graph& g,
 596     VertexIndexMap vim, EdgeWeightMap ewm, EdgeIndexMap eim,
 597     std::vector< typename graph_traits< Graph >::edge_descriptor >* pcc = 0,
 598     FloatTraits ft = FloatTraits())
 599 {
 600     typedef typename remove_const<
 601         typename property_traits< EdgeWeightMap >::value_type >::type Weight;
 602     typename std::vector< Weight > ed_w2(boost::num_edges(g), 1);
 603     return maximum_cycle_ratio(
 604         g, vim, ewm, make_iterator_property_map(ed_w2.begin(), eim), pcc, ft);
 605 }
 606
 607 template < typename Graph, typename VertexIndexMap, typename EdgeWeightMap,
 608     typename EdgeIndexMap >
 609 inline double maximum_cycle_mean(const Graph& g, VertexIndexMap vim,
 610     EdgeWeightMap ewm, EdgeIndexMap eim,
 611     std::vector< typename graph_traits< Graph >::edge_descriptor >* pcc = 0)
 612 {
 613     return maximum_cycle_mean(g, vim, ewm, eim, pcc, mcr_float<>());
 614 }
 615
 616 // Minimum Cycle Mean
 617
 618 template < typename FloatTraits, typename Graph, typename VertexIndexMap,
 619     typename EdgeWeightMap, typename EdgeIndexMap >
 620 inline typename FloatTraits::value_type minimum_cycle_mean(const Graph& g,
 621     VertexIndexMap vim, EdgeWeightMap ewm, EdgeIndexMap eim,
 622     std::vector< typename graph_traits< Graph >::edge_descriptor >* pcc = 0,
 623     FloatTraits ft = FloatTraits())
 624 {
 625     typedef typename remove_const<
 626         typename property_traits< EdgeWeightMap >::value_type >::type Weight;
 627     typename std::vector< Weight > ed_w2(boost::num_edges(g), 1);
 628     return minimum_cycle_ratio(
 629         g, vim, ewm, make_iterator_property_map(ed_w2.begin(), eim), pcc, ft);
 630 }
 631
 632 template < typename Graph, typename VertexIndexMap, typename EdgeWeightMap,
 633     typename EdgeIndexMap >
 634 inline double minimum_cycle_mean(const Graph& g, VertexIndexMap vim,
 635     EdgeWeightMap ewm, EdgeIndexMap eim,
 636     std::vector< typename graph_traits< Graph >::edge_descriptor >* pcc = 0)
 637 {
 638     return minimum_cycle_mean(g, vim, ewm, eim, pcc, mcr_float<>());
 639 }
 640
 641 } // namespace boost
 642
 643 #endif