In this lecture, we will begin implementing in the depth first search algorithm and the previous graphing
section.
We used an adjacency matrix to create our graph.
What I want to do to provide you additional examples of how to create a graph, we are going to use
a non adjacency matrix based graph.
So let's go ahead and start setting this up to see what it looks like.
So we will derive a few traits in such as copy clone, partial equality, IQ for equality and hash.
And now we will say pub struct vertex of type U eight and now we can copy and paste this, put it down
again and instead of vertex here we will create our edge.
We will now derive
clone for our structure or for our graph.
So we will say pub struct graph and we will say vertices are going to be a vector of type vertex and
we will say edges are going to be a vector of type edge and we're going to allow dead code.
That way we can get rid of these yellow squiggles.
That way we don't see them just kind of throughout our code.
All right, So now that we have our graph here, we could begin implementing in some of the methods
that we saw in our previous section.
So we will say simple graph and we will say pub, f and new.
We'll say vertices which are going to be of type vector vertex.
We will have our edges, which are going to be a vector of edge.
And we were going to return self.
And here we will create a new graph vertices edges.
So now we need to implement in a couple of traits.
And the traits that we need to implement in are the from and into traits.
And these traits are inherently linked and this is by their natural implementation.
Because if you are able to convert a type, let's say type A from type B, then it should be easy to
convert from type B to type A, So let's see what this implementation looks like.
So we'll save from you eight for Vertex.
Then we want to implement the from method that says item of type you et self and we want to return vertex
of the item right here that we passed in.
So now we need to implement in a couple of methods for our vertex struct.
We want to get the value back.
So we'll say pub f value pass in a reference to our self where we return U8 and we return the value
in our of our vertex.
And lastly, we need to get our neighbors.
So again we will say self and we need our graph to be able to evaluate our neighbors.
We will say graph, we will bring in a vec dx q vertex, and then here we will say graph dot edges,
dot or filter on our edges where edge
equals self.
And now we want to map.
Our edge is one in two and collect.
Let's do a cargo format to clean that up.
All right.
So that looks pretty good.
So now we need to do the implement from four.
Our edge as well.
And let's see why we have an unfriendly.
Everything looks good so far.
So we will say and pull from, we will say you eight to you eight, four edge, say F and from item
of you, eight you eight
self.
And here we will say edge item dot zero.
Item dot one.
And both of those look good as well.
All right.
And we are unhappy because we need to add in our other eight here to make our tuple struck satisfy what
it's looking for.
So let's see what we're looking for here because of return type.
So we have self graphing and graph vector IQ of vertex.
Graph edges dot editor dot filter where we pass in E to the closure where e zero is equal to self zero
and we pass in ee1 end to.
We don't want that there.
We want it right there.
And now we can cargo format it.
All right.
Perfect.
So now we cleaned all of that up and we've set up our graph successfully and all of our tuples for our
vertex and our edges.
So everything there is looking.
Correct.
So there's one additional collection that we need to bring into scope and that is going to be our hash
set.
So now that we have hash set brought into scope, we can begin implementing in our depth first search.
So we will say depth first search and we're going to pass in a graph and it's going to be a reference
to a graph where our route is going to be a vertex and our objective is also going to be a vertex.
And what we're going to do is return an option that contains vector of Type U eight, and we want to
return an optional with a vector with a history of vertices visited or a none if the element does not
exist in the graph.
Right.
So we can have the solution, the depth for solution.
But imagine if we pass in an objective or a route that does not exist in the graph.
Well then we would want to return a none in that case so we can create some of our vectors.
We can say let visited and this is going to be a hash set of type vertex and here we will say hash set
new.
We need to keep our history, which is going to be au8 and we are going to create our new vector.
And lastly, we're going to have our Q, which is going to be a vector Q and we're going to go ahead
and initialize that as well.
So in our queue, since we know our first element is our root element or root vertex, we can go ahead
and push the root vertex into the back of the queue.
And so while there is an element in the queue, we need to get that element out of the queue so we can
say why let some current vertex and then we want to say queue dot pop the front.
So now we can add this into our history and say current vertex dot value
and now we want to verify if this vertex that we just popped is the objective.
So we will say if current vertex is equal to objective, then we want to return some history.
Otherwise we need to go over all of the neighbors of the current vertex.
So what we can do and to get rid of these squiggles, let's return non here.
That way everything is happy
with spell visited right is it did all right
And now again we need to go over all of the neighbors of our current vortex Vertex excuse me so we can
say for neighbor and current vertex dot neighbors and passing our graph dot into itor dot reverse.
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
visited nodes if this value does not yet exist.
So we will say if visited dot insert neighbor, then we want to push it into the queue and we will push
neighbor into the queue.
Okay.
So.
We have cannot find value in scope.
Let me take you out and let's do a cargo format.
All right.
So it looks like we have another error
here.
What is our current air cannot borrow?
Q is immutable as it is not.
That would help as well.
So we will make that mutable.
Okay, so now all of our ears are gone.
And so again, we return none if all the vertex or of all the vertices are visited and the objective
is not found.
So I said we were going to go over this reverse rev really quickly.
And it is a double ended iterator and a double iterate.
A double ended iterator has one extra capability over something that implements an iterator.
It is the ability to take items from the front and the back.
Right.
So this is useful for us since we need to backtrack.
So this allows us to make sure that we're going both ways with our iterator.
That way we can go again as far deep on that branch as we can, and then also be able to iterate the
opposite way as well.
So our depth first search implementation is looking pretty good.
So we're starting out at our root value, putting it into the queue, popping it, seeing if if we are
at our objective already.
And then if not, we are going to visit all the neighbors and add them into the queue as well and then
perform the exact same operations.
That way we can ensure that we are visiting all the vertices.
So in order for us to test this, we're going to use the graph that we did in the previous lecture
test.
We will use super to bring everything into scope and we will create our test case where we test depth
the first search.
So we will say let our vertices equal a vector of one, two, three, four, five, six and seven.
And now we need to create our edges, let edges equal a vector, and we will connect 1 to 2,
1 to 3, 2 to 4,
2 to 5.
3 to 6.
And 3 to 7.
3 to 6.
And 3 to 7.
Close our parentheses there.
Get rid of this extra one.
So now we have our edges as well.
So now we say let root equal one.
Let objective is equal to seven.
Our correct path is going to be a vector.
And our path, if you remember correctly, is going to be one, two, four, five, three, six and
seven, which we found in the previous lecture.
And now we will say let graph equals graph new and here we will say vertices dot in to itor dot map
and now we want to map each vertices
into and collect.
That way we turn our vertices into you eight.
And now we want to do our edges for the same thing.
So into itor map our edges dot into
dot collect and I believe I am missing a parentheses right here, which means I have an extra one right
there.
So everything's happy now.
And now we can say assert equals our graph, our route dot into our objective, dot into.
And I need to obviously put all this inside of the depth search function.
So for us to do that, we will quickly correct that
and we will say some.
Correct that way we can compare it.
So now if we run cargo tests, we expect a success to be printed out.
And that was what we got.
We got our success returned.
So again, we implement it in a non adjacency matrix graph just to show a different way of implementing
in a graph.
And then for depth first search, we use a Q to start out at our root node.
We pop from the Q, push that into history because that is what we are going to return once we hit our
objective.
If we do not ever hit our objective vertex, we return none.
And then and then as long as we're not at our objective vertex and still have vertices inside the Q,
we need to visit all the neighbors and we do that in this block of code here.
So hopefully this made good sense.
If you have any questions on my implementation on depth for search, please feel free to ask them in
the Q&A section and I will see you in the next lecture.