graph__evat_8h-source.html

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

<a name="l00125"></a>00125 
<a name="l00126"></a>00126     <span class="keywordtype">int</span> offset_v1;
<a name="l00127"></a>00127     
<a name="l00128"></a>00128     <span class="keywordtype">bool</span> swap_vids; <span class="comment">// flag to denote if vids in evat_v2 should be swapped </span>
<a name="l00129"></a>00129                     <span class="comment">// before appending to v1</span>
<a name="l00130"></a>00130     <span class="keywordtype">bool</span> l2_swap=0; <span class="comment">// flag to denote if vids in v1 should be swapped </span>
<a name="l00131"></a>00131                     <span class="comment">// before insertion to vat; this occurs in the special case when l2_eq=1 </span>
<a name="l00132"></a>00132 
<a name="l00133"></a>00133     <span class="keywordflow">for</span>(it_evat_v1=evat_v1.<a class="code" href="classevat.html#576e837271071e10535be5b0276c06c6">begin</a>(), offset_v1=0; it_evat_v1!=evat_v1.<a class="code" href="classevat.html#eb2eff3b7a1e3a340731d33ecb472ebf">end</a>(); it_evat_v1++, offset_v1++) {
<a name="l00134"></a>00134 #ifdef PRINT
<a name="l00135"></a>00135       cout&lt;&lt;<span class="stringliteral">"evat_v1="</span>&lt;&lt;it_evat_v1-&gt;first&lt;&lt;<span class="stringliteral">" "</span>&lt;&lt;it_evat_v1-&gt;second&lt;&lt;endl;
<a name="l00136"></a>00136 #endif
<a name="l00137"></a>00137       <span class="keywordflow">for</span>(it_evat_v2=evat_v2.<a class="code" href="classevat.html#576e837271071e10535be5b0276c06c6">begin</a>(); it_evat_v2!=evat_v2.<a class="code" href="classevat.html#eb2eff3b7a1e3a340731d33ecb472ebf">end</a>(); it_evat_v2++) {
<a name="l00138"></a>00138 #ifdef PRINT
<a name="l00139"></a>00139         cout&lt;&lt;<span class="stringliteral">"evat_v2="</span>&lt;&lt;it_evat_v2-&gt;first&lt;&lt;<span class="stringliteral">" "</span>&lt;&lt;it_evat_v2-&gt;second&lt;&lt;endl;
<a name="l00140"></a>00140 #endif
<a name="l00141"></a>00141 
<a name="l00147"></a>00147 
<a name="l00148"></a>00148         <span class="keywordflow">if</span>(!new_edge_state) { <span class="comment">// both vertex labels of new edge are same</span>
<a name="l00149"></a>00149           <span class="keywordflow">if</span>(l2_eq) {
<a name="l00150"></a>00150             <span class="comment">// this is extension of level-2 with same labels</span>
<a name="l00151"></a>00151             <span class="comment">// now, we have to check all four possibilities for a </span>
<a name="l00152"></a>00152             <span class="comment">// match here, since all four labels are equal</span>
<a name="l00153"></a>00153             <span class="keywordflow">if</span>(it_evat_v1-&gt;second==it_evat_v2-&gt;first) {
<a name="l00154"></a>00154               swap_vids=0;
<a name="l00155"></a>00155               l2_swap=0;
<a name="l00156"></a>00156             }
<a name="l00157"></a>00157             <span class="keywordflow">else</span> <span class="keywordflow">if</span>(it_evat_v1-&gt;second==it_evat_v2-&gt;second) {
<a name="l00158"></a>00158               swap_vids=1;
<a name="l00159"></a>00159               l2_swap=0;
<a name="l00160"></a>00160             }
<a name="l00161"></a>00161             <span class="keywordflow">else</span> <span class="keywordflow">if</span>(it_evat_v1-&gt;first==it_evat_v2-&gt;first) {
<a name="l00162"></a>00162               swap_vids=0;
<a name="l00163"></a>00163               l2_swap=1;
<a name="l00164"></a>00164             }
<a name="l00165"></a>00165             <span class="keywordflow">else</span> <span class="keywordflow">if</span>(it_evat_v1-&gt;first==it_evat_v2-&gt;second) {
<a name="l00166"></a>00166               swap_vids=1;
<a name="l00167"></a>00167               l2_swap=1;
<a name="l00168"></a>00168             }
<a name="l00169"></a>00169             <span class="keywordflow">else</span>
<a name="l00170"></a>00170               <span class="keywordflow">continue</span>;
<a name="l00171"></a>00171           }<span class="comment">//if(l2_eq)</span>
<a name="l00172"></a>00172           <span class="keywordflow">else</span> {
<a name="l00173"></a>00173             <span class="keywordflow">if</span>(is_fwd_chain) {
<a name="l00174"></a>00174               <span class="keywordflow">if</span>(it_evat_v1-&gt;second!=it_evat_v2-&gt;first)
<a name="l00175"></a>00175                 <span class="keywordflow">if</span>(it_evat_v1-&gt;second!=it_evat_v2-&gt;second) <span class="comment">// none of the vids in v2 matches</span>
<a name="l00176"></a>00176                   <span class="keywordflow">continue</span>;
<a name="l00177"></a>00177                 <span class="keywordflow">else</span>
<a name="l00178"></a>00178                   swap_vids=1;
<a name="l00179"></a>00179               <span class="keywordflow">else</span>
<a name="l00180"></a>00180                   swap_vids=0;
<a name="l00181"></a>00181             }
<a name="l00182"></a>00182             <span class="keywordflow">else</span> {
<a name="l00183"></a>00183               <span class="keywordflow">if</span>(it_evat_v1-&gt;first!=it_evat_v2-&gt;first)
<a name="l00184"></a>00184                 <span class="keywordflow">if</span>(it_evat_v1-&gt;first!=it_evat_v2-&gt;second) <span class="comment">// none of the vids in v2 matches</span>
<a name="l00185"></a>00185                   <span class="keywordflow">continue</span>;
<a name="l00186"></a>00186                 <span class="keywordflow">else</span>
<a name="l00187"></a>00187                   swap_vids=1;
<a name="l00188"></a>00188               <span class="keywordflow">else</span>
<a name="l00189"></a>00189                 swap_vids=0;
<a name="l00190"></a>00190             }
<a name="l00191"></a>00191           } <span class="comment">//else l2_eq</span>
<a name="l00192"></a>00192         } <span class="comment">//if !new_edge_state</span>
<a name="l00193"></a>00193         <span class="keywordflow">else</span> { <span class="comment">// vertex labels of new edge are different</span>
<a name="l00194"></a>00194           swap_vids=new_edge_state-1; <span class="comment">// swap if edge is of the form B-A</span>
<a name="l00195"></a>00195                                       <span class="comment">// but not if A-B</span>
<a name="l00196"></a>00196 
<a name="l00197"></a>00197           <span class="keywordflow">if</span>(l2_eq) { <span class="comment">// special case for L-2 with same labelled first edge</span>
<a name="l00198"></a>00198             <span class="keywordflow">if</span>(!swap_vids) {
<a name="l00199"></a>00199               <span class="keywordflow">if</span>(it_evat_v1-&gt;first!=it_evat_v2-&gt;first)
<a name="l00200"></a>00200                 <span class="keywordflow">if</span>(it_evat_v1-&gt;second!=it_evat_v2-&gt;first)
<a name="l00201"></a>00201                   <span class="keywordflow">continue</span>; <span class="comment">// no matching vids</span>
<a name="l00202"></a>00202                 <span class="keywordflow">else</span>
<a name="l00203"></a>00203                   l2_swap=0;
<a name="l00204"></a>00204               <span class="keywordflow">else</span>
<a name="l00205"></a>00205                 l2_swap=1;
<a name="l00206"></a>00206             }
<a name="l00207"></a>00207             <span class="keywordflow">else</span> {
<a name="l00208"></a>00208               <span class="keywordflow">if</span>(it_evat_v1-&gt;first!=it_evat_v2-&gt;second)
<a name="l00209"></a>00209                 <span class="keywordflow">if</span>(it_evat_v1-&gt;second!=it_evat_v2-&gt;second)
<a name="l00210"></a>00210                   <span class="keywordflow">continue</span>; <span class="comment">// no matching vids</span>
<a name="l00211"></a>00211                 <span class="keywordflow">else</span>
<a name="l00212"></a>00212                   l2_swap=0;
<a name="l00213"></a>00213               <span class="keywordflow">else</span>
<a name="l00214"></a>00214                 l2_swap=1;
<a name="l00215"></a>00215             }
<a name="l00216"></a>00216           }
<a name="l00217"></a>00217           <span class="keywordflow">else</span> {
<a name="l00218"></a>00218             <span class="keywordflow">if</span>(is_fwd_chain) {
<a name="l00219"></a>00219               <span class="keywordflow">if</span>(swap_vids &amp;&amp; it_evat_v1-&gt;second!=it_evat_v2-&gt;second)
<a name="l00220"></a>00220                 <span class="keywordflow">continue</span>;
<a name="l00221"></a>00221               <span class="keywordflow">if</span>(!swap_vids &amp;&amp; it_evat_v1-&gt;second!=it_evat_v2-&gt;first)
<a name="l00222"></a>00222                 <span class="keywordflow">continue</span>;
<a name="l00223"></a>00223             }
<a name="l00224"></a>00224             <span class="keywordflow">else</span> {
<a name="l00225"></a>00225               <span class="keywordflow">if</span>(swap_vids) {
<a name="l00226"></a>00226                 cerr&lt;&lt;<span class="stringliteral">"evat.fwd_intersect: swap_vids="</span>&lt;&lt;swap_vids&lt;&lt;<span class="stringliteral">" for !fwd_chain. This candidate should not have been canonical"</span>&lt;&lt;endl;
<a name="l00227"></a>00227                 <span class="keywordflow">return</span>;
<a name="l00228"></a>00228               }
<a name="l00229"></a>00229               <span class="keywordflow">if</span>(it_evat_v1-&gt;first!=it_evat_v2-&gt;first)
<a name="l00230"></a>00230                 <span class="keywordflow">continue</span>;
<a name="l00231"></a>00231             }
<a name="l00232"></a>00232           }
<a name="l00233"></a>00233         } <span class="comment">//else !new_edge_state</span>
<a name="l00234"></a>00234 
<a name="l00235"></a>00235         <span class="keywordflow">if</span>(!swap_vids) {
<a name="l00236"></a>00236           <span class="keywordflow">if</span>(!vat_v1.is_new_vertex(it_evat_v2-&gt;second, tid, offset_v1))
<a name="l00237"></a>00237             <span class="keywordflow">continue</span>;
<a name="l00238"></a>00238         }
<a name="l00239"></a>00239         <span class="keywordflow">else</span>
<a name="l00240"></a>00240           <span class="keywordflow">if</span>(!vat_v1.is_new_vertex(it_evat_v2-&gt;first, tid, offset_v1))
<a name="l00241"></a>00241             <span class="keywordflow">continue</span>;
<a name="l00242"></a>00242 <span class="preprocessor">#ifdef PRINT        </span>
<a name="l00243"></a>00243 <span class="preprocessor"></span>        cout&lt;&lt;<span class="stringliteral">"evat::fwd_intersect: valid fwd extension"</span>&lt;&lt;endl;
<a name="l00244"></a>00244 <span class="preprocessor">#endif</span>
<a name="l00246"></a>00246 <span class="preprocessor">        // first append common evats from v1's rmp</span>
<a name="l00247"></a>00247 <span class="preprocessor"></span>        <span class="keywordflow">if</span>(!cand_vat.empty() &amp;&amp; cand_vat.back().first==v1.first) { <span class="comment">// this tid exists</span>
<a name="l00248"></a>00248           <span class="keywordflow">if</span>(rmp_index&gt;0)
<a name="l00249"></a>00249             cand_vat.copy_vats(v1, offset_v1, rmp_index, l2_swap);
<a name="l00250"></a>00250           cand_vat.copy_vids_hs(v1_vids[offset_v1]);
<a name="l00251"></a>00251         }
<a name="l00252"></a>00252         <span class="keywordflow">else</span> { <span class="comment">// this is a new tid, create a new entry in vat</span>
<a name="l00253"></a>00253           <span class="keywordflow">if</span>(rmp_index&gt;0)
<a name="l00254"></a>00254             cand_vat.copy_vats_tid(v1, offset_v1, rmp_index, l2_swap);
<a name="l00255"></a>00255           cand_vat.copy_vids_tid(v1_vids[offset_v1]);
<a name="l00256"></a>00256         }
<a name="l00257"></a>00257 
<a name="l00258"></a>00258 <span class="preprocessor">#ifdef PRINT    </span>
<a name="l00259"></a>00259 <span class="preprocessor"></span>        cout&lt;&lt;<span class="stringliteral">"evat::fwd_intersect: appending new_occurrence"</span>&lt;&lt;endl;
<a name="l00260"></a>00260 <span class="preprocessor">#endif    </span>