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

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

 }