1
00:00:06,710 --> 00:00:11,000
In this lecture, we are going to begin implementing an AR graph.

2
00:00:11,930 --> 00:00:19,490
And since we talked about different graphs in the previous lecture, we are also going to implement

3
00:00:19,490 --> 00:00:27,620
in a directed graph and an undirected graph and both of our graphs are going to be weighted.

4
00:00:28,740 --> 00:00:36,360
So since we are going to implement in two grabs directed and undirected, it would make sense to have

5
00:00:36,360 --> 00:00:43,380
two separate structs directed graph and an undirected graph

6
00:00:48,570 --> 00:00:50,670
inside of our directed graph.

7
00:00:50,670 --> 00:00:56,460
If you recall in the previous lecture I said that we were going to use adjacency matrix.

8
00:00:56,460 --> 00:01:04,440
So that's what we will call our field inside of here Adjacency, here we go, Matrix.

9
00:01:05,490 --> 00:01:13,950
And what we're going to do is we're going to use a hash map that is going to have a string and also

10
00:01:13,950 --> 00:01:20,370
a vector that contains a string and an I 32 tuple.

11
00:01:22,790 --> 00:01:24,470
And we're going to use a hash map.

12
00:01:24,470 --> 00:01:33,190
And a hash map is a data structure that uses a hashing function to map identifying values known as keys.

13
00:01:33,200 --> 00:01:41,540
So the key in our hash map is going to be the string, which is going to be the node or the vertex,

14
00:01:41,780 --> 00:01:48,770
and it's going to map it to their associated values, which is going to be our vector of a string and

15
00:01:48,770 --> 00:01:59,930
an I 32 where the string is another vertex and the 32 is the weight of the edge and the hash maps.

16
00:02:00,740 --> 00:02:08,870
So you can see that they're allowing this object to be associated to our vector here, which is going

17
00:02:08,870 --> 00:02:13,250
to contain the other nodes and edges that.

18
00:02:14,200 --> 00:02:20,200
Our node here connects to and a hash map has extremely fast lookup.

19
00:02:20,200 --> 00:02:27,760
So obviously this is going to be this is going to play very nicely with when we add nodes and also create

20
00:02:27,760 --> 00:02:31,330
edges on our vertex or our vertices.

21
00:02:31,480 --> 00:02:37,390
So we'll take this and we'll also plop this down here for our undirected.

22
00:02:37,390 --> 00:02:44,200
And since we are using a hash map, we need to bring into scope the hash map.

23
00:02:47,560 --> 00:02:48,220
All right.

24
00:02:48,490 --> 00:02:51,010
And now what we can do.

25
00:02:51,010 --> 00:03:00,670
And since both graphs undirected and directed, are very similar, the only difference is one, you

26
00:03:00,670 --> 00:03:08,080
have to look to see if one node can actually go to the other node and the other, which is a directed

27
00:03:08,080 --> 00:03:14,530
and the other which is in this case is undirected, is as long as there's an edge between two nodes,

28
00:03:14,530 --> 00:03:15,700
they can go either way.

29
00:03:15,700 --> 00:03:17,530
So there's a very slight difference.

30
00:03:17,530 --> 00:03:22,390
And with this we can implement our methods in using a trait.

31
00:03:22,660 --> 00:03:27,520
That way we're not doing two completely separate implementations for each graph.

32
00:03:28,420 --> 00:03:36,880
So we know that each graph is going to need a new method so that we can create a either a directed or

33
00:03:36,880 --> 00:03:38,140
an undirected graph.

34
00:03:39,250 --> 00:03:48,850
And then we also are going to have a method that allows us to retrieve a mutable reference to our adjacency

35
00:03:48,850 --> 00:03:52,120
matrix value inside of our struct.

36
00:03:54,520 --> 00:04:02,740
So we will say an immutable self and we will return a mutable reference hash map.

37
00:04:05,390 --> 00:04:14,960
String with a vector that contains our string and our 32.

38
00:04:17,340 --> 00:04:18,240
Close it out.

39
00:04:18,270 --> 00:04:18,630
All right.

40
00:04:18,630 --> 00:04:19,770
So that looks good.

41
00:04:20,280 --> 00:04:25,650
And now we can actually add some logic to some of our methods.

42
00:04:25,650 --> 00:04:30,480
So we both know each graph is going to need to be able to add a node.

43
00:04:30,480 --> 00:04:32,940
So we will say add node.

44
00:04:33,300 --> 00:04:39,030
And with this adding a node, we know that we're changing a field so we have a mutable reference to

45
00:04:39,030 --> 00:04:46,650
ourself and we're going to add our node, which is going to be a string, and in this case we'll return

46
00:04:46,650 --> 00:04:47,460
a Boolean.

47
00:04:47,460 --> 00:04:51,570
That way we know if our node was successfully added or not.

48
00:04:52,800 --> 00:05:01,260
Well, we want to make sure that our node doesn't already exist in our adjacency matrix so we can match

49
00:05:01,260 --> 00:05:09,810
on our adjacency matrix and we're going to get our adjacency matrix by calling our method here and we

50
00:05:09,810 --> 00:05:18,030
will say get, which is a hash map method available to us and we will get our node a K, So our key

51
00:05:18,150 --> 00:05:24,180
so we're looking for this node inside of one of these hash maps here, depending on if it's directed

52
00:05:24,180 --> 00:05:25,350
or undirected.

53
00:05:27,720 --> 00:05:30,300
So if the node doesn't exist, well, that's good.

54
00:05:30,300 --> 00:05:31,740
That means we can add it.

55
00:05:32,610 --> 00:05:39,210
So we can say self dot, adjacency matrix, dot insert.

56
00:05:40,780 --> 00:05:52,720
We want to de reference the node, call it to string and we need to give it a vector when we add it

57
00:05:52,720 --> 00:05:53,020
in.

58
00:05:53,020 --> 00:06:01,150
That way, when we go to add in edges, we have a vector where we can connect the additional node with

59
00:06:01,150 --> 00:06:08,710
its weighted edge and upon that being added successfully, we want to add true.

60
00:06:08,950 --> 00:06:16,360
And in the case that we cannot add, which is any other case, then we want to return false.

61
00:06:17,560 --> 00:06:21,730
So let's make sure that everything is still building properly.

62
00:06:21,730 --> 00:06:28,210
So we will say cargo build and that's because I need an SX there.

63
00:06:29,230 --> 00:06:29,770
All right.

64
00:06:29,770 --> 00:06:34,570
So we are compiling correctly, so everything looks good to go so far.

65
00:06:35,740 --> 00:06:39,630
So now we want to be able to add edges.

66
00:06:39,640 --> 00:06:43,330
That way we can start connecting different nodes together.

67
00:06:43,600 --> 00:06:46,780
So we will create add edge here.

68
00:06:46,780 --> 00:06:51,520
And since we are going to modify the vector in our hash map.

69
00:06:52,530 --> 00:06:59,340
Again, we're going to have a mutable reference to our self and we're going to pass in an edge which

70
00:06:59,340 --> 00:07:06,240
is going to contain a tuple with a string slice, string, slice and an I 32.

71
00:07:06,780 --> 00:07:14,190
So these two string slices are going to represent the two nodes that we are trying to connect.

72
00:07:14,340 --> 00:07:25,350
And this I 32 is going to represent the edge at the edges weight between the two nodes.

73
00:07:25,830 --> 00:07:31,290
So what we can do here is, first off, we need to make sure that the node that we are trying to connect

74
00:07:31,290 --> 00:07:37,020
to exist so we can say add node to edge zero.

75
00:07:37,020 --> 00:07:42,360
So add a node for this edge and add a node for this edge.

76
00:07:42,360 --> 00:07:49,470
And remember, we can do that because if that if that node already exists, then we just return false.

77
00:07:49,470 --> 00:07:50,910
So no harm was done.

78
00:07:51,150 --> 00:07:56,550
Otherwise, we are going to add in this node here.

79
00:07:56,670 --> 00:08:00,870
That way we're not adding an edge to something that doesn't exist.

80
00:08:02,400 --> 00:08:09,570
So now that we have, we have confirmed that both of our nodes that we are trying to have an edge between

81
00:08:09,570 --> 00:08:11,430
exist, we can.

82
00:08:14,160 --> 00:08:23,070
Begin adding in our edge so we can say, get our adjacency matrix, we want to get the entry and entry

83
00:08:23,070 --> 00:08:31,500
is a hash map method available to us where we get the entry for this node.

84
00:08:31,500 --> 00:08:37,440
So we are literally going into the hash map and getting all the information associated with this node.

85
00:08:37,830 --> 00:08:45,960
And so we want it to be two string and then we're going to modify it.

86
00:08:48,760 --> 00:09:01,930
And we'll pass in a closure where we modify accordingly by pushing in and we are pushing into our vector

87
00:09:02,350 --> 00:09:08,380
and we are pushing in the edge one.

88
00:09:08,380 --> 00:09:15,250
So this node and we're going to have to turn it to a string because that is what our vector wants

89
00:09:19,330 --> 00:09:23,800
to string and we need to give it the weight.

90
00:09:23,950 --> 00:09:25,960
And edge two is here.

91
00:09:26,920 --> 00:09:33,040
So remember, 012 So what we are doing is connecting EDGE zero.

92
00:09:33,920 --> 00:09:38,570
Two edge, one with the weight Edge two

93
00:09:41,270 --> 00:09:45,530
and let's run cargo format to make this look nice.

94
00:09:45,530 --> 00:09:46,130
All right.

95
00:09:46,130 --> 00:09:51,110
So again, we're getting our entry for the node that we are wanting to connect an edge to.

96
00:09:51,110 --> 00:09:55,940
So Edge zero, we want it to connect to EDGE one.

97
00:09:56,390 --> 00:10:07,070
So we take that entry, we modify it, and we're pushing in to the vector, the edge one, and our weight,

98
00:10:07,070 --> 00:10:09,110
which is going, which is this right here.

99
00:10:09,110 --> 00:10:11,210
So we are pushing in.

100
00:10:12,200 --> 00:10:18,110
Hey, Edge Zero is going to connect to EDGE one with the Weight edge too.

101
00:10:19,370 --> 00:10:29,120
And that's all we need to do for adding an edge so we can now implement an additional method called

102
00:10:29,870 --> 00:10:30,920
neighbors.

103
00:10:35,630 --> 00:10:41,090
And our neighbors is going to return

104
00:10:44,870 --> 00:10:50,090
a result because we want to see if there's any neighbors, because there might not be.

105
00:10:50,570 --> 00:10:54,410
And we want to have a vector.

106
00:10:56,870 --> 00:10:59,930
And our vector is what contains.

107
00:11:00,880 --> 00:11:06,130
All the neighbors to our node because remember, we're pushing in.

108
00:11:07,560 --> 00:11:14,730
When we add in a new edge, which therefore means that we're going to have a new neighbor so we can

109
00:11:14,730 --> 00:11:16,710
just return the vector.

110
00:11:17,520 --> 00:11:28,710
And we also need to return maybe a custom air type here, because what if we want the neighbor of a

111
00:11:28,710 --> 00:11:30,810
node that doesn't exist?

112
00:11:30,810 --> 00:11:41,670
So something here like our custom air type of node not in graph seems to make pretty good sense to me.

113
00:11:41,970 --> 00:11:53,370
So what we can do here is actually create ourself a new custom air type and so we'll give it a derive

114
00:11:53,880 --> 00:11:54,780
debug.

115
00:11:55,170 --> 00:12:04,020
That way we can print it out if we need to and we will say node not in graph and this is going to be

116
00:12:04,020 --> 00:12:10,800
our custom air type if a node does not exist.

117
00:12:12,120 --> 00:12:19,620
So now if we pass in a node that doesn't exist, we will get back our custom air type of node, not

118
00:12:19,620 --> 00:12:20,400
in graph.

119
00:12:21,760 --> 00:12:28,360
So I feel like that's a pretty, pretty safe thing to do to ensure that, hey, when we return, an

120
00:12:28,360 --> 00:12:28,720
error.

121
00:12:28,720 --> 00:12:34,060
If the node doesn't exist, we know why that air was returned.

122
00:12:34,600 --> 00:12:40,930
So what we can do is say match self dot adjacency matrix.

123
00:12:40,930 --> 00:12:44,920
So we want to get our adjacency matrix and then we want to get the node.

124
00:12:47,170 --> 00:12:55,330
So if that node does not exist, then we want to return our air of our node, not in graph.

125
00:12:55,420 --> 00:13:04,570
Otherwise, if that node does exist, that's great because all we have to do now is return our OC with

126
00:13:05,260 --> 00:13:07,090
that value inside.

127
00:13:07,720 --> 00:13:16,090
And that value inside is going to be our vector of our strings and our weights.

128
00:13:16,510 --> 00:13:23,350
So we're returning back a reference to our vector, and that vector is going to contain all the nodes

129
00:13:23,350 --> 00:13:28,050
and all the weighted edges that are associated with that node.

130
00:13:28,060 --> 00:13:33,250
So that is all we need to do to get all of our neighbors for our graph.

131
00:13:34,950 --> 00:13:43,680
So it looks like all of our trait methods are indeed good to go.

132
00:13:43,920 --> 00:13:54,600
So let's begin implementing in our trait for our directed and undirected graph so we can say pull graph

133
00:13:55,350 --> 00:14:01,290
for directed graph and we will say F and new.

134
00:14:01,440 --> 00:14:06,450
And here we want to return a directed graph.

135
00:14:06,660 --> 00:14:17,190
And so we say directed graph and we have our adjacency matrix and obviously we need a new hash map.

136
00:14:23,250 --> 00:14:24,750
So that looks pretty good.

137
00:14:24,930 --> 00:14:32,790
And then the other thing that we need to implement just for our directed graph is our adjacency matrix.

138
00:14:35,160 --> 00:14:47,250
And here we are returning a mutable reference to our hash map of a string of a with a vector that contains

139
00:14:47,250 --> 00:14:51,120
a string 32 tuple.

140
00:14:53,280 --> 00:14:58,230
And so here we just want to return a mutable reference to our self dot.

141
00:15:01,390 --> 00:15:03,190
Adjacency matrix.

142
00:15:05,160 --> 00:15:10,800
So that's all we need to do for our undirected or for excuse me, for our directed graph.

143
00:15:11,220 --> 00:15:18,360
So now we need to pull graph for undirected graph implement new again.

144
00:15:18,360 --> 00:15:27,810
And this time we are returning an undirected graph where here we need to have our undirected graph that

145
00:15:27,810 --> 00:15:32,640
returns an undirected graph with a new hash map.

146
00:15:35,520 --> 00:15:42,450
And again, we need to create our adjacency matrix, which is a mutable reference to our cell

147
00:15:45,900 --> 00:15:47,070
and mute.

148
00:15:47,760 --> 00:15:51,450
Hash map, string vec.

149
00:15:55,030 --> 00:15:56,620
String I 32.

150
00:15:58,060 --> 00:16:06,090
And now we want to return a mutable reference to our self thought adjacency matrix.

151
00:16:06,100 --> 00:16:11,560
All right, So let's make sure we don't have any compiler errors and we're good to go.

152
00:16:11,740 --> 00:16:14,750
And let's do a cargo format to make sure everything looks good.

153
00:16:14,770 --> 00:16:15,430
Awesome.

154
00:16:16,960 --> 00:16:28,150
So there is actually one more method that we need to implement ourself for our undirected graph.

155
00:16:28,870 --> 00:16:35,920
And I want to take a look at this method right here that we implemented in on our trait called Add Edge.

156
00:16:37,000 --> 00:16:44,920
So if we look at this again, we see that we are making sure that our node exists, that we are trying

157
00:16:44,920 --> 00:16:48,700
to add an edge between for both, for both nodes.

158
00:16:49,120 --> 00:16:57,700
And that way we can we know for a fact that, hey, both of these nodes are in our adjacency table or

159
00:16:57,700 --> 00:16:59,620
excuse me, our adjacency matrix.

160
00:17:00,580 --> 00:17:08,620
So what we're doing is we're connecting Edge zero to Edge one with this weighted value here.

161
00:17:10,420 --> 00:17:15,610
So if you take a second to kind of think about that and again, I'll say it again, we're going from

162
00:17:15,610 --> 00:17:19,120
0 to 1 with this weight.

163
00:17:20,140 --> 00:17:27,160
Well, that means that we did the directed graph implementation here for ADD Edge.

164
00:17:27,400 --> 00:17:28,900
But what about Undirected?

165
00:17:28,900 --> 00:17:29,230
Right?

166
00:17:29,230 --> 00:17:34,780
Because we also need Edge one to go to Edge zero.

167
00:17:34,780 --> 00:17:40,660
So we need to specify that, hey, this edge goes both ways because currently this edge is only going

168
00:17:40,660 --> 00:17:42,490
to go from 0 to 1.

169
00:17:42,490 --> 00:17:44,290
So from 0 to 1.

170
00:17:44,710 --> 00:17:50,320
So from Node A to node B, but currently it does not go from B to A.

171
00:17:51,310 --> 00:18:03,040
So what I want you to do is I want you to add in the implementation for add edge and our function setup

172
00:18:03,040 --> 00:18:06,790
will look the same for as it did in our trait.

173
00:18:07,510 --> 00:18:21,550
And we need to have a string string sli string slice I 32 and we can actually copy in the rest our copy

174
00:18:21,550 --> 00:18:22,590
in what we did above.

175
00:18:22,600 --> 00:18:26,290
So we are making sure both of our nodes are here

176
00:18:28,780 --> 00:18:30,760
before we try to add an edge.

177
00:18:31,690 --> 00:18:39,250
And now we are going to add our edge between this vertex and this vertex.

178
00:18:39,250 --> 00:18:43,240
So we are getting our adjacency matrix entry

179
00:18:45,520 --> 00:18:49,090
edge .0.2 string.

180
00:18:50,620 --> 00:19:05,950
Now we want to modify it, pass in via closure, our value that we returned and we want to push in edge

181
00:19:05,950 --> 00:19:07,840
.1.2

182
00:19:10,600 --> 00:19:16,150
string and then our weight so edge dot to

183
00:19:19,210 --> 00:19:23,440
all right let's cargo format this to make it pretty.

184
00:19:25,180 --> 00:19:33,130
All right so as you can see, everything is the exact same as what we did above.

185
00:19:35,710 --> 00:19:47,470
So what I want you to do now as a small little assignment is I want you to add in connecting

186
00:19:49,930 --> 00:20:00,490
edge dot one to edge dot zero so that the graph is now undirected, right?

187
00:20:00,490 --> 00:20:10,000
Because if we go from 0 to 1, but also from 1 to 0, so from this vertex to this vertex and then go

188
00:20:10,000 --> 00:20:14,650
this vertex to this vertex, then it's technically undirected.

189
00:20:16,210 --> 00:20:25,570
So I want you to take a minute to try and implement this in yourself and we'll go over my implementation

190
00:20:25,570 --> 00:20:26,890
and the next lecture.

191
00:20:26,890 --> 00:20:32,710
And we will also begin implementing in our test cases in the next lecture so that we can test out our

192
00:20:32,710 --> 00:20:35,980
graph to make sure it is functioning properly.

193
00:20:36,700 --> 00:20:39,550
So I will see you in the next lecture.