<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html><head><meta http-equiv="Content-Type" content="text/html;charset=UTF-8"> <title>DTN Reference Implementation: MultiGraph.h Source File</title> <link href="doxygen.css" rel="stylesheet" type="text/css"> <link href="tabs.css" rel="stylesheet" type="text/css"> </head><body> <!-- Generated by Doxygen 1.5.6 --> <div class="navigation" id="top"> <div class="tabs"> <ul> <li><a href="main.html"><span>Main Page</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> </ul> </div> <h1>MultiGraph.h</h1><a href="MultiGraph_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"> * Copyright 2007 Intel Corporation</span> <a name="l00003"></a>00003 <span class="comment"> * </span> <a name="l00004"></a>00004 <span class="comment"> * Licensed under the Apache License, Version 2.0 (the "License");</span> <a name="l00005"></a>00005 <span class="comment"> * you may not use this file except in compliance with the License.</span> <a name="l00006"></a>00006 <span class="comment"> * You may obtain a copy of the License at</span> <a name="l00007"></a>00007 <span class="comment"> * </span> <a name="l00008"></a>00008 <span class="comment"> * http://www.apache.org/licenses/LICENSE-2.0</span> <a name="l00009"></a>00009 <span class="comment"> * </span> <a name="l00010"></a>00010 <span class="comment"> * Unless required by applicable law or agreed to in writing, software</span> <a name="l00011"></a>00011 <span class="comment"> * distributed under the License is distributed on an "AS IS" BASIS,</span> <a name="l00012"></a>00012 <span class="comment"> * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.</span> <a name="l00013"></a>00013 <span class="comment"> * See the License for the specific language governing permissions and</span> <a name="l00014"></a>00014 <span class="comment"> * limitations under the License.</span> <a name="l00015"></a>00015 <span class="comment"> */</span> <a name="l00016"></a>00016 <a name="l00017"></a>00017 <span class="preprocessor">#ifndef _MULTIGRAPH_H_</span> <a name="l00018"></a>00018 <span class="preprocessor"></span><span class="preprocessor">#define _MULTIGRAPH_H_</span> <a name="l00019"></a>00019 <span class="preprocessor"></span> <a name="l00020"></a>00020 <span class="preprocessor">#include <vector></span> <a name="l00021"></a>00021 <span class="preprocessor">#include <oasys/debug/InlineFormatter.h></span> <a name="l00022"></a>00022 <span class="preprocessor">#include <oasys/debug/Formatter.h></span> <a name="l00023"></a>00023 <span class="preprocessor">#include <oasys/debug/Logger.h></span> <a name="l00024"></a>00024 <span class="preprocessor">#include <oasys/util/StringBuffer.h></span> <a name="l00025"></a>00025 <span class="preprocessor">#include <oasys/util/Time.h></span> <a name="l00026"></a>00026 <a name="l00027"></a>00027 <span class="keyword">namespace </span>dtn { <a name="l00028"></a>00028 <a name="l00029"></a>00029 <span class="keyword">class </span>Bundle; <a name="l00030"></a>00030 <a name="l00034"></a>00034 <span class="keyword">template</span> <<span class="keyword">typename</span> _NodeInfo, <span class="keyword">typename</span> _EdgeInfo> <a name="l00035"></a><a class="code" href="classdtn_1_1MultiGraph.html">00035</a> <span class="keyword">class </span><a class="code" href="classdtn_1_1MultiGraph.html" title="Data structure to represent a multigraph.">MultiGraph</a> : <span class="keyword">public</span> oasys::<a class="code" href="classoasys_1_1Formatter.html">Formatter</a>, <span class="keyword">public</span> oasys::<a class="code" href="classoasys_1_1Logger.html">Logger</a> { <a name="l00036"></a>00036 <span class="keyword">public</span>: <a name="l00038"></a>00038 <span class="keyword">class </span><a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html" title="The edge class.">Edge</a>; <a name="l00039"></a>00039 <span class="keyword">class </span><a class="code" href="classdtn_1_1MultiGraph_1_1EdgeVector.html" title="Helper data structure for a vector of edges.">EdgeVector</a>; <a name="l00040"></a>00040 <span class="keyword">class </span><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>; <a name="l00041"></a>00041 <span class="keyword">class </span><a class="code" href="classdtn_1_1MultiGraph_1_1NodeVector.html" title="Helper data structure for a vector of nodes.">NodeVector</a>; <a name="l00042"></a>00042 <span class="keyword">class </span><a class="code" href="classdtn_1_1MultiGraph_1_1WeightFn.html" title="The abstract weight function class.">WeightFn</a>; <a name="l00044"></a>00044 <a name="l00046"></a>00046 <a class="code" href="classdtn_1_1MultiGraph.html#45465930b4c1e4be0f25ddc8ec3cc2c9" title="Constructor.">MultiGraph</a>(); <a name="l00047"></a>00047 <a name="l00049"></a>00049 <a class="code" href="classdtn_1_1MultiGraph.html#1ff6ca466b1a3d0d3ba7e1c9e7e1c7b0" title="Destructor.">~MultiGraph</a>(); <a name="l00050"></a>00050 <a name="l00052"></a>00052 <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* <a class="code" href="classdtn_1_1MultiGraph.html#c250f8c8d1b8970870067c6e73058ee9" title="Add a new node.">add_node</a>(<span class="keyword">const</span> std::string& <span class="keywordtype">id</span>, <span class="keyword">const</span> _NodeInfo& <a class="code" href="dtncat_8c.html#71f51a2e8cbe9a53031fa72596edc09f">info</a>); <a name="l00053"></a>00053 <a name="l00055"></a>00055 <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* <a class="code" href="classdtn_1_1MultiGraph.html#a9a0d61ec5663bc8954b0db5969b68f4" title="Find a node with the given id.">find_node</a>(<span class="keyword">const</span> std::string& <span class="keywordtype">id</span>) <span class="keyword">const</span>; <a name="l00056"></a>00056 <a name="l00058"></a>00058 <span class="keywordtype">bool</span> <a class="code" href="classdtn_1_1MultiGraph.html#c6c2ee3ec320168b2399e3ae4a77936b" title="Delete a node and all its edges.">del_node</a>(<span class="keyword">const</span> std::string& <span class="keywordtype">id</span>); <a name="l00059"></a>00059 <a name="l00061"></a>00061 <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html" title="The edge class.">Edge</a>* <a class="code" href="classdtn_1_1MultiGraph.html#059a319c2a8018b46b292b3dbc01ce8a" title="Add an edge.">add_edge</a>(<a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* a, <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* b, <span class="keyword">const</span> _EdgeInfo& info); <a name="l00062"></a>00062 <a name="l00064"></a>00064 <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html" title="The edge class.">Edge</a>* <a class="code" href="classdtn_1_1MultiGraph.html#45b321b90cabaab2d960b50bfa65f3ab" title="Find an edge.">find_edge</a>(<span class="keyword">const</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* a, <span class="keyword">const</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* b, <span class="keyword">const</span> _EdgeInfo& info); <a name="l00065"></a>00065 <a name="l00068"></a>00068 <span class="keywordtype">bool</span> <a class="code" href="classdtn_1_1MultiGraph.html#32aff4a713436864c2f147c03393bbbe" title="Remove the specified edge from the given node, deleting the Edge object.">del_edge</a>(<a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* node, <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html" title="The edge class.">Edge</a>* edge); <a name="l00069"></a>00069 <a name="l00074"></a>00074 <span class="keywordtype">void</span> <a class="code" href="classdtn_1_1MultiGraph.html#5d091d22c14ffe7c29ff7890d69c9f89" title="Find the shortest path between two nodes by running Dijkstra&#39;s algorithm, filling...">shortest_path</a>(<span class="keyword">const</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* a, <span class="keyword">const</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* b, <a name="l00075"></a>00075 <a class="code" href="classdtn_1_1MultiGraph_1_1EdgeVector.html" title="Helper data structure for a vector of edges.">EdgeVector</a>* path, <a class="code" href="classdtn_1_1MultiGraph_1_1WeightFn.html" title="The abstract weight function class.">WeightFn</a>* weight_fn, <a name="l00076"></a>00076 <a class="code" href="classdtn_1_1Bundle.html" title="The internal representation of a bundle.">Bundle</a>* bundle = NULL); <a name="l00077"></a>00077 <a name="l00080"></a>00080 <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html" title="The edge class.">Edge</a>* <a class="code" href="classdtn_1_1MultiGraph.html#05257dfbccf2c15813faef76b0a8ff6c" title="More limited version of the shortest path that just returns the next hop edge.">best_next_hop</a>(<span class="keyword">const</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* a, <span class="keyword">const</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* b, <a class="code" href="classdtn_1_1MultiGraph_1_1WeightFn.html" title="The abstract weight function class.">WeightFn</a>* weight_fn, <a name="l00081"></a>00081 <a class="code" href="classdtn_1_1Bundle.html" title="The internal representation of a bundle.">Bundle</a>* bundle = NULL); <a name="l00082"></a>00082 <a name="l00084"></a>00084 <span class="keywordtype">void</span> <a class="code" href="classdtn_1_1MultiGraph.html#8b4f62ab231dd63ea2fe3c45d59ead17" title="Clear the contents of the graph.">clear</a>(); <a name="l00085"></a>00085 <a name="l00087"></a>00087 <span class="keywordtype">int</span> <a class="code" href="classdtn_1_1MultiGraph.html#70aafb526a9df1513b7683549261ec47" title="Virtual from Formatter.">format</a>(<span class="keywordtype">char</span>* <a class="code" href="num2sdnv_8c.html#a81cdcc7ff6987bc85c073253e32715f">buf</a>, <span class="keywordtype">size_t</span> sz) <span class="keyword">const</span>; <a name="l00088"></a>00088 <a name="l00090"></a><a class="code" href="classdtn_1_1MultiGraph.html#6d2fd66634cd1087df9f6554abbf107a">00090</a> std::string <a class="code" href="classdtn_1_1MultiGraph.html#6d2fd66634cd1087df9f6554abbf107a" title="Return a string dump of the graph.">dump</a>()<span class="keyword"> const</span> <a name="l00091"></a>00091 <span class="keyword"> </span>{ <a name="l00092"></a>00092 <span class="keywordtype">char</span> buf[1024]; <a name="l00093"></a>00093 <span class="keywordtype">int</span> <a class="code" href="num2sdnv_8c.html#fed088663f8704004425cdae2120b9b3">len</a> = <a class="code" href="classdtn_1_1MultiGraph.html#70aafb526a9df1513b7683549261ec47" title="Virtual from Formatter.">format</a>(buf, <span class="keyword">sizeof</span>(buf)); <a name="l00094"></a>00094 <span class="keywordflow">return</span> std::string(buf, len); <a name="l00095"></a>00095 } <a name="l00096"></a>00096 <a name="l00098"></a><a class="code" href="classdtn_1_1MultiGraph.html#105482907b76044f8faa3720c8c97c4c">00098</a> <span class="keyword">const</span> NodeVector& <a class="code" href="classdtn_1_1MultiGraph.html#105482907b76044f8faa3720c8c97c4c" title="Accessor for the nodes array.">nodes</a>() { <span class="keywordflow">return</span> <a class="code" href="classdtn_1_1MultiGraph.html#a195b6b49cc23c6af28dd923260b0641" title="The vector of all nodes.">nodes_</a>; } <a name="l00099"></a>00099 <a name="l00103"></a><a class="code" href="structdtn_1_1MultiGraph_1_1SearchInfo.html">00103</a> <span class="keyword">struct </span><a class="code" href="structdtn_1_1MultiGraph_1_1SearchInfo.html" title="Struct used to encapsulate state that may be needed by weight functors and which...">SearchInfo</a> { <a name="l00104"></a>00104 <a class="code" href="structdtn_1_1MultiGraph_1_1SearchInfo.html#a5100b190cfe33324c1cc1a0ff84cfae">SearchInfo</a>(<a class="code" href="classdtn_1_1Bundle.html" title="The internal representation of a bundle.">Bundle</a>* bundle); <a name="l00105"></a>00105 <a name="l00106"></a><a class="code" href="structdtn_1_1MultiGraph_1_1SearchInfo.html#d0ed97c1d2a9134fe3beea03f408f4ad">00106</a> <a class="code" href="classdtn_1_1Bundle.html" title="The internal representation of a bundle.">Bundle</a>* <a class="code" href="structdtn_1_1MultiGraph_1_1SearchInfo.html#d0ed97c1d2a9134fe3beea03f408f4ad">bundle_</a>; <a name="l00107"></a><a class="code" href="structdtn_1_1MultiGraph_1_1SearchInfo.html#0771afe20f821866802568b7ead09d81">00107</a> oasys::Time <a class="code" href="structdtn_1_1MultiGraph_1_1SearchInfo.html#0771afe20f821866802568b7ead09d81">now_</a>; <a name="l00108"></a>00108 }; <a name="l00109"></a>00109 <a name="l00111"></a><a class="code" href="classdtn_1_1MultiGraph_1_1WeightFn.html">00111</a> <span class="keyword">class </span><a class="code" href="classdtn_1_1MultiGraph_1_1WeightFn.html" title="The abstract weight function class.">WeightFn</a> { <a name="l00112"></a>00112 <span class="keyword">public</span>: <a name="l00113"></a><a class="code" href="classdtn_1_1MultiGraph_1_1WeightFn.html#847cd5faf7950d4154a9ddb2470c3e89">00113</a> <span class="keyword">virtual</span> <a class="code" href="classdtn_1_1MultiGraph_1_1WeightFn.html#847cd5faf7950d4154a9ddb2470c3e89">~WeightFn</a>() {} <a name="l00114"></a>00114 <span class="keyword">virtual</span> u_int32_t <a class="code" href="classdtn_1_1MultiGraph_1_1WeightFn.html#4ab6a29f9f340047899302407b2ae81c">operator()</a>(<span class="keyword">const</span> <a class="code" href="structdtn_1_1MultiGraph_1_1SearchInfo.html" title="Struct used to encapsulate state that may be needed by weight functors and which...">SearchInfo</a>& info, <a name="l00115"></a>00115 <span class="keyword">const</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html" title="The edge class.">Edge</a>* edge) = 0; <a name="l00116"></a>00116 }; <a name="l00117"></a>00117 <a name="l00119"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html">00119</a> <span class="keyword">class </span><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a> { <a name="l00120"></a>00120 <span class="keyword">public</span>: <a name="l00122"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#20e591ba975de22a236b4bbd2df0accb">00122</a> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#20e591ba975de22a236b4bbd2df0accb" title="Constructor.">Node</a>(<span class="keyword">const</span> std::string& <span class="keywordtype">id</span>, <span class="keyword">const</span> _NodeInfo info) <a name="l00123"></a>00123 : <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#5d430462e0ec27e8d777c1ef39231885">id_</a>(id), <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#2387a918bfd8669226bc6c62aebefe63">info_</a>(info) {} <a name="l00124"></a>00124 <a name="l00125"></a>00125 <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#e40d5e4005b1f7ef3bffa97a5ddd19ca">~Node</a>(); <a name="l00126"></a>00126 <a name="l00127"></a>00127 <span class="keywordtype">bool</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#16384aef9ea88c3d34c7ef596c9e4b1c">del_edge</a>(<a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html" title="The edge class.">Edge</a>* edge); <a name="l00128"></a>00128 <a name="l00129"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#5e8016f9c2e46fe81258cc4c3eb597ee">00129</a> <span class="keyword">const</span> std::string& <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#5e8016f9c2e46fe81258cc4c3eb597ee">id</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#5d430462e0ec27e8d777c1ef39231885">id_</a>; } <a name="l00130"></a>00130 <a name="l00131"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#96c7bd3d7f08a00f695b76d210890f37">00131</a> <span class="keyword">const</span> _NodeInfo& <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#96c7bd3d7f08a00f695b76d210890f37">info</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#2387a918bfd8669226bc6c62aebefe63">info_</a>; } <a name="l00132"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#3316aa822c760f05026daac68753a838">00132</a> _NodeInfo& <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#3316aa822c760f05026daac68753a838">mutable_info</a>() { <span class="keywordflow">return</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#2387a918bfd8669226bc6c62aebefe63">info_</a>; } <a name="l00133"></a>00133 <a name="l00134"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#f17f73294b7a81c08f78398f3088bac4">00134</a> <span class="keyword">const</span> <a class="code" href="classdtn_1_1MultiGraph_1_1EdgeVector.html" title="Helper data structure for a vector of edges.">EdgeVector</a>& <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#f17f73294b7a81c08f78398f3088bac4">out_edges</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#c8babf47c1e30701338cc508235fe63f">out_edges_</a>; } <a name="l00135"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#ab01e3e037c8fdd5a15048122cc61efc">00135</a> <span class="keyword">const</span> <a class="code" href="classdtn_1_1MultiGraph_1_1EdgeVector.html" title="Helper data structure for a vector of edges.">EdgeVector</a>& <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#ab01e3e037c8fdd5a15048122cc61efc">in_edges</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#ecd7bea3c46cbf8b18aed516c5833a5a">in_edges_</a>; } <a name="l00136"></a>00136 <a name="l00137"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#de77e4a647c1dca257c188b9162d0d25">00137</a> <a class="code" href="classdtn_1_1MultiGraph_1_1EdgeVector.html" title="Helper data structure for a vector of edges.">EdgeVector</a>& <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#f17f73294b7a81c08f78398f3088bac4">out_edges</a>() { <span class="keywordflow">return</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#c8babf47c1e30701338cc508235fe63f">out_edges_</a>; } <a name="l00138"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#cd4d7571810d456330fac1d624df39fc">00138</a> <a class="code" href="classdtn_1_1MultiGraph_1_1EdgeVector.html" title="Helper data structure for a vector of edges.">EdgeVector</a>& <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#ab01e3e037c8fdd5a15048122cc61efc">in_edges</a>() { <span class="keywordflow">return</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#ecd7bea3c46cbf8b18aed516c5833a5a">in_edges_</a>; } <a name="l00139"></a>00139 <a name="l00140"></a>00140 <span class="keyword">private</span>: <a name="l00141"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#516ddcbe742d58fd5c1e5cd091134922">00141</a> <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="classdtn_1_1MultiGraph.html" title="Data structure to represent a multigraph.">MultiGraph</a>; <a name="l00142"></a>00142 <a name="l00143"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#5d430462e0ec27e8d777c1ef39231885">00143</a> std::string <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#5d430462e0ec27e8d777c1ef39231885">id_</a>; <a name="l00144"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#2387a918bfd8669226bc6c62aebefe63">00144</a> _NodeInfo <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#2387a918bfd8669226bc6c62aebefe63">info_</a>; <a name="l00145"></a>00145 <a name="l00146"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#c8babf47c1e30701338cc508235fe63f">00146</a> <a class="code" href="classdtn_1_1MultiGraph_1_1EdgeVector.html" title="Helper data structure for a vector of edges.">EdgeVector</a> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#c8babf47c1e30701338cc508235fe63f">out_edges_</a>; <a name="l00147"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#ecd7bea3c46cbf8b18aed516c5833a5a">00147</a> <a class="code" href="classdtn_1_1MultiGraph_1_1EdgeVector.html" title="Helper data structure for a vector of edges.">EdgeVector</a> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#ecd7bea3c46cbf8b18aed516c5833a5a">in_edges_</a>; <a name="l00148"></a>00148 <a name="l00149"></a>00149 <span class="comment">// XXX/demmer see below</span> <a name="l00150"></a>00150 <span class="comment">// friend class MultiGraph::DijkstraCompare;</span> <a name="l00151"></a>00151 <a name="l00153"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#46844a5c91b046afa234fc45835ea3ca">00153</a> <span class="keyword">mutable</span> u_int32_t <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#46844a5c91b046afa234fc45835ea3ca" title="Dijkstra algorithm state.">distance_</a>; <a name="l00154"></a>00154 <a name="l00155"></a>00155 <span class="keyword">mutable</span> <span class="keyword">enum</span> { <a name="l00156"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#ab4f01861321459910276b49a88621ea1840948ca3e95a120293f9be73b3d5ab">00156</a> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#ab4f01861321459910276b49a88621ea1840948ca3e95a120293f9be73b3d5ab">WHITE</a>, <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#ab4f01861321459910276b49a88621ea80af735ffd1d75aa1fbcbee243babed9">GRAY</a>, <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#ab4f01861321459910276b49a88621eaaff25f972101411f2fa464d53fdf0b11">BLACK</a> <a name="l00157"></a>00157 } <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#e4be619104845767ffdead91cd5e6055" title="Dijkstra algorithm state.">color_</a>; <a name="l00158"></a>00158 <a name="l00159"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#cc585d08e12c4cfed4be38e661dfef53">00159</a> <span class="keyword">mutable</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html" title="The edge class.">Edge</a>* <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html#cc585d08e12c4cfed4be38e661dfef53" title="Dijkstra algorithm state.">prev_</a>; <a name="l00161"></a>00161 }; <a name="l00162"></a>00162 <a name="l00166"></a><a class="code" href="classdtn_1_1MultiGraph.html#681a67ccaac7566e4f38ab36cf35d428">00166</a> <span class="keyword">static</span> u_int32_t <a class="code" href="classdtn_1_1MultiGraph.html#681a67ccaac7566e4f38ab36cf35d428" title="XXX/demmer this stupid helper function is needed because DijkstraCompare can&#39;t...">NodeDistance</a>(<span class="keyword">const</span> Node* n) { <a name="l00167"></a>00167 <span class="keywordflow">return</span> n->distance_; <a name="l00168"></a>00168 } <a name="l00169"></a>00169 <a name="l00171"></a><a class="code" href="structdtn_1_1MultiGraph_1_1DijkstraCompare.html">00171</a> <span class="keyword">struct </span><a class="code" href="structdtn_1_1MultiGraph_1_1DijkstraCompare.html" title="Helper class to compute Dijkstra distance.">DijkstraCompare</a> { <a name="l00172"></a><a class="code" href="structdtn_1_1MultiGraph_1_1DijkstraCompare.html#63a87e5becb844d079d46a7b29e66aa8">00172</a> <span class="keywordtype">bool</span> <a class="code" href="structdtn_1_1MultiGraph_1_1DijkstraCompare.html#63a87e5becb844d079d46a7b29e66aa8">operator()</a>(<span class="keyword">const</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* a, <span class="keyword">const</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* b)<span class="keyword"> const </span>{ <a name="l00173"></a>00173 <span class="keywordflow">return</span> <a class="code" href="classdtn_1_1MultiGraph.html#681a67ccaac7566e4f38ab36cf35d428" title="XXX/demmer this stupid helper function is needed because DijkstraCompare can&#39;t...">NodeDistance</a>(a) > <a class="code" href="classdtn_1_1MultiGraph.html#681a67ccaac7566e4f38ab36cf35d428" title="XXX/demmer this stupid helper function is needed because DijkstraCompare can&#39;t...">NodeDistance</a>(b); <a name="l00174"></a>00174 } <a name="l00175"></a>00175 }; <a name="l00176"></a>00176 <a name="l00178"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html">00178</a> <span class="keyword">class </span><a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html" title="The edge class.">Edge</a> { <a name="l00179"></a>00179 <span class="keyword">public</span>: <a name="l00181"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#6a655f819d397c80ea810283be36facc">00181</a> <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#6a655f819d397c80ea810283be36facc" title="Constructor.">Edge</a>(<a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* s, <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* d, <span class="keyword">const</span> _EdgeInfo info) <a name="l00182"></a>00182 : <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#3da17b87de9397146aaebe56c6e9dabf">source_</a>(s), <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#0a8d42859f0d63776ea0eebd9eeaff4a">dest_</a>(d), <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#802f299c1a44c624ec034cb3e15c8b14">info_</a>(info) {} <a name="l00183"></a>00183 <a name="l00185"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#37eb79787421514fb3507e7003792015">00185</a> <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#37eb79787421514fb3507e7003792015" title="Destructor clears contents for debugging purposes.">~Edge</a>() { <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#3da17b87de9397146aaebe56c6e9dabf">source_</a> = NULL; <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#0a8d42859f0d63776ea0eebd9eeaff4a">dest_</a> = NULL; } <a name="l00186"></a>00186 <a name="l00187"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#a7c774da0b1da3bf803e80642353a2eb">00187</a> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#a7c774da0b1da3bf803e80642353a2eb">source</a>() { <span class="keywordflow">return</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#3da17b87de9397146aaebe56c6e9dabf">source_</a>; } <a name="l00188"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#2ee41e994c997f93e43a62cb97e48b4a">00188</a> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#2ee41e994c997f93e43a62cb97e48b4a">dest</a>() { <span class="keywordflow">return</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#0a8d42859f0d63776ea0eebd9eeaff4a">dest_</a>; } <a name="l00189"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#7010a5721ffc933e14d2a4249a2bcae1">00189</a> <span class="keyword">const</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#a7c774da0b1da3bf803e80642353a2eb">source</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#3da17b87de9397146aaebe56c6e9dabf">source_</a>; } <a name="l00190"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#f89a9e4fe8870136fc69a94db60c272d">00190</a> <span class="keyword">const</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#2ee41e994c997f93e43a62cb97e48b4a">dest</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#0a8d42859f0d63776ea0eebd9eeaff4a">dest_</a>; } <a name="l00191"></a>00191 <a name="l00192"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#a4b05c6e17d0b34e1b129c40c48ec094">00192</a> <span class="keyword">const</span> _EdgeInfo& <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#a4b05c6e17d0b34e1b129c40c48ec094">info</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#802f299c1a44c624ec034cb3e15c8b14">info_</a>; } <a name="l00193"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#9919f41c989d9e9bfe28dbf26a3dd81e">00193</a> _EdgeInfo& <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#9919f41c989d9e9bfe28dbf26a3dd81e">mutable_info</a>() { <span class="keywordflow">return</span> <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#802f299c1a44c624ec034cb3e15c8b14">info_</a>; } <a name="l00194"></a>00194 <a name="l00195"></a>00195 <span class="keyword">protected</span>: <a name="l00196"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#3da17b87de9397146aaebe56c6e9dabf">00196</a> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#3da17b87de9397146aaebe56c6e9dabf">source_</a>; <a name="l00197"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#0a8d42859f0d63776ea0eebd9eeaff4a">00197</a> <a class="code" href="classdtn_1_1MultiGraph_1_1Node.html" title="The node class.">Node</a>* <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#0a8d42859f0d63776ea0eebd9eeaff4a">dest_</a>; <a name="l00198"></a><a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#802f299c1a44c624ec034cb3e15c8b14">00198</a> _EdgeInfo <a class="code" href="classdtn_1_1MultiGraph_1_1Edge.html#802f299c1a44c624ec034cb3e15c8b14">info_</a>; <a name="l00199"></a>00199 }; <a name="l00200"></a>00200 <a name="l00201"></a><a class="code" href="classdtn_1_1MultiGraph.html#8da89fa48b9c6ef76cf3f700f2300115">00201</a> <span class="keyword">typedef</span> oasys::InlineFormatter<_EdgeInfo> <a class="code" href="classdtn_1_1MultiGraph.html#8da89fa48b9c6ef76cf3f700f2300115">EdgeFormatter</a>; <a name="l00202"></a>00202 <a name="l00204"></a><a class="code" href="classdtn_1_1MultiGraph_1_1NodeVector.html">00204</a> <span class="keyword">class </span><a class="code" href="classdtn_1_1MultiGraph_1_1NodeVector.html" title="Helper data structure for a vector of nodes.">NodeVector</a> : <span class="keyword">public</span> oasys::<a class="code" href="classoasys_1_1Formatter.html">Formatter</a>, <a name="l00205"></a>00205 <span class="keyword">public</span> std::<a class="code" href="classstd_1_1vector.html">vector</a><Node*> { <a name="l00206"></a>00206 <span class="keyword">public</span>: <a name="l00207"></a>00207 <span class="keywordtype">int</span> <a class="code" href="classdtn_1_1MultiGraph_1_1NodeVector.html#03d5e72d189741e9234582bfa3101b14">format</a>(<span class="keywordtype">char</span>* buf, <span class="keywordtype">size_t</span> sz) <span class="keyword">const</span>; <a name="l00208"></a><a class="code" href="classdtn_1_1MultiGraph_1_1NodeVector.html#39f722cc34f1ec1b5df8f4807da142ad">00208</a> std::string <a class="code" href="classdtn_1_1MultiGraph_1_1NodeVector.html#39f722cc34f1ec1b5df8f4807da142ad">dump</a>()<span class="keyword"> const</span> <a name="l00209"></a>00209 <span class="keyword"> </span>{ <a name="l00210"></a>00210 <span class="keywordtype">char</span> buf[1024]; <a name="l00211"></a>00211 <span class="keywordtype">int</span> <a class="code" href="num2sdnv_8c.html#fed088663f8704004425cdae2120b9b3">len</a> = <a class="code" href="classdtn_1_1MultiGraph_1_1NodeVector.html#03d5e72d189741e9234582bfa3101b14">format</a>(buf, <span class="keyword">sizeof</span>(buf)); <a name="l00212"></a>00212 <span class="keywordflow">return</span> std::string(buf, len); <a name="l00213"></a>00213 } <a name="l00214"></a>00214 }; <a name="l00215"></a>00215 <a name="l00217"></a><a class="code" href="classdtn_1_1MultiGraph_1_1EdgeVector.html">00217</a> <span class="keyword">class </span><a class="code" href="classdtn_1_1MultiGraph_1_1EdgeVector.html" title="Helper data structure for a vector of edges.">EdgeVector</a> : <span class="keyword">public</span> oasys::<a class="code" href="classoasys_1_1Formatter.html">Formatter</a>, <a name="l00218"></a>00218 <span class="keyword">public</span> std::<a class="code" href="classstd_1_1vector.html">vector</a><Edge*> { <a name="l00219"></a>00219 <span class="keyword">public</span>: <a name="l00220"></a>00220 <span class="keywordtype">int</span> <a class="code" href="classdtn_1_1MultiGraph_1_1EdgeVector.html#d7994817b0e71077cddf5408a0ed781c">format</a>(<span class="keywordtype">char</span>* buf, <span class="keywordtype">size_t</span> sz) <span class="keyword">const</span>; <a name="l00221"></a>00221 <span class="keywordtype">void</span> <a class="code" href="classdtn_1_1MultiGraph_1_1EdgeVector.html#523a4211f2e3aca1b2c6d3bb94871db8">debug_format</a>(oasys::StringBuffer* buf) <span class="keyword">const</span>; <a name="l00222"></a><a class="code" href="classdtn_1_1MultiGraph_1_1EdgeVector.html#c01b202040803b00989d4cc3d0737f39">00222</a> std::string <a class="code" href="classdtn_1_1MultiGraph_1_1EdgeVector.html#c01b202040803b00989d4cc3d0737f39">dump</a>()<span class="keyword"> const</span> <a name="l00223"></a>00223 <span class="keyword"> </span>{ <a name="l00224"></a>00224 <span class="keywordtype">char</span> buf[1024]; <a name="l00225"></a>00225 <span class="keywordtype">int</span> <a class="code" href="num2sdnv_8c.html#fed088663f8704004425cdae2120b9b3">len</a> = <a class="code" href="classdtn_1_1MultiGraph_1_1EdgeVector.html#d7994817b0e71077cddf5408a0ed781c">format</a>(buf, <span class="keyword">sizeof</span>(buf)); <a name="l00226"></a>00226 <span class="keywordflow">return</span> std::string(buf, len); <a name="l00227"></a>00227 } <a name="l00228"></a>00228 }; <a name="l00229"></a>00229 <a name="l00230"></a>00230 <span class="keyword">protected</span>: <a name="l00233"></a>00233 <span class="keywordtype">bool</span> <a class="code" href="classdtn_1_1MultiGraph.html#634989e9fdaa33497ebd44bf3dcb2f95" title="Helper function to follow the prev_ links that result from a Dijkstra search from...">get_reverse_path</a>(<span class="keyword">const</span> Node* a, <span class="keyword">const</span> Node* b, EdgeVector* path); <a name="l00234"></a>00234 <a name="l00236"></a><a class="code" href="classdtn_1_1MultiGraph.html#a195b6b49cc23c6af28dd923260b0641">00236</a> NodeVector <a class="code" href="classdtn_1_1MultiGraph.html#a195b6b49cc23c6af28dd923260b0641" title="The vector of all nodes.">nodes_</a>; <a name="l00237"></a>00237 }; <a name="l00238"></a>00238 <a name="l00239"></a>00239 } <span class="comment">// namespace dtn</span> <a name="l00240"></a>00240 <a name="l00241"></a>00241 <span class="preprocessor">#include "MultiGraph.tcc"</span> <a name="l00242"></a>00242 <a name="l00243"></a>00243 <span class="preprocessor">#endif </span><span class="comment">/* _MULTIGRAPH_H_ */</span> </pre></div></div> <hr size="1"><address style="text-align: right;"><small>Generated on Mon Jul 21 14:09:46 2008 for DTN Reference Implementation by <a href="http://www.doxygen.org/index.html"> <img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.5.6 </small></address> </body> </html>