<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>dijkstra.h Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
<link href="tabs.css" rel="stylesheet" type="text/css">
</head><body>
<div align="left"><a href="http://www.mrpt.org/">Main MRPT website</a> > <b>C++ reference</b> </div>
<div align="right">
<a href="index.html"><img border="0" src="mrpt_logo.png" alt="MRPT logo"></a>
</div>
<!-- Generated by Doxygen 1.7.5 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
<div id="navrow1" class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="modules.html"><span>Modules</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li><a href="annotated.html"><span>Classes</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
<li>
<div id="MSearchBox" class="MSearchBoxInactive">
<div class="left">
<form id="FSearchBox" action="search.php" method="get">
<img id="MSearchSelect" src="search/mag.png" alt=""/>
<input type="text" id="MSearchField" name="query" value="Search" size="20" accesskey="S"
onfocus="searchBox.OnSearchFieldFocus(true)"
onblur="searchBox.OnSearchFieldFocus(false)"/>
</form>
</div><div class="right"></div>
</div>
</li>
</ul>
</div>
<div id="navrow2" class="tabs2">
<ul class="tablist">
<li><a href="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>File Members</span></a></li>
</ul>
</div>
<div class="header">
<div class="headertitle">
<div class="title">dijkstra.h</div> </div>
</div>
<div class="contents">
<a href="dijkstra_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/* +---------------------------------------------------------------------------+</span>
<a name="l00002"></a>00002 <span class="comment"> | The Mobile Robot Programming Toolkit (MRPT) C++ library |</span>
<a name="l00003"></a>00003 <span class="comment"> | |</span>
<a name="l00004"></a>00004 <span class="comment"> | http://www.mrpt.org/ |</span>
<a name="l00005"></a>00005 <span class="comment"> | |</span>
<a name="l00006"></a>00006 <span class="comment"> | Copyright (C) 2005-2011 University of Malaga |</span>
<a name="l00007"></a>00007 <span class="comment"> | |</span>
<a name="l00008"></a>00008 <span class="comment"> | This software was written by the Machine Perception and Intelligent |</span>
<a name="l00009"></a>00009 <span class="comment"> | Robotics Lab, University of Malaga (Spain). |</span>
<a name="l00010"></a>00010 <span class="comment"> | Contact: Jose-Luis Blanco <jlblanco@ctima.uma.es> |</span>
<a name="l00011"></a>00011 <span class="comment"> | |</span>
<a name="l00012"></a>00012 <span class="comment"> | This file is part of the MRPT project. |</span>
<a name="l00013"></a>00013 <span class="comment"> | |</span>
<a name="l00014"></a>00014 <span class="comment"> | MRPT is free software: you can redistribute it and/or modify |</span>
<a name="l00015"></a>00015 <span class="comment"> | it under the terms of the GNU General Public License as published by |</span>
<a name="l00016"></a>00016 <span class="comment"> | the Free Software Foundation, either version 3 of the License, or |</span>
<a name="l00017"></a>00017 <span class="comment"> | (at your option) any later version. |</span>
<a name="l00018"></a>00018 <span class="comment"> | |</span>
<a name="l00019"></a>00019 <span class="comment"> | MRPT is distributed in the hope that it will be useful, |</span>
<a name="l00020"></a>00020 <span class="comment"> | but WITHOUT ANY WARRANTY; without even the implied warranty of |</span>
<a name="l00021"></a>00021 <span class="comment"> | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |</span>
<a name="l00022"></a>00022 <span class="comment"> | GNU General Public License for more details. |</span>
<a name="l00023"></a>00023 <span class="comment"> | |</span>
<a name="l00024"></a>00024 <span class="comment"> | You should have received a copy of the GNU General Public License |</span>
<a name="l00025"></a>00025 <span class="comment"> | along with MRPT. If not, see <http://www.gnu.org/licenses/>. |</span>
<a name="l00026"></a>00026 <span class="comment"> | |</span>
<a name="l00027"></a>00027 <span class="comment"> +---------------------------------------------------------------------------+ */</span>
<a name="l00028"></a>00028 <span class="preprocessor">#ifndef MRPT_DIJKSTRA_H</span>
<a name="l00029"></a>00029 <span class="preprocessor"></span><span class="preprocessor">#define MRPT_DIJKSTRA_H</span>
<a name="l00030"></a>00030 <span class="preprocessor"></span>
<a name="l00031"></a>00031 <span class="preprocessor">#include <<a class="code" href="_c_directed_graph_8h.html">mrpt/graphs/CDirectedGraph.h</a>></span>
<a name="l00032"></a>00032 <span class="preprocessor">#include <<a class="code" href="_c_directed_tree_8h.html">mrpt/graphs/CDirectedTree.h</a>></span>
<a name="l00033"></a>00033 <span class="preprocessor">#include <<a class="code" href="stl__extensions_8h.html">mrpt/utils/stl_extensions.h</a>></span>
<a name="l00034"></a>00034
<a name="l00035"></a>00035 <span class="keyword">namespace </span>mrpt
<a name="l00036"></a>00036 {
<a name="l00037"></a>00037 <span class="keyword">namespace </span>graphs
<a name="l00038"></a>00038 {
<a name="l00039"></a>00039 <span class="keyword">using namespace </span>std;
<a name="l00040"></a>00040 <span class="keyword">using namespace </span>mrpt::utils;
<a name="l00041"></a>00041 <span class="comment"></span>
<a name="l00042"></a>00042 <span class="comment"> /** The Dijkstra algorithm for finding the shortest path between a given source node in a (weighted) directed graph and all other nodes in the form of a tree.</span>
<a name="l00043"></a>00043 <span class="comment"> * The constructor takes as input the graph (the set of directed edges) computes all the needed data, then</span>
<a name="l00044"></a>00044 <span class="comment"> * successive calls to \a getShortestPathTo return the paths efficiently from the root.</span>
<a name="l00045"></a>00045 <span class="comment"> * The entire generated tree can be also retrieved with \a getTreeGraph.</span>
<a name="l00046"></a>00046 <span class="comment"> *</span>
<a name="l00047"></a>00047 <span class="comment"> * Input graphs are represented by instances of (or classes derived from) mrpt::graphs::CDirectedGraph, and node's IDs are uint64_t values,</span>
<a name="l00048"></a>00048 <span class="comment"> * although the type mrpt::utils::TNodeID is also provided for clarity in the code.</span>
<a name="l00049"></a>00049 <span class="comment"> *</span>
<a name="l00050"></a>00050 <span class="comment"> * The second template argument MAPS_IMPLEMENTATION allows choosing between a sparse std::map<> representation (using mrpt::utils::map_traits_stdmap)</span>
<a name="l00051"></a>00051 <span class="comment"> * for several intermediary and final results, and an alternative (using mrpt::utils::map_traits_map_as_vector as argument)</span>
<a name="l00052"></a>00052 <span class="comment"> * dense implementation which is much faster, but can be only used if the TNodeID's start in 0 or a low value.</span>
<a name="l00053"></a>00053 <span class="comment"> *</span>
<a name="l00054"></a>00054 <span class="comment"> * See <a href="http://www.mrpt.org/Example:Dijkstra_optimal_path_search_in_graphs" > this page </a> for a complete example.</span>
<a name="l00055"></a>00055 <span class="comment"> * \ingroup mrpt_graphs_grp</span>
<a name="l00056"></a>00056 <span class="comment"> */</span>
<a name="l00057"></a>00057 <span class="comment">//Was: template<class TYPE_EDGES, class MAPS_IMPLEMENTATION = map_traits_stdmap ></span>
<a name="l00058"></a>00058 <span class="keyword">template</span><<span class="keyword">class</span> TYPE_GRAPH, <span class="keyword">class</span> MAPS_IMPLEMENTATION = map_traits_stdmap >
<a name="l00059"></a>00059 <span class="keyword">class </span>CDijkstra
<a name="l00060"></a>00060 {
<a name="l00061"></a>00061 <span class="keyword">protected</span>:<span class="comment"></span>
<a name="l00062"></a>00062 <span class="comment"> /** Auxiliary struct for topological distances from root node */</span>
<a name="l00063"></a>00063 <span class="keyword">struct </span>TDistance
<a name="l00064"></a>00064 {
<a name="l00065"></a><a class="code" href="structmrpt_1_1graphs_1_1_c_dijkstra_1_1_t_distance.html#a541a2d5e504084ea2a9470e364c393d5">00065</a> <span class="keywordtype">double</span> <a class="code" href="structmrpt_1_1graphs_1_1_c_dijkstra_1_1_t_distance.html#a541a2d5e504084ea2a9470e364c393d5">dist</a>;
<a name="l00066"></a><a class="code" href="structmrpt_1_1graphs_1_1_c_dijkstra_1_1_t_distance.html#afced0a067a912ee2074944e83ae2f513">00066</a> <span class="keyword">inline</span> <a class="code" href="structmrpt_1_1graphs_1_1_c_dijkstra_1_1_t_distance.html#afced0a067a912ee2074944e83ae2f513">TDistance</a>() : dist( std::numeric_limits<double>::max() ) { }
<a name="l00067"></a><a class="code" href="structmrpt_1_1graphs_1_1_c_dijkstra_1_1_t_distance.html#a749c11f73546b848011ba05f08cb5ef2">00067</a> <span class="keyword">inline</span> <a class="code" href="structmrpt_1_1graphs_1_1_c_dijkstra_1_1_t_distance.html#a749c11f73546b848011ba05f08cb5ef2">TDistance</a>(<span class="keyword">const</span> <span class="keywordtype">double</span> D) : dist(D) { }
<a name="l00068"></a><a class="code" href="structmrpt_1_1graphs_1_1_c_dijkstra_1_1_t_distance.html#ae52fc5ce5181342b76123d99a461b3b8">00068</a> <span class="keyword">inline</span> <span class="keyword">const</span> <a class="code" href="structmrpt_1_1graphs_1_1_c_dijkstra_1_1_t_distance.html" title="Auxiliary struct for topological distances from root node.">TDistance</a> & operator =(<span class="keyword">const</span> <span class="keywordtype">double</span> D) { dist = D; <span class="keywordflow">return</span> *<span class="keyword">this</span>;}
<a name="l00069"></a>00069 };
<a name="l00070"></a>00070 <span class="comment"></span>
<a name="l00071"></a>00071 <span class="comment"> /** Auxiliary struct for backward paths */</span>
<a name="l00072"></a>00072 <span class="keyword">struct </span>TPrevious
<a name="l00073"></a>00073 {
<a name="l00074"></a><a class="code" href="structmrpt_1_1graphs_1_1_c_dijkstra_1_1_t_previous.html#a9872c6332dc0d10e66d3b4a3510d6207">00074</a> <span class="keyword">inline</span> <a class="code" href="structmrpt_1_1graphs_1_1_c_dijkstra_1_1_t_previous.html#a9872c6332dc0d10e66d3b4a3510d6207">TPrevious</a>() : id( <a class="code" href="base_2include_2mrpt_2utils_2types_8h.html#adc1f75e937273167bcd0a11caf344fce">INVALID_NODEID</a> ) { }
<a name="l00075"></a><a class="code" href="structmrpt_1_1graphs_1_1_c_dijkstra_1_1_t_previous.html#ae8a92af903d5d86583555fdc169cbb36">00075</a> <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> <a class="code" href="structmrpt_1_1graphs_1_1_c_dijkstra_1_1_t_previous.html#ae8a92af903d5d86583555fdc169cbb36">id</a>;
<a name="l00076"></a>00076 };
<a name="l00077"></a>00077
<a name="l00078"></a>00078 <span class="comment">// Cached input data:</span>
<a name="l00079"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#af52585f2d062804741818d519cddabb0">00079</a> <span class="keyword">const</span> TYPE_GRAPH & <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#af52585f2d062804741818d519cddabb0">m_cached_graph</a>;
<a name="l00080"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#adeae3a44444d148bf2e850fd3da686e9">00080</a> <span class="keyword">const</span> <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#adeae3a44444d148bf2e850fd3da686e9">m_source_node_ID</a>;
<a name="l00081"></a>00081
<a name="l00082"></a>00082 <span class="comment">// Private typedefs:</span>
<a name="l00083"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a9e7e94b5f4018e9c16bc570ce4d45428">00083</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> MAPS_IMPLEMENTATION::template <a class="code" href="classstd_1_1map.html" title="STL class.">map<TNodeID, std::set<TNodeID></a> > <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a9e7e94b5f4018e9c16bc570ce4d45428" title="A std::map (or a similar container according to MAPS_IMPLEMENTATION) with all the neighbors of every ...">list_all_neighbors_t</a>; <span class="comment">//!< A std::map (or a similar container according to MAPS_IMPLEMENTATION) with all the neighbors of every node.</span>
<a name="l00084"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a4a213405545ae6e0f3ed7190a1f364a1">00084</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> MAPS_IMPLEMENTATION::template <a class="code" href="classstd_1_1map.html">map<TNodeID,TPairNodeIDs></a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a4a213405545ae6e0f3ed7190a1f364a1">id2pairIDs_map_t</a>;
<a name="l00085"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a070c22b796e3e9c049bc4e862f5c0f75">00085</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> MAPS_IMPLEMENTATION::template <a class="code" href="classstd_1_1map.html">map<TNodeID,TDistance></a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a070c22b796e3e9c049bc4e862f5c0f75">id2dist_map_t</a>;
<a name="l00086"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#af187ca2211e827942ca720216f91b0fa">00086</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> MAPS_IMPLEMENTATION::template <a class="code" href="classstd_1_1map.html">map<TNodeID,TPrevious></a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#af187ca2211e827942ca720216f91b0fa">id2id_map_t</a>;
<a name="l00087"></a>00087
<a name="l00088"></a>00088 <span class="comment">// Intermediary and final results:</span>
<a name="l00089"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#abeaf8359121cd18fabd5133800fb7d5d">00089</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a070c22b796e3e9c049bc4e862f5c0f75">id2dist_map_t</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#abeaf8359121cd18fabd5133800fb7d5d" title="All the distances.">m_distances</a>; <span class="comment">//!< All the distances</span>
<a name="l00090"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a6b050a04c01a4c3d5caaaffaeb9dd30d">00090</a> <span class="comment"></span> std<a class="code" href="classstd_1_1map.html">::map<TNodeID,TDistance></a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a6b050a04c01a4c3d5caaaffaeb9dd30d">m_distances_non_visited</a>; <span class="comment">// Use a std::map here in all cases.</span>
<a name="l00091"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a602b64b80a61122fd64c46ecc47986ba">00091</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#af187ca2211e827942ca720216f91b0fa">id2id_map_t</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a602b64b80a61122fd64c46ecc47986ba">m_prev_node</a>;
<a name="l00092"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#af932bdf8bab5eb152811d211cbaf3e59">00092</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a4a213405545ae6e0f3ed7190a1f364a1">id2pairIDs_map_t</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#af932bdf8bab5eb152811d211cbaf3e59">m_prev_arc</a>;
<a name="l00093"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a9ac1ecc52cba8d70aa77f4eef5c01322">00093</a> std<a class="code" href="classstd_1_1set.html">::set<TNodeID></a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a9ac1ecc52cba8d70aa77f4eef5c01322">m_lstNode_IDs</a>;
<a name="l00094"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#af4e60d2189650038dda97b28b866cf0f">00094</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a9e7e94b5f4018e9c16bc570ce4d45428" title="A std::map (or a similar container according to MAPS_IMPLEMENTATION) with all the neighbors of every ...">list_all_neighbors_t</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#af4e60d2189650038dda97b28b866cf0f">m_allNeighbors</a>;
<a name="l00095"></a>00095
<a name="l00096"></a>00096 <span class="keyword">public</span>:<span class="comment"></span>
<a name="l00097"></a>00097 <span class="comment"> /** @name Useful typedefs</span>
<a name="l00098"></a>00098 <span class="comment"> @{ */</span>
<a name="l00099"></a>00099
<a name="l00100"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a2fd492f10b06ce86db21006d1e4776fb">00100</a> <span class="keyword">typedef</span> TYPE_GRAPH <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a2fd492f10b06ce86db21006d1e4776fb" title="The type of the graph, typically a mrpt::graphs::CDirectedGraph<> or any other derived class...">graph_t</a>; <span class="comment">//!< The type of the graph, typically a mrpt::graphs::CDirectedGraph<> or any other derived class</span>
<a name="l00101"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a8c5b974cf6bcafbc9d71d3e0291c4fda">00101</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a2fd492f10b06ce86db21006d1e4776fb" title="The type of the graph, typically a mrpt::graphs::CDirectedGraph<> or any other derived class...">graph_t</a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a8c5b974cf6bcafbc9d71d3e0291c4fda" title="The type of edge data in graph_t.">::edge_t</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a8c5b974cf6bcafbc9d71d3e0291c4fda" title="The type of edge data in graph_t.">edge_t</a>; <span class="comment">//!< The type of edge data in graph_t</span>
<a name="l00102"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#ac88e78f980cdc8a6052ac190c2013f05">00102</a> <span class="comment"></span> <span class="keyword">typedef</span> std<a class="code" href="classstd_1_1list.html" title="STL class.">::list<TPairNodeIDs></a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#ac88e78f980cdc8a6052ac190c2013f05" title="A list of edges used to describe a path on the graph.">edge_list_t</a>; <span class="comment">//!< A list of edges used to describe a path on the graph</span>
<a name="l00103"></a>00103 <span class="comment"></span><span class="comment"></span>
<a name="l00104"></a>00104 <span class="comment"> /** @} */</span>
<a name="l00105"></a>00105 <span class="comment"></span>
<a name="l00106"></a>00106 <span class="comment"> /** Constructor, which takes the input graph and executes the entire Dijkstra algorithm from the given root node ID.</span>
<a name="l00107"></a>00107 <span class="comment"> *</span>
<a name="l00108"></a>00108 <span class="comment"> * The graph is given by the set of directed edges, stored in a mrpt::graphs::CDirectedGraph class.</span>
<a name="l00109"></a>00109 <span class="comment"> *</span>
<a name="l00110"></a>00110 <span class="comment"> * If a function \a functor_edge_weight is provided, it will be used to compute the weight of edges.</span>
<a name="l00111"></a>00111 <span class="comment"> * Otherwise, all edges weight the unity.</span>
<a name="l00112"></a>00112 <span class="comment"> *</span>
<a name="l00113"></a>00113 <span class="comment"> * After construction, call \a getShortestPathTo to get the shortest path to a node or \a getTreeGraph for the tree representation.</span>
<a name="l00114"></a>00114 <span class="comment"> *</span>
<a name="l00115"></a>00115 <span class="comment"> * \sa getShortestPathTo, getTreeGraph</span>
<a name="l00116"></a>00116 <span class="comment"> * \exception std::exception If the source nodeID is not found in the graph</span>
<a name="l00117"></a>00117 <span class="comment"> */</span>
<a name="l00118"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a17f4737da51b1f3822fcf5ef78543a4c">00118</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html" title="The Dijkstra algorithm for finding the shortest path between a given source node in a (weighted) dire...">CDijkstra</a>(
<a name="l00119"></a>00119 <span class="keyword">const</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a2fd492f10b06ce86db21006d1e4776fb" title="The type of the graph, typically a mrpt::graphs::CDirectedGraph<> or any other derived class...">graph_t</a> &graph,
<a name="l00120"></a>00120 <span class="keyword">const</span> <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> source_node_ID,
<a name="l00121"></a>00121 <span class="keywordtype">double</span> (*functor_edge_weight)(<span class="keyword">const</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a2fd492f10b06ce86db21006d1e4776fb" title="The type of the graph, typically a mrpt::graphs::CDirectedGraph<> or any other derived class...">graph_t</a>& graph, <span class="keyword">const</span> <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> id_from, <span class="keyword">const</span> <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> id_to, <span class="keyword">const</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a8c5b974cf6bcafbc9d71d3e0291c4fda" title="The type of edge data in graph_t.">edge_t</a> &edge) = NULL,
<a name="l00122"></a>00122 <span class="keywordtype">void</span> (*functor_on_progress)(<span class="keyword">const</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a2fd492f10b06ce86db21006d1e4776fb" title="The type of the graph, typically a mrpt::graphs::CDirectedGraph<> or any other derived class...">graph_t</a>& graph, <span class="keywordtype">size_t</span> visitedCount) = NULL
<a name="l00123"></a>00123 )
<a name="l00124"></a>00124 : m_cached_graph(graph), m_source_node_ID(source_node_ID)
<a name="l00125"></a>00125 {
<a name="l00126"></a>00126 <a class="code" href="mrpt__macros_8h.html#a45b840af519f33816311acdbb28d7c10">MRPT_START</a>
<a name="l00127"></a>00127 <span class="comment">/*</span>
<a name="l00128"></a>00128 <span class="comment"> 1 function Dijkstra(G, w, s)</span>
<a name="l00129"></a>00129 <span class="comment"> 2 for each vertex v in V[G] // Initializations</span>
<a name="l00130"></a>00130 <span class="comment"> 3 m_distances[v] := infinity</span>
<a name="l00131"></a>00131 <span class="comment"> 4 m_prev_node[v] := undefined</span>
<a name="l00132"></a>00132 <span class="comment"> 5 m_distances[s] := 0</span>
<a name="l00133"></a>00133 <span class="comment"> 6 S := empty set</span>
<a name="l00134"></a>00134 <span class="comment"> 7 Q := V[G]</span>
<a name="l00135"></a>00135 <span class="comment"> 8 while Q is not an empty set // The algorithm itself</span>
<a name="l00136"></a>00136 <span class="comment"> 9 u := Extract_Min(Q)</span>
<a name="l00137"></a>00137 <span class="comment"> 10 S := S union {u}</span>
<a name="l00138"></a>00138 <span class="comment"> 11 for each edge (u,v) outgoing from u</span>
<a name="l00139"></a>00139 <span class="comment"> 12 if m_distances[u] + w(u,v) < m_distances[v] // Relax (u,v)</span>
<a name="l00140"></a>00140 <span class="comment"> 13 m_distances[v] := m_distances[u] + w(u,v)</span>
<a name="l00141"></a>00141 <span class="comment"> 14 m_prev_node[v] := u</span>
<a name="l00142"></a>00142 <span class="comment"> */</span>
<a name="l00143"></a>00143
<a name="l00144"></a>00144 <span class="comment">// Makea list of all the nodes in the graph:</span>
<a name="l00145"></a>00145 graph.getAllNodes( m_lstNode_IDs );
<a name="l00146"></a>00146 <span class="keyword">const</span> <span class="keywordtype">size_t</span> nNodes = m_lstNode_IDs.size();
<a name="l00147"></a>00147
<a name="l00148"></a>00148 <span class="keywordflow">if</span> ( m_lstNode_IDs.find(source_node_ID)==m_lstNode_IDs.end() )
<a name="l00149"></a>00149 <a class="code" href="mrpt__macros_8h.html#a61a8d46146210ee20fa1ff423257a5ec">THROW_EXCEPTION_CUSTOM_MSG1</a>(<span class="stringliteral">"Cannot find the source node_ID=%u in the graph"</span>,static_cast<unsigned int>(source_node_ID));
<a name="l00150"></a>00150
<a name="l00151"></a>00151 <span class="comment">// Init:</span>
<a name="l00152"></a>00152 <span class="comment">// m_distances: already initialized to infinity by default.</span>
<a name="l00153"></a>00153 <span class="comment">// m_prev_node: idem</span>
<a name="l00154"></a>00154 <span class="comment">// m_prev_arc: idem</span>
<a name="l00155"></a>00155 <span class="comment">// m_visited: idem</span>
<a name="l00156"></a>00156 <span class="keywordtype">size_t</span> visitedCount = 0;
<a name="l00157"></a>00157 m_distances [source_node_ID] = 0;
<a name="l00158"></a>00158 m_distances_non_visited[source_node_ID] = 0;
<a name="l00159"></a>00159
<a name="l00160"></a>00160 <span class="comment">// Precompute all neighbors:</span>
<a name="l00161"></a>00161 graph.getAdjacencyMatrix(m_allNeighbors);
<a name="l00162"></a>00162
<a name="l00163"></a>00163 <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> u;
<a name="l00164"></a>00164 <span class="keywordflow">do</span> <span class="comment">// The algorithm:</span>
<a name="l00165"></a>00165 {
<a name="l00166"></a>00166 <span class="comment">// Find the nodeID with the minimum known distance so far considered:</span>
<a name="l00167"></a>00167 <span class="keywordtype">double</span> min_d = std::numeric_limits<double>::max();
<a name="l00168"></a>00168 u = <a class="code" href="base_2include_2mrpt_2utils_2types_8h.html#adc1f75e937273167bcd0a11caf344fce">INVALID_NODEID</a>;
<a name="l00169"></a>00169
<a name="l00170"></a>00170 <span class="comment">// No need to check if the min. distance node is not visited yet, since we</span>
<a name="l00171"></a>00171 <span class="comment">// keep two lists: m_distances_non_visited & m_distances</span>
<a name="l00172"></a>00172 <span class="keywordflow">for</span> (<span class="keyword">typename</span> <a class="code" href="classstd_1_1map_1_1const__iterator.html" title="STL iterator class.">std::map<TNodeID,TDistance>::const_iterator</a> itDist=m_distances_non_visited.begin();itDist!=m_distances_non_visited.end();++itDist)
<a name="l00173"></a>00173 {
<a name="l00174"></a>00174 <span class="keywordflow">if</span> (itDist->second.dist < min_d)
<a name="l00175"></a>00175 {
<a name="l00176"></a>00176 u = itDist->first;
<a name="l00177"></a>00177 min_d = itDist->second.dist;
<a name="l00178"></a>00178 }
<a name="l00179"></a>00179 }
<a name="l00180"></a>00180 <a class="code" href="mrpt__macros_8h.html#ad30ea0382c594c0e2efe88212e9352b0">ASSERTMSG_</a>(u!=<a class="code" href="base_2include_2mrpt_2utils_2types_8h.html#adc1f75e937273167bcd0a11caf344fce">INVALID_NODEID</a>, <span class="stringliteral">"Graph is not fully connected!"</span>)
<a name="l00181"></a>00181
<a name="l00182"></a>00182 <span class="comment">// Save distance (for possible future reference...) and remove this node from "non-visited":</span>
<a name="l00183"></a>00183 m_distances[u]=m_distances_non_visited[u];
<a name="l00184"></a>00184 m_distances_non_visited.erase(u);
<a name="l00185"></a>00185
<a name="l00186"></a>00186 visitedCount++;
<a name="l00187"></a>00187
<a name="l00188"></a>00188 <span class="comment">// Let the user know about our progress...</span>
<a name="l00189"></a>00189 <span class="keywordflow">if</span> (functor_on_progress) (*functor_on_progress)(graph,visitedCount);
<a name="l00190"></a>00190
<a name="l00191"></a>00191 <span class="comment">// For each arc from "u":</span>
<a name="l00192"></a>00192 <span class="keyword">const</span> std<a class="code" href="classstd_1_1set.html">::set<TNodeID></a> & neighborsOfU = m_allNeighbors[u]; <span class="comment">//graph.getNeighborsOf(u,neighborsOfU);</span>
<a name="l00193"></a>00193 <span class="keywordflow">for</span> (<a class="code" href="classstd_1_1set_1_1const__iterator.html" title="STL iterator class.">std::set<TNodeID>::const_iterator</a> itNei=neighborsOfU.begin();itNei!=neighborsOfU.end();++itNei)
<a name="l00194"></a>00194 {
<a name="l00195"></a>00195 <span class="keyword">const</span> <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> i = *itNei;
<a name="l00196"></a>00196 <span class="keywordflow">if</span> (i==u) <span class="keywordflow">continue</span>; <span class="comment">// ignore self-loops...</span>
<a name="l00197"></a>00197
<a name="l00198"></a>00198 <span class="comment">// the "edge_ui" may be searched here or a bit later, so the "bool" var will tell us.</span>
<a name="l00199"></a>00199 <span class="keyword">typename</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a2fd492f10b06ce86db21006d1e4776fb" title="The type of the graph, typically a mrpt::graphs::CDirectedGraph<> or any other derived class...">graph_t</a><a class="code" href="eigen__plugins_8h.html#a8dbda719917732693c56cee228465ed9">::const_iterator</a> edge_ui;
<a name="l00200"></a>00200 <span class="keywordtype">bool</span> edge_ui_reverse = <span class="keyword">false</span>;
<a name="l00201"></a>00201 <span class="keywordtype">bool</span> edge_ui_found = <span class="keyword">false</span>;
<a name="l00202"></a>00202
<a name="l00203"></a>00203 <span class="comment">// Get weight of edge u<->i</span>
<a name="l00204"></a>00204 <span class="keywordtype">double</span> edge_ui_weight;
<a name="l00205"></a>00205 <span class="keywordflow">if</span> (!functor_edge_weight)
<a name="l00206"></a>00206 edge_ui_weight = 1.;
<a name="l00207"></a>00207 <span class="keywordflow">else</span>
<a name="l00208"></a>00208 { <span class="comment">// edge may be i->u or u->i:</span>
<a name="l00209"></a>00209 edge_ui = graph.edges.find( make_pair(u,i) );
<a name="l00210"></a>00210 <span class="keywordflow">if</span> ( edge_ui==graph.edges.end() )
<a name="l00211"></a>00211 {
<a name="l00212"></a>00212 edge_ui = graph.edges.find( make_pair(i,u));
<a name="l00213"></a>00213 edge_ui_reverse = <span class="keyword">true</span>;
<a name="l00214"></a>00214 }
<a name="l00215"></a>00215 <a class="code" href="mrpt__macros_8h.html#a47eb5a445c2bf3d9190396510ea9683e">ASSERT_</a>(edge_ui!=graph.edges.end());
<a name="l00216"></a>00216 edge_ui_weight = (*functor_edge_weight)( graph, edge_ui->first.first,edge_ui->first.second, edge_ui->second );
<a name="l00217"></a>00217 edge_ui_found = <span class="keyword">true</span>;
<a name="l00218"></a>00218 }
<a name="l00219"></a>00219
<a name="l00220"></a>00220 <span class="keywordflow">if</span> ( (min_d+edge_ui_weight) < m_distances[i].dist) <span class="comment">// the [] creates the entry if needed</span>
<a name="l00221"></a>00221 {
<a name="l00222"></a>00222 m_distances[i].dist = m_distances_non_visited[i].dist = min_d+edge_ui_weight;
<a name="l00223"></a>00223 m_prev_node[i].id = u;
<a name="l00224"></a>00224 <span class="comment">// If still not done above, detect the direction of the arc now:</span>
<a name="l00225"></a>00225 <span class="keywordflow">if</span> (!edge_ui_found)
<a name="l00226"></a>00226 {
<a name="l00227"></a>00227 edge_ui = graph.edges.find( make_pair(u,i) );
<a name="l00228"></a>00228 <span class="keywordflow">if</span> ( edge_ui==graph.edges.end() ) {
<a name="l00229"></a>00229 edge_ui = graph.edges.find( make_pair(i,u));
<a name="l00230"></a>00230 edge_ui_reverse = <span class="keyword">true</span>;
<a name="l00231"></a>00231 }
<a name="l00232"></a>00232 <a class="code" href="mrpt__macros_8h.html#a47eb5a445c2bf3d9190396510ea9683e">ASSERT_</a>(edge_ui!=graph.edges.end());
<a name="l00233"></a>00233 }
<a name="l00234"></a>00234
<a name="l00235"></a>00235 <span class="keywordflow">if</span> ( !edge_ui_reverse )
<a name="l00236"></a>00236 m_prev_arc[i] = make_pair(u,i); <span class="comment">// *u -> *i</span>
<a name="l00237"></a>00237 <span class="keywordflow">else</span> m_prev_arc[i] = make_pair(i,u); <span class="comment">// *i -> *u</span>
<a name="l00238"></a>00238 }
<a name="l00239"></a>00239 }
<a name="l00240"></a>00240 } <span class="keywordflow">while</span> ( visitedCount<nNodes );
<a name="l00241"></a>00241
<a name="l00242"></a>00242 <a class="code" href="mrpt__macros_8h.html#a88a917260793b56abd83ad2a0d849eb1">MRPT_END</a>
<a name="l00243"></a>00243 } <span class="comment">// end Dijkstra</span>
<a name="l00244"></a>00244
<a name="l00245"></a>00245 <span class="comment"></span>
<a name="l00246"></a>00246 <span class="comment"> /** @name Query Dijkstra results</span>
<a name="l00247"></a>00247 <span class="comment"> @{ */</span>
<a name="l00248"></a>00248 <span class="comment"></span>
<a name="l00249"></a>00249 <span class="comment"> /** Return the distance from the root node to any other node using the Dijkstra-generated tree \exception std::exception On unknown node ID</span>
<a name="l00250"></a>00250 <span class="comment"> */</span>
<a name="l00251"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a880c48bfb47f65da4a6fa46bfa93a456">00251</a> <span class="keyword">inline</span> <span class="keywordtype">double</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a880c48bfb47f65da4a6fa46bfa93a456" title="Return the distance from the root node to any other node using the Dijkstra-generated tree On unknown...">getNodeDistanceToRoot</a>(<span class="keyword">const</span> <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> <span class="keywordtype">id</span>)<span class="keyword"> const </span>{
<a name="l00252"></a>00252 <span class="keyword">typename</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a070c22b796e3e9c049bc4e862f5c0f75">id2dist_map_t</a><a class="code" href="eigen__plugins_8h.html#a8dbda719917732693c56cee228465ed9">::const_iterator</a> it=m_distances.find(<span class="keywordtype">id</span>);
<a name="l00253"></a>00253 <span class="keywordflow">if</span> (it==m_distances.end()) <a class="code" href="mrpt__macros_8h.html#aaa3f404ea85a6575a7139f8d101370ba">THROW_EXCEPTION</a>(<span class="stringliteral">"Node was not found in the graph when running Dijkstra"</span>);
<a name="l00254"></a>00254 <span class="keywordflow">return</span> it->second.dist;
<a name="l00255"></a>00255 }
<a name="l00256"></a>00256 <span class="comment"></span>
<a name="l00257"></a>00257 <span class="comment"> /** Return the set of all known node IDs (actually, a const ref to the internal set object). */</span>
<a name="l00258"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a9f59bf4dd2a2a3d2eb76cb8cf1dffd68">00258</a> <span class="keyword">inline</span> <span class="keyword">const</span> std<a class="code" href="classstd_1_1set.html">::set<TNodeID></a> & <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a9f59bf4dd2a2a3d2eb76cb8cf1dffd68" title="Return the set of all known node IDs (actually, a const ref to the internal set object).">getListOfAllNodes</a>()<span class="keyword"> const </span>{<span class="keywordflow">return</span> m_lstNode_IDs;}
<a name="l00259"></a>00259 <span class="comment"></span>
<a name="l00260"></a>00260 <span class="comment"> /** Return the node ID of the tree root, as passed in the constructor */</span>
<a name="l00261"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a2d1d2121baf359ce8c500fdb507a9a90">00261</a> <span class="keyword">inline</span> <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a2d1d2121baf359ce8c500fdb507a9a90" title="Return the node ID of the tree root, as passed in the constructor.">getRootNodeID</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> m_source_node_ID; }
<a name="l00262"></a>00262 <span class="comment"></span>
<a name="l00263"></a>00263 <span class="comment"> /** Return the adjacency matrix of the input graph, which is cached at construction so if needed later just use this copy to avoid recomputing it \sa mrpt::graphs::CDirectedGraph::getAdjacencyMatrix */</span>
<a name="l00264"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a8cab529e1aaa9ba013087f896b21dfd3">00264</a> <span class="keyword">inline</span> <span class="keyword">const</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a9e7e94b5f4018e9c16bc570ce4d45428" title="A std::map (or a similar container according to MAPS_IMPLEMENTATION) with all the neighbors of every ...">list_all_neighbors_t</a> & <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a8cab529e1aaa9ba013087f896b21dfd3" title="Return the adjacency matrix of the input graph, which is cached at construction so if needed later ju...">getCachedAdjacencyMatrix</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> m_allNeighbors; }
<a name="l00265"></a>00265 <span class="comment"></span>
<a name="l00266"></a>00266 <span class="comment"> /** Returns the shortest path between the source node passed in the constructor and the given target node.</span>
<a name="l00267"></a>00267 <span class="comment"> * The reconstructed path contains a list of arcs (all of them exist in the graph with the given direction), such as the</span>
<a name="l00268"></a>00268 <span class="comment"> * the first edge starts at the origin passed in the constructor, and the last one contains the given target.</span>
<a name="l00269"></a>00269 <span class="comment"> *</span>
<a name="l00270"></a>00270 <span class="comment"> * \note An empty list of edges is returned when target equals the source node.</span>
<a name="l00271"></a>00271 <span class="comment"> * \sa getTreeGraph</span>
<a name="l00272"></a>00272 <span class="comment"> */</span>
<a name="l00273"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#ad3bd1fc3783ea4feeab29073501733c9">00273</a> <span class="keywordtype">void</span> getShortestPathTo(
<a name="l00274"></a>00274 <span class="keyword">const</span> <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> target_node_ID,
<a name="l00275"></a>00275 <a class="code" href="classstd_1_1list.html" title="STL class.">edge_list_t</a> &out_path
<a name="l00276"></a>00276 )<span class="keyword"> const</span>
<a name="l00277"></a>00277 <span class="keyword"> </span>{
<a name="l00278"></a>00278 out_path.clear();
<a name="l00279"></a>00279 <span class="keywordflow">if</span> (target_node_ID==m_source_node_ID) <span class="keywordflow">return</span>;
<a name="l00280"></a>00280
<a name="l00281"></a>00281 <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> nod = target_node_ID;
<a name="l00282"></a>00282 <span class="keywordflow">do</span>
<a name="l00283"></a>00283 {
<a name="l00284"></a>00284 <span class="keyword">typename</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a4a213405545ae6e0f3ed7190a1f364a1">id2pairIDs_map_t</a><a class="code" href="eigen__plugins_8h.html#a8dbda719917732693c56cee228465ed9">::const_iterator</a> it = m_prev_arc.find(nod);
<a name="l00285"></a>00285 <a class="code" href="mrpt__macros_8h.html#a47eb5a445c2bf3d9190396510ea9683e">ASSERT_</a>(it!=m_prev_arc.end())
<a name="l00286"></a>00286
<a name="l00287"></a>00287 out_path.push_front( it->second );
<a name="l00288"></a>00288 nod = m_prev_node.find(nod)->second.id;
<a name="l00289"></a>00289 } <span class="keywordflow">while</span> (nod!=m_source_node_ID);
<a name="l00290"></a>00290
<a name="l00291"></a>00291 } <span class="comment">// end of getShortestPathTo</span>
<a name="l00292"></a>00292
<a name="l00293"></a>00293 <span class="comment"></span>
<a name="l00294"></a>00294 <span class="comment"> /** Type for graph returned by \a getTreeGraph: a graph like the original input graph, but with edge data being pointers to the original data (to save copy time & memory)</span>
<a name="l00295"></a>00295 <span class="comment"> */</span>
<a name="l00296"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a9c2622105686acaeb1a3fa8cc369d1a1">00296</a> <span class="keyword">typedef</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_tree.html" title="A special kind of graph in the form of a tree with directed edges and optional edge annotations of te...">CDirectedTree<const edge_t *></a> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a9c2622105686acaeb1a3fa8cc369d1a1" title="Type for graph returned by getTreeGraph: a graph like the original input graph, but with edge data be...">tree_graph_t</a>;
<a name="l00297"></a>00297 <span class="comment"></span>
<a name="l00298"></a>00298 <span class="comment"> /** Returns a tree representation of the graph, as determined by the Dijkstra shortest paths from the root node.</span>
<a name="l00299"></a>00299 <span class="comment"> * Note that the annotations on each edge in the tree are "const pointers" to the original graph edge data, so</span>
<a name="l00300"></a>00300 <span class="comment"> * it's mandatory for the original input graph not to be deleted as long as this tree is used.</span>
<a name="l00301"></a>00301 <span class="comment"> * \sa getShortestPathTo</span>
<a name="l00302"></a>00302 <span class="comment"> */</span>
<a name="l00303"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a7ee3c82616266200c491d79233c92ca8">00303</a> <span class="keywordtype">void</span> getTreeGraph( <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_tree.html" title="A special kind of graph in the form of a tree with directed edges and optional edge annotations of te...">tree_graph_t</a> &out_tree )<span class="keyword"> const</span>
<a name="l00304"></a>00304 <span class="keyword"> </span>{
<a name="l00305"></a>00305 <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_tree.html" title="A special kind of graph in the form of a tree with directed edges and optional edge annotations of te...">tree_graph_t</a>::TEdgeInfo TreeEdgeInfo;
<a name="l00306"></a>00306
<a name="l00307"></a>00307 out_tree.<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_tree.html#adc8f90b30fd8e07a984fe19b8a360b8c" title="Empty all edge data and set "root" to INVALID_NODEID.">clear</a>();
<a name="l00308"></a>00308 out_tree.<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_tree.html#abe1d11c870b7f6959c3a1ed7e80d09c6" title="The root of the tree.">root</a> = m_source_node_ID;
<a name="l00309"></a>00309 <span class="keywordflow">for</span> (<span class="keyword">typename</span> <a class="code" href="eigen__plugins_8h.html#a8dbda719917732693c56cee228465ed9">id2pairIDs_map_t::const_iterator</a> itArcs=m_prev_arc.begin();itArcs!=m_prev_arc.end();++itArcs)
<a name="l00310"></a>00310 { <span class="comment">// For each saved arc in "m_prev_arc", recover the original data in the input graph and save it to the output tree structure.</span>
<a name="l00311"></a>00311 <span class="keyword">const</span> <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> <span class="keywordtype">id</span> = itArcs->first;
<a name="l00312"></a>00312 <span class="keyword">const</span> <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> id_from = itArcs->second.first;
<a name="l00313"></a>00313 <span class="keyword">const</span> <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> id_to = itArcs->second.second;
<a name="l00314"></a>00314
<a name="l00315"></a>00315 std<a class="code" href="classstd_1_1list.html" title="STL class.">::list<TreeEdgeInfo></a> &edges = out_tree.<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_tree.html#a35deef833923a007dd80797da31854ee" title="The edges of each node.">edges_to_children</a>[<span class="keywordtype">id</span>==id_from ? id_to : id_from];
<a name="l00316"></a>00316 TreeEdgeInfo newEdge;
<a name="l00317"></a>00317 newEdge.reverse = (<span class="keywordtype">id</span>==id_from); <span class="comment">// true: root towards leafs.</span>
<a name="l00318"></a>00318 newEdge.id = id;
<a name="l00319"></a>00319 <span class="keyword">typename</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_dijkstra.html#a2fd492f10b06ce86db21006d1e4776fb" title="The type of the graph, typically a mrpt::graphs::CDirectedGraph<> or any other derived class...">graph_t</a><a class="code" href="eigen__plugins_8h.html#a8dbda719917732693c56cee228465ed9">::edges_map_t::const_iterator</a> itEdgeData = m_cached_graph.edges.find(make_pair(id_from,id_to));
<a name="l00320"></a>00320 <a class="code" href="mrpt__macros_8h.html#ad30ea0382c594c0e2efe88212e9352b0">ASSERTMSG_</a>(itEdgeData!=m_cached_graph.edges.end(),<a class="code" href="namespacemrpt.html#a3a27af794b658df5491e2b7678f8ccb8" title="A std::string version of C sprintf.">format</a>(<span class="stringliteral">"Edge %u->%u is in Dijkstra paths but not in original graph!"</span>,static_cast<unsigned int>(id_from),static_cast<unsigned int>(id_to) ))
<a name="l00321"></a>00321 newEdge.data = & itEdgeData->second;
<a name="l00322"></a>00322 edges.push_back( newEdge );
<a name="l00323"></a>00323 }
<a name="l00324"></a>00324
<a name="l00325"></a>00325 }<span class="comment">// end getTreeGraph</span>
<a name="l00326"></a>00326
<a name="l00327"></a>00327
<a name="l00328"></a>00328 <span class="comment"></span>
<a name="l00329"></a>00329 <span class="comment"> /** @} */</span>
<a name="l00330"></a>00330
<a name="l00331"></a>00331 }; <span class="comment">// end class</span>
<a name="l00332"></a>00332
<a name="l00333"></a>00333 } <span class="comment">// End of namespace</span>
<a name="l00334"></a>00334 } <span class="comment">// End of namespace</span>
<a name="l00335"></a>00335 <span class="preprocessor">#endif</span>
</pre></div></div>
</div>
<br><hr><br> <table border="0" width="100%"> <tr> <td> Page generated by <a href="http://www.doxygen.org" target="_blank">Doxygen 1.7.5</a> for MRPT 0.9.5 SVN: at Sun Sep 25 17:20:18 UTC 2011</td><td></td> <td width="100"> </td> <td width="150"> </td></tr> </table> </body></html>
