/* maze.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::vector class template and its iterators.
 */
#include <vector>

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

/*
 * Defines the std::pair class template and the std::make_pair function
 * template.
 */
#include <utility>

/*
 * Defines the boost::property_map and boost::associative_property_map class
 * templates and the boost::get, boost::put, and
 * boost::make_iterator_property_map 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::listS, boost::vecS, and boost::directedS selector tags.
 */
#include <boost/graph/graph_selectors.hpp>

/*
 * Defines the boost::predecessor_recorder class template and the
 * boost::null_visitor class.
 */
#include <boost/graph/visitors.hpp>

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

/*
 * Defines the boost::dfs_visitor class template and the
 * boost::depth_first_visit and boost::make_dfs_visitor function templates.
 */
#include <boost/graph/depth_first_search.hpp>

using namespace boost;

int main(int argc, char** argv)
{
    typedef adjacency_list<listS,vecS,directedS>
            Graph;
    typedef graph_traits<Graph>::vertex_descriptor
            Vertex;
    typedef graph_traits<Graph>::vertex_iterator
            VertexIterator;
    typedef std::map<Vertex,Vertex>
            VertexMap;
    typedef associative_property_map<VertexMap>
            PredecessorMap;
    typedef predecessor_recorder<PredecessorMap,on_tree_edge>
            PredVisitor;
    typedef dfs_visitor<std::pair<PredVisitor,null_visitor> >
            DFSVisitor;
    typedef property_map<Graph,vertex_index_t>::type
            VertexIndexMap;
    typedef std::list<Vertex>
            Path;
    typedef Path::iterator
            PathIterator;

    Graph  g(12);
    Path   solution_path;
    Vertex target_vertex = vertex(11, g);

    add_edge(vertex(0, g), vertex(1, g), g);
    add_edge(vertex(1, g), vertex(4, g), g);
    add_edge(vertex(2, g), vertex(1, g), g);
    add_edge(vertex(3, g), vertex(1, g), g);
    add_edge(vertex(4, g), vertex(2, g), g);
    add_edge(vertex(4, g), vertex(3, g), g);
    add_edge(vertex(4, g), vertex(7, g), g);
    add_edge(vertex(5, g), vertex(2, g), g);
    add_edge(vertex(5, g), vertex(4, g), g);
    add_edge(vertex(6, g), vertex(3, g), g);
    add_edge(vertex(6, g), vertex(4, g), g);
    add_edge(vertex(7, g), vertex(5, g), g);
    add_edge(vertex(7, g), vertex(6, g), g);
    add_edge(vertex(7, g), vertex(10, g), g);
    add_edge(vertex(8, g), vertex(5, g), g);
    add_edge(vertex(8, g), vertex(7, g), g);
    add_edge(vertex(9, g), vertex(6, g), g);
    add_edge(vertex(9, g), vertex(7, g), g);
    add_edge(vertex(10, g), vertex(8, g), g);
    add_edge(vertex(10, g), vertex(9, g), g);
    add_edge(vertex(10, g), vertex(11, g), g);

    VertexIterator vi, vi_end;

    for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
    {
        VertexMap
          v_map;
        PredecessorMap
          pred_map(v_map);
        PredVisitor
          pred_vis(pred_map);
        null_visitor
          null_vis;
        DFSVisitor
          dfs_vis = make_dfs_visitor(std::make_pair(pred_vis, null_vis));
        VertexIndexMap
          index_map = get(vertex_index_t(), g);
        Vertex
          source_vertex = *vi;

        depth_first_visit(
          g
        , source_vertex
        , dfs_vis
        , make_iterator_property_map(
            std::vector<default_color_type>(num_vertices(g)).begin()
          , index_map
          , white_color
          )
        );

        Vertex v = target_vertex;

        while (v != get(pred_map, v))
        {
            solution_path.push_front(v);
            v = get(pred_map, v);
        }

        if (v == source_vertex)
        {
            solution_path.push_front(v);
            PathIterator solution_begin = solution_path.begin();
            PathIterator solution_end   = solution_path.end();

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

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

            std::cout << std::endl;
        }
        else
        {
            std::cout << "The path cannot be calculated from vertex ";
            std::cout << get(index_map, source_vertex) << std::endl;
        }

        solution_path.clear();
    }

    return 0;
}