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