boost::probabilities Namespace Reference

Probability and likelihood quantities. More...

Classes
class	likelihood
	Likelihood quantity. More...
class	out_of_range
	Exception to indicate a runtime value failure. More...
struct	linear_domain
	Linear domain of operations. More...
struct	log_domain
	Log domain of operations. More...
struct	ValidatorConcept
	Validator Concept checking class. More...
class	validator_archetype
	Validator Concept archetype. More...
struct	likelihood_tag
struct	probability_tag
struct	domain_traits
	Domain-specific traits for likelihoods and probabilities. More...
struct	domain_traits< Type, linear_domain, Value >
struct	domain_traits< Type, log_domain, Value >
struct	null_validator
	Null validator. More...
struct	range_validator
	Range-enforcing validator. More...
class	truncating_validator
	Truncating validator. More...
class	probability
	Probability quantity. More...
template<typename TargetDomain, typename SourceDomain, typename Value, typename Validator>
likelihood< TargetDomain, Value, Validator >	domain_cast (const likelihood< SourceDomain, Value, Validator > &l)
	Cast domain of operations.
template<typename TargetDomain, typename SourceDomain, typename Value, typename Validator>
likelihood< TargetDomain, Value, Validator >::value_type	value_cast (const likelihood< SourceDomain, Value, Validator > &l)
	Cast the value of a likelihood.
template<typename Ldomain, typename Lvalue, typename Lvalidator, typename Rdomain, typename Rvalue, typename Rvalidator>
likelihood< Ldomain, Lvalue, Lvalidator >	operator+ (const likelihood< Ldomain, Lvalue, Lvalidator > &lhs, const likelihood< Rdomain, Rvalue, Rvalidator > &rhs)
	Addition of likelihoods.
template<typename Ldomain, typename Lvalue, typename Lvalidator, typename Rdomain, typename Rvalue, typename Rvalidator>
likelihood< Ldomain, Lvalue, Lvalidator >	operator+ (const likelihood< Ldomain, Lvalue, Lvalidator > &lhs, const probability< Rdomain, Rvalue, Rvalidator > &rhs)
	Mixed addition of a likelihood and a probability.
template<typename Ldomain, typename Lvalue, typename Lvalidator, typename Rdomain, typename Rvalue, typename Rvalidator>
likelihood< Ldomain, Lvalue, Lvalidator >	operator+ (const probability< Ldomain, Lvalue, Lvalidator > &lhs, const likelihood< Rdomain, Rvalue, Rvalidator > &rhs)
	Mixed addition of a probability and a likelihood.
template<typename Ldomain, typename Lvalue, typename Lvalidator, typename Rdomain, typename Rvalue, typename Rvalidator>
likelihood< Ldomain, Lvalue, Lvalidator >	operator- (const likelihood< Ldomain, Lvalue, Lvalidator > &lhs, const likelihood< Rdomain, Rvalue, Rvalidator > &rhs)
	Subtraction of likelihoods.
template<typename Ldomain, typename Lvalue, typename Lvalidator, typename Rdomain, typename Rvalue, typename Rvalidator>
likelihood< log_domain, Lvalue, Lvalidator >	operator * (const likelihood< Ldomain, Lvalue, Lvalidator > &lhs, const likelihood< Rdomain, Rvalue, Rvalidator > &rhs)
	Multiplication of likelihoods.
template<typename Ldomain, typename Lvalue, typename Lvalidator, typename Rdomain, typename Rvalue, typename Rvalidator>
likelihood< log_domain, Lvalue, Lvalidator >	operator * (const likelihood< Ldomain, Lvalue, Lvalidator > &lhs, const probability< Rdomain, Rvalue, Rvalidator > &rhs)
	Mixed multiplication of a likelihood and a probability.
template<typename Ldomain, typename Lvalue, typename Lvalidator, typename Rdomain, typename Rvalue, typename Rvalidator>
likelihood< log_domain, Lvalue, Lvalidator >	operator * (const probability< Ldomain, Lvalue, Lvalidator > &lhs, const likelihood< Rdomain, Rvalue, Rvalidator > &rhs)
	Mixed multiplication of a probability and a likelihood.
template<typename Ldomain, typename Lvalue, typename Lvalidator, typename Rdomain, typename Rvalue, typename Rvalidator>
likelihood< log_domain, Lvalue, Lvalidator >	operator/ (const likelihood< Ldomain, Lvalue, Lvalidator > &lhs, const likelihood< Rdomain, Rvalue, Rvalidator > &rhs)
	Division of likelihoods.
template<typename Domain, typename Value, typename Validator, typename Integer>
likelihood< Domain, Value, Validator >	pow (const likelihood< Domain, Value, Validator > &base, Integer n)
	Power function of likelihoods.
template<typename TargetDomain, typename SourceDomain, typename Value, typename Validator>
probability< TargetDomain, Value, Validator >	domain_cast (const probability< SourceDomain, Value, Validator > &p)
	Cast domain of operations.
template<typename TargetDomain, typename SourceDomain, typename Value, typename Validator>
probability< TargetDomain, Value, Validator >::value_type	value_cast (const probability< SourceDomain, Value, Validator > &p)
	Cast the value of a probability.
template<typename Ldomain, typename Lvalue, typename Lvalidator, typename Rdomain, typename Rvalue, typename Rvalidator>
probability< Ldomain, Lvalue, Lvalidator >	operator+ (const probability< Ldomain, Lvalue, Lvalidator > &lhs, const probability< Rdomain, Rvalue, Rvalidator > &rhs)
	Addition of probabilities.
template<typename Ldomain, typename Lvalue, typename Lvalidator, typename Rdomain, typename Rvalue, typename Rvalidator>
probability< Ldomain, Lvalue, Lvalidator >	operator- (const probability< Ldomain, Lvalue, Lvalidator > &lhs, const probability< Rdomain, Rvalue, Rvalidator > &rhs)
	Subtraction of probabilities.
template<typename Ldomain, typename Lvalue, typename Lvalidator, typename Rdomain, typename Rvalue, typename Rvalidator>
probability< log_domain, Lvalue, Lvalidator >	operator * (const probability< Ldomain, Lvalue, Lvalidator > &lhs, const probability< Rdomain, Rvalue, Rvalidator > &rhs)
	Multiplication of probabilities.
template<typename Ldomain, typename Lvalue, typename Lvalidator, typename Rdomain, typename Rvalue, typename Rvalidator>
probability< log_domain, Lvalue, Lvalidator >	operator/ (const probability< Ldomain, Lvalue, Lvalidator > &lhs, const probability< Rdomain, Rvalue, Rvalidator > &rhs)
	Division of probabilities.
template<typename Domain, typename Value, typename Validator, typename Integer>
probability< Domain, Value, Validator >	pow (const probability< Domain, Value, Validator > &base, Integer n)
	Power function of probabilities.
Functions
template<typename VertexListGraph, typename WeightMap, typename DistanceMap, typename PredecessorMap, typename ColorMap, typename IndexMap>
void	most_likely_paths (const VertexListGraph &g, typename graph_traits< VertexListGraph >::vertex_descriptor s, WeightMap weight, DistanceMap distance, PredecessorMap pred, ColorMap color, IndexMap id)
	Most likely paths algorithm.
template<typename VertexListGraph, typename Param, typename Tag, typename Rest>
void	most_likely_paths (const VertexListGraph &g, typename graph_traits< VertexListGraph >::vertex_descriptor s, const bgl_named_params< Param, Tag, Rest > &params)
	Most likely paths graph algorithm.

---

Detailed Description

Probability and likelihood quantities.

In some applications, the logarithm of the probability is more convenient than the original probability, because the values are less subject to overflow. Unfortunately, all useful mathematical operations on probabilitys cannot be performed with logarithms; for example, addition of two probabilities cannot. Consequently, practical probability calculations involve transformations back and forth between the linear (i.e., probability) space and the log (i.e., ) space. The purpose of this namespace is to encapsulate these operations within a set of appropriate types.

---

Function Documentation

template<typename VertexListGraph, typename Param, typename Tag, typename Rest> void boost::probabilities::most_likely_paths (  const VertexListGraph &  g, typename graph_traits< VertexListGraph >::vertex_descriptor  s, const bgl_named_params< Param, Tag, Rest > &  params )  [inline]

Most likely paths graph algorithm. Parameters: g  Directed acyclic vertex list graph. s  Source vertex. params  Named parameters. This algorithm identifies the most likely paths originating from a specific vertex and traversing through a directed acyclic graph. The set of named parameters may include any of the following. IN: weight_map(WeightMap w_map) The weight or ``length'' of each edge in the graph. The type WeightMap must be a model of Readable Property Map. The edge descriptor type of the graph needs to be usable as the key type for the weight map. The value type for the map must be Multiplyable with the value type of the distance map. Because quantities are combined multiplicatively along each path, edge weights must represent conditional probabilities or conditional likelihoods. Default: get(edge_weight,g) UTIL/OUT: distance_map(DistanceMap d_map) The most likely path weight from the source vertex s to each vertex in the graph g is recorded in this property map. The most likely path weight is the product of the edge weights along the most likely path. The type DistanceMap must be a model of Read/Write Property Map. The vertex descriptor type of the graph needs to be usable as the key type of the distance map. The value type of the distance map must be constructible from a boost::probabilities::probability. Default: iterator_property_map created from a std::vector of the WeightMap's value type of size num_vertices(g) and using the i_map for the index map. OUT: predecessor_map(PredecessorMap p_map) The predecessor map records the edges in the minimum spanning tree representing the most likely paths emanating from the source vertex s. Upon completion of the algorithm, the edges (p[u],u) for all u in V are in the minimum spanning tree. If p[u] = u then u is either the source vertex or a vertex that is not reachable from the source. The PredecessorMap type must be a Read/Write Property Map with key and vertex types the same as the vertex descriptor type of the graph. Default: as implemented by dag_shortest_paths(). UTIL/OUT: color_map(ColorMap c_map) This is used during the execution of the algorithm to mark the vertices. The vertices start out white and become gray when they are inserted in the queue. They then turn black when they are removed from the queue. At the end of the algorithm, vertices reachable from the source vertex will have been colored black. All other vertices will still be white. The type ColorMap must be a model of Read/Write Property Map. A vertex descriptor must be usable as the key type of the map, and the value type of the map must be a model of Color Value. Default: as implemented by dag_shortest_paths(). IN: vertex_index_map(VertexIndexMap i_map) This maps each vertex to an integer in the range [0, num_vertices(g)). This is necessary for efficient updates of the heap data structure when an edge is relaxed. The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map. Default: get(vertex_index,g). Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacenty_list with VertexList=listS does not have an internal vertex_index property. The most likely paths algorithm is implemented in terms of the DAG shortest paths algorithm, dag_shortest_paths(), provided by the Boost Graph Library.

---