[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.25,0:00:01.90,Default,,0000,0000,0000,,So here's a simple graph.
Dialogue: 0,0:00:01.90,0:00:03.90,Default,,0000,0000,0000,,We're going to start here with node number 2,
Dialogue: 0,0:00:03.90,0:00:06.18,Default,,0000,0000,0000,,and we're going to set the depth there equal to 0.
Dialogue: 0,0:00:06.18,0:00:10.29,Default,,0000,0000,0000,,And our goal is to find these depths for each of these vertices.
Dialogue: 0,0:00:10.29,0:00:12.15,Default,,0000,0000,0000,,Originally, none of these are set.
Dialogue: 0,0:00:12.15,0:00:14.66,Default,,0000,0000,0000,,We're just going to say that's the value for hasn't visited yet.
Dialogue: 0,0:00:14.66,0:00:19.32,Default,,0000,0000,0000,,And we're going to begin by setting vertex number 2 to the value 0.
Dialogue: 0,0:00:19.32,0:00:23.23,Default,,0000,0000,0000,,So we note that the furthest vertex away from node 2 is two hops away.
Dialogue: 0,0:00:23.23,0:00:27.80,Default,,0000,0000,0000,,So the maximum depth here is 2, and we should expect that we should iterate twice.
Dialogue: 0,0:00:27.80,0:00:31.54,Default,,0000,0000,0000,,So we're going to begin the algorithm by looking at all of these edges in parallel.
Dialogue: 0,0:00:31.54,0:00:33.34,Default,,0000,0000,0000,,And what we're looking for is a pattern
Dialogue: 0,0:00:33.34,0:00:37.71,Default,,0000,0000,0000,,where one of the vertices of these edges is going to have a depth value set,
Dialogue: 0,0:00:37.71,0:00:39.51,Default,,0000,0000,0000,,and the other one does not.
Dialogue: 0,0:00:39.51,0:00:42.48,Default,,0000,0000,0000,,And we're going to find that 3 edges have this particular quality.
Dialogue: 0,0:00:42.48,0:00:45.52,Default,,0000,0000,0000,,So one of them is going to be the edge between 1 and 2.
Dialogue: 0,0:00:45.52,0:00:47.18,Default,,0000,0000,0000,,We'll check and see.
Dialogue: 0,0:00:47.18,0:00:53.50,Default,,0000,0000,0000,,The depth at vertex 2 is 0 and vertex 1 has not been visited yet.
Dialogue: 0,0:00:53.50,0:00:57.23,Default,,0000,0000,0000,,So we'll set it equal to 0 plus 1, which is 1.
Dialogue: 0,0:00:57.23,0:01:01.13,Default,,0000,0000,0000,,We'll do the same thing for this edge here between 2 and 3, okay?
Dialogue: 0,0:01:01.13,0:01:03.47,Default,,0000,0000,0000,,We visited 2; its value was 0.
Dialogue: 0,0:01:03.47,0:01:06.07,Default,,0000,0000,0000,,We haven't visited 3, so we set its value to be 1.
Dialogue: 0,0:01:06.07,0:01:08.31,Default,,0000,0000,0000,,And this edge here, 2 and 6.
Dialogue: 0,0:01:08.31,0:01:10.41,Default,,0000,0000,0000,,Now we complete the first iteration.
Dialogue: 0,0:01:10.41,0:01:12.41,Default,,0000,0000,0000,,We visited every single edge
Dialogue: 0,0:01:12.41,0:01:16.96,Default,,0000,0000,0000,,and run 6 threads in parallel to make this particular determination.
Dialogue: 0,0:01:16.96,0:01:18.96,Default,,0000,0000,0000,,Now we begin our second iteration.
Dialogue: 0,0:01:18.96,0:01:21.22,Default,,0000,0000,0000,,So now, again, what we're looking for is an edge
Dialogue: 0,0:01:21.22,0:01:24.37,Default,,0000,0000,0000,,where the vertex value of one end of the edge has been set
Dialogue: 0,0:01:24.37,0:01:26.69,Default,,0000,0000,0000,,and the other one has not yet been visited.
Dialogue: 0,0:01:26.69,0:01:28.100,Default,,0000,0000,0000,,So we're going to find that's true for the other 3 edges.
Dialogue: 0,0:01:28.100,0:01:34.50,Default,,0000,0000,0000,,So the edge between 0 and 1, we find that the depth at vertex number 1 is 1.
Dialogue: 0,0:01:34.50,0:01:37.54,Default,,0000,0000,0000,,We find that vertex 0 has not yet been visited.
Dialogue: 0,0:01:37.54,0:01:41.30,Default,,0000,0000,0000,,So we set its depth to 1 plus 1 equals 2.
Dialogue: 0,0:01:41.30,0:01:44.62,Default,,0000,0000,0000,,And the same is going to be true for the edges between 3 and 4
Dialogue: 0,0:01:44.62,0:01:47.21,Default,,0000,0000,0000,,and the edge between 5 and 6, okay?
Dialogue: 0,0:01:47.21,0:01:50.29,Default,,0000,0000,0000,,Now we filled in a value for all of our vertices here,
Dialogue: 0,0:01:50.29,0:01:52.00,Default,,0000,0000,0000,,and we're thus complete.