AU: delta generation: cut cycles in graph more aggressively

AU: delta generation: cut cycles in graph more aggressively

I found that with some deltas I was generating, finding and cutting
all cycles in the graph was taking way too long (hours). This CL
increases the agressiveness used to cut edges and presents a test case
that performs particularly poorly without this optimization.

BUG=chromium-os:5060
TEST=attached unittest, tested generating/applying delta w/ images that
needed this optimization

[petkov, 2010-07-23 06:32:23]

Same general comment about following development as the other CL.

LGTM

http://codereview.chromium.org/3015023/diff/1/2
File cycle_breaker.cc (right):

http://codereview.chromium.org/3015023/diff/1/2#newcode143
cycle_breaker.cc:143: if (StackContainsCutEdge())
this seems to introduce n^2 kind of complexity... I assume sizes are OK to not
be a problem (or, maybe, there's a bigger problem already anyway).

[adlr, 2010-07-26 20:49:38]

On Thu, Jul 22, 2010 at 11:32 PM, <petkov@chromium.org> wrote:

> Same general comment about following development as the other CL.
>
> LGTM
>
>
>
> http://codereview.chromium.org/3015023/diff/1/2
> File cycle_breaker.cc (right):
>
> http://codereview.chromium.org/3015023/diff/1/2#newcode143
> cycle_breaker.cc:143: if (StackContainsCutEdge())
> this seems to introduce n^2 kind of complexity... I assume sizes are OK
> to not be a problem (or, maybe, there's a bigger problem already
> anyway).


This is something that could be looked at for future optimization, but in
general this CL fixes a much bigger need for optimization.

I'm going to push this for now, we can revisit this later if it's an issue.

-andrew


>
>
> http://codereview.chromium.org/3015023/show
>