1 00:00:00,150 --> 00:00:09,180 OK, so in this video today, we are going to go over the solution to the project. 2 00:00:09,540 --> 00:00:16,560 One of the solutions, of course, you could have implemented a different solution, which is totally 3 00:00:16,560 --> 00:00:18,030 fine and actually expected. 4 00:00:18,450 --> 00:00:24,960 It would be strange to have the exact same solution, but I just wanted to go over some things in case 5 00:00:24,960 --> 00:00:26,300 some people hit some walls. 6 00:00:26,310 --> 00:00:32,310 I'm not going to be starting from scratch and coding every single character in line in front of you 7 00:00:32,910 --> 00:00:33,380 here. 8 00:00:33,390 --> 00:00:40,470 But I've already written the code and I will include a GitHub link to it, as well as some expected 9 00:00:40,890 --> 00:00:47,070 output like an example of the expected output because topological thought could have different outputs 10 00:00:47,070 --> 00:00:50,100 as long as the ordering are appropriate. 11 00:00:50,790 --> 00:00:53,460 And in that topological topological order. 12 00:00:54,000 --> 00:00:57,030 So let's go ahead and get started. 13 00:00:57,030 --> 00:01:02,790 Since I put the headers in the project description, I'm not going to refer to the headers a whole lot. 14 00:01:03,600 --> 00:01:10,410 Just kind of the implementations of main course, start CBP and of course, plan ACP. 15 00:01:11,040 --> 00:01:15,240 And of course, maybe the list, of course, list that Jason here. 16 00:01:16,280 --> 00:01:18,020 So here in my course. 17 00:01:19,300 --> 00:01:21,010 Class I have. 18 00:01:22,000 --> 00:01:27,520 The island you see in line five I am doing using Jason. 19 00:01:27,940 --> 00:01:33,270 You don't have to include this everywhere, I might have some redundancies in my code that I left here. 20 00:01:33,280 --> 00:01:33,970 You seen this. 21 00:01:34,630 --> 00:01:35,440 So apologies. 22 00:01:36,670 --> 00:01:44,320 If I have that, but I kind of just smacked it everywhere, and if you are having problems with Jason, 23 00:01:44,320 --> 00:01:51,760 you know, some errors with C++ not recognizing the JSON, these JSON functions are available and Jason 24 00:01:51,760 --> 00:01:56,830 object, you might want to make sure you're including this line. 25 00:01:57,280 --> 00:02:04,510 And also that you have this Jason, that HP header in your project folder, your project directory. 26 00:02:06,550 --> 00:02:10,520 So continuing on, I have my constructor for course here. 27 00:02:10,540 --> 00:02:19,180 It takes a JSON object as an argument coming from the JSON object is the JSON object of the library, 28 00:02:19,840 --> 00:02:27,280 and I'm using an initialization list format here where I am initializing each one of my course data 29 00:02:27,280 --> 00:02:36,200 members to the corresponding the corresponding value from the JSON course object. 30 00:02:36,220 --> 00:02:36,670 So. 31 00:02:37,830 --> 00:02:45,050 Here you notice, for example, it's head over here we have instructor, for example, right here instructors, 32 00:02:45,060 --> 00:02:50,850 one of our attribute keys, which will if we index it with the object. 33 00:02:51,480 --> 00:02:54,090 This is a JSON course object. 34 00:02:55,620 --> 00:03:01,530 From here to here, and if we are doing the object and then index the instructor, it will give us this. 35 00:03:01,980 --> 00:03:03,480 And so therefore. 36 00:03:05,750 --> 00:03:14,390 You know, that name would be getting initialized for our instructor data member here and so on and 37 00:03:14,390 --> 00:03:22,490 so forth, doing the creating the other necessary parts of our object here in initializing them. 38 00:03:23,150 --> 00:03:24,800 So of course, it's tidal. 39 00:03:25,250 --> 00:03:31,310 And then you notice that inside of the constructor here, after this initialization list part, I am 40 00:03:31,310 --> 00:03:37,940 doing a loop because the prerequisites are a JSON array and. 41 00:03:39,100 --> 00:03:47,920 I need to then go through all of those items in the array and push it back to my pre-requisites string 42 00:03:47,920 --> 00:03:48,490 vector. 43 00:03:50,860 --> 00:03:56,710 So that's a constructor, and then the rest of these are just setter getter functions for all of our 44 00:03:56,710 --> 00:04:00,340 data members, including the vector here. 45 00:04:01,510 --> 00:04:07,330 So that is all I really did for the representation of our course abstract data type. 46 00:04:07,690 --> 00:04:09,220 Let's head over to course plan. 47 00:04:11,060 --> 00:04:12,770 So the course plan. 48 00:04:13,710 --> 00:04:14,130 A lot. 49 00:04:14,190 --> 00:04:21,450 Pretty much everything is driven by the constructor and that since I did it that way in Maine, I only 50 00:04:21,450 --> 00:04:29,130 really make a course plan object pointer and use the new keyword, so it's dynamically allocated. 51 00:04:31,190 --> 00:04:37,310 And I pass it the command line argument, which will be this file here, which I set up in and IT configurations 52 00:04:37,310 --> 00:04:37,760 already. 53 00:04:39,260 --> 00:04:46,160 And so we receive that file we initialize our stream is a data member, so we're going to set up that 54 00:04:46,160 --> 00:04:49,940 stream with this input file that is now a string after this line. 55 00:04:50,900 --> 00:04:57,590 We create a new JSON object, and we read into that JSON object from our file. 56 00:04:59,230 --> 00:05:08,530 So you notice that right here we're going through and we're looking through all of the courses of that 57 00:05:08,530 --> 00:05:13,510 Jason object, as this whole file is basically a giant JSON object. 58 00:05:14,600 --> 00:05:22,100 And so when we do this whole object and we index courses, it gives us this Jason array of all these 59 00:05:22,100 --> 00:05:23,330 course objects here. 60 00:05:25,210 --> 00:05:28,270 So each elm in that loop is one of these. 61 00:05:30,270 --> 00:05:38,430 So we're going through and creating a dynamically allocated new course object. 62 00:05:39,640 --> 00:05:40,960 And passing. 63 00:05:41,990 --> 00:05:49,910 The JSON object in and you notice that's what we are doing here is we get that Jason object and said 64 00:05:49,910 --> 00:05:50,330 all these. 65 00:05:52,280 --> 00:05:59,030 Then I have my pre-match beans map, which is just the steel map type, and what I do here is I'm just 66 00:05:59,030 --> 00:06:04,130 creating something that I can look up a course. 67 00:06:04,130 --> 00:06:04,430 I'd. 68 00:06:05,710 --> 00:06:11,410 And it'll give me the corresponding course object, this is just how it will be useful later on when 69 00:06:11,410 --> 00:06:13,270 we're creating our graph and everything. 70 00:06:15,890 --> 00:06:21,020 And then I create a new vector, you could probably just do that here and make it one line, but I just 71 00:06:21,020 --> 00:06:24,230 did it here and it's a vector, of course, pointers. 72 00:06:25,340 --> 00:06:28,970 And so our adjacency list will be our graph. 73 00:06:30,250 --> 00:06:39,070 So what we're doing here is just making a key, which is the corseted string and all of its neighbors 74 00:06:39,070 --> 00:06:45,160 will be stored in this vector, which is just this is just adding an empty vector as each one is. 75 00:06:45,160 --> 00:06:50,110 The neighbor lists for the adjacency list when I call create graph. 76 00:06:50,710 --> 00:06:52,810 It goes into this function. 77 00:06:53,110 --> 00:07:03,130 And for each course and pre mappings, add the course as a neighbor to each of its prerequisite courses. 78 00:07:03,160 --> 00:07:07,480 So this is one of the things I was talking about where you need to think about what it means to be a 79 00:07:07,480 --> 00:07:08,290 prerequisite. 80 00:07:08,740 --> 00:07:14,980 The graph basically needs to have directionality, like coming from those dependency nodes. 81 00:07:14,980 --> 00:07:23,080 So if you have a node that has, if you have a node that is a dependency for another node, then you're 82 00:07:23,080 --> 00:07:25,150 basically going from that. 83 00:07:25,150 --> 00:07:30,280 You'll be having an arrow from that dependency node to the node that it's dependent on. 84 00:07:30,280 --> 00:07:32,680 So the prerequisites are kind of the opposite. 85 00:07:33,130 --> 00:07:37,630 You know, the pre the prerequisites were mapped to each object. 86 00:07:37,640 --> 00:07:40,240 That's like, what are the things that it's dependent on? 87 00:07:40,480 --> 00:07:46,900 When we create the graph, we actually want to say what dependency? 88 00:07:47,440 --> 00:07:54,260 What courses do these given dependencies fulfill? 89 00:07:54,580 --> 00:07:57,490 So you're going from like the dependent. 90 00:07:59,090 --> 00:08:08,150 From the DEP., the prerequisite to the node that has that dependency as a requirement, a prerequisite. 91 00:08:08,330 --> 00:08:12,200 So it's kind of the other way around like that's how we want to build our graph as we want. 92 00:08:12,290 --> 00:08:18,770 We don't want to be able to visit a node without us first visiting the nodes that are the prerequisites. 93 00:08:19,580 --> 00:08:24,170 So for that reason, I build this loop right here. 94 00:08:24,380 --> 00:08:28,500 So you notice that I'm going over each element in the pre mappings. 95 00:08:29,090 --> 00:08:40,550 And if the elements so DOT first is basically the key string for the course ID Elhamed second gives 96 00:08:40,550 --> 00:08:41,870 us that. 97 00:08:45,020 --> 00:08:48,010 Course, the course object. 98 00:08:48,430 --> 00:08:55,420 So what we are doing is we're referencing the actual corf course object of each one in the map. 99 00:08:55,780 --> 00:09:01,870 And then we are calling upon this pre-requisites function, which gives us all the prerequisite, the 100 00:09:01,870 --> 00:09:03,610 list of prerequisites for that course. 101 00:09:03,910 --> 00:09:10,450 And as long as it's not an empty vector for the prerequisites, then we loop through each item in that 102 00:09:10,450 --> 00:09:10,960 vector. 103 00:09:13,120 --> 00:09:21,580 And what we are doing is we're actually know we're looping through, yeah, all of the prerequisites 104 00:09:21,580 --> 00:09:28,000 and for each one of those we are creating, are you pushing it back as a neighbor? 105 00:09:28,660 --> 00:09:30,430 Here we push it back as a neighbor. 106 00:09:30,520 --> 00:09:32,440 The actual course object. 107 00:09:33,160 --> 00:09:36,670 And then we use the key of the item. 108 00:09:36,670 --> 00:09:37,090 So. 109 00:09:40,560 --> 00:09:45,570 That is how we are setting up our graph there. 110 00:09:45,600 --> 00:09:52,860 So getting the graph set up correctly, building our adjacency list, that's what this function is for. 111 00:09:56,310 --> 00:10:03,450 OK, then once the graph is set up correctly, we call the TOPO sort, which is our topological sort. 112 00:10:04,580 --> 00:10:10,910 And kind of like it talked about in the lecture, this is, you know, fairly simple addition. 113 00:10:10,920 --> 00:10:14,300 This is a fairly simple modification to our existing debt for research. 114 00:10:14,300 --> 00:10:21,440 As you'll see, we basically just loop over each element in the adjacency list, which is an ordered 115 00:10:21,440 --> 00:10:21,710 map. 116 00:10:22,580 --> 00:10:28,430 And you remember that the first is the key, which is a string, it's the course ID, the second is 117 00:10:28,430 --> 00:10:29,480 the list of neighbors. 118 00:10:29,990 --> 00:10:37,790 So what we are doing is we're just passing the first, which is a way to identify our course for a given 119 00:10:38,030 --> 00:10:38,590 vertex. 120 00:10:39,740 --> 00:10:44,210 So if it's not visited, then we're going to pass it to our death for a search function. 121 00:10:45,470 --> 00:10:49,880 We come in our death for a search function, and this is literally what you've already done before all 122 00:10:49,880 --> 00:10:50,690 of this right here. 123 00:10:50,720 --> 00:10:57,170 The only different thing is that we're saying here we have the course to the front of the queue during 124 00:10:57,170 --> 00:10:58,340 the recursive phase. 125 00:10:58,340 --> 00:11:03,620 So when we're popping off the stack, so that is how we topological sort, it's doing it, adding it 126 00:11:03,620 --> 00:11:05,870 in the reverse order because we're doing push front. 127 00:11:06,050 --> 00:11:11,960 That's I used a deck, a double and Q, you might have used another data structure if you figure something 128 00:11:11,960 --> 00:11:12,440 else out. 129 00:11:13,450 --> 00:11:18,510 But we are adding here is the actual course we have that pre-match beans, which was nice. 130 00:11:18,520 --> 00:11:24,130 It was a way for us to just reference the course side string and it would give us back the course. 131 00:11:24,400 --> 00:11:28,900 And so here we can create a topological order in with the actual courses. 132 00:11:31,400 --> 00:11:36,920 So that is our death research and topological sort, once we're done with that, our plan is created 133 00:11:36,920 --> 00:11:37,520 actually. 134 00:11:37,520 --> 00:11:44,540 So our our our plan deck is populated with everything it needs in the correct order. 135 00:11:44,930 --> 00:11:48,530 And so what we do is all we have left to do is really print it out. 136 00:11:48,530 --> 00:11:49,520 So I used. 137 00:11:51,020 --> 00:11:53,420 An overloaded output operator. 138 00:11:53,780 --> 00:11:55,100 So if we look in Maine. 139 00:11:57,190 --> 00:12:01,930 I created this just this object, and all I really do is when you create this object, the constructor 140 00:12:01,930 --> 00:12:03,160 already did everything for us. 141 00:12:03,160 --> 00:12:04,470 It created the course plant. 142 00:12:05,470 --> 00:12:10,480 So all that's left to do is output the course plan. 143 00:12:11,360 --> 00:12:19,400 And since I overloaded this, we're sending a pointer, this is a cosplaying pointer, so we need to 144 00:12:19,400 --> 00:12:22,650 have that represented here in our alpha. 145 00:12:22,740 --> 00:12:28,730 Operator You see, we pass a course when pointers and argument and then we're just looping through the 146 00:12:28,730 --> 00:12:32,270 course plan, which is our deck for that given object. 147 00:12:33,170 --> 00:12:39,230 We update the order so we can have like one two three four all the way up to the last of the courses. 148 00:12:39,230 --> 00:12:40,760 And then we're just. 149 00:12:42,280 --> 00:12:47,950 Printing out the relevant data, members of the you know, the appropriate data members of the course 150 00:12:47,950 --> 00:12:55,230 object so we can print out the information about the course and they will all be in the correct ideological 151 00:12:55,240 --> 00:12:55,600 order. 152 00:12:55,630 --> 00:12:59,670 You must also return out for the alpha operator. 153 00:12:59,890 --> 00:13:02,080 You notice I have this comment in our print function. 154 00:13:02,470 --> 00:13:04,820 This is fully valid as well, too, if you didn't want it. 155 00:13:04,840 --> 00:13:08,590 This isn't necessary to overload the alpha operator if you don't want to. 156 00:13:10,090 --> 00:13:14,860 You can just make a print specific print function to print out your plan. 157 00:13:14,860 --> 00:13:17,990 So this is that as well, if you did that as totally fine. 158 00:13:18,010 --> 00:13:23,620 It's pretty much the same same thing and unit is here instead and main you would have just in this line 159 00:13:23,620 --> 00:13:24,640 instead of this line. 160 00:13:25,210 --> 00:13:28,210 So, you know, CP Arrow print the course. 161 00:13:29,820 --> 00:13:36,530 OK, so and then, you know, of course, everything that uses the new keyword, we have to delete. 162 00:13:36,540 --> 00:13:42,930 So I just kind of used, you know, we looped over the objects in our pre mapping, which if we look 163 00:13:42,930 --> 00:13:46,650 right here, we use new to create a new object to put new course here. 164 00:13:47,220 --> 00:13:53,070 And then when we made our graph, we were referencing these objects I just went through and looped through 165 00:13:53,070 --> 00:13:57,150 and deleted those objects here in the destructor. 166 00:13:57,150 --> 00:14:00,180 So you will need to do that as well. 167 00:14:01,470 --> 00:14:07,620 And in Maine, of course, we're deleting this object here that we created the new keyword. 168 00:14:08,640 --> 00:14:15,450 So let's go ahead and just run this, and we will get a specific, unique ordering. 169 00:14:17,050 --> 00:14:21,520 Of these, this might be kind of small for you if you can read it, I increase the text size for the 170 00:14:21,520 --> 00:14:26,650 code, but my people, yeah, you can increase this to cool. 171 00:14:27,740 --> 00:14:30,580 So hopefully this is big enough for you to read. 172 00:14:30,730 --> 00:14:32,800 This is just in ordering. 173 00:14:32,810 --> 00:14:37,180 You might have the same ordering or you might have a different ordering if you arrange things differently 174 00:14:37,180 --> 00:14:37,930 in your project. 175 00:14:39,010 --> 00:14:42,280 But it should print out like this and I will. 176 00:14:43,450 --> 00:14:50,260 Paste this on the kind of where I put the GitHub link as well, so you can reference it, but you should 177 00:14:50,260 --> 00:14:57,460 also draw the graph like I was talking about kind of how the graph should be properly created with the 178 00:14:57,460 --> 00:14:58,360 prerequisites. 179 00:14:58,390 --> 00:15:00,820 And that way, you can trace it. 180 00:15:00,820 --> 00:15:05,950 And when you get your topological order and you can see how it works by following the path on your on 181 00:15:05,950 --> 00:15:06,370 your graph. 182 00:15:07,790 --> 00:15:10,230 So, yeah, here's an ordering. 183 00:15:10,300 --> 00:15:17,990 And with that, I think that we have gone over pretty much everything you need, of course, if you 184 00:15:17,990 --> 00:15:27,650 need to look over the code, I will provide, but I hope you enjoyed this project and can see the applications 185 00:15:27,650 --> 00:15:28,880 of top logical sort. 186 00:15:29,270 --> 00:15:31,260 And with that, I will see you in the next election.