Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r55467 - in branches/release: boost/graph libs libs/graph/doc libs/graph/example libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-08-08 14:19:55

Author: jewillco
Date: 2009-08-08 14:19:53 EDT (Sat, 08 Aug 2009)
New Revision: 55467
URL: http://svn.boost.org/trac/boost/changeset/55467

Log:
Merged in changes from trunk
Text files modified:
   branches/release/boost/graph/compressed_sparse_row_graph.hpp | 17
   branches/release/boost/graph/erdos_renyi_generator.hpp | 18
   branches/release/boost/graph/graphviz.hpp | 50
   branches/release/boost/graph/howard_cycle_ratio.hpp | 1075 ++++++++++++++++++++-------------------
   branches/release/boost/graph/rmat_graph_generator.hpp | 127 ++--
   branches/release/boost/graph/small_world_generator.hpp | 22
   branches/release/libs/graph/doc/howard_cycle_ratio.html | 277 ++++++----
   branches/release/libs/graph/doc/read_graphml.html | 2
   branches/release/libs/graph/doc/read_graphviz.html | 2
   branches/release/libs/graph/doc/write-graphviz.html | 88 +-
   branches/release/libs/graph/doc/write_graphml.html | 2
   branches/release/libs/graph/example/cycle_ratio_example.cpp | 139 ++--
   branches/release/libs/graph/test/cycle_ratio_tests.cpp | 484 ++++++++++-------
   branches/release/libs/graph/test/metis_test.cpp | 1
   branches/release/libs/maintainers.txt | 2
   15 files changed, 1231 insertions(+), 1075 deletions(-)

Modified: branches/release/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- branches/release/boost/graph/compressed_sparse_row_graph.hpp (original)
+++ branches/release/boost/graph/compressed_sparse_row_graph.hpp 2009-08-08 14:19:53 EDT (Sat, 08 Aug 2009)
@@ -1468,8 +1468,14 @@
 typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator it;
 EdgeIndex v_row_start = g.m_rowstart[v];
 EdgeIndex next_row_start = g.m_rowstart[v + 1];
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+ return std::make_pair(it(ed(v, v_row_start)),
+ it(ed(v, next_row_start)));
+#else
+ // Special case to allow incremental construction
 return std::make_pair(it(ed(v, v_row_start)),
 it(ed(v, (std::max)(v_row_start, next_row_start))));
+#endif
}

template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
@@ -1478,7 +1484,12 @@
{
 EdgeIndex v_row_start = g.m_rowstart[v];
 EdgeIndex next_row_start = g.m_rowstart[v + 1];
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+ return next_row_start - v_row_start;
+#else
+ // Special case to allow incremental construction
 return (std::max)(v_row_start, next_row_start) - v_row_start;
+#endif
}

// From AdjacencyGraph
@@ -1489,9 +1500,15 @@
{
 EdgeIndex v_row_start = g.m_rowstart[v];
 EdgeIndex next_row_start = g.m_rowstart[v + 1];
+#ifdef BOOST_GRAPH_USE_NEW_CSR_INTERFACE
+ return std::make_pair(g.m_column.begin() + v_row_start,
+ g.m_column.begin() + next_row_start);
+#else
+ // Special case to allow incremental construction
 return std::make_pair(g.m_column.begin() + v_row_start,
 g.m_column.begin() +
 (std::max)(v_row_start, next_row_start));
+#endif
}

// Extra, common functions

Modified: branches/release/boost/graph/erdos_renyi_generator.hpp
==============================================================================
--- branches/release/boost/graph/erdos_renyi_generator.hpp (original)
+++ branches/release/boost/graph/erdos_renyi_generator.hpp 2009-08-08 14:19:53 EDT (Sat, 08 Aug 2009)
@@ -45,26 +45,26 @@

 public:
 erdos_renyi_iterator() : gen(), n(0), edges(0), allow_self_loops(false) {}
- erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
+ erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
 double fraction = 0.0, bool allow_self_loops = false)
 : gen(&gen), n(n), edges(edges_size_type(fraction * n * n)),
 allow_self_loops(allow_self_loops)
- {
+ {
 if (is_undirected) edges = edges / 2;
- next();
+ next();
 }

- erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
+ erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
 edges_size_type m, bool allow_self_loops = false)
 : gen(&gen), n(n), edges(m),
 allow_self_loops(allow_self_loops)
- {
- next();
+ {
+ next();
 }

 const std::pair<vertices_size_type, vertices_size_type>&
 dereference() const { return current; }
-
+
 void increment() {
 --edges;
 next();
@@ -128,14 +128,14 @@
 this->gen.reset(new uniform_01<RandomGenerator>(gen));

 if (prob == 0.0) {src = (std::numeric_limits<vertices_size_type>::max)(); return;}
- next();
+ next();
 }

 const std::pair<vertices_size_type, vertices_size_type>&
 dereference() const {
 return current;
 }
-
+
 bool equal(const sorted_erdos_renyi_iterator& o) const {
 return src == o.src && tgt_index == o.tgt_index;
 }

Modified: branches/release/boost/graph/graphviz.hpp
==============================================================================
--- branches/release/boost/graph/graphviz.hpp (original)
+++ branches/release/boost/graph/graphviz.hpp 2009-08-08 14:19:53 EDT (Sat, 08 Aug 2009)
@@ -237,7 +237,7 @@
 template <typename Graph, typename VertexPropertiesWriter,
 typename EdgePropertiesWriter, typename GraphPropertiesWriter,
 typename VertexID>
- inline void
+ inline void
 write_graphviz
 (std::ostream& out, const Graph& g,
 VertexPropertiesWriter vpw,
@@ -246,6 +246,8 @@
 VertexID vertex_id
 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
 {
+ BOOST_CONCEPT_ASSERT((EdgeListGraphConcept<Graph>));
+
 typedef typename graph_traits<Graph>::directed_category cat_type;
 typedef graphviz_io_traits<cat_type> Traits;
 std::string name = "G";
@@ -271,7 +273,7 @@

 template <typename Graph, typename VertexPropertiesWriter,
 typename EdgePropertiesWriter, typename GraphPropertiesWriter>
- inline void
+ inline void
 write_graphviz(std::ostream& out, const Graph& g,
 VertexPropertiesWriter vpw,
 EdgePropertiesWriter epw,
@@ -284,7 +286,7 @@
 template <typename Graph>
 inline void
 write_graphviz(std::ostream& out, const Graph& g
- BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
+ BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
 {
 default_writer dw;
 default_writer gw;
@@ -416,7 +418,7 @@

 detail::write_graphviz_subgraph(out, g,
 vertex_marker.begin(),
- edge_marker.begin(),
+ edge_marker.begin(),
 get(vertex_index, g));
 }

@@ -434,20 +436,20 @@

 template <typename Graph, typename VertexID>
 void write_graphviz(std::ostream& out, const subgraph<Graph>& g,
- VertexID vertex_id)
+ VertexID vertex_id)
 {
 std::vector<bool> edge_marker(num_edges(g), true);
 std::vector<bool> vertex_marker(num_vertices(g), true);

 detail::write_graphviz_subgraph(out, g,
 vertex_marker.begin(),
- edge_marker.begin(),
+ edge_marker.begin(),
 vertex_id);
 }

 template <typename Graph, typename VertexID>
 void write_graphviz(const std::string& filename, const subgraph<Graph>& g,
- VertexID vertex_id)
+ VertexID vertex_id)
 {
 std::ofstream out(filename.c_str());
 std::vector<bool> edge_marker(num_edges(g), true);
@@ -494,7 +496,7 @@
 // Library has not existed for a while
 // extern void read_graphviz(const std::string& file, GraphvizDigraph& g);
 // extern void read_graphviz(FILE* file, GraphvizDigraph& g);
- //
+ //
 // extern void read_graphviz(const std::string& file, GraphvizGraph& g);
 // extern void read_graphviz(FILE* file, GraphvizGraph& g);

@@ -507,7 +509,7 @@
 void operator()(std::ostream& out, Descriptor key) const
 {
 bool first = true;
- for (dynamic_properties::const_iterator i = dp->begin();
+ for (dynamic_properties::const_iterator i = dp->begin();
 i != dp->end(); ++i) {
 if (typeid(key) == i->second->key()) {
 if (first) out << " [";
@@ -529,14 +531,14 @@
 {
 public:
 dynamic_vertex_properties_writer(const dynamic_properties& dp,
- const std::string& node_id)
+ const std::string& node_id)
 : dp(&dp), node_id(&node_id) { }

 template<typename Descriptor>
 void operator()(std::ostream& out, Descriptor key) const
 {
 bool first = true;
- for (dynamic_properties::const_iterator i = dp->begin();
+ for (dynamic_properties::const_iterator i = dp->begin();
 i != dp->end(); ++i) {
 if (typeid(key) == i->second->key()
 && i->first != *node_id) {
@@ -577,8 +579,8 @@
 };

 template<typename Vertex>
- inline std::string
- get(node_id_property_map<Vertex> pm,
+ inline std::string
+ get(node_id_property_map<Vertex> pm,
 typename node_id_property_map<Vertex>::key_type v)
 { return get(*pm.node_id, *pm.dp, v); }

@@ -587,7 +589,7 @@
 template<typename Graph>
 inline void
 write_graphviz(std::ostream& out, const Graph& g,
- const dynamic_properties& dp,
+ const dynamic_properties& dp,
 const std::string& node_id = "node_id"
 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph,vertex_list_graph_tag))
 {
@@ -677,7 +679,7 @@
 static int idx = 0;
 return edge_t(idx++);
 };
-
+
 bool operator==(const edge_t& rhs) const {
 return idx_ == rhs.idx_;
 }
@@ -693,14 +695,14 @@
 virtual bool is_directed() const = 0;
 virtual void do_add_vertex(const node_t& node) = 0;

- virtual void
+ virtual void
 do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)
 = 0;

- virtual void
+ virtual void
 set_node_property(const id_t& key, const node_t& node, const id_t& value) = 0;

- virtual void
+ virtual void
 set_edge_property(const id_t& key, const edge_t& edge, const id_t& value) = 0;

 virtual void // RG: need new second parameter to support BGL subgraphs
@@ -722,7 +724,7 @@

 bool is_directed() const
 {
- return
+ return
 boost::is_convertible<
 typename boost::graph_traits<MutableGraph>::directed_category,
 boost::directed_tag>::value;
@@ -735,17 +737,17 @@

 // Set up a mapping from name to BGL vertex.
 bgl_nodes.insert(std::make_pair(node, v));
-
+
 // node_id_prop_ allows the caller to see the real id names for nodes.
 put(node_id_prop_, dp_, v, node);
 }

- void
+ void
 do_add_edge(const edge_t& edge, const node_t& source, const node_t& target)
 {
 std::pair<bgl_edge_t, bool> result =
 add_edge(bgl_nodes[source], bgl_nodes[target], graph_);
-
+
 if(!result.second) {
 // In the case of no parallel edges allowed
 boost::throw_exception(bad_parallel_edge(source, target));
@@ -773,7 +775,7 @@
 put(key, dp_, &graph_, value);
 }

-
+
 protected:
 MutableGraph& graph_;
 dynamic_properties& dp_;
@@ -791,7 +793,7 @@
template <typename MutableGraph>
bool read_graphviz(std::istream& in, MutableGraph& graph,
 dynamic_properties& dp,
- std::string const& node_id = "node_id")
+ std::string const& node_id = "node_id")
{
 std::string data;
 in >> std::noskipws;

Modified: branches/release/boost/graph/howard_cycle_ratio.hpp
==============================================================================
--- branches/release/boost/graph/howard_cycle_ratio.hpp (original)
+++ branches/release/boost/graph/howard_cycle_ratio.hpp 2009-08-08 14:19:53 EDT (Sat, 08 Aug 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 BOOST_GRAPH_CYCLE_RATIO_HOWARD_HPP
+#define BOOST_GRAPH_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. (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: branches/release/boost/graph/rmat_graph_generator.hpp
==============================================================================
--- branches/release/boost/graph/rmat_graph_generator.hpp (original)
+++ branches/release/boost/graph/rmat_graph_generator.hpp 2009-08-08 14:19:53 EDT (Sat, 08 Aug 2009)
@@ -47,7 +47,7 @@
 { }

 template <typename T>
- bool operator()(const T& x, const T& y)
+ bool operator()(const T& x, const T& y)
 { return distrib(x) == id || distrib(y) == id; }

private:
@@ -58,16 +58,16 @@
template <typename RandomGenerator, typename T>
void
generate_permutation_vector(RandomGenerator& gen, std::vector<T>& vertexPermutation, T n)
-{
+{
 using boost::uniform_int;

 vertexPermutation.resize(n);
-
+
 // Generate permutation map of vertex numbers
 uniform_int<T> rand_vertex(0, n-1);
 for (T i = 0; i < n; ++i)
 vertexPermutation[i] = i;
-
+
 // Can't use std::random_shuffle unless we create another (synchronized) PRNG
 for (T i = 0; i < n; ++i)
 std::swap(vertexPermutation[i], vertexPermutation[rand_vertex(gen)]);
@@ -75,14 +75,14 @@

template <typename RandomGenerator, typename T>
std::pair<T,T>
-generate_edge(shared_ptr<uniform_01<RandomGenerator> > prob, T n,
+generate_edge(shared_ptr<uniform_01<RandomGenerator> > prob, T n,
 unsigned int SCALE, double a, double b, double c, double d)
{
 T u = 0, v = 0;
 T step = n/2;
 for (unsigned int j = 0; j < SCALE; ++j) {
 double p = (*prob)();
-
+
 if (p < a)
 ;
 else if (p >= a && p < a + b)
@@ -93,18 +93,18 @@
 u += step;
 v += step;
 }
-
+
 step /= 2;

 // 0.2 and 0.9 are hardcoded in the reference SSCA implementation.
 // The maximum change in any given value should be less than 10%
- a *= 0.9 + 0.2 * (*prob)();
- b *= 0.9 + 0.2 * (*prob)();
- c *= 0.9 + 0.2 * (*prob)();
- d *= 0.9 + 0.2 * (*prob)();
-
+ a *= 0.9 + 0.2 * (*prob)();
+ b *= 0.9 + 0.2 * (*prob)();
+ c *= 0.9 + 0.2 * (*prob)();
+ d *= 0.9 + 0.2 * (*prob)();
+
 double S = a + b + c + d;
-
+
 a /= S; b /= S; c /= S;
 // d /= S;
 // Ensure all values add up to 1, regardless of floating point errors
@@ -119,8 +119,8 @@
 /*
 Chakrabarti's R-MAT scale free generator.

- For all flavors of the R-MAT iterator a+b+c+d must equal 1 and for the
- unique_rmat_iterator 'm' << 'n^2'. If 'm' is too close to 'n^2' the
+ For all flavors of the R-MAT iterator a+b+c+d must equal 1 and for the
+ unique_rmat_iterator 'm' << 'n^2'. If 'm' is too close to 'n^2' the
 generator may be unable to generate sufficient unique edges

 To get a true scale free distribution {a, b, c, d : a > b, a > c, a > d}
@@ -145,19 +145,19 @@
 : gen(), edge(0) { }

 // Initialize for edge generation
- rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
+ rmat_iterator(RandomGenerator& gen, vertices_size_type n,
+ edges_size_type m, double a, double b, double c,
 double d, bool permute_vertices = true)
- : gen(), n(n), a(a), b(b), c(c), d(d), edge(m),
- permute_vertices(permute_vertices),
+ : gen(), n(n), a(a), b(b), c(c), d(d), edge(m),
+ permute_vertices(permute_vertices),
 SCALE(int_log2(n))
-
+
 {
 this->gen.reset(new uniform_01<RandomGenerator>(gen));

 assert(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));

- if (permute_vertices)
+ if (permute_vertices)
 generate_permutation_vector(gen, vertexPermutation, n);

 // TODO: Generate the entire adjacency matrix then "Clip and flip" if undirected graph
@@ -167,9 +167,9 @@
 tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);

 if (permute_vertices)
- current = std::make_pair(vertexPermutation[u],
+ current = std::make_pair(vertexPermutation[u],
 vertexPermutation[v]);
- else
+ else
 current = std::make_pair(u, v);

 --edge;
@@ -177,16 +177,16 @@

 reference operator*() const { return current; }
 pointer operator->() const { return &current; }
-
+
 rmat_iterator& operator++()
 {
 vertices_size_type u, v;
 tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);

 if (permute_vertices)
- current = std::make_pair(vertexPermutation[u],
+ current = std::make_pair(vertexPermutation[u],
 vertexPermutation[v]);
- else
+ else
 current = std::make_pair(u, v);

 --edge;
@@ -223,15 +223,15 @@
 std::vector<vertices_size_type> vertexPermutation;
 value_type current;
 };
-
+
 // Sorted version for CSR
 template <typename T>
 struct sort_pair {
 bool operator() (const std::pair<T,T>& x, const std::pair<T,T>& y)
- {
+ {
 if (x.first == y.first)
 return x.second > y.second;
- else
+ else
 return x.first > y.first;
 }
 };
@@ -257,25 +257,25 @@
 { }

 // Initialize for edge generation
- sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
+ sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
+ edges_size_type m, double a, double b, double c,
 double d, bool permute_vertices = true,
 EdgePredicate ep = keep_all_edges())
 : gen(), permute_vertices(permute_vertices),
 values(sort_pair<vertices_size_type>()), done(false)
-
+
 {
 assert(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));

 this->gen.reset(new uniform_01<RandomGenerator>(gen));

 std::vector<vertices_size_type> vertexPermutation;
- if (permute_vertices)
+ if (permute_vertices)
 generate_permutation_vector(gen, vertexPermutation, n);
-
+
 // TODO: "Clip and flip" if undirected graph
 int SCALE = int_log2(n);
-
+
 for (edges_size_type i = 0; i < m; ++i) {

 vertices_size_type u, v;
@@ -297,7 +297,7 @@

 reference operator*() const { return current; }
 pointer operator->() const { return &current; }
-
+
 sorted_rmat_iterator& operator++()
 {
 if (!values.empty()) {
@@ -359,23 +359,23 @@
 { }

 // Initialize for edge generation
- unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
+ unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
+ edges_size_type m, double a, double b, double c,
 double d, bool permute_vertices = true,
 EdgePredicate ep = keep_all_edges())
 : gen(), done(false)
-
+
 {
 assert(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));

 this->gen.reset(new uniform_01<RandomGenerator>(gen));

 std::vector<vertices_size_type> vertexPermutation;
- if (permute_vertices)
+ if (permute_vertices)
 generate_permutation_vector(gen, vertexPermutation, n);

 int SCALE = int_log2(n);
-
+
 std::map<value_type, bool> edge_map;

 edges_size_type edges = 0;
@@ -383,14 +383,14 @@
 vertices_size_type u, v;
 tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);

- // Lowest vertex number always comes first
+ // Lowest vertex number always comes first
 // (this means we don't have to worry about i->j and j->i being in the edge list)
 if (u > v && is_same<directed_category, undirected_tag>::value)
 std::swap(u, v);

 if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
 edge_map[std::make_pair(u, v)] = true;
-
+
 if (permute_vertices) {
 if (ep(vertexPermutation[u], vertexPermutation[v]))
 values.push_back(std::make_pair(vertexPermutation[u], vertexPermutation[v]));
@@ -404,20 +404,20 @@
 } while (edges < m);
 // NGE - Asking for more than n^2 edges will result in an infinite loop here
 // Asking for a value too close to n^2 edges may as well
-
+
 current = values.back();
 values.pop_back();
 }

 reference operator*() const { return current; }
 pointer operator->() const { return &current; }
-
+
 unique_rmat_iterator& operator++()
 {
 if (!values.empty()) {
 current = values.back();
 values.pop_back();
- } else
+ } else
 done = true;

 return *this;
@@ -470,30 +470,30 @@
 : gen(), values(sort_pair<vertices_size_type>()), done(true) { }

 // Initialize for edge generation
- sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
- edges_size_type m, double a, double b, double c,
- double d, bool bidirectional = false,
+ sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n,
+ edges_size_type m, double a, double b, double c,
+ double d, bool bidirectional = false,
 bool permute_vertices = true,
 EdgePredicate ep = keep_all_edges())
- : gen(), bidirectional(bidirectional),
+ : gen(), bidirectional(bidirectional),
 values(sort_pair<vertices_size_type>()), done(false)
-
+
 {
 assert(boost::test_tools::check_is_close(a + b + c + d, 1., boost::test_tools::fraction_tolerance(1.e-5)));

 this->gen.reset(new uniform_01<RandomGenerator>(gen));
-
+
 std::vector<vertices_size_type> vertexPermutation;
 if (permute_vertices)
 generate_permutation_vector(gen, vertexPermutation, n);

 int SCALE = int_log2(n);
-
+
 std::map<value_type, bool> edge_map;
-
+
 edges_size_type edges = 0;
 do {
-
+
 vertices_size_type u, v;
 tie(u, v) = generate_edge(this->gen, n, SCALE, a, b, c, d);

@@ -501,8 +501,8 @@
 if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
 edge_map[std::make_pair(u, v)] = true;
 edge_map[std::make_pair(v, u)] = true;
-
- if (ep(u, v))
+
+ if (ep(u, v)) {
 if (permute_vertices) {
 values.push(std::make_pair(vertexPermutation[u], vertexPermutation[v]));
 values.push(std::make_pair(vertexPermutation[v], vertexPermutation[u]));
@@ -510,15 +510,16 @@
 values.push(std::make_pair(u, v));
 values.push(std::make_pair(v, u));
 }
+ }

 ++edges;
 }
 } else {
- // Lowest vertex number always comes first
+ // Lowest vertex number always comes first
 // (this means we don't have to worry about i->j and j->i being in the edge list)
 if (u > v && is_same<directed_category, undirected_tag>::value)
 std::swap(u, v);
-
+
 if (edge_map.find(std::make_pair(u, v)) == edge_map.end()) {
 edge_map[std::make_pair(u, v)] = true;

@@ -533,7 +534,7 @@
 ++edges;
 }
 }
-
+
 } while (edges < m);
 // NGE - Asking for more than n^2 edges will result in an infinite loop here
 // Asking for a value too close to n^2 edges may as well
@@ -544,13 +545,13 @@

 reference operator*() const { return current; }
 pointer operator->() const { return &current; }
-
+
 sorted_unique_rmat_iterator& operator++()
 {
 if (!values.empty()) {
 current = values.top();
 values.pop();
- } else
+ } else
 done = true;

 return *this;
@@ -578,7 +579,7 @@
 bool bidirectional;

 // Internal data structures
- std::priority_queue<value_type, std::vector<value_type>,
+ std::priority_queue<value_type, std::vector<value_type>,
 sort_pair<vertices_size_type> > values;
 value_type current;
 bool done;

Modified: branches/release/boost/graph/small_world_generator.hpp
==============================================================================
--- branches/release/boost/graph/small_world_generator.hpp (original)
+++ branches/release/boost/graph/small_world_generator.hpp 2009-08-08 14:19:53 EDT (Sat, 08 Aug 2009)
@@ -20,7 +20,7 @@
 template<typename RandomGenerator, typename Graph>
 class small_world_iterator
 {
- typedef typename graph_traits<Graph>::vertices_size_type
+ typedef typename graph_traits<Graph>::vertices_size_type
 vertices_size_type;

 public:
@@ -31,20 +31,20 @@
 typedef void difference_type;

 small_world_iterator() : gen(0) {}
- small_world_iterator(RandomGenerator& gen, vertices_size_type n,
- vertices_size_type k, double prob = 0.0,
- bool allow_self_loops = false)
- : gen(&gen), n(n), k(k), prob(prob), source(0),
- target(allow_self_loops? 0 : 1),
- allow_self_loops(allow_self_loops),
+ small_world_iterator(RandomGenerator& gen, vertices_size_type n,
+ vertices_size_type k, double prob = 0.0,
+ bool allow_self_loops = false)
+ : gen(&gen), n(n), k(k), prob(prob), source(0),
+ target(allow_self_loops? 0 : 1),
+ allow_self_loops(allow_self_loops),
 current(0, allow_self_loops? 0 : 1)
 { }

 reference operator*() const { return current; }
 pointer operator->() const { return &current; }
-
+
 small_world_iterator& operator++()
- {
+ {
 target = (target + 1) % n;
 if (target == (source + k/2 + 1) % n) {
 ++source;
@@ -62,8 +62,8 @@
 vertices_size_type upper = (source + k/2) % n;
 do {
 current.second = rand_vertex_gen(*gen);
- } while (current.second >= lower && current.second <= upper
- || (upper < lower
+ } while ((current.second >= lower && current.second <= upper)
+ || (upper < lower
 && (current.second >= lower || current.second <= upper)));
 } else {
 current.second = target;

Modified: branches/release/libs/graph/doc/howard_cycle_ratio.html
==============================================================================
--- branches/release/libs/graph/doc/howard_cycle_ratio.html (original)
+++ branches/release/libs/graph/doc/howard_cycle_ratio.html 2009-08-08 14:19:53 EDT (Sat, 08 Aug 2009)
@@ -9,11 +9,11 @@

 
@@ -34,143 +34,200 @@
<BODY TEXT="#000000" LINK="#0000ee" VLINK="#551a8b" BGCOLOR="#ffffff" DIR="LTR">
<IMG SRC="../../..//boost.png" NAME="graphics1" ALT="C++ Boost" ALIGN=BOTTOM WIDTH=277 HEIGHT=86 BORDER=0>

-<H1><TT>maximum(minimum)_cycle_ratio</TT>
-</H1>
-// non-named parameter version
-
+<H1><TT>[maximum|minimum]_cycle_ratio</TT></H1>

-<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&gt::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>

+
+
+The <tt>maximum_cycle_ratio()</tt> function calculates the maximum cycle ratio of a
+weighted directed multigraph G=(V,E,W1,W2), where V is a vertex set,
+E is an edge set, W1 and W2 are edge weight functions, W2 is nonnegative.
+As a multigraph, G can have multiple edges connecting a pair of vertices.
+
+
+Let every edge e has two weights W1(e) and W2(e).
+Let c be a cycle of the graphg. Then, the cycle ratio, cr(c), is defined as:

-<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&gt::value_type plus_infinity =
- (std::numeric_limits<int>::max)());
- </PRE>
-
-The maximum_cycle_ratio() function calculates the maximum cycle ratio of a weighted directed multigraph g=(V,E,W1,W2), where V is a vertex set, E is an edge set, W1 and W2 are edge weight functions, W2 is nonnegative. Multigraph 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 maximal_cycle_ratio() returns minus_infinity if graph has no cycles. The value of the minus_infinity parameter should be small enough to garanty that g has at leat one cycle with greater ratio.
-
-
-Let every edge e have two weights W1(e) and W2(e). Let c be a cycle of a graph g. The cycle ratio (cr(c)) is defined as:
-<IMG SRC="figs/cr.jpg" NAME="graphics2" ALT="Cycle ratio definition" ALIGN=LEFT WIDTH=295 HEIGHT=82 BORDER=0> 
-The maximum (minimum) cycle ratio (mcr) is the maximum (minimum) cycle ratio of all cycles of the graph.
-Cycle calls critical if its ratio is equal to mcr. If the pcc 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.
-
-For a graph G=(V,E,W1,W2) let G'=(V,E,-W1,W2) be a graph with opposite W1 function, then the minimum cycle ratio of G is the opposite maximum cycle ratio of G'.
-The minimum_cycle_ratio() function just calls the maximum_cycle_ratio() with the opposite W1 function, so if the type value of the W1 weight is integral then it must be signed.
+<IMG SRC="figs/cr.jpg" ALT="Cycle ratio definition" BORDER=0>
+
+
+The maximum (minimum) cycle ratio (mcr) is the maximum (minimum) cycle ratio
+of all cycles of the graph. A cycle is called critical if its ratio is equal
+to the mcr. 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 pcc 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.
+

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).
-<H3>
-Where Defined</H3>
-<TT>boost/graph/howard_cycle_ratio.hpp</TT>
+
+
+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>
+
+
+<H3>Where Defined</H3>
+<TT>boost/graph/howard_cycle_ratio.hpp</TT>

<H3>Parameters</H3>
-IN: const TGraph& g 
-
-<BLOCKQUOTE>A directed weighted multigraph.
-The graph's type must be a model of VertexListGraph
-and IncidenceGraph
+IN: <tt>FloatTraits</tt> 
+<blockquote>
+The <tt>FloatTrats</tt> encapsulates customizable limits-like information for
+floating point types. This type must 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: 
+<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>
+IN: <tt>const Graph& g </tt>
+
+<BLOCKQUOTE>A weighted directed multigraph.
+The graph's type must be a model of VertexListGraph
+and IncidenceGraph
</BLOCKQUOTE>
-IN: TVertexIndexMap vim
+IN: <tt>VertexIndexMap vim</tt>

<BLOCKQUOTE>Maps each vertex of the graph to a unique integer in the
range [0, num_vertices(g)).
</BLOCKQUOTE>
-IN: TWeight1EdgeMap ew1m
+IN: <tt>EdgeWeight1 ew1m</t>

<BLOCKQUOTE>
-The W1 edge weight function. For minimum_cycle_ratio() if the type value of the ew1m is integral then it must be signed.
+The W1 edge weight function.
</BLOCKQUOTE>
-IN: TWeight2EdgeMap ew2m
-
-<BLOCKQUOTE>The W2 edge weight function. Must be nonnegative.</BLOCKQUOTE>
-IN: TEdgeIndexMap eim
+IN: <tt>EdgeWeight2 ew2m</tt>

-<BLOCKQUOTE>Maps each edge of the graph g to a unique integer
-in the range <TT>[0, num_edges(g)). </TT></BLOCKQUOTE>
-
-IN: boost::property_traits<TWeight1EdgeMap>::value_type minus_infinity
+<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>
+
+OUT: <tt>std::vector<typename boost::graph_traits<Graph>::edge_descriptor>* pcc</tt>

-<BLOCKQUOTE>Small enough value to garanty that g has at least one cycle with greater ratio</BLOCKQUOTE>
-IN: boost::property_traits<TWeight1EdgeMap>::value_type plus_infinity
+<BLOCKQUOTE>
+If non zero then one critical cycle will be stored in the std::vector. Default
+value is 0.
+</BLOCKQUOTE>
+
+IN (only for maximum/minimal_cycle_mean()): <tt>EdgeIndexMap eim</tt>

-<BLOCKQUOTE>Big enough value to garanty that g has at least one cycle with less ratio. Expression -plus_infinity must be well defined.</BLOCKQUOTE>
-
-OUT: std::vector<typename
-boost::graph_traits<TGraph>::edge_descriptor>* pcc
-<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>
There is no known precise upper bound for the time complexity of the
-algorithm. Imperical time complexity is O(E), where the
-constant tends to be pretty small. Space complexity is also O(E).
+algorithm. Imperical time complexity is O(|E|), where the constant tends to
+be pretty small (about 20-30). Space complexity is equal to 7*|V| plus the
+space required to store a graph.

+
<H3>Example</H3>
-The program in cycle_ratio_example.cpp
-generates random graph and computes its maximum cycle ratio.
+The program in cycle_ratio_example.cpp
+generates a random graph and computes its maximum cycle ratio.

+
<HR>
<TABLE CELLPADDING=2 CELLSPACING=2>
- <TR VALIGN=TOP>
- <TD>
- Copyright © 2000-2006
- </TD>
- <TD>
- <A HREF="http://www.lsi.upc.edu/~dmitry">Dmitry
- Bufistov</A>, Universitat Politecnica de Cataluña
- </TD>
- </TR>
+ <TR VALIGN=TOP>
+ <TD>
+ Copyright © 2006-2009
+ </TD>
+ <TD>
+ <A HREF="http://www.lsi.upc.edu/~dmitry">Dmitry
+ Bufistov</A>, Andrey Parfenov
+ </TD>
+ </TR>
</TABLE>
 
-
-</BODY>
-</HTML>
+</HTML>

Modified: branches/release/libs/graph/doc/read_graphml.html
==============================================================================
--- branches/release/libs/graph/doc/read_graphml.html (original)
+++ branches/release/libs/graph/doc/read_graphml.html 2009-08-08 14:19:53 EDT (Sat, 08 Aug 2009)
@@ -156,7 +156,7 @@
</div>
<div class="footer">
<hr class="footer" />
-Generated on: 2009-06-12 00:31 UTC.
+Generated on: 2009-06-12 00:41 UTC.
Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source.

</div>

Modified: branches/release/libs/graph/doc/read_graphviz.html
==============================================================================
--- branches/release/libs/graph/doc/read_graphviz.html (original)
+++ branches/release/libs/graph/doc/read_graphviz.html 2009-08-08 14:19:53 EDT (Sat, 08 Aug 2009)
@@ -231,7 +231,7 @@
</div>
<div class="footer">
<hr class="footer" />
-Generated on: 2009-06-12 00:31 UTC.
+Generated on: 2009-06-12 00:41 UTC.
Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source.

</div>

Modified: branches/release/libs/graph/doc/write-graphviz.html
==============================================================================
--- branches/release/libs/graph/doc/write-graphviz.html (original)
+++ branches/release/libs/graph/doc/write-graphviz.html 2009-08-08 14:19:53 EDT (Sat, 08 Aug 2009)
@@ -2,17 +2,17 @@


<Head>
<Title>Boost Graph Library: write graphviz</Title>
-<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
- ALINK="#ff0000">
-<IMG SRC="../../../boost.png"
- ALT="C++ Boost" width="277" height="86">
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">

 

@@ -23,42 +23,42 @@

<pre>
// Output graph structure without properties.
-template < typename VertexListGraph >
-void
-write_graphviz(std::ostream& out, const VertexListGraph& g);
+template < typename VertexAndEdgeListGraph >
+void
+write_graphviz(std::ostream& out, const VertexAndEdgeListGraph& g);

// Graph structure with customized property output
-template < typename VertexListGraph, typename VertexPropertyWriter >
-void
-write_graphviz(std::ostream& out, const VertexListGraph& g,
+template < typename VertexAndEdgeListGraph, typename VertexPropertyWriter >
+void
+write_graphviz(std::ostream& out, const VertexAndEdgeListGraph& g,
 VertexPropertyWriter vpw);

-template < typename VertexListGraph, typename VertexPropertyWriter,
+template < typename VertexAndEdgeListGraph, typename VertexPropertyWriter,
 typename EdgePropertyWriter >
void
-write_graphviz(std::ostream& out, const VertexListGraph& g,
+write_graphviz(std::ostream& out, const VertexAndEdgeListGraph& g,
 VertexPropertyWriter vpw, EdgePropertyWriter epw);

-template < typename VertexListGraph, typename VertexPropertyWriter,
+template < typename VertexAndEdgeListGraph, typename VertexPropertyWriter,
 typename EdgePropertyWriter, typename GraphPropertyWriter >
-void
-write_graphviz(std::ostream& out, const VertexListGraph& g,
- VertexPropertyWriter vpw, EdgePropertyWriter epw,
+void
+write_graphviz(std::ostream& out, const VertexAndEdgeListGraph& g,
+ VertexPropertyWriter vpw, EdgePropertyWriter epw,
 GraphPropertyWriter gpw);

-template < typename VertexListGraph, typename VertexPropertyWriter,
+template < typename VertexAndEdgeListGraph, typename VertexPropertyWriter,
 typename EdgePropertyWriter, typename GraphPropertyWriter,
 typename VertexID >
-void
-write_graphviz(std::ostream& out, const VertexListGraph& g,
- VertexPropertyWriter vpw, EdgePropertyWriter epw,
+void
+write_graphviz(std::ostream& out, const VertexAndEdgeListGraph& g,
+ VertexPropertyWriter vpw, EdgePropertyWriter epw,
 GraphPropertyWriter gpw, VertexID vertex_id);

// Graph structure with dynamic property output
template<typename Graph>
void
write_graphviz(std::ostream& out, const Graph& g,
- const dynamic_properties& dp,
+ const dynamic_properties& dp,
 const std::string& node_id = "node_id");

template<typename Graph, typename VertexID>
@@ -69,9 +69,9 @@
</pre>


-This is to write a BGL graph object into an output stream in graphviz
-dot format so that users can make use of AT&T graphviz to draw a
-picture with nice layout.
+This is to write a BGL graph object into an output stream in graphviz dot format
+so that users can make use of AT&T graphviz
+to draw a picture with nice layout.

The first version with two parameters will write the graph into a
<tt>std::ostream</tt> where each vertex is represented by its numerical vertex
@@ -121,7 +121,7 @@
Thus, users could easily extend the <tt>write_graphviz</tt> function
by creating their own PropertyWriter only.

-A PropertyWriter
+A PropertyWriter
for vertices or edges is a functor which can be called with two parameters:
<tt>std::ostream</tt> and either a vertex or an edge descriptor. It should output a
pair of brackets with a series of assigments "name=value" inside.
@@ -151,10 +151,10 @@
</pre>


-A PropertyWriter
-for graphs is a functor which is called with one parameter of type
+A PropertyWriter
+for graphs is a functor which is called with one parameter of type
<tt>std::ostream</tt> and should print a series of graph properties. The following
-code excerpt is an example of a PropertyWriter for a graph.
+code excerpt is an example of a PropertyWriter for a graph.
<pre>
 struct sample_graph_writer {
 void operator()(std::ostream& out) const {
@@ -176,28 +176,28 @@
 OUT: <tt>std::ostream& out</tt>
<blockquote>
 A standard <tt>std::ostream</tt> object.
-</blockquote>
+</blockquote>

- IN: <tt>VertexListGraph& g</tt>
+ IN: <tt>VertexAndEdgeListGraph& g</tt>
<blockquote>
- A directed or undirected graph. The graph's type must be a model of
- VertexListGraph. Also the graph
- must have an internal <tt>vertex_index</tt> property map.
-</blockquote>
+ A directed or undirected graph. The graph's type must be a model of
+ VertexAndEdgeListGraph. Also the
+ graph must have an internal <tt>vertex_index</tt> property map.
+</blockquote>

 IN: <tt>VertexPropertyWriter vpw</tt>
<blockquote>
 A functor that models PropertyWriter concept to print
 properties of a vertex. 
Default: <tt>default_writer()</tt>
-</blockquote>
+</blockquote>

 IN: <tt>EdgePropertyWriter epw</tt>
<blockquote>
 A functor that models PropertyWriter concept to print
 properties of an edge. 
Default: <tt>default_writer()</tt>
-</blockquote>
+</blockquote>

 IN: <tt>GraphPropertyWriter epw</tt>
<blockquote>
@@ -228,15 +228,15 @@
Example
</H3>

-This example demonstrates using BGL-graphviz interface to write
+This example demonstrates using BGL-graphviz interface to write
a BGL graph into a graphviz format file.

<pre>
#include <boost/graph/graphviz.hpp>

-enum files_e { dax_h, yow_h, boz_h, zow_h, foo_cpp,
+enum files_e { dax_h, yow_h, boz_h, zow_h, foo_cpp,
 foo_o, bar_cpp, bar_o, libfoobar_a,
- zig_cpp, zig_o, zag_cpp, zag_o,
+ zig_cpp, zig_o, zag_cpp, zag_o,
 libzigzag_a, killerapp, N };
const char* name[] = { "dax.h", "yow.h", "boz.h", "zow.h", "foo.cpp",
 "foo.o", "bar.cpp", "bar.o", "libfoobar.a",
@@ -245,13 +245,13 @@

int main(int,char*[])
{
-
+
 typedef pair<int,int> Edge;
 Edge used_by[] = {
 Edge(dax_h, foo_cpp), Edge(dax_h, bar_cpp), Edge(dax_h, yow_h),
 Edge(yow_h, bar_cpp), Edge(yow_h, zag_cpp),
 Edge(boz_h, bar_cpp), Edge(boz_h, zig_cpp), Edge(boz_h, zag_cpp),
- Edge(zow_h, foo_cpp),
+ Edge(zow_h, foo_cpp),
 Edge(foo_cpp, foo_o),
 Edge(foo_o, libfoobar_a),
 Edge(bar_cpp, bar_o),
@@ -269,7 +269,7 @@

 using namespace boost;

- typedef adjacency_list< vecS, vecS, directedS,
+ typedef adjacency_list< vecS, vecS, directedS,
 property< vertex_color_t, default_color_type >,
 property< edge_weight_t, int >
> Graph;
@@ -343,4 +343,4 @@
</TD></TR></TABLE>

</BODY>
-</HTML>
+</HTML>

Modified: branches/release/libs/graph/doc/write_graphml.html
==============================================================================
--- branches/release/libs/graph/doc/write_graphml.html (original)
+++ branches/release/libs/graph/doc/write_graphml.html 2009-08-08 14:19:53 EDT (Sat, 08 Aug 2009)
@@ -259,7 +259,7 @@
</div>
<div class="footer">
<hr class="footer" />
-Generated on: 2009-06-12 00:31 UTC.
+Generated on: 2009-06-12 00:41 UTC.
Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source.

</div>

Modified: branches/release/libs/graph/example/cycle_ratio_example.cpp
==============================================================================
--- branches/release/libs/graph/example/cycle_ratio_example.cpp (original)
+++ branches/release/libs/graph/example/cycle_ratio_example.cpp 2009-08-08 14:19:53 EDT (Sat, 08 Aug 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: branches/release/libs/graph/test/cycle_ratio_tests.cpp
==============================================================================
--- branches/release/libs/graph/test/cycle_ratio_tests.cpp (original)
+++ branches/release/libs/graph/test/cycle_ratio_tests.cpp 2009-08-08 14:19:53 EDT (Sat, 08 Aug 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,264 @@
* 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];
+ assert (argc >= 2);
+ 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(argv[1], 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;
}

Modified: branches/release/libs/graph/test/metis_test.cpp
==============================================================================
--- branches/release/libs/graph/test/metis_test.cpp (original)
+++ branches/release/libs/graph/test/metis_test.cpp 2009-08-08 14:19:53 EDT (Sat, 08 Aug 2009)
@@ -33,6 +33,7 @@

   // Open the METIS input file
   std::ifstream in(filename);
+ assert (in.good());
   graph::metis_reader reader(in);

   // Load the graph using the default distribution

Modified: branches/release/libs/maintainers.txt
==============================================================================
--- branches/release/libs/maintainers.txt (original)
+++ branches/release/libs/maintainers.txt 2009-08-08 14:19:53 EDT (Sat, 08 Aug 2009)
@@ -37,7 +37,7 @@
fusion Joel de Guzman <joel -at- boost-consulting.com>, Dan Marsden <danmarsden -at- yahoo.co.uk>, Tobias Schwinger <tschwinger -at- isonews2.com>
function_types Tobias Schwinger <tschwinger -at- isonews2.com>
gil Lubomir Bourdev <lbourdev -at- adobe.com>, Hailin Jin <hljin -at- adobe.com>
-graph Douglas Gregor <dgregor -at- cs.indiana.edu>
+graph Andrew Sutton <asutton -at- cs.kent.edu>
integer Daryle Walker <darylew -at- hotmail.com>
interprocess Ion Gaztanaga <igaztanaga -at- gmail.com>
intrusive Ion Gaztanaga <igaztanaga -at- gmail.com>

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk