Talk:Strongly connected component

Computing Stub‑class

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing
Stub	This article has been rated as Stub-class on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's importance scale.
	This article has been automatically rated by a bot or other tool as Stub-class because it uses a stub template. Please ensure the assessment is correct before removing the `\|auto=` parameter.

Mathematics Start‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

There is also

There is also an algorithm called SCC that computes strongly connected components in graphs, by taking the inverse of a graph and working on the transpose G^t (V, E^-1) of G. Would it help if I put the pseudocode algorithm in here? Jontce 11:08, 17 May 2005 (UTC)[reply]
Isn't this a dictionary definition? At least, it should be linked to something else. m.e. 10:40, 28 May 2004 (UTC)[reply]

This page does not render correctly in IE7

Question about the algorithm

In step 1, DFS is called on a specific vertex v.

It needs to visit every vertex in the (weakly) connected component that v belongs to, to compute its finishing time.

In a directed graph, how can we choose the start node v for DFS in such a way as to visit every node in the weakly connected component of v and not add to the total complexity of the algorithm? This does not seem obvious to me. Thanks if you can explain this.

- Panayk (talk) 16:40, 18 January 2008 (UTC)[reply]

Nevermind. DSF is called on more than one starting vertices, taking care not to call it on (or revisit during a call) an already visited vertex. Perhaps we should mention that.

- Panayk (talk) 18:16, 18 January 2008 (UTC)[reply]

Algorithm

The algorithm section seems to be lifted word-for-word from CLR... —Preceding unsigned comment added by 67.114.158.146 (talk) 08:05, 9 April 2008 (UTC)[reply]

Is the image correct?

I see that C and H are not connected, is that correct? —Preceding unsigned comment added by 128.61.23.186 (talk) 19:36, 5 June 2008 (UTC)[reply]

yes, it is ok. They don't need to be directly connected by edges. --Fioravante Patrone en (talk) 20:08, 21 August 2008 (UTC)[reply]

I think he's right, since the definition is a PATH between two points. C can get to H and vice versa over a path. It's the fact that you can go both ways that makes that group strongly connected Delvarworld (talk) 08:22, 17 April 2011 (UTC)[reply]

Definition

The current definition (and the example) of a strongly connected component subtly avoids the delicate question whether a singleton node without selfloop is strongly connected or not.--94.221.120.119 (talk) 19:46, 22 January 2012 (UTC)[reply]

It does sort of avoid the question, but I think the only reasonable choice is to count a single node (without selfloop) as strongly connected to itself, by paths of lengths zero. For otherwise, it would not be true that strong connectivity is an equivalence relation and that the strongly connected components form a partition of any graph's vertices. —David Eppstein (talk) 22:30, 22 January 2012 (UTC)[reply]

Wrong definition of acyclic graphs

The article says that a graph is acyclic if and only if it has no strongly connected subgraphs with more than one vertex. However, a vertex with a selfloop fulfill this condition but is not acyclic. 141.3.44.192 (talk) 08:27, 13 September 2012 (UTC)[reply]

Interesting point. Does a node on its own count as 'strongly connected'? I think yes, as there is a path (of length zero) from each node to itself. Therefore, the only subgraph that is strongly connected, but acyclic, is a single vertex without a self-loop. Maybe it should be "a graph is acyclic if and only if it has no strongly connected subgraphs with at least one edge." Aaron McDaid (talk - contribs) 09:20, 13 September 2012 (UTC)[reply]

Different (graph) condesations?

There are some other possible notions of condensation, where the type of subgraph condensed isn't a strongly connected component. For example McCabe's algorithm for computing the essential complexity of a CFG (iteratively) condenses only the sub-graphs that have a single entry (source) and single exit point (sink), which are of course the structured programming control structures. Perhaps condensation isn't quite the proper term for that (it seems to also involve a sort of fixpoint iteration), but that's the term I found in a textbook (which has something like 3 editions, so it's probably not complete bunk) when I was looking for secondary sources for McCabe's paper: Paul C. Jorgensen (2002). Software Testing: A Craftsman's Approach, Second Edition (2nd ed.). CRC Press. p. 150. ISBN 978-0-8493-0809-3.

That book also defines a couple more condensation that like along 2-components, which is for condensing/finding DD-paths. (You can use the google books search function to find them inside.)

In modern compilers, the condensation (although called "reducibility" as McCabe called his stuff in original) is actually done on a different type of sub-graphs called natural loops, defined as "single-entry, multiple-exit loop, with only a single branch back to the entry from within it". (This done so it fits better with languages that have break statements etc. In fact languages like Modula-2 have been designed so they emit natural loops when compiled.) This is standard material in most compiler textbooks; it's in the Dragon Book etc.

I'm not sure if these are worth mentioning here of if Condensation (graph theory) should perhaps be the place. Isn't there some general pattern-matching type of condensation defined somewhere? The above clearly are particularizaitions of a similar template, just with the sub-graphs matched changed. Also, they're all pattern matching just on sub-graphs to condense, there's no other (programming language) notion involved at the CFG level. (Unlike flow charts, CFGs don't have node types or branch labels etc.) 188.27.81.64 (talk) 08:19, 17 July 2014 (UTC)[reply]