Boost  v1.57.0
doxygen for www.boost.org
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
Public Types | Public Member Functions | Protected Member Functions | List of all members
boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 > Class Template Reference

Calculates optimum (maximum/minimum) cycle ratio of a directed graph. More...

#include <howard_cycle_ratio.hpp>

Inheritance diagram for boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >:
Inheritance graph
[legend]

Public Types

enum  my_color_type {
  my_white = 0,
  my_black
}
 
typedef FloatTraits::value_type float_t
 
typedef
FloatTraits::comparator_props_t 		cmp_props_t
 
typedef FloatTraits::comparator comparator_t
 
typedef graph_traits< Graph >
::vertex_descriptor 		vertex_t
 
typedef graph_traits< Graph >
::edge_descriptor 		edge_t
 
typedef graph_traits< Graph >
::vertices_size_type 		vn_t
 
typedef std::vector< float_t > vp_t
 
typedef
boost::iterator_property_map
< typename vp_t::iterator,
VertexIndexMap > 		distance_map_t
 
typedef std::vector< edge_t > ve_t
 
typedef std::vector
< my_color_type > 		vcol_t
 
typedef
::boost::iterator_property_map
< typename ve_t::iterator,
VertexIndexMap > 		policy_t
 
typedef
::boost::iterator_property_map
< typename vcol_t::iterator,
VertexIndexMap > 		color_map_t
 
typedef std::list< vertex_t > pinel_t
 
typedef std::vector< pinel_t > inedges1_t
 
typedef
::boost::iterator_property_map
< typename
inedges1_t::iterator,
VertexIndexMap > 		inedges_t
 
typedef std::vector< edge_t > critical_cycle_t
 
typedef
boost::iterator_property_map
< std::vector< int >::iterator,
VertexIndexMap > 		badv_t
 

Public Member Functions

 mcr_howard (const Graph &g, VertexIndexMap vim, EdgeWeight1 ewm, EdgeWeight2 ew2m)
 Constructor. More...
 
float_t ocr_howard ()
 
virtual ~mcr_howard ()
 

Protected Member Functions

virtual void store_critical_edge (edge_t, critical_cycle_t &)
 
virtual void store_critical_cycle (critical_cycle_t &)
 

Detailed Description

template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
class boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >

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).

Member Typedef Documentation

template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef boost::iterator_property_map< std::vector<int>::iterator, VertexIndexMap > boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::badv_t
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef FloatTraits::comparator_props_t boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::cmp_props_t
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef ::boost::iterator_property_map< typename vcol_t::iterator, VertexIndexMap > boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::color_map_t
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef FloatTraits::comparator boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::comparator_t
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef std::vector<edge_t> boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::critical_cycle_t
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef boost::iterator_property_map< typename vp_t::iterator, VertexIndexMap > boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::distance_map_t
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef graph_traits<Graph>::edge_descriptor boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::edge_t
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef FloatTraits::value_type boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::float_t
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef std::vector<pinel_t> boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::inedges1_t
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef ::boost::iterator_property_map< typename inedges1_t::iterator, VertexIndexMap > boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::inedges_t
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef std::list<vertex_t> boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::pinel_t
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef ::boost::iterator_property_map< typename ve_t::iterator, VertexIndexMap > boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::policy_t
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef std::vector<my_color_type> boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::vcol_t
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef std::vector<edge_t> boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::ve_t
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef graph_traits<Graph>::vertex_descriptor boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::vertex_t
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef graph_traits<Graph>::vertices_size_type boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::vn_t
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
typedef std::vector<float_t> boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::vp_t

Member Enumeration Documentation

template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
enum boost::detail::mcr_howard::my_color_type
Enumerator
my_white 
my_black 

Constructor & Destructor Documentation

template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::mcr_howard ( const Graph &  g,
VertexIndexMap  vim,
EdgeWeight1  ewm,
EdgeWeight2  ew2m 
)
inline

Constructor.

Parameters
g= (V, E) - a directed multigraph.
vimVertex Index Map. Read property Map: V -> [0, num_vertices(g)).
ewmedge weight map. Read property map: E -> R
ew2medge weight map. Read property map: E -> R+
inftyA big enough value to guaranty that there exist a cycle with better ratio.
cmpThe compare operator for float_ts.
template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
virtual boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::~mcr_howard ( )
inlinevirtual

Member Function Documentation

template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
float_t boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::ocr_howard ( )
inline
Returns
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.

Referenced by boost::detail::optimum_cycle_ratio().

template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
virtual void boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::store_critical_cycle ( critical_cycle_t &  )
inlineprotectedvirtual

Reimplemented in boost::detail::mcr_howard1< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >.

template<typename FloatTraits, typename Graph, typename VertexIndexMap, typename EdgeWeight1, typename EdgeWeight2>
virtual void boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::store_critical_edge ( edge_t  ,
critical_cycle_t &   
)
inlineprotectedvirtual

Reimplemented in boost::detail::mcr_howard1< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >.

The documentation for this class was generated from the following file: