📄 graph__iso__check_8h-source.html
字号:
<a name="l00150"></a>00150 <a name="l00151"></a>00151 <span class="comment">// create separate codes for each pair in ids</span><a name="l00152"></a>00152 <span class="comment">// each such pair shall have to be tested for isomorphism</span><a name="l00153"></a>00153 <a name="l00154"></a>00154 tt_rest.<a class="code" href="classtime__tracker.html#cbe4e1e72cf61ff3f4c135e161fc5a50">start</a>();<a name="l00155"></a>00155 <span class="keywordflow">for</span>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0; i<ids.size(); i++) {<a name="l00156"></a>00156 CAN_CODE new_cc(<span class="keyword">typename</span> CAN_CODE::FIVE_TUPLE(0, 1, cand_pat->label(ids[i].first), e, cand_pat->label(ids[i].second)), ids[i].first, ids[i].second);<a name="l00157"></a>00157 new_cc.init_rmp();<a name="l00158"></a>00158 new_codes.push_back(new_cc);<a name="l00159"></a>00159 }<a name="l00160"></a>00160 <a name="l00161"></a>00161 <span class="comment">// codes in new_codes are all equivalent</span><a name="l00162"></a>00162 <span class="comment">// check if any one is < current one</span><a name="l00163"></a>00163 <a name="l00164"></a>00164 <a name="l00165"></a>00165 <span class="keywordflow">if</span>(new_codes[0][0]<cand_pat->_canonical_code[0]) {<a name="l00166"></a>00166 <span class="preprocessor">#ifdef PRINT</span><a name="l00167"></a>00167 <span class="preprocessor"></span> cout<<<span class="stringliteral">"Isomorphism decision made at first level: new_tuple="</span><<new_codes[0][0]<<endl;<a name="l00168"></a>00168 cout<<<span class="stringliteral">"current_code="</span><<cand_pat->_canonical_code[0]<<endl;<a name="l00169"></a>00169 <span class="preprocessor">#endif</span><a name="l00170"></a>00170 <span class="preprocessor"></span> cand_pat->_is_canonical=<span class="keyword">false</span>;<a name="l00171"></a>00171 tt_iso_chk.<a class="code" href="classtime__tracker.html#a6790d26a9c1c83569711a7634413856">stop</a>();<a name="l00172"></a>00172 <span class="keywordflow">return</span> <span class="keyword">false</span>;<a name="l00173"></a>00173 }<a name="l00174"></a>00174 tt_rest.<a class="code" href="classtime__tracker.html#a6790d26a9c1c83569711a7634413856">stop</a>();<a name="l00175"></a>00175 <a name="l00176"></a>00176 <span class="keywordflow">for</span>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0; i<new_codes.size(); i++) {<a name="l00177"></a>00177 tt_minimal.<a class="code" href="classtime__tracker.html#cbe4e1e72cf61ff3f4c135e161fc5a50">start</a>();<a name="l00178"></a>00178 <span class="keywordtype">bool</span> r = minimal(cand_pat, new_codes[i]);<a name="l00179"></a>00179 <span class="keywordflow">if</span>(!r) {<a name="l00180"></a>00180 cand_pat->_is_canonical=<span class="keyword">false</span>;<a name="l00181"></a>00181 tt_iso_chk.<a class="code" href="classtime__tracker.html#a6790d26a9c1c83569711a7634413856">stop</a>();<a name="l00182"></a>00182 <span class="keywordflow">return</span> <span class="keyword">false</span>;<a name="l00183"></a>00183 }<a name="l00184"></a>00184 tt_minimal.<a class="code" href="classtime__tracker.html#a6790d26a9c1c83569711a7634413856">stop</a>();<a name="l00185"></a>00185 }<a name="l00186"></a>00186 <a name="l00187"></a>00187 <span class="comment">// execution reaches here iff all codes were found to be >= current one</span><a name="l00188"></a>00188 cand_pat->_is_canonical=<span class="keyword">true</span>;<a name="l00189"></a>00189 tt_iso_chk.<a class="code" href="classtime__tracker.html#a6790d26a9c1c83569711a7634413856">stop</a>();<a name="l00190"></a>00190 <span class="keywordflow">return</span> <span class="keyword">true</span>;<a name="l00191"></a>00191 <a name="l00192"></a>00192 }<span class="comment">//end check_isomorphism()</span><a name="l00193"></a>00193 <a name="l00194"></a>00194 <a name="l00195"></a>00195 <span class="comment">// find minimal pair, acc to DFS ordering</span><a name="l00196"></a>00196 <span class="keyword">template</span><<span class="keyword">typename</span> PATTERN><a name="l00197"></a>00197 <span class="keywordtype">void</span> iso_startup(<span class="keyword">const</span> PATTERN* cand_pat, <span class="keyword">typename</span> PATTERN::VERTEX_T& src_v, <span class="keyword">typename</span> PATTERN::VERTEX_T& dest_v, <span class="keyword">typename</span> PATTERN::EDGE_T& e, vector<pair<int, int> >& ids) { <a name="l00198"></a>00198 num_startup++; <a name="l00199"></a>00199 tt_iso_startup.<a class="code" href="classtime__tracker.html#cbe4e1e72cf61ff3f4c135e161fc5a50">start</a>();<a name="l00200"></a>00200 <span class="comment">// find minimal pair, acc to DFS ordering</span><a name="l00201"></a>00201 <span class="keyword">typename</span> PATTERN::CONST_IT it;<a name="l00202"></a>00202 <span class="keyword">typename</span> PATTERN::CONST_EIT_PAIR eit_p;<a name="l00203"></a>00203 <span class="keywordflow">for</span>(it=cand_pat->begin(); it!=cand_pat->end(); it++) {<a name="l00204"></a>00204 <span class="keywordflow">if</span>(it->v>src_v)<a name="l00205"></a>00205 <span class="keywordflow">continue</span>;<a name="l00206"></a>00206 <a name="l00207"></a>00207 eit_p=cand_pat->out_edges(it->id);<a name="l00208"></a>00208 <a name="l00209"></a>00209 <span class="keywordflow">if</span>(it->v<src_v) {<a name="l00210"></a>00210 <span class="comment">// new minimal src label found </span><a name="l00211"></a>00211 <span class="comment">// find edge with least label </span><a name="l00212"></a>00212 ids.clear();<a name="l00213"></a>00213 e=eit_p.first->second;<a name="l00214"></a>00214 src_v=it->v;<a name="l00215"></a>00215 dest_v=cand_pat->label(eit_p.first->first);<a name="l00216"></a>00216 ids.push_back(make_pair(it->id, eit_p.first->first));<a name="l00217"></a>00217 eit_p.first++;<a name="l00218"></a>00218 }<a name="l00219"></a>00219 <a name="l00220"></a>00220 <span class="keywordflow">while</span>(eit_p.first!=eit_p.second) {<a name="l00221"></a>00221 <span class="keywordflow">if</span>(eit_p.first->second<=e) {<a name="l00222"></a>00222 <span class="keywordflow">if</span>(eit_p.first->second<e) {<a name="l00223"></a>00223 <span class="comment">// new minimal edge found</span><a name="l00224"></a>00224 ids.clear();<a name="l00225"></a>00225 e=eit_p.first->second;<a name="l00226"></a>00226 dest_v=cand_pat->label(eit_p.first->first);<a name="l00227"></a>00227 ids.push_back(make_pair(it->id, eit_p.first->first));<a name="l00228"></a>00228 eit_p.first++;<a name="l00229"></a>00229 <span class="keywordflow">continue</span>;<a name="l00230"></a>00230 }<a name="l00231"></a>00231 <a name="l00232"></a>00232 <span class="keywordflow">if</span>(cand_pat->label(eit_p.first->first)<=dest_v) {<a name="l00233"></a>00233 <span class="keywordflow">if</span>(cand_pat->label(eit_p.first->first)<dest_v) {<a name="l00234"></a>00234 <span class="comment">// new least dest label found</span><a name="l00235"></a>00235 ids.clear();<a name="l00236"></a>00236 dest_v=cand_pat->label(eit_p.first->first);<a name="l00237"></a>00237 }<a name="l00238"></a>00238 ids.push_back(make_pair(it->id, eit_p.first->first));<a name="l00239"></a>00239 }<a name="l00240"></a>00240 }<span class="comment">//end if eit_p.first->second<=e</span><a name="l00241"></a>00241 eit_p.first++;<a name="l00242"></a>00242 } <a name="l00243"></a>00243 }<span class="comment">//end for</span><a name="l00244"></a>00244 <a name="l00245"></a>00245 tt_iso_startup.<a class="code" href="classtime__tracker.html#a6790d26a9c1c83569711a7634413856">stop</a>();<a name="l00246"></a>00246 <a name="l00247"></a>00247 }<span class="comment">//end iso_startup()</span><a name="l00248"></a>00248 <a name="l00249"></a>00249 <a name="l00252"></a>00252 <span class="keyword">template</span><<span class="keyword">typename</span> PATTERN, <span class="keyword">typename</span> CAN_CODE><a name="l00253"></a>00253 <span class="keywordtype">bool</span> minimal(<span class="keyword">const</span> PATTERN* cand_pat, CAN_CODE& new_code) {<a name="l00254"></a>00254 <a name="l00255"></a>00255 <a class="code" href="classelement__parser.html">element_parser<typename PATTERN::EDGE_T></a> ed_prsr;<a name="l00256"></a>00256 <a class="code" href="classelement__parser.html">element_parser<typename PATTERN::VERTEX_T></a> vt_prsr;<a name="l00257"></a>00257 <a name="l00258"></a>00258 <span class="comment">// starts by checking if a back-edge can be added</span><a name="l00259"></a>00259 <span class="comment">// else, the minimal fwd edge is added and minimality checked again</span><a name="l00260"></a>00260 <a name="l00262"></a>00262 <span class="comment">// if all edges have been added to new_code, then no new edges can be added</span><a name="l00263"></a>00263 <span class="comment">// hence cand_pat is minimal</span><a name="l00264"></a>00264 <span class="keywordflow">if</span>(cand_pat->canonical_code().size()==new_code.size())<a name="l00265"></a>00265 <span class="keywordflow">return</span> <span class="keyword">true</span>;<a name="l00266"></a>00266 <a name="l00267"></a>00267 <span class="keyword">const</span> CAN_CODE& current_code=cand_pat->canonical_code();<a name="l00268"></a>00268 <span class="keyword">typename</span> CAN_CODE::CONST_IT cc_it=new_code.end()-1;<a name="l00269"></a>00269 <span class="keywordtype">bool</span> is_last_fwd=(cc_it->_i<cc_it->_j); <span class="comment">// denotes if last edge in new_code was a fwd edge</span><a name="l00270"></a>00270 <span class="keywordtype">int</span> last_vid=(is_last_fwd)? cc_it->_j: cc_it->_i; <span class="comment">// vid to which edge shall be added </span><a name="l00271"></a>00271 <span class="keywordtype">int</span> last_vid_g=new_code.gid(last_vid);<a name="l00272"></a>00272 <span class="keyword">typename</span> PATTERN::CONST_EIT_PAIR eit_p=cand_pat->out_edges(last_vid_g);<a name="l00273"></a>00273 <span class="keywordtype">int</span> code_index=new_code.size();<a name="l00274"></a>00274 <span class="keyword">typename</span> CAN_CODE::RMP_T& rmp=new_code.rmost_path();<a name="l00275"></a>00275 <span class="keyword">typename</span> CAN_CODE::RMP_T::iterator rmp_it;<a name="l00276"></a>00276 <a name="l00278"></a>00278 <span class="keywordtype">int</span> back_vid, last_back_vid;<a name="l00279"></a>00279 back_vid=last_vid;<a name="l00280"></a>00280 <span class="keyword">typename</span> PATTERN::EDGE_T e=<span class="keyword">typename</span> PATTERN::EDGE_T();<a name="l00281"></a>00281 <a name="l00282"></a>00282 <span class="keywordflow">if</span>(is_last_fwd)<a name="l00283"></a>00283 <span class="comment">// relatively straight forward - add the farthest back edge you find</span><a name="l00284"></a>00284 last_back_vid=-1;<a name="l00285"></a>00285 <span class="keywordflow">else</span><a name="l00286"></a>00286 <span class="comment">// add a back edge only if it's after the last back edge present</span><a name="l00287"></a>00287 last_back_vid=cc_it->_j;<a name="l00288"></a>00288 <a name="l00289"></a>00289 <span class="keywordflow">while</span>(eit_p.first!=eit_p.second) {<a name="l00290"></a>00290 rmp_it=rmp.end()-3;<a name="l00291"></a>00291 <a name="l00292"></a>00292 <span class="comment">// check if this vid occurs on the rmp of can code</span><a name="l00293"></a>00293 <span class="keywordflow">while</span>(rmp_it>=rmp.begin()) {<a name="l00294"></a>00294 <span class="keywordflow">if</span>(*rmp_it==new_code.cid(eit_p.first->first))<a name="l00295"></a>00295 <span class="keywordflow">break</span>;<a name="l00296"></a>00296 <a name="l00297"></a>00297 <span class="keywordflow">if</span>(*rmp_it<new_code.cid(eit_p.first->first))<a name="l00298"></a>00298 rmp_it=rmp.begin();<a name="l00299"></a>00299 <a name="l00300"></a>00300 rmp_it--;<a name="l00301"></a>00301 }<a name="l00302"></a>00302 <a name="l00303"></a>00303 <span class="keywordflow">if</span>(rmp_it<rmp.begin()) {<a name="l00304"></a>00304 eit_p.first++;<a name="l00305"></a>00305 <span class="keywordflow">continue</span>;<a name="l00306"></a>00306 }⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -