<!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>CDirectedGraph.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">CDirectedGraph.h</div> </div> </div> <div class="contents"> <a href="_c_directed_graph_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_DIRECTEDGRAPH_H</span> <a name="l00029"></a>00029 <span class="preprocessor"></span><span class="preprocessor">#define MRPT_DIRECTEDGRAPH_H</span> <a name="l00030"></a>00030 <span class="preprocessor"></span> <a name="l00031"></a>00031 <span class="preprocessor">#include <<a class="code" href="utils__defs_8h.html">mrpt/utils/utils_defs.h</a>></span> <a name="l00032"></a>00032 <span class="comment">//#include <mrpt/math/utils.h></span> <a name="l00033"></a>00033 <a name="l00034"></a>00034 <span class="comment">/*---------------------------------------------------------------</span> <a name="l00035"></a>00035 <span class="comment"> Class</span> <a name="l00036"></a>00036 <span class="comment"> ---------------------------------------------------------------*/</span> <a name="l00037"></a>00037 <span class="keyword">namespace </span>mrpt <a name="l00038"></a>00038 { <a name="l00039"></a>00039 <span class="keyword">namespace </span>graphs <a name="l00040"></a>00040 { <a name="l00041"></a>00041 <span class="keyword">using</span> mrpt<a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">::utils::TNodeID</a>; <a name="l00042"></a>00042 <span class="keyword">using</span> mrpt<a class="code" href="namespacemrpt_1_1utils.html#aee71d7beb4d61406566af3847410d0e4" title="A pair of node IDs.">::utils::TPairNodeIDs</a>; <a name="l00043"></a>00043 <span class="comment"></span> <a name="l00044"></a>00044 <span class="comment"> /** \addtogroup mrpt_graphs_grp</span> <a name="l00045"></a>00045 <span class="comment"> @{ */</span> <a name="l00046"></a>00046 <a name="l00047"></a><a class="code" href="namespacemrpt_1_1graphs_1_1detail.html">00047</a> <span class="keyword">namespace </span>detail <a name="l00048"></a>00048 {<span class="comment"></span> <a name="l00049"></a>00049 <span class="comment"> /** An empty structure */</span> <a name="l00050"></a>00050 <span class="keyword">struct </span><a class="code" href="structmrpt_1_1graphs_1_1detail_1_1edge__annotations__empty.html" title="An empty structure.">edge_annotations_empty</a> { }; <a name="l00051"></a>00051 } <a name="l00052"></a>00052 <span class="comment"></span> <a name="l00053"></a>00053 <span class="comment"> /** A directed graph with the argument of the template specifying the type of the annotations in the edges.</span> <a name="l00054"></a>00054 <span class="comment"> * This class only keeps a list of edges (in the member \a edges), so there is no information stored for each node but its existence referred by a node_ID.</span> <a name="l00055"></a>00055 <span class="comment"> *</span> <a name="l00056"></a>00056 <span class="comment"> * Note that edges are stored as a std::multimap<> to allow <b>multiple edges</b> between the same pair of nodes.</span> <a name="l00057"></a>00057 <span class="comment"> *</span> <a name="l00058"></a>00058 <span class="comment"> * \sa mrpt::math::CDijkstra, mrpt::graphs::CNetworkOfPoses, mrpt::graphs::CDirectedTree</span> <a name="l00059"></a>00059 <span class="comment"> * \ingroup mrpt_graphs_grp</span> <a name="l00060"></a>00060 <span class="comment"> */</span> <a name="l00061"></a>00061 <span class="keyword">template</span><<span class="keyword">class</span> TYPE_EDGES, <span class="keyword">class</span> EDGE_ANNOTATIONS = detail::edge_annotations_empty> <a name="l00062"></a>00062 <span class="keyword">class </span><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html" title="A directed graph with the argument of the template specifying the type of the annotations in the edge...">CDirectedGraph</a> <a name="l00063"></a>00063 { <a name="l00064"></a>00064 <span class="keyword">public</span>:<span class="comment"></span> <a name="l00065"></a>00065 <span class="comment"> /** The type of each global pose in \a nodes: an extension of the \a TYPE_EDGES pose with any optional user-defined data */</span> <a name="l00066"></a>00066 <span class="keyword">struct </span>edge_t : <span class="keyword">public</span> TYPE_EDGES, <span class="keyword">public</span> EDGE_ANNOTATIONS <a name="l00067"></a>00067 { <a name="l00068"></a>00068 <span class="comment">// Replicate possible constructors:</span> <a name="l00069"></a><a class="code" href="structmrpt_1_1graphs_1_1_c_directed_graph_1_1edge__t.html#a25c89cb2fb42eea5a08cd8a85d31a33f">00069</a> <span class="keyword">inline</span> <a class="code" href="structmrpt_1_1graphs_1_1_c_directed_graph_1_1edge__t.html#a25c89cb2fb42eea5a08cd8a85d31a33f">edge_t</a> () : TYPE_EDGES() { } <a name="l00070"></a><a class="code" href="structmrpt_1_1graphs_1_1_c_directed_graph_1_1edge__t.html#ad521f69ac88981b2ace3114e7b48c09f">00070</a> <span class="keyword">template</span> <<span class="keyword">typename</span> ARG1> <span class="keyword">inline</span> <a class="code" href="structmrpt_1_1graphs_1_1_c_directed_graph_1_1edge__t.html#ad521f69ac88981b2ace3114e7b48c09f">edge_t</a> (<span class="keyword">const</span> ARG1 &a1) : TYPE_EDGES(a1) { } <a name="l00071"></a><a class="code" href="structmrpt_1_1graphs_1_1_c_directed_graph_1_1edge__t.html#ade469aa99dddad0fc579c8138beacd65">00071</a> <span class="keyword">template</span> <<span class="keyword">typename</span> ARG1,<span class="keyword">typename</span> ARG2> <span class="keyword">inline</span> <a class="code" href="structmrpt_1_1graphs_1_1_c_directed_graph_1_1edge__t.html#ade469aa99dddad0fc579c8138beacd65">edge_t</a> (<span class="keyword">const</span> ARG1 &a1,<span class="keyword">const</span> ARG2 &a2) : TYPE_EDGES(a1,a2) { } <a name="l00072"></a>00072 }; <a name="l00073"></a>00073 <a name="l00074"></a>00074 <a name="l00075"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a61f20647604df391401a440bbcada042">00075</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> mrpt<a class="code" href="classstd_1_1multimap.html" title="STL class.">::aligned_containers<TPairNodeIDs,edge_t>::multimap_t</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a61f20647604df391401a440bbcada042" title="The type of the member edges.">edges_map_t</a>; <span class="comment">//!< The type of the member \a edges</span> <a name="l00076"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a79519246c2bf66e78eacaffa55ca0272">00076</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="classstd_1_1multimap.html" title="STL class.">edges_map_t</a><a class="code" href="classstd_1_1multimap_1_1iterator.html" title="STL iterator class.">::iterator</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a79519246c2bf66e78eacaffa55ca0272">iterator</a>; <a name="l00077"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a8acbd51f416c2688ce308c7b04a0d41e">00077</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="classstd_1_1multimap.html" title="STL class.">edges_map_t</a><a class="code" href="classstd_1_1multimap_1_1const__iterator.html" title="STL iterator class.">::const_iterator</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a8acbd51f416c2688ce308c7b04a0d41e">const_iterator</a>; <a name="l00078"></a>00078 <span class="comment"></span> <a name="l00079"></a>00079 <span class="comment"> /** The public member with the directed edges in the graph */</span> <a name="l00080"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f">00080</a> <a class="code" href="classstd_1_1multimap.html" title="STL class.">edges_map_t</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>; <a name="l00081"></a>00081 <a name="l00082"></a>00082 <a name="l00083"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a26820ef15775e01b82e64f4333a98115">00083</a> <span class="keyword">inline</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a26820ef15775e01b82e64f4333a98115" title="Copy constructor from a multimap<pair< >, >">CDirectedGraph</a>(<span class="keyword">const</span> <a class="code" href="classstd_1_1multimap.html" title="STL class.">edges_map_t</a> &obj) : <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>(obj) { } <span class="comment">//!< Copy constructor from a multimap<pair< >, ></span> <a name="l00084"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a7f6ab2dcf88a4d2efbe062d000f99d18">00084</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a7f6ab2dcf88a4d2efbe062d000f99d18" title="Default constructor.">CDirectedGraph</a>() : <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>() {} <span class="comment">//!< Default constructor</span> <a name="l00085"></a>00085 <span class="comment"></span> <a name="l00086"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a00410afac8cede69cdc275ff3e4a1a30">00086</a> <span class="keyword">inline</span> <a class="code" href="classstd_1_1multimap_1_1iterator.html" title="STL iterator class.">iterator</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a00410afac8cede69cdc275ff3e4a1a30">begin</a>() { <span class="keywordflow">return</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.begin(); } <a name="l00087"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a265aeeb118a342f8773badf2d0242d6d">00087</a> <span class="keyword">inline</span> <a class="code" href="classstd_1_1multimap_1_1iterator.html" title="STL iterator class.">iterator</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a265aeeb118a342f8773badf2d0242d6d">end</a>() { <span class="keywordflow">return</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.end(); } <a name="l00088"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a9f0c17f5db14446650391ba6c37bd6cc">00088</a> <span class="keyword">inline</span> <a class="code" href="classstd_1_1multimap_1_1const__iterator.html" title="STL iterator class.">const_iterator</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a9f0c17f5db14446650391ba6c37bd6cc">begin</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.begin(); } <a name="l00089"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a5c0aaefb7f5394d9ca8f9c3052df8a5f">00089</a> <span class="keyword">inline</span> <a class="code" href="classstd_1_1multimap_1_1const__iterator.html" title="STL iterator class.">const_iterator</a> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a5c0aaefb7f5394d9ca8f9c3052df8a5f">end</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.end(); } <a name="l00090"></a>00090 <a name="l00091"></a>00091 <span class="comment"></span> <a name="l00092"></a>00092 <span class="comment"> /** @name Edges/nodes utility methods</span> <a name="l00093"></a>00093 <span class="comment"> @{ */</span> <a name="l00094"></a>00094 <a name="l00095"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a5fbfb47dfb250f23acf3a7802a70dac3">00095</a> <span class="keyword">inline</span> <span class="keywordtype">size_t</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a5fbfb47dfb250f23acf3a7802a70dac3" title="The number of edges in the graph.">edgeCount</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.size(); } <span class="comment">//!< The number of edges in the graph</span> <a name="l00096"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a0fbd2b4cc97be2a0e1a96c91e0727b8c">00096</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a0fbd2b4cc97be2a0e1a96c91e0727b8c" title="Erase all edges.">clearEdges</a>() { <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.clear(); } <span class="comment">//!< Erase all edges</span> <a name="l00097"></a>00097 <span class="comment"></span> <a name="l00098"></a>00098 <span class="comment"></span> <a name="l00099"></a>00099 <span class="comment"> /** Insert an edge (from -> to) with the given edge value. \sa insertEdgeAtEnd */</span> <a name="l00100"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a8db3c28b8b73e01cf5e38cef5b9ab1df">00100</a> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a8db3c28b8b73e01cf5e38cef5b9ab1df" title="Insert an edge (from -> to) with the given edge value.">insertEdge</a>(<a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> from_nodeID, <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> to_nodeID,<span class="keyword">const</span> edge_t &edge_value ) <a name="l00101"></a>00101 { <a name="l00102"></a>00102 EIGEN_ALIGN16 <span class="keyword">typename</span> <a class="code" href="classstd_1_1multimap.html" title="STL class.">edges_map_t</a><a class="code" href="eigen__plugins_8h.html#afd07186978da46f9908364e389f8a403" title="Type of the elements.">::value_type</a> entry( <a name="l00103"></a>00103 std::make_pair(from_nodeID,to_nodeID), <a name="l00104"></a>00104 edge_value); <a name="l00105"></a>00105 <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.insert(entry); <a name="l00106"></a>00106 } <a name="l00107"></a>00107 <span class="comment"></span> <a name="l00108"></a>00108 <span class="comment"> /** Insert an edge (from -> to) with the given edge value (more efficient version to be called if you know that the end will go at the end of the sorted std::multimap). \sa insertEdge */</span> <a name="l00109"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a69842cf7adcab68da36898d217fb1977">00109</a> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a69842cf7adcab68da36898d217fb1977" title="Insert an edge (from -> to) with the given edge value (more efficient version to be called if you kno...">insertEdgeAtEnd</a>(<a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> from_nodeID, <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> to_nodeID,<span class="keyword">const</span> edge_t &edge_value ) <a name="l00110"></a>00110 { <a name="l00111"></a>00111 EIGEN_ALIGN16 <span class="keyword">typename</span> <a class="code" href="classstd_1_1multimap.html" title="STL class.">edges_map_t</a><a class="code" href="eigen__plugins_8h.html#afd07186978da46f9908364e389f8a403" title="Type of the elements.">::value_type</a> entry( <a name="l00112"></a>00112 std::make_pair(from_nodeID,to_nodeID), <a name="l00113"></a>00113 edge_value); <a name="l00114"></a>00114 <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.insert(<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.end(), entry); <a name="l00115"></a>00115 } <a name="l00116"></a>00116 <span class="comment"></span> <a name="l00117"></a>00117 <span class="comment"> /** Test is the given directed edge exists. */</span> <a name="l00118"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a8d9be5feb0368b37f4598ce7a591a96c">00118</a> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a8d9be5feb0368b37f4598ce7a591a96c" title="Test is the given directed edge exists.">edgeExists</a>(<a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> from_nodeID, <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> to_nodeID)<span class="keyword"> const</span> <a name="l00119"></a>00119 <span class="keyword"> </span>{ <span class="keywordflow">return</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.find(std::make_pair(from_nodeID,to_nodeID))!=<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.end(); } <a name="l00120"></a>00120 <span class="comment"></span> <a name="l00121"></a>00121 <span class="comment"> /** Return a reference to the content of a given edge.</span> <a name="l00122"></a>00122 <span class="comment"> * If several edges exist between the given nodes, the first one is returned.</span> <a name="l00123"></a>00123 <span class="comment"> * \exception std::exception if the given edge does not exist</span> <a name="l00124"></a>00124 <span class="comment"> * \sa getEdges</span> <a name="l00125"></a>00125 <span class="comment"> */</span> <a name="l00126"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a2d858a4b74c090b99a3aa1f4c92e76d6">00126</a> edge_t & <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a2d858a4b74c090b99a3aa1f4c92e76d6" title="Return a reference to the content of a given edge.">getEdge</a>(<a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> from_nodeID, <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> to_nodeID) <a name="l00127"></a>00127 { <a name="l00128"></a>00128 <a class="code" href="classstd_1_1multimap_1_1iterator.html" title="STL iterator class.">iterator</a> it = <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.find(std::make_pair(from_nodeID,to_nodeID)); <a name="l00129"></a>00129 <span class="keywordflow">if</span> (it==<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.end()) <a name="l00130"></a>00130 <a class="code" href="mrpt__macros_8h.html#aaa3f404ea85a6575a7139f8d101370ba">THROW_EXCEPTION</a>( <a class="code" href="namespacemrpt.html#a3a27af794b658df5491e2b7678f8ccb8" title="A std::string version of C sprintf.">format</a>(<span class="stringliteral">"Edge %u->%u does not exist"</span>,(<span class="keywordtype">unsigned</span>)from_nodeID,(<span class="keywordtype">unsigned</span>)to_nodeID) ) <a name="l00131"></a>00131 <span class="keywordflow">else</span> <span class="keywordflow">return</span> it->second; <a name="l00132"></a>00132 } <a name="l00133"></a>00133 <span class="comment"></span> <a name="l00134"></a>00134 <span class="comment"> /** Return a reference to the content of a given edge.</span> <a name="l00135"></a>00135 <span class="comment"> * If several edges exist between the given nodes, the first one is returned.</span> <a name="l00136"></a>00136 <span class="comment"> * \exception std::exception if the given edge does not exist</span> <a name="l00137"></a>00137 <span class="comment"> * \sa getEdges</span> <a name="l00138"></a>00138 <span class="comment"> */</span> <a name="l00139"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#ada6c10bb7f912abb084c2e4173845619">00139</a> <span class="keyword">const</span> edge_t & <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a2d858a4b74c090b99a3aa1f4c92e76d6" title="Return a reference to the content of a given edge.">getEdge</a>(<a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> from_nodeID, <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> to_nodeID)<span class="keyword"> const</span> <a name="l00140"></a>00140 <span class="keyword"> </span>{ <a name="l00141"></a>00141 <a class="code" href="classstd_1_1multimap_1_1const__iterator.html" title="STL iterator class.">const_iterator</a> it = <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.find(std::make_pair(from_nodeID,to_nodeID)); <a name="l00142"></a>00142 <span class="keywordflow">if</span> (it==<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.end()) <a name="l00143"></a>00143 <a class="code" href="mrpt__macros_8h.html#aaa3f404ea85a6575a7139f8d101370ba">THROW_EXCEPTION</a>( <a class="code" href="namespacemrpt.html#a3a27af794b658df5491e2b7678f8ccb8" title="A std::string version of C sprintf.">format</a>(<span class="stringliteral">"Edge %u->%u does not exist"</span>,(<span class="keywordtype">unsigned</span>)from_nodeID,(<span class="keywordtype">unsigned</span>)to_nodeID) ) <a name="l00144"></a>00144 <span class="keywordflow">else</span> <span class="keywordflow">return</span> it->second; <a name="l00145"></a>00145 } <a name="l00146"></a>00146 <span class="comment"></span> <a name="l00147"></a>00147 <span class="comment"> /** Return a pair<first,last> of iterators to the range of edges between two given nodes. \sa getEdge */</span> <a name="l00148"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#adf2bb3bd0774fee8fd3f14f7f316aaa1">00148</a> std::pair<iterator,iterator> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#adf2bb3bd0774fee8fd3f14f7f316aaa1" title="Return a pair<first,last> of iterators to the range of edges between two given nodes.">getEdges</a>(<a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> from_nodeID, <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> to_nodeID) { <a name="l00149"></a>00149 <span class="keywordflow">return</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.equal_range( std::make_pair(from_nodeID,to_nodeID) ); <a name="l00150"></a>00150 }<span class="comment"></span> <a name="l00151"></a>00151 <span class="comment"> /** Return a pair<first,last> of const iterators to the range of edges between two given nodes. \sa getEdge */</span> <a name="l00152"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a548e07d2c9b49ceb08610f3e4eca19dc">00152</a> std::pair<const_iterator,const_iterator> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a548e07d2c9b49ceb08610f3e4eca19dc" title="Return a pair<first,last> of const iterators to the range of edges between two given nodes...">getEdges</a>(<a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> from_nodeID, <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> to_nodeID)<span class="keyword"> const </span>{ <a name="l00153"></a>00153 <span class="keywordflow">return</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.equal_range( std::make_pair(from_nodeID,to_nodeID) ); <a name="l00154"></a>00154 } <a name="l00155"></a>00155 <span class="comment"></span> <a name="l00156"></a>00156 <span class="comment"> /** Erase all edges between the given nodes (it has no effect if no edge existed)</span> <a name="l00157"></a>00157 <span class="comment"> */</span> <a name="l00158"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a9e072ff6281e3aacf318b84685fc2a55">00158</a> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a9e072ff6281e3aacf318b84685fc2a55" title="Erase all edges between the given nodes (it has no effect if no edge existed)">eraseEdge</a>(<a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> from_nodeID, <a class="code" href="namespacemrpt_1_1utils.html#a718b4f99645b7e9f6501c9b7bb2a2fe7" title="The type for node IDs in graphs of different types.">TNodeID</a> to_nodeID) { <a name="l00159"></a>00159 <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.erase(std::make_pair(from_nodeID,to_nodeID)); <a name="l00160"></a>00160 } <a name="l00161"></a>00161 <span class="comment"></span> <a name="l00162"></a>00162 <span class="comment"> /** Return a list of all the node_ID's of the graph, generated from all the nodes that appear in the list of edges</span> <a name="l00163"></a>00163 <span class="comment"> */</span> <a name="l00164"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#ad73f9ea9eaa069cf1b7000b8b560155e">00164</a> <span class="keywordtype">void</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a11fed5f0111f8a42f891f788aea8408e" title="Less efficient way to get all nodes that returns a copy of the set object.">getAllNodes</a>( <a class="code" href="classstd_1_1set.html">std::set<TNodeID></a> &lstNode_IDs)<span class="keyword"> const</span> <a name="l00165"></a>00165 <span class="keyword"> </span>{ <a name="l00166"></a>00166 lstNode_IDs.clear(); <a name="l00167"></a>00167 <span class="keywordflow">for</span> (<span class="keyword">typename</span> <a class="code" href="classstd_1_1multimap_1_1const__iterator.html" title="STL iterator class.">edges_map_t::const_iterator</a> it=<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.begin();it!=<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.end();++it) <a name="l00168"></a>00168 { <a name="l00169"></a>00169 lstNode_IDs.insert(it->first.first); <a name="l00170"></a>00170 lstNode_IDs.insert(it->first.second); <a name="l00171"></a>00171 } <a name="l00172"></a>00172 } <a name="l00173"></a>00173 <span class="comment"></span> <a name="l00174"></a>00174 <span class="comment"> /** Less efficient way to get all nodes that returns a copy of the set object \sa getAllNodes( std::set<TNodeID> &lstNode_IDs) */</span> <a name="l00175"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a11fed5f0111f8a42f891f788aea8408e">00175</a> <span class="keyword">inline</span> std<a class="code" href="classstd_1_1set.html">::set<TNodeID></a> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a11fed5f0111f8a42f891f788aea8408e" title="Less efficient way to get all nodes that returns a copy of the set object.">getAllNodes</a>()<span class="keyword"> const </span>{ std<a class="code" href="classstd_1_1set.html">::set<TNodeID></a> lst; <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a11fed5f0111f8a42f891f788aea8408e" title="Less efficient way to get all nodes that returns a copy of the set object.">getAllNodes</a>(lst); <span class="keywordflow">return</span> lst; } <a name="l00176"></a>00176 <span class="comment"></span> <a name="l00177"></a>00177 <span class="comment"> /** Count how many different node IDs appear in the graph edges.</span> <a name="l00178"></a>00178 <span class="comment"> */</span> <a name="l00179"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#aac62b79ce4e35b186bf12427ef72f77e">00179</a> <span class="keywordtype">size_t</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#aac62b79ce4e35b186bf12427ef72f77e" title="Count how many different node IDs appear in the graph edges.">countDifferentNodesInEdges</a>()<span class="keyword"> const</span> <a name="l00180"></a>00180 <span class="keyword"> </span>{ <a name="l00181"></a>00181 std<a class="code" href="classstd_1_1set.html">::set<TNodeID></a> aux; <a name="l00182"></a>00182 <span class="keywordflow">for</span> (<span class="keyword">typename</span> <a class="code" href="classstd_1_1multimap_1_1const__iterator.html" title="STL iterator class.">edges_map_t::const_iterator</a> it=<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.begin();it!=<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.end();++it) <a name="l00183"></a>00183 { <a name="l00184"></a>00184 aux.insert(it->first.first); <a name="l00185"></a>00185 aux.insert(it->first.second); <a name="l00186"></a>00186 } <a name="l00187"></a>00187 <span class="keywordflow">return</span> aux.size(); <a name="l00188"></a>00188 } <a name="l00189"></a>00189 <span class="comment"></span> <a name="l00190"></a>00190 <span class="comment"> /** Return the list of all neighbors of "nodeID", by creating a list of their node IDs. \sa getAdjacencyMatrix */</span> <a name="l00191"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#ab275c72b1763fb12b09f762e83ad6355">00191</a> <span class="keywordtype">void</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#ab275c72b1763fb12b09f762e83ad6355" title="Return the list of all neighbors of "nodeID", by creating a list of their node IDs.">getNeighborsOf</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> nodeID, <a class="code" href="classstd_1_1set.html">std::set<TNodeID></a> &neighborIDs)<span class="keyword"> const</span> <a name="l00192"></a>00192 <span class="keyword"> </span>{ <a name="l00193"></a>00193 neighborIDs.clear(); <a name="l00194"></a>00194 <span class="keywordflow">for</span> (<span class="keyword">typename</span> <a class="code" href="classstd_1_1multimap_1_1const__iterator.html" title="STL iterator class.">edges_map_t::const_iterator</a> it=<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.begin();it!=<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.end();++it) <a name="l00195"></a>00195 { <a name="l00196"></a>00196 <span class="keywordflow">if</span> (it->first.first==nodeID) <a name="l00197"></a>00197 neighborIDs.insert(it->first.second); <a name="l00198"></a>00198 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (it->first.second==nodeID) <a name="l00199"></a>00199 neighborIDs.insert(it->first.first); <a name="l00200"></a>00200 } <a name="l00201"></a>00201 } <a name="l00202"></a>00202 <span class="comment"></span> <a name="l00203"></a>00203 <span class="comment"> /** Return a map from node IDs to all its neighbors (that is, connected nodes, regardless of the edge direction)</span> <a name="l00204"></a>00204 <span class="comment"> * This is a much more efficient method than calling getNeighborsOf() for each node in the graph.</span> <a name="l00205"></a>00205 <span class="comment"> * Possible values for the template argument MAP_NODEID_SET_NODEIDS are:</span> <a name="l00206"></a>00206 <span class="comment"> * - std::map<TNodeID, std::set<TNodeID> ></span> <a name="l00207"></a>00207 <span class="comment"> * - mrpt::utils::map_as_vector<TNodeID, std::set<TNodeID> ></span> <a name="l00208"></a>00208 <span class="comment"> * \sa getNeighborsOf</span> <a name="l00209"></a>00209 <span class="comment"> */</span> <a name="l00210"></a>00210 <span class="keyword">template</span> <<span class="keyword">class</span> MAP_NODEID_SET_NODEIDS> <a name="l00211"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b05ec8c7974689a9013c142fe82b3e5">00211</a> <span class="keywordtype">void</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b05ec8c7974689a9013c142fe82b3e5" title="Return a map from node IDs to all its neighbors (that is, connected nodes, regardless of the edge dir...">getAdjacencyMatrix</a>( MAP_NODEID_SET_NODEIDS &outAdjacency )<span class="keyword"> const</span> <a name="l00212"></a>00212 <span class="keyword"> </span>{ <a name="l00213"></a>00213 outAdjacency.clear(); <a name="l00214"></a>00214 <span class="keywordflow">for</span> (<span class="keyword">typename</span> <a class="code" href="classstd_1_1multimap_1_1const__iterator.html" title="STL iterator class.">edges_map_t::const_iterator</a> it=<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.begin();it!=<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.end();++it) <a name="l00215"></a>00215 { <a name="l00216"></a>00216 outAdjacency[it->first.first].insert(it->first.second); <a name="l00217"></a>00217 outAdjacency[it->first.second].insert(it->first.first); <a name="l00218"></a>00218 } <a name="l00219"></a>00219 } <a name="l00220"></a>00220 <span class="comment"></span> <a name="l00221"></a>00221 <span class="comment"> /** Just like \a getAdjacencyMatrix but return only the adjacency for those node_ids in the set \a onlyForTheseNodes</span> <a name="l00222"></a>00222 <span class="comment"> * (both endings nodes of an edge must be within the set for it to be returned) */</span> <a name="l00223"></a>00223 <span class="keyword">template</span> <<span class="keyword">class</span> MAP_NODEID_SET_NODEIDS,<span class="keyword">class</span> SET_NODEIDS> <a name="l00224"></a><a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a3434d7335a5ef1f2bf166c438a0e23ac">00224</a> <span class="keywordtype">void</span> <a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b05ec8c7974689a9013c142fe82b3e5" title="Return a map from node IDs to all its neighbors (that is, connected nodes, regardless of the edge dir...">getAdjacencyMatrix</a>( MAP_NODEID_SET_NODEIDS &outAdjacency, <span class="keyword">const</span> SET_NODEIDS &onlyForTheseNodes )<span class="keyword"> const</span> <a name="l00225"></a>00225 <span class="keyword"> </span>{ <a name="l00226"></a>00226 outAdjacency.clear(); <a name="l00227"></a>00227 <span class="keyword">const</span> <span class="keyword">typename</span> SET_NODEIDS<a class="code" href="classstd_1_1multimap_1_1const__iterator.html" title="STL iterator class.">::const_iterator</a> setEnd = onlyForTheseNodes.end(); <a name="l00228"></a>00228 <span class="keywordflow">for</span> (<span class="keyword">typename</span> <a class="code" href="classstd_1_1multimap_1_1const__iterator.html" title="STL iterator class.">edges_map_t::const_iterator</a> it=<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.begin();it!=<a class="code" href="classmrpt_1_1graphs_1_1_c_directed_graph.html#a6b82920b6172bcdaeb088c64a6c9a80f" title="The public member with the directed edges in the graph.">edges</a>.end();++it) <a name="l00229"></a>00229 { <a name="l00230"></a>00230 <span class="keywordflow">if</span> (onlyForTheseNodes.find(it->first.first)==setEnd || onlyForTheseNodes.find(it->first.second)==setEnd) <a name="l00231"></a>00231 <span class="keywordflow">continue</span>; <a name="l00232"></a>00232 outAdjacency[it->first.first].insert(it->first.second); <a name="l00233"></a>00233 outAdjacency[it->first.second].insert(it->first.first); <a name="l00234"></a>00234 } <a name="l00235"></a>00235 } <a name="l00236"></a>00236 <span class="comment"></span> <a name="l00237"></a>00237 <span class="comment"> /** @} */</span> <span class="comment">// end of edge/nodes utilities</span> <a name="l00238"></a>00238 <a name="l00239"></a>00239 }; <span class="comment">// end class CDirectedGraph</span> <a name="l00240"></a>00240 <span class="comment"></span> <a name="l00241"></a>00241 <span class="comment"> /** @} */</span> <a name="l00242"></a>00242 } <span class="comment">// End of namespace</span> <a name="l00243"></a>00243 } <span class="comment">// End of namespace</span> <a name="l00244"></a>00244 <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>