In this lecture, we are going to begin implementing an AR graph.
And since we talked about different graphs in the previous lecture, we are also going to implement
in a directed graph and an undirected graph and both of our graphs are going to be weighted.
So since we are going to implement in two grabs directed and undirected, it would make sense to have
two separate structs directed graph and an undirected graph
inside of our directed graph.
If you recall in the previous lecture I said that we were going to use adjacency matrix.
So that's what we will call our field inside of here Adjacency, here we go, Matrix.
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
a vector that contains a string and an I 32 tuple.
And we're going to use a hash map.
And a hash map is a data structure that uses a hashing function to map identifying values known as keys.
So the key in our hash map is going to be the string, which is going to be the node or the vertex,
and it's going to map it to their associated values, which is going to be our vector of a string and
an I 32 where the string is another vertex and the 32 is the weight of the edge and the hash maps.
So you can see that they're allowing this object to be associated to our vector here, which is going
to contain the other nodes and edges that.
Our node here connects to and a hash map has extremely fast lookup.
So obviously this is going to be this is going to play very nicely with when we add nodes and also create
edges on our vertex or our vertices.
So we'll take this and we'll also plop this down here for our undirected.
And since we are using a hash map, we need to bring into scope the hash map.
All right.
And now what we can do.
And since both graphs undirected and directed, are very similar, the only difference is one, you
have to look to see if one node can actually go to the other node and the other, which is a directed
and the other which is in this case is undirected, is as long as there's an edge between two nodes,
they can go either way.
So there's a very slight difference.
And with this we can implement our methods in using a trait.
That way we're not doing two completely separate implementations for each graph.
So we know that each graph is going to need a new method so that we can create a either a directed or
an undirected graph.
And then we also are going to have a method that allows us to retrieve a mutable reference to our adjacency
matrix value inside of our struct.
So we will say an immutable self and we will return a mutable reference hash map.
String with a vector that contains our string and our 32.
Close it out.
All right.
So that looks good.
And now we can actually add some logic to some of our methods.
So we both know each graph is going to need to be able to add a node.
So we will say add node.
And with this adding a node, we know that we're changing a field so we have a mutable reference to
ourself and we're going to add our node, which is going to be a string, and in this case we'll return
a Boolean.
That way we know if our node was successfully added or not.
Well, we want to make sure that our node doesn't already exist in our adjacency matrix so we can match
on our adjacency matrix and we're going to get our adjacency matrix by calling our method here and we
will say get, which is a hash map method available to us and we will get our node a K, So our key
so we're looking for this node inside of one of these hash maps here, depending on if it's directed
or undirected.
So if the node doesn't exist, well, that's good.
That means we can add it.
So we can say self dot, adjacency matrix, dot insert.
We want to de reference the node, call it to string and we need to give it a vector when we add it
in.
That way, when we go to add in edges, we have a vector where we can connect the additional node with
its weighted edge and upon that being added successfully, we want to add true.
And in the case that we cannot add, which is any other case, then we want to return false.
So let's make sure that everything is still building properly.
So we will say cargo build and that's because I need an SX there.
All right.
So we are compiling correctly, so everything looks good to go so far.
So now we want to be able to add edges.
That way we can start connecting different nodes together.
So we will create add edge here.
And since we are going to modify the vector in our hash map.
Again, we're going to have a mutable reference to our self and we're going to pass in an edge which
is going to contain a tuple with a string slice, string, slice and an I 32.
So these two string slices are going to represent the two nodes that we are trying to connect.
And this I 32 is going to represent the edge at the edges weight between the two nodes.
So what we can do here is, first off, we need to make sure that the node that we are trying to connect
to exist so we can say add node to edge zero.
So add a node for this edge and add a node for this edge.
And remember, we can do that because if that if that node already exists, then we just return false.
So no harm was done.
Otherwise, we are going to add in this node here.
That way we're not adding an edge to something that doesn't exist.
So now that we have, we have confirmed that both of our nodes that we are trying to have an edge between
exist, we can.
Begin adding in our edge so we can say, get our adjacency matrix, we want to get the entry and entry
is a hash map method available to us where we get the entry for this node.
So we are literally going into the hash map and getting all the information associated with this node.
And so we want it to be two string and then we're going to modify it.
And we'll pass in a closure where we modify accordingly by pushing in and we are pushing into our vector
and we are pushing in the edge one.
So this node and we're going to have to turn it to a string because that is what our vector wants
to string and we need to give it the weight.
And edge two is here.
So remember, 012 So what we are doing is connecting EDGE zero.
Two edge, one with the weight Edge two
and let's run cargo format to make this look nice.
All right.
So again, we're getting our entry for the node that we are wanting to connect an edge to.
So Edge zero, we want it to connect to EDGE one.
So we take that entry, we modify it, and we're pushing in to the vector, the edge one, and our weight,
which is going, which is this right here.
So we are pushing in.
Hey, Edge Zero is going to connect to EDGE one with the Weight edge too.
And that's all we need to do for adding an edge so we can now implement an additional method called
neighbors.
And our neighbors is going to return
a result because we want to see if there's any neighbors, because there might not be.
And we want to have a vector.
And our vector is what contains.
All the neighbors to our node because remember, we're pushing in.
When we add in a new edge, which therefore means that we're going to have a new neighbor so we can
just return the vector.
And we also need to return maybe a custom air type here, because what if we want the neighbor of a
node that doesn't exist?
So something here like our custom air type of node not in graph seems to make pretty good sense to me.
So what we can do here is actually create ourself a new custom air type and so we'll give it a derive
debug.
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
our custom air type if a node does not exist.
So now if we pass in a node that doesn't exist, we will get back our custom air type of node, not
in graph.
So I feel like that's a pretty, pretty safe thing to do to ensure that, hey, when we return, an
error.
If the node doesn't exist, we know why that air was returned.
So what we can do is say match self dot adjacency matrix.
So we want to get our adjacency matrix and then we want to get the node.
So if that node does not exist, then we want to return our air of our node, not in graph.
Otherwise, if that node does exist, that's great because all we have to do now is return our OC with
that value inside.
And that value inside is going to be our vector of our strings and our weights.
So we're returning back a reference to our vector, and that vector is going to contain all the nodes
and all the weighted edges that are associated with that node.
So that is all we need to do to get all of our neighbors for our graph.
So it looks like all of our trait methods are indeed good to go.
So let's begin implementing in our trait for our directed and undirected graph so we can say pull graph
for directed graph and we will say F and new.
And here we want to return a directed graph.
And so we say directed graph and we have our adjacency matrix and obviously we need a new hash map.
So that looks pretty good.
And then the other thing that we need to implement just for our directed graph is our adjacency matrix.
And here we are returning a mutable reference to our hash map of a string of a with a vector that contains
a string 32 tuple.
And so here we just want to return a mutable reference to our self dot.
Adjacency matrix.
So that's all we need to do for our undirected or for excuse me, for our directed graph.
So now we need to pull graph for undirected graph implement new again.
And this time we are returning an undirected graph where here we need to have our undirected graph that
returns an undirected graph with a new hash map.
And again, we need to create our adjacency matrix, which is a mutable reference to our cell
and mute.
Hash map, string vec.
String I 32.
And now we want to return a mutable reference to our self thought adjacency matrix.
All right, So let's make sure we don't have any compiler errors and we're good to go.
And let's do a cargo format to make sure everything looks good.
Awesome.
So there is actually one more method that we need to implement ourself for our undirected graph.
And I want to take a look at this method right here that we implemented in on our trait called Add Edge.
So if we look at this again, we see that we are making sure that our node exists, that we are trying
to add an edge between for both, for both nodes.
And that way we can we know for a fact that, hey, both of these nodes are in our adjacency table or
excuse me, our adjacency matrix.
So what we're doing is we're connecting Edge zero to Edge one with this weighted value here.
So if you take a second to kind of think about that and again, I'll say it again, we're going from
0 to 1 with this weight.
Well, that means that we did the directed graph implementation here for ADD Edge.
But what about Undirected?
Right?
Because we also need Edge one to go to Edge zero.
So we need to specify that, hey, this edge goes both ways because currently this edge is only going
to go from 0 to 1.
So from 0 to 1.
So from Node A to node B, but currently it does not go from B to A.
So what I want you to do is I want you to add in the implementation for add edge and our function setup
will look the same for as it did in our trait.
And we need to have a string string sli string slice I 32 and we can actually copy in the rest our copy
in what we did above.
So we are making sure both of our nodes are here
before we try to add an edge.
And now we are going to add our edge between this vertex and this vertex.
So we are getting our adjacency matrix entry
edge .0.2 string.
Now we want to modify it, pass in via closure, our value that we returned and we want to push in edge
.1.2
string and then our weight so edge dot to
all right let's cargo format this to make it pretty.
All right so as you can see, everything is the exact same as what we did above.
So what I want you to do now as a small little assignment is I want you to add in connecting
edge dot one to edge dot zero so that the graph is now undirected, right?
Because if we go from 0 to 1, but also from 1 to 0, so from this vertex to this vertex and then go
this vertex to this vertex, then it's technically undirected.
So I want you to take a minute to try and implement this in yourself and we'll go over my implementation
and the next lecture.
And we will also begin implementing in our test cases in the next lecture so that we can test out our
graph to make sure it is functioning properly.
So I will see you in the next lecture.