Graphs/Transitive Closure - Revision history

Admin: /* Big O Cost */

2017-09-09T13:59:32Z

Big O Cost

← Older revision		Revision as of 13:59, 9 September 2017
Line 29:		Line 29:
	Performing a DFS or BFS costs <math>O(n+m)</math>, so performing a DFS or BFS on every node costs <math>O(n(n+m))</math> (where n is number vertices and m is number of edges). Because number of edges is <math>O(n^2)</math>, this gives an overall cost of <math>O(n^3)</math>.		Performing a DFS or BFS costs <math>O(n+m)</math>, so performing a DFS or BFS on every node costs <math>O(n(n+m))</math> (where n is number vertices and m is number of edges). Because number of edges is <math>O(n^2)</math>, this gives an overall cost of <math>O(n^3)</math>.

	The [[Graphs/Floyd Warshall]] algorithm is also asymptotically <math>O(n^3)</math>, but performs better for dense graphs and for graphs represented with an adjacency matrix ~~or adjacency map~~ (see [[Graphs/Data Structures]]). It is also algorithmically simpler.		The [[Graphs/Floyd Warshall]] algorithm is also asymptotically <math>O(n^3)</math>, but performs better for dense graphs and for graphs represented with an adjacency matrix data structure (see [[Graphs/Data Structures]]). It is also algorithmically simpler.

	=Flags=		=Flags=

	{{GraphsFlag}}		{{GraphsFlag}}

Admin: /* Computing Transitive Closure */

2017-09-09T13:59:13Z

Computing Transitive Closure

← Older revision		Revision as of 13:59, 9 September 2017
Line 19:		Line 19:
	Computing the transitive closure on a directed graph is not as trivial, but still straightforward (can still use a BFS or DFS).		Computing the transitive closure on a directed graph is not as trivial, but still straightforward (can still use a BFS or DFS).

	~~Alternative~~ method: if we use a data structure for storing the graph that supports O(1) lookup time for finding if there is an edge between u and v, we can implement the Floyd-Warshall algorithm, which is ''potentially'' faster than computing DFS on every node.		An alternative method is to use the [[Graphs/Floyd Warshall]] algorithm: if we use a data structure for storing the graph that supports O(1) lookup time for finding if there is an edge between u and v, we can implement the Floyd-Warshall algorithm, which is ''potentially'' faster than computing DFS on every node.

			For dense graphs or adjacency matrix representations, use Floyd-Warshall.

			For sparse graphs, adjacency list/adjacency map representations, or very large graphs, use nested DFS.

	==Big O Cost==		==Big O Cost==

Admin: /* Big O Cost */

2017-09-09T13:55:33Z

Big O Cost

← Older revision		Revision as of 13:55, 9 September 2017
Line 23:		Line 23:
	==Big O Cost==		==Big O Cost==

	~~To compute the transitive closure~~, ~~we nee~~ a ~~way to support~~ O(1) ~~lookups~~ of ~~whether an edge exists between u and v. This can be done using an adjacency matrix structure (see [[Graphs/Data_Structures]]~~). ~~As long as we can support these~~ O(1) ~~lookups~~, ~~we can construct the transitive closure in~~ <math>O(n~~(n+m)~~)</math> ~~time~~.		Performing a DFS or BFS costs <math>O(n+m)</math>, so performing a DFS or BFS on every node costs <math>O(n(n+m))</math> (where n is number vertices and m is number of edges). Because number of edges is <math>O(n^2)</math>, this gives an overall cost of <math>O(n^3)</math>.

	~~This cost comes from the fact that we are performing n graph traversals, each starting from a different vertex. We can use a DFS or a BFS, either one~~ is <math>O(n+m)</math> ~~cost~~.		The [[Graphs/Floyd Warshall]] algorithm is also asymptotically <math>O(n^3)</math>, but performs better for dense graphs and for graphs represented with an adjacency matrix or adjacency map (see [[Graphs/Data Structures]]). It is also algorithmically simpler.

	=Flags=		=Flags=

	{{GraphsFlag}}		{{GraphsFlag}}

Admin: /* Computing Transitive Closure */

2017-09-09T13:47:42Z

Computing Transitive Closure

← Older revision		Revision as of 13:47, 9 September 2017
Line 18:		Line 18:

	Computing the transitive closure on a directed graph is not as trivial, but still straightforward (can still use a BFS or DFS).		Computing the transitive closure on a directed graph is not as trivial, but still straightforward (can still use a BFS or DFS).

			Alternative method: if we use a data structure for storing the graph that supports O(1) lookup time for finding if there is an edge between u and v, we can implement the Floyd-Warshall algorithm, which is ''potentially'' faster than computing DFS on every node.

	==Big O Cost==		==Big O Cost==

Admin: /* Computing Transitive Closure */

2017-09-09T13:45:29Z

Computing Transitive Closure

← Older revision		Revision as of 13:45, 9 September 2017
Line 17:		Line 17:
	Computing the transitive closure on an undirected graph is pretty trivial - equivalent to finding components.		Computing the transitive closure on an undirected graph is pretty trivial - equivalent to finding components.

	Computing the transitive closure on a directed graph is ~~NOT~~ trivial.		Computing the transitive closure on a directed graph is not as trivial, but still straightforward (can still use a BFS or DFS).

	==Big O Cost==		==Big O Cost==

Admin: /* Notes */

2017-09-09T13:22:36Z

Notes

← Older revision		Revision as of 13:22, 9 September 2017
Line 6:		Line 6:

	If there is a directed path from u to v on G, there is a directed edge from u to v on the transitive closure G*.		If there is a directed path from u to v on G, there is a directed edge from u to v on the transitive closure G*.

			==Usefulness of Transitive Closure==

			The transitive closure G* of the graph helps us answer reachability questions ''fast''.

			==Computing Transitive Closure==

			To compute the transitive closure, we need to find all possible paths, between all pairs u and v. We can do that using a BFS or a DFS.

			Computing the transitive closure on an undirected graph is pretty trivial - equivalent to finding components.

			Computing the transitive closure on a directed graph is NOT trivial.

	==Big O Cost==		==Big O Cost==

Admin: /* Big O Cost */

2017-09-09T13:08:06Z

Big O Cost

← Older revision		Revision as of 13:08, 9 September 2017
Line 9:		Line 9:
	==Big O Cost==		==Big O Cost==

	To compute the transitive closure, we nee a way to support O(1) lookups of whether an edge exists between u and v.		To compute the transitive closure, we nee a way to support O(1) lookups of whether an edge exists between u and v. This can be done using an adjacency matrix structure (see [[Graphs/Data_Structures]]). As long as we can support these O(1) lookups, we can construct the transitive closure in <math>O(n(n+m))</math> time.


			This cost comes from the fact that we are performing n graph traversals, each starting from a different vertex. We can use a DFS or a BFS, either one is <math>O(n+m)</math> cost.

	=Flags=		=Flags=

	{{GraphsFlag}}		{{GraphsFlag}}

Admin at 12:49, 9 September 2017

2017-09-09T12:49:31Z

← Older revision		Revision as of 12:49, 9 September 2017
Line 10:		Line 10:

	To compute the transitive closure, we nee a way to support O(1) lookups of whether an edge exists between u and v.		To compute the transitive closure, we nee a way to support O(1) lookups of whether an edge exists between u and v.



			=Flags=

			{{GraphsFlag}}

Admin: Created page with "=Notes= The transitive closure of a directed graph G is denoted G. The transitive closure G has all the same vertices as the graph G, but it has edges representing the pat..."

2017-09-09T12:49:20Z

Created page with "=Notes= The transitive closure of a directed graph G is denoted G*. The transitive closure G* has all the same vertices as the graph G, but it has edges representing the pat..."

New page

=Notes=

The transitive closure of a directed graph G is denoted G*.

The transitive closure G* has all the same vertices as the graph G, but it has edges representing the paths from u to v.

If there is a directed path from u to v on G, there is a directed edge from u to v on the transitive closure G*.

==Big O Cost==

To compute the transitive closure, we nee a way to support O(1) lookups of whether an edge exists between u and v.

Graphs/Transitive Closure - Revision history

Admin: /* Big O Cost */

Admin: /* Computing Transitive Closure */

Admin: /* Big O Cost */

Admin: /* Computing Transitive Closure */

Admin: /* Computing Transitive Closure */

Admin: /* Notes */

Admin: /* Big O Cost */

Admin at 12:49, 9 September 2017

Admin: Created page with "=Notes= The transitive closure of a directed graph G is denoted G*. The transitive closure G* has all the same vertices as the graph G, but it has edges representing the pat..."

Admin: Created page with "=Notes= The transitive closure of a directed graph G is denoted G. The transitive closure G has all the same vertices as the graph G, but it has edges representing the pat..."