Issue 3020026: AU: Fix bug in impl of Johnson's circuit finding algorithm.

Keyboard Shortcuts

	File
u :	up to issue
j / k :	jump to file after / before current file
J / K :	jump to next file with a comment after / before current file
	Side-by-side diff
i :	toggle intra-line diffs
e :	expand all comments
c :	collapse all comments
s :	toggle showing all comments
n / p :	next / previous diff chunk or comment
N / P :	next / previous comment
<Up> / <Down> :	next / previous line

	Issue
u :	up to list of issues
j / k :	jump to patch after / before current patch
o / <Enter> :	open current patch in side-by-side view
i :	open current patch in unified diff view

	Issue List
j / k :	jump to issue after / before current issue
o / <Enter> :	open current issue

Issue 3020026: AU: Fix bug in impl of Johnson's circuit finding algorithm. (Closed)

Created:
10 years, 5 months ago by adlr

Modified:
9 years ago

Reviewers:
petkov

CC:
chromium-os-reviews_chromium.org

Base URL:
ssh://git@chromiumos-git/update_engine.git

Visibility:
Public.

Description

AU: Fix bug in impl of Johnson's circuit finding algorithm. The original paper at http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf is correct in the algorithm description. I made a mistake when translating it from pseudo code to C++. This CL corrects that mistake. BUG=chromium-os:5043 TEST=unittest, tested building and applying an update that exposed this issue

Patch Set 1 #

Created: 10 years, 5 months ago

Download [raw] [tar.bz2]

		Unified diffs	Side-by-side diffs	Delta from patch set	Stats (+32 lines, -1 line)			Patch
	M	cycle_breaker.cc	View		1 chunk	+5 lines, -1 line	0 comments	Download
	M	cycle_breaker_unittest.cc	View		1 chunk	+27 lines, -0 lines	0 comments	Download

Messages

Total messages: 2 (0 generated)

Expand Messages | Collapse Messages

petkov

10 years, 5 months ago (2010-07-23 06:18:46 UTC) #2

I haven't followed the development so it's difficult to jump in. I'll try to
read the paper in my spare time :-)

AFAICT, LGTM. It seems that if the code was broken to start with, this change is
not going to make it any worse.

Expand Messages | Collapse Messages