most_likely_paths.hpp

Go to the documentation of this file.

/*
 * $Id: most_likely_paths.hpp,v 1.3 2007/10/18 02:24:24 brook Exp $
 */

/*
 * Copyright (c) 2007 Brook Milligan.
 * Distributed under 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_MOST_LIKELY_PATHS_HPP
#define BOOST_MOST_LIKELY_PATHS_HPP

#include <boost/probability.hpp>
#include <boost/graph/dag_shortest_paths.hpp>

namespace boost
{

  namespace probabilities
  {

    namespace detail
    {

      template <typename T, typename U>
      struct mpy
      {
        T operator () (const T& a, const U& b) const { return a * b; }
      };

    } // namespace detail

    template <typename VertexListGraph, typename WeightMap,
              typename DistanceMap, typename PredecessorMap, typename ColorMap,
              typename IndexMap>
    inline void
    most_likely_paths
    (const VertexListGraph& g,
     typename graph_traits<VertexListGraph>::vertex_descriptor s,
     WeightMap weight, DistanceMap distance, PredecessorMap pred,
     ColorMap color, IndexMap id)
    {
      // XXX - assert that the graph is directed...

      typedef typename boost::property_traits<DistanceMap>::value_type
        distance_type;
      typedef typename boost::property_traits<WeightMap>::value_type
        weight_type;

      typedef std::greater<distance_type> compare_type;
      typedef detail::mpy<distance_type,weight_type> combine_type;

      distance_type identity
        (probability<linear_domain,typename distance_type::value_type>(1));
      distance_type infinity
        (probability<linear_domain,typename distance_type::value_type>(0));

      boost::dag_shortest_paths
        (g, s, weight_map(weight).distance_map(distance)
         .predecessor_map(pred).color_map(color)
         .distance_compare(compare_type()).distance_combine(combine_type())
         .distance_zero(identity).distance_inf(infinity).vertex_index_map(id)
         );
    }

    namespace detail
    {

      template <typename VertexListGraph,
                typename WeightMap, typename DistanceMap, typename IndexMap,
                typename Param, typename Tag, typename Rest>
      inline void
      dispatch
      (const VertexListGraph& g,
       typename graph_traits<VertexListGraph>::vertex_descriptor s,
       WeightMap weight, DistanceMap distance, IndexMap id,
       const bgl_named_params<Param,Tag,Rest>& params)
      {
        typedef typename property_traits<WeightMap>::value_type T;
        typename std::vector<T>::size_type n;
        n = is_default_param(distance) ? num_vertices(g) : 1;
        std::vector<T> distance_map(n);

        most_likely_paths
          (g, s,
           choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
           choose_param(distance, make_iterator_property_map
                        (distance_map.begin(), id, distance_map[0])),
           get_param(params, vertex_predecessor),
           get_param(params, vertex_color),
           id
           );
      }

    } // namespace detail

    template <typename VertexListGraph,
              typename Param, typename Tag, typename Rest>
    inline void
    most_likely_paths
    (const VertexListGraph& g,
     typename graph_traits<VertexListGraph>::vertex_descriptor s,
     const bgl_named_params<Param,Tag,Rest>& params)
    {
      detail::dispatch
        (g, s,
         choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
         get_param(params, vertex_distance),
         choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
         params);
    }

  } // namespace probabilities

} // namespace boost

#endif

---