1
00:00:06,040 --> 00:00:13,300
In this lecture, we will begin implementing in the depth first search algorithm and the previous graphing

2
00:00:13,300 --> 00:00:13,930
section.

3
00:00:13,930 --> 00:00:17,290
We used an adjacency matrix to create our graph.

4
00:00:17,500 --> 00:00:25,690
What I want to do to provide you additional examples of how to create a graph, we are going to use

5
00:00:25,990 --> 00:00:28,780
a non adjacency matrix based graph.

6
00:00:29,500 --> 00:00:32,680
So let's go ahead and start setting this up to see what it looks like.

7
00:00:34,030 --> 00:00:45,460
So we will derive a few traits in such as copy clone, partial equality, IQ for equality and hash.

8
00:00:46,660 --> 00:00:58,120
And now we will say pub struct vertex of type U eight and now we can copy and paste this, put it down

9
00:00:58,120 --> 00:01:01,660
again and instead of vertex here we will create our edge.

10
00:01:03,760 --> 00:01:05,410
We will now derive

11
00:01:07,570 --> 00:01:11,080
clone for our structure or for our graph.

12
00:01:11,800 --> 00:01:23,260
So we will say pub struct graph and we will say vertices are going to be a vector of type vertex and

13
00:01:23,260 --> 00:01:32,950
we will say edges are going to be a vector of type edge and we're going to allow dead code.

14
00:01:33,250 --> 00:01:37,240
That way we can get rid of these yellow squiggles.

15
00:01:38,560 --> 00:01:41,080
That way we don't see them just kind of throughout our code.

16
00:01:43,780 --> 00:01:53,230
All right, So now that we have our graph here, we could begin implementing in some of the methods

17
00:01:53,230 --> 00:01:56,110
that we saw in our previous section.

18
00:01:56,110 --> 00:02:01,780
So we will say simple graph and we will say pub, f and new.

19
00:02:02,140 --> 00:02:09,220
We'll say vertices which are going to be of type vector vertex.

20
00:02:12,210 --> 00:02:17,580
We will have our edges, which are going to be a vector of edge.

21
00:02:22,920 --> 00:02:26,400
And we were going to return self.

22
00:02:26,400 --> 00:02:31,980
And here we will create a new graph vertices edges.

23
00:02:35,170 --> 00:02:39,580
So now we need to implement in a couple of traits.

24
00:02:40,630 --> 00:02:45,240
And the traits that we need to implement in are the from and into traits.

25
00:02:45,250 --> 00:02:52,120
And these traits are inherently linked and this is by their natural implementation.

26
00:02:52,120 --> 00:03:00,250
Because if you are able to convert a type, let's say type A from type B, then it should be easy to

27
00:03:00,250 --> 00:03:05,770
convert from type B to type A, So let's see what this implementation looks like.

28
00:03:05,770 --> 00:03:10,060
So we'll save from you eight for Vertex.

29
00:03:11,680 --> 00:03:25,030
Then we want to implement the from method that says item of type you et self and we want to return vertex

30
00:03:25,630 --> 00:03:29,770
of the item right here that we passed in.

31
00:03:32,290 --> 00:03:37,210
So now we need to implement in a couple of methods for our vertex struct.

32
00:03:37,210 --> 00:03:39,010
We want to get the value back.

33
00:03:39,010 --> 00:03:52,150
So we'll say pub f value pass in a reference to our self where we return U8 and we return the value

34
00:03:52,150 --> 00:03:55,000
in our of our vertex.

35
00:03:56,140 --> 00:03:59,920
And lastly, we need to get our neighbors.

36
00:03:59,920 --> 00:04:06,670
So again we will say self and we need our graph to be able to evaluate our neighbors.

37
00:04:07,060 --> 00:04:23,260
We will say graph, we will bring in a vec dx q vertex, and then here we will say graph dot edges,

38
00:04:23,260 --> 00:04:32,650
dot or filter on our edges where edge

39
00:04:34,900 --> 00:04:37,030
equals self.

40
00:04:39,460 --> 00:04:41,500
And now we want to map.

41
00:04:44,160 --> 00:04:51,510
Our edge is one in two and collect.

42
00:04:55,620 --> 00:04:59,280
Let's do a cargo format to clean that up.

43
00:05:00,270 --> 00:05:00,840
All right.

44
00:05:00,840 --> 00:05:02,460
So that looks pretty good.

45
00:05:02,610 --> 00:05:07,470
So now we need to do the implement from four.

46
00:05:11,490 --> 00:05:13,470
Our edge as well.

47
00:05:14,760 --> 00:05:18,330
And let's see why we have an unfriendly.

48
00:05:26,710 --> 00:05:28,030
Everything looks good so far.

49
00:05:29,020 --> 00:05:44,410
So we will say and pull from, we will say you eight to you eight, four edge, say F and from item

50
00:05:45,070 --> 00:05:48,160
of you, eight you eight

51
00:05:51,100 --> 00:05:52,240
self.

52
00:05:53,830 --> 00:05:58,870
And here we will say edge item dot zero.

53
00:05:59,500 --> 00:06:01,480
Item dot one.

54
00:06:04,270 --> 00:06:07,840
And both of those look good as well.

55
00:06:10,810 --> 00:06:11,590
All right.

56
00:06:13,540 --> 00:06:21,250
And we are unhappy because we need to add in our other eight here to make our tuple struck satisfy what

57
00:06:21,250 --> 00:06:22,460
it's looking for.

58
00:06:22,480 --> 00:06:28,900
So let's see what we're looking for here because of return type.

59
00:06:32,850 --> 00:06:37,030
So we have self graphing and graph vector IQ of vertex.

60
00:06:37,050 --> 00:06:51,030
Graph edges dot editor dot filter where we pass in E to the closure where e zero is equal to self zero

61
00:06:51,300 --> 00:06:57,150
and we pass in ee1 end to.

62
00:07:01,100 --> 00:07:02,900
We don't want that there.

63
00:07:04,700 --> 00:07:06,260
We want it right there.

64
00:07:06,680 --> 00:07:08,540
And now we can cargo format it.

65
00:07:08,540 --> 00:07:09,020
All right.

66
00:07:09,020 --> 00:07:09,520
Perfect.

67
00:07:09,530 --> 00:07:17,510
So now we cleaned all of that up and we've set up our graph successfully and all of our tuples for our

68
00:07:17,510 --> 00:07:19,160
vertex and our edges.

69
00:07:19,250 --> 00:07:22,520
So everything there is looking.

70
00:07:22,520 --> 00:07:23,210
Correct.

71
00:07:23,390 --> 00:07:33,080
So there's one additional collection that we need to bring into scope and that is going to be our hash

72
00:07:33,080 --> 00:07:33,620
set.

73
00:07:34,040 --> 00:07:42,380
So now that we have hash set brought into scope, we can begin implementing in our depth first search.

74
00:07:42,380 --> 00:07:51,140
So we will say depth first search and we're going to pass in a graph and it's going to be a reference

75
00:07:51,140 --> 00:07:59,540
to a graph where our route is going to be a vertex and our objective is also going to be a vertex.

76
00:08:01,010 --> 00:08:12,770
And what we're going to do is return an option that contains vector of Type U eight, and we want to

77
00:08:12,770 --> 00:08:23,210
return an optional with a vector with a history of vertices visited or a none if the element does not

78
00:08:23,210 --> 00:08:24,200
exist in the graph.

79
00:08:24,200 --> 00:08:24,530
Right.

80
00:08:24,530 --> 00:08:29,510
So we can have the solution, the depth for solution.

81
00:08:29,510 --> 00:08:34,700
But imagine if we pass in an objective or a route that does not exist in the graph.

82
00:08:34,700 --> 00:08:42,290
Well then we would want to return a none in that case so we can create some of our vectors.

83
00:08:42,290 --> 00:08:54,290
We can say let visited and this is going to be a hash set of type vertex and here we will say hash set

84
00:08:55,070 --> 00:08:55,580
new.

85
00:08:58,760 --> 00:09:09,860
We need to keep our history, which is going to be au8 and we are going to create our new vector.

86
00:09:11,690 --> 00:09:19,130
And lastly, we're going to have our Q, which is going to be a vector Q and we're going to go ahead

87
00:09:19,130 --> 00:09:20,690
and initialize that as well.

88
00:09:22,520 --> 00:09:31,010
So in our queue, since we know our first element is our root element or root vertex, we can go ahead

89
00:09:31,010 --> 00:09:35,210
and push the root vertex into the back of the queue.

90
00:09:35,750 --> 00:09:43,010
And so while there is an element in the queue, we need to get that element out of the queue so we can

91
00:09:43,010 --> 00:09:53,570
say why let some current vertex and then we want to say queue dot pop the front.

92
00:09:56,810 --> 00:10:04,460
So now we can add this into our history and say current vertex dot value

93
00:10:07,070 --> 00:10:14,420
and now we want to verify if this vertex that we just popped is the objective.

94
00:10:14,420 --> 00:10:24,680
So we will say if current vertex is equal to objective, then we want to return some history.

95
00:10:26,720 --> 00:10:33,560
Otherwise we need to go over all of the neighbors of the current vertex.

96
00:10:34,190 --> 00:10:39,860
So what we can do and to get rid of these squiggles, let's return non here.

97
00:10:39,860 --> 00:10:42,890
That way everything is happy

98
00:10:46,130 --> 00:10:52,580
with spell visited right is it did all right

99
00:10:55,220 --> 00:11:02,300
And now again we need to go over all of the neighbors of our current vortex Vertex excuse me so we can

100
00:11:02,300 --> 00:11:21,380
say for neighbor and current vertex dot neighbors and passing our graph dot into itor dot reverse.

101
00:11:25,610 --> 00:11:37,010
So what we want to do is and I'll go over rev in a second is we want to insert in the hash set of the

102
00:11:37,010 --> 00:11:39,830
visited nodes if this value does not yet exist.

103
00:11:39,830 --> 00:11:54,620
So we will say if visited dot insert neighbor, then we want to push it into the queue and we will push

104
00:11:54,650 --> 00:11:56,900
neighbor into the queue.

105
00:11:59,900 --> 00:12:00,370
Okay.

106
00:12:00,410 --> 00:12:00,620
So.

107
00:12:00,970 --> 00:12:05,940
We have cannot find value in scope.

108
00:12:05,950 --> 00:12:13,000
Let me take you out and let's do a cargo format.

109
00:12:15,370 --> 00:12:16,150
All right.

110
00:12:17,620 --> 00:12:20,020
So it looks like we have another error

111
00:12:22,360 --> 00:12:23,170
here.

112
00:12:24,070 --> 00:12:26,290
What is our current air cannot borrow?

113
00:12:26,290 --> 00:12:28,360
Q is immutable as it is not.

114
00:12:29,500 --> 00:12:30,940
That would help as well.

115
00:12:32,200 --> 00:12:33,970
So we will make that mutable.

116
00:12:34,750 --> 00:12:36,640
Okay, so now all of our ears are gone.

117
00:12:38,050 --> 00:12:43,420
And so again, we return none if all the vertex or of all the vertices are visited and the objective

118
00:12:43,420 --> 00:12:44,500
is not found.

119
00:12:44,890 --> 00:12:51,880
So I said we were going to go over this reverse rev really quickly.

120
00:12:52,120 --> 00:12:58,090
And it is a double ended iterator and a double iterate.

121
00:12:58,540 --> 00:13:04,840
A double ended iterator has one extra capability over something that implements an iterator.

122
00:13:05,290 --> 00:13:11,440
It is the ability to take items from the front and the back.

123
00:13:12,670 --> 00:13:12,940
Right.

124
00:13:12,940 --> 00:13:16,000
So this is useful for us since we need to backtrack.

125
00:13:16,330 --> 00:13:21,060
So this allows us to make sure that we're going both ways with our iterator.

126
00:13:21,070 --> 00:13:31,030
That way we can go again as far deep on that branch as we can, and then also be able to iterate the

127
00:13:31,030 --> 00:13:32,620
opposite way as well.

128
00:13:34,690 --> 00:13:38,590
So our depth first search implementation is looking pretty good.

129
00:13:38,590 --> 00:13:46,240
So we're starting out at our root value, putting it into the queue, popping it, seeing if if we are

130
00:13:46,240 --> 00:13:47,740
at our objective already.

131
00:13:47,740 --> 00:13:54,010
And then if not, we are going to visit all the neighbors and add them into the queue as well and then

132
00:13:54,010 --> 00:13:56,680
perform the exact same operations.

133
00:13:56,680 --> 00:14:00,280
That way we can ensure that we are visiting all the vertices.

134
00:14:01,900 --> 00:14:08,500
So in order for us to test this, we're going to use the graph that we did in the previous lecture

135
00:14:14,290 --> 00:14:15,280
test.

136
00:14:16,090 --> 00:14:27,520
We will use super to bring everything into scope and we will create our test case where we test depth

137
00:14:27,520 --> 00:14:29,080
the first search.

138
00:14:30,130 --> 00:14:41,230
So we will say let our vertices equal a vector of one, two, three, four, five, six and seven.

139
00:14:42,940 --> 00:14:51,220
And now we need to create our edges, let edges equal a vector, and we will connect 1 to 2,

140
00:14:54,100 --> 00:14:58,900
1 to 3, 2 to 4,

141
00:15:01,690 --> 00:15:03,100
2 to 5.

142
00:15:06,690 --> 00:15:07,650
3 to 6.

143
00:15:07,650 --> 00:15:09,190
And 3 to 7.

144
00:15:09,210 --> 00:15:10,500
3 to 6.

145
00:15:10,740 --> 00:15:14,820
And 3 to 7.

146
00:15:15,000 --> 00:15:16,600
Close our parentheses there.

147
00:15:16,620 --> 00:15:18,120
Get rid of this extra one.

148
00:15:18,510 --> 00:15:22,380
So now we have our edges as well.

149
00:15:24,900 --> 00:15:27,480
So now we say let root equal one.

150
00:15:27,690 --> 00:15:31,860
Let objective is equal to seven.

151
00:15:32,460 --> 00:15:37,560
Our correct path is going to be a vector.

152
00:15:37,560 --> 00:15:44,190
And our path, if you remember correctly, is going to be one, two, four, five, three, six and

153
00:15:44,190 --> 00:15:47,580
seven, which we found in the previous lecture.

154
00:15:47,760 --> 00:16:00,480
And now we will say let graph equals graph new and here we will say vertices dot in to itor dot map

155
00:16:00,480 --> 00:16:02,490
and now we want to map each vertices

156
00:16:05,610 --> 00:16:09,690
into and collect.

157
00:16:09,690 --> 00:16:12,810
That way we turn our vertices into you eight.

158
00:16:18,180 --> 00:16:21,630
And now we want to do our edges for the same thing.

159
00:16:21,630 --> 00:16:31,830
So into itor map our edges dot into

160
00:16:35,280 --> 00:16:46,950
dot collect and I believe I am missing a parentheses right here, which means I have an extra one right

161
00:16:46,950 --> 00:16:47,640
there.

162
00:16:48,720 --> 00:16:50,250
So everything's happy now.

163
00:16:50,520 --> 00:17:03,450
And now we can say assert equals our graph, our route dot into our objective, dot into.

164
00:17:03,450 --> 00:17:10,980
And I need to obviously put all this inside of the depth search function.

165
00:17:12,090 --> 00:17:16,560
So for us to do that, we will quickly correct that

166
00:17:20,250 --> 00:17:22,020
and we will say some.

167
00:17:24,160 --> 00:17:26,410
Correct that way we can compare it.

168
00:17:27,010 --> 00:17:32,800
So now if we run cargo tests, we expect a success to be printed out.

169
00:17:32,800 --> 00:17:34,390
And that was what we got.

170
00:17:34,420 --> 00:17:36,160
We got our success returned.

171
00:17:37,180 --> 00:17:44,770
So again, we implement it in a non adjacency matrix graph just to show a different way of implementing

172
00:17:44,770 --> 00:17:45,580
in a graph.

173
00:17:45,730 --> 00:17:50,800
And then for depth first search, we use a Q to start out at our root node.

174
00:17:50,800 --> 00:17:58,060
We pop from the Q, push that into history because that is what we are going to return once we hit our

175
00:17:58,060 --> 00:17:58,780
objective.

176
00:17:58,780 --> 00:18:02,770
If we do not ever hit our objective vertex, we return none.

177
00:18:04,450 --> 00:18:11,260
And then and then as long as we're not at our objective vertex and still have vertices inside the Q,

178
00:18:11,290 --> 00:18:17,050
we need to visit all the neighbors and we do that in this block of code here.

179
00:18:17,950 --> 00:18:20,920
So hopefully this made good sense.

180
00:18:21,430 --> 00:18:28,960
If you have any questions on my implementation on depth for search, please feel free to ask them in

181
00:18:28,960 --> 00:18:32,110
the Q&A section and I will see you in the next lecture.