1
00:00:00,251 --> 00:00:01,902
So here's a simple graph.
2
00:00:01,902 --> 00:00:03,905
We're going to start here with node number 2,
3
00:00:03,905 --> 00:00:06,182
and we're going to set the depth there equal to 0.
4
00:00:06,182 --> 00:00:10,290
And our goal is to find these depths for each of these vertices.
5
00:00:10,290 --> 00:00:12,152
Originally, none of these are set.
6
00:00:12,152 --> 00:00:14,655
We're just going to say that's the value for hasn't visited yet.
7
00:00:14,655 --> 00:00:19,321
And we're going to begin by setting vertex number 2 to the value 0.
8
00:00:19,321 --> 00:00:23,227
So we note that the furthest vertex away from node 2 is two hops away.
9
00:00:23,227 --> 00:00:27,802
So the maximum depth here is 2, and we should expect that we should iterate twice.
10
00:00:27,802 --> 00:00:31,537
So we're going to begin the algorithm by looking at all of these edges in parallel.
11
00:00:31,537 --> 00:00:33,336
And what we're looking for is a pattern
12
00:00:33,336 --> 00:00:37,708
where one of the vertices of these edges is going to have a depth value set,
13
00:00:37,708 --> 00:00:39,512
and the other one does not.
14
00:00:39,512 --> 00:00:42,480
And we're going to find that 3 edges have this particular quality.
15
00:00:42,480 --> 00:00:45,516
So one of them is going to be the edge between 1 and 2.
16
00:00:45,516 --> 00:00:47,182
We'll check and see.
17
00:00:47,182 --> 00:00:53,503
The depth at vertex 2 is 0 and vertex 1 has not been visited yet.
18
00:00:53,503 --> 00:00:57,231
So we'll set it equal to 0 plus 1, which is 1.
19
00:00:57,231 --> 00:01:01,131
We'll do the same thing for this edge here between 2 and 3, okay?
20
00:01:01,131 --> 00:01:03,467
We visited 2; its value was 0.
21
00:01:03,467 --> 00:01:06,066
We haven't visited 3, so we set its value to be 1.
22
00:01:06,066 --> 00:01:08,306
And this edge here, 2 and 6.
23
00:01:08,306 --> 00:01:10,408
Now we complete the first iteration.
24
00:01:10,408 --> 00:01:12,409
We visited every single edge
25
00:01:12,409 --> 00:01:16,956
and run 6 threads in parallel to make this particular determination.
26
00:01:16,956 --> 00:01:18,961
Now we begin our second iteration.
27
00:01:18,961 --> 00:01:21,217
So now, again, what we're looking for is an edge
28
00:01:21,217 --> 00:01:24,367
where the vertex value of one end of the edge has been set
29
00:01:24,367 --> 00:01:26,690
and the other one has not yet been visited.
30
00:01:26,690 --> 00:01:28,997
So we're going to find that's true for the other 3 edges.
31
00:01:28,997 --> 00:01:34,501
So the edge between 0 and 1, we find that the depth at vertex number 1 is 1.
32
00:01:34,501 --> 00:01:37,540
We find that vertex 0 has not yet been visited.
33
00:01:37,540 --> 00:01:41,305
So we set its depth to 1 plus 1 equals 2.
34
00:01:41,305 --> 00:01:44,625
And the same is going to be true for the edges between 3 and 4
35
00:01:44,625 --> 00:01:47,208
and the edge between 5 and 6, okay?
36
00:01:47,208 --> 00:01:50,287
Now we filled in a value for all of our vertices here,
37
00:01:50,287 --> 00:01:52,000
and we're thus complete.