AU: Cycle Breaker for directed graphs.

AU: Cycle Breaker for directed graphs.

A new class CycleBreaker that uses Johnson's elementary circuit
finding algorithm to find cycles in a directed graph. This class goes
beyond Johnson's algorithm to also break them using a simple greedy
algorithm.

Like Johnson's elementary circuit finding algorithm, this is not
intended to find cycles that contain only one node (i.e., a node that
points to itself).

[Daniel Erat, 2010-03-10 01:15:44]

I'll try to find some time soon to read/understand the algorithm so I can
double-check the code.

http://codereview.chromium.org/784001/diff/1/3
File src/platform/update_engine/cycle_breaker.cc (right):

http://codereview.chromium.org/784001/diff/1/3#newcode19
src/platform/update_engine/cycle_breaker.cc:19: // Make a copy, which we will
modify by removing edges. Thus, each
should this be "in each" instead?

http://codereview.chromium.org/784001/diff/1/3#newcode27
src/platform/update_engine/cycle_breaker.cc:27: // We arbitrarily order each
vertex by it's index in the graph. Thus,
s/it's/its/

http://codereview.chromium.org/784001/diff/1/3#newcode75
src/platform/update_engine/cycle_breaker.cc:75: it != (--stack_.end()); ++it) {
does (stack_.end() - 1) work instead of (--stack_.end()) here?  seems a bit
cleaner

http://codereview.chromium.org/784001/diff/1/4
File src/platform/update_engine/cycle_breaker.h (right):

http://codereview.chromium.org/784001/diff/1/4#newcode31
src/platform/update_engine/cycle_breaker.h:31: void BreakCycles(const Graph&
graph);
this pattern (a method that stores its output inside of the object, presumably
just to replace it the next time it's called) seems a bit weird to me.  would it
be easy to change things so that the output (just 'cut_edges_', i think) is
returned as an out-param of BreakCycles(), and the CycleBreaker object doesn't
hold any state other than while BreakCycles() is running?

[adlr, 2010-03-10 19:06:05]

ready for another look, thanks.

http://codereview.chromium.org/784001/diff/1/3
File src/platform/update_engine/cycle_breaker.cc (right):

http://codereview.chromium.org/784001/diff/1/3#newcode19
src/platform/update_engine/cycle_breaker.cc:19: // Make a copy, which we will
modify by removing edges. Thus, each
On 2010/03/10 01:15:44, Daniel Erat wrote:
> should this be "in each" instead?

yeah, done

http://codereview.chromium.org/784001/diff/1/3#newcode27
src/platform/update_engine/cycle_breaker.cc:27: // We arbitrarily order each
vertex by it's index in the graph. Thus,
On 2010/03/10 01:15:44, Daniel Erat wrote:
> s/it's/its/

Done.

http://codereview.chromium.org/784001/diff/1/3#newcode75
src/platform/update_engine/cycle_breaker.cc:75: it != (--stack_.end()); ++it) {
On 2010/03/10 01:15:44, Daniel Erat wrote:
> does (stack_.end() - 1) work instead of (--stack_.end()) here?  seems a bit
> cleaner

Done.

http://codereview.chromium.org/784001/diff/1/4
File src/platform/update_engine/cycle_breaker.h (right):

http://codereview.chromium.org/784001/diff/1/4#newcode31
src/platform/update_engine/cycle_breaker.h:31: void BreakCycles(const Graph&
graph);
On 2010/03/10 01:15:44, Daniel Erat wrote:
> this pattern (a method that stores its output inside of the object, presumably
> just to replace it the next time it's called) seems a bit weird to me.  would
it
> be easy to change things so that the output (just 'cut_edges_', i think) is
> returned as an out-param of BreakCycles(), and the CycleBreaker object doesn't
> hold any state other than while BreakCycles() is running?

Done.

[Daniel Erat, 2010-03-10 22:50:01]

LGTM

You were right about that paper -- I gave up on interpreting the pseudocode. :-(

http://codereview.chromium.org/784001/diff/6001/7002
File src/platform/update_engine/cycle_breaker.cc (right):

http://codereview.chromium.org/784001/diff/6001/7002#newcode71
src/platform/update_engine/cycle_breaker.cc:71: out_cut_edges->swap(cut_edges_);
nit: DCHECK(stack_.empty()) here?

http://codereview.chromium.org/784001/diff/6001/7003
File src/platform/update_engine/cycle_breaker.h (right):

http://codereview.chromium.org/784001/diff/6001/7003#newcode8
src/platform/update_engine/cycle_breaker.h:8: // This is a modified
implemenation of Donald B. Johnson's algorithm for
s/implemenation/implementation/

http://codereview.chromium.org/784001/diff/6001/7004
File src/platform/update_engine/cycle_breaker_unittest.cc (right):

http://codereview.chromium.org/784001/diff/6001/7004#newcode69
src/platform/update_engine/cycle_breaker_unittest.cc:69:
utils::SetContainsKey(broken_edges, make_pair(n_h, n_g)));
also check that there are exactly three edges in the set?

[adlr, 2010-03-11 00:41:42]

fixed and submitted. thanks!

http://codereview.chromium.org/784001/diff/6001/7002
File src/platform/update_engine/cycle_breaker.cc (right):

http://codereview.chromium.org/784001/diff/6001/7002#newcode71
src/platform/update_engine/cycle_breaker.cc:71: out_cut_edges->swap(cut_edges_);
On 2010/03/10 22:50:01, Daniel Erat wrote:
> nit: DCHECK(stack_.empty()) here?

Done.

http://codereview.chromium.org/784001/diff/6001/7003
File src/platform/update_engine/cycle_breaker.h (right):

http://codereview.chromium.org/784001/diff/6001/7003#newcode8
src/platform/update_engine/cycle_breaker.h:8: // This is a modified
implemenation of Donald B. Johnson's algorithm for
On 2010/03/10 22:50:01, Daniel Erat wrote:
> s/implemenation/implementation/

Done.

http://codereview.chromium.org/784001/diff/6001/7004
File src/platform/update_engine/cycle_breaker_unittest.cc (right):

http://codereview.chromium.org/784001/diff/6001/7004#newcode69
src/platform/update_engine/cycle_breaker_unittest.cc:69:
utils::SetContainsKey(broken_edges, make_pair(n_h, n_g)));
On 2010/03/10 22:50:01, Daniel Erat wrote:
> also check that there are exactly three edges in the set?

Done.