[MUSIC] In this video, I'm going to be talking through what we're looking for in your project this week. So at the high level, the two things we're looking for is, for you to spend a minute to two minutes talking about the problem that you're trying to solve, and then about three minutes talking about some hard component of your project, whether that be a design choice you made in terms of your classes or some piece that you struggle with the algorithms. Now, I do recommend you do read the full project description, but I'm just going to give you an example here. All right, so here we go. So the problem that I was trying to solve in my project this week was, I was trying to solve the same one that Mia explained, which was trying to find communities in social network. And the idea for this is let's say, I have this social network here and as humans, it's pretty easy for us to see really quickly that this is kind of a community, this is more of a community, and this is more of a community. Than across those communities, right? And the question is how can we algorithmically figure that out. And the way we might be able to that is actually, the way I like to think about it, is thinking about neighborhoods in a city. So within small residential neighborhoods, you actually have a lot of connections, lot of different ways to get from one place to another. It's really easy to get from say here to here from here to here and there's multiple paths to really do that. But when you try to go between neighborhoods, there are only a few arterial roads that allow you to do that. And the way we can figure out which there arterials are, is by doing essentially the shortest path between all possible pairings of nodes. And let me just do a couple of these here, and then we'll see what this is doing for us. So let's say, I want to start here and I want to go all the way over here. My shortest path is going to be essentially this. Right. Another option would be let's say, I want to get from here to here. Well, I'm going to take this path. If I want to go from here to here. I'm going to go this path. Either the more times we do this, the more we're seeing that these two edges are essentially on the critical path for tons of these different shores paths. And these are essentially are arterials. Now we can use this algorithm for a lot of different ways. Where we could use this to figure out what the arterials are in a major city to see, in terms of traffic conditions what could be bad about having just one road between neighborhoods. We could also see for a large computer network that this is the core edge, and if we lose connection between these, we're actually going to lose connections across the network. So it's lots of different things we can do here, but I use it in this project to figure out these communities. And essentially by cutting out these two edges, because they're so commonly used and the shortest paths, I can now identify that these are committees. All right, so that was a problem I was trying to solve. What I was doing with the graph project is, I had a whole bunch of different algorithms I was employing, I was doing search. I was doing the algorithms for this. I just had a whole bunch of different things I was playing with with my graph. Each of those algorithms had another feature that needed to keep track of, from the avertasis to the etnas. We will just focus on the. Very early on, if you do like a search or something like that you will very quickly say, I want a visited variable before I. Fairly early on depending on the algorithm you're doing, you realize you want a distance to keep track of how you got there. Or a distance to know the best distance you've seen so far to get to this node. You also then realize well I might want a vertex parent to know how I got here. My shortest path. And this just kept getting bigger and bigger, and I had a few more variables here but it's not worth writing them all out. And what I realized was my vertex class had become really unmanageable. It had all this information which was really metadata about algorithms, that the algorithms were using. And really didn't have anything to do with a vertex class. So what I ended up thinking about was, could I divide out the information that I'm storing for vertices, stuff that actually matters for the vertex, from the stuff that I'm just keeping track of when I'm doing my algorithms? I had some ideas for that. My first idea was to essentially, whenever I have a vertice and I have a vertex object. Each of my vertex objects, I'll also keep a parallel array or parallel list of metadata objects. And I got rid of that idea pretty quickly. I realized it was going to be really hard to manage these parallel arrays all the time. So I scratched that idea and I said, well, maybe I should just pair these. I should make a larger class, like vertex wrapper or something that stored the vertex and everything actually that matters to vertices. And then, also stored the metadata for all of my various algorithms. I liked this idea in terms of continue to work my code. But then, I ran into problems with the, in the sense that is this going to be bad. Because I'm storing all the same information I was storing before. Yeah, I'm putting them somewhere else. But it's still a whole bunch of extra data I'm storing and I'm keeping around all the time, whether or not I'm using an algorithm or not. So I ended up doing what felt like a heavyweight solution. But I am actually really happy that I did it. What I ended up doing was I had my own class, which I called Algorithm Data. And this was an interface. And I'm sorry, it was actually an abstract class. And what I did was, I just then had derived classes of like, breath first search AlgData. And I had this for all my different algorithms, and then inside of those is where I actually kept Visited Distance, things like that. So it took a while, actually, to refactor my code to have this now just have a single algorithm data object, which got initialized and used whenever I was using one of my algorithms, but I'm really happy I did it. Because when it was all said and done, my algorithms got a lot cleaner, my vertex class got a lot cleaner. And now, when I want to add more algorithms to my class, it's going to be easy to do so. So again, I had a lot of fun with figuring out these different communities, and I had a lot of fun kind of making some tough design decisions working through my project.