//======================================================================= // Copyright 2015 by Ireneusz Szcześniak // Authors: Ireneusz Szcześniak // // 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) //======================================================================= //======================================================================= // The custom Dijkstra call, which returns the optional path as a list // along with the cost of the path. The search is stopped when the // destination node is reached. //======================================================================= #ifndef BOOST_GRAPH_CUSTOM_DIJKSTRA_CALL #define BOOST_GRAPH_CUSTOM_DIJKSTRA_CALL #include #include #include #include #include #include #include namespace boost { //======================================================================== // Finish the search when a given node is examined, i.e. when the // shortest path to that node is found. // ======================================================================== // The type of the exception thrown by the cdc_visitor. struct cdc_exception {}; template struct cdc_visitor { typedef typename Graph::vertex_descriptor vertex_descriptor; typedef on_examine_vertex event_filter; cdc_visitor(vertex_descriptor t): m_t(t) {} void operator()(vertex_descriptor v, const Graph& g) { if (v == m_t) throw cdc_exception(); } vertex_descriptor m_t; }; //======================================================================== // The function. //=======================================================================+ template optional>> custom_dijkstra_call(const Graph &g, typename Graph::vertex_descriptor s, typename Graph::vertex_descriptor t, WeightMap wm, IndexMap im) { typedef typename Graph::vertex_descriptor vertex_descriptor; typedef typename Graph::edge_descriptor edge_descriptor; typedef typename std::list path_type; typedef typename WeightMap::value_type weight_type; typedef typename std::pair kr_type; std::vector pred_vec(num_vertices(g)); auto pred = make_iterator_property_map(pred_vec.begin(), im); auto rep = record_edge_predecessors(pred, on_edge_relaxed()); auto qat = cdc_visitor(t); auto dv = make_dijkstra_visitor(std::make_pair(rep, qat)); try { dijkstra_shortest_paths(g, s, weight_map(wm).vertex_index_map(im). visitor(dv)); } catch (cdc_exception) {} optional result; // Was the solution found? if (pred[t] != edge_descriptor()) { // The cost of the shortest path. value_initialized cost; // The path found. path_type path; // Trace the solution to the source. vertex_descriptor c = t; while (c != s) { const edge_descriptor &e = pred[c]; // Build the path. path.push_front(e); // Calculate the cost of the path. cost += get(wm, e); // Find the predecessing vertex. c = source(e, g); } result = std::make_pair(cost, path); } return result; } } // boost #endif /* BOOST_GRAPH_CUSTOM_DIJKSTRA_CALL */