| //======================================================================= |
| // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
| // Copyright 2009 Trustees of Indiana University. |
| // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Michael Hansen |
| // |
| // 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_DIJKSTRA_NO_COLOR_MAP_HPP |
| #define BOOST_GRAPH_DIJKSTRA_NO_COLOR_MAP_HPP |
| |
| #include <boost/pending/indirect_cmp.hpp> |
| #include <boost/graph/relax.hpp> |
| #include <boost/pending/relaxed_heap.hpp> |
| #include <boost/graph/detail/d_ary_heap.hpp> |
| #include <boost/graph/dijkstra_shortest_paths.hpp> |
| #include <boost/graph/iteration_macros.hpp> |
| |
| namespace boost { |
| |
| // No init version |
| template <typename Graph, typename DijkstraVisitor, |
| typename PredecessorMap, typename DistanceMap, |
| typename WeightMap, typename VertexIndexMap, |
| typename DistanceCompare, typename DistanceWeightCombine, |
| typename DistanceInfinity, typename DistanceZero> |
| void dijkstra_shortest_paths_no_color_map_no_init |
| (const Graph& graph, |
| typename graph_traits<Graph>::vertex_descriptor start_vertex, |
| PredecessorMap predecessor_map, |
| DistanceMap distance_map, |
| WeightMap weight_map, |
| VertexIndexMap index_map, |
| DistanceCompare distance_compare, |
| DistanceWeightCombine distance_weight_combine, |
| DistanceInfinity distance_infinity, |
| DistanceZero distance_zero, |
| DijkstraVisitor visitor) |
| { |
| typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
| typedef typename property_traits<DistanceMap>::value_type Distance; |
| typedef typename property_traits<WeightMap>::value_type Weight; |
| |
| typedef indirect_cmp<DistanceMap, DistanceCompare> DistanceIndirectCompare; |
| DistanceIndirectCompare |
| distance_indirect_compare(distance_map, distance_compare); |
| |
| // Choose vertex queue type |
| #if BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP |
| typedef relaxed_heap<Vertex, DistanceIndirectCompare, VertexIndexMap> |
| VertexQueue; |
| VertexQueue vertex_queue(num_vertices(graph), |
| distance_indirect_compare, |
| index_map); |
| #else |
| // Default - use d-ary heap (d = 4) |
| typedef |
| detail::vertex_property_map_generator<Graph, VertexIndexMap, std::size_t> |
| IndexInHeapMapHelper; |
| typedef typename IndexInHeapMapHelper::type IndexInHeapMap; |
| typedef |
| d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, DistanceCompare> |
| VertexQueue; |
| |
| boost::scoped_array<std::size_t> index_in_heap_map_holder; |
| IndexInHeapMap index_in_heap = |
| IndexInHeapMapHelper::build(graph, index_map, |
| index_in_heap_map_holder); |
| VertexQueue vertex_queue(distance_map, index_in_heap, distance_compare); |
| #endif |
| |
| // Add vertex to the queue |
| vertex_queue.push(start_vertex); |
| |
| // Starting vertex will always be the first discovered vertex |
| visitor.discover_vertex(start_vertex, graph); |
| |
| while (!vertex_queue.empty()) { |
| Vertex min_vertex = vertex_queue.top(); |
| vertex_queue.pop(); |
| |
| visitor.examine_vertex(min_vertex, graph); |
| |
| // Check if any other vertices can be reached |
| Distance min_vertex_distance = get(distance_map, min_vertex); |
| |
| if (!distance_compare(min_vertex_distance, distance_infinity)) { |
| // This is the minimum vertex, so all other vertices are unreachable |
| return; |
| } |
| |
| // Examine neighbors of min_vertex |
| typedef typename graph_traits<Graph>::edge_descriptor Edge; |
| BGL_FORALL_OUTEDGES_T(min_vertex, current_edge, graph, Graph) { |
| visitor.examine_edge(current_edge, graph); |
| |
| // Check if the edge has a negative weight |
| if (distance_compare(get(weight_map, current_edge), distance_zero)) { |
| boost::throw_exception(negative_edge()); |
| } |
| |
| // Extract the neighboring vertex and get its distance |
| Vertex neighbor_vertex = target(current_edge, graph); |
| Distance neighbor_vertex_distance = get(distance_map, neighbor_vertex); |
| bool is_neighbor_undiscovered = |
| !distance_compare(neighbor_vertex_distance, distance_infinity); |
| |
| // Attempt to relax the edge |
| bool was_edge_relaxed = relax(current_edge, graph, weight_map, |
| predecessor_map, distance_map, |
| distance_weight_combine, distance_compare); |
| |
| if (was_edge_relaxed) { |
| vertex_queue.update(neighbor_vertex); |
| visitor.edge_relaxed(current_edge, graph); |
| } else { |
| visitor.edge_not_relaxed(current_edge, graph); |
| } |
| |
| if (is_neighbor_undiscovered) { |
| visitor.discover_vertex(neighbor_vertex, graph); |
| vertex_queue.push(neighbor_vertex); |
| } |
| } // end out edge iteration |
| |
| visitor.finish_vertex(min_vertex, graph); |
| } // end while queue not empty |
| } |
| |
| // Full init version |
| template <typename Graph, typename DijkstraVisitor, |
| typename PredecessorMap, typename DistanceMap, |
| typename WeightMap, typename VertexIndexMap, |
| typename DistanceCompare, typename DistanceWeightCombine, |
| typename DistanceInfinity, typename DistanceZero> |
| void dijkstra_shortest_paths_no_color_map |
| (const Graph& graph, |
| typename graph_traits<Graph>::vertex_descriptor start_vertex, |
| PredecessorMap predecessor_map, |
| DistanceMap distance_map, |
| WeightMap weight_map, |
| VertexIndexMap index_map, |
| DistanceCompare distance_compare, |
| DistanceWeightCombine distance_weight_combine, |
| DistanceInfinity distance_infinity, |
| DistanceZero distance_zero, |
| DijkstraVisitor visitor) |
| { |
| // Initialize vertices |
| BGL_FORALL_VERTICES_T(current_vertex, graph, Graph) { |
| visitor.initialize_vertex(current_vertex, graph); |
| |
| // Default all distances to infinity |
| put(distance_map, current_vertex, distance_infinity); |
| |
| // Default all vertex predecessors to the vertex itself |
| put(predecessor_map, current_vertex, current_vertex); |
| } |
| |
| // Set distance for start_vertex to zero |
| put(distance_map, start_vertex, distance_zero); |
| |
| // Pass everything on to the no_init version |
| dijkstra_shortest_paths_no_color_map_no_init(graph, |
| start_vertex, predecessor_map, distance_map, weight_map, |
| index_map, distance_compare, distance_weight_combine, |
| distance_infinity, distance_zero, visitor); |
| } |
| |
| namespace detail { |
| |
| // Handle defaults for PredecessorMap, DistanceCompare, |
| // DistanceWeightCombine, DistanceInfinity and DistanceZero |
| template <typename Graph, typename DistanceMap, typename WeightMap, |
| typename VertexIndexMap, typename Params> |
| inline void |
| dijkstra_no_color_map_dispatch2 |
| (const Graph& graph, |
| typename graph_traits<Graph>::vertex_descriptor start_vertex, |
| DistanceMap distance_map, WeightMap weight_map, |
| VertexIndexMap index_map, const Params& params) |
| { |
| // Default for predecessor map |
| dummy_property_map predecessor_map; |
| |
| typedef typename property_traits<DistanceMap>::value_type DistanceType; |
| dijkstra_shortest_paths_no_color_map |
| (graph, start_vertex, |
| choose_param(get_param(params, vertex_predecessor), predecessor_map), |
| distance_map, weight_map, index_map, |
| choose_param(get_param(params, distance_compare_t()), |
| std::less<DistanceType>()), |
| choose_param(get_param(params, distance_combine_t()), |
| closed_plus<DistanceType>()), |
| choose_param(get_param(params, distance_inf_t()), |
| (std::numeric_limits<DistanceType>::max)()), |
| choose_param(get_param(params, distance_zero_t()), |
| DistanceType()), |
| choose_param(get_param(params, graph_visitor), |
| make_dijkstra_visitor(null_visitor()))); |
| } |
| |
| template <typename Graph, typename DistanceMap, typename WeightMap, |
| typename IndexMap, typename Params> |
| inline void |
| dijkstra_no_color_map_dispatch1 |
| (const Graph& graph, |
| typename graph_traits<Graph>::vertex_descriptor start_vertex, |
| DistanceMap distance_map, WeightMap weight_map, |
| IndexMap index_map, const Params& params) |
| { |
| // Default for distance map |
| typedef typename property_traits<WeightMap>::value_type DistanceType; |
| typename std::vector<DistanceType>::size_type |
| vertex_count = is_default_param(distance_map) ? num_vertices(graph) : 1; |
| |
| std::vector<DistanceType> default_distance_map(vertex_count); |
| |
| detail::dijkstra_no_color_map_dispatch2 |
| (graph, start_vertex, choose_param(distance_map, |
| make_iterator_property_map(default_distance_map.begin(), index_map, |
| default_distance_map[0])), |
| weight_map, index_map, params); |
| } |
| } // namespace detail |
| |
| // Named parameter version |
| template <typename Graph, typename Param, typename Tag, typename Rest> |
| inline void |
| dijkstra_shortest_paths_no_color_map |
| (const Graph& graph, |
| typename graph_traits<Graph>::vertex_descriptor start_vertex, |
| const bgl_named_params<Param, Tag, Rest>& params) |
| { |
| // Default for edge weight and vertex index map is to ask for them |
| // from the graph. Default for the visitor is null_visitor. |
| detail::dijkstra_no_color_map_dispatch1 |
| (graph, start_vertex, |
| get_param(params, vertex_distance), |
| choose_const_pmap(get_param(params, edge_weight), graph, edge_weight), |
| choose_const_pmap(get_param(params, vertex_index), graph, vertex_index), |
| params); |
| } |
| |
| } // namespace boost |
| |
| #endif // BOOST_GRAPH_DIJKSTRA_NO_COLOR_MAP_HPP |