adj__list_8h-source.html

这是一个用于数据挖掘的常用算法的模板库（数据挖掘的C++模板库for UNIX)

<a name="l00113"></a>00113   <span class="keyword">friend</span> ostream&amp; operator&lt;&lt; &lt;&gt;(ostream&amp;, <span class="keyword">const</span> <a class="code" href="structvertex__info.html">vertex_info&lt;VERTEX_T, EDGE_T, ALLOC&gt;</a>&amp;);
<a name="l00114"></a>00114 
<a name="l00116"></a><a class="code" href="structvertex__info.html#487be5ba6c64222a987df9935b35a7e3">00116</a>   VERTEX_T <a class="code" href="structvertex__info.html#487be5ba6c64222a987df9935b35a7e3">v</a>; <span class="comment">//vertex object</span>
<a name="l00117"></a>00117   <span class="keywordtype">int</span> id; <span class="comment">//id of this vertex</span>
<a name="l00118"></a>00118   EDGES out_edges; <span class="comment">//stores all edges for an undirected graph</span>
<a name="l00119"></a>00119   EDGES in_edges; <span class="comment">//calls to this member should be made only for digraphs</span>
<a name="l00120"></a>00120 
<a name="l00121"></a>00121 }; <span class="comment">//end struct vertex_info</span>
<a name="l00122"></a>00122 
<a name="l00123"></a>00123 <span class="comment">// overloaded extraction over a pair - used by following hash_map extraction</span>
<a name="l00124"></a>00124 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> E_T&gt;
<a name="l00125"></a>00125 ostream&amp; operator&lt;&lt; (ostream&amp; ostr, const std::pair&lt;int, E_T&gt;&amp; p) {
<a name="l00126"></a>00126   ostr&lt;&lt;<span class="stringliteral">"("</span>&lt;&lt;p.first&lt;&lt;<span class="stringliteral">" "</span>&lt;&lt;p.second&lt;&lt;<span class="stringliteral">")"</span>;
<a name="l00127"></a>00127   <span class="keywordflow">return</span> ostr;
<a name="l00128"></a>00128 }
<a name="l00129"></a>00129 
<a name="l00130"></a>00130 <span class="comment">// overloaded extraction over the edgelist map</span>
<a name="l00131"></a>00131 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> E_T&gt;
<a name="l00132"></a>00132 ostream&amp; operator&lt;&lt; (ostream&amp; ostr, const vector&lt;pair&lt;int, E_T&gt; &gt;&amp; hm) {
<a name="l00133"></a>00133   <span class="keyword">typename</span> vector&lt;pair&lt;int, E_T&gt; &gt;::const_iterator it;
<a name="l00134"></a>00134   <span class="keywordflow">for</span>(it=hm.begin(); it!=hm.end(); it++)
<a name="l00135"></a>00135     std::cout&lt;&lt;*it&lt;&lt;<span class="stringliteral">" "</span>;
<a name="l00136"></a>00136   <span class="keywordflow">return</span> ostr;
<a name="l00137"></a>00137 }
<a name="l00138"></a>00138 
<a name="l00139"></a>00139 
<a name="l00140"></a>00140 <span class="comment">//friend extraction over output streams</span>
<a name="l00141"></a>00141 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> V_T, <span class="keyword">typename</span> E_T&gt;
<a name="l00142"></a>00142 ostream&amp; operator&lt;&lt; (ostream&amp; ostr, const vertex_info&lt;V_T, E_T&gt;&amp; vi) {
<a name="l00143"></a>00143   ostr&lt;&lt;<span class="stringliteral">"["</span>&lt;&lt;vi.id&lt;&lt;<span class="stringliteral">"|"</span>&lt;&lt;vi.v&lt;&lt;<span class="stringliteral">"] OUT: "</span>;
<a name="l00144"></a>00144   <span class="keyword">typename</span> <a class="code" href="structvertex__info.html">vertex_info&lt;V_T, E_T&gt;::CONST_EIT</a> it;
<a name="l00145"></a>00145   ostr&lt;&lt;vi.out_edges;
<a name="l00146"></a>00146   ostr&lt;&lt;<span class="stringliteral">" IN: "</span>;
<a name="l00147"></a>00147   ostr&lt;&lt;vi.in_edges;
<a name="l00148"></a>00148   ostr&lt;&lt;endl;
<a name="l00149"></a>00149   <span class="keywordflow">return</span> ostr;
<a name="l00150"></a>00150 }<span class="comment">//end operator&lt;&lt;</span>
<a name="l00151"></a>00151 
<a name="l00152"></a>00152 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> V_T, <span class="keyword">typename</span> E_T, <span class="keyword">template</span> &lt;<span class="keyword">typename</span>&gt; <span class="keyword">class </span>ALLOC &gt;
<a name="l00153"></a>00153 <span class="keyword">class </span><a class="code" href="classadj__list.html">adj_list</a>;
<a name="l00154"></a>00154   
<a name="l00155"></a>00155 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> V_T, <span class="keyword">typename</span> E_T, <span class="keyword">template</span> &lt;<span class="keyword">typename</span>&gt; <span class="keyword">class </span>ALLOC &gt;
<a name="l00156"></a>00156 ostream&amp; operator&lt;&lt; (ostream&amp;, const adj_list&lt;V_T, E_T, ALLOC&gt;&amp;);
<a name="l00157"></a>00157 
<a name="l00164"></a>00164 <span class="keyword">template</span>&lt;<span class="keyword">typename</span> V_T, <span class="keyword">typename</span> E_T, <span class="keyword">template</span> &lt;<span class="keyword">typename</span>&gt; <span class="keyword">class </span>ALLOC=std::allocator&gt;
<a name="l00165"></a><a class="code" href="classadj__list.html">00165</a> <span class="keyword">class </span><a class="code" href="classadj__list.html">adj_list</a>
<a name="l00166"></a>00166 {
<a name="l00167"></a>00167 
<a name="l00168"></a>00168  <span class="keyword">public</span>:
<a name="l00169"></a>00169   <span class="keyword">typedef</span> V_T VERTEX_T;
<a name="l00170"></a>00170   <span class="keyword">typedef</span> E_T EDGE_T;
<a name="l00171"></a>00171   <span class="keyword">typedef</span> <a class="code" href="structvertex__info.html">vertex_info&lt;VERTEX_T, EDGE_T, ALLOC&gt;</a> <a class="code" href="structvertex__info.html">VERTEX_INFO</a>;
<a name="l00172"></a>00172   <span class="keyword">typedef</span> <a class="code" href="classadj__list.html">adj_list&lt;V_T, E_T, ALLOC &gt;</a> <a class="code" href="classadj__list.html">ADJ_L</a>;
<a name="l00173"></a>00173 
<a name="l00174"></a>00174   <span class="keyword">template</span>&lt;<span class="keyword">typename</span> T&gt;
<a name="l00175"></a>00175   <span class="keyword">class </span>VERTEX_LIST: <span class="keyword">public</span> std::vector&lt;T, ALLOC&lt;T&gt; &gt; {};<span class="comment">//each vertex and its info is stored as a vector, for fast lookup since we'll know its unique id</span>
<a name="l00176"></a>00176 
<a name="l00177"></a>00177   <span class="keyword">typedef</span> VERTEX_LIST&lt;VERTEX_INFO&gt; ADJ_LIST;
<a name="l00178"></a>00178 
<a name="l00179"></a>00179   <span class="keyword">typedef</span> <span class="keyword">typename</span> ADJ_LIST::iterator IT;
<a name="l00180"></a>00180   <span class="keyword">typedef</span> <span class="keyword">typename</span> ADJ_LIST::const_iterator CONST_IT;
<a name="l00181"></a>00181   <span class="keyword">typedef</span> <span class="keyword">typename</span> VERTEX_INFO::EIT EIT;
<a name="l00182"></a>00182   <span class="keyword">typedef</span> <span class="keyword">typename</span> VERTEX_INFO::CONST_EIT CONST_EIT;
<a name="l00183"></a>00183   <span class="keyword">typedef</span> std::pair&lt;EIT, EIT&gt; EIT_PAIR;
<a name="l00184"></a>00184   <span class="keyword">typedef</span> std::pair&lt;CONST_EIT, CONST_EIT&gt; CONST_EIT_PAIR;
<a name="l00185"></a>00185 
<a name="l00186"></a>00186   <span class="keywordtype">void</span>* operator new(size_t <a class="code" href="classadj__list.html#82beab1a8b5d2aaf00b5ee265ab7f8b9">size</a>) {
<a name="l00187"></a>00187     ALLOC&lt;ADJ_L&gt; aa;
<a name="l00188"></a>00188     <span class="keywordflow">return</span> aa.allocate(size);
<a name="l00189"></a>00189   }
<a name="l00190"></a>00190 
<a name="l00191"></a>00191   <span class="keywordtype">void</span>  operator delete(<span class="keywordtype">void</span> *p, size_t size) {
<a name="l00192"></a>00192     <span class="keywordflow">if</span> (p) {
<a name="l00193"></a>00193       ALLOC&lt;ADJ_L&gt; aa;
<a name="l00194"></a>00194       aa.deallocate(static_cast&lt;ADJ_L*&gt; (p), size);
<a name="l00195"></a>00195     }
<a name="l00196"></a>00196   }
<a name="l00197"></a>00197  
<a name="l00198"></a>00198   <span class="comment">//default constructor</span>
<a name="l00199"></a>00199   <a class="code" href="classadj__list.html">adj_list</a>() {}
<a name="l00200"></a>00200     
<a name="l00201"></a>00201   IT begin() {<span class="keywordflow">return</span> _alist.begin();}
<a name="l00202"></a>00202   CONST_IT begin()<span class="keyword"> const </span>{<span class="keywordflow">return</span> _alist.begin();}
<a name="l00203"></a>00203   IT end() {<span class="keywordflow">return</span> _alist.end();}
<a name="l00204"></a>00204   CONST_IT end()<span class="keyword"> const </span>{<span class="keywordflow">return</span> _alist.end();}
<a name="l00205"></a>00205 
<a name="l00206"></a>00206   <span class="keyword">inline</span>
<a name="l00207"></a><a class="code" href="classadj__list.html#82beab1a8b5d2aaf00b5ee265ab7f8b9">00207</a>   <span class="keywordtype">int</span> <a class="code" href="classadj__list.html#82beab1a8b5d2aaf00b5ee265ab7f8b9">size</a>()<span class="keyword"> const </span>{<span class="keywordflow">return</span> _alist.size();} 
<a name="l00208"></a>00208   <span class="keywordtype">void</span> clear() {_alist.clear();}
<a name="l00209"></a>00209   <span class="keywordtype">void</span> push_back(<span class="keyword">const</span> VERTEX_INFO&amp; vi) {_alist.push_back(vi);}
<a name="l00210"></a>00210 
<a name="l00212"></a>00212   IT <a class="code" href="classadj__list.html#91205b35a8ce0ca20ce43aab5b39d87d">vertex_vals</a>(<span class="keyword">const</span> <span class="keywordtype">int</span>&amp;);
<a name="l00213"></a>00213 
<a name="l00214"></a>00214   CONST_IT <a class="code" href="classadj__list.html#91205b35a8ce0ca20ce43aab5b39d87d">vertex_vals</a>(<span class="keyword">const</span> <span class="keywordtype">int</span>&amp; idval)<span class="keyword"> const </span>{
<a name="l00215"></a>00215     CONST_IT it=_alist.begin();
<a name="l00216"></a>00216     <span class="keywordflow">if</span>(idval&gt;<a class="code" href="classadj__list.html#82beab1a8b5d2aaf00b5ee265ab7f8b9">size</a>()-1) {
<a name="l00217"></a>00217   std::cerr&lt;&lt;<span class="stringliteral">"adj_list.vertex_vals: out of range vertex id, "</span>&lt;&lt;idval&lt;&lt;endl;
<a name="l00218"></a>00218   exit(0);
<a name="l00219"></a>00219     }
<a name="l00220"></a>00220     it+=idval;
<a name="l00221"></a>00221     <span class="keywordflow">return</span> it;
<a name="l00222"></a>00222   }<span class="comment">// end vertex_vals() const</span>
<a name="l00223"></a>00223 
<a name="l00226"></a><a class="code" href="classadj__list.html#528f1fe0f4e10a6627285be96bfbb2d1">00226</a>   std::pair&lt;EIT, EIT&gt; <a class="code" href="classadj__list.html#528f1fe0f4e10a6627285be96bfbb2d1">out_edges</a>(<span class="keyword">const</span> <span class="keywordtype">int</span>&amp; idval) {
<a name="l00227"></a>00227     IT it=<a class="code" href="classadj__list.html#91205b35a8ce0ca20ce43aab5b39d87d">vertex_vals</a>(idval);
<a name="l00228"></a>00228     <span class="keywordflow">return</span> make_pair(it-&gt;out_begin(), it-&gt;out_end());
<a name="l00229"></a>00229   }<span class="comment">//end out_edges()</span>