📄 graph__vat_8h-source.html
字号:
<a name="l00149"></a>00149 <a name="l00150"></a>00150 <span class="keywordtype">void</span> insert_occurrence(<span class="keyword">const</span> pair<int, int>& new_occurrence) {<a name="l00151"></a>00151 _vat.back().second.back().push_back(new_occurrence);<a name="l00152"></a>00152 }<a name="l00153"></a>00153 <a name="l00154"></a>00154 <a name="l00155"></a>00155 <span class="keywordtype">void</span> insert_vid_hs(<span class="keyword">const</span> <span class="keywordtype">int</span>& vid) { <a name="l00156"></a>00156 VSET vs;<a name="l00157"></a>00157 vs.insert(vid);<a name="l00158"></a>00158 _vids.back().push_back(vs);<a name="l00159"></a>00159 }<a name="l00160"></a>00160 <a name="l00161"></a>00161 <a name="l00162"></a>00162 <span class="keywordtype">void</span> insert_vid(<span class="keyword">const</span> <span class="keywordtype">int</span>& vid) { <a name="l00163"></a>00163 _vids.back().back().insert(vid);<a name="l00164"></a>00164 }<a name="l00165"></a>00165 <a name="l00166"></a>00166 <a name="l00167"></a>00167 <span class="keywordtype">void</span> insert_vid_tid(<span class="keyword">const</span> <span class="keywordtype">int</span>& vid) {<a name="l00168"></a>00168 VSET vset;<a name="l00169"></a>00169 vset.insert(vid);<a name="l00170"></a>00170 vector<VSET, ALLOC<VSET> > vsets;<a name="l00171"></a>00171 vsets.push_back(vset);<a name="l00172"></a>00172 _vids.push_back(vsets); <a name="l00173"></a>00173 }<span class="comment">//insert_vid_tid()</span><a name="l00174"></a>00174 <a name="l00175"></a>00175 <a name="l00176"></a>00176 <span class="keywordtype">void</span> copy_vats(<span class="keyword">const</span> pair<<span class="keywordtype">int</span>, ST<<a class="code" href="classevat.html">evat<ALLOC></a>, ALLOC<<a class="code" href="classevat.html">evat<ALLOC></a> > > >& v1, <span class="keyword">const</span> <span class="keywordtype">int</span>& offset, <span class="keyword">const</span> <span class="keywordtype">int</span>& sz, <span class="keywordtype">bool</span> swap=0) {<a name="l00177"></a>00177 <span class="keywordtype">int</span> i;<a name="l00178"></a>00178 <span class="keywordflow">for</span>(i=0; i<sz; i++)<a name="l00179"></a>00179 <span class="keywordflow">if</span>(swap)<a name="l00180"></a>00180 _vat.back().second[i].push_back(make_pair(v1.second[i][offset].second, v1.second[i][offset].first));<a name="l00181"></a>00181 <span class="keywordflow">else</span><a name="l00182"></a>00182 _vat.back().second[i].push_back(v1.second[i][offset]);<a name="l00183"></a>00183 }<span class="comment">//copy_vats()</span><a name="l00184"></a>00184 <a name="l00185"></a>00185 <a name="l00186"></a>00186 <span class="keywordtype">void</span> copy_vats_tid(<span class="keyword">const</span> pair<<span class="keywordtype">int</span>, ST<<a class="code" href="classevat.html">evat<ALLOC></a>, ALLOC<<a class="code" href="classevat.html">evat<ALLOC></a> > > >& v1, <span class="keyword">const</span> <span class="keywordtype">int</span>& offset, <span class="keyword">const</span> <span class="keywordtype">int</span>& sz, <span class="keywordtype">bool</span> swap=0) {<a name="l00187"></a>00187 <span class="keywordtype">int</span> i;<a name="l00188"></a>00188 ST<EVAT, ALLOC<EVAT> > new_entry;<a name="l00189"></a>00189 <a name="l00190"></a>00190 <span class="keywordflow">for</span>(i=0; i<sz; i++) {<a name="l00191"></a>00191 <a class="code" href="classevat.html">evat<ALLOC></a> tmp_evat;<a name="l00192"></a>00192 <span class="keywordflow">if</span>(swap)<a name="l00193"></a>00193 tmp_evat.push_back(make_pair(v1.second[i][offset].second, v1.second[i][offset].first));<a name="l00194"></a>00194 <span class="keywordflow">else</span><a name="l00195"></a>00195 tmp_evat.push_back(v1.second[i][offset]);<a name="l00196"></a>00196 new_entry.push_back(tmp_evat);<a name="l00197"></a>00197 }<a name="l00198"></a>00198 _vat.push_back(make_pair(v1.first, new_entry));<a name="l00199"></a>00199 }<span class="comment">//copy_vats_tid()</span><a name="l00200"></a>00200 <a name="l00201"></a>00201 <a name="l00202"></a>00202 <span class="keywordtype">void</span> copy_vids_hs(<span class="keyword">const</span> VSET& v1_vids) {<a name="l00203"></a>00203 <a name="l00204"></a>00204 VSET vs;<a name="l00205"></a>00205 <span class="keyword">typename</span> VSET::const_iterator it;<a name="l00206"></a>00206 <span class="keywordflow">for</span>(it=v1_vids.begin(); it!=v1_vids.end(); it++)<a name="l00207"></a>00207 vs.insert(*it);<a name="l00208"></a>00208 _vids.back().push_back(vs);<a name="l00209"></a>00209 }<span class="comment">//copy_vids()</span><a name="l00210"></a>00210 <a name="l00211"></a>00211 <a name="l00212"></a>00212 <span class="keywordtype">void</span> copy_vids_tid(<span class="keyword">const</span> VSET& v1_vids) {<a name="l00213"></a>00213 VSET vset;<a name="l00214"></a>00214 <span class="keyword">typename</span> VSET::const_iterator it;<a name="l00215"></a>00215 <span class="keywordflow">for</span>(it=v1_vids.begin(); it!=v1_vids.end(); it++)<a name="l00216"></a>00216 vset.insert(*it);<a name="l00217"></a>00217 vector<VSET, ALLOC<VSET> > vsets;<a name="l00218"></a>00218 vsets.push_back(vset);<a name="l00219"></a>00219 _vids.push_back(vsets);<a name="l00220"></a>00220 }<span class="comment">//copy_vids_tid()</span><a name="l00221"></a>00221 <a name="l00222"></a>00222 <a name="l00225"></a>00225 <span class="comment">// NOTE: only one candidate is generated in a FkxF1 join of graphs, </span><a name="l00226"></a>00226 <span class="comment">// hence only the first value in cand_pats should be inspected</span><a name="l00227"></a>00227 <span class="keyword">template</span><<span class="keyword">typename</span> PATTERN, <span class="keyword">typename</span> PAT_SUP><a name="l00228"></a><a class="code" href="classvat_3_01GRAPH__PROP_00_01V__Fk1__MINE__PROP_00_01ALLOC_00_01ST_01_4.html#867248a3e91c6b8d64b30fd3e5988ef7">00228</a> <span class="keyword">static</span> <a class="code" href="classvat_3_01GRAPH__PROP_00_01V__Fk1__MINE__PROP_00_01ALLOC_00_01ST_01_4.html">VAT</a>** intersection(<span class="keyword">const</span> <a class="code" href="classvat_3_01GRAPH__PROP_00_01V__Fk1__MINE__PROP_00_01ALLOC_00_01ST_01_4.html">VAT</a>* v1, <span class="keyword">const</span> <a class="code" href="classvat_3_01GRAPH__PROP_00_01V__Fk1__MINE__PROP_00_01ALLOC_00_01ST_01_4.html">VAT</a>* v2, PAT_SUP** cand_sups, PATTERN** cand_pats, <span class="keywordtype">bool</span>) {<a name="l00229"></a>00229 <span class="preprocessor">#ifdef PRINT</span><a name="l00230"></a>00230 <span class="preprocessor"></span> cout<<<span class="stringliteral">"VAT intersection entered with v1="</span><<v1<<endl;<a name="l00231"></a>00231 cout<<<span class="stringliteral">"v2="</span><<v2<<endl;<a name="l00232"></a>00232 <span class="preprocessor">#endif</span><a name="l00233"></a>00233 <span class="preprocessor"></span><a name="l00234"></a>00234 tt_vat.<a class="code" href="classtime__tracker.html#cbe4e1e72cf61ff3f4c135e161fc5a50">start</a>();<a name="l00235"></a>00235 <a name="l00236"></a>00236 <span class="comment">// How it works</span><a name="l00237"></a>00237 <span class="comment">// 1. determine which edge of v1 is being extended and get its evat1</span><a name="l00238"></a>00238 <span class="comment">// 2. determine right-most-path of candidate (rmp)</span><a name="l00239"></a>00239 <span class="comment">// 3. find common occurrences in v2 and evat1</span><a name="l00240"></a>00240 <span class="comment">// 4. copy these common occurrences to new_vat, and also copy evats in </span><a name="l00241"></a>00241 <span class="comment">// rmp corresponding to these common occurrences</span><a name="l00242"></a>00242 <a name="l00243"></a>00243 <a class="code" href="classvat_3_01GRAPH__PROP_00_01V__Fk1__MINE__PROP_00_01ALLOC_00_01ST_01_4.html">VAT</a>* cand_vat=<span class="keyword">new</span> <a class="code" href="classvat_3_01GRAPH__PROP_00_01V__Fk1__MINE__PROP_00_01ALLOC_00_01ST_01_4.html">VAT</a>;<a name="l00244"></a>00244 <span class="keywordtype">bool</span> is_fwd;<a name="l00245"></a>00245 <span class="keywordtype">bool</span> is_fwd_chain=<span class="keyword">false</span>; <span class="comment">// flag to denote whether edge appended by </span><a name="l00246"></a>00246 <span class="comment">// intersection is at the root (which is when flag=0)</span><a name="l00247"></a>00247 <span class="keywordtype">bool</span> l2_eq=(cand_pats[0]->size()==3) && (cand_pats[0]->label(0)==cand_pats[0]->label(1)); <span class="comment">// special case in evat intersection for L-2 with first edge </span><a name="l00248"></a>00248 <span class="comment">// with equal vertex labels</span><a name="l00249"></a>00249 <a name="l00250"></a>00250 <span class="keywordtype">int</span> rmp_index; <span class="comment">// index of last vid on rmp common to cand_pat and its </span><a name="l00251"></a>00251 <span class="comment">// parent's rmp</span><a name="l00252"></a>00252 <span class="keywordtype">int</span> new_edge_state=-1; <span class="comment">// flag to denote if the new edge to be added has </span><a name="l00253"></a>00253 <span class="comment">// same labeled vertices, of the form A-A (flag=0); or is of the form </span><a name="l00254"></a>00254 <span class="comment">// A-B (flag=1); or is not canonical at all, of the form B-A (flag=2).</span><a name="l00255"></a>00255 <span class="comment">// evat intersection needs to take this into account</span><a name="l00256"></a>00256 <a name="l00257"></a>00257 <span class="keywordtype">int</span> rvid=cand_pats[0]->rmost_vid();<a name="l00258"></a>00258 <span class="keywordtype">int</span> edge_vid=-1; <span class="comment">// vid of the other vertex (other than rvid) connected </span><a name="l00259"></a>00259 <span class="comment">// to rvid as to form the new edge</span><a name="l00260"></a>00260 <a name="l00261"></a>00261 <span class="keyword">typename</span> PATTERN::CONST_EIT_PAIR eit_p=cand_pats[0]->out_edges(rvid);<a name="l00262"></a>00262 <span class="keywordtype">int</span> back_idx=-1; <span class="comment">// this is used only for back extensions. It holds the </span><a name="l00263"></a>00263 <span class="comment">// index of edge_vid in rmp of cand_pats[0]</span><a name="l00264"></a>00264 <a name="l00265"></a>00265 <span class="keywordflow">if</span>(eit_p.second-eit_p.first>1)<a name="l00266"></a>00266 is_fwd=<span class="keyword">false</span>; <span class="comment">// last edge was fwd edge only if outdegree of last vid=1</span><a name="l00267"></a>00267 <span class="keywordflow">else</span><a name="l00268"></a>00268 is_fwd=<span class="keyword">true</span>;<a name="l00269"></a>00269 <a name="l00270"></a>00270 <span class="comment">// get other vertex's vid</span><a name="l00271"></a>00271 <span class="keywordflow">if</span>(is_fwd) {<a name="l00272"></a>00272 edge_vid=eit_p.first->first;<a name="l00273"></a>00273 <span class="keywordflow">if</span>(!edge_vid) <span class="comment">// rvid is attached to the root</span><a name="l00274"></a>00274 is_fwd_chain=0;<a name="l00275"></a>00275 <span class="keywordflow">else</span><a name="l00276"></a>00276 is_fwd_chain=1;<a name="l00277"></a>00277 }<a name="l00278"></a>00278 <span class="keywordflow">else</span> {<a name="l00279"></a>00279 <span class="comment">//prev_vid=eit_p.first->first;</span><a name="l00280"></a>00280 eit_p.second--;<a name="l00281"></a>00281 edge_vid=eit_p.second->first;<a name="l00282"></a>00282 <a name="l00285"></a>00285 <span class="comment">// TO DO: this is currently a linear search through rmp, is there a </span><a name="l00286"></a>00286 <span class="comment">// more efficient way??</span><a name="l00287"></a>00287 <span class="keyword">const</span> <span class="keyword">typename</span> PATTERN::RMP_T& cand_rmp=cand_pats[0]->rmost_path();<a name="l00288"></a>00288 <span class="keywordflow">for</span>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0; i<cand_rmp.size(); i++) {<a name="l00289"></a>00289 <span class="keywordflow">if</span>(cand_rmp[i]==edge_vid) {<a name="l00290"></a>00290 back_idx=i;<a name="l00291"></a>00291 <span class="keywordflow">break</span>;<a name="l00292"></a>00292 }<a name="l00293"></a>00293 }<a name="l00294"></a>00294 <a name="l00295"></a>00295 <span class="keywordflow">if</span>(back_idx==-1) {<a name="l00296"></a>00296 cerr<<<span class="stringliteral">"vat.intersect: back_idx not found for edge_vid="</span><<edge_vid<<<span class="stringliteral">" in rmp.size="</span><<cand_rmp.size()<<endl;⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -