x
Yes
No
Do you want to visit DriveHQ English website?
Inicio
Características
Precios
Prueba gratuita
Software cliente
Acerca de nosotros
Servidor de archivos
|
Solución de copias de seguridad
|
Servidor FTP
|
Servidor de correo electrónico
|
Alojamiento web
|
Software cliente
Servidor de archivos
Solución de copia de seguridad
Servidor FTP
Servidor de correo electrónico
Alojamiento web
Software cliente
dag_shortest_paths.hpp - Hosted on DriveHQ Cloud IT Platform
Arriba
Subir
Descargar
Compartir
Publicar
Nueva carpeta
Nuevo archivo
Copiar
Cortar
Eliminar
Pegar
Clasificación
Actualizar
Ruta de la carpeta: \\game3dprogramming\materials\GameFactory\GameFactoryDemo\references\boost_1_35_0\boost\graph\dag_shortest_paths.hpp
Girar
Efecto
Propiedad
Historial
//======================================================================= // Copyright 2002 Indiana University. // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek // // 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) //======================================================================= #ifndef BOOST_GRAPH_DAG_SHORTEST_PATHS_HPP #define BOOST_GRAPH_DAG_SHORTEST_PATHS_HPP #include
#include
// single-source shortest paths for a Directed Acyclic Graph (DAG) namespace boost { // Initalize distances and call depth first search template
inline void dag_shortest_paths (const VertexListGraph& g, typename graph_traits
::vertex_descriptor s, DistanceMap distance, WeightMap weight, ColorMap color, PredecessorMap pred, DijkstraVisitor vis, Compare compare, Combine combine, DistInf inf, DistZero zero) { typedef typename graph_traits
::vertex_descriptor Vertex; std::vector
rev_topo_order; rev_topo_order.reserve(num_vertices(g)); // Call 'depth_first_visit', not 'topological_sort', because we don't // want to traverse the entire graph, only vertices reachable from 's', // and 'topological_sort' will traverse everything. The logic below // is the same as for 'topological_sort', only we call 'depth_first_visit' // and 'topological_sort' calls 'depth_first_search'. topo_sort_visitor
> > topo_visitor(std::back_inserter(rev_topo_order)); depth_first_visit(g, s, topo_visitor, color); typename graph_traits
::vertex_iterator ui, ui_end; for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { put(distance, *ui, inf); put(pred, *ui, *ui); } put(distance, s, zero); vis.discover_vertex(s, g); typename std::vector
::reverse_iterator i; for (i = rev_topo_order.rbegin(); i != rev_topo_order.rend(); ++i) { Vertex u = *i; vis.examine_vertex(u, g); typename graph_traits
::out_edge_iterator e, e_end; for (tie(e, e_end) = out_edges(u, g); e != e_end; ++e) { vis.discover_vertex(target(*e, g), g); bool decreased = relax(*e, g, weight, pred, distance, combine, compare); if (decreased) vis.edge_relaxed(*e, g); else vis.edge_not_relaxed(*e, g); } vis.finish_vertex(u, g); } } namespace detail { // Defaults are the same as Dijkstra's algorithm // Handle Distance Compare, Combine, Inf and Zero defaults template
inline void dag_sp_dispatch2 (const VertexListGraph& g, typename graph_traits
::vertex_descriptor s, DistanceMap distance, WeightMap weight, ColorMap color, IndexMap id, DijkstraVisitor vis, const Params& params) { typedef typename property_traits
::value_type D; dummy_property_map p_map; dag_shortest_paths (g, s, distance, weight, color, choose_param(get_param(params, vertex_predecessor), p_map), vis, choose_param(get_param(params, distance_compare_t()), std::less
()), choose_param(get_param(params, distance_combine_t()), closed_plus
()), choose_param(get_param(params, distance_inf_t()), (std::numeric_limits
::max)()), choose_param(get_param(params, distance_zero_t()), D())); } // Handle DistanceMap and ColorMap defaults template
inline void dag_sp_dispatch1 (const VertexListGraph& g, typename graph_traits
::vertex_descriptor s, DistanceMap distance, WeightMap weight, ColorMap color, IndexMap id, DijkstraVisitor vis, const Params& params) { typedef typename property_traits
::value_type T; typename std::vector
::size_type n; n = is_default_param(distance) ? num_vertices(g) : 1; std::vector
distance_map(n); n = is_default_param(color) ? num_vertices(g) : 1; std::vector
color_map(n); dag_sp_dispatch2 (g, s, choose_param(distance, make_iterator_property_map(distance_map.begin(), id, distance_map[0])), weight, choose_param(color, make_iterator_property_map(color_map.begin(), id, color_map[0])), id, vis, params); } } // namespace detail template
inline void dag_shortest_paths (const VertexListGraph& g, typename graph_traits
::vertex_descriptor s, const bgl_named_params
& params) { // assert that the graph is directed... null_visitor null_vis; detail::dag_sp_dispatch1 (g, s, get_param(params, vertex_distance), choose_const_pmap(get_param(params, edge_weight), g, edge_weight), get_param(params, vertex_color), choose_const_pmap(get_param(params, vertex_index), g, vertex_index), choose_param(get_param(params, graph_visitor), make_dijkstra_visitor(null_vis)), params); } } // namespace boost #endif // BOOST_GRAPH_DAG_SHORTEST_PATHS_HPP
dag_shortest_paths.hpp
Dirección de la página
Dirección del archivo
Anterior
21/95
Siguiente
Descargar
( 6 KB )
Comments
Total ratings:
0
Average rating:
No clasificado
of 10
Would you like to comment?
Join now
, or
Logon
if you are already a member.