/*
 * $Id: example0c.cpp,v 1.1 2007/09/16 02:50:36 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)
 */

/*
 * The purpose of this example is to illustrate a typical generic
 * algorithm and its use to solve a general and commonly encountered
 * problem: finding the most likely paths through a graph.  It was
 * created as an example for the library documentation, and included
 * here to ensure that it compiles correctly.  Note that the actual
 * structure of the graph used here is meaningless; its relevance is
 * simply to provide a graph for the generic algorithm to traverse.
 *
 * The expected output follows.
 *
 * source vertex:  s
 * destination predecessor
 *      vertex      vertex  likelihood
 *           r           r           0
 *           s           s           1
 *           t           s         0.2
 *           u           s         0.6
 *           v           t        0.08
 *           x           u         0.6
 *
 * Thus, for example, the most likely path from node 's' to node 'x'
 * has a likelihood of 0.6 and is s -> u -> x.  Notice that node 'r'
 * is inaccessible from node 's', as indicated by the likelihood of
 * zero (0) and the fact that it is its own predecessor vertex.
 */

#include <iomanip>
#include <iostream>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/likelihood.hpp>
#include <boost/most_likely_paths.hpp>

/*
 * Note: the following types define the representation for vertex
 * distances and for edge weights in the graph.  Any meaningful
 * combination of probability and likelihood types, in either the
 * linear or log domains, may be used instead of the choices below and
 * the results will remain unchanged.  This illustrates the generic
 * nature of the most_likely_paths algorithm defined above.
 */
typedef boost::log_likelihood distance_type;
typedef boost::probability weight_type;

struct vertex_type
{
  typedef boost::adjacency_list_traits<boost::vecS, boost::vecS,
				       boost::directedS>::vertex_descriptor
  vertex_descriptor;
  std::string name;
  distance_type d;
  vertex_descriptor predecessor;
};

struct edge_type
{
  typedef boost::probabilities::linear_domain linear_domain;
  edge_type () : weight() { }
  template <typename T>
  edge_type (T w)
    : weight(boost::probabilities::probability<linear_domain,T>(w)) { }
  weight_type weight;
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
			      vertex_type, edge_type> graph_type;

static graph_type graph_factory ();
static std::ostream& operator << (std::ostream&, const distance_type&);

int
main ()
{
  graph_type g (graph_factory());
  graph_type::vertex_descriptor source (1);

  boost::probabilities::most_likely_paths
    (g, source,
     weight_map(get(&edge_type::weight,g)).distance_map(get(&vertex_type::d,g))
     .predecessor_map(get(&vertex_type::predecessor,g))
     );

  const int w (12);
  std::cout << "source vertex:  " << g[source].name << std::endl;
  std::cout << std::setw(w) << "destination"
	    << std::setw(w) << "predecessor" << std::endl;
  std::cout << std::setw(w) << "vertex"
	    << std::setw(w) << "vertex"
	    << std::setw(w) << "likelihood" << std::endl;

  boost::graph_traits<graph_type>::vertex_iterator vi , vi_end;
  for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
    std::cout << std::setw(w) << g[*vi].name
	      << std::setw(w) << g[g[*vi].predecessor].name
	      << std::setw(w) << g[*vi].d << std::endl;

  return 0;
}

// construct a graph
graph_type
graph_factory ()
{
  graph_type g(6);
  enum verts { r, s, t, u, v, x };
  add_edge(r, s, edge_type(0.5), g);
  add_edge(r, t, edge_type(0.3), g);
  add_edge(s, t, edge_type(0.2), g);
  add_edge(s, u, edge_type(0.6), g);
  add_edge(t, u, edge_type(0.7), g);
  add_edge(t, v, edge_type(0.4), g);
  add_edge(t, x, edge_type(1), g);
  add_edge(u, v, edge_type(0.1), g);
  add_edge(u, x, edge_type(1), g);
  add_edge(v, x, edge_type(0.1), g);
  g[r].name = "r";
  g[s].name = "s";
  g[t].name = "t";
  g[u].name = "u";
  g[v].name = "v";
  g[x].name = "x";

  return g;
}

// output the distance type in the linear domain
std::ostream&
operator << (std::ostream& s, const distance_type& d)
{
  typedef boost::probabilities::linear_domain linear_domain;
  return s << boost::probabilities::value_cast<linear_domain>(d);
}