So tell me about a project that you worked on. >> Sure let me tell you about some code we developed for part of the third course in the specialization. >> Okay. >> So the project in that course is we want the learners to take some map data. So some data and street data in the world. So let's say we have some streets that look like this. There's a street here and maybe there's this curvy street right there and another street running here, maybe another street running there. And the goal for the learners is that they want to find intersections in this map, or take intersections in this map and then plot directions from one point to another. So basically what they need to work with is these intersection points and connections between them. But this map data, as you can probably imagine, is real world and it's extremely complex. So there's a lot more than just these intersection points in this data. In fact, in addition to these intersection points, you actually get all these other little points along each of these lines. So you've got all these yellow points here and ditto for all the other lines here. >> So those dots trace the shape of the road. >> Exactly, so these dots are necessary so that we can trace the shape of the road. But in terms of finding routes, direction planning, they're not really important, right? >> Right. >> Because the only time you have a choice is at an intersection. >> Right. >> So we could do some route planning on the full set of data here, but the problem is that the graph that the users would have to work with, the learners would work with, it would be very, very large. So that would be kind of a problem. So we wanted to be able to prune out all these yellow dots here so that the learners didn't have to include them in their graph and allow the learners to work just with these intersection points and the connections between them. So, that was the technical problem that we had to deal with. So, how did we deal with it? [LAUGH] That's a good question. So what we did was we first considered all of the data. This is the data that comes back to us from the full map flaps. And what we did was we represented all of the data you see here, all the points in pink and in yellow, as a graph. So these are points in our graph, a full graph, and there are edges between each of the points that are connected by a road segment. Each of the row segments also has some meta information so not just these points but also like the name of the road, the type of the road and so on and so forth. And again, our goal was to identify the pink points and discard all the yellow points. >> And were the pink points distinguished in the graph? >> No, they weren't. >> That's a good question so we had to figure out how to identify the pink points and then take only those. And create a graph where the pink points themselves are connected. So the way we did that was we had to define what is exactly an intersection? How would we identify an intersection given this graph structure? And after a lot of thought, we went back and forth. How does an intersection look? Roads coming in, roads going out. What we realized was that it was easier to identify what an intersection isn't. So in other words, these points in here, you can see those aren't intersections because there's just a single road that passes right through them. Now to make this slightly more complicated we have both one way streets and two way streets. So there are a couple different scenarios where we look at a point in the graph and determine that it's not an intersection. And here's what these look like. So on the one hand we have this situation where we have a point. This could be pink or yellow. And a road coming in and a road going out. And this road has the same name, say this is Main street. So this is represent a one-way street going through this point. And in this situation, this node right here, that's not an intersection so we can rule that out. >> So it will be yellow. >> Exactly, that's a yellow point and we can ignore it. >> Okay. >> The other situation where we don't have an intersection is just the two-way street version of this. So we have a road passing through in this direction but it's a two-way street. We have edges in both directions. All of these road segments have the same name. This is also not an intersection. If either of those conditions is not true, then we know that we're dealing with an intersection and we should consider it a pink point. So that's what we did. There are some little detailed complexities here like, how do we represent this graph so that it's easy to find the nodes that are just coming in and the edges going out? So we couldn't just use a straight up adjacency matrix going out. We had to be able to find the incoming nodes as well. So that was made a little bit more complex. But once we identified the inner sections, the pink points, using this algorithm. So anything that didn't look like this Is considered an intersection. We grab those points out as nodes in the graph that we wanted to give to our learners. So, there'd also be points down here, these dead ends, so on and so forth. Next, we had and that's if the roads ended here, they continue, there be more intersection over there. The next thing we had to do was connect them. >> Yeah. >> Well, that actually turned out to be pretty straightforward. It was just a depth for search out of each of these intersection notes through the graph to the closest neighbor. So just a one hop, essentially one intersection hop for search. So we would start right here and we would then trace out through these yellow points which we could easily do with our graphic presentation until we reached another intersection. >> Right. >> And then we say, okay, these two are connected with an edge. We come back here and we go in a different direction. So we had to mark these as visited so we didn't repeat that path. We connect these two, we connect these two, and so on and so forth. So that's how we took all these very complex dense data and turn it into a much more reasonable sparse representation for our learners. >> That's great, thank you. >> Sure.
