/* boost/graph/loop_erased_random_paths.hpp header file
 *
 * Copyright 2004 Cromwell D. Enage.  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_GRAPH_LOOP_ERASED_RANDOM_PATHS_HPP
#define BOOST_GRAPH_LOOP_ERASED_RANDOM_PATHS_HPP

/*
 * Defines the std::vector class template.
 */
#include <vector>

/*
 * Defines the boost::bind function template.
 */
#include <boost/bind.hpp>

/*
 * Defines the boost::function_requires function template and the basic concept
 * check templates.
 */
#include <boost/concept_check.hpp>

/*
 * Defines the boost::property_traits class template and the boost::get and
 * boost::put function templates.
 */
#include <boost/property_map.hpp>

/*
 * Defines the boost::tie function template.
 */
#include <boost/utility.hpp>

/*
 * Defines the BGL concept check templates.
 */
#include <boost/graph/graph_concepts.hpp>

/*
 * Defines the boost::graph_traits class template and the directed category
 * tags.
 */
#include <boost/graph/graph_traits.hpp>

/*
 * Defines the boost::vertex_index_t property tag.
 */
#include <boost/graph/properties.hpp>

/*
 * The graph type and its associated non-member function templates must be
 * defined externally.
 */
//#include <boost/graph/adjacency_list.hpp>

/*
 * Defines the boost::uniform_int class template, to be used as a random-index
 * distribution.
 */
#include <boost/random/uniform_int.hpp>

/*
 * Defines the boost::variate_generator class template, to be used as the
 * front-end random index generator.
 */
#include <boost/random/variate_generator.hpp>

/*
 * Defines the keyword structs to be used in boost::keyword.
 */
#include <boost/graph/named_function_params.hpp>

/*
 * Defines the Boost.NamedParams library components.
 */
#include <boost/named_params.hpp>

namespace boost {
 namespace graph {
  namespace loop_erased_random_paths_ {

    /*
     * The generic RandomSuccessor() function.
     */
    template <
      typename InputGraph
    , typename RandomIndexGenerator
    , typename InputIndexMap
    , typename UtilGraph
    , typename UtilIndexMap
    , typename UtilColorMap
    >
    typename graph_traits<InputGraph>::vertex_descriptor get_random_predecessor(
      typename graph_traits<InputGraph>::vertex_descriptor v
    , InputGraph& in_g
    , RandomIndexGenerator& rig
    , InputIndexMap in_index_map
    , UtilGraph& u_g
    , UtilIndexMap u_index_map
    , UtilColorMap u_color_map
    )
    {
        typedef typename property_traits<UtilColorMap>::value_type
                UtilColorValue;
        typedef color_traits<UtilColorValue>
                UtilColor;

        std::vector<typename graph_traits<UtilGraph>::vertex_descriptor>
          prev;
        typename graph_traits<UtilGraph>::vertex_descriptor
          u = vertex(get(in_index_map, v), u_g);
        typename graph_traits<UtilGraph>::adjacency_iterator
          ai, aend;

        for (tie(ai, aend) = adjacent_vertices(u, u_g); ai != aend; ++ai)
        {
            if (get(u_color_map, *ai) == UtilColor::white())
            {
                prev.push_back(*ai);
            }
        }

        if (prev.empty())
        {
            return v;
        }

        return vertex(get(u_index_map, prev[rig(prev.size())]), in_g);
    }

    /*
     * The implementation.
     */
    template <
      typename InputGraph
    , typename RandomIndexGenerator
    , typename OutputPredecessorMap
    , typename InputIndexMap
    , typename InputColorMap
    , typename UtilGraph
    , typename UtilIndexMap
    , typename UtilColorMap
    >
    bool impl(
      InputGraph& in_g
    , typename graph_traits<InputGraph>::vertex_descriptor source
    , RandomIndexGenerator& rig
    , OutputPredecessorMap out_pred_map
    , InputIndexMap in_index_map
    , InputColorMap in_color_map
    , UtilGraph& u_g
    , UtilIndexMap u_index_map
    , UtilColorMap u_color_map
    )
    {
        function_requires<
          VertexListGraphConcept<InputGraph>
        >();
        function_requires<
          AdjacencyGraphConcept<InputGraph>
        >();
        typedef graph_traits<InputGraph>
                InputGraphTraits;
        typedef typename InputGraphTraits::vertex_descriptor
                InputVertex;
        function_requires<
          ReadWritePropertyMapConcept<OutputPredecessorMap,InputVertex>
        >();
        function_requires<
          ReadablePropertyMapConcept<InputIndexMap,InputVertex>
        >();
        function_requires<
          ReadWritePropertyMapConcept<InputColorMap,InputVertex>
        >();
        typedef typename property_traits<InputColorMap>::value_type
                InputColorValue;
        typedef color_traits<InputColorValue>
                InputColor;
        function_requires<
          VertexListGraphConcept<UtilGraph>
        >();
        function_requires<
          AdjacencyGraphConcept<UtilGraph>
        >();
        function_requires<
          EdgeMutableGraphConcept<UtilGraph>
        >();
        typedef graph_traits<UtilGraph>
                UtilGraphTraits;
        typedef typename UtilGraphTraits::vertex_descriptor
                UtilVertex;
        function_requires<
          ReadablePropertyMapConcept<UtilIndexMap,UtilVertex>
        >();
        function_requires<
          ReadWritePropertyMapConcept<UtilColorMap,UtilVertex>
        >();
        typedef typename property_traits<UtilColorMap>::value_type
                UtilColorValue;
        typedef color_traits<UtilColorValue>
                UtilColor;

        typename InputGraphTraits::vertex_iterator vi, vend;
        typename InputGraphTraits::adjacency_iterator ai, aend;
        UtilVertex w;

        for (tie(vi, vend) = vertices(in_g); vi != vend; ++vi)
        {
            put(out_pred_map, *vi, *vi);
            put(in_color_map, *vi, InputColor::white());
            w = vertex(get(in_index_map, *vi), u_g);

            for (tie(ai, aend) = adjacent_vertices(*vi, in_g); ai != aend; ++ai)
            {
                add_edge(vertex(get(in_index_map, *ai), u_g), w, u_g);
            }
        }

        put(in_color_map, source, InputColor::black());

        InputVertex u, v;
        typename UtilGraphTraits::vertex_iterator ui, uend;
        bool is_tree = true;

        for (tie(vi, vend) = vertices(in_g); vi != vend; ++vi)
        {
            for (tie(ui, uend) = vertices(u_g); ui != uend; ++ui)
            {
                put(u_color_map, *ui, UtilColor::white());
            }

            for (v = *vi; get(in_color_map, v) == InputColor::white(); v = u)
            {
                put(u_color_map, get(in_index_map, v), UtilColor::black());
                u = get_random_predecessor(
                      v
                    , in_g
                    , rig
                    , in_index_map
                    , u_g
                    , u_index_map
                    , u_color_map
                    );

                if (u == v)
                {
                    is_tree = false;
                }

                put(out_pred_map, v, u);
                put(in_color_map, v, InputColor::black());
            }
        }

        for (tie(ui, uend) = vertices(u_g); ui != uend; ++ui)
        {
            clear_vertex(*ui, u_g);
        }

        return is_tree;
    }

    struct input_graph_t;
    struct source_vertex_t;
    struct random_index_generator_t;
    struct output_predecessor_map_t;
    struct input_index_map_t;
    struct input_color_map_t;
    struct util_graph_t;
    struct util_index_map_t;
    struct util_color_map_t;

    struct keywords_t
      : keywords<
          input_graph_t
        , source_vertex_t
        , random_index_generator_t
        , output_predecessor_map_t
        , input_index_map_t
        , input_color_map_t
        , util_graph_t
        , util_index_map_t
        , util_color_map_t
        >
    {
    };
  }  // namespace loop_erased_random_paths_

  namespace {

    boost::keyword<
      loop_erased_random_paths_::input_graph_t
    > bgl_input_graph;
    boost::keyword<
      loop_erased_random_paths_::source_vertex_t
    > bgl_source_vertex;
    boost::keyword<
      loop_erased_random_paths_::random_index_generator_t
    > bgl_random_index_generator;
    boost::keyword<
      loop_erased_random_paths_::output_predecessor_map_t
    > bgl_output_predecessor_map;
    boost::keyword<
      loop_erased_random_paths_::input_index_map_t
    > bgl_input_index_map;
    boost::keyword<
      loop_erased_random_paths_::input_color_map_t
    > bgl_input_color_map;
    boost::keyword<
      loop_erased_random_paths_::util_graph_t
    > bgl_util_graph;
    boost::keyword<
      loop_erased_random_paths_::util_index_map_t
    > bgl_util_index_map;
    boost::keyword<
      loop_erased_random_paths_::util_color_map_t
    > bgl_util_color_map;
  }  // unnamed namespace

BOOST_NAMED_PARAMS_FUN(
  bool                      // return type
, loop_erased_random_paths  // name of function
, 4                         // number of arguments without defaults
, 9                         // total number of arguments
, loop_erased_random_paths_::keywords_t
)
{
    typedef typename find_named_param<
                       Params
                     , loop_erased_random_paths_::input_graph_t
                     >::type
            InputGraph;
    typedef typename find_named_param<
                       Params
                     , loop_erased_random_paths_::input_index_map_t
                     , property_map<InputGraph,vertex_index_t>
                     >::type
            InputIndexMap;
    typedef typename find_named_param<
                       Params
                     , loop_erased_random_paths_::util_graph_t
                     >::type
            UtilGraph;
    typedef typename find_named_param<
                       Params
                     , loop_erased_random_paths_::util_index_map_t
                     , property_map<UtilGraph,vertex_index_t>
                     >::type
            UtilIndexMap;

    InputGraph& in_g
      = p[bgl_input_graph];
    InputIndexMap in_index_map
      = p[bgl_input_index_map | get(vertex_index_t(), in_g)];
    UtilGraph& u_g
      = p[bgl_util_graph];
    UtilIndexMap u_index_map
      = p[bgl_util_index_map | get(vertex_index_t(), u_g)];

    return
      loop_erased_random_paths_::impl(
        in_g
      , p[bgl_source_vertex]
      , p[bgl_random_index_generator]
      , p[
          bgl_output_predecessor_map
        | get(vertex_predecessor_t(), in_g)
        ]
      , in_index_map
      , p[
          bgl_input_color_map
        | make_iterator_property_map(
            std::vector<default_color_type>(num_vertices(in_g)).begin()
          , in_index_map
          , white_color
          )
        ]
      , u_g
      , u_index_map
      , p[
          bgl_util_color_map
        | make_iterator_property_map(
            std::vector<default_color_type>(num_vertices(u_g)).begin()
          , u_index_map
          , white_color
          )
        ]
      );
}

 }  // namespace graph
}  // namespace boost

#endif /* BOOST_GRAPH_LOOP_ERASED_RANDOM_PATHS_HPP */