//=======================================================================

// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, 

//

// 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)

//=======================================================================

/*

 * © Portions copyright (c) 2006-2007 Nokia Corporation.  All rights reserved.

*/

#include <boost/config.hpp>

#include <iostream>

#include <fstream>

#include <boost/graph/graph_traits.hpp>

#include <boost/graph/adjacency_list.hpp>

#include <boost/graph/dijkstra_shortest_paths.hpp>

#ifdef __SYMBIAN32__

#include "std_log_result.h"

#define LOG_FILENAME_LINE __FILE__, __LINE__

#endif

using namespace boost;

int

main(int, char *[])

{

  typedef adjacency_list < listS, vecS, directedS,

    no_property, property < edge_weight_t, int > > graph_t;

  typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;

  typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;

  typedef std::pair<int, int> Edge;

  const int num_nodes = 5;

  enum nodes { A, B, C, D, E };

  char name[] = "ABCDE";

  Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),

    Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B)

  };

  int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };

  int num_arcs = sizeof(edge_array) / sizeof(Edge);

#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300

  graph_t g(num_nodes);

  property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);

  for (std::size_t j = 0; j < num_arcs; ++j) {

    edge_descriptor e; bool inserted;

    tie(e, inserted) = add_edge(edge_array[j].first, edge_array[j].second, g);

    weightmap[e] = weights[j];

  }

#else

  graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);

  property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);

#endif

  std::vector<vertex_descriptor> p(num_vertices(g));

  std::vector<int> d(num_vertices(g));

  vertex_descriptor s = vertex(A, g);

#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300

  // VC++ has trouble with the named parameters mechanism

  property_map<graph_t, vertex_index_t>::type indexmap = get(vertex_index, g);

  dijkstra_shortest_paths(g, s, &p[0], &d[0], weightmap, indexmap, 

                          std::less<int>(), closed_plus<int>(), 

                          (std::numeric_limits<int>::max)(), 0,

                          default_dijkstra_visitor());

#else

  dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d[0]));

#endif

  std::cout << "distances and parents:" << std::endl;

  graph_traits < graph_t >::vertex_iterator vi, vend;

  for (tie(vi, vend) = vertices(g); vi != vend; ++vi) {

    std::cout << "distance(" << name[*vi] << ") = " << d[*vi] << ", ";

    std::cout << "parent(" << name[*vi] << ") = " << name[p[*vi]] << std::

      endl;

  }

  std::cout << std::endl;

  std::ofstream dot_file("figs/dijkstra-eg.dot");

  dot_file << "digraph D {\n"

    << "  rankdir=LR\n"

    << "  size=\"4,3\"\n"

    << "  ratio=\"fill\"\n"

    << "  edge[style=\"bold\"]\n" << "  node[shape=\"circle\"]\n";

  graph_traits < graph_t >::edge_iterator ei, ei_end;

  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {

    graph_traits < graph_t >::edge_descriptor e = *ei;

    graph_traits < graph_t >::vertex_descriptor

      u = source(e, g), v = target(e, g);

    dot_file << name[u] << " -> " << name[v]

      << "[label=\"" << get(weightmap, e) << "\"";

    if (p[v] == u)

      dot_file << ", color=\"black\"";

    else

      dot_file << ", color=\"grey\"";

    dot_file << "]";

  }

  dot_file << "}";

   #ifdef __SYMBIAN32__

	std_log(LOG_FILENAME_LINE,"[End Test Case ]");

	testResultXml("dijkstra-example");

	close_log_file();

    #endif

  return EXIT_SUCCESS;

}