Calculates optimum (maximum/minimum) cycle ratio of a directed graph. More...
#include <howard_cycle_ratio.hpp>
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 &) |
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).
typedef boost::iterator_property_map< std::vector<int>::iterator, VertexIndexMap > boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::badv_t |
typedef FloatTraits::comparator_props_t boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::cmp_props_t |
typedef ::boost::iterator_property_map< typename vcol_t::iterator, VertexIndexMap > boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::color_map_t |
typedef FloatTraits::comparator boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::comparator_t |
typedef std::vector<edge_t> boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::critical_cycle_t |
typedef boost::iterator_property_map< typename vp_t::iterator, VertexIndexMap > boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::distance_map_t |
typedef graph_traits<Graph>::edge_descriptor boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::edge_t |
typedef FloatTraits::value_type boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::float_t |
typedef std::vector<pinel_t> boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::inedges1_t |
typedef ::boost::iterator_property_map< typename inedges1_t::iterator, VertexIndexMap > boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::inedges_t |
typedef std::list<vertex_t> boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::pinel_t |
typedef ::boost::iterator_property_map< typename ve_t::iterator, VertexIndexMap > boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::policy_t |
typedef std::vector<my_color_type> boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::vcol_t |
typedef std::vector<edge_t> boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::ve_t |
typedef graph_traits<Graph>::vertex_descriptor boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::vertex_t |
typedef graph_traits<Graph>::vertices_size_type boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::vn_t |
typedef std::vector<float_t> boost::detail::mcr_howard< FloatTraits, Graph, VertexIndexMap, EdgeWeight1, EdgeWeight2 >::vp_t |
enum boost::detail::mcr_howard::my_color_type |
|
inline |
Constructor.
g | = (V, E) - a directed multigraph. |
vim | Vertex Index Map. Read property Map: V -> [0, num_vertices(g)). |
ewm | edge weight map. Read property map: E -> R |
ew2m | edge weight map. Read property map: E -> R+ |
infty | A big enough value to guaranty that there exist a cycle with better ratio. |
cmp | The compare operator for float_ts. |
|
inlinevirtual |
|
inline |
Referenced by boost::detail::optimum_cycle_ratio().
|
inlineprotectedvirtual |
|
inlineprotectedvirtual |