📄 graph__iso__check_8h-source.html
字号:
<a name="l00307"></a>00307 <a name="l00308"></a>00308 <span class="comment">// atleast 2 nodes prior to last one</span><a name="l00309"></a>00309 <span class="keywordflow">if</span>(new_code.cid(eit_p.first->first)<back_vid <span class="comment">// this vertex is farthest one seen so far</span><a name="l00310"></a>00310 && new_code.cid(eit_p.first->first)>last_back_vid) { <span class="comment">// a valid back edge must end </span><a name="l00311"></a>00311 <span class="comment">// at a vertex after last_back_vid</span><a name="l00312"></a>00312 back_vid=new_code.cid(eit_p.first->first);<a name="l00313"></a>00313 e=eit_p.first->second;<a name="l00314"></a>00314 }<a name="l00315"></a>00315 eit_p.first++;<a name="l00316"></a>00316 }<a name="l00317"></a>00317 <a name="l00318"></a>00318 <span class="keywordflow">if</span>(back_vid!=last_vid) {<a name="l00319"></a>00319 <span class="comment">// valid back edge found</span><a name="l00320"></a>00320 <span class="keyword">typename</span> PATTERN::VERTEX_T lbl1=cand_pat->label(new_code.gid(last_vid));<a name="l00321"></a>00321 <span class="keyword">typename</span> PATTERN::VERTEX_T lbl2=cand_pat->label(new_code.gid(back_vid));<a name="l00322"></a>00322 <span class="keyword">typename</span> CAN_CODE::FIVE_TUPLE new_tuple(last_vid, back_vid, lbl1, e, lbl2);<a name="l00323"></a>00323 <span class="keywordflow">if</span>(new_tuple<current_code[code_index]) {<a name="l00324"></a>00324 <span class="preprocessor">#ifdef PRINT</span><a name="l00325"></a>00325 <span class="preprocessor"></span> cout<<<span class="stringliteral">"decision at back-edge: new tuple is more minimal"</span><<endl;<a name="l00326"></a>00326 cout<<<span class="stringliteral">"new_tuple="</span><<new_tuple<<endl;<a name="l00327"></a>00327 cout<<<span class="stringliteral">"curent_tuple="</span><<current_code[code_index]<<endl;<a name="l00328"></a>00328 cout<<<span class="stringliteral">"current_code"</span><<current_code<<endl;<a name="l00329"></a>00329 <span class="preprocessor">#endif</span><a name="l00330"></a>00330 <span class="preprocessor"></span> <span class="keywordflow">return</span> <span class="keyword">false</span>;<a name="l00331"></a>00331 }<a name="l00332"></a>00332 <a name="l00333"></a>00333 <span class="keywordflow">if</span>(current_code[code_index]<new_tuple) {<a name="l00334"></a>00334 <span class="preprocessor">#ifdef PRINT</span><a name="l00335"></a>00335 <span class="preprocessor"></span> cout<<<span class="stringliteral">"decision at back-edge: current tuple is more minimal"</span><<endl;<a name="l00336"></a>00336 cout<<<span class="stringliteral">"new_tuple="</span><<new_tuple<<endl;<a name="l00337"></a>00337 cout<<<span class="stringliteral">"curent_tuple="</span><<current_code[code_index]<<endl;<a name="l00338"></a>00338 cout<<<span class="stringliteral">"current_code"</span><<current_code<<endl;<a name="l00339"></a>00339 <span class="preprocessor">#endif</span><a name="l00340"></a>00340 <span class="preprocessor"></span> <span class="keywordflow">return</span> <span class="keyword">true</span>;<a name="l00341"></a>00341 }<a name="l00342"></a>00342 <span class="keywordflow">else</span> {<a name="l00343"></a>00343 new_code.append(new_tuple);<a name="l00344"></a>00344 <span class="comment">// no changes to new_code's rmp, nor to the cid-gid mappings since</span><a name="l00345"></a>00345 <span class="comment">// back edge implies both vertices were already present in it</span><a name="l00346"></a>00346 <span class="keywordflow">return</span> minimal(cand_pat, new_code);<a name="l00347"></a>00347 }<a name="l00348"></a>00348 }<a name="l00349"></a>00349 <a name="l00350"></a>00350 <span class="comment">// execution gets here iff back-edge add failed</span><a name="l00352"></a>00352 <span class="comment"></span> <span class="comment">// how to: find the deepest outgoing edge, and among all such edges find the </span><a name="l00353"></a>00353 <span class="comment">// minimal one, i.e. least edge-label + least dest-label</span><a name="l00354"></a>00354 <a name="l00355"></a>00355 <span class="keywordtype">bool</span> fwd_found=<span class="keyword">false</span>;<a name="l00356"></a>00356 rmp_it=rmp.end()-1;<a name="l00357"></a>00357 last_vid=*rmp_it;<a name="l00358"></a>00358 vector<int> new_vids; <span class="comment">// equivalent minimal vertices whose minimality has to be checked recursively</span><a name="l00359"></a>00359 e=ed_prsr.parse_element(INF_LABEL);<a name="l00360"></a>00360 <span class="keyword">typename</span> PATTERN::VERTEX_T dest_v=vt_prsr.parse_element(INF_LABEL);<a name="l00361"></a>00361 <a name="l00362"></a>00362 <span class="keywordflow">while</span>(rmp_it>=rmp.begin()) {<a name="l00363"></a>00363 <span class="comment">// get neighbors of current vertex</span><a name="l00364"></a>00364 eit_p=cand_pat->out_edges(new_code.gid(*rmp_it));<a name="l00365"></a>00365 <a name="l00366"></a>00366 <span class="comment">// try to find minimal fwd edge</span><a name="l00367"></a>00367 <span class="keywordflow">while</span>(eit_p.first!=eit_p.second) {<a name="l00368"></a>00368 <span class="keywordflow">if</span>(new_code.cid(eit_p.first->first)!=-1) {<a name="l00369"></a>00369 <span class="comment">// this vertex is already part of minimal code (CHECK THIS ??)</span><a name="l00370"></a>00370 eit_p.first++;<a name="l00371"></a>00371 <span class="keywordflow">continue</span>;<a name="l00372"></a>00372 }<a name="l00373"></a>00373 <a name="l00374"></a>00374 <span class="keywordflow">if</span>(eit_p.first->second<=e) {<a name="l00375"></a>00375 <span class="comment">// minimal edge</span><a name="l00376"></a>00376 <span class="keyword">typename</span> PATTERN::VERTEX_T curr_lbl=cand_pat->label(eit_p.first->first);<a name="l00377"></a>00377 <span class="keywordflow">if</span>(eit_p.first->second<e) {<a name="l00378"></a>00378 <span class="comment">// new minimal edge found</span><a name="l00379"></a>00379 new_vids.clear();<a name="l00380"></a>00380 e=eit_p.first->second;<a name="l00381"></a>00381 dest_v=curr_lbl;<a name="l00382"></a>00382 }<a name="l00383"></a>00383 <a name="l00384"></a>00384 <span class="keywordflow">if</span>(curr_lbl<=dest_v) {<a name="l00385"></a>00385 <span class="comment">// minimal dest label</span><a name="l00386"></a>00386 <span class="keywordflow">if</span>(curr_lbl<dest_v) {<a name="l00387"></a>00387 new_vids.clear();<a name="l00388"></a>00388 dest_v=curr_lbl;<a name="l00389"></a>00389 }<a name="l00390"></a>00390 new_vids.push_back(eit_p.first->first);<a name="l00391"></a>00391 }<a name="l00392"></a>00392 }<a name="l00393"></a>00393 eit_p.first++;<a name="l00394"></a>00394 }<span class="comment">//end while eit_p.first..</span><a name="l00395"></a>00395 <a name="l00396"></a>00396 <span class="keywordflow">if</span>(!new_vids.empty()) {<a name="l00397"></a>00397 <span class="comment">// fwd extension found at this level</span><a name="l00398"></a>00398 fwd_found=<span class="keyword">true</span>;<a name="l00399"></a>00399 <span class="keywordflow">break</span>;<a name="l00400"></a>00400 }<a name="l00401"></a>00401 <a name="l00402"></a>00402 rmp_it--;<a name="l00403"></a>00403 rmp.pop_back();<a name="l00404"></a>00404 }<span class="comment">//end while !fwd_found..</span><a name="l00405"></a>00405 <a name="l00406"></a>00406 <span class="keywordflow">if</span>(!fwd_found || rmp_it<rmp.begin()) {<a name="l00407"></a>00407 <span class="comment">// no fwd edge extension could be found i.e. all fwd edges have been added</span><a name="l00408"></a>00408 <span class="comment">// so this code is minimal</span><a name="l00409"></a>00409 <span class="comment">//cout<<"Isomorphism decision at fwd-edge: all edges exhausted"<<endl;</span><a name="l00410"></a>00410 <span class="keywordflow">return</span> <span class="keyword">true</span>;<a name="l00411"></a>00411 }<a name="l00412"></a>00412 <a name="l00413"></a>00413 <span class="keyword">typename</span> CAN_CODE::FIVE_TUPLE new_tuple(*rmp_it, last_vid+1, cand_pat->label(new_code.gid(*rmp_it)), e, cand_pat->label(new_vids[0]));<a name="l00414"></a>00414 <span class="keywordflow">if</span>(new_tuple<current_code[code_index]) {<a name="l00415"></a>00415 <span class="comment">// new edge is more minimal</span><a name="l00416"></a>00416 <span class="preprocessor">#ifdef PRINT</span><a name="l00417"></a>00417 <span class="preprocessor"></span> cout<<<span class="stringliteral">"decision at fwd-edge: new_edge is more minimal"</span><<endl;<a name="l00418"></a>00418 cout<<<span class="stringliteral">"new_tuple: "</span><<new_tuple<<endl;<a name="l00419"></a>00419 cout<<<span class="stringliteral">"current_tuple: "</span><<current_code[code_index]<<endl;<a name="l00420"></a>00420 cout<<<span class="stringliteral">"current_code="</span><<current_code<<endl;<a name="l00421"></a>00421 <span class="preprocessor">#endif</span><a name="l00422"></a>00422 <span class="preprocessor"></span> <span class="keywordflow">return</span> <span class="keyword">false</span>;<a name="l00423"></a>00423 }<a name="l00424"></a>00424 <a name="l00425"></a>00425 <span class="keywordflow">if</span>(current_code[code_index]<new_tuple) {<a name="l00426"></a>00426 <span class="comment">// current tuple is more minimal</span><a name="l00427"></a>00427 <span class="preprocessor">#ifdef PRINT</span><a name="l00428"></a>00428 <span class="preprocessor"></span> cout<<<span class="stringliteral">"decision at fwd-edge: current tuple is more minimal"</span><<endl;<a name="l00429"></a>00429 cout<<<span class="stringliteral">"new_tuple: "</span><<new_tuple<<endl;<a name="l00430"></a>00430 cout<<<span class="stringliteral">"current_tuple: "</span><<current_code[code_index]<<endl;<a name="l00431"></a>00431 cout<<<span class="stringliteral">"current_code="</span><<current_code<<endl;<a name="l00432"></a>00432 <span class="preprocessor">#endif</span><a name="l00433"></a>00433 <span class="preprocessor"></span> <span class="keywordflow">return</span> <span class="keyword">true</span>;<a name="l00434"></a>00434 }<a name="l00435"></a>00435 <a name="l00436"></a>00436 <span class="comment">// check minimality against each new code</span><a name="l00437"></a>00437 <span class="keywordflow">for</span>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0; i<new_vids.size(); i++) {<a name="l00438"></a>00438 CAN_CODE next_code=new_code;<a name="l00439"></a>00439 next_code.append(new_tuple, new_code.gid(*rmp_it), new_vids[i]);<a name="l00440"></a>00440 next_code.append_rmp(last_vid+1);<a name="l00441"></a>00441 <span class="keywordflow">if</span>(!minimal(cand_pat, next_code))<a name="l00442"></a>00442 <span class="keywordflow">return</span> <span class="keyword">false</span>;<a name="l00443"></a>00443 }<a name="l00444"></a>00444 <a name="l00445"></a>00445 <span class="comment">// all codes were greater than cand_pat's code</span><a name="l00446"></a>00446 <span class="preprocessor">#ifdef PRINT</span><a name="l00447"></a>00447 <span class="preprocessor"></span> cout<<<span class="stringliteral">"decision at fwd-edge: this code more minimal than all codes"</span><<endl;<a name="l00448"></a>00448 <span class="preprocessor">#endif</span><a name="l00449"></a>00449 <span class="preprocessor"></span> <span class="keywordflow">return</span> <span class="keyword">true</span>;<a name="l00450"></a>00450 <a name="l00451"></a>00451 }<span class="comment">//end minimal()</span><a name="l00452"></a>00452 <a name="l00453"></a>00453 <span class="preprocessor">#endif</span></pre></div><hr size="1"><address style="align: right;"><small>Generated on Wed Jul 26 14:01:08 2006 for DMTL by <a href="http://www.doxygen.org/index.html"><img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.4.7 </small></address></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -