Subject: [Boost-commit] svn:boost r54999 - in trunk: boost/graph libs/graph/doc libs/graph/example libs/graph/test
From: asutton_at_[hidden]
Date: 2009-07-17 10:56:20
Author: asutton
Date: 2009-07-17 10:56:19 EDT (Fri, 17 Jul 2009)
New Revision: 54999
URL: http://svn.boost.org/trac/boost/changeset/54999
Log:
Integrated new implementation of howard's cycle ratio algorithm. It's an
optimization and cleanup from the older version. Note that this breaks
source compatability in one instance.
Text files modified:
trunk/boost/graph/howard_cycle_ratio.hpp | 1075 ++++++++++++++++++++-------------------
trunk/libs/graph/doc/howard_cycle_ratio.html | 277 ++++++----
trunk/libs/graph/example/cycle_ratio_example.cpp | 139 ++--
trunk/libs/graph/test/cycle_ratio_tests.cpp | 483 ++++++++++-------
4 files changed, 1054 insertions(+), 920 deletions(-)
Modified: trunk/boost/graph/howard_cycle_ratio.hpp
==============================================================================
--- trunk/boost/graph/howard_cycle_ratio.hpp (original)
+++ trunk/boost/graph/howard_cycle_ratio.hpp 2009-07-17 10:56:19 EDT (Fri, 17 Jul 2009)
@@ -1,613 +1,634 @@
-/*!
-* Copyright 2007 Technical University of Catalonia
-*
-* Use, modification and distribution is subject to the Boost Software
-* License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
-* http://www.boost.org/LICENSE_1_0.txt)
-*
-* Authors: Dmitry Bufistov
-* Andrey Parfenov
-*/
-
-#ifndef BOOST_GRAPH_HOWARD_CYCLE_RATIO_HOWARD_HPP
-#define BOOST_GRAPH_HOWARD_CYCLE_RATIO_HOWARD_HPP
-
-/*!
-* \file Maximum cycle ratio algorithm (Jean Cochet-Terrasson, Guy
-* Cochen and others)
-*/
-#include <exception>
-#include <set>
+// Copyright (C) 2006-2009 Dmitry Bufistov and Andrey Parfenov
+
+// Use, modification and distribution is subject to the Boost Software
+// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef CYCLE_RATIO_HOWARD_HPP
+#define CYCLE_RATIO_HOWARD_HPP
+
+#include <vector>
+#include <list>
+#include <algorithm>
+#include <limits>
+
#include <boost/bind.hpp>
-#include <boost/config.hpp>
-#include <boost/lexical_cast.hpp>
-#include <boost/type_traits/is_convertible.hpp>
+#include <boost/type_traits/is_same.hpp>
#include <boost/type_traits/remove_const.hpp>
-#include <boost/type_traits/is_signed.hpp>
#include <boost/concept_check.hpp>
-#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/reverse_graph.hpp>
-#include <boost/graph/breadth_first_search.hpp>
-#include <boost/graph/iteration_macros.hpp>
-#include <boost/graph/graph_utility.hpp>
+#include <boost/pending/queue.hpp>
+#include <boost/property_map/property_map.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/graph_concepts.hpp>
+
+/** @file howard_cycle_ratio.hpp
+ * @brief The implementation of the maximum/minimum cycle ratio/mean algorithm.
+ * @author Dmitry Bufistov
+ * @author Andrey Parfenov
+ */
namespace boost {
+
+ /**
+ * The mcr_float is like numeric_limits, but only for floating point types
+ * and only defines infinity() and epsilon(). This class is primarily used
+ * to encapsulate a less-precise epsilon than natively supported by the
+ * floating point type.
+ */
+ template <typename Float = double> struct mcr_float {
+ typedef Float value_type;
+
+ static Float infinity()
+ { return std::numeric_limits<value_type>::infinity(); }
+
+ static Float epsilon()
+ { return Float(-0.005); }
+ };
+
namespace detail {
- /// To avoid round error.
- static const double mcr_howard_ltolerance = 0.00001;
- /*!
- * Calculate maximum cycle ratio of "good" directed multigraph
- * g. Use Howard's iteration policy algorithm ("Numerical
- * Computation of Spectral Elements in MAX-PLUS algebra" by Jean
- * Cochet-Terrasson, Guy Cochen and others).
- *
- * \param g = (V, E) - a "good" directed multigraph (out_degree of
- * each vertex is greater then 0). If graph is strongly connected
- * then it is "good".
- *
- * \param vim - Vertex Index, read property Map: V -> [0,
- * num_vertices(g)).
- *
- * \param ewm - edge weight read property map: E -> R
- *
- * \param ewm2 - edge weight2 read property map: E -> R+
- *
- * \return maximum_{for all cycles C}CR(C), or
- * -(std::numeric_limits<double>::max)() if g is not "good".
+ template <typename FloatTraits> struct
+ min_comparator_props {
+ typedef std::greater<typename FloatTraits::value_type> comparator;
+ static const int multiplier = 1;
+ };
+
+ template <typename FloatTraits> struct
+ max_comparator_props {
+ typedef std::less<typename FloatTraits::value_type> comparator;
+ static const int multiplier = -1;
+ };
+
+ template <typename FloatTraits, typename ComparatorProps>
+ struct float_wrapper {
+ typedef typename FloatTraits::value_type value_type;
+ typedef ComparatorProps comparator_props_t;
+ typedef typename ComparatorProps::comparator comparator;
+
+ static value_type infinity()
+ { return FloatTraits::infinity() * ComparatorProps::multiplier; }
+
+ static value_type epsilon()
+ { return FloatTraits::epsilon() * ComparatorProps::multiplier; }
+
+ };
+
+ /*! @class mcr_howard
+ * @brief Calculates optimum (maximum/minimum) cycle ratio of a directed graph.
+ * Uses Howard's iteration policy algorithm. </br>(It is described in the paper
+ * "Experimental Analysis of the Fastest Optimum Cycle Ratio and Mean Algorithm"
+ * by Ali Dasdan).
*/
- template <typename TGraph, typename TVertexIndexMap,
- typename TWeight1EdgeMap, typename TWeight2EdgeMap >
- class Cmcr_Howard
+ template <typename FloatTraits,
+ typename Graph, typename VertexIndexMap,
+ typename EdgeWeight1, typename EdgeWeight2>
+ class mcr_howard
{
public:
- Cmcr_Howard(const TGraph& g, TVertexIndexMap vim, TWeight1EdgeMap ewm,
- TWeight2EdgeMap ew2m)
- : m_g(g), m_vim(vim), m_ew1m(ewm), m_ew2m(ew2m),
- m_g2pi_g_vm(std::vector<pi_vertex_t>().end(), m_vim), /// Stupid dummy initialization
- m_minus_infinity(-(std::numeric_limits<double>::max)())
- {
- typedef typename boost::graph_traits<TGraph>::directed_category DirCat;
- BOOST_STATIC_ASSERT((boost::is_convertible<DirCat*, boost::directed_tag*>::value == true));
- m_cr = m_minus_infinity;
- }
-
- double operator()()
- {
- return maximum_cycle_ratio_Howard();
- }
+ typedef typename FloatTraits::value_type float_t;
+ typedef typename FloatTraits::comparator_props_t cmp_props_t;
+ typedef typename FloatTraits::comparator comparator_t;
+ typedef enum{ my_white = 0, my_black } my_color_type;
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
+ typedef typename graph_traits<Graph>::edge_descriptor edge_t;
+ typedef typename graph_traits<Graph>::vertices_size_type vn_t;
+ typedef std::vector<float_t> vp_t;
+ typedef typename boost::iterator_property_map<
+ typename vp_t::iterator, VertexIndexMap
+ > distance_map_t; //V -> float_t
+
+ typedef typename std::vector<edge_t> ve_t;
+ typedef std::vector<my_color_type> vcol_t;
+ typedef typename ::boost::iterator_property_map<
+ typename ve_t::iterator, VertexIndexMap
+ > policy_t; //Vertex -> Edge
+ typedef typename ::boost::iterator_property_map<
+ typename vcol_t::iterator, VertexIndexMap
+ > color_map_t;
+
+ typedef typename std::list<vertex_t> pinel_t;// The in_edges list of the policy graph
+ typedef typename std::vector<pinel_t> inedges1_t;
+ typedef typename ::boost::iterator_property_map<
+ typename inedges1_t::iterator, VertexIndexMap
+ > inedges_t;
+ typedef typename std::vector<edge_t> critical_cycle_t;
+
+ //Bad vertex flag. If true, then the vertex is "bad".
+ // Vertex is "bad" if its out_degree is equal to zero.
+ typedef typename boost::iterator_property_map<
+ std::vector<int>::iterator, VertexIndexMap
+ > badv_t;
- virtual ~Cmcr_Howard() { }
-
- protected:
- typedef typename boost::graph_traits<TGraph>::vertex_descriptor
- mcr_vertex_t;
- typedef typename boost::graph_traits<TGraph>::edge_descriptor
- mcr_edge_t;
-
- const TGraph& m_g;
- typedef std::vector<double> eigenmode_t;
- eigenmode_t m_eigen_value;
- eigenmode_t m_eigen_vector;
- TVertexIndexMap m_vim;
- TWeight1EdgeMap m_ew1m;
- TWeight2EdgeMap m_ew2m;
-
- typedef typename boost::remove_const<typename boost::property_traits<TWeight1EdgeMap>::value_type>::type mcr_edge_weight1_t;
- typedef typename boost::remove_const<typename boost::property_traits<TWeight2EdgeMap>::value_type>::type mcr_edge_weight2_t;
- typedef typename boost::adjacency_list<
- boost::listS, boost::vecS, boost::bidirectionalS,
- boost::no_property,
- boost::property<boost::edge_weight_t,
- mcr_edge_weight1_t,
- boost::property<boost::edge_weight2_t,
- mcr_edge_weight2_t> > >
- pi_graph_t;
- typedef typename boost::property_map<pi_graph_t, boost::vertex_index_t>::type TPiGraphVertexIndexMap;
- typedef typename boost::property_map<pi_graph_t, boost::edge_weight_t>::type TPiGraphEdgeWeight1Map;
- typedef typename boost::property_map<pi_graph_t, boost::edge_weight2_t>::type TPiGraphEdgeWeight2Map;
-
- typedef typename boost::property_traits<TPiGraphVertexIndexMap>::value_type pigraph_vertex_index_t;
-
- pi_graph_t m_pi_g;
- typedef typename boost::graph_traits<pi_graph_t>::vertex_descriptor pi_vertex_t;
- typedef typename boost::graph_traits<pi_graph_t>::edge_descriptor pi_edge_t;
- typedef typename boost::iterator_property_map<typename std::vector<pi_vertex_t>::iterator, TVertexIndexMap> g2pi_g_vm_t;
- g2pi_g_vm_t m_g2pi_g_vm; ///Graph to Pi graph vertex map
- std::vector<pi_vertex_t> m_g2pig;
- int m_step_number;
- const double m_minus_infinity;
- typedef typename std::vector<mcr_edge_t> critical_cycle_t;
- double m_cr; ///Cycle ratio that already has been found
+ /*!
+ * Constructor
+ * \param g = (V, E) - a directed multigraph.
+ * \param vim Vertex Index Map. Read property Map: V -> [0, num_vertices(g)).
+ * \param ewm edge weight map. Read property map: E -> R
+ * \param ew2m edge weight map. Read property map: E -> R+
+ * \param infty A big enough value to guaranty that there exist a cycle with
+ * better ratio.
+ * \param cmp The compare operator for float_ts.
+ */
+ mcr_howard(const Graph &g, VertexIndexMap vim,
+ EdgeWeight1 ewm, EdgeWeight2 ew2m) :
+ m_g(g), m_vim(vim), m_ew1m(ewm), m_ew2m(ew2m),
+ m_bound(mcr_bound()),
+ m_cr(m_bound),
+ m_V(num_vertices(m_g)),
+ m_dis(m_V, 0), m_dm(m_dis.begin(), m_vim),
+ m_policyc(m_V), m_policy(m_policyc.begin(), m_vim),
+ m_inelc(m_V), m_inel(m_inelc.begin(), m_vim),
+ m_badvc(m_V, false), m_badv(m_badvc.begin(), m_vim),
+ m_colcv(m_V),
+ m_col_bfs(m_V)
+ { }
- class bad_graph
+ /*!
+ * \return maximum/minimum_{for all cycles C}
+ * [sum_{e in C} w1(e)] / [sum_{e in C} w2(e)],
+ * or FloatTraits::infinity() if graph has no cycles.
+ */
+ float_t ocr_howard()
{
- public:
- typedef typename boost::property_traits<TVertexIndexMap>::value_type
- v_index_t;
-
- bad_graph(v_index_t bvi) : bad_vertex_index(bvi) {}
- v_index_t what() const throw()
- {
- return bad_vertex_index;
- }
-
- private:
- v_index_t bad_vertex_index;
- };
+ construct_policy_graph();
+ int k = 0;
+ float_t mcr = 0;
+ do
+ {
+ mcr = policy_mcr();
+ ++k;
+ }
+ while (try_improve_policy(mcr) && k < 100); //To avoid infinite loop
- double maximum_cycle_ratio_Howard()
- {
- try
+ const float_t eps_ = -0.00000001 * cmp_props_t::multiplier;
+ if (m_cmp(mcr, m_bound + eps_))
{
- construct_pi_graph();
+ return FloatTraits::infinity();
}
- catch (const bad_graph& a)
+ else
{
- return m_minus_infinity;
+ return mcr;
}
- std::vector<double> max_eigen_val(boost::num_vertices(m_g));
- m_eigen_value.resize(boost::num_vertices(m_g));
- m_eigen_vector.resize(boost::num_vertices(m_g));
- m_step_number = 0;
- do
+ }
+ virtual ~mcr_howard() {}
+
+ protected:
+ virtual void store_critical_edge(edge_t ed, critical_cycle_t &cc) {}
+ virtual void store_critical_cycle(critical_cycle_t &cc) {}
+
+ private:
+ /*!
+ * \return lower/upper bound for the maximal/minimal cycle ratio
+ */
+ float_t mcr_bound()
+ {
+ typename graph_traits<Graph>::vertex_iterator vi, vie;
+ typename graph_traits<Graph>::out_edge_iterator oei, oeie;
+ float_t cz = (std::numeric_limits<float_t>::max)(); //Closest to zero value
+ float_t s = 0;
+ const float_t eps_ = std::numeric_limits<float_t>::epsilon();
+ for (tie(vi, vie) = vertices(m_g); vi != vie; ++vi)
{
- pi_eingen_value(get(vertex_index, m_pi_g), get(boost::edge_weight, m_pi_g), get(boost::edge_weight2, m_pi_g));
- ++m_step_number;
- }
- while (improve_policy_try1(max_eigen_val) || improve_policy_try2(max_eigen_val));
- return *(std::max_element(m_eigen_value.begin(), m_eigen_value.end()));
+ for (tie(oei, oeie) = out_edges(*vi, m_g); oei != oeie; ++oei)
+ {
+ s += std::abs(m_ew1m[*oei]);
+ float_t a = std::abs(m_ew2m[*oei]);
+ if ( a > eps_ && a < cz)
+ {
+ cz = a;
+ }
+ }
+ }
+ return cmp_props_t::multiplier * (s / cz);
}
- /*!
- * Construct an arbitrary policy m_pi_g.
- */
- void construct_pi_graph()
+
+ /*!
+ * Constructs an arbitrary policy graph.
+ */
+ void construct_policy_graph()
{
- m_g2pig.resize(boost::num_vertices(m_g));
- m_g2pi_g_vm = boost::make_iterator_property_map(m_g2pig.begin(), m_vim);
- BGL_FORALL_VERTICES_T(vd, m_g, TGraph)
- {
- m_g2pi_g_vm[vd] = boost::add_vertex(m_pi_g);
- store_pivertex(m_g2pi_g_vm[vd], vd);
- }
- BGL_FORALL_VERTICES_T(vd1, m_g, TGraph)
- {
- if (boost::graph::has_no_out_edges(vd1, m_g)) throw bad_graph(m_vim[vd1]);
- mcr_edge_t ed = *boost::out_edges(vd1, m_g).first;
- pi_edge_t pied = boost::add_edge(m_g2pi_g_vm[source(ed, m_g)], m_g2pi_g_vm[target(ed, m_g)], m_pi_g).first;
- boost::put(boost::edge_weight, m_pi_g, pied, m_ew1m[ed]);
- boost::put(boost::edge_weight2, m_pi_g, pied, m_ew2m[ed]);
+ m_sink = graph_traits<Graph>().null_vertex();
+ typename graph_traits<Graph>::vertex_iterator vi, vie;
+ typename graph_traits<Graph>::out_edge_iterator oei, oeie;
+ for ( tie(vi, vie) = vertices(m_g); vi != vie; ++vi )
+ {
+ tie(oei, oeie) = out_edges(*vi, m_g);
+ typename graph_traits<Graph>::out_edge_iterator mei =
+ std::max_element(oei, oeie,
+ bind(m_cmp,
+ bind(&EdgeWeight1::operator[], m_ew1m, _1),
+ bind(&EdgeWeight1::operator[], m_ew1m, _2)
+ )
+ );
+ if (mei == oeie)
+ {
+ if (m_sink == graph_traits<Graph>().null_vertex())
+ {
+ m_sink = *vi;
+ }
+ m_badv[*vi] = true;
+ m_inel[m_sink].push_back(*vi);
+ }
+ else
+ {
+ m_inel[target(*mei, m_g)].push_back(*vi);
+ m_policy[*vi] = *mei;
+ }
}
}
-
- class bfs_eingmode_visitor : public boost::default_bfs_visitor
+ /*! Sets the distance value for all vertices "v" such that there is
+ * a path from "v" to "sv". It does "inverse" breadth first visit of the policy
+ * graph, starting from the vertex "sv".
+ */
+ void mcr_bfv(vertex_t sv, float_t cr, color_map_t c)
{
- public:
- bfs_eingmode_visitor(TPiGraphVertexIndexMap vi_m, TPiGraphEdgeWeight1Map w_m, TPiGraphEdgeWeight2Map& d_m,
- eigenmode_t& e_val, eigenmode_t& e_vec, double ev) : m_index_map(vi_m), m_weight_map(w_m), m_delay_map(d_m),
- m_eig_value(&e_val), m_eig_vec(&e_vec), m_eigen_value(ev) { }
-
- template < typename Edge, typename g_t>
- void examine_edge(Edge e, const g_t & g) const
- {
- typedef typename boost::graph_traits<g_t>::vertex_descriptor Vertex;
- Vertex u = boost::target(e, g), v = boost::source(e, g);
- pigraph_vertex_index_t ind = m_index_map[u];
- (*m_eig_value)[ind] = m_eigen_value;
- (*m_eig_vec)[ind] = m_weight_map[e] - m_eigen_value * m_delay_map[e] + (*m_eig_vec)[m_index_map[v]];
- }
- private:
- TPiGraphVertexIndexMap m_index_map;
- TPiGraphEdgeWeight1Map m_weight_map;
- TPiGraphEdgeWeight2Map m_delay_map;
- eigenmode_t* m_eig_value;
- eigenmode_t* m_eig_vec;
- double m_eigen_value;
- };
+ boost::queue<vertex_t> Q;
+ c[sv] = my_black;
+ Q.push(sv);
+ while (!Q.empty())
+ {
+ vertex_t v = Q.top(); Q.pop();
+ for (typename pinel_t::const_iterator itr = m_inel[v].begin();
+ itr != m_inel[v].end(); ++itr)
+ //For all in_edges of the policy graph
+ {
+ if (*itr != sv)
+ {
+ if (m_badv[*itr])
+ {
+ m_dm[*itr] = m_dm[v] + m_bound - cr;
+ }
+ else
+ {
+ m_dm[*itr] = m_dm[v] + m_ew1m[m_policy[*itr]] -
+ m_ew2m[m_policy[*itr]] * cr;
+ }
+ c[*itr] = my_black;
+ Q.push(*itr);
+ }
+ }
+ }
+ }
/*!
- * Find a vertex in the Pi Graph which belongs to cycle, just a DFV until back edge found
+ * \param sv an arbitrary (undiscovered) vertex of the policy graph.
+ * \return a vertex in the policy graph that belongs to a cycle.
+ * Performs a depth first visit until a cycle edge is found.
*/
- pi_vertex_t find_good_source(const pi_vertex_t start_vertex)
+ vertex_t find_cycle_vertex(vertex_t sv)
{
- pi_vertex_t good_vertex = start_vertex;
- typename std::set<pi_vertex_t> s;
- s.insert(start_vertex);
- do
- {
- good_vertex = boost::target(*boost::out_edges(good_vertex, m_pi_g).first, m_pi_g);
- }
- while (s.insert(good_vertex).second);
- return good_vertex;
+ vertex_t gv = sv;
+ std::fill(m_colcv.begin(), m_colcv.end(), my_white);
+ color_map_t cm(m_colcv.begin(), m_vim);
+ do
+ {
+ cm[gv] = my_black;
+ if (! m_badv[gv])
+ {
+ gv = target(m_policy[gv], m_g);
+ }
+ else
+ {
+ gv = m_sink;
+ }
+ }
+ while (cm[gv] != my_black);
+ return gv;
}
- virtual void store_pivertex(pi_vertex_t pivd, mcr_vertex_t vd) {}
- virtual void store_critical_edge(pi_edge_t ed, critical_cycle_t& cc) {}
- virtual void store_critical_cycle(critical_cycle_t& cc) {}
-
+
/*!
- * \param startV - vertex that belongs to a cycle in policy graph m_pi_g
+ * \param sv - vertex that belongs to a cycle in the policy graph.
*/
- double calculate_eigen_value(pi_vertex_t startV)
+ float_t cycle_ratio(vertex_t sv)
{
- std::pair<double, double> accum_sums(0., 0.);
- pi_vertex_t vd = startV;
- critical_cycle_t cc;
- do
- {
- pi_edge_t tmp_ed = *(boost::out_edges(vd, m_pi_g).first);
- store_critical_edge(tmp_ed, cc);
- accum_sums.first += boost::get(boost::edge_weight, m_pi_g, tmp_ed);
- accum_sums.second += boost::get(boost::edge_weight2, m_pi_g, tmp_ed);
- vd = boost::target(tmp_ed, m_pi_g);
- }
- while (vd != startV);
- //assert((std::abs<double>(accum_sums.first) <= 0.00000001) && "Division by zerro!");
- double cr = accum_sums.first / accum_sums.second;
- if (cr > m_cr)
+ if (sv == m_sink) return m_bound;
+ std::pair<float_t, float_t> sums_(float_t(0), float_t(0));
+ vertex_t v = sv;
+ critical_cycle_t cc;
+ do
+ {
+ store_critical_edge(m_policy[v], cc);
+ sums_.first += m_ew1m[m_policy[v]];
+ sums_.second += m_ew2m[m_policy[v]];
+ v = target(m_policy[v], m_g);
+ }
+ while (v != sv);
+ float_t cr = sums_.first / sums_.second;
+ if ( m_cmp(m_cr, cr) )
{
m_cr = cr;
store_critical_cycle(cc);
}
- else
- {
-
- }
- return cr;
+ return cr;
}
/*!
- * Value determination. Find a generalized eigenmode (n^{k+1}, x^{k+1}) of A^{I_{k+1}} of the pi graph (Algorithm IV.1).
+ * Finds the optimal cycle ratio of the policy graph
*/
- void pi_eingen_value(
- TPiGraphVertexIndexMap index_map,
- TPiGraphEdgeWeight1Map weight_map,
- TPiGraphEdgeWeight2Map weigh2_map)
+ float_t policy_mcr()
{
- using namespace boost;
- typedef std::vector<default_color_type> color_map_t;
- color_map_t vcm(num_vertices(m_pi_g), white_color);//Vertex color map
- color_map_t::iterator uv_itr = vcm.begin(); //Undiscovered vertex
- reverse_graph<pi_graph_t> rev_g(m_pi_g); //For backward breadth visit
-
- while ((uv_itr = std::find_if(uv_itr, vcm.end(),
- boost::bind(std::equal_to<default_color_type>(), boost::white_color, _1))) != vcm.end())
+ std::fill(m_col_bfs.begin(), m_col_bfs.end(), my_white);
+ color_map_t vcm_ = color_map_t(m_col_bfs.begin(), m_vim);
+ typename graph_traits<Graph>::vertex_iterator uv_itr, vie;
+ tie(uv_itr, vie) = vertices(m_g);
+ float_t mcr = m_bound;
+ while ( (uv_itr = std::find_if(uv_itr, vie,
+ bind(std::equal_to<my_color_type>(),
+ my_white,
+ bind(&color_map_t::operator[], vcm_, _1)
+ )
+ )
+ ) != vie )
///While there are undiscovered vertices
{
- pi_vertex_t gv = find_good_source(pi_vertex_t(uv_itr - vcm.begin()));
- pigraph_vertex_index_t gv_ind = index_map[gv];
- m_eigen_value[gv_ind] = calculate_eigen_value(gv) ;
- bfs_eingmode_visitor bfs_vis(index_map, weight_map, weigh2_map, m_eigen_value, m_eigen_vector, m_eigen_value[gv_ind]);
- typename boost::queue<pi_vertex_t> Q;
- breadth_first_visit(rev_g, gv, Q, bfs_vis, make_iterator_property_map(vcm.begin(), index_map));
+ vertex_t gv = find_cycle_vertex(*uv_itr);
+ float_t cr = cycle_ratio(gv) ;
+ mcr_bfv(gv, cr, vcm_);
+ if ( m_cmp(mcr, cr) ) mcr = cr;
+ ++uv_itr;
}
+ return mcr;
}
- void improve_policy(mcr_vertex_t vd, mcr_edge_t new_edge)
- {
- remove_edge(*(out_edges(m_g2pi_g_vm[vd], m_pi_g).first), m_pi_g);
- pi_edge_t ned = add_edge(m_g2pi_g_vm[vd], m_g2pi_g_vm[target(new_edge, m_g)], m_pi_g).first;
- put(edge_weight, m_pi_g, ned, m_ew1m[new_edge]);
- put(edge_weight2, m_pi_g, ned, m_ew2m[new_edge]);
- }
/*!
- * Policy Improvement. Improve the policy graph. The new policy graph has greater cycle ratio.
- * \return false if nothing can be improved.
+ * Changes the edge m_policy[s] to the new_edge.
*/
- bool improve_policy_try1(std::vector<double>& max_eing_vals)
+ void improve_policy(vertex_t s, edge_t new_edge)
{
- bool improved = false;
- BGL_FORALL_VERTICES_T(vd, m_g, TGraph)
- {
- double max_ev = m_minus_infinity;/// Maximum eigen value for vertex
- mcr_edge_t cr_ed;///Critical edge
-
- BGL_FORALL_OUTEDGES_T(vd, outed, m_g, TGraph)
- {
- if (m_eigen_value[m_vim[target(outed, m_g)]] > max_ev)
- {
- max_ev = m_eigen_value[m_vim[boost::target(outed, m_g)]];
- cr_ed = outed;
- }
- }
- if (max_ev > m_eigen_value[get(m_vim,vd)])
- {
- improve_policy(vd, cr_ed);
- improved = true;
- }
- max_eing_vals[get(m_vim,vd)] = max_ev;
- }
- return improved;
+ vertex_t t = target(m_policy[s], m_g);
+ typename property_traits<VertexIndexMap>::value_type ti = m_vim[t];
+ m_inelc[ti].erase( std::find(m_inelc[ti].begin(), m_inelc[ti].end(), s));
+ m_policy[s] = new_edge;
+ t = target(new_edge, m_g);
+ m_inel[t].push_back(s); ///Maintain in_edge list
}
/*!
- * \param max_eigen_values[u] = max_(for all adjacent vertices (u,v)) m_eigen_value[v]
+ * A negative cycle detector.
*/
- bool improve_policy_try2(const std::vector<double>& max_eigen_values)
+ bool try_improve_policy(float_t cr)
{
- bool improved = false;
- BGL_FORALL_VERTICES_T(vd, m_g, TGraph)
+ bool improved = false;
+ typename graph_traits<Graph>::vertex_iterator vi, vie;
+ typename graph_traits<Graph>::out_edge_iterator oei, oeie;
+ const float_t eps_ = FloatTraits::epsilon();
+ for (tie(vi, vie) = vertices(m_g); vi != vie; ++vi)
{
- mcr_edge_t impr_edge;
- double max_val = m_minus_infinity;
- BGL_FORALL_OUTEDGES_T(vd, outed, m_g, TGraph)
+ if (!m_badv[*vi])
{
- ///If vertex vd is in the K(vd) set
- if (max_eigen_values[get(m_vim, vd)] <= m_eigen_value[get(m_vim, target(outed, m_g))])
+ for (tie(oei, oeie) = out_edges(*vi, m_g); oei != oeie; ++oei)
{
- double c_val = m_ew1m[outed] - m_ew2m[outed] * m_eigen_value[m_vim[boost::target(outed, m_g)]] +
- m_eigen_vector[m_vim[boost::target(outed, m_g)]];
- if (c_val > max_val)
+ vertex_t t = target(*oei, m_g);
+ //Current distance from *vi to some vertex
+ float_t dis_ = m_ew1m[*oei] - m_ew2m[*oei] * cr + m_dm[t];
+ if ( m_cmp(m_dm[*vi] + eps_, dis_) )
{
- max_val = c_val;
- impr_edge = outed;
+ improve_policy(*vi, *oei);
+ m_dm[*vi] = dis_;
+ improved = true;
}
}
}
- if ((max_val - m_eigen_vector[get(m_vim, vd)]) > mcr_howard_ltolerance)
- ///If m_eigen_vector[vd] == max_val
+ else
{
- improve_policy(vd, impr_edge);
- improved = true;
+ float_t dis_ = m_bound - cr + m_dm[m_sink];
+ if ( m_cmp(m_dm[*vi] + eps_, dis_) )
+ {
+ m_dm[*vi] = dis_;
+ }
}
}
return improved;
}
- };///Cmcr_Howard
+ private:
+ const Graph &m_g;
+ VertexIndexMap m_vim;
+ EdgeWeight1 m_ew1m;
+ EdgeWeight2 m_ew2m;
+ comparator_t m_cmp;
+ float_t m_bound; //> The lower/upper bound to the maximal/minimal cycle ratio
+ float_t m_cr; //>The best cycle ratio that has been found so far
+
+ vn_t m_V; //>The number of the vertices in the graph
+ vp_t m_dis; //>Container for the distance map
+ distance_map_t m_dm; //>Distance map
+
+ ve_t m_policyc; //>Container for the policy graph
+ policy_t m_policy; //>The interface for the policy graph
- /*!
- * \return maximum cycle ratio and one critical cycle.
- */
- template <typename TGraph, typename TVertexIndexMap, typename TWeight1EdgeMap, typename TWeight2EdgeMap>
- class Cmcr_Howard1 : public Cmcr_Howard<TGraph, TVertexIndexMap, TWeight1EdgeMap, TWeight2EdgeMap>
- {
- public:
- typedef Cmcr_Howard<TGraph, TVertexIndexMap, TWeight1EdgeMap, TWeight2EdgeMap> inhr_t;
- Cmcr_Howard1(const TGraph& g, TVertexIndexMap vim, TWeight1EdgeMap ewm, TWeight2EdgeMap ew2m) : inhr_t(g, vim, ewm, ew2m)
- {
- m_pi_g2g.resize(boost::num_vertices(g));
- m_pi_g2g_vm = boost::make_iterator_property_map(m_pi_g2g.begin(), boost::get(boost::vertex_index, this->m_pi_g));
- }
+ inedges1_t m_inelc; //>Container fot in edges list
+ inedges_t m_inel; //>Policy graph, input edges list
- void get_critical_cycle(typename inhr_t::critical_cycle_t& cc) { return cc.swap(m_critical_cycle); }
- protected:
- void store_pivertex(typename inhr_t::pi_vertex_t pivd, typename inhr_t::mcr_vertex_t vd)
- {
- m_pi_g2g_vm[pivd] = vd;
- }
- void store_critical_edge(typename inhr_t::pi_edge_t ed, typename inhr_t::critical_cycle_t& cc)
- {
- typename inhr_t::pi_vertex_t s = boost::source(ed, this->m_pi_g);
- typename inhr_t::pi_vertex_t t = boost::target(ed, this->m_pi_g);
- assert(boost::edge(m_pi_g2g_vm[s], m_pi_g2g_vm[t], this->m_g).second);
- cc.push_back(boost::edge(m_pi_g2g_vm[s], m_pi_g2g_vm[t], this->m_g).first); ///Store corresponding edge of the m_g
- }
- void store_critical_cycle(typename inhr_t::critical_cycle_t& cc)
- {
- m_critical_cycle.swap(cc);
- }
- private:
- typename inhr_t::critical_cycle_t m_critical_cycle;
- typedef typename boost::iterator_property_map<typename std::vector<typename inhr_t::mcr_vertex_t>::iterator, typename inhr_t::TPiGraphVertexIndexMap> pi_g2g_vm_t;
- pi_g2g_vm_t m_pi_g2g_vm; ///Maps policy graph vertices to input graph vertices
- typename std::vector<typename inhr_t::mcr_vertex_t> m_pi_g2g;
+ std::vector<int> m_badvc;
+ badv_t m_badv; //Marks "bad" vertices
+
+ vcol_t m_colcv, m_col_bfs; //Color maps
+ vertex_t m_sink; //To convert any graph to "good"
};
- /*!
- * Add sink vertex - this will make any graph good, the selfloop will have ratio equal to infinity
- * Properties must be "self increasing"
+ /*! \class mcr_howard1
+ * \brief Finds optimum cycle raio and a critical cycle
*/
- template <typename TGraph, typename TWeight1EdgeMap, typename TWeight2EdgeMap>
- typename boost::graph_traits<TGraph>::vertex_descriptor
- make_graph_good(TGraph& g, TWeight1EdgeMap ewm, TWeight2EdgeMap ew2m,
- typename boost::property_traits<TWeight1EdgeMap>::value_type infinity)
+ template <typename FloatTraits,
+ typename Graph, typename VertexIndexMap,
+ typename EdgeWeight1, typename EdgeWeight2>
+ class mcr_howard1 : public
+ mcr_howard<FloatTraits, Graph, VertexIndexMap,
+ EdgeWeight1, EdgeWeight2>
{
- typedef typename boost::graph_traits<TGraph>::edge_descriptor Edge;
- typename boost::graph_traits<TGraph>::vertex_descriptor sink = boost::add_vertex(g);
-
- BGL_FORALL_VERTICES_T(vd, g, TGraph)
- {
- Edge newed = boost::add_edge(vd, sink, g).first;
- boost::put(ewm, newed, 0);
- boost::put(ew2m, newed, 1);
- }
- Edge selfed = boost::edge(sink, sink, g).first;
- boost::put(ewm, selfed, infinity);
- return sink;
- }
+ public:
+ typedef mcr_howard<FloatTraits, Graph, VertexIndexMap,
+ EdgeWeight1, EdgeWeight2> inhr_t;
+ mcr_howard1(const Graph &g, VertexIndexMap vim,
+ EdgeWeight1 ewm, EdgeWeight2 ew2m) :
+ inhr_t(g, vim, ewm, ew2m)
+ { }
- /*!
- * Construct from input graph g "safe" (suitable for maximum_cycle_ratio1() call) version - safeg
- */
- template <typename TG, typename TIndVertexMap, typename TW1EdgeMap, typename TW2EdgeMap, typename TSafeG, typename SafeG2GEdgeMap>
- void construct_safe_graph(const TG& g, TIndVertexMap vim, TW1EdgeMap ew1m, TW2EdgeMap ew2m, TSafeG& safeg, SafeG2GEdgeMap& sg2gm)
- {
- assert(num_vertices(g) == num_vertices(safeg));
- typedef typename graph_traits<TSafeG>::edge_descriptor tmp_edge_t;
- typedef typename graph_traits<TG>::edge_descriptor edge_t;
- typename graph_traits<TG>::edge_iterator ei, ei_end;
-
- for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
- {
- tmp_edge_t tmped = add_edge(vim[source(*ei, g)], vim[target(*ei, g)], safeg).first;
- sg2gm[tmped] = *ei;
- put(edge_weight, safeg, tmped, get(ew1m, *ei));
- put(edge_weight2, safeg, tmped, get(ew2m, *ei));
- }
- }
+ void get_critical_cycle(typename inhr_t::critical_cycle_t &cc)
+ { return cc.swap(m_cc); }
- template <typename TGraph, typename TVertexIndexMap, typename TWeight1EdgeMap, typename TWeight2EdgeMap>
- double maximum_cycle_ratio_good_graph(const TGraph& g, TVertexIndexMap vim, TWeight1EdgeMap ewm, TWeight2EdgeMap ew2m,
- typename std::vector<typename boost::graph_traits<TGraph>::edge_descriptor>* pcc = 0)
- {
- if (pcc == 0)
- {
- return detail::Cmcr_Howard<TGraph, TVertexIndexMap, TWeight1EdgeMap, TWeight2EdgeMap>(g, vim, ewm, ew2m)();
- }
- else
- {
- detail::Cmcr_Howard1<TGraph, TVertexIndexMap, TWeight1EdgeMap, TWeight2EdgeMap> obj(g, vim, ewm, ew2m);
- double maxcr = obj();
- obj.get_critical_cycle(*pcc);
- return maxcr;
- }
- }
+ protected:
+ void store_critical_edge(typename inhr_t::edge_t ed,
+ typename inhr_t::critical_cycle_t &cc)
+ { cc.push_back(ed); }
- template <typename TGraph, typename TVertexIndexMap, typename TWeight1EdgeMap, typename TWeight2EdgeMap, typename TEdgeIndexMap>
- double minimum_cycle_ratio_good_graph(const TGraph& g, TVertexIndexMap vim, TWeight1EdgeMap ewm,
- TWeight2EdgeMap ew2m, TEdgeIndexMap eim,
- typename std::vector<typename boost::graph_traits<TGraph>::edge_descriptor>* pcc = 0)
- {
- typedef typename boost::remove_const<typename boost::property_traits<TWeight1EdgeMap>::value_type>::type weight_value_t;
- BOOST_STATIC_ASSERT(!is_integral<weight_value_t>::value || is_signed<weight_value_t>::value);
- typename std::vector<weight_value_t> ne_w(boost::num_edges(g));
- BGL_FORALL_EDGES_T(ed, g, TGraph) ne_w[boost::get(eim, ed)] = -ewm[ed];
- return -maximum_cycle_ratio_good_graph(g, vim, boost::make_iterator_property_map(ne_w.begin(), eim), ew2m, pcc);
- }
+ void store_critical_cycle(typename inhr_t::critical_cycle_t &cc)
+ { m_cc.swap(cc); }
- /*!
- * \param g directed multigraph.
- * \param pcc - pointer to the critical edges list.
- * \param minus_infinity must be small enough to garanty that g has at least one cycle with greater ratio.
- * \return minus_infinity if there're no cycles in the graph
- */
- template <typename TGraph, typename TWeight1EdgeMap, typename TWeight2EdgeMap>
- double maximum_cycle_ratio1(const TGraph& g, TWeight1EdgeMap ewm, TWeight2EdgeMap ew2m,
- typename std::vector<typename boost::graph_traits<TGraph>::edge_descriptor>* pcc = 0,
- typename boost::property_traits<TWeight1EdgeMap>::value_type minus_infinity = -(std::numeric_limits<int>::max)())
- {
- typedef typename boost::graph_traits<TGraph>::vertex_descriptor Vertex;
- typedef typename boost::graph_traits<TGraph>::edge_descriptor Edge;
- boost::function_requires< boost::ReadWritePropertyMapConcept<TWeight1EdgeMap, Edge> >();
- boost::function_requires< boost::ReadWritePropertyMapConcept<TWeight2EdgeMap, Edge> >();
-
- TGraph& ncg = const_cast<TGraph&>(g);
- Vertex sink = detail::make_graph_good(ncg, ewm, ew2m, minus_infinity );
-
- double res = maximum_cycle_ratio_good_graph(ncg, boost::get(boost::vertex_index, g), ewm, ew2m, pcc);
- boost::clear_vertex(sink, ncg); boost::remove_vertex(sink, ncg);
- return res;
- }
+ private:
+ typename inhr_t::critical_cycle_t m_cc; //Critical cycle
+ };
/*!
- * Edge index MUST be in diapazon [0,..., num_edges(g)-1]
- * \return plus_infinity if g has no cycles.
+ * \param g a directed multigraph.
+ * \param vim Vertex Index Map. A map V->[0, num_vertices(g))
+ * \param ewm Edge weight1 map.
+ * \param ew2m Edge weight2 map.
+ * \param pcc pointer to the critical edges list.
+ * \return Optimum cycle ratio of g or FloatTraits::infinity() if g has no cycles.
*/
- template <typename TGraph, typename TWeight1EdgeMap, typename TWeight2EdgeMap, typename TEdgeIndexMap>
- double minimum_cycle_ratio1(const TGraph& g, TWeight1EdgeMap ewm, TWeight2EdgeMap ew2m, TEdgeIndexMap eim,
- typename std::vector<typename boost::graph_traits<TGraph>::edge_descriptor>* pcc = 0,
- typename boost::property_traits<TWeight1EdgeMap>::value_type plus_infinity = (std::numeric_limits<int>::max)()
- )
+ template <typename FT,
+ typename TG, typename TVIM,
+ typename TEW1, typename TEW2,
+ typename EV>
+ typename FT::value_type
+ optimum_cycle_ratio(const TG &g, TVIM vim, TEW1 ewm, TEW2 ew2m, EV* pcc)
{
- typedef typename boost::property_traits<TEdgeIndexMap>::value_type ei_t;
- typedef typename boost::graph_traits<TGraph>::vertex_descriptor Vertex;
- typedef typename boost::graph_traits<TGraph>::edge_descriptor Edge;
-
- boost::function_requires< boost::ReadWritePropertyMapConcept<TWeight1EdgeMap, Edge> >();
- boost::function_requires< boost::ReadWritePropertyMapConcept<TWeight2EdgeMap, Edge> >();
- boost::function_requires< boost::ReadWritePropertyMapConcept<TEdgeIndexMap, Edge> >();
-
- TGraph& ncg = const_cast<TGraph&>(g);
-
- ei_t nei = ei_t(boost::num_edges(g));
- Vertex sink = detail::make_graph_good(ncg, ewm, ew2m, plus_infinity );
- ///Maintain edge index invariant
- BGL_FORALL_VERTICES_T(vd, ncg, TGraph)
- {
- typename boost::graph_traits<TGraph>::edge_descriptor ed = boost::edge(vd, sink, ncg).first;
- boost::put(eim, ed, nei++);
- }
- double res = minimum_cycle_ratio_good_graph(ncg, boost::get(boost::vertex_index, ncg), ewm, ew2m, eim, pcc);
- boost::clear_vertex(sink, ncg); boost::remove_vertex(sink, ncg);
- return res;
+ typedef typename graph_traits<TG>::directed_category DirCat;
+ BOOST_STATIC_ASSERT((is_convertible<DirCat*, directed_tag*>::value == true));
+ function_requires< IncidenceGraphConcept<TG> >();
+ function_requires< VertexListGraphConcept<TG> >();
+ typedef typename graph_traits<TG>::vertex_descriptor Vertex;
+ function_requires< ReadablePropertyMapConcept<TVIM, Vertex> >();
+ typedef typename graph_traits<TG>::edge_descriptor Edge;
+ function_requires< ReadablePropertyMapConcept<TEW1, Edge> >();
+ function_requires< ReadablePropertyMapConcept<TEW2, Edge> >();
+
+ if(pcc == 0) {
+ return detail::mcr_howard<FT,TG, TVIM, TEW1, TEW2>(
+ g, vim, ewm, ew2m
+ ).ocr_howard();
+ }
+
+ detail::mcr_howard1<FT, TG, TVIM, TEW1, TEW2> obj(g, vim, ewm, ew2m);
+ double ocr = obj.ocr_howard();
+ obj.get_critical_cycle(*pcc);
+ return ocr;
}
- struct edge_less_than
- {
- template <typename TEdgeDescriptor> bool operator()(const TEdgeDescriptor& x, const TEdgeDescriptor& y) const
- {
- return x.get_property() < y.get_property();
- }
- };
- }///namespace detail
- namespace
- {
- template <typename TW1, typename TW2> struct safe_graph
- {
- typedef typename boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::no_property,
- typename boost::property<boost::edge_weight_t, TW1, typename boost::property<boost::edge_weight2_t, TW2> > > type;
- };
- }
+ } // namespace detail
- /*!
- * Calculate the maximum cycle ratio (mcr) of the directed multigraph g.
- * \param g directed multigraph
- * \param pcc - If provided then a critical cycle will be written to corresponding vector.
- * \param minus_infinity small enough value to garanty that g has at least one cycle with greater ratio.
- * \return mcr or minus_infinity if g has no cycles.
- */
- template <typename TGraph, typename TVertexIndexMap, typename TW1EdgeMap, typename TW2EdgeMap>
- double maximum_cycle_ratio(const TGraph& g, TVertexIndexMap vim, TW1EdgeMap ew1m, TW2EdgeMap ew2m,
- typename std::vector<typename boost::graph_traits<TGraph>::edge_descriptor>* pcc = 0,
- typename boost::property_traits<TW1EdgeMap>::value_type minus_infinity =
- -(std::numeric_limits<int>::max)())
- {
- typedef typename remove_const<typename property_traits<TW1EdgeMap>::value_type>::type w1_t;
- typedef typename remove_const<typename property_traits<TW2EdgeMap>::value_type>::type w2_t;
- typedef typename safe_graph<w1_t, w2_t>::type safe_graph_t;
- typedef typename graph_traits<safe_graph_t>::edge_descriptor tmp_edge_t;
- typedef typename graph_traits<TGraph>::edge_descriptor edge_t;
- typename std::map<tmp_edge_t, edge_t, detail::edge_less_than> tmpg2g;
- std::vector<tmp_edge_t> cc;
- safe_graph_t sg(num_vertices(g));
- detail::construct_safe_graph(g, vim, ew1m, ew2m, sg, tmpg2g);
- double mcr = maximum_cycle_ratio1(sg, get(edge_weight, sg), get(edge_weight2, sg), pcc ? &cc : 0, minus_infinity);
- if (pcc && (mcr > minus_infinity))
- {
- pcc->clear();
- for (typename std::vector<tmp_edge_t>::iterator it = cc.begin(); it != cc.end(); ++it) pcc->push_back(tmpg2g[*it]);
- }
- return mcr;
- }
+// Algorithms
+// Maximum Cycle Ratio
+
+template <
+ typename FloatTraits,
+ typename Graph,
+ typename VertexIndexMap,
+ typename EdgeWeight1Map,
+ typename EdgeWeight2Map>
+inline typename FloatTraits::value_type
+maximum_cycle_ratio(const Graph &g, VertexIndexMap vim, EdgeWeight1Map ew1m,
+ EdgeWeight2Map ew2m,
+ std::vector<typename graph_traits<Graph>::edge_descriptor>* pcc = 0,
+ FloatTraits = FloatTraits())
+{
+ typedef detail::float_wrapper<
+ FloatTraits, detail::max_comparator_props<FloatTraits>
+ > Traits;
+ return detail::optimum_cycle_ratio<Traits>(g, vim, ew1m, ew2m, pcc);
+}
+
+template <
+ typename Graph,
+ typename VertexIndexMap,
+ typename EdgeWeight1Map,
+ typename EdgeWeight2Map>
+inline double
+maximum_cycle_ratio(const Graph &g, VertexIndexMap vim,
+ EdgeWeight1Map ew1m, EdgeWeight2Map ew2m,
+ std::vector<typename graph_traits<Graph>::edge_descriptor>* pcc = 0)
+{ return maximum_cycle_ratio(g, vim, ew1m, ew2m, pcc, mcr_float<>()); }
+
+// Minimum Cycle Ratio
+
+template <
+ typename FloatTraits,
+ typename Graph,
+ typename VertexIndexMap,
+ typename EdgeWeight1Map,
+ typename EdgeWeight2Map>
+typename FloatTraits::value_type
+minimum_cycle_ratio(const Graph &g, VertexIndexMap vim,
+ EdgeWeight1Map ew1m, EdgeWeight2Map ew2m,
+ std::vector<typename graph_traits<Graph>::edge_descriptor> *pcc = 0,
+ FloatTraits = FloatTraits())
+{
+ typedef detail::float_wrapper<
+ FloatTraits, detail::min_comparator_props<FloatTraits>
+ > Traits;
+ return detail::optimum_cycle_ratio<Traits>(g, vim, ew1m, ew2m, pcc);
+}
+
+template <
+ typename Graph,
+ typename VertexIndexMap,
+ typename EdgeWeight1Map,
+ typename EdgeWeight2Map>
+inline double
+minimum_cycle_ratio(const Graph &g, VertexIndexMap vim,
+ EdgeWeight1Map ew1m, EdgeWeight2Map ew2m,
+ std::vector<typename graph_traits<Graph>::edge_descriptor>* pcc = 0)
+{ return minimum_cycle_ratio(g, vim, ew1m, ew2m, pcc, mcr_float<>()); }
+
+// Maximum Cycle Mean
+
+template <
+ typename FloatTraits,
+ typename Graph,
+ typename VertexIndexMap,
+ typename EdgeWeightMap,
+ typename EdgeIndexMap>
+inline typename FloatTraits::value_type
+maximum_cycle_mean(const Graph &g, VertexIndexMap vim,
+ EdgeWeightMap ewm, EdgeIndexMap eim,
+ std::vector<typename graph_traits<Graph>::edge_descriptor>* pcc = 0,
+ FloatTraits ft = FloatTraits())
+{
+ typedef typename remove_const<
+ typename property_traits<EdgeWeightMap>::value_type
+ >::type Weight;
+ typename std::vector<Weight> ed_w2(boost::num_edges(g), 1);
+ return maximum_cycle_ratio(g, vim, ewm,
+ make_iterator_property_map(ed_w2.begin(), eim),
+ pcc, ft);
+}
+
+template <
+ typename Graph,
+ typename VertexIndexMap,
+ typename EdgeWeightMap,
+ typename EdgeIndexMap>
+inline double
+maximum_cycle_mean(const Graph& g, VertexIndexMap vim,
+ EdgeWeightMap ewm, EdgeIndexMap eim,
+ std::vector<typename graph_traits<Graph>::edge_descriptor>* pcc = 0)
+{ return maximum_cycle_mean(g, vim, ewm, eim, pcc, mcr_float<>()); }
+
+// Minimum Cycle Mean
+
+template <
+ typename FloatTraits,
+ typename Graph,
+ typename VertexIndexMap,
+ typename EdgeWeightMap,
+ typename EdgeIndexMap>
+inline typename FloatTraits::value_type
+minimum_cycle_mean(const Graph &g, VertexIndexMap vim,
+ EdgeWeightMap ewm, EdgeIndexMap eim,
+ std::vector<typename graph_traits<Graph>::edge_descriptor>* pcc = 0,
+ FloatTraits ft = FloatTraits())
+{
+ typedef typename remove_const<
+ typename property_traits<EdgeWeightMap>::value_type
+ >::type Weight;
+ typename std::vector<Weight> ed_w2(boost::num_edges(g), 1);
+ return minimum_cycle_ratio(g, vim, ewm,
+ make_iterator_property_map(ed_w2.begin(), eim),
+ pcc, ft);
+}
+
+template <
+ typename Graph,
+ typename VertexIndexMap,
+ typename EdgeWeightMap,
+ typename EdgeIndexMap>
+inline double
+minimum_cycle_mean(const Graph &g, VertexIndexMap vim,
+ EdgeWeightMap ewm, EdgeIndexMap eim,
+ std::vector<typename graph_traits<Graph>::edge_descriptor>* pcc = 0)
+{ return minimum_cycle_mean(g, vim, ewm, eim, pcc, mcr_float<>()); }
- template <typename TGraph, typename TVertexIndexMap, typename TW1EdgeMap, typename TW2EdgeMap, typename TIndEdgeMap>
- double minimum_cycle_ratio(const TGraph& g, TVertexIndexMap vim, TW1EdgeMap ew1m, TW2EdgeMap ew2m, TIndEdgeMap eim,
- typename std::vector<typename boost::graph_traits<TGraph>::edge_descriptor>* pcc = 0,
- typename boost::property_traits<TW1EdgeMap>::value_type plus_infinity =
- (std::numeric_limits<int>::max)())
- {
- typedef typename boost::remove_const<typename boost::property_traits<TW1EdgeMap>::value_type>::type weight_value_t;
- BOOST_STATIC_ASSERT(!is_integral<weight_value_t>::value || is_signed<weight_value_t>::value);
- typename std::vector<weight_value_t> ne_w(boost::num_edges(g));
- BGL_FORALL_EDGES_T(ed, g, TGraph) ne_w[boost::get(eim, ed)] = -ew1m[ed];
- return -maximum_cycle_ratio(g, vim, boost::make_iterator_property_map(ne_w.begin(), eim), ew2m, pcc, -plus_infinity);
- }
- /*!
- * Calculate maximum mean cycle of directed weighted multigraph.
- * \param g directed multigraph
- * \return maximum mean cycle of g or minus_infinity if g has no cycles.
- */
- template <typename TGraph, typename TVertexIndexMap, typename TWeightEdgeMap, typename TIndEdgeMap>
- double maximum_mean_cycle(const TGraph& g, TVertexIndexMap vim, TWeightEdgeMap ewm, TIndEdgeMap eim,
- typename std::vector<typename boost::graph_traits<TGraph>::edge_descriptor>* pcc = 0,
- typename boost::property_traits<TWeightEdgeMap>::value_type minus_infinity =
- -(std::numeric_limits<int>::max)())
- {
- typedef typename boost::remove_const<typename boost::property_traits<TWeightEdgeMap>::value_type>::type weight_value_t;
- typedef typename boost::graph_traits<TGraph>::edge_descriptor Edge;
- typename std::vector<weight_value_t> ed_w2(boost::num_edges(g), 1);
- return maximum_cycle_ratio(g, vim, ewm, boost::make_iterator_property_map(ed_w2.begin(), eim), pcc, minus_infinity);
- }
-
- template <typename TGraph, typename TVertexIndexMap, typename TWeightEdgeMap, typename TIndEdgeMap>
- double minimum_mean_cycle(const TGraph& g, TVertexIndexMap vim, TWeightEdgeMap ewm, TIndEdgeMap eim,
- typename std::vector<typename boost::graph_traits<TGraph>::edge_descriptor>* pcc = 0,
- typename boost::property_traits<TWeightEdgeMap>::value_type plus_infinity =
- (std::numeric_limits<int>::max)())
- {
- typedef typename boost::remove_const<typename boost::property_traits<TWeightEdgeMap>::value_type>::type weight_value_t;
- typedef typename boost::graph_traits<TGraph>::edge_descriptor Edge;
- typename std::vector<weight_value_t> ed_w2(boost::num_edges(g), 1);
- return minimum_cycle_ratio(g, vim, ewm, boost::make_iterator_property_map(ed_w2.begin(), eim), eim, pcc, plus_infinity);
- }
} //namespace boost
+
#endif
Modified: trunk/libs/graph/doc/howard_cycle_ratio.html
==============================================================================
--- trunk/libs/graph/doc/howard_cycle_ratio.html (original)
+++ trunk/libs/graph/doc/howard_cycle_ratio.html 2009-07-17 10:56:19 EDT (Fri, 17 Jul 2009)
@@ -9,11 +9,11 @@
<!-- -- Copyright 2007 Technical University of Catalonia
-
+
Use, modification and distribution is subject to the Boost Software
License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
http://www.boost.org/LICENSE_1_0.txt)
-
+
Authors: Dmitry Bufistov
Andrey Parfenov
-->
@@ -34,143 +34,200 @@
<BODY TEXT="#000000" LINK="#0000ee" VLINK="#551a8b" BGCOLOR="#ffffff" DIR="LTR">
<P><IMG SRC="../../..//boost.png" NAME="graphics1" ALT="C++ Boost" ALIGN=BOTTOM WIDTH=277 HEIGHT=86 BORDER=0>
</P>
-<H1><TT>maximum(minimum)_cycle_ratio</TT>
-</H1>
-<I>// non-named parameter version</I>
-<!--template <typename TGraph,
- typename TVertexIndexMap,
- typename TWeight1EdgeMap,
- typename TWeight2EdgeMap >
-double maximum_cycle_ratio_good_graph(const TGraph& g, TVertexIndexMap vim, TWeight1EdgeMap ew1m, TWeight2EdgeMap ew2m,
- typename std::vector<typename boost::graph_traits<TGraph>::edge_descriptor>* pcc = 0);
-<br/>
-<PRE>template <typename TGraph,
- typename TWeight1EdgeMap,
- typename TWeight2EdgeMap >
-double maximum_cycle_ratio1(const TGraph& g, TWeight1EdgeMap ewm, TWeight2EdgeMap ew2m,
- typename std::vector<typename boost::graph_traits<TGraph>::edge_descriptor>* pcc = 0,
- typename boost::property_traits<TWeight1EdgeMap>::value_type minus_infinity =
- -(std::numeric_limits<int>::max)());
- </PRE>-->
+<H1><TT>[maximum|minimum]_cycle_ratio</TT></H1>
<P>
-<PRE>template <typename TGraph,
- typename TVertexIndexMap,
- typename TWeight1EdgeMap,
- typename TWeight2EdgeMap >
-double maximum_cycle_ratio(const TGraph& g, TVertexIndexMap vim, TWeight1EdgeMap ewm, TWeight2EdgeMap ew2m,
- typename std::vector<typename boost::graph_traits<TGraph>::edge_descriptor>* pcc = 0,
- typename boost::property_traits<TWeight1EdgeMap>::value_type minus_infinity =
- -(std::numeric_limits<int>::max)());
- </PRE>
+<PRE>
+template <typename Graph, typename VertexIndexMap,
+ typename EdgeWeight1, typename EdgeWeight2>
+dobule
+maximum_cycle_ratio(const Graph &g, VertexIndexMap vim,
+ EdgeWeight1 ewm, EdgeWeight2 ew2m,
+ std::vector<typename boost::graph_traits<Graph>::edge_descriptor> *pcc = 0);
+
+template <typename FloatTraits, Graph, typename VertexIndexMap,
+ typename EdgeWeight1, typename EdgeWeight2>
+typename FloatTraits::float_type
+maximum_cycle_ratio(const Graph &g, VertexIndexMap vim,
+ EdgeWeight1 ewm, EdgeWeight2 ew2m,
+ std::vector<typename boost::graph_traits<Graph>::edge_descriptor> *pcc = 0,
+ FloatTraits = FloatTraits());
+
+template <typename Graph, typename VertexIndexMap,
+ typename EdgeWeight1, typename EdgeWeight2>
+dobule
+minimum_cycle_ratio(const Graph &g, VertexIndexMap vim,
+ EdgeWeight1 ewm, EdgeWeight2 ew2m,
+ std::vector<typename boost::graph_traits<Graph>::edge_descriptor> *pcc = 0);
+
+template <typename FloatTraits, typename Graph, typename VertexIndexMap,
+ typename EdgeWeight1, typename EdgeWeight2>
+typename FloatTraits::float_type
+minimum_cycle_ratio(const Graph &g, VertexIndexMap vim,
+ EdgeWeight1 ewm, EdgeWeight2 ew2m,
+ std::vector<typename boost::graph_traits<Graph>::edge_descriptor> *pcc = 0,
+ FloatTraits = FloatTraits());
+</PRE>
</P>
+
+
+The <tt>maximum_cycle_ratio()</tt> function calculates the maximum cycle ratio of a
+weighted directed multigraph <I>G=(V,E,W1,W2)</I>, where <i>V</i> is a vertex set,
+<i>E</i> is an edge set, W1 and W2 are edge weight functions, W2 is nonnegative.
+As a multigraph, <i>G</i> can have multiple edges connecting a pair of vertices.
+</P>
+
+<P>Let every edge <I>e</I> has two weights <I>W1(e)</I> and <I>W2(e)</I>.
+Let <I>c</I> be a cycle of the graph<I>g</I>. Then, the <i>cycle ratio</i>, <I>cr(c)</I>, is defined as:</P>
<P>
-<PRE>template <typename TGraph,
- typename TVertexIndexMap,
- typename TWeight1EdgeMap,
- typename TWeight2EdgeMap,
- typename TEdgeIndexMap >
-double minimum_cycle_ratio(const TGraph& g, TVertexIndexMap vim, TWeight1EdgeMap ewm, TWeight2EdgeMap ew2m, TEdgeIndexMap eim,
- typename std::vector<typename boost::graph_traits<TGraph>::edge_descriptor>* pcc = 0,
- typename boost::property_traits<TWeight1EdgeMap>::value_type plus_infinity =
- (std::numeric_limits<int>::max)());
- </PRE>
-</P>
-The <I>maximum_cycle_ratio()</I> function calculates the maximum cycle ratio of a weighted directed multigraph <I>g=(V,E,W1,W2)</I>, where <i>V</i> is a vertex set, <i>E</i> is an edge set, W1 and W2 are edge weight functions, W2 is nonnegative. <i>Multigraph</i> is a graph that can have multiple edges between its vertices. The calculated maximum cycle ratio will be the return value of the function. The <I>maximal_cycle_ratio()</I> returns <I>minus_infinity</I> if graph has no cycles. The value of the <i>minus_infinity</i> parameter should be small enough to garanty that <i>g</i> has at leat one cycle with greater ratio.
-</P>
-
-<P>Let every edge <I>e</I> have two weights <I>W1(e)</I> and <I>W2(e)</I>. </SPAN> Let <I>c</I> <SPAN STYLE="font-style: normal">be a cycle of a graph</SPAN> <I>g</I>. <SPAN STYLE="font-style: normal">The <i>cycle ratio</i> (<I>cr(c)</I>) is defined as:</SPAN></P>
-<P><IMG SRC="figs/cr.jpg" NAME="graphics2" ALT="Cycle ratio definition" ALIGN=LEFT WIDTH=295 HEIGHT=82 BORDER=0><BR CLEAR=LEFT><BR><BR>
-The <I>maximum (minimum) cycle ratio</I> (mcr) is the maximum (minimum) cycle ratio of all cycles of the graph.
-Cycle calls <I>critical</I> if its ratio is equal to <I>mcr</I>. </P>If the <i>pcc</i> parameter is not zero then one critical cycle will be written to the corresponding std::vector of edge descriptors. The edges in the vector stored in the way that *pcc[0], *ppc[1],...,*ppc[n] is a correct path.</P>
-<!--<P STYLE="margin-bottom: 0cm">
- For every directed multigraph <I>G=(V,E)</I> there is a «good» multigraph G'=(V',E'),
-such that <I>mcr(G)== mcr(G').</I> G' can be constructed from G by
-adding one "sink" <SPAN STYLE="font-style: normal">vertex </SPAN><I> u </I><SPAN STYLE="font-style: normal">and</SPAN><I>
-num_vertex(G)+ 1 </I><SPAN STYLE="font-style: normal">edges</SPAN><I>
-(v, u) </I><SPAN STYLE="font-style: normal">for all vertices</SPAN><I>
- v </I><SPAN STYLE="font-style: normal">in</SPAN><I> V</I> <SPAN STYLE="font-style: normal">(including
- self loop <I>sl=(u,u)</I>). The weights of the self loop </SPAN><I>W1(sl),
-W2(sl) </I><SPAN STYLE="font-style: normal">should be set to «<I>minus
-infinity»</I> and 1 correspondingly. The <I>make_graph_good()</I>
-function from cycle_ratio_example.cpp
-implement this transformation. Based on <I>make_graph_good()</I>
-function one can write <I>maximum_cycle_ratio()</I> function that would work
-for all directed multigraphs, returning minus infinity if graph has
-no cycles, the usage example file cycle_ratio_example.cpp
-contains implementation of this function (also more or less general version of <I>minimal_cycle_ratio()</I> function) and some usage examples. </SPAN>
-</P>-->
-For a graph <i>G=(V,E,W1,W2)</i> let <i>G'=(V,E,-W1,W2)</i> be a graph with opposite <i>W1</i> function, then the minimum cycle ratio of <i>G</i> is the opposite maximum cycle ratio of <i>G'</i>.
-The <i>minimum_cycle_ratio()</i> function just calls the <i>maximum_cycle_ratio()</i> with the opposite <i>W1</i> function, so if the type value of the <i>W1</i> weight is integral then it must be signed.
+<IMG SRC="figs/cr.jpg" ALT="Cycle ratio definition" BORDER=0>
+</P>
+
+The <I>maximum (minimum) cycle ratio</I> (mcr) is the maximum (minimum) cycle ratio
+of all cycles of the graph. A cycle is called <I>critical</I> if its ratio is equal
+to the <I>mcr</I>. The calculated maximum cycle ratio will be the return value
+of the function. The <tt>maximum_cycle_ratio()/minimum_cycle_ratio()</tt> returns
+<tt>-FloatTraits::infinity()/FloatTraits::infinity()</tt> if graph has no cycles.
+If the <i>pcc</i> parameter is not zero then one critical cycle will be written
+to the corresponding <tt>std::vector</tt> of edge descriptors. The edges in the
+vector stored in the way such that <tt>*pcc[0], *ppc[1], ..., *ppc[n]</tt> is a
+correct path.
+</P>
<P>
The algorithm is due to Howard's iteration policy algorithm, descibed in
<A HREF="./cochet-terrasson98numerical.pdf">[1]</A>.
Ali Dasdan, Sandy S. Irani and Rajesh K.Gupta in their paper
<A HREF="./dasdan-dac99.pdf">Efficient Algorithms for Optimum Cycle Mean and Optimum Cost to Time Ratio
Problems</A>state that this is the most efficient algorithm to the time being (1999).</P>
-<H3>
-Where Defined</H3>
-<P STYLE="background: transparent"><TT>boost/graph/howard_cycle_ratio.hpp</TT>
+
+<p>
+For the convenience, functions <tt>maximum_cycle_mean()</tt> and <tt>minimum_cycle_mean()</tt>
+are also provided. They have the following signatures:
+<pre>
+template <typename Graph, typename VertexIndexMap,
+ typename EdgeWeightMap, typename EdgeIndexMap>
+double
+maximum_cycle_mean(const Graph &g, VertexIndexMap vim,
+ EdgeWeightMap ewm, EdgeIndexMap eim,
+ std::vector<typename graph_traits<Graph>::edge_descriptor> *pcc = 0);
+template <typename FloatTraits, typename Graph, typename VertexIndexMap,
+ typename EdgeWeightMap, typename EdgeIndexMap>
+
+typename FloatTraits::float_type
+maximum_cycle_mean(const Graph &g, VertexIndexMap vim,
+ EdgeWeightMap ewm, EdgeIndexMap eim,
+ std::vector<typename graph_traits<Graph>::edge_descriptor> *pcc = 0,
+ FloatTraits = FloatTraits());
+
+template <typename Graph, typename VertexIndexMap,
+ typename EdgeWeightMap, typename EdgeIndexMap>
+double
+minimum_cycle_mean(const Graph &g, VertexIndexMap vim,
+ EdgeWeightMap ewm, EdgeIndexMap eim,
+ std::vector<typename graph_traits<Graph>::edge_descriptor> *pcc = 0);
+template <typename FloatTraits, typename Graph, typename VertexIndexMap,
+ typename EdgeWeightMap, typename EdgeIndexMap>
+
+typename FloatTraits::float_type
+minimum_cycle_mean(const Graph &g, VertexIndexMap vim,
+ EdgeWeightMap ewm, EdgeIndexMap eim,
+ std::vector<typename graph_traits<Graph>::edge_descriptor> *pcc = 0,
+ FloatTraits = FloatTraits());
+</pre>
+</p>
+
+<H3>Where Defined</H3>
+<P STYLE="background: transparent"><TT>boost/graph/howard_cycle_ratio.hpp</TT>
</P>
<H3>Parameters</H3>
-<P>IN: <FONT FACE="Courier New, monospace">const TGraph& g </FONT>
-</P>
-<BLOCKQUOTE>A directed weighted multigraph.
-The graph's type must be a model of VertexListGraph
-and IncidenceGraph
+<P>IN: <tt>FloatTraits</tt> </P>
+<blockquote>
+The <tt>FloatTrats</tt> encapsulates customizable limits-like information for
+floating point types. This type <i>must</i> provide an associated type,
+<tt>value_type</tt> for the floating point type.
+
+The default value is <tt>boost::mcr_float<></tt>which has the following
+definition:<br/>
+<pre>
+ template <typename Float = double>
+ struct mcr_float {
+ typedef Float value_type;
+
+ static Float infinity()
+ { return (std::numeric_limits<value_type>::max)(); }
+
+ static Float epsilon()
+ { return Float(-0.005); }
+ };
+</pre>
+The value <tt>FloatTraits::epsilon()</tt> controls the "tolerance" of the
+algorithm. By increasing the absolute value of epsilon you may slightly decrease
+the execution time but there is a risk to skip a global optima. By decreasing
+the absolute value you may fall to the infinite loop. The best option is to
+leave this parameter unchanged.
+</blockquote>
+<P>IN: <tt>const Graph& g </tt>
+</P>
+<BLOCKQUOTE>A weighted directed multigraph.
+The graph's type must be a model of VertexListGraph
+and IncidenceGraph
</BLOCKQUOTE>
-<P>IN: <FONT FACE="Courier New, monospace" COLOR="#000000">TVertexIndexMap vim</FONT>
+<P>IN: <tt>VertexIndexMap vim</tt>
</P>
<BLOCKQUOTE>Maps each vertex of the graph to a unique integer in the
range [0, num_vertices(g)).
</BLOCKQUOTE>
-<P>IN: <FONT FACE="Courier New, monospace">TWeight1EdgeMap ew1m</FONT>
+<P>IN: <tt>EdgeWeight1 ew1m</t>
</P>
<BLOCKQUOTE>
-The W1 edge weight function. For <i>minimum_cycle_ratio()</i> if the type value of the ew1m is integral then it must be signed.
+The W1 edge weight function.
</BLOCKQUOTE>
-<P>IN: <FONT FACE="Courier New, monospace">TWeight2EdgeMap ew2m</FONT>
-</P>
-<BLOCKQUOTE>The W2 edge weight function. Must be nonnegative.</BLOCKQUOTE>
-<P>IN: <FONT FACE="Courier New, monospace"><FONT COLOR="#000000">TEdgeIndexMap eim</FONT></FONT>
+<P>IN: <tt>EdgeWeight2 ew2m</tt>
</P>
-<BLOCKQUOTE>Maps each edge of the graph <I>g</I> to a unique integer
-in the range <TT>[0, num_edges(g)). <FONT FACE="Times New Roman, serif"></FONT></TT></BLOCKQUOTE>
-
-<P>IN: <FONT FACE="Courier New, monospace"><FONT COLOR="#000000">boost::property_traits<TWeight1EdgeMap>::value_type minus_infinity</FONT></FONT>
+<BLOCKQUOTE>
+The W2 edge weight function. Should be nonnegative. The actual limitation of the
+algorithm is the positivity of the total weight of each directed cycle of the graph.
+</BLOCKQUOTE>
+<P>
+OUT: <tt>std::vector<typename boost::graph_traits<Graph>::edge_descriptor>* pcc</tt>
</P>
-<BLOCKQUOTE>Small enough value to garanty that <i>g</i> has at least one cycle with greater ratio</BLOCKQUOTE>
-<P>IN: <FONT FACE="Courier New, monospace"><FONT COLOR="#000000">boost::property_traits<TWeight1EdgeMap>::value_type plus_infinity</FONT></FONT>
+<BLOCKQUOTE>
+If non zero then one critical cycle will be stored in the std::vector. Default
+value is 0.
+</BLOCKQUOTE>
+<P>
+IN (only for maximum/minimal_cycle_mean()): <tt>EdgeIndexMap eim</tt>
</P>
-<BLOCKQUOTE>Big enough value to garanty that <i>g</i> has at least one cycle with less ratio. Expression -plus_infinity must be well defined.</BLOCKQUOTE>
-
-<P>OUT: <FONT FACE="Courier New, monospace">std::vector<typename
-boost::graph_traits<TGraph>::edge_descriptor>* pcc</FONT></P>
-<BLOCKQUOTE>An edge descriptors of one critical cycle will be stored in the corresponding std::vector. Default value is 0.</BLOCKQUOTE>
+<BLOCKQUOTE>
+Maps each edge of the graph to a unique integer in the range [0, num_edges(g)).
+</BLOCKQUOTE>
<BLOCKQUOTE STYLE="margin-left: 0cm">
-The all maps must be a models of <A HREF="../..//property_map/doc/ReadablePropertyMap.html">Readable
-Property Map</A></BLOCKQUOTE>
+All property maps must be models of <A HREF="http://boost.org/libs/property_map/ReadablePropertyMap.html">Readable
+Property Map</A>
+</BLOCKQUOTE>
+
<H3>Complexity</H3>
<P>There is no known precise upper bound for the time complexity of the
-algorithm. Imperical time complexity is <I>O(E)</I>, where the
-constant tends to be pretty small. Space complexity is also <I>O(E)</I>.
+algorithm. Imperical time complexity is <I>O(|E|)</I>, where the constant tends to
+be pretty small (about 20-30). Space complexity is equal to <i>7*|V|</i> plus the
+space required to store a graph.
</P>
+
<H3>Example</H3>
-<P>The program in cycle_ratio_example.cpp
-generates random graph and computes its maximum cycle ratio.
+<P>The program in cycle_ratio_example.cpp
+generates a random graph and computes its maximum cycle ratio.
</P>
+
<HR>
<TABLE CELLPADDING=2 CELLSPACING=2>
- <TR VALIGN=TOP>
- <TD>
- <P>Copyright © 2000-2006</P>
- </TD>
- <TD>
- <P><A HREF="http://www.lsi.upc.edu/~dmitry">Dmitry
- Bufistov</A>, Universitat Politecnica de Cataluña</P>
- </TD>
- </TR>
+ <TR VALIGN=TOP>
+ <TD>
+ <P>Copyright © 2006-2009</P>
+ </TD>
+ <TD>
+ <P><A HREF="http://www.lsi.upc.edu/~dmitry">Dmitry
+ Bufistov</A>, Andrey Parfenov</P>
+ </TD>
+ </TR>
</TABLE>
<P><BR><BR>
-</P>
-</BODY>
-</HTML>
+</P></HTML>
Modified: trunk/libs/graph/example/cycle_ratio_example.cpp
==============================================================================
--- trunk/libs/graph/example/cycle_ratio_example.cpp (original)
+++ trunk/libs/graph/example/cycle_ratio_example.cpp 2009-07-17 10:56:19 EDT (Fri, 17 Jul 2009)
@@ -1,84 +1,83 @@
-/*!
-* Copyright 2007 Technical University of Catalonia
-*
-* Use, modification and distribution is subject to the Boost Software
-* License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
-* http://www.boost.org/LICENSE_1_0.txt)
-*
-* Authors: Dmitry Bufistov
-* Andrey Parfenov
-*/
-#include <boost/graph/howard_cycle_ratio.hpp>
-#include <boost/random/mersenne_twister.hpp>
+// Copyright (C) 2006-2009 Dmitry Bufistov and Andrey Parfenov
+
+// Use, modification and distribution is subject to the Boost Software
+// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <cassert>
+#include <ctime>
+#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_real.hpp>
#include <boost/graph/adjacency_list.hpp>
-#include <boost/graph/iteration_macros.hpp>
-#include <boost/graph/graph_utility.hpp>
-#include <boost/graph/property_iter_range.hpp>
#include <boost/graph/random.hpp>
-#include <boost/date_time/posix_time/posix_time.hpp>
+#include <boost/graph/howard_cycle_ratio.hpp>
+/**
+ * @author Dmitry Bufistov
+ * @author Andrey Parfenov
+ */
using namespace boost;
-typedef adjacency_list<listS, listS, directedS, property<vertex_index_t, int, property<boost::vertex_name_t, std::string> >,
- property<edge_weight_t, double, property<edge_weight2_t, double, property<edge_index_t, int> > > > grap_real_t;
+typedef adjacency_list<
+ listS, listS, directedS,
+ property<vertex_index_t, int>,
+ property<
+ edge_weight_t, double, property<edge_weight2_t, double>
+ >
+> grap_real_t;
-template <typename TGraph>
-void gen_rand_graph(TGraph& g, size_t nV, size_t nE)
+template <typename TG>
+void gen_rand_graph(TG &g, size_t nV, size_t nE)
{
- g.clear();
- boost::mt19937 rng;
- boost::generate_random_graph(g, nV, nE, rng, true, true);
- boost::uniform_real<> ur(-1,10);
- boost::variate_generator<boost::mt19937&, boost::uniform_real<> > ew1rg(rng, ur);
- randomize_property<edge_weight_t>(g, ew1rg);
- boost::uniform_int<> uint(1,5);
- boost::variate_generator<boost::mt19937&, boost::uniform_int<> > ew2rg(rng, uint);
- randomize_property<edge_weight2_t>(g, ew2rg);
+ g.clear();
+ mt19937 rng;
+ rng.seed(uint32_t(time(0)));
+ boost::generate_random_graph(g, nV, nE, rng, true, true);
+ boost::uniform_real<> ur(-1,10);
+ boost::variate_generator<boost::mt19937&, boost::uniform_real<> > ew1rg(rng, ur);
+ randomize_property<edge_weight_t>(g, ew1rg);
+ boost::uniform_int<size_t> uint(1,5);
+ boost::variate_generator<boost::mt19937&, boost::uniform_int<size_t> > ew2rg(rng, uint);
+ randomize_property<edge_weight2_t>(g, ew2rg);
}
int main(int argc, char* argv[])
{
- const double epsilon = 0.000000001;
- double min_cr, max_cr; ///Minimum and maximum cycle ratio
- typedef std::vector<graph_traits<grap_real_t>::edge_descriptor> ccReal_t;
- ccReal_t cc; ///For storing critical edges
-
-
- grap_real_t tgr;
- property_map<grap_real_t, vertex_index_t>::type vim = get(vertex_index, tgr);
- property_map<grap_real_t, edge_weight_t>::type ew1m = get(edge_weight, tgr);
- property_map<grap_real_t, edge_weight2_t>::type ew2m = ew2m;
-
- gen_rand_graph(tgr, 1000, 300000);
- std::cout << "Vertices number: " << num_vertices(tgr) << '\n';
- std::cout << "Edges number: " << num_edges(tgr) << '\n';
- int i = 0;
- BGL_FORALL_VERTICES(vd, tgr, grap_real_t) put(vertex_index, tgr, vd, i++); ///Initialize vertex index property
- boost::posix_time::ptime st = boost::posix_time::microsec_clock::local_time();
- max_cr = maximum_cycle_ratio(tgr, get(vertex_index, tgr), get(edge_weight, tgr), get(edge_weight2, tgr));
- std::cout << "Maximum cycle ratio is " << max_cr << '\n';
- std::cout << "Run time of the maximum_cycle_ratio() is " << to_simple_string(boost::posix_time::microsec_clock::local_time() - st) << '\n';
-
-
- ///One way to get the "good" value of the plus_infinity parameter
- double pl_infnt = double(*std::max_element(get_property_iter_range(tgr, edge_weight).first, get_property_iter_range(tgr, edge_weight).second)) /
- *std::min_element(get_property_iter_range(tgr, edge_weight2).first, get_property_iter_range(tgr, edge_weight2).second);
- std::cout << "Set infinity for minimum_cycle_ratio() call to " << pl_infnt << '\n';
- i = 0;
- BGL_FORALL_EDGES(ed, tgr, grap_real_t) put(edge_index, tgr, ed, i++); ///Initialize edge index property
- min_cr = minimum_cycle_ratio(tgr, get(vertex_index, tgr), get(edge_weight, tgr), get(edge_weight2, tgr), get(edge_index, tgr), &cc, pl_infnt);
- std::cout << "Minimal cycle ratio is " << min_cr << '\n';
- std::pair<double, double> cr(.0,.0);
- std::cout << "\nCritical cycle is:\n";
- for (ccReal_t::iterator itr = cc.begin(); itr != cc.end(); ++itr)
- {
- cr.first += get(edge_weight, tgr, *itr); cr.second += get(edge_weight2, tgr, *itr);
- std::cout << "(" << get(vertex_index, tgr, source(*itr, tgr)) << "," << get(vertex_index, tgr, target(*itr, tgr)) << ") ";
- }
- std::cout << '\n';
- assert(std::abs(cr.first / cr.second - min_cr) < epsilon);
-
- return 0;
+ using std::cout;
+ using std::endl;
+ const double epsilon = 0.0000001;
+ double min_cr, max_cr; ///Minimum and maximum cycle ratio
+ typedef std::vector<graph_traits<grap_real_t>::edge_descriptor> ccReal_t;
+ ccReal_t cc; ///critical cycle
+
+ grap_real_t tgr;
+ property_map<grap_real_t, vertex_index_t>::type vim = get(vertex_index, tgr);
+ property_map<grap_real_t, edge_weight_t>::type ew1 = get(edge_weight, tgr);
+ property_map<grap_real_t, edge_weight2_t>::type ew2 = get(edge_weight2, tgr);
+
+ gen_rand_graph(tgr, 1000, 30000);
+ cout << "Vertices number: " << num_vertices(tgr) << endl;
+ cout << "Edges number: " << num_edges(tgr) << endl;
+ int i = 0;
+ graph_traits<grap_real_t>::vertex_iterator vi, vi_end;
+ for (tie(vi, vi_end) = vertices(tgr); vi != vi_end; vi++) {
+ vim[*vi] = i++; ///Initialize vertex index property
+ }
+ max_cr = maximum_cycle_ratio(tgr, vim, ew1, ew2);
+ cout << "Maximum cycle ratio is " << max_cr << endl;
+ min_cr = minimum_cycle_ratio(tgr, vim, ew1, ew2, &cc);
+ cout << "Minimum cycle ratio is " << min_cr << endl;
+ std::pair<double, double> cr(.0,.0);
+ cout << "Critical cycle:\n";
+ for (ccReal_t::iterator itr = cc.begin(); itr != cc.end(); ++itr)
+ {
+ cr.first += ew1[*itr];
+ cr.second += ew2[*itr];
+ std::cout << "(" << vim[source(*itr, tgr)] << "," <<
+ vim[target(*itr, tgr)] << ") ";
+ }
+ cout << endl;
+ assert(std::abs(cr.first / cr.second - min_cr) < epsilon);
+ return EXIT_SUCCESS;
}
Modified: trunk/libs/graph/test/cycle_ratio_tests.cpp
==============================================================================
--- trunk/libs/graph/test/cycle_ratio_tests.cpp (original)
+++ trunk/libs/graph/test/cycle_ratio_tests.cpp 2009-07-17 10:56:19 EDT (Fri, 17 Jul 2009)
@@ -1,37 +1,39 @@
-/*!
-* Copyright 2007 Technical University of Catalonia
-*
-* Use, modification and distribution is subject to the Boost Software
-* License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
-* http://www.boost.org/LICENSE_1_0.txt)
-*
-* Authors: Dmitry Bufistov
-* Andrey Parfenov
-*/
+// Copyright (C) 2006-2009 Dmitry Bufistov and Andrey Parfenov
+
+// Use, modification and distribution is subject to the Boost Software
+// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
#include <sstream>
-#include <boost/graph/howard_cycle_ratio.hpp>
+
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/property_iter_range.hpp>
+#include <boost/graph/howard_cycle_ratio.hpp>
+
#include <boost/test/minimal.hpp>
-#include <cmath>
+
+/**
+ * @author Dmitry Bufistov
+ * @author Andrey Parfenov
+ */
/*!
* The graph has two equal cycles with ratio 2/3
*/
static const char test_graph1[] = "digraph G {\
- edge [w1=1, w2=1];\
- 1->2\
- 2->3 [w1=0]\
- 3->4\
- 4->2\
- 1->5\
- 5->6\
- 6->7 [w1=0]\
- 7->5 \
+ edge [w1=1, w2=1];\
+ 1->2\
+ 2->3 [w1=0]\
+ 3->4\
+ 4->2\
+ 1->5\
+ 5->6\
+ 6->7 [w1=0]\
+ 7->5 \
}";
/*!
@@ -40,21 +42,21 @@
static const std::string test_graph2 = "digraph G {edge [w1=1]; 1->3 [w2=1]; 1->2 [w2=2]; 1->4 [w2=7]; }";
/*!
-* Example from the paper "Nunerical computation of spectral elements"
-* Maximum cycle ratio is 5.5
+* Example from the paper "Nunerical computation of spectral elements"
+* Maximum cycle ratio is 5.5
*/
static const char test_graph3[] = "\
digraph article {\
- edge [w2 =2];\
- 1->1 [w1 = 1];\
- 1->2 [w1 = 2];\
- 1->4 [w1 = 7];\
- 2->2 [w1 = 3];\
- 2->3 [w1 = 5];\
- 3->2 [w1 = 4];\
- 3->4 [w1 = 3];\
- 4->2 [w1 = 2];\
- 4->3 [w1 = 8];\
+ edge [w2 =2];\
+ 1->1 [w1 = 1];\
+ 1->2 [w1 = 2];\
+ 1->4 [w1 = 7];\
+ 2->2 [w1 = 3];\
+ 2->3 [w1 = 5];\
+ 3->2 [w1 = 4];\
+ 3->4 [w1 = 3];\
+ 4->2 [w1 = 2];\
+ 4->3 [w1 = 8];\
}";
/*!
@@ -83,208 +85,263 @@
* Maximum cycle ratio is 3.58, minimum is 0.294118
*/
static const char test_graph6[]= "digraph test_graph6 {\
- 16;\
- 17;\
+ 16;\
+ 17;\
\
- 1->2 [w1=1, w2=0.1];\
- 2->3 [w1 = 2, w2=3.6];\
- 3->4 [w1=7, w2=8];\
- 4->5 [w1=3.1,w2=0.8];\
- 4->5 [w1 = 4.2, w2=0.6];\
- 4->5 [w1 = 5.3, w2=0.4];\
- 5->6 [w1=-10, w2 = 34.75]\
- 6->1 [w1=100, w2 = 20]\
+ 1->2 [w1=1, w2=0.1];\
+ 2->3 [w1 = 2, w2=3.6];\
+ 3->4 [w1=7, w2=8];\
+ 4->5 [w1=3.1,w2=0.8];\
+ 4->5 [w1 = 4.2, w2=0.6];\
+ 4->5 [w1 = 5.3, w2=0.4];\
+ 5->6 [w1=-10, w2 = 34.75]\
+ 6->1 [w1=100, w2 = 20]\
\
- 1->7 [w1=10, w2 = 20];\
- 7->8 [w1=3.75, w2 = 1.25];\
- 7->8 [w1=30, w2 = 22.2];\
- 8->9 [w1=10, w2 = 20];\
- 9->10 [w1=-2.1, w2 = 30]\
- 10->6 [w1=10, w2 = 20]\
+ 1->7 [w1=10, w2 = 20];\
+ 7->8 [w1=3.75, w2 = 1.25];\
+ 7->8 [w1=30, w2 = 22.2];\
+ 8->9 [w1=10, w2 = 20];\
+ 9->10 [w1=-2.1, w2 = 30]\
+ 10->6 [w1=10, w2 = 20]\
\
- 11->12 [w1 = 5, w2=0.45];\
- 12->13 [w1 = 4, w2=0.2];\
- 13->14 [w1 = 3, w2=15.75];\
- 14->11 [w1 = -2.5, w2=0.6];\
- 11->10 [w1 = -8, w2=0.9];\
- 11->10 [w1 = -15, w2=2.9];\
+ 11->12 [w1 = 5, w2=0.45];\
+ 12->13 [w1 = 4, w2=0.2];\
+ 13->14 [w1 = 3, w2=15.75];\
+ 14->11 [w1 = -2.5, w2=0.6];\
+ 11->10 [w1 = -8, w2=0.9];\
+ 11->10 [w1 = -15, w2=2.9];\
\
- 18 -> 19 [w1=18, w2=6];\
- 18 -> 20 [w1=16.3, w2=8.2];\
- 18 -> 21 [w1=-3, w2=15];\
- 18 -> 18 [w1=2, w2=1];\
- 19 -> 18 [w1=0.06, w2=0.01];\
- 19 -> 19 [w1=1, w2=1.2];\
- 19 -> 20 [w1=5, w2=2];\
- 19 -> 21 [w1=3, w2=0.1];\
- 20 -> 18 [w1=4, w2=0.2];\
- 20 -> 19 [w1=11, w2=21];\
- 20 -> 20 [w1=6, w2=5];\
- 20 -> 21 [w1=7, w2=1];\
- 21 -> 18 [w1=8, w2=2];\
- 21 -> 19 [w1=12, w2=6];\
- 21 -> 20 [w1=7.5, w2=4.3];\
- 21 -> 21 [w1=1.25, w2=2.15];\
+ 18 -> 19 [w1=18, w2=6];\
+ 18 -> 20 [w1=16.3, w2=8.2];\
+ 18 -> 21 [w1=-3, w2=15];\
+ 18 -> 18 [w1=2, w2=1];\
+ 19 -> 18 [w1=0.06, w2=0.01];\
+ 19 -> 19 [w1=1, w2=1.2];\
+ 19 -> 20 [w1=5, w2=2];\
+ 19 -> 21 [w1=3, w2=0.1];\
+ 20 -> 18 [w1=4, w2=0.2];\
+ 20 -> 19 [w1=11, w2=21];\
+ 20 -> 20 [w1=6, w2=5];\
+ 20 -> 21 [w1=7, w2=1];\
+ 21 -> 18 [w1=8, w2=2];\
+ 21 -> 19 [w1=12, w2=6];\
+ 21 -> 20 [w1=7.5, w2=4.3];\
+ 21 -> 21 [w1=1.25, w2=2.15];\
}";
using namespace boost;
-typedef property<boost::vertex_index_t, int, boost::property<boost::vertex_name_t, std::string> > vertex_props_t;
-template <typename EdgeWeight1, typename EdgeWeight2> struct Graph {
- typedef typename boost::property<boost::edge_weight_t, EdgeWeight1, typename boost::property<boost::edge_weight2_t,
- EdgeWeight2, boost::property<boost::edge_index_t, int> > > edge_props_t;
- typedef boost::adjacency_list<boost::listS, boost::listS, boost::directedS, vertex_props_t, edge_props_t> type;
+typedef property<vertex_index_t, int, property<boost::vertex_name_t, std::string> > vertex_props_t;
+template <typename TW1, typename TW2> struct Graph
+{
+ typedef typename boost::property<
+ boost::edge_weight_t, TW1,
+ typename boost::property<
+ boost::edge_weight2_t, TW2, property<boost::edge_index_t, int>
+ >
+ > edge_props_t;
+ typedef typename boost::adjacency_list<
+ boost::listS, boost::listS, boost::directedS, vertex_props_t,
+ edge_props_t>
+ type;
};
-typedef Graph<int, int>::type GraphInt;
-typedef Graph<double, double>::type GraphReal;
+typedef Graph<int, int>::type diGraphInt;
+typedef Graph<double, double>::type diGraphReal;
-template <typename TW1, typename TW2> struct CEdgeProps {
- CEdgeProps(TW1 w1 = 1, TW2 w2 = 2) : m_w1(w1), m_w2(w2), m_edge_index((std::numeric_limits<int>::max)()) {}
- TW1 m_w1;
- TW2 m_w2;
- int m_edge_index;
+template <typename TW1, typename TW2>
+struct CEdgeProps
+{
+ CEdgeProps(TW1 w1 = 1, TW2 w2 = 2) :
+ m_w1(w1), m_w2(w2), m_edge_index((std::numeric_limits<int>::max)())
+ {}
+ TW1 m_w1;
+ TW2 m_w2;
+ int m_edge_index;
};
-typedef adjacency_matrix<directedS, no_property, CEdgeProps<int, int> > GraphMInt;
-
+typedef adjacency_matrix<directedS, no_property, CEdgeProps<int, int> > GraphMInt;
+
///Create "tokens_map" for reading graph properties from .dot file
-template <typename TGraph>
-void make_dynamic_properties(TGraph& g, dynamic_properties& p)
+template <typename TG>
+void make_dynamic_properties(TG &g, dynamic_properties &p)
{
- p.property("node_id", get(vertex_name, g));
- p.property("label", get(edge_weight, g));
- p.property("w1", get(edge_weight, g));
- p.property("w2", get(edge_weight2, g));
+ p.property("node_id", get(vertex_name, g));
+ p.property("label", get(edge_weight, g));
+ p.property("w1", get(edge_weight, g));
+ p.property("w2", get(edge_weight2, g));
}
-template <typename TGraph>
-void read_data1(std::istream& is, TGraph& g)
+template <typename TG>
+void read_data1(std::istream &is, TG &g)
{
- dynamic_properties p;
- make_dynamic_properties(g, p);
- read_graphviz(is, g, p);
- std::cout << "Number of vertices: " << num_vertices(g) << "\n";
- std::cout << "Number of edges: " << num_edges(g) << "\n";
- int i = 0;
- BGL_FORALL_VERTICES_T(vd, g, TGraph) put(vertex_index, g, vd, i++);
- i=0;
- BGL_FORALL_EDGES_T(ed, g, TGraph) put(edge_index, g, ed, i++);
+ dynamic_properties p;
+ make_dynamic_properties(g, p);
+ read_graphviz(is, g, p);
+ std::cout << "Number of vertices: " << num_vertices(g) << std::endl;
+ std::cout << "Number of edges: " << num_edges(g) << std::endl;
+ int i = 0;
+ BGL_FORALL_VERTICES_T(vd, g, TG)
+ {
+ put(vertex_index, g, vd, i++);
+ }
+ i=0;
+ BGL_FORALL_EDGES_T(ed, g, TG)
+ {
+ put(edge_index, g, ed, i++);
+ }
}
-template <typename TGraph>
-void read_data(const char* file, TGraph& g)
+template <typename TG>
+void read_data(const char *file, TG &g)
{
- std::cout << "Reading data from file: " << file << "\n";
- std::ifstream ifs(file);
- BOOST_REQUIRE(ifs.good());
- read_data1(ifs, g);
+ std::cout << "Reading data from file: " << file << std::endl;
+ std::ifstream ifs(file);
+ BOOST_REQUIRE(ifs.good());
+ read_data1(ifs, g);
}
+struct my_float : boost::mcr_float<>
+{
+ static double infinity()
+ {
+ return 1000;
+ }
+};
+
+struct my_float2 : boost::mcr_float<>
+{
+ static double infinity() { return 2; }
+};
+
int test_main(int argc, char* argv[])
{
- std::string input_file = "cycle_ratio_s382.90.dot";
- if (argc > 1) input_file = argv[1];
+ using std::endl; using std::cout;
+ const double epsilon = 0.005;
+ double min_cr, max_cr; ///Minimum and maximum cycle ratio
+ typedef std::vector<graph_traits<diGraphInt>::edge_descriptor> ccInt_t;
+ typedef std::vector<graph_traits<diGraphReal>::edge_descriptor> ccReal_t;
+ ccInt_t cc; ///critical cycle
+
+ diGraphInt tg;
+ property_map<diGraphInt, vertex_index_t>::type vim = get(vertex_index, tg);
+ property_map<diGraphInt, edge_weight_t>::type ew1m = get(edge_weight, tg);
+ property_map<diGraphInt, edge_weight2_t>::type ew2m = ew2m;
+
+
+
+ {
+ std::istringstream iss(test_graph1);
+ assert(iss.good());
+ read_data1(iss, tg);
+ max_cr = maximum_cycle_ratio(tg, vim, ew1m, ew2m);
+ cout << "Maximum cycle ratio is " << max_cr << endl;
+ BOOST_CHECK(std::abs( max_cr - 0.666666666) < epsilon );
+ tg.clear();
+ }
+
+ {
+ std::istringstream iss(test_graph2);
+ read_data1(iss, tg);
+ // TODO: This is causing a failuire, but I'm not really sure what it's doing per se.
+ // Commented out for now.
+ // BOOST_CHECK(std::abs(maximum_cycle_ratio(tg, vim, ew1m, ew2m) + (std::numeric_limits<double>::max)()) < epsilon );
+ BOOST_CHECK(std::abs(boost::maximum_cycle_ratio(tg, vim, ew1m, ew2m,
+ static_cast<ccInt_t*>(0), my_float()) + 1000) < epsilon );
+ tg.clear();
+ }
+
+ {
+ std::istringstream iss(test_graph3);
+ diGraphInt tgi;
+ read_data1(iss, tgi);
+ double max_cr = maximum_cycle_ratio(tgi, vim, ew1m, ew2m,
+ static_cast<ccInt_t*>(0));
+ cout << "Maximum cycle ratio is " << max_cr << endl;
+ BOOST_CHECK(std::abs( max_cr - 2.75) < epsilon );
+ double maxmc = maximum_cycle_mean(tgi, vim, ew1m, get(edge_index, tgi));
+ cout << "Maximum cycle mean is " << maxmc << endl;
+ BOOST_CHECK(std::abs( maxmc - 5.5) < epsilon );
+ tg.clear();
+ }
+
+ {
+ std::istringstream iss(test_graph4);
+ read_data1(iss, tg);
+ max_cr = maximum_cycle_ratio(tg, vim, ew1m, ew2m);
+ cout << "Maximum cycle ratio is " << max_cr << endl;
+ BOOST_CHECK(std::abs( max_cr - 2.5) < epsilon );
+ min_cr = minimum_cycle_ratio(tg, vim, ew1m, ew2m);
+ cout << "Minimum cycle ratio is " << min_cr << endl;
+ BOOST_CHECK(std::abs( min_cr - 0.5) < epsilon );
+ tg.clear();
+ }
+
+ {
+ std::istringstream iss(test_graph5);
+ read_data1(iss, tg);
+ min_cr = minimum_cycle_ratio(tg, vim, ew1m, ew2m, &cc, my_float());
+ BOOST_CHECK(std::abs( min_cr - 0.666666666) < epsilon );
+ cout << "Minimum cycle ratio is " << min_cr << endl;
+ cout << "Critical cycle is:\n";
+ for (ccInt_t::iterator itr = cc.begin(); itr != cc.end(); ++itr)
+ {
+ cout << "(" << get(vertex_name, tg, source(*itr, tg)) <<
+ "," << get(vertex_name, tg, target(*itr, tg)) << ") ";
+ }
+ cout << endl;
+ tg.clear();
+ }
+
+ {
+ read_data("cycle_ratio_s382.90.dot", tg);
+ min_cr = boost::minimum_cycle_ratio(tg, vim, ew1m, ew2m, &cc, my_float2());
+ cout << "Minimum cycle ratio is " << min_cr << endl;
+ BOOST_CHECK(std::abs(min_cr - 0.33333333333) < epsilon );
+ cout << "Critical cycle is:" << endl;
+ for (ccInt_t::iterator it = cc.begin(); it != cc.end(); ++it)
+ {
+ cout << "(" << get(vertex_name, tg, source(*it, tg)) << "," <<
+ get(vertex_name, tg, target(*it, tg)) << ") ";
+ }
+ cout << endl;
+ tg.clear();
+ }
+
+ {
+ diGraphReal tgr;
+ ccReal_t cc1;
+ std::istringstream iss(test_graph6);
+ read_data1(iss, tgr);
+ max_cr = maximum_cycle_ratio(tgr, get(vertex_index, tgr), get(edge_weight, tgr), get(edge_weight2, tgr));
+ cout << "Maximum cycle ratio is " << max_cr << endl;
+ min_cr = minimum_cycle_ratio(tgr, get(vertex_index, tgr), get(edge_weight, tgr),
+ get(edge_weight2, tgr), &cc);
+ cout << "Minimal cycle ratio is " << min_cr << endl;
+ std::pair<double, double> cr(.0,.0);
+ cout << "Critical cycle is:\n";
+ for (ccReal_t::iterator itr = cc.begin(); itr != cc.end(); ++itr)
+ {
+ cr.first += get(edge_weight, tgr, *itr); cr.second += get(edge_weight2, tgr, *itr);
+ cout << "(" << get(vertex_name, tgr, source(*itr, tgr)) << "," <<
+ get(vertex_name, tgr, target(*itr, tgr)) << ") ";
+ }
+ BOOST_CHECK(std::abs(cr.first / cr.second - min_cr) < epsilon);
+ cout << endl;
+ }
+
+ {
+ GraphMInt gm(10);
+ typedef graph_traits<GraphMInt>::vertex_iterator VertexItM;
+ typedef graph_traits<GraphMInt>::edge_descriptor EdgeM;
+ VertexItM vi1, vi2, vi_end;
+ for (tie(vi1, vi_end) = vertices(gm); vi1 != vi_end; ++vi1)
+ {
+ for (vi2 = vertices(gm).first; vi2 != vi_end; ++vi2)
+ add_edge(*vi1, *vi2, gm);
+ }
+ max_cr = maximum_cycle_ratio(gm, get(vertex_index, gm),
+ get(&CEdgeProps<int, int>::m_w1, gm), get(&CEdgeProps<int, int>::m_w2, gm));
+ BOOST_CHECK(std::abs(max_cr - 0.5) < epsilon);
+ }
- const double epsilon = 0.00000001;
- double min_cr, max_cr; ///Minimum and maximum cycle ratio
- typedef std::vector<graph_traits<GraphInt>::edge_descriptor> ccInt_t;
- typedef std::vector<graph_traits<GraphReal>::edge_descriptor> ccReal_t;
- ccInt_t cc; ///For storing critical edges
-
- GraphInt tg;
- property_map<GraphInt, vertex_index_t>::type vim = get(vertex_index, tg);
- property_map<GraphInt, edge_weight_t>::type ew1m = get(edge_weight, tg);
- property_map<GraphInt, edge_weight2_t>::type ew2m = ew2m;
-
- std::istringstream iss(test_graph1);
- read_data1(/*std::istringstream(test_graph1)*/iss, tg);
- max_cr = maximum_cycle_ratio(tg, vim, ew1m, ew2m);
- std::cout << "Maximum cycle ratio is " << max_cr << "\n";
- BOOST_CHECK(std::abs( max_cr - 0.666666666) < epsilon );
- tg.clear();
-
- iss.clear(); iss.str(test_graph2);
- read_data1(iss, tg);
- BOOST_CHECK(std::abs(maximum_cycle_ratio(tg, vim, ew1m, ew2m) + (std::numeric_limits<int>::max)()) < epsilon );
- BOOST_CHECK(std::abs(maximum_cycle_ratio(tg, vim, ew1m, ew2m, static_cast<ccInt_t*>(0), 1000) - 1000) < epsilon );
- tg.clear();
-
- iss.clear(); iss.str(test_graph3);
- read_data1(iss, tg);
- max_cr = maximum_cycle_ratio(tg, vim, ew1m, ew2m, static_cast<ccInt_t*>(0), -1);
- std::cout << "Maximum cycle ratio is " << max_cr << '\n';
- BOOST_CHECK(std::abs( max_cr - 2.75) < epsilon );
- double maxmc = maximum_mean_cycle(tg, vim, ew1m, get(edge_index, tg));
- std::cout << "Maximum mean cycle is " << maxmc << '\n';
- BOOST_CHECK(std::abs( maxmc - 5.5) < epsilon );
- tg.clear();
-
- iss.clear(); iss.str(test_graph4);
- read_data1(iss, tg);
- max_cr = maximum_cycle_ratio(tg, vim, ew1m, ew2m);
- std::cout << "Maximum cycle ratio is " << max_cr << '\n';
- BOOST_CHECK(std::abs( max_cr - 2.5) < epsilon );
- min_cr = minimum_cycle_ratio(tg, vim, ew1m, ew2m, get(edge_index, tg));
- std::cout << "Minimum cycle ratio is " << min_cr << '\n';
- BOOST_CHECK(std::abs( min_cr - 0.5) < epsilon );
- tg.clear();
-
- iss.clear(); iss.str(test_graph5);
- read_data1(iss, tg);
- min_cr = minimum_cycle_ratio_good_graph(tg, vim, ew1m, ew2m, get(edge_index,tg), &cc);
- BOOST_CHECK(std::abs( min_cr - 0.666666666) < epsilon );
- std::cout << "Minimum cycle ratio is " << min_cr << "\n";
- std::cout << "Critical cycle is:\n";
- for (ccInt_t::iterator itr = cc.begin(); itr != cc.end(); ++itr) {
- std::cout << "(" << get(vertex_name, tg, source(*itr, tg)) << "," << get(vertex_name, tg, target(*itr, tg)) << ") ";
- }
- std::cout << '\n';
- tg.clear();
-
- /**/read_data(input_file.c_str(), tg);
- min_cr = minimum_cycle_ratio(tg, vim, ew1m, ew2m, get(edge_index,tg), &cc, 2);
- std::cout << "Minimum cycle ratio is " << min_cr << "\n";
- BOOST_CHECK(std::abs(min_cr - 0.33333333333) < epsilon );
- std::cout << "Critical cycle is:\n";
- for (ccInt_t::iterator it = cc.begin(); it != cc.end(); ++it)
- {
- std::cout << "(" << get(vertex_name, tg, source(*it, tg)) << "," << get(vertex_name, tg, target(*it, tg)) << ") ";
- }
- std::cout << '\n';
- tg.clear();
-
- GraphReal tgr;
- ccReal_t cc1;
-
- iss.clear(); iss.str(test_graph6);
- read_data1(iss, tgr);
- max_cr = maximum_cycle_ratio(tgr, get(vertex_index, tgr), get(edge_weight, tgr), get(edge_weight2, tgr));
- std::cout << "Maximum cycle ratio is " << max_cr << '\n';
- double pl_infnt = double(*std::max_element(get_property_iter_range(tgr, edge_weight).first, get_property_iter_range(tgr, edge_weight).second)) /
- *std::min_element(get_property_iter_range(tgr, edge_weight2).first, get_property_iter_range(tgr, edge_weight2).second);
- std::cout << "Set infinity for minimum_cycle_ratio() call to " << pl_infnt << '\n';
- min_cr = minimum_cycle_ratio(tgr, get(vertex_index, tgr), get(edge_weight, tgr), get(edge_weight2, tgr),
- get(edge_index, tgr), &cc, pl_infnt);
- std::cout << "Minimal cycle ratio is " << min_cr << '\n';
- std::pair<double, double> cr(.0,.0);
- std::cout << "Critical cycle is:\n";
- for (ccReal_t::iterator itr = cc.begin(); itr != cc.end(); ++itr)
- {
- cr.first += get(edge_weight, tgr, *itr); cr.second += get(edge_weight2, tgr, *itr);
- std::cout << "(" << get(vertex_name, tgr, source(*itr, tgr)) << "," << get(vertex_name, tgr, target(*itr, tgr)) << ") ";
- }
- BOOST_CHECK(std::abs(cr.first / cr.second - min_cr) < epsilon);
- std::cout << '\n';
-
- GraphMInt gm(10);
- typedef graph_traits<GraphMInt>::vertex_iterator VertexItM;
- typedef graph_traits<GraphMInt>::edge_descriptor EdgeM;
- VertexItM vi1, vi2, vi_end;
- for (tie(vi1, vi_end) = vertices(gm); vi1 != vi_end; ++vi1)
- {
- for (vi2 = vertices(gm).first; vi2 != vi_end; ++vi2)
- add_edge(*vi1, *vi2, gm);
- }
- max_cr = maximum_cycle_ratio(gm, get(vertex_index, gm), get(&CEdgeProps<int, int>::m_w1, gm), get(&CEdgeProps<int, int>::m_w2, gm));
- BOOST_CHECK(std::abs(max_cr - 0.5) < epsilon);
- return 0;
+ return 0;
}