Live Coding: Avoiding Traffic with Wolfram Language

Hello everyone. Thanks for joining. Today we're going to look at a case study. We're going to set out to solve a particular problem using code. In particular, we're going to use Wolfram language to avoid traffic. Let me set up the domain like a little bit more before we go on. So what we're going to try and do is find out how you would get around London in this case somehow like as anti socially as possible. We aren't necessarily trying to minimize our a transit time which is trying to minimize the sort of like the number of faces that we see and on our way. This will involve doing a few things. There's obviously many ways to set up this problem and then attack this problem. But what we're going to do is look at traffic cameras in order to count cars and there's going to be a little bit of image processing involved in that. And then after that we're going to build a graph of London using some more image processing and then we'll go on from there. It's for the rest. We'll see what happens as we go on. So without further ado, let's start. So here's the agenda. This is the introduction now. And then we'll break the question into two halves that we spoke about and then we'll start looking at the data that's available to us and talking about a little bit and wrangle in the sense that we'll have to clean it up a little bit and then we'll explore. We will go through this data and sort of see what we can see straight off the bat, like see what we can do straight away. And then after we're done exploring I guess we'll start exploiting and then we'll say goodbye. Please feel free to ask questions. The more questions the better. Cool. So I've basically, I've said this. We're going to do some image processing and a little bit of graph theory. A graph will kind of sneak up on us at some point. There's a second graph, right, so there's going to be a graph of London so that you have the junction in the roads, these are your dots and lines. But there'll be, we will do some matching at some point and it'll turn out that this is a mistake. One thing I want to say is that I think it says somewhere in the promotional material that this code is supposed to be sort of real world and hacky. I'm definitely not completely proud of all of the code that I've written today, but it seems to get the job done. And also I made at least one, some sort of, at least one modeling decision that wasn't. That turned out not to be great, but we'll fix it and go from there. Okay, so there's at least two questions. In order to answer the question how do you get around London whilst avoiding cars? We're going to answer at least these two questions. How do we, first of all, how do we get an impression of like how many cars there are at different points anyway? How do we get this? I mean, I'm in Oxford, you guys might be anywhere. How do we understand what cars are doing in London? And then secondly, how do we actually get a graph of London that will address both these questions? Okay, so the way I propose we count cards at the junction is by accessing a live feed of each junction. There are cameras at junctions for some of them you can just get a picture from a junction at this current time. So we have that picture and then we're going to use some kind of built in machine learning functionality in Mathematica to count cards in each frame. So this is where we start. This is a endpoint. It's given to us by Transport for London. And my first thought upon like, you know, so I say import this endpoint, like get the data that it's, you know, consume the data that's providing. I asked for it in JSON. So like the sort of structured format that we can look at. And immediately when I see this thing, I'm kind of a little bit stunned. It does not look like a kind of normal comprehensible like adjacent thing with keys and entries. It looks kind of strange. But the thing is it's also too big to sort of fit in a cell. So we're going to look at it piece by piece. I'm going to look at a random choice out of these endpoints. We can see that it's a list of some things and I can't tell what the things are. So I'll take a random one just to start figuring out where we're sat. But still when I look at this, it looks kind of strange. There's a lot that's going on. I get kind of dizzy. But if I squint right, this is what we're after. There's a.jpg that's good, that's a picture. We want a picture of this, of this place here. So how do we get in here? We have to sort of work outwards. There's a list. So if we look at the Keys of F. These are like, you know, the sort of top level. There's something called Additional Properties, which is where, where the JPEG is right, the JPEG is in Additional properties. So that's great. But Additional properties is a list. It's a list where we have associations with a bunch of stuff and then the key is part of the association rather than the left hand side or something. But anyway, we can see that we are looking for the association which has key set to image URL. That's what we're looking for. So first of all we want to make sure we want to. Because there's no guarantee that all of these places have a image associated with. So we have our endpoints, but we want endpoints with pictures with snapshots. So we're going to select from the endpoints, select from the endpoints, any of them where any of their additional properties has the key image URL. That's what's going on here. Good. Okay, so, so now we have, now we know that in each one of these endpoints there exists this thing of your image URL. Now we actually want to extract the, the, the image URL. So what do we do? This is we, we're creating like a, an anonymous function here that will, will kind of pull out the image URL. And we want to, you know, from each endpoint that looks like this, we want to go in the additional properties, take the first one, which should be the only one that has this, this image URL key, and then we're going to take the value. That's what's going on here. Look at the value of, you know, the, the selection from additional properties of image URL. The reason I use select first instead of select is because select will give you a list, but select first will give you the element. So it's just a little bit, a little bit neater. Cool. And then we'll start to build our associations, our data. What are we interested in? What do we need to know in order to start counting cars and solve this problem? We need the position of each camera. So if you look somewhere, we have the latitude and longitude. I guess is if we looked at the keys of F. We have the latitude and longitude that gives us opposition. So we, we take the latitude and longitude, we wrap it up in geoposition. This is like a wrapper that Mathematica has to deal with geographic positions. So that's good. And then we get the actual snapshot at this point. This is the URL. And then we want the name because this will help us later on, make like a, like a, like a little like a. An interface that we can use to sort of probe around and do stuff. Okay, good. So that's the rough structure of the thing that we're going to be working with. So we were careful to select only the, you know, the endpoints where there was an image associated with it. But that's not enough. It's not enough to have an image because some of these images we want to count as not really existing. Like, so if sometimes like a camera is offline for whatever reason, and then we get a frame that looks like this and we want to. Or we would like to get rid of frames that look like this. So how can we do that? Well, one thing we could do is to know that this frame is mostly the same color. It's like there's this exact shade of gray. And we're going to say that, okay, if the vast majority of the frame is this particular shade of gray, then then the median pixel value of this frame is also going to be that same shade of gray. And it's very deeply unlikely that some other image that is useful to us also has that exact gray as its median. So you can use that median as a reason to exclude a frame. So particularly, how do we get the median? There's this thing called image measurement. So measure in the frame, get the median, and then we get this, this very specific kind of gray. And now we can use. We. Now we can sort of create a function that will turn the image URL into the image itself. How does this work? Basically, we take the sort of association that we saw above, and then the first thing we do is try and import the. We say frame is, and we try and import the snapshot. Okay. And then we say, okay, if that thing that we imported is not an image, so it failed, the importing failed, or if it's median is this kind of gray here, that means we think it's not useful, then we return nothing. Otherwise we replace in that association, we replace the snapshot with the important frame. Something that I use quite often in Mathematica is this fact that nothing in a list that disappears. So if you have like a list and it's like A, B, C, D, nothing, capital N, and then E, that nothing goes away. So basically this frame, like it still returns something, but it effectively deletes the data points where there's no nice frame. So you can run that and over our data, that takes a little while. I prepared something earlier so it won't bother. In fact, let's actually look at sort of what we're looking at. There we go. Our URLs have turned into images, so that's good news. But how do we count the cars in each image? It's not easy. And to be completely honest, I wouldn't know how to solve this if I had to solve it somehow from first principles. But you don't need to. At least if you have Mathematica, because it has algorithms for this sort of thing, you create a function called count cause. And what it does is it finds the circle image bounding boxes in the frame of whatever it classes as an automobile, a car or a bus. Right? So we're counting all of the identified automobiles or buses in our frame. Someone is wondering why are some things blue and some things black in terms of the variables? So this is quite a useful thing in like the Mathematica front end. Basically, if it doesn't have a definition for something at the moment, right, it'll color it as blue, otherwise it's colored as black. So if I run this and define count cause, then count cause changes color to let us know that it has a definition. So this is quite useful for debugging because if you run a cell and then it gives you something strange that you didn't expect, it doesn't seem to have evaluated, but you see blue in that cell, then that's just because parts of your expression don't have definitions. And that's fine. It's fine to I need to find something like in mathematics, fine. Say something like Q to the O, for example. Even though I've not defined either of those two things, you can work with it symbolically. Q to the O is Q to the O, which is good and bad, right? It's good because you can do stuff like this. You can do maths in Mathematica. But it's bad because if I forgot to actually define count cause and then I started using it in Python or in C or in most languages, right? This would give you an error. And that's a good thing because you meant to find it. Probably. But anyway, it's just something to look out for. Okay, so where are we? We have a bunch of these things. We have a bunch of things that look like this. We have a position, position of the camera, a name. At the moment we have the picture of the camera, but we don't need that anymore. We'll get rid of it. And then we have a number of cars that it's counted. So that's enough already to build a sort of like traffic map of London. Just to sort of see like how things look in the map just as a kind of sanity check to see that our points are actually in London and you know, they are where we would expect traffic cameras to be. So it's also a good way to check that our accounting works because okay, like so you know, this, this spot is very red. If we look at it then there's a lot of cars there so it expect it to be very red. This spot is sort of very blue. Okay. So you know, it's good to check that there's no, there's no cars there. Something. Okay, this is like somewhere in the middle and you know, we can start to check and I will talk briefly about how this works, but someone has asked a question which, which is good. Simon asks is it too much of an oversimplified statement to purport the fact that the scope of this problem should be filtered and integral to the variable speed of the, of the medium object I a traveling car? So, so actually Simon, when I first set out to solve this what I thought would be a good idea, I didn't pursue it too much. So maybe this could be an exercise for yourself is you saw that we can find these image bounding boxes so we can actually bound where the car is in the frame. And even better if we go back to the very start, we looked at the jpeg, but you can see that there's also an MP4. So actually what, what, what, what would be a good. What, what could be a good idea is to look at these videos, not these images. Look at the bounding boxes per frame and then see how much they're moving and then use that as the thing that you're trying to minimize. This is why I was sort of careful to say at the start that what I will actually be minimizing in today in this, in this, in this presentation is simply just the number of faces you see. If you really, if you wanted to get to a quicker then what you're saying might be a good idea. Look at the video and maybe you don't care how many cars are there. You just care if the cars are moving or not. Right? How, how quickly can you get through this junction? That's something that, that's something that you could. It's not all we did. We. It's not that what we will do today we will just count cars and try and avoid them. Probably it correlates a lot the more cars there are right? There's, there's probably lower but what you're suggesting is. Is more sophisticated and more accurate, which is frightening. You also said it's oversimplified, but up until I didn't read that. Anyway. So how does this heatmapper work? Briefly? It's a, it's geographics. So it's, you know, geographical. It's a picture of some geography. And at the car we have these geomarkers. Geomarkers are like pins on Google Maps. You can see them, they just point to places. And so we're mapping this over our data and we're going to take the position. So each position, we'll color it according to the traffic that's there essentially. But we do some sort of logarithmic scaling because some, some like, we can see that some places are like very busy. In fact, a few places are very busy, but some places are basically empty. So, you know, if you have like a graph that looks like, You know, if you, if you have like a graph that looks like this, it's not actually like very useful, right? Because it's like you can't see anything and then suddenly it's gone past you. So, so in situations like that, it's pretty cool to. Look like a logarithmic scaling. So then you can see the nuance in the spectrum. Right. But we have a tracking map and I forgot to say we don't just have a geomarker. Right. We've tooltipped it with the snapshot. So when we mouse over we get the actual picture that gave us the, the, the traffic count. Okay. So we want to model motion around London. So what would be cool is to have like a graph of London. And it's confusing, right, because graph is used in multiple ways. What I want is a, just a, like an abstract model of, you know, the junctions in London and which junctions connect to where and stuff like this. Probably, I didn't check, but probably. And this, this, this also would have been this sort of simplified things quite a bit. This probably already exists on the Internet. Someone has already. I mean, it definitely exists on the Internet. Maybe it exists publicly. Someone has a, a graph of London where things tagged with the, you know, the, the, the latitude and longitude, et cetera. But I guess maybe we like a challenge. We'll try and do it ourselves. We. Let's. So first of all, we want to bound. We have these cameras, right, and we want to find the box that contains them. So that's what this geo range thing is here. Break it down a little bit. Counter data, all position. I'm saying, okay, counter Data. We have this data. Take all of them and for each one, take their position. So. So I don't want to spit them all out. I find it'll probably be fine. Yeah. So we're taking these and then what I really want is the stuff inside the latitude and longitude. So I'm going to say first over those things to get the latitude and longitude. And that's what's going on in this next cell. That's what's going on here. We've got latitude and longitudes and then transpose will be transposing a lot. This is basically. It's just like a transposing. If you're transposing a matrix, right, we have latitude, longitude, latitude, longitude, like in different lists. But what do we want is the range that bounds them. So we want the minimum latitude and the maximum latitude and we also want the minimum longitude and the maximum longitude. So if we have these latitude longitude pairs in a list, we transpose them, we get lots of latitudes and lots of longitudes and then we find the minimum max of the, you know, the latitude and longitude. So that gives us a range. That's what's going on there. Cool. And then we're going to get a picture of London. We just say geographics, give us a picture of London in particular, want a. The part of London that's like boxing our cameras. And we also want no street maps, no like no labels, no text. We want as plain an image as possible. Why? Because what we want to do is extract from this image the roads. So luckily, right, the roads have like the sort of same color. What we're going to do is like mask according to the presence of the color. And then we'll do some thresholding to like pull it out, right, to like threshold and pull out the. This kind of, you know, this web that we see here. And then we'll do some like, just a little bit of cleanup. So we have this image and we want the stuff that's colored like this. Say can you can. If you can't see my mouse, then maybe you can see that there's. The roads have the same color. How can we. How can you pick the same color? There's loads of ways you can access the pixels, right, and then tally them. But there's this function called dominant colors that has like. We'll do some like clustering as well. So you're not being completely strict about what do you mean by the same color. So if you ask for the dominant colors, then we can see that it picks them out. So there's this, like, sort of background, there's the blue of the Thames and so on. And then there's what we want, the color of the road. So I literally just copy and paste that into the next cell color detect London of this thing. So let's actually go bit by bit. So color detects of London. This is London, by the way. This picture, it's also a city, but in this slide is a picture. We want to detect that particular color. So we see that it's kind of. It's colored each pixel by its proximity to this color here. That's cool. And then we'll do this thing called morphological binaries, which is thresholding. Could have copied and pasted. So it's thresholding, but it's thresholding with the idea that there are connections. So threshold is kind of strict thresholding. You're saying, okay, if your pixel is at least as bright, then we round it up to 1, otherwise we floor it down to 0. But morphological binarizing is like, okay, there's like an object in the foreground that we're trying to extract, and maybe every now and then it dips below the threshold. But we want to be a little bit forgiving and we want to kind of like keep our neighbors, basically. Okay, so we're getting close, right? You just see there's like a bit of noise. There's like these things here which we might as well get rid of, although it probably would have been fine. So delete small components to get rid of the small components. All of these functions, by the way, I didn't mean to open it up, but this is good that it did. They have parameters, like, you can specify what you mean to be a threshold, right? You can specify a threshold. You can specify the size of what you consider to be a small component. But for now, this seems fine. Okay, so if we, like, squint at this picture, we can see it's looking pretty good, but it's a little bit broken and cracked in places. We want to kind of grow things a little bit. We could dilate them, but we're going to do this thing called closing by a disk matrix. Basically, if two things are close together, we'll sub them together. So once all that is done, then we have something that we will call close enough for what we're going to do. We have this thing, and now we want to make a graph out of it. Luckily, there's a function for that, so I didn't have to read too much. I just say morphological graph of roads and you may notice that the boxes here on the outside have different colors because they're talking about different things. Now, this is a picture. This is just an array of pixels, but this is a graph. This is a set of vertices and edges. You can see, like these vertices are the dots, these are the junctions. And then we have edges which connect the junctions that were connected here. Okay, so it's sort of an abstraction of London. You know, these edges are straight when some of the things are curved. But that's fine. What would we just want to know connection? We want to know if I'm at a junction, which other junctions can I get to? Sam is asking what allows us to calibrate our input, our sensors real time to improve accuracy of results. Would cloud coverage be considered extracted noise? So obviously I haven't considered this. If we look at the snapshots, I suppose what I would say is, luckily the things that we're trying to count cause they're quite big and, you know, the algorithm will do okay for, you know, it'll survive the noise of like cloud coverage and stuff like this. If you want to, again to be really sophisticated, then I suppose you could also consider your cloud coverage and stuff like this. But I think, I think and I hope for us today, the signal is a lot louder than the noise anyway. I suppose the noise that we counted most of all was like when we did our image processing here. And we can see that there's still some noise that have, like. So maybe we could have been a little bit more intelligent in our image processing here. There's still some things that are broken off when I look at it. At least the connections are still sort of maintained. That's fine. But yeah, thanks for the question. Anyway. So here's our graph. We've created our graph of London. But we have a problem, our first real problem that we need to surmount. How do we. How do we map? Okay, so there's two worlds basically that we have. We have the camera world and this is the world of like latitude and longitude. You know, these things have latitude and longitude and they exist somewhere in the world. We also have the graph world. These nodes don't have a latitude or a longitude. They have cartesian coordinates, right? They have like an X and Y coordinate, but they don't have a latitude, longitude. What we need to do is find out where the cameras live on this graph. Right. Which sounds like quite a simple problem. Maybe it is quite a simple problem and I've missed something, but it requires, I think, a little bit of thought at least a little teeny bit of thought. If anyone has an idea, they can say, and maybe it's a good idea. I don't know, you may have a better idea than what I had. That's completely possible. And anyway, he suggests that if you have one, there's no harm. So here's how I propose we solve this problem. And this is why, by the way, we calculated the. This is one reason why we calculated like an explicit geographic range, let's say, in our geographic range. And I don't actually know what the number is, this is probably wrong. But let's say there's 5 degrees of longitude across London. I think it's way smaller. But let's say it's 5 degrees of longitude and we have a camera that's 2 degrees along that range. So it's 2/5 of the way along that sort of the longitude probably. Then where it'll sit on Our graph is 2/5 along the way of the Cartesian range. Right. So that's what we're going to try and do. So first of all, what we're going to need to do is find like the coordinates of our vertices. We can do that quite straight. We just ask for what the graph embedding of that graph is. So I asked for the graph embedding of the graph and then I map reverse over it. Why do I do that? Actually, this tripped me up. And you may have just seen I was like using my hands the wrong direction when I was talking about longitude. For some reason in my head, I assumed that latitude because lateral was sideways. That's going to be your east to west. But it turns out it's the other way around. So I'm thinking sort of X Y in my head, but it actually should be Y X. So that's why I'm reversing the Cartesian exponents here. Okay, so this list is now where our vertices live in the graph that we just saw. And it's the Y X coordinates. So it's this high and then this much along and it's in the order of our vertices. Our vertices are ordered. We have a first, a second, a first vertex. I don't know what the ordering is, it won't matter. But they're ordered. And the first vertex exists here in this sort of range. Okay, second vertex exists here. Now again, we're going to want to sort of rectify this geographic and embedding range. So I'm going to do something similar than what we did before. We have Y X, Y X Y, X, Y, X. But I want Y, Y, Y, XX, X, X. And then I want the minimum maximum of the Y's and the X. So that's what the embedding range will do. And it'll give us a minimum and maximum Y or minimum maximum X. And then I'm going to create this function. It's called graph the latitude, longitude. It will take something like this and it'll spit out where it exists in the, in the geographic range though. So how does it work roughly? It looks like this. So we take, here we're going to apply this to Y and X, right? So this is going to be Y. And what we're first going to do is translate to sort of zero so, you know, Y. We're going to Translate all the Y's to 0 by like taking away the kind of the minimum here. Okay. And then we'll normalize by the actual width, in this case the height of our range. So instead of going from. So now instead of going from 0.5 to 675.5, we're going to go from 0 to 1. Okay, that's good because now we can just rescale by our geographic range and then we retranslate and the same for our X coordinate. That is what this function is doing. There may have been a simpler way to write this. This is like a. Because this is just like, you know, it's like translations and it's just translations and scaling. So you could do this with matrices. And in general with Mathematica, it's better to do this sort of thing with matrices because it's going to be more optimized. Like once you start doing things in bulk, it's like a matrix computation is better, but it's fine. We have a lot of data, so this will be okay. And it's also more readable. Navid asks a very question here. Are we optimizing one individual avoiding traffic or are we optimizing citywide traffic to avoid jams and backlogs? So two things what we're doing is we're being individualistic. We're trying to, for us, you and your car. We're trying to minimize the number of cars that you see. That's what we're trying to do. But another thing that's tangentially related is there's this theorem. There's this theorem in game theory. Essentially it's called the price of anarchy. Maybe you're remembering this wrong, but it's called. There's this thing called the price of anarchy, which is about some like, it's kind of like a traffic model. Like what are we looking at? It's a very simplified model where you're looking at traffic moving around a graph. And essentially the upshot of this theory, if I remember correctly, is that if everyone acts like completely self interestedly and they're trying to minimize their own transit route around the graph, or they're trying to optimize their own objective function, then of course this solution, it won't be globally optimal for everyone, but it's bounded. How much worse it can be is bounded I think is by 4/3. So if everyone is this is only tangentiality related, by the way. But I just kind of want to say it in the graph like this. If everyone is trying to minimize their own transit time, then things will be worse than if they were kind of like optimized globally. We could expect that, right? But it's not arbitrarily worse, it's at most 4/3 as worse in the aggregate. So you definitely want to Google what I'm saying because I might be remembering it wrong, but I think that's correct. I think it is called the price of anarchy in these things. Anyway, okay, so you know, we've done like some division and stuff and maybe I'm not like, you know, completely sure that I've done things correctly. So it's always good to check. So what's going on here? Translated embeddings is graph to lat longbedding. What does that mean? This is map apply. So I don't just want to map the function over the list, I want to apply the function over the list. Because there's a difference between say X of A and B and X of the list A and B. If we just mapped graph long over the embedding, these won't be filled out. So map apply. Instead of giving you in each coordinate this, it gives you this essentially it's just a bit of sugar. And then to check what I'm going to do is this thing, I'll turn the. So, so now in this thing, right, if we look at say random sample, random sample phone translating embeddings, then they should be. There should be geopositions, right? There should be geopositions. So let's have a look. That's right. This is the geoposition. The first geoposition is where the first vertex ends up in the geoworld. So we have those and then we're just going to draw them to make sure that things looked roughly correct. Right. The nodes in our graph are landing Roughly where we would expect the junctions to be, where the nodes have come from in the first place. And if we look, we see that we did a pretty good job. Actually, recently a friend has told me about this function called geograph plot, which we'll try out. I may butcher this. Okay. The geograph plot will. If we will plot a jat, as the name suggests, it'll plot a graph geographically. So we want to. We have this London graph, but we want to replace the vertices. So let's say because this London graph, its vertices are still. That they're not. They don't have the latitude and longitude associated with it yet. So let's say I think it's going to be like, well, I spell it wrong. Okay, that's the wrong. But I can just have complete. So what I want to replace is the vertex list of the graph. Right. I think. I want to replace them with the translated embeddings, something like this. I think that's okay. I want to say normal, I think. Okay, that looks a lot better. Okay, so this is also, I think, more evidence that we did. Okay, so far, right. This looks roughly like we have actually just built a. Not only we built a graph of London, but we know where the vertices are. This, this looks, you know, right to me. The sort of roads or where the roads roughly are and you know, the vertices are roughly where the junctions are. And so far I think we can, we can pat ourselves on the back. Let me explain though, what just happened. So, association thread, if you give it two lists of the same dimensions. So we can actually just do a little example. If you give it two lists of like the same dimensions. So let's say A, B and 1, 2 is going to give you an association where A is pointing to 1 and B is pointing to 2. So we're saying the first vertex goes to the first geo position that we calculated and the second vertex goes to the second geo position that we calculated. The reason why we say normal and actually I suspect this will change at some point. But the reason we say normal is when you're doing replacement rules, usually it expects a list of rules rather than an association, although they have very similar semantics. I guess this will change at some point. But we basically, if we say normal of this thing, we get a. We get a list of list. Good so far? I think so. Good. So we're going to create that converter more explicitly. I guess I'm going to take our embedding and we're going to have it. So like, I'll just Run this and show you what it looks like. That's not very useful. First, at normal converter or maybe. So basically what a converter is doing is it's going from the Cartesian graph world to the sort of geographic real world. It's saying the vertex that's here is actually here. At this point though, I kind of realize that I've been thinking conceptually a little bit backwards. It's not a disaster. But the thing is we are moving here in this direction from nodes, two cameras, right? We're trying to sort of fit our nodes into cameras. But if we look. So I'm saying VC is our vertex, count a number of vertices, and our number of points is our number of data points. We have quite a lot more nodes and cameras. Excuse me. So you know, what we're trying to do is like squish our nodes into our cameras when it would be more comfortable to kind of expand our cameras into our nodes. And we want this to be the other way around. So luckily we don't have to do all that. Again. We can invert an association using this kind of. I guess it's documented, but this function exists. And yeah, we can invert our association. So now basically we just flip our arrows. Let's just take the first one. We flip our arrows. So now our cameras are pointing to our Cartesian like locations. How does this function work? Something I want you guys to know, because it's useful, is that there are functions in Mathematica that show you the definitions of stuff looks like the DAM values and stuff like that, and it formats it nicely for you. So one way to get at this is this resource function called show definitions that some hero has written. There's also something like this in general utilities, but they both do the same things. So if you're wondering, oh, how did this thing work? Is it complicated? What's going on? We can ask what is the definition? And we can see that the definition is actually, there's not much to it. Association thread. We've already met this. That's the thing that, you know, did this. It, you know, lines up all this and then draws the arrows and we're associating the values to the keys. It's actually, it's actually quite straightforward. Okay, so good. We built our graph. Basically, we built our graph. Now we need to map cameras to nodes. Okay. So my first thought was like, okay, just, you know, we now these, these, these cameras and nodes, they're in the same world. They're in like they have these geographic locations. So we should just, you know, it should be straightforwards and maybe it is, but we, we just take a camera and we just give it to the nearest node. And the way we can do that is by something like nearest. Okay, so what's going on here? We are grouping the positions, the positions of our cameras by the, the nearest node that they go to. So if we look, we see that there's actually quite a lot of collisions and quite a lot of competition. Say like, okay, so this, like, so these, there's like maybe five cameras here or something or, and they're all nearest to this node. So they're all sort of competing for that same node. And so we have to make decisions about how we match cameras to nodes. I'll do it because this is actually the mistake I made. I said I thought that we should match cameras to nodes, that for each camera there should be a junction. And that sounds reasonable, but the mistake is not true because of course cameras can also exist on a road with no junction. So this competition will be because, you know, there's cameras on roads and then they're going to compete for a junction at either end, you know, with the camera that's also at that junction. But I didn't realize at this point. So let's pretend we don't know that and let's just run for this slide. I'll run for this particular slide a little bit quickly because it's slightly technical and as I just said, it also doesn't work. But just for your culture, we'll go through it anyway. Yeah, so at this point I'm still thinking about matchings and I'm thinking that, okay, we need to make decisions about which one of these cameras gets the node. My first thought was like, okay, you know, we could just run through this list and we'd be like, okay, whichever, which one of these is clear is nearest, we'll take that one and then we'll keep going and we'll do like a kind of a so called, like greedy approach where at each stage locally, make the best decision locally and then hope for a solution that's globally optimal. But depending on the order of things, this can be quite bad. You can get quite a bad matching this way. So I thought that maybe we should try and find a globally optimal solution because that's something that we can do. It's not too difficult. So here's the setup and here's where this other graph comes in. So there are, there's, there are these things called bipartite graphs. Okay, bipartite. Because they come in two, two pods. And here's what I want you to imagine. On the left hand side we have, we have cameras, okay. And on the right hand side we have nodes. Each edge here will tell you the distance between that camera and the node we want to pick. For each one of these cameras we want to pick an edge that matches it with a node that minimizes the sum of those distances. We want the thing that minimizes the total sum. To do that, first of all we're going to have to build this graph. And this graph is determined by the weights of these edges. So if these things were two miles away then this edge will be two. And if these were half a mile away then this edge will be half. We need to build that graph and we're going to build it from its adjacency graph. We have a list, right for the. If, let's say for the second camera in the third node I have a matrix where the second and third position is the distance between the second camera and the third node. So let's start. We have, we're going to get the. So that matrix is a distance matrix. It's a, it's a matrix that gives us all the pairwise positions, pairwise differences rather. So, okay, we have all the positions, we have the positions that are nodes landed up on. So these are all geographic. And then we build a distance matrix. And the thing is with this matrix is because we were working like in the GEO world, the I wanted onto two of these. The coordinates of these matrices are given in miles. I just want to get rid of the miles. I don't care about the units because it's like a linear, it's just like a constant that doesn't matter. So we want to get rid of those. But the first thing to do is to check just to be sure that actually all of these are in miles. Because if some of these are in miles and then some of us are in kilometers, then we can't just get rid of the unit because they need to be rectified. So what I did is I flattened the matrix, it's turn into a big list, extract the unit and then delete duplicates to see how many different things we have. And we just have miles. That's good, we can just throw away the unit. That's what we do, we throw away the unit. And then the next sort of issue in this, like in this sort of, it's like a doom side quest I guess is the next issue is we want to find the minimum weight matching. We want the closest matching. But Mathematica only has functions that give the maximum weight matching. So okay, in my head I'm like, that's fine, we can just split the distances and negate them. But I suppose, because I suppose Mathematica also expects these edges all to be positive because when I just negated the magnitudes and run it, it gave me an empty set for the matching. It picked no edges, which is not what I want. I wanted to pick a saturating matching. So what I do is kind of flip things from the ceiling in a way. I say, okay, we're trying to just like in a hand, wavy sense. If we're trying to minimize our distance from the floor, we can maximize our distance from the ceiling. It doesn't matter that we add this constant to every coordinate because we're going to have the same number of edges in every matching. So we change the value of the optimum matching, but we don't change what the optimal matching is. Okay, so that's good. We have a distance matrix, but we want this to be an adjacency matrix of a graph. So in particular had better be square. We see that it's not a square matrix. It has different height and width. So we're going to create, we're going to turn this into the adjacency matrix of a, of a graph by basically adding these squares to say. So we're going to say, as I say, I won't go for this too much, but we're going to add these squares. So like, basically, so our width is the number of nodes and we say, okay, so the top part of our adjacency matrix is going to be nodes and they don't have any connections to each other. Right. The absence of an edge here you can interpret as an edge of infinite weight. So, okay, so that's good. And so, you know, once we've done the slipping, we basically. I can just show you how this looks, I guess. So the array plot. This might take a little while, but I think we'll just settle for like an image of this, of this adjacency matrix. Okay, so here we have the nodes in the original graph, right, which now are in a new graph, the second graph, and they aren't connected to each other. But then when we get to the cameras, then each node is connected to a camera with some weight. Likewise the cameras, they're not connected to each other, but they're connected to the, the nodes. Okay, so we have, we say we have this adjacency matrix and Then we create a weighted graph which has, you know, some number of edges, just to check that we didn't do something wrong. We can ask if it's bipartite, if it looks, you know, like this, because that's what we wanted and it says true, that's a good sign. And then if we're not matching, we can just say, find independent edge set. And then that'll give us a matching. So that'll run for a bit and give us a matching. So one quick thing. How do we know that Find independent headset gives us a maximum matching? To be honest, maybe I was blind, but from the documentation for me, it wasn't completely clear. It says it gives you one of the maximum number of edges. And then if you look at the. In the scope section, it says that it works for weighted graphs. But I still. It wasn't completely clear to me if it was optimal. So there's two reasons why I think it gives you a maximum matching. The first is if you look at. Let's just. What's it called? Wolfram. I don't remember the exact name. There you go. There's a deprecated function called bipartite matching and cover. And that one explicitly, it says two things, says that it gives you a matching with maximum weight. And then if you look at the options, it also says that it's been superseded by finding the pendant headset. So that's a piece of evidence, but I kind of wanted a little bit more. I wanted to be sure. So this line of code gives us the weight of the matching that we found, has a weight of this much. And then what I do is I create 200 random matchings and then look for the best one, the heaviest one out of those, and you see that it's quite a bit lighter. So what we can infer from this is, like, even if it wasn't finding the maximum matching, which I think it is, it's definitely not doing stuff at random. It's doing something. It's giving us a good matching. So that's fine. And then we're going to find our vertex weights. Okay, so let's actually look at this matching. If we look at our. What we've done right, is we've put. We have. First of all, we have our nodes in our graph of London. And then on top of that, we have our cameras. So these cameras are going to have bigger numbers. Essentially. The first camera actually will have coordinate the number of nodes plus one. That's where this sort of thing comes from. So what we do Is we're taking the right hand side of this matching, subtracting the vertex count to get back to our zero to number of data points. Reordering our data according to those things, looking up the traffic. Because remember, the data has like name, snapshot, whatever. We want the number of cars, we line them up with the left hand side of the matching and then we take the rules. So we transpose and then we draw the arrows. So basically what we have now is so vertex weights. This thing that we just did, the fifth thing is saying, okay, this vertex is pointing to this vertex gets this much weight. Okay, so now we can start to. We're going to pause just to see what we've done. So let's run this again. Our graph like it looks roughly correctly located. But as I say, the mashing was not great. I found this out later on when I went to create this little manipulate thing that we did. But also if you compare it to the heat map, it just is not great. If you look at the heat map, This is actually fine. But anyway, wait, this is not the actual heat map. I'm not sure what happened here. But anyway, if you look at the heat map from above. Oh no, never mind. Here's the heat map. Yeah. Okay. Yeah. If we look at the actual heat map, we see that there's like loads of junk, like loads of cameras on the same road that don't have a junction. So we went forward this effort to match cameras to junctions, but the cameras don't necessarily match the junctions. We basically made it. Well, I say we. I made a modeling decision that wasn't great. So I was, I was talking to Dan, who's a friend of mine in the office about this and I'm like, man, like this code is like, it's sort of, it's ruining my life. It doesn't seem to work. The matching is crap. But yeah, I did all this, I did all this stuff. And he suggested why not just average. If we look at nearest again this things from before, If these five cameras are clustered around this node, then we might as well just sum up the traffic of these cameras. We don't need to match, we don't need a one to one matching. We won't have a one to one matching because sometimes cameras are on roads. So we will instead just sum up the traffic of these things. And then that sum we will assign to this node. We'll say those cars, if they're nearest to that node, then we'll just collapse into that node. So here's what we want to do right, we want to go from here, from these left hand sides, from the embedding of the vertices to the vertex itself, the right hand side from these like geopositions, we want to go back to the cameras that were located at those geopositions. So geopos2 data is doing that second thing. What we're going to do is so counter data, that's our original data set that we started off with. And we're going to create this association which points from these positions here to the whole data set and then nearest of data. What we've done is something a little bit confusing. We are mapping map of geopositor data over nearest. What does that mean? So this is a so called operator form. It's kind of like, it's like a functional construct. So we can actually just see how that looks like map. So let's say we have this function X and then we create a new function map of X. If we apply that to a list, let's just do it like this. That will map X over the list. Okay, so map geopositive data. Once we map that over nearest, we're applying it to each one of these lists. And then when you apply it to a list, it'll fall for that list because of this map here and it'll turn each one of these into data. So you can check that this looks roughly correct. I think it does. And now instead of a list of geopositions, we've sort of refound the whole piece of data where it came from. Okay, now I want to do something similar to the left hand side. So okay, so we said the first vertex goes to the first place in this embedding and this kind of thing so association thread will give us will point from these to its position and then we are going to map that over the keys by using keymap. The first thing I did was say, okay, we have this thing that points from these cartesian coordinates to its rank, its position, the ordering as a vertex. But my first attempt didn't work. It said there's no such thing as this key here. And what has happened and I don't know why this is the nearest thing that has introduced this. But we're not actually going from our cartesian coordinates to our geographic coordinates here. We're going through like it's been wrapped in a list. So basically you need to get rid of that list. So before I do the embedding coordinates to Verdex, I say first I just, I just get the first thing out. Cool. So now we have, we're looking good. So now I do this little trick of a sparse array. It's not, it's not completely efficient, but we're running this just once. So it's fin, basically. So if we look, if we look at this first thing here, we say this node gets like five cameras. We know from that that some nodes are going to be close to no cameras, right? Because there's already more nodes than cameras. So in general, some nodes won't appear here on the left hand side, but we still want them to exist. So what do we do? We're going to do something like this. The rough thing is this. Okay, so let's say I say sparse array, a sparse array in general. So this is not just a Wolfram thing, this is like a computer thing. A sparse array is, let's say you have a list of like a billion elements, but only five of them have some sort of value that isn't zero. Say there's no point remembering that whole billion elements if most of them are zero. You just want to remember where your five different coordinates are and know that the rest are zero. So if I say for example, sparse array and then I say, okay, the third thing is two and the fifth thing is eight. And you're also a one dimensional thing with 10 coordinates, then you get the sparsary. If we say normal of that, we're going to get the list back. So this is like a, like a, this is a way to get these zeros about doing a lot of typing. If you already know this, it's turn into a sports array and then say normal. So this is kind of what we're doing. We have this vertex data thing. But again, although we got the whole data point, we only want the traffic. So I'd say for each one of these things just take the traffic and then total. Because you know, if we look at this first thing then now we're going to have here we're going to have like five numbers, you know, for a car each in each camera. So total get the number of cars normal to get to get. Again, because that's an association, we want a list of rules. And then sparse array to get this thing and the normal to put the zeros basically where there was, where the verdict didn't get any cameras. Okay. And then, you know, we go, Okay, that makes no sense. I had to run the cell. Yeah. Okay, so again we're going to do something similar just to see like what we've done. So let's just. I'll just run These it's similar to what we've done before. What's most interesting is this graph. So we get this graph and I promise the matching is sort of better. Now we've calculated things differently. You see, there's quite a few zeros where there was no cameras. There's more zeros in this thing. That's not a bad thing. Okay, and now for later, we're going to want to remember like, which. We want to want to remember which, like which name went to which, like, you know, was associated with which. With which vertex with which node. So we're just going to like distribute rules. What does that mean? In our vertex to data thing, we have something like this, something roughly like this. A. So you know, the vertex, let's just call it V goes to whatever P1, P2P. Let's say camera one, camera two, camera three. But I want basically to get. Instead I want V1 goes to camera one, V2 goes to camera three, V3V goes to camera three. So that's going to look like this. What I want is an output is this thing. So how does this work roughly? I say distribute rule. It takes a rule of something that points to a list and then what that is is you just map the rule over the list so this gets mapped over the whole list. And then the matching is basically that. So again, just always check that we're roughly doing the right thing. Let's just see. Let's take two of them to check that. See that we did the right thing. Okay, good. It looks like the vertices vertex numbers are pointing to names. That's good. So that was issue zero, which is not really in the Wolfram spirit because like we do stuff like one indexed. But that's the issue that we had to solve before we got to the actual issues. We have to decide now how to deal with these nodes that don't have any cause because probably they have cause there, but there are just no cameras there. Also another thing, this has been going on for a bit over an hour. So probably these cars have moved in the meantime. What we want to do a little bit is simulate the motion of cars around this graph just a little bit. So how do we do that? We're going to start with an initial state, which is a list of our vertex weights. So let's just take the first five. See, you know, see what it looks like. Okay, well, a lot of those are zero. Right. But some of them won't be. You know, some of vertices have rates. Okay, this looks more like it. So, so There you go. Some of vertices have weights. Our initial state in our simulation that we're about to do, each, each vertex, each node has some cars that are there. And I'll be a little bit brief about this, but what we're going to do is say that a, you know, if you have some number of cars at a junction, this is a, this is definitely a simplifying assumption. But if you have some cars at a junction, let's assume that they kind of move out over the edges sort of uniformly. So let's say if you had nine cars at a junction with three exits, then three cars are going to go out over each line. It's probably not completely true, but it'll, it'll do for now. How we're going to achieve this is by using the adjacency matrix of this graph. So what we're going to say is, okay, let's say we're in time step T plus 1. How do we calculate how many cars are at each vertex at time step t plus one? Well, we're going to look at the previous state, right, the state at time t. And we're going to draw from our neighbors right in time T, but inversely proportional to the degree of those neighbors to get the adjacency matrix. And we want to scale the columns by one over the vertex, degree of the vertex at the column. So we transpose the matrix to go from rows to columns. We scale each column by one over the degree and then we transpose it again basically to go back. So this kind of, so I didn't make this sort of thing up. This is, this is quite a common thing that you might see basically when you're looking at influence in graphs. And actually, if I remember it correctly, this is roughly how Google used to work a long time ago before machine learning sort of became really powerful. I just want to point to a similarity here. So roughly how Google used to work is okay. If you as a website you are cited, but you're cited by more websites, then probably you're like a higher ranked website. You should be ranked higher in whatever, in the search results. Um, but each citation kind of becomes less valuable the more that citing that. So if like a website, you know, cites like hundreds of millions of websites, then you don't want to consider it too much, right? Because it's, you know, it's, it's citing things very freely. Its citations kind of don't mean much anymore. So this is somehow similar to what's going on here. In fact, when you look at Matrices, it's the same thing, but basically, yeah. If a junction has a lot of exits, then probably you won't receive that much traffic from it. So that's the one over the degree thing that's going on. Anyway, we do this for free steps. You can do any number of steps, but we're gonna do it for free steps. Something I do wrong quite often when I'm working with vectors and matrices in Mathematica is I used the wrong symbol for multiplication. Actually, what I used here was this thing. That's something that I wanted. There's this thing like in Mathematica, let's say you have like a matrix 1, 2, 3, 4, and then you multiply that by 5, 6. This doesn't, you know, as numbers. This doesn't make sense. But what we're going to do is multiply that whole first list by five and that whole second list by six. And then when you multiply a list by a number that just falls through and then we multiply again quantum wise. So I did that here when I multiplied each column by one over its degree, but I didn't mean to do it here. So it's kind of like a dot product instead of Mathematica. So that looks more like it. And then I just take the ceiling and I claim we've solved our first issue with that. Well, what we did is we kind of just simulated the motion of traffic a little bit around this graph just to kind of like, you know, smush out the image and also to make up for lost time. Okay, the. Our next issue is that we want to. We want to find the shortest path through this graph. You know, now that we have some weights, we want to find the lightest weight path through this graph to get through different places. But at the moment, we're working with vertices, right? We've got vertex weights. And this is. We need to do something about this. We want edge weights, not vertex weights. So we're gonna, I guess, settle for something that's like. That's quite simple. We're going to say that the weight of an edge, right? How. How many cars that are on an edge is going to be the average of its two endpoints. If there's five cars and it's in the entrance and 10 cars in the exit, then there's seven and a half cars on the edge is what are we going to see? Which I think is not a horrible assumption. It satisfies the kind of stuff that you'd want. Like, if one endpoint gets busy, then so does the Edge. I mean, that kind of makes sense. Okay, so let's look at what edges are. In Mathematica, edges look like this. We can look at the input form, actually. I mean, input form like this. Okay, it's an undirected edge 513. But I kind of want these to be lists. So map apply. Again, that's the triple art. I'm going to replace undirected edge of list. So now we have a list 513 instead of undirected edge 513. And then I look up in the state, the traffic at each side, basically. So what's going on here is like if you have a list like this, 2, 3, 4, 5, 6, you can index it in a few ways. In Mathematica there's this kind of shorthand where if I index it by another list 5 and 2. What I mean is I want the 5th and the 2nd, the 5th and the 2nd coordinate here, which is 5 and 2. So in the state, we're looking up the traffic, the state of the traffic at each endpoint of this edge. So in this case, the 5th and the 13th vertex. And then I say mean. So it's going to add them up and divide it by two. So again, random sample, just to make sure that we still have numbers. Like, if I did something wrong here, then these may not be numbers. And then these are how busy our edges are. Okay, now we're finally sort of reaching the end of this thing. We'll do the same thing from before just to visualize it. We will look, we'll scale things logarithmically and assign some colors according to this temperature map just to create a visual. If we run this, then we see what has happened is like, okay, as we've simulated the motion of this traffic, it's kind of moved away from the ends here. And it's kind of. Because there's no entrance here and the things have moved towards the center of the graph, which maybe is realistic. But we have our model. We have a model of the traffic of London at the very least, so we can start finding shortest paths. Now we have the model. So first of all, just start writing some code and see how things go. We'll just pick two random places. So sample from the matching two random places. Then find in the graph that we just made the shortest path between those two places. But we'll take the first one because again, in our matching we're pointing to the names, the vertices, and there we go. And then we'll highlight in the graph the actual path. So that's great. And we keep running that. But maybe what we want is like something that we can start clicking on. So there's this thing in alphabetical called manipulate, which basically lets you. You specify your expression that you care about. So here we're saying, okay, you have two places, P1 and P2, and then would find the shortest path in the graph between those two places. And then the expression that we evaluate is this sort of highlighted graph thing. But then we say, okay, P1 and P2 can. Can range over our matching. So cool, we can start clicking on places and I'm just picking things at random and we can kind of start to get shortest paths between places. And this is. This is what we made. So there's a few things to address. Right. So Sam mentioned earlier on our metric could be different. Right. As you said, like we. As we said, what we're actually minimizing is the number of cars we come across. But maybe you don't care about that. You just want to get somewhere as quickly as possible. In which case you should consider not only how fast the car's moving, but also the length of the roads. We haven't considered the length of the roads at all. That's another thing. That's something to consider if you want to improve this. And I think that's all I can think of. So. To summarize. Yeah, we set out a question and then we split our question into smaller questions, attacked each sub question had varying levels of success. Had to retry at some point because, you know, in this case, me, I was like, oh, we need a matching, but we don't. Well, we probably shouldn't have a matching because of how these things work. And we built a little sort of miniature, like, application in the end. So I will pause for more questions if there are any. Stephen, I'm glad you liked it. Cool. So it appears that there are no questions. I want to thank you all again for coming and I hope that everyone has a. Everyone has a great weekend.