Path-based strong component algorithm: Difference between revisions

Revision as of 17:41, 10 June 2010

Latest revision as of 19:57, 12 October 2024

(27 intermediate revisions by 17 users not shown)

Line 1:

{{Short description|Graph algorithm}}

In [[graph theory]], the '''Cheriyan–Mehlhorn/Gabow algorithm''' is a [[linear-time]] method for finding the [[Strongly connected component|strong components]] of a [[Directed graph|digraph]]. It was discovered in 1996 by Joseph Cheriyan and [[Kurt Mehlhorn]]

In [[graph theory]], the [[strongly connected component]]s of a [[directed graph]] may be found using an algorithm that uses [[depth-first search]] in combination with two [[stack (data structure)|stacks]], one to keep track of the vertices in the current component and the second to keep track of the current search path.<ref>{{harvtxt|Sedgewick|2004}}.</ref> Versions of this algorithm have been proposed by {{harvtxt|Purdom|1970}}, {{harvtxt|Munro|1971}}, {{harvtxt|Dijkstra|1976}}, {{harvtxt|Cheriyan|Mehlhorn|1996}}, and {{harvtxt|Gabow|2000}}; of these, Dijkstra's version was the first to achieve [[linear time]].<ref>[http://www.cs.colorado.edu/~hal/Papers/DFS/pbDFShistory.html History of Path-based DFS for Strong Components], Harold N. Gabow, accessed 2012-04-24.</ref>

<ref>{{cite journal|

last1=Cheriyan|first1= J.|

last2=Mehlhorn|first2=K.|author2-link=Kurt Mehlhorn

title=Algorithms for dense graphs and networks on the random access computer|

journal=[[Algorithmica]]|

volume=15|

pages=521–549|

year=1996

}}</ref>

and rediscovered in 1999 by [[Harold N. Gabow]]

<ref>{{Cite book

| last = Sedgewick | first = R.

| title = [[Algorithms in C]], 3rd Ed., Part 5 - Graph Algorithms

| ___location = Cambridge MA

| publisher = Addison-Wesley

| year= 2002

}}</ref>

and is a variation on [[Tarjan's strongly connected components algorithm|Tarjan's algorithm]]. The algorithm uses a second [[stack]] to decide when to remove [[Vertex (graph theory)|vertices]] in the same strong component from the main [[Stack (data structure)|stack]], instead of a vertex-indexed [[array]] of [[Depth-first search|preorder numbers]].

==Description==

The algorithm is easily derived from the "path-based view"

The algorithm performs a depth-first search of the given graph ''G'', maintaining as it does two stacks ''S'' and ''P'' (in addition to the normal call stack for a recursive function).

of [[depth-first search]]. This contrasts with the more widely known "tree-based view"

Stack ''S'' contains all the vertices that have not yet been assigned to a strongly connected component, in the order in which the depth-first search reaches the vertices.

<ref>{{Introduction to Algorithms}}</ref>.

Stack ''P'' contains vertices that have not yet been determined to belong to different strongly connected components from each other. It also uses a counter ''C'' of the number of vertices reached so far, which it uses to compute the preorder numbers of the vertices.

The ''path-based view''

conceptualizes a depth-first search as constructing

a sequence of paths

<ref>{{cite journal|

last=Gabow|first=H.N.|

title=Path-based depth-first search for strong and biconnected components|

journal=[[Information Processing Letters]]|

volume=74|

pages=107–114|

year=2000

}}</ref>.

The ''tree-based view''

conceptualizes the search as

constructing a depth-first spanning tree.

The path-based view is simpler and can be used to derive

most basic depth-first search algorithms (e.g., topological ordering,

strong and biconnected components)

<ref>{{citation

| last = Gabow

| first = H.N.

| contribution = Searching (Ch 10.1)

| editor-last1 = Gross

| editor-first1 = J.L.

| editor-last2 = Yellen

| editor-first2 = J.

| title = Discrete Math. and its Applications: Handbook of Graph Theory

| volume = 25

| pages = 953–984

| publisher = CRC Press

| place = Boca Raton, FL

| year = 2003

}}</ref>.

The tree-based view is more powerful and provides the framework

for more advanced graph algorithms (e.g., planarity testing, triconnected

components).

When the depth-first search reaches a vertex ''v'', the algorithm performs the following steps:

#Set the preorder number of ''v'' to ''C'', and increment ''C''.

#Push ''v'' onto ''S'' and also onto ''P''.

#For each edge from ''v'' to a neighboring vertex ''w'':

#* If the preorder number of ''w'' has not yet been assigned (the edge is a [[Depth-first search#Output of a depth-first search|tree edge]]), recursively search ''w'';

#*Otherwise, if ''w'' has not yet been assigned to a strongly connected component (the edge is a forward/back/cross edge):

#**Repeatedly pop vertices from ''P'' until the top element of ''P'' has a preorder number less than or equal to the preorder number of ''w''.

#If ''v'' is the top element of ''P'':

#*Pop vertices from ''S'' until ''v'' has been popped, and assign the popped vertices to a new component.

#*Pop ''v'' from ''P''.

The overall algorithm consists of a loop through the vertices of the graph, calling this recursive search on each vertex that does not yet have a preorder number assigned to it.

== References ==

<references/>

==Related algorithms==

Like this algorithm, [[Tarjan's strongly connected components algorithm]] also uses depth first search together with a stack to keep track of vertices that have not yet been assigned to a component, and moves these vertices into a new component when it finishes expanding the final vertex of its component. However, in place of the stack ''P'', Tarjan's algorithm uses a vertex-indexed [[array (data type)|array]] of preorder numbers, assigned in the order that vertices are first visited in the [[depth-first search]]. The preorder array is used to keep track of when to form a new component.

==Notes==

{{reflist}}

==References==

*{{citation

| last1 = Cheriyan | first1 = J.

| last2 = Mehlhorn | first2 = K. | author2-link = Kurt Mehlhorn

| doi = 10.1007/BF01940880

| journal = [[Algorithmica]]

| pages = 521–549

| title = Algorithms for dense graphs and networks on the random access computer

| volume = 15

| year = 1996| issue = 6

| s2cid = 8930091

}}.

*{{citation

| last = Dijkstra | first = Edsger | author-link = Edsger Dijkstra

| ___location = NJ

| at = Ch.&nbsp;25

| publisher = Prentice Hall

| title = A Discipline of Programming

| year = 1976}}.

*{{citation

| last = Gabow | first = Harold N. | author-link = Harold N. Gabow

| doi = 10.1016/S0020-0190(00)00051-X

| issue = 3–4

| journal = Information Processing Letters

| mr = 1761551

| pages = 107–114

| title = Path-based depth-first search for strong and biconnected components

| volume = 74

| year = 2000

| url = https://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/path%20based...pdf}}.

*{{citation

| last = Munro | first = Ian | author-link = Ian Munro (computer scientist)

| journal = Information Processing Letters

| pages = 56–58

| title = Efficient determination of the transitive closure of a directed graph

| volume = 1

| year = 1971

| issue = 2

| doi=10.1016/0020-0190(71)90006-8}}.

*{{citation

| last = Purdom | first = P. Jr.

| journal = BIT

| pages = 76–94

| title = A transitive closure algorithm

| volume = 10

| year = 1970

| doi=10.1007/bf01940892| s2cid = 20818200

| url = http://digital.library.wisc.edu/1793/57514

}}.

*{{citation

| last = Sedgewick | first = R.

| contribution = 19.8 Strong Components in Digraphs

| edition = 3rd

| ___location = Cambridge MA

| pages = 205–216

| publisher = Addison-Wesley

| title = Algorithms in Java, Part 5 – Graph Algorithms

| year = 2004}}.

[[Category:Graph algorithms]]