<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 25, 2017 at 6:17 PM, Hongbin Zheng <span dir="ltr"><<a href="mailto:etherzhhb@gmail.com" target="_blank">etherzhhb@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi Daniel,<div><br></div><div>I mean "*<span style="font-size:12.8px">As a set*, B + C dominate D</span>".</div><div class="gmail_extra"><br><div class="gmail_quote"><span class="">On Tue, Apr 25, 2017 at 5:42 PM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">When you say collectively, you mean "would dominate it if considered a single block together?<div><br></div><div>IE</div><div><br></div><div>   A</div><div>/      \</div><div>B    C</div><div>  \  /</div><div>   D</div><div><br></div><div>As a set, B + C dominate D.</div><div><br></div><div>The set you are looking for there is (i believe):</div><div><br></div><div>For each predecessor, walk the idom tree until you hit NCA of all predecessors.</div></div></blockquote></span><div>What do you mean by NCA?</div></div></div></div></blockquote><div><br></div><div>Nearest common ancestor</div><div><br></div><div>If you have dfs numbers for the dom tree, you can do this very fast.</div><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span class=""><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>While you walk it, place all nodes on each branch in a set.</div><div><br></div><div>Any set that collectively dominates D must contain at least one member from each of these set, or be on the idom path between NCA and root.</div><div><br></div><div>IE above, it would be that </div><div>Set 1 = {B}</div><div>Set 2 = {C}</div><div>Set IDOM to root = {A}.</div><div><br></div><div>If you find something in "set IDOM to root", the answer is always "yes", since that block alone dominates it, the collective set must dominate it.</div><div>(unless you use a stricter definition of collective)</div><div><br></div><div>For the tree</div><div>  A</div><div> /   \</div><div>B   D</div><div>|     |</div><div>C   E</div><div> \   /</div><div>   F</div><div><br></div><div>Set 1 = {B, C}</div><div>Set 2 = {D, E}</div><div>set IDOM to root = {A}<br><br></div></div></blockquote><div><br></div></span><div>Thanks a lot</div><span class="HOEnZb"><font color="#888888"><div>Hongbin</div></font></span></div></div></div>
</blockquote></div><br></div></div>