OK, so in this video today, we are going to go over the solution to the project.
One of the solutions, of course, you could have implemented a different solution, which is totally
fine and actually expected.
It would be strange to have the exact same solution, but I just wanted to go over some things in case
some people hit some walls.
I'm not going to be starting from scratch and coding every single character in line in front of you
here.
But I've already written the code and I will include a GitHub link to it, as well as some expected
output like an example of the expected output because topological thought could have different outputs
as long as the ordering are appropriate.
And in that topological topological order.
So let's go ahead and get started.
Since I put the headers in the project description, I'm not going to refer to the headers a whole lot.
Just kind of the implementations of main course, start CBP and of course, plan ACP.
And of course, maybe the list, of course, list that Jason here.
So here in my course.
Class I have.
The island you see in line five I am doing using Jason.
You don't have to include this everywhere, I might have some redundancies in my code that I left here.
You seen this.
So apologies.
If I have that, but I kind of just smacked it everywhere, and if you are having problems with Jason,
you know, some errors with C++ not recognizing the JSON, these JSON functions are available and Jason
object, you might want to make sure you're including this line.
And also that you have this Jason, that HP header in your project folder, your project directory.
So continuing on, I have my constructor for course here.
It takes a JSON object as an argument coming from the JSON object is the JSON object of the library,
and I'm using an initialization list format here where I am initializing each one of my course data
members to the corresponding the corresponding value from the JSON course object.
So.
Here you notice, for example, it's head over here we have instructor, for example, right here instructors,
one of our attribute keys, which will if we index it with the object.
This is a JSON course object.
From here to here, and if we are doing the object and then index the instructor, it will give us this.
And so therefore.
You know, that name would be getting initialized for our instructor data member here and so on and
so forth, doing the creating the other necessary parts of our object here in initializing them.
So of course, it's tidal.
And then you notice that inside of the constructor here, after this initialization list part, I am
doing a loop because the prerequisites are a JSON array and.
I need to then go through all of those items in the array and push it back to my pre-requisites string
vector.
So that's a constructor, and then the rest of these are just setter getter functions for all of our
data members, including the vector here.
So that is all I really did for the representation of our course abstract data type.
Let's head over to course plan.
So the course plan.
A lot.
Pretty much everything is driven by the constructor and that since I did it that way in Maine, I only
really make a course plan object pointer and use the new keyword, so it's dynamically allocated.
And I pass it the command line argument, which will be this file here, which I set up in and IT configurations
already.
And so we receive that file we initialize our stream is a data member, so we're going to set up that
stream with this input file that is now a string after this line.
We create a new JSON object, and we read into that JSON object from our file.
So you notice that right here we're going through and we're looking through all of the courses of that
Jason object, as this whole file is basically a giant JSON object.
And so when we do this whole object and we index courses, it gives us this Jason array of all these
course objects here.
So each elm in that loop is one of these.
So we're going through and creating a dynamically allocated new course object.
And passing.
The JSON object in and you notice that's what we are doing here is we get that Jason object and said
all these.
Then I have my pre-match beans map, which is just the steel map type, and what I do here is I'm just
creating something that I can look up a course.
I'd.
And it'll give me the corresponding course object, this is just how it will be useful later on when
we're creating our graph and everything.
And then I create a new vector, you could probably just do that here and make it one line, but I just
did it here and it's a vector, of course, pointers.
And so our adjacency list will be our graph.
So what we're doing here is just making a key, which is the corseted string and all of its neighbors
will be stored in this vector, which is just this is just adding an empty vector as each one is.
The neighbor lists for the adjacency list when I call create graph.
It goes into this function.
And for each course and pre mappings, add the course as a neighbor to each of its prerequisite courses.
So this is one of the things I was talking about where you need to think about what it means to be a
prerequisite.
The graph basically needs to have directionality, like coming from those dependency nodes.
So if you have a node that has, if you have a node that is a dependency for another node, then you're
basically going from that.
You'll be having an arrow from that dependency node to the node that it's dependent on.
So the prerequisites are kind of the opposite.
You know, the pre the prerequisites were mapped to each object.
That's like, what are the things that it's dependent on?
When we create the graph, we actually want to say what dependency?
What courses do these given dependencies fulfill?
So you're going from like the dependent.
From the DEP., the prerequisite to the node that has that dependency as a requirement, a prerequisite.
So it's kind of the other way around like that's how we want to build our graph as we want.
We don't want to be able to visit a node without us first visiting the nodes that are the prerequisites.
So for that reason, I build this loop right here.
So you notice that I'm going over each element in the pre mappings.
And if the elements so DOT first is basically the key string for the course ID Elhamed second gives
us that.
Course, the course object.
So what we are doing is we're referencing the actual corf course object of each one in the map.
And then we are calling upon this pre-requisites function, which gives us all the prerequisite, the
list of prerequisites for that course.
And as long as it's not an empty vector for the prerequisites, then we loop through each item in that
vector.
And what we are doing is we're actually know we're looping through, yeah, all of the prerequisites
and for each one of those we are creating, are you pushing it back as a neighbor?
Here we push it back as a neighbor.
The actual course object.
And then we use the key of the item.
So.
That is how we are setting up our graph there.
So getting the graph set up correctly, building our adjacency list, that's what this function is for.
OK, then once the graph is set up correctly, we call the TOPO sort, which is our topological sort.
And kind of like it talked about in the lecture, this is, you know, fairly simple addition.
This is a fairly simple modification to our existing debt for research.
As you'll see, we basically just loop over each element in the adjacency list, which is an ordered
map.
And you remember that the first is the key, which is a string, it's the course ID, the second is
the list of neighbors.
So what we are doing is we're just passing the first, which is a way to identify our course for a given
vertex.
So if it's not visited, then we're going to pass it to our death for a search function.
We come in our death for a search function, and this is literally what you've already done before all
of this right here.
The only different thing is that we're saying here we have the course to the front of the queue during
the recursive phase.
So when we're popping off the stack, so that is how we topological sort, it's doing it, adding it
in the reverse order because we're doing push front.
That's I used a deck, a double and Q, you might have used another data structure if you figure something
else out.
But we are adding here is the actual course we have that pre-match beans, which was nice.
It was a way for us to just reference the course side string and it would give us back the course.
And so here we can create a topological order in with the actual courses.
So that is our death research and topological sort, once we're done with that, our plan is created
actually.
So our our our plan deck is populated with everything it needs in the correct order.
And so what we do is all we have left to do is really print it out.
So I used.
An overloaded output operator.
So if we look in Maine.
I created this just this object, and all I really do is when you create this object, the constructor
already did everything for us.
It created the course plant.
So all that's left to do is output the course plan.
And since I overloaded this, we're sending a pointer, this is a cosplaying pointer, so we need to
have that represented here in our alpha.
Operator You see, we pass a course when pointers and argument and then we're just looping through the
course plan, which is our deck for that given object.
We update the order so we can have like one two three four all the way up to the last of the courses.
And then we're just.
Printing out the relevant data, members of the you know, the appropriate data members of the course
object so we can print out the information about the course and they will all be in the correct ideological
order.
You must also return out for the alpha operator.
You notice I have this comment in our print function.
This is fully valid as well, too, if you didn't want it.
This isn't necessary to overload the alpha operator if you don't want to.
You can just make a print specific print function to print out your plan.
So this is that as well, if you did that as totally fine.
It's pretty much the same same thing and unit is here instead and main you would have just in this line
instead of this line.
So, you know, CP Arrow print the course.
OK, so and then, you know, of course, everything that uses the new keyword, we have to delete.
So I just kind of used, you know, we looped over the objects in our pre mapping, which if we look
right here, we use new to create a new object to put new course here.
And then when we made our graph, we were referencing these objects I just went through and looped through
and deleted those objects here in the destructor.
So you will need to do that as well.
And in Maine, of course, we're deleting this object here that we created the new keyword.
So let's go ahead and just run this, and we will get a specific, unique ordering.
Of these, this might be kind of small for you if you can read it, I increase the text size for the
code, but my people, yeah, you can increase this to cool.
So hopefully this is big enough for you to read.
This is just in ordering.
You might have the same ordering or you might have a different ordering if you arrange things differently
in your project.
But it should print out like this and I will.
Paste this on the kind of where I put the GitHub link as well, so you can reference it, but you should
also draw the graph like I was talking about kind of how the graph should be properly created with the
prerequisites.
And that way, you can trace it.
And when you get your topological order and you can see how it works by following the path on your on
your graph.
So, yeah, here's an ordering.
And with that, I think that we have gone over pretty much everything you need, of course, if you
need to look over the code, I will provide, but I hope you enjoyed this project and can see the applications
of top logical sort.
And with that, I will see you in the next election.