reset password
Author Message
mnava18
Posts: 86
Posted 21:47 Nov 05, 2014 |

im a little confused about these 2. i understand them and how they work. but the topological ordering with dfs that we learned on tuesday , is different from the Kosaraju algo were using thursday right?  or does Kosaraju use topological sorting? i was thinking that the first dfs pass of Kosaraju uses topological sorting and then the 2nd dfs pass finds the scc's of the graph.

Last edited by mnava18 at 21:48 Nov 05, 2014.
Izuniga3
Posts: 4
Posted 21:52 Nov 05, 2014 |
The topo ordering that we did on tuesday is the same as the one we are going to do for thursday. Its just that you do one pass going to the head of the array and the next pass you take into account the first ordering and then go in reverse. Hopefully that made sense if it didn't I could explain more lol.
rabbott
Posts: 1649
Posted 22:00 Nov 05, 2014 |

Topological sorting and Kosaraju's algorithm operate on different sorts of graphs. Topological sorting works only on DAGs. Strongly connected components don't exist in DAGs. To have a strongly connected component you need loops in the graph, which violates the DAG condition. It's best to think of the two algorithms as different. 

On the other hand, once one runs Kosaraju's algorithm, if one thinks of each SCC as a node in what Roughgarden called a meta-graph, the resulting meta-graph is a DAG. So in that sense they are related. But Kosaraju's algorithm does not find labels for the meta-graph as a topological sort would do. 

I know that may all sound confusing. So the best thing is not to try to relate the two algorithms. Just understand each one on its own terms.

Last edited by rabbott at 22:03 Nov 05, 2014.
mnava18
Posts: 86
Posted 22:10 Nov 05, 2014 |

that makes alot more sense now, thanks alot professor 

cthanh
Posts: 56
Posted 00:57 Nov 06, 2014 |

Just for clarification:

Are you saying Kosaraju's algorithm did not label the graph at all or that it does so in a different method from a topological sort?

According to the video, I thought it was the latter.

Thanks

rabbott
Posts: 1649
Posted 08:21 Nov 06, 2014 |

You're right. It labels the nodes—or more accurately arranges the nodes in a linear order for the second phase to use. It's the order that matters, not the labels. The labels and order can be considered a topological sort if when you follow it, you don't follow links to Nodes that have already been seen. The effect is that each SCC becomes a dead end in the induced topological ordering.

Last edited by rabbott at 08:27 Nov 06, 2014.