/* loop_erased_random_paths.cpp source 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)
 */

/*
 * Defines the std::ostream class and std::cout, its global instance.
 */
#include <iostream>

/*
 * Defines the std::list class template and its iterators.
 */
#include <list>

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

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

/*
 * Defines the boost::mt19937 class, to be used as a random-number-generating
 * engine.
 */
#include <boost/random/mersenne_twister.hpp>

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

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

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

/*
 * Defines the vertex and edge property tags.
 */
#include <boost/graph/properties.hpp>

/*
 * Defines the boost::directedS and boost::undirectedS selector tags.
 */
#include <boost/graph/graph_selectors.hpp>

/*
 * Defines the boost::adjacency_list class template and its associated
 * non-member function templates.
 */
#include <boost/graph/adjacency_list.hpp>

/*
 * Defines the boost::adjacency_matrix class template and its associated
 * non-member function templates.
 */
#include <boost/graph/adjacency_matrix.hpp>

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

using namespace boost;
using namespace graph;

template <typename Graph>
void init_graph(Graph& g)
{
    add_edge(vertex(0, g), vertex(7, g), g);
    add_edge(vertex(1, g), vertex(2, g), g);
    add_edge(vertex(2, g), vertex(10, g), g);
    add_edge(vertex(2, g), vertex(5, g), g);
    add_edge(vertex(3, g), vertex(10, g), g);
    add_edge(vertex(3, g), vertex(0, g), g);
    add_edge(vertex(4, g), vertex(5, g), g);
    add_edge(vertex(4, g), vertex(0, g), g);
    add_edge(vertex(5, g), vertex(14, g), g);
    add_edge(vertex(6, g), vertex(3, g), g);
    add_edge(vertex(7, g), vertex(17, g), g);
    add_edge(vertex(7, g), vertex(11, g), g);
    add_edge(vertex(8, g), vertex(17, g), g);
    add_edge(vertex(8, g), vertex(1, g), g);
    add_edge(vertex(9, g), vertex(11, g), g);
    add_edge(vertex(9, g), vertex(1, g), g);
    add_edge(vertex(10, g), vertex(19, g), g);
    add_edge(vertex(10, g), vertex(15, g), g);
    add_edge(vertex(10, g), vertex(8, g), g);
    add_edge(vertex(11, g), vertex(19, g), g);
    add_edge(vertex(11, g), vertex(15, g), g);
    add_edge(vertex(11, g), vertex(4, g), g);
    add_edge(vertex(12, g), vertex(19, g), g);
    add_edge(vertex(12, g), vertex(8, g), g);
    add_edge(vertex(12, g), vertex(4, g), g);
    add_edge(vertex(13, g), vertex(15, g), g);
    add_edge(vertex(13, g), vertex(8, g), g);
    add_edge(vertex(13, g), vertex(4, g), g);
    add_edge(vertex(14, g), vertex(22, g), g);
    add_edge(vertex(14, g), vertex(12, g), g);
    add_edge(vertex(15, g), vertex(22, g), g);
    add_edge(vertex(15, g), vertex(6, g), g);
    add_edge(vertex(16, g), vertex(12, g), g);
    add_edge(vertex(16, g), vertex(6, g), g);
    add_edge(vertex(17, g), vertex(20, g), g);
    add_edge(vertex(18, g), vertex(9, g), g);
    add_edge(vertex(19, g), vertex(23, g), g);
    add_edge(vertex(19, g), vertex(18, g), g);
    add_edge(vertex(20, g), vertex(23, g), g);
    add_edge(vertex(20, g), vertex(13, g), g);
    add_edge(vertex(21, g), vertex(18, g), g);
    add_edge(vertex(21, g), vertex(13, g), g);
    add_edge(vertex(22, g), vertex(21, g), g);
    add_edge(vertex(23, g), vertex(16, g), g);
}

template <
  typename Graph
, typename RNGEngine
>
void loop_erased_random_paths_example(
  const unsigned int start_index
, const unsigned int end_index
, const unsigned int max_weight
, unsigned int num_runs
)
{
    typedef typename graph_traits<Graph>::vertex_descriptor
            Vertex;
    typedef std::map<Vertex,Vertex>
            VertexMap;
    typedef associative_property_map<VertexMap>
            PredecessorMap;
    typedef typename property_map<Graph,vertex_index_t>::type
            VertexIndexMap;
    typedef std::list<Vertex>
            Path;
    typedef typename Path::iterator
            PathIterator;
    typedef random_number_generator<RNGEngine,unsigned int>
            RandomIndexGenerator;

    Graph                g(24);
    Graph                u_g(24);
    Vertex               src_vertex = vertex(start_index, g);
    Vertex               target_vertex = vertex(end_index, g);
    Vertex               v;
    VertexMap            v_map;
    PredecessorMap       pred_map(v_map);
    VertexIndexMap       index_map = get(vertex_index_t(), g);
    Path                 path;
    PathIterator         begin, end;
    RNGEngine            rng_engine;
    RandomIndexGenerator rig(rng_engine);

    init_graph(g);

    while (num_runs > 0)
    {
        loop_erased_random_paths(
          bgl_input_graph = g
        , bgl_output_predecessor_map = pred_map
        , bgl_source_vertex = src_vertex
        , bgl_input_index_map = index_map
        , bgl_util_graph = u_g
        , bgl_random_index_generator = rig
        );

        for (
          v = target_vertex;
          v != get(pred_map, v);
          v = get(pred_map, v)
        )
        {
            path.push_front(v);
        }

        if (v == src_vertex)
        {
            path.push_front(v);
            begin = path.begin();
            end = path.end();

            std::cout << "The path: " << get(index_map, *begin);

            while (++begin != end)
            {
                std::cout << " -> " << get(index_map, *begin);
            }

            std::cout << std::endl;
            --num_runs;
        }

        path.clear();
    }
}

template <
  typename UndirectedGraph
, typename DirectedGraph
, typename RNGEngine
>
void example(
  const unsigned int start_index
, const unsigned int end_index
, const unsigned int max_weight
, const unsigned int num_runs
)
{
    std::cout << "Running loop_erased_random_paths function template on ";
    std::cout << "undirected graph." << std::endl;
    loop_erased_random_paths_example<UndirectedGraph,RNGEngine>(
      start_index, end_index, max_weight, num_runs
    );
    std::cout << std::endl;

    std::cout << "Running loop_erased_random_paths function template on ";
    std::cout << "directed graph." << std::endl;
    loop_erased_random_paths_example<DirectedGraph,RNGEngine>(
      start_index, end_index, max_weight, num_runs
    );
}

template <
  typename EdgeContainerSelector
, typename RNGEngine
>
void vec_adjacency_list_example(
  const unsigned int start_index
, const unsigned int end_index
, const unsigned int max_weight
, const unsigned int num_runs
)
{
    typedef adjacency_list<
              EdgeContainerSelector
            , vecS
            , undirectedS
            , no_property
            , property<edge_weight_t,int>
            , no_property
            >
            UndirectedGraph;
    typedef adjacency_list<
              EdgeContainerSelector
            , vecS
            , directedS
            , no_property
            , property<edge_weight_t,int>
            , no_property
            >
            DirectedGraph;
    typedef adjacency_list<
              EdgeContainerSelector
            , vecS
            , bidirectionalS
            , no_property
            , property<edge_weight_t,int>
            , no_property
            >
            BidirectionalGraph;

    example<UndirectedGraph,DirectedGraph,RNGEngine>(
      start_index, end_index, max_weight, num_runs
    );
    std::cout << std::endl;

    std::cout << "Running loop_erased_random_paths function template on ";
    std::cout << "bidirectional graph." << std::endl;
    loop_erased_random_paths_example<BidirectionalGraph,RNGEngine>(
      start_index, end_index, max_weight, num_runs
    );
}

template <
  typename RNGEngine
>
void adjacency_matrix_example(
  const unsigned int start_index
, const unsigned int end_index
, const unsigned int max_weight
, const unsigned int num_runs
)
{
    typedef adjacency_matrix<
              undirectedS
            , no_property
            , property<edge_weight_t,int>
            , no_property
            >
            UndirectedGraph;
    typedef adjacency_matrix<
              directedS
            , no_property
            , property<edge_weight_t,int>
            , no_property
            >
            DirectedGraph;

    example<UndirectedGraph,DirectedGraph,RNGEngine>(
      start_index, end_index, max_weight, num_runs
    );
}

int usage()
{
    std::cout << "Options:" << std::endl;
    std::cout << "-s#, where # is an integer between 0 and 23, inclusive";
    std::cout << " (default is 0)" << std::endl;
    std::cout << "-e#, where # is an integer between 0 and 23, inclusive";
    std::cout << " (default is 22)" << std::endl;
    std::cout << "-m#, where # is an integer between 0 and 65536, inclusive";
    std::cout << " (default is 16384)" << std::endl;
    std::cout << "-n#, where # is a nonnegative integer";
    std::cout << " (default is 256)" << std::endl;
    return 0;
}

int main(int argc, char** argv)
{
    unsigned int start_index = 0;
    unsigned int end_index = 22;
    unsigned int max_weight = 16384;
    unsigned int num_runs = 256;
    char* arg;

    while (--argc > 0)
    {
        arg = argv[argc];

        if ((std::strlen(arg) > 2) && (arg[0] == '-'))
        {
            switch (arg[1])
            {
                case 's':
                    start_index = std::atoi(&arg[2]);

                    if (start_index > 23)
                    {
                        return usage();
                    }

                    break;

                case 'e':
                    end_index = std::atoi(&arg[2]);

                    if (end_index > 23)
                    {
                        return usage();
                    }

                    break;

                case 'm':
                    max_weight = std::atoi(&arg[2]);

                    if (max_weight > 65536)
                    {
                        return usage();
                    }

                    break;

                case 'n':
                    num_runs = std::atoi(&arg[2]);
                    break;

                default:
                    return usage();
            }
        }
        else
        {
            return usage();
        }
    }

//    adjacency_matrix_example<mt19937>(
//    vec_adjacency_list_example<multisetS,mt19937>(
//    vec_adjacency_list_example<setS,mt19937>(
//    vec_adjacency_list_example<listS,mt19937>(
    vec_adjacency_list_example<vecS,mt19937>(
      start_index, end_index, max_weight, num_runs
    );

    return 0;
}