Hello.
We just finished coding the very first partner algorithm, the DFS.
Now we want to test it naturally to better understand the inner workings of an algorithm.
We will start all by testing on a much smaller, tiny means.
If the DFS is able to find a part to go after mapping, then we can be confident enough to run it on
the original.
Now let's head over to the desk mapping dot pi, which I modified a little bit to test out our path
planner algorithm.
Let's go.
So here we are at the desk mapping the pie.
We start by importing the DFS class that we've just developed earlier.
We then create its object and then after we perform the mapping stage on the tiny maze.
We then head on over to the port planning algorithm where we call the get pass function of our DFS class.
Now this function takes in three arguments.
The first is the graph extracted from the board member class.
Then we have the start and the point, basically the start and the goal point from which you want to
find all possible parts.
Once we find all possible paths, this gets output to this false variable and then displayed by the
sprint statement.
Now for the start point, I've simply said this to the entry point of the myth and for the end.
Or the ghoul.
We are simply said this to the random interest point on our meals.
That is three common four.
Now, if I run this.
What we got are these three windows.
After performing mappings did so the tiny miss.
If we zoom this over you will see that this is a lot simpler.
What we used for debugging the mappings did so right on the top is the maze entry point and the right
in the bottom is a maze exit.
But we want to find all possible paths from the maze entry and three four, which will be somewhere
in the middle of this maze.
So all possible path that lead up to the school.
So and below here in the terminal you can see the graph that has been extracted.
Now, if I press enter, it should give us the path planning towards the goal.
Woops we have an error and the error is a name error which says that the name get path is not defined.
Why is that happening?
It says on the line 28 of the bot path meaning or part.
So let's head on over and see why we have the center.
So line 28 is right here we are where we are recursively calling the get bots function.
But the problem is we tried to solve this problem or problem solve this problem of finding all possible
path using recursion.
But we have named this function as a static method.
And the reason we did that, because we wanted this function to be a static method, because we did
not want access to any instance variable or the member function of the DFS class.
But the problem exist because we want to inform this or solve this problem.
Using recursion and recursion requires the X to the member function of the same that or the same access
to the same function that is getting called from.
So this is a problem.
So how do we fix this?
One method is to remove the instance or static method that we have declared this function as and simply
keep it as a member function so that we could access this function from inside the function.
But another method that can simply let this method be a static method and still call this function from
inside it and perform recursion.
And that can be done by simply writing the class name and then calling the the function.
That was the static method.
So one says Kristy.
This should hopefully solve this problem.
We don't know what the test method or fight and plus play.
After the mapping stage has been performed in space groups, we now have anywhere.
So the recursion error, it says, is the maximum recursion depth exceeded.
So basically what's happening is that whichever recursion that we were using, the problem is that it
went into an infinite loop and basically set up a maximum recursion depth exceeded it.
So we need to head on over to the board part, planning part and see where in this algorithm this is
happening.
Now, there are two goals of this error.
One course can be that we haven't defined the simplest case or the best condition for our particular
function that is using recursion.
But if you look right here, we have defined the simplest case.
So there is no in the problem the function to theoretically get simplified until it leaves to this base
condition and then returns this part and rolled back all the previous sub problems, eventually finishing
the function.
And then the problem that could occur that could cost is infinite because an error is that when this
function is getting called, there is no check whether it is stuck in a loop or not.
And this can get stuck into a loop when we're using undirected graphs and we're using injector graphs.
So we need to keep a check of which node that we were visiting.
So if we look on the graph that we extracted earlier, we have see neighbor nodes that includes nodes
that have access to and from each other.
So we do not visit knows that we have already visited.
So that can be done by simply saying that if the node was already visited, do not visit that node.
And there is inside the fourth variable right here, because when we call this function that becomes
start and that gets saved inside the path variable.
So we need to check whether if the node is in path, don't visit that node.
Another thing that we do, we really hope that apart from the neighbor nodes, we also keep track of
the case of each note.
So the case of Node is not a neighbor node, it's just represents the case of each node.
For example, the start node is the this case is start.
So we don't want to visit that node.
So these are the two conditions that we need to apply to solve this infinite precaution error for this
particular function.
So let's do this.
So we write here if the node not in path.
So we like to, if not, not in part.
So if it is not already visited and nor does not equal to case, then you should visit that particular
note and then recursively call that function.
So this will hopefully solve the error of infinite recursion.
Now, if I head on over to this map and our path presently.
And once the mapping stage has been completed, we press spacebar and this time we have the solution.
So we have found the path that lead up to the mass entry that was zero four to the random interest point
that was three or four.
So we have found all possible paths and they are basically three for this particular case.
So.
This has worked correctly.
But to better understand what was happening behind the scenes, we need to perform the same step.
But using the debug tools of the VR score so that we could see what would happen.
What was happening.
Line by line when we were solving to find all possible paths to the goal.
Let's do that.
So we are now ready to debug the get pass function and understand recursion along the way.
So I've opened several windows and let's see them one by one.
On the right hand side of the graph that you've just extracted that represents the node and the connection
between those nodes.
And on the left hand side you have the debug window.
And in the middle we have the test mapping North Point and right at line 28, I've added a breakpoint
to indicate to a debugger that this is the function that I want to debug a lesson on this.
When this gets started, you will see that the mapping process executes and then when I press spacebar,
this function gets called.
This is the point where the program has stopped because of the breakpoint.
Now let's close this terminal and you will see once I press F11 or step into, we enter this function
on the left hand side.
A lot of things has gone populated.
So let's look at this watch window.
This watch window is basically for us to watch some specific variables that we want to keep track while
executing this function.
This includes the start and end node, which is basically the start point and the goal point from which
you want to find all possible parts.
So these are zero four and three four.
If you look on the right hand side of this image, you're going to see a04 and three four have been
given distinct indicate the start point and end point respectively.
So this is giving us the correct output.
And then we have the node which is not populated here at this moment.
Then we have the path which is initialized to an empty list, and then we have the path now pass basically
restored all the possible paths towards our goal node and then we have the call stack window.
Now this window was very useful in recursion because it basically tells how many missing methods and
how many times have they been called by executing the particular window.
So you can see the main has been called once and the great path has been called once.
So we are right now executing the good parts and that is why it is right on the top for a stick.
So at this moment we have the start point as zero four and .34, which is on the spot window.
And in this graph class.
Let's proceed further by pressing F11 and you will see that the path now gets concatenated.
Well.
So start now.
Get candidate for the empty list of path variable.
So path is now not an empty list, but it has been updated to zero four tuple inside the list.
So this includes all the visited variables or visited nodes that we have visited while moving towards
the goal node.
And then we proceed to a condition that ticks whether we have reached the simplest case or not.
And that would be if the start node is equal to load, but the starting with the zero four and the end
notice three four.
So they are not equal.
This condition does not get through.
So we move on to the next condition.
The next condition is where the start node is part of the graph or not.
And if you look on the right hand side, you can see this dark node is indeed part of the graph and
it is connected to other neighbors notes.
So this is part of the graph, so this will not get executed.
We move to the next step that is initializing the past variable to an empty list.
Now this way we will have installed all possible paths.
Once they get extracted, we then proceed to the next step.
This includes.
The neighbour knows extracting the neighbour knows iteratively from a stock note.
At the moment the stock notes zeal for its neighbor.
Note If you look right over here is two four.
So it has only one neighbor.
And also another thing that each node has is the case of that node.
And that is also can be represented as a neighbor node.
But we don't want to visit the case.
So we will simply ignore the the node that is equal to case which that which I mentioned right over
here.
So we literally extract all the neighbor node of our start node, so we proceed further.
At the moment, the name of Node is Case.
As I mentioned before, we want to ignore all nodes that are named as case, which is indicated right
over here.
So this will move back and iterate over the next neighbor known for our stock node.
So it does move back and then we trade over the next neighbor node is to put the two for is the neighbor
node of our zero for function and it is the only neighbor node and it is not visited and it is not equal
to case.
So this condition gets true.
So we recursively call the get part function by providing the node of the neighbor node.
That is true port as the start note.
So this sticker simply called and you will see the note now equals 2 to 4 and this will get recursively
call.
And the good false function is now being called recursively.
And this is why the start node now becomes two four.
So this is a two fold.
And in the call stack you will see that the recursion has called the gets good part function once more.
So you can see two calls of the same function.
And this is how recursion, books and this is why call stack is very useful in understanding the understanding
recursion.
So at this moment we have called get pass function twice and they have not been completed as of yet.
So we have to start node of two four and the end node of three four.
So we are visiting two four.
So if you look at two four, it has three neighbor nodes zero, four, three, three and three, four
and also the case node.
So we proceed further.
You will see that this is not equal to end because two four is not equal three four.
So this does not get executed and it is also part of the graph.
So this also gets nodes executed, baskets really slide to an empty list.
And then we as the neighbor node for our two for note the neighbor note 424043, three and three four.
And the key is no.
So the first we ignore the case node.
We go back it later with the next neighbor note for our two four that now becomes.
That all becomes.
Zero four, but the offer has already been visited, which is indicated if we look at the part which
is zero four and two four.
So we don't want to with the zero four, we go back and iterate over the next neighbor node and the
next neighbor will be either three, three, three, four.
You proceed further, you will see that this is three, three.
So three is not part of the.
It has not been visited.
So we visit three three as a neighbor node.
So once it was in the treaty.
So we visit the city and once to visit the TNC, you will see that this particular node is a four junction
and it has access to four other nodes.
That includes two, four, three, four, three, one and four, four, and also the case node.
Now we start off by simply congratulating the start node.
That was three three because it was being treated as the node.
This guest could get native to the port, which is which is zero 4 to 4 right now.
Once this statement gets executed, this now becomes zero for.
Two, four and two, three.
Now we proceed further and check whether this starting word is equal to N, but three three is not equal
to three four.
So this does not get executed.
It is also part of the graph indicated by this window and then proceed for the initials or part.
And then it was in the neighbor node for the TSI note.
So the first neighbor node is always case.
We ignore the case.
With the next node there is now 313.
One is not part of the part.
If we look right over here, so there is no three one right over here.
So we can visit three when we visit three, one next.
So we visit T1 next and then proceed to three one.
So we recursively call our get function.
So at the moment, if we look on the call stack, right at this moment, there are four, four calls
of the get pass function.
And all of these calls have not been completed because once a particular call has completed, it gets
removed from the stack.
So this whole process will complete when this text is simply empty.
At this moment, we have fourth call of the get pass function and this is called when we are visited
three one.
Now this is the point.
You will see that the get passed call inside the call stick will will decrease by one.
And the reason is, when we visit the three one, you will see that the neighbor note of three one is
three Z.
But we have just been to three Z, so it is already part of the fourth.
So if you look right here.
So it is already part of the fourth.
So it was already part of the plot.
And Steven also gets added to this plot.
So once we proceed further, it is not equal to end because this is Article three, four or one is an
Article four, and it is also part of the graph as indicated on this image.
So this does not get executed.
Also get initialized to an empty list.
And then it was eight, the neighbor node order three one.
So three one has only one name a note that is three three apart from the case note.
So after the case, nor was it we see that we have the neighbor node of.
They were all dizzy, but.
Well, see, these all already been visited, which is indicated by the.
Well, it's variable right over here.
You can see it is already part of the board.
So this condition does not get to you because we go back and we see that there is no other never known.
So what has done is basically an empty list or an empty plot.
So this gets written.
And with this, Goodstein is right over here where it was being called.
So you will see at this moment there are four called the get false function.
But once this gets it down, the get path called stack decreases by one.
So now there are only 3 seconds left.
Now you proceed further.
We simply get this empty list as a new path.
We calculate this out of the parts because it's an empty list.
So now we visit.
So now we visit the Nord is right now to vote, but the two port has already visited so we don't visit
that.
So this is I mean, was it it was all done.
Was it to go back to treaty?
We don't bother to to poll.
So now we have already visited three one.
So what is left for us to do is to visit either three, four or four foot.
So what are we visiting right now?
So we will see.
That now the neighbor notice to report.
So we are visiting three four.
So t four is going to be visited next because it is not part of the port is indicated right over here.
So three four is not part of the park.
We can visit see four and it is not equal to kids.
So we visit three for next.
And once they visit three, four, you will realize.
That we can coordinate this to the pot, which was basically diagonal zero 4 to 4 and to three.
So we concatenate this two, three, three in the end, and this becomes, you know, four, two, four,
two and three, four.
We realize the triple is equal to and the start is equal to earn.
So we return the port that we have right now.
So this is the part that leads up to the goal, you know, four, two, four, two, three, four.
So we return this time as a new boss and goals to reduce by one new pots and new products added to the
pots.
And then we go back and once we edit this for the passwords found a042433 and three four and this gets
included to the parts, so forth.
Now here's one part that leads up to the goal.
So in this way, recursion has found one part where it has not completed as of yet.
It will complete until it has found all possible path to the goal.
So at this moment, what is happening is that the start node is now three three.
So we have visited one.
We have visited seafood and we have already visited Tupac.
So what is left is two, four, four to visit.
So you will see the note now becomes maybe it will not become four, four, visit four, four, because
it's not part of the part.
And once we waited for the call in case by one, and this goes concatenated to our part.
So it was it was it the four four?
So once you visit the four four, you will see that this has three labor nodes.
This includes three, four, three, three and six, four.
And the problem with this is that we have already visited three, four and three, three.
So these are we visited.
And three.
Four is already visited.
Sorry, we have visited two or three, but we have not visited three.
Four.
It was visited in the previous part, but in the current part it has not been visited.
So if you look on the parts right now, it includes zero 4 to 4, 20 and three and four and four four.
So there is no three for right now because default is it was in the previous block.
So in this part, we don't have three, four, so we haven't visit three four yet.
So we will now visit three for next.
So once we proceed further at this moment, you will see that we are on four four.
It is an article two and it is part of the graph and parts.
Just initialize two empty list within the neighbor node.
The first is always obviously the case node.
We ignore the case node.
We then within the next node that is three, three, three, three is already visited.
So we don't visit that.
We go back.
And then we have the next day with no that is three four or it is it is just not part of the park.
So was it that not called a function a game called stack increased by one and then.
Once we proceed further, we add this to the part three, four to the part that includes 04242, three,
four, four and three, four, four and three, four.
But this isn't a path now.
And if you look right over here, the start is now three four and is three four.
So these both gets equal.
So we return the pot.
So we have found a path that leads up to that goes know it.
So we are visiting three four.
So three, four is the gold node.
And this means that we have found a path that leads up to the gold.
So this is from 042242332442, three, four.
So we have on the second pot.
So this gets output as new pots and this gets concatenated to the path.
So we have now found two paths to our gold note.
So we proceed further and then proceed to the next case.
Now for the next case, you're building for four.
So we are still three, three, and we have now visited three or four and they're only left for us to
do is to visit six for.
So if you look if you move further, you will see that maybe one or 264.
So you're visiting six for now.
It is not part of the path as it is evident right over here.
And then it was at six four called the function again and then this get good coordinated to the part.
This is not equal to.
And this is part of the curve.
And baskets in a slice to an empty list.
And then the neighbor.
No.
464064172264.
You will see that it has only one neighbor node that is for pork, but for vote is already visited because
we have been through that node two needs to this node.
So we cannot go back and we need to simply ignore six four.
So what would happen is.
But if you look right over here, then they would know it would be.
Firstly the case, not ignore the case.
The next is the fourth for what we have already been to for, for as it is indicated from the fourth.
So if you look at the part you've already been to for four.
So we will not visit that node.
Then we can return an empty list or two.
Empty list.
This is done.
You go back.
We go back to four, four because it was already visited.
And then we see that we have visited all neighbors of four, four, so we can go back again.
And this time you will see the stock node now become.
So you see.
So we go back to treaty and you will see that we have visited three, four, four, four and three,
one.
So we need to go back again because all the neighboring nodes of three three have also been visited.
So this time we go back one more step and go back to two four.
And you will see the two four.
We have already missed the zero four and the Canadian of two four.
The only thing left for us to do is to visit the final.
They were node of the three port.
So this will be evident.
Once they visited.
Mostly it was the neighbor note for our two four that is left that is three four.
We visit the T for this guide to the path, which is right now zero four and two four.
This gets added to the pot, which becomes zero four, two, four and three four as three four is a
start and three four is, then this becomes equal.
So we return the part.
So we have found another solution.
So you're visiting t four.
So T four is the goal.
So this is the part.
The third part that we found was the goal.
So this is the final part that we found was the goal.
And in total, we have found three paths that lead up to the goal.
And this will get concatenated for the false list.
And.
Once we can coordinate all these parts.
And return them.
This function gets executed in the baskets return.
We now have the possibility.
And if you expand this path, you will see that three paths that we have.
And then we will print out the user, return the mean.
And if for display.
And if you display a terminal, you will see that the path that we have just found.
So these are the bars.
So these are all possible paths that lead up to the goal node from 04234.
We have found three paths to lead up to the goal.
So this is how recursion can be used to find all possible paths inside a DFS algorithm.
So this was working correctly and we can now test it out on our original maze and find all possible
paths that lead up to the maze exit building.
Thank you.
And.
But.
All right.
In the previous session, we not only debunked but also rated the good part function for the DFS.
Now all that is left for us to do is to simply integrated to the whole project.
Now, for this reason, I made a few modifications in a few files, starting with the board part, planning
that part apart from the DFS.
I've got a new class that is brought forth then.
And the reason for creating this class is twofold.
The first reason being that I wanted to display the phone part back on the miss from which it was extracted
from.
Because just printing out the part on the console seems to be not or insufficient.
And the reason is that for the larger maze is displaying that the path in the form of tuples does not
help in understanding whether it was the correct path or not.
Rather, displaying it on the maze from which it was extracted from seems to be a much better option.
The other reason is that I wanted to develop and test out different path planning algorithms other than
DFS.
So creating a separate class that has access to all these path planning algorithms and can be tested
by simply selecting a method as an argument for a function seems to be the best option.
And the other modification that I did was inside the boat mapping out by way of a new instance variable
that is not me.
And this variable gets initialized inside the graph y function where it gets initialized to thin crop
or the boundary to move me.
Now this setup is well initialized and created because of the path planning function of find, path
and display.
And its third argument is third argument is the means on which you want to draw the following part.
So this is the maze that will get become as a third argument that was extracted in the mapping or part.
So now we can simply head over to Salvador part and import this board port planner class and then call
the fine python display function.
So we do exactly that.
We import.
Bought porcelain glass from the bought bought planning file by writing import bar pot planner.
We had only worked with a solar class after we have created the object for bought mapper required the
object.
For Bought Planet.
And then rewrite.
What?
Portland an object.
And then we head on over to the main solving function here.
After we perform the mapping process or the mapping stage.
We now call the port plan a function of fine ports.
And the split of this takes in four arguments.
The first being the graph that was extracted in the mapping stage.
So we pass in the graph by writing self dot board member dot graph.
Da da.
So this is the graph that becomes the first argument for this function.
Then we need to provide the start and end point are basically the entry and exit point of the miss.
So start point just initialize to self.
But bought matter not drop not stuck in the same way we we we initialize the end point.
For our partner that glass and that is theft or bought.
My partner dropped or dead.
And the last thing that is left for us to do is to simply describe the mess.
The mist will get initialized to surf dot board mapper.
Not me.
So the mess that we have just initialized earlier in the bot mapping class to 10:00.
So these are the four arguments that become the inputs to find path and display.
And this will simply get us all possible paths from the main entry to the main exit.
And once it finds all those possible paths, it will display one part to the user so that we could validate
whether those phone paths were correct or not.
Now we can simply head on over to a terminal where I've already started the simulation.
Run the miss solver after building it.
Once I build this, I run the missile over.
And you will see after the process completes, we have the maze occupancy grid dressing space for.
Gives us the interest points and the connected note that was output or the mapping process.
Then pressing spacebar again.
We will get the phone back from the DFS.
So here you have simply displayed the phone card from the DFS that leads from the maze entry to the
maze exit and is shown in the form of beautiful colors.
So this has been relative to twice now that the DFS is indeed working correctly and finding the bot
from the maze entry to the maze exit.
So now we can head on over to using DFS to find the shortest path to the go from the maze entry to the
maze exit building.
Thank you.
And.
But.