test: epoc32/include/stdapis/boost/graph/dijkstra_shortest

     1 //=======================================================================

     2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

     3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek

     4 //

     5 // Distributed under the Boost Software License, Version 1.0. (See

     6 // accompanying file LICENSE_1_0.txt or copy at

     7 // http://www.boost.org/LICENSE_1_0.txt)

     8 //=======================================================================

     9 #ifndef BOOST_GRAPH_DIJKSTRA_HPP

    10 #define BOOST_GRAPH_DIJKSTRA_HPP

    12 #include <functional>

    13 #include <boost/limits.hpp>

    14 #include <boost/graph/named_function_params.hpp>

    15 #include <boost/graph/breadth_first_search.hpp>

    16 #include <boost/graph/relax.hpp>

    17 #include <boost/pending/indirect_cmp.hpp>

    18 #include <boost/graph/exception.hpp>

    19 #include <boost/pending/relaxed_heap.hpp>

    21 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING

    22 #  include <boost/pending/mutable_queue.hpp>

    23 #endif // BOOST_GRAPH_DIJKSTRA_TESTING

    25 namespace boost {

    27 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING

    28   static bool dijkstra_relaxed_heap = true;

    29 #endif

    31   template <class Visitor, class Graph>

    32   struct DijkstraVisitorConcept {

    33     void constraints() {

    34       function_requires< CopyConstructibleConcept<Visitor> >();

    35       vis.initialize_vertex(u, g);

    36       vis.discover_vertex(u, g);

    37       vis.examine_vertex(u, g);

    38       vis.examine_edge(e, g);

    39       vis.edge_relaxed(e, g);

    40       vis.edge_not_relaxed(e, g);

    41       vis.finish_vertex(u, g);

    42     }

    43     Visitor vis;

    44     Graph g;

    45     typename graph_traits<Graph>::vertex_descriptor u;

    46     typename graph_traits<Graph>::edge_descriptor e;

    47   };

    49   template <class Visitors = null_visitor>

    50   class dijkstra_visitor : public bfs_visitor<Visitors> {

    51   public:

    52     dijkstra_visitor() { }

    53     dijkstra_visitor(Visitors vis)

    54       : bfs_visitor<Visitors>(vis) { }

    56     template <class Edge, class Graph>

    57     void edge_relaxed(Edge e, Graph& g) {

    58       invoke_visitors(this->m_vis, e, g, on_edge_relaxed());

    59     }

    60     template <class Edge, class Graph>

    61     void edge_not_relaxed(Edge e, Graph& g) {

    62       invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());

    63     }

    64   private:

    65     template <class Edge, class Graph>

    66     void tree_edge(Edge u, Graph& g) { }

    67   };

    68   template <class Visitors>

    69   dijkstra_visitor<Visitors>

    70   make_dijkstra_visitor(Visitors vis) {

    71     return dijkstra_visitor<Visitors>(vis);

    72   }

    73   typedef dijkstra_visitor<> default_dijkstra_visitor;

    75   namespace detail {

    77     template <class UniformCostVisitor, class UpdatableQueue,

    78       class WeightMap, class PredecessorMap, class DistanceMap,

    79       class BinaryFunction, class BinaryPredicate>

    80     struct dijkstra_bfs_visitor

    81     {

    82       typedef typename property_traits<DistanceMap>::value_type D;

    84       dijkstra_bfs_visitor(UniformCostVisitor vis, UpdatableQueue& Q,

    85                            WeightMap w, PredecessorMap p, DistanceMap d,

    86                            BinaryFunction combine, BinaryPredicate compare,

    87                            D zero)

    88         : m_vis(vis), m_Q(Q), m_weight(w), m_predecessor(p), m_distance(d),

    89           m_combine(combine), m_compare(compare), m_zero(zero)  { }

    91       template <class Edge, class Graph>

    92       void tree_edge(Edge e, Graph& g) {

    93         m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,

    94                             m_combine, m_compare);

    95         if (m_decreased)

    96           m_vis.edge_relaxed(e, g);

    97         else

    98           m_vis.edge_not_relaxed(e, g);

    99       }

   100       template <class Edge, class Graph>

   101       void gray_target(Edge e, Graph& g) {

   102         m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,

   103                             m_combine, m_compare);

   104         if (m_decreased) {

   105           m_Q.update(target(e, g));

   106           m_vis.edge_relaxed(e, g);

   107         } else

   108           m_vis.edge_not_relaxed(e, g);

   109       }

   111       template <class Vertex, class Graph>

   112       void initialize_vertex(Vertex u, Graph& g) { }

   113       template <class Edge, class Graph>

   114       void non_tree_edge(Edge, Graph&) { }

   115       template <class Vertex, class Graph>

   116       void discover_vertex(Vertex u, Graph& g) { m_vis.discover_vertex(u, g); }

   117       template <class Vertex, class Graph>

   118       void examine_vertex(Vertex u, Graph& g) { m_vis.examine_vertex(u, g); }

   119       template <class Edge, class Graph>

   120       void examine_edge(Edge e, Graph& g) {

   121         if (m_compare(get(m_weight, e), m_zero))

   122           throw negative_edge();

   123         m_vis.examine_edge(e, g);

   124       }

   125       template <class Edge, class Graph>

   126       void black_target(Edge, Graph&) { }

   127       template <class Vertex, class Graph>

   128       void finish_vertex(Vertex u, Graph& g) { m_vis.finish_vertex(u, g); }

   130       UniformCostVisitor m_vis;

   131       UpdatableQueue& m_Q;

   132       WeightMap m_weight;

   133       PredecessorMap m_predecessor;

   134       DistanceMap m_distance;

   135       BinaryFunction m_combine;

   136       BinaryPredicate m_compare;

   137       bool m_decreased;

   138       D m_zero;

   139     };

   141   } // namespace detail

   143   // Call breadth first search with default color map.

   144   template <class VertexListGraph, class DijkstraVisitor,

   145             class PredecessorMap, class DistanceMap,

   146             class WeightMap, class IndexMap, class Compare, class Combine,

   147             class DistZero>

   148   inline void

   149   dijkstra_shortest_paths_no_init

   150     (const VertexListGraph& g,

   151      typename graph_traits<VertexListGraph>::vertex_descriptor s,

   152      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,

   153      IndexMap index_map,

   154      Compare compare, Combine combine, DistZero zero,

   155      DijkstraVisitor vis)

   156   {

   157     std::vector<default_color_type> color(num_vertices(g));

   158     default_color_type c = white_color;

   159     dijkstra_shortest_paths_no_init( g, s, predecessor, distance, weight,

   160       index_map, compare, combine, zero, vis,

   161         make_iterator_property_map(&color[0], index_map, c));

   162   }

   164   // Call breadth first search

   165   template <class VertexListGraph, class DijkstraVisitor,

   166             class PredecessorMap, class DistanceMap,

   167             class WeightMap, class IndexMap, class Compare, class Combine,

   168             class DistZero, class ColorMap>

   169   inline void

   170   dijkstra_shortest_paths_no_init

   171     (const VertexListGraph& g,

   172      typename graph_traits<VertexListGraph>::vertex_descriptor s,

   173      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,

   174      IndexMap index_map,

   175      Compare compare, Combine combine, DistZero zero,

   176      DijkstraVisitor vis, ColorMap color)

   177   {

   178     typedef indirect_cmp<DistanceMap, Compare> IndirectCmp;

   179     IndirectCmp icmp(distance, compare);

   181     typedef typename graph_traits<VertexListGraph>::vertex_descriptor Vertex;

   183 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING

   184     if (!dijkstra_relaxed_heap) {

   185       typedef mutable_queue<Vertex, std::vector<Vertex>, IndirectCmp, IndexMap>

   186         MutableQueue;

   188       MutableQueue Q(num_vertices(g), icmp, index_map);

   190       detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap,

   191         PredecessorMap, DistanceMap, Combine, Compare>

   192       bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);

   194       breadth_first_visit(g, s, Q, bfs_vis, color);

   195       return;

   196     }

   197 #endif // BOOST_GRAPH_DIJKSTRA_TESTING

   199     typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue;

   201     MutableQueue Q(num_vertices(g), icmp, index_map);

   203     detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap,

   204       PredecessorMap, DistanceMap, Combine, Compare>

   205         bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);

   207     breadth_first_visit(g, s, Q, bfs_vis, color);

   208   }

   210   // Initialize distances and call breadth first search with default color map

   211   template <class VertexListGraph, class DijkstraVisitor,

   212             class PredecessorMap, class DistanceMap,

   213             class WeightMap, class IndexMap, class Compare, class Combine,

   214             class DistInf, class DistZero>

   215   inline void

   216   dijkstra_shortest_paths

   217     (const VertexListGraph& g,

   218      typename graph_traits<VertexListGraph>::vertex_descriptor s,

   219      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,

   220      IndexMap index_map,

   221      Compare compare, Combine combine, DistInf inf, DistZero zero,

   222      DijkstraVisitor vis)

   223   {

   224     std::vector<default_color_type> color(num_vertices(g));

   225     default_color_type c = white_color;

   226     dijkstra_shortest_paths(g, s, predecessor, distance, weight, index_map,

   227                             compare, combine, inf, zero, vis,

   228                             make_iterator_property_map(&color[0], index_map,

   229                                                        c));

   230   }

   232   // Initialize distances and call breadth first search

   233   template <class VertexListGraph, class DijkstraVisitor,

   234             class PredecessorMap, class DistanceMap,

   235             class WeightMap, class IndexMap, class Compare, class Combine,

   236             class DistInf, class DistZero, class ColorMap>

   237   inline void

   238   dijkstra_shortest_paths

   239     (const VertexListGraph& g,

   240      typename graph_traits<VertexListGraph>::vertex_descriptor s,

   241      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,

   242      IndexMap index_map,

   243      Compare compare, Combine combine, DistInf inf, DistZero zero,

   244      DijkstraVisitor vis, ColorMap color)

   245   {

   246     typedef typename property_traits<ColorMap>::value_type ColorValue;

   247     typedef color_traits<ColorValue> Color;

   248     typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;

   249     for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {

   250       vis.initialize_vertex(*ui, g);

   251       put(distance, *ui, inf);

   252       put(predecessor, *ui, *ui);

   253       put(color, *ui, Color::white());

   254     }

   255     put(distance, s, zero);

   257     dijkstra_shortest_paths_no_init(g, s, predecessor, distance, weight,

   258                             index_map, compare, combine, zero, vis, color);

   259   }

   261   namespace detail {

   263     // Handle defaults for PredecessorMap and

   264     // Distance Compare, Combine, Inf and Zero

   265     template <class VertexListGraph, class DistanceMap, class WeightMap,

   266               class IndexMap, class Params, class ColorMap>

   267     inline void

   268     dijkstra_dispatch2

   269       (const VertexListGraph& g,

   270        typename graph_traits<VertexListGraph>::vertex_descriptor s,

   271        DistanceMap distance, WeightMap weight, IndexMap index_map,

   272        const Params& params, ColorMap color)

   273     {

   274       // Default for predecessor map

   275       dummy_property_map p_map;

   277       typedef typename property_traits<DistanceMap>::value_type D;

   278       dijkstra_shortest_paths

   279         (g, s,

   280          choose_param(get_param(params, vertex_predecessor), p_map),

   281          distance, weight, index_map,

   282          choose_param(get_param(params, distance_compare_t()),

   283                       std::less<D>()),

   284          choose_param(get_param(params, distance_combine_t()),

   285                       closed_plus<D>()),

   286          choose_param(get_param(params, distance_inf_t()),

   287                       (std::numeric_limits<D>::max)()),

   288          choose_param(get_param(params, distance_zero_t()),

   289                       D()),

   290          choose_param(get_param(params, graph_visitor),

   291                       make_dijkstra_visitor(null_visitor())),

   292          color);

   293     }

   295     template <class VertexListGraph, class DistanceMap, class WeightMap,

   296               class IndexMap, class Params, class ColorMap>

   297     inline void

   298     dijkstra_dispatch1

   299       (const VertexListGraph& g,

   300        typename graph_traits<VertexListGraph>::vertex_descriptor s,

   301        DistanceMap distance, WeightMap weight, IndexMap index_map,

   302        const Params& params, ColorMap color)

   303     {

   304       // Default for distance map

   305       typedef typename property_traits<WeightMap>::value_type D;

   306       typename std::vector<D>::size_type

   307         n = is_default_param(distance) ? num_vertices(g) : 1;

   308       std::vector<D> distance_map(n);

   310       // Default for color map

   311       typename std::vector<default_color_type>::size_type

   312         m = is_default_param(color) ? num_vertices(g) : 1;

   313       std::vector<default_color_type> color_map(m);

   315       detail::dijkstra_dispatch2

   316         (g, s, choose_param(distance, make_iterator_property_map

   317                             (distance_map.begin(), index_map,

   318                              distance_map[0])),

   319          weight, index_map, params,

   320          choose_param(color, make_iterator_property_map

   321                       (color_map.begin(), index_map,

   322                        color_map[0])));

   323     }

   324   } // namespace detail

   326   // Named Parameter Variant

   327   template <class VertexListGraph, class Param, class Tag, class Rest>

   328   inline void

   329   dijkstra_shortest_paths

   330     (const VertexListGraph& g,

   331      typename graph_traits<VertexListGraph>::vertex_descriptor s,

   332      const bgl_named_params<Param,Tag,Rest>& params)

   333   {

   334     // Default for edge weight and vertex index map is to ask for them

   335     // from the graph.  Default for the visitor is null_visitor.

   336     detail::dijkstra_dispatch1

   337       (g, s,

   338        get_param(params, vertex_distance),

   339        choose_const_pmap(get_param(params, edge_weight), g, edge_weight),

   340        choose_const_pmap(get_param(params, vertex_index), g, vertex_index),

   341        params,

   342        get_param(params, vertex_color));

   343   }

   345 } // namespace boost

   347 #endif // BOOST_GRAPH_DIJKSTRA_HPP

author	William Roberts <williamr@symbian.org>
	Wed, 31 Mar 2010 12:33:34 +0100
branch	Symbian3
changeset 4	837f303aceeb
permissions	-rw-r--r--