1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/stdcpp/tsrc/Boost_test/graph/src/dijkstra-example.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,116 @@
1.4 +//=======================================================================
1.5 +// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
1.6 +//
1.7 +// Distributed under the Boost Software License, Version 1.0. (See
1.8 +// accompanying file LICENSE_1_0.txt or copy at
1.9 +// http://www.boost.org/LICENSE_1_0.txt)
1.10 +//=======================================================================
1.11 +
1.12 +/*
1.13 + * © Portions copyright (c) 2006-2007 Nokia Corporation. All rights reserved.
1.14 +*/
1.15 +
1.16 +
1.17 +#include <boost/config.hpp>
1.18 +#include <iostream>
1.19 +#include <fstream>
1.20 +
1.21 +#include <boost/graph/graph_traits.hpp>
1.22 +#include <boost/graph/adjacency_list.hpp>
1.23 +#include <boost/graph/dijkstra_shortest_paths.hpp>
1.24 +
1.25 +#ifdef __SYMBIAN32__
1.26 +#include "std_log_result.h"
1.27 +#define LOG_FILENAME_LINE __FILE__, __LINE__
1.28 +#endif
1.29 +
1.30 +
1.31 +
1.32 +using namespace boost;
1.33 +
1.34 +int
1.35 +main(int, char *[])
1.36 +{
1.37 + typedef adjacency_list < listS, vecS, directedS,
1.38 + no_property, property < edge_weight_t, int > > graph_t;
1.39 + typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
1.40 + typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
1.41 + typedef std::pair<int, int> Edge;
1.42 +
1.43 + const int num_nodes = 5;
1.44 + enum nodes { A, B, C, D, E };
1.45 + char name[] = "ABCDE";
1.46 + Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
1.47 + Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B)
1.48 + };
1.49 + int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
1.50 + int num_arcs = sizeof(edge_array) / sizeof(Edge);
1.51 +#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
1.52 + graph_t g(num_nodes);
1.53 + property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
1.54 + for (std::size_t j = 0; j < num_arcs; ++j) {
1.55 + edge_descriptor e; bool inserted;
1.56 + tie(e, inserted) = add_edge(edge_array[j].first, edge_array[j].second, g);
1.57 + weightmap[e] = weights[j];
1.58 + }
1.59 +#else
1.60 + graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
1.61 + property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
1.62 +#endif
1.63 + std::vector<vertex_descriptor> p(num_vertices(g));
1.64 + std::vector<int> d(num_vertices(g));
1.65 + vertex_descriptor s = vertex(A, g);
1.66 +
1.67 +#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
1.68 + // VC++ has trouble with the named parameters mechanism
1.69 + property_map<graph_t, vertex_index_t>::type indexmap = get(vertex_index, g);
1.70 + dijkstra_shortest_paths(g, s, &p[0], &d[0], weightmap, indexmap,
1.71 + std::less<int>(), closed_plus<int>(),
1.72 + (std::numeric_limits<int>::max)(), 0,
1.73 + default_dijkstra_visitor());
1.74 +#else
1.75 + dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d[0]));
1.76 +#endif
1.77 +
1.78 + std::cout << "distances and parents:" << std::endl;
1.79 + graph_traits < graph_t >::vertex_iterator vi, vend;
1.80 + for (tie(vi, vend) = vertices(g); vi != vend; ++vi) {
1.81 + std::cout << "distance(" << name[*vi] << ") = " << d[*vi] << ", ";
1.82 + std::cout << "parent(" << name[*vi] << ") = " << name[p[*vi]] << std::
1.83 + endl;
1.84 + }
1.85 + std::cout << std::endl;
1.86 +
1.87 + std::ofstream dot_file("figs/dijkstra-eg.dot");
1.88 +
1.89 + dot_file << "digraph D {\n"
1.90 + << " rankdir=LR\n"
1.91 + << " size=\"4,3\"\n"
1.92 + << " ratio=\"fill\"\n"
1.93 + << " edge[style=\"bold\"]\n" << " node[shape=\"circle\"]\n";
1.94 +
1.95 + graph_traits < graph_t >::edge_iterator ei, ei_end;
1.96 + for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
1.97 + graph_traits < graph_t >::edge_descriptor e = *ei;
1.98 + graph_traits < graph_t >::vertex_descriptor
1.99 + u = source(e, g), v = target(e, g);
1.100 + dot_file << name[u] << " -> " << name[v]
1.101 + << "[label=\"" << get(weightmap, e) << "\"";
1.102 + if (p[v] == u)
1.103 + dot_file << ", color=\"black\"";
1.104 + else
1.105 + dot_file << ", color=\"grey\"";
1.106 + dot_file << "]";
1.107 + }
1.108 + dot_file << "}";
1.109 +
1.110 + #ifdef __SYMBIAN32__
1.111 + std_log(LOG_FILENAME_LINE,"[End Test Case ]");
1.112 + testResultXml("dijkstra-example");
1.113 + close_log_file();
1.114 + #endif
1.115 + return EXIT_SUCCESS;
1.116 +}
1.117 +
1.118 +
1.119 +