|
|
| Line 1: |
Line 1: |
| − | Be sure to apply the errata and change the direction of the edge between F and H.
| |
| | | | |
| − | A topological sorting of this graph would be:
| |
| − |
| |
| − | A, B, D, E, C, H, G, I, J, F
| |
| − |
| |
| − | --[[User:Someguy|Someguy]] ([[User talk:Someguy|talk]]) 05:13, 3 March 2016 (EST)
| |
| − |
| |
| − | After the direction change of the edge between F and H, vertex H has no incoming edges, just like vertex A. If we start DFS at vertex A, according to the "topsort" on page 181, vertex H is supposed to appear at the beginning of the sorting, rather than in the middle:
| |
| − |
| |
| − | H, A, B, D, E, C, G, I, J, F
| |
| − |
| |
| − | Please correct me if I am wrong.
| |
| − |
| |
| − | --[[User:Ohk|Ohk]] ([[User talk:Ohk|talk]]) 08:03, 3 March 2016 (EST)
| |
| − |
| |
| − | If the direction from H->F is changed to F->H, then J should be the terminal vertex ?
| |
| − |
| |
| − | A pre-order DFS walk should give the ordering : A B C F H G I J D E
| |
| − |
| |
| − | The RPO toposort should be : A B D E C F H G I J
| |
| − |
| |
| − | --[[User:Someguy|Someguy]] ([[User talk:Someguy|talk]]) 04:27, 4 March 2016 (EST)
| |
| − |
| |
| − | Hi Ohk, thanks for the reply.
| |
| − |
| |
| − | The original graph on page 185 in the book pdf (obtained from "sist.sysu.edu.cn/~isslxm/DSA/textbook/Skiena.-.TheAlgorithmDesignManual.pdf") contains a directed cycle (G->F->H->G). According to the errata ("www3.cs.stonybrook.edu/~skiena/algorist/book/errata"), we should "reverse the edge (F,H)" to make it acyclic; that is to say changing the edge from F->H to H->F. It is different from yours (from H->F to F->H).
| |
| − |
| |
| − | As I understand, after the change either J or F could be the terminal vertex, since both vertices have no outgoing edges. A and H have no incoming edges, so they are unreachable from other vertices. I removed the "http//" prefix in the above links as I do not have the right to put external link.
| |
| − |
| |
| − | --[[User:Ohk|Ohk]] ([[User talk:Ohk|talk]]) 06:18, 4 March 2016 (EST)
| |
| − |
| |
| − | Aww Snap ! I have the Kindle edition of the book and it already has the correct graph.
| |
| − |
| |
| − | I am avoiding looking at the code in the book and building up the code on trying to mimic the pseudo-code
| |
| − |
| |
| − | And as per my code, the RPO order is : A, B, D, E, G, I, J, C, F
| |
| − |
| |
| − | The adjacency representation for the graph being : {A=[B, D], B=[C, D, E], C=[F], D=[E, G], E=[C, F, G], F=[], G=[F, I], H=[F, G, J], I=[J], J=[]}
| |
| − |
| |
| − | (where A=[B,D] means node A forms and edge with nodes B,D etc)
| |
| − |
| |
| − | Node H does not even appear in the topology then. And when tested with other graphs I do get correct RPO order though.
| |
| − |
| |
| − | But I see your point... H should not appear in the middle of the order, it's not reachable from any node.
| |
| − |
| |
| − | --[[User:Someguy|Someguy]] ([[User talk:Someguy|talk]]) 06:57, 4 March 2016 (EST)
| |
| − |
| |
| − | Yes, for a vertex with multiple outgoing edges, if we explore the edge in alphabetical order, then the pre-order DFS walk from A would give the ordering: A, B, C, F, D, E, G, I, J. The RPO order is: A, B, D, E, G, I, J, C, F.
| |
| − |
| |
| − | Since the "topsort" given on the page 181 has a for-loop outermost, after finishing the DFS walk from A, it then starts another DFS from H, which will only explore the vertex H. Then H will be pushed into the stack. The final RPO would be: H, A, B, D, E, G, I, J, C, F.
| |
| − |
| |
| − | --[[User:Ohk|Ohk]] ([[User talk:Ohk|talk]]) 08:45, 4 March 2016 (EST)
| |
| − |
| |
| − | Agreed...
| |
