TADM2E 5.2 - Revision history

Matt: Undo revision 1055 by FuckMatt (talk)

2020-08-01T01:06:17Z

Undo revision 1055 by FuckMatt (talk)

FuckMatt: Blanked the page

2020-07-31T09:35:29Z

Blanked the page

Ohk at 13:45, 4 March 2016

2016-03-04T13:45:31Z

Someguy at 12:05, 4 March 2016

2016-03-04T12:05:49Z

Someguy at 11:57, 4 March 2016

2016-03-04T11:57:42Z

Ohk at 11:25, 4 March 2016

2016-03-04T11:25:56Z

Ohk at 11:19, 4 March 2016

2016-03-04T11:19:40Z

Ohk at 11:18, 4 March 2016

2016-03-04T11:18:04Z

Someguy at 09:30, 4 March 2016

2016-03-04T09:30:25Z

Someguy at 09:29, 4 March 2016

2016-03-04T09:29:55Z

← Older revision	Revision as of 01:06, 1 August 2020
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...

← Older revision		Revision as of 09:35, 31 July 2020
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...~~

← Older revision		Revision as of 13:45, 4 March 2016
Line 50:		Line 50:

	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.		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...

← Older revision		Revision as of 12:05, 4 March 2016
Line 49:		Line 49:
	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.		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 ~~should~~ be: H, 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.

← Older revision		Revision as of 11:57, 4 March 2016
Line 44:		Line 44:

	But I see your point... H should not appear in the middle of the order, it's not reachable from any node.		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 should be: H, A, B, D, E, G, I, J, C, F.

← Older revision		Revision as of 11:25, 4 March 2016
Line 42:		Line 42:

	Node H does not even appear in the topology then. And when tested with other graphs I do get correct RPO order though.		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.

@@ Line 35: / Line 35: @@
 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, C, F, D, E, G, I, J
+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=[]}

← Older revision		Revision as of 11:18, 4 March 2016
Line 28:		Line 28:

	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.		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, C, F, D, E, G, I, J
		+
		+	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.

← Older revision		Revision as of 09:30, 4 March 2016
Line 27:		Line 27:
	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).		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.	+	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.
−
−	I removed the "http//" prefix in the above links as I do not have the right to put external link.

← Older revision		Revision as of 09:29, 4 March 2016
Line 29:		Line 29:
	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.		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.	+	I removed the "http//" prefix in the above links as I do not have the right to put external link.