Issue 657055: AU: Tarjan's algorithm.

Issue 657055: AU: Tarjan's algorithm. (Closed)

Created:
10 years, 10 months ago by adlr

Modified:
9 years ago

Reviewers:
Daniel Erat

CC:
chromium-os-reviews_googlegroups.com

Visibility:
Public.

Description

AU: Tarjan's algorithm. Add an implementation of Tarjan's algorith for finding Strongly Connected Components in a graph. This version is slightly modified: it takes in a vertex in addition to the graph and returns only the SCC containing that vertex.

Patch Set 1 #

Total comments: 6

Patch Set 2 : fixes for review #

Created: 10 years, 9 months ago

Download [raw] [tar.bz2]

	Unified diffs	Side-by-side diffs	Delta from patch set	Stats (+192 lines, -0 lines)			Patch
M	src/platform/update_engine/SConstruct	View		2 chunks	+2 lines, -0 lines	0 comments	Download
A	src/platform/update_engine/tarjan.h	View	1	1 chunk	+39 lines, -0 lines	0 comments	Download
A	src/platform/update_engine/tarjan.cc	View	1	1 chunk	+70 lines, -0 lines	0 comments	Download
A	src/platform/update_engine/tarjan_unittest.cc	View	1	1 chunk	+80 lines, -0 lines	0 comments	Download
M	src/platform/update_engine/utils.h	View		1 chunk	+1 line, -0 lines	0 comments	Download

Messages

Total messages: 3 (0 generated)

Expand Messages | Collapse Messages

Daniel Erat

LGTM http://codereview.chromium.org/657055/diff/1/3 File src/platform/update_engine/tarjan.cc (right): http://codereview.chromium.org/657055/diff/1/3#newcode20 src/platform/update_engine/tarjan.cc:20: vector<Vertex::Index> TarjanAlgorithm::Execute(Vertex::Index vertex, Graph* graph) { wrap long ...

10 years, 10 months ago (2010-02-24 04:10:59 UTC) #2

adlr

10 years, 9 months ago (2010-03-09 23:56:33 UTC) #3

fixed and submitted. thanks!

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

http://codereview.chromium.org/657055/diff/1/3#newcode20
src/platform/update_engine/tarjan.cc:20: vector<Vertex::Index>
TarjanAlgorithm::Execute(Vertex::Index vertex, Graph* graph) {
On 2010/02/24 04:10:59, Daniel Erat wrote:
> wrap long line

Done.

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

http://codereview.chromium.org/657055/diff/1/4#newcode11
src/platform/update_engine/tarjan.h:11: // Note: a true Tarjan algorithm would
find all stronly connected components
On 2010/02/24 04:10:59, Daniel Erat wrote:
> sp: strongly

Done.

http://codereview.chromium.org/657055/diff/1/4#newcode24
src/platform/update_engine/tarjan.h:24: std::vector<Vertex::Index>
Execute(Vertex::Index vertex, Graph* graph);
On 2010/02/24 04:10:59, Daniel Erat wrote:
> pass a pointer to the out vector in instead so you can avoid a potential copy?

Done.

Expand Messages | Collapse Messages