Graph algorithms on the database with pgRouting
CC Attribution 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Vergara, Vicky
What are the alternatives when a road is closed? You didn't find a path, because your graph is disconnected and you didn't know? pgRouting is more than finding the Shortest Path on the database. We provide graph algorithms that can solve those questions and more! pgRouting extends the PostGIS PostgreSQL geo-spatial database to provide shortest path search and other graph analysis functionality. This presentation will show the current state of the pgRouting development: * Wide range of shortest path search algorithms * Flow analysis * Graph Contraction * Graph Coloring Among other algorithms We will explain the different categories for the functions on the library: * Official * Proposed * Experimental We will talk about other products that we provide: * osm2pgrouting * pgRoutingLayer for QGIS
 We are moving to our next presenter. I'll add Vicky. Thank you, Felix. Vicky is preparing his presentation. I think we will have a presentation directly from Mexico, right? Right. So I'm trying to share my screen. Share. Share screen. We still have two minutes, Vicky. And can you see the screen? Not yet. Share. Share screen. Oh. Mm-hmm. Mm-hmm. I'm going to share. Mm-hmm. Mm-hmm. I have it here. So we can see your screen. Not perfect. Yeah, if you can hide the browser, maybe do a full screen. How do I do a full screen? No. F11? F11? Mm-hmm. F11. Yeah, we still see the... Yeah. F10, maybe? No, in my browser, F11 switched to full screen. Yeah. F11, F11. There. Well, at least you don't see the bottom things. Yes. But we still... Yeah, I can see that you can still see this... this thing. No. Yeah, but don't worry. It's okay. Are you showing some code or something like that? No. Oh, it's okay right now. Okay, I can start? In 15 seconds, yes, you can. So let's start sharp on the hour. Oh, now it's full screen. Yes. It's full screen. Okay. All right. So, Vicky, the stage is yours. Thank you very much. Buenos días, buenas tardes, buenas noches, good morning, good afternoon, good evening. I'm going to talk about graph algorithms in the database. Well, at least that is the title. And more with PG Rowdy. This is not going to be too technical. So, the first thing I want to mention is that normally in phosphor Gs, I gather signatures from the participants. And this is a great memory that I have of Malena Lipman who is her own handwriting the last time I saw her on 2019 in phosphor G Argentina. And I'm dedicating this presentation to Malena on her memory. So, who am I? I'm an economist. So, I'm doing PG Rowdy development. I'm from Mexico and I am an OSG of fun and participants. And that is my email where you can contact me. And I will be giving this presentation about PG Rowdy. So, what are we going to cover today is what is PG Rowdy? What is Rowdy? How we develop PG Rowdy? We're going to mention some of the PG Rowdy products. We're going to talk about graphs. And we're going to talk about the student contributions in the last two years. So, going into topics, what is PG Rowdy? Well, PG Rowdy is an OSGEO community project. And it's open source. It's a library that is, like, it requires post-gis enabled database on Postgres SQL database. And it serves to route, that's why the name, vehicles or pedestrians in, for example, a city. So, in general, this is what is PG Rowdy. And it's always your community, open source, library for an enabled database or geographical enabled database in Postgres for doing routing. But what is routing? Routing, well, it's basically these questions. I am here and I want to go there. And we're going to go using the shortest distance. And we know that from elementary school that the shortest distance is in a straight line. But there we go. Once we get our route, and oh, surprise, the elephant doesn't have wings. And it's going above buildings, above crossing streets that shouldn't be crossed on those positions. And, well, the straight line didn't work quite well when we're putting the routing in context. So we need to develop PG Rowdy to solve that problem when we have things in context. And we do it by working on the theory. The theory is very important for us. And in this presentation, I'm going to present a theory that it's out of the box to demonstrate how we develop PG Rowdy. So, in secondary school, we were taught that gravity pulls objects down to the earth. And probably in high school, we were taught about tension. So if an object gets pulled down and it's tied up to a string, well, the string will get tense. And we're going to use this theory to solve a routing, the problem that we had before. So, PG Rowdy, we do it by its test-driven development. So what that means is that we create our tests and we define, this is my testing data, this is the expected result, and then we develop the algorithm. So let's start with the testing data. So suppose that we have this situation. It's not drawn to scale, as you can see, because like the edge 2, it's very long compared with the edge 14, which is the, we can think about it of the length of the edges, so this drawing is not up to scale. But we want to go from node 1 and go to node 5. So that is our objective. How do we do it using the shortest path? So we manually expect a result, we try many things, and we find out that we need to traverse the blue, like blue segment, the dark segment, and the orange segment. In this case, it's black because the background is white, but in our algorithm, the segment that it's black, we're going to color it white. So let's start with implementing our algorithm. The previous graph is representing this map. Okay? The black segment is under a tunnel. You can see the tunnel. So we're going to model this map with our algorithm, which is going to consist on segments represented with the strings, the color strings, and the vertices represented with these balls. And we have our red ball on the left and the blue ball on the right. So let's do test our theory to find the shortest path from the red ball to the blue ball. And we know that our expected result is using the light blue string, the white string that it's not seen because it's on a tunnel, and the orange string. That is our expected result. So let's see the demonstration. That is our map. We remove the tunnel. And that is the graph that it's representing the map. We want to go from the red to the blue. We call the red ball, which is our source, and we get all the strings that are a tense that depart from the blue ball, which are the orange, the white, and the blue. And we get our straight line that consists on blue, white, and orange. Now I have to add there. So with this demonstration, I hope you liked it, we prove that our algorithm was correct. We obtained the expected result, and that is how we developed PG routing. Right now we have over 30,000 unit tests proving that the algorithms that we are implementing are okay. So now let's talk about PG routing products. We not only have PG routing, but we also have two projects that help people to use PG routing. The first one is OSM2 PG routing, which will take OSM data and import it to the database so that we can use PG routing with that data. And the second one is that you cannot use PG routing if you import data with OSM2po, for example. It needs to be done with OSM2PG routing if you're using OSM data. We have functions that allow users to use other kind of data, but we are an open source project, so we developed this for open source data. The next sub-project that we have is PG routing layer. It's a very simple plugin for QGIS that allows people to play around with basic PG routing functions and visually see the results. And this year we started with VRP routing thanks to Ashish Kumar, and VRP stands for Vehicle Routing Problems. Right now, PG routing has an experimental function that is for vehicle routing problems, which is pick deliver. And we decided that we're going to start using a different repository for those kind of routing problems. So a vehicle routing problem is, for example, to solve problems like you have a set of vehicles and you need to pick up garbage containers and you need an answer of how the vehicle is going to go from the depot where the vehicle starts with the driver, how it traverses the city, and at the end, after it's been full, how it goes to the dump to get emptied and goes back to the depot. So that could be one vehicle routing problem. You can have school buses that you need to pick up the students and take them to school, or vice versa, you get the students from the school and distribute the students along the city. So those are the kind of problems that we intend to solve on the VRP routing new extension. The requirement of this new extension is going to be with some projects that are not actually packed. So it's not going to be a package yet because the dependencies need to be existing there. And of course, PGU routing. And the summary of current PGU routing that you can obtain with packages is OSM2 PGU routing, PGU routing, and PGU routing layer. Now, the topic of the graphs, which is what the title of this presentation was about. For the graphs, PGU routing actually, it's about graphs, graphs algorithms. And you can interpret a graph like, for example, a river. And we have algorithms that make flow analysis. You can have analysis of flow of vehicles, flow of water, flow of electricity with some of the functionality that we have in PGU routing. So it's not only about routing cars or pedestrians. We can also use PGU routing to find out interactions between people, like the six steps from one person to another, how long, how that you don't take more than six steps to get a connection with somebody else in the world kind of problem. So we can use PGU routing for human connections. We can use PGU routing also for example for connectivity of computers, routers, servers. And of course, what we're used to is to use PGU routing for routing vehicles. But if you interpret the graph, you can interpret it to determine where your sour system would go, where the electricity lines would be placed. So the graphs, the interpretation of the graphs is not only for vehicles. That is the point that I want to make sure that it's gone over you. You can use it for much more many things. Now, in PGU routing, we have several classifications of the functions. We have official functions proposed and experimental. Experimental functions are the newest functions and they are written normally by the Google Summer of Code students. And once we have some feedback from the general users, we can move them to proposed. And once they are proposed in the next major version, they can go to be part of the official functions. So basically experimental, please try to use them. And soon we will release version 3.3. It's not a major release. It's a minor release. And this will contain new functionality that was done by these student contributions from Google Summer of Code of 2020 and 2021. Like Ashish, who also helped on VRP routing. He added a depth first search traversal on a graph and a sequential vertex coloring of a graph. Vinith Kumar added also a coloring function which is edge coloring, which comes from boost libraries and what this graph does instead, compared with the one that Ashish created, it colors edges. Prakash also contributed to PG routing, but in his case, he is converting a graph to using the langur target dominator 3 to obtain the dominator 3. Also, he created a beeper type, which is a coloring graph, coloring algorithm that just tries to color a graph with two colors, if it can be parted in two. Himanshu Rush created a function to test the planarity of a graph. These graphs, K5 and K33 are not planar graphs. Basically, like streets would be planar graphs, except when you add bridges, which are crossing. So that wouldn't be a planar graph. A planar graph you can draw in a two-dimensional space without having segments crossing. And Hamwu, who created a transcefit closure algorithm for a graph. For the future, we don't want to be an OSGEO community anymore. That is right. But don't be sad, because we want to be an OSGEO project. So we're working hard to make this happen. Hopefully we will have our application to become an OSGEO project before this year ends. And please, please start using PG routing, start contributing to PG routing. You can fork PG routing on GitHub. And thanks very much for coming here. I'm going to post some links about PG routing, the documentation, the workshop, support, and my mail. And you can look for me in walking around in the social gathering or looking at more presentations. Thanks very much. Thank you very much, Vicky. It was an amazing presentation. Thank you. I've just shared your presentation on the chat on the venue less, so people can review your presentation. And we have questions from the audience. Please add your questions on the venue less platform. But we have already one question, Vicky, on the private chat here. You can have a question about which attributes can be used for routing. Okay, yes, you can use a speed to get route by time. You can use inclination, like for a pedestrian routing that is going for hiking. Going uphill is more slower than going downhill. So you can make this cost depend on the angle of the road. You can make the routing depending on the importance of the road. Like for very wide roads, you want wide pipes for sorts. And for very narrow roads, you want smaller pipes. You can make it depend on the amount of people that are living in the road instead of the length of the road. So yes, you can use the cost and you can use it on the fly. That means that you don't have to preprocess everything, but you can just change your cost function on the fly. Thank you, Vicky. We have another question regarding if pedestrian routing can be used to build the Isochron areas. Yes, with PGR routing, PGR driving distance, you can use this cost to make these areas. And we also have PGR alpha shape that shouldn't be in PGR routing. It should be in post GIS because that is a geometry function, but for historical things, it's in PGR routing. But you can also use the results of driving distance with ST convex hull and many other functions in post GIS that can create this area. Okay. It's not automated, but it can be done. Yes, it's in many steps. Just like you saw in Regina's presentation, you need many steps to achieve what you really want to achieve. Okay. Maybe it can be a contribution to PGR routing to make these Isochrons more automatic, right? Well, one thing that I by experience know is like, if I start thinking as a user, if I start using PGR routing, which I don't like to use it, then my mind goes, it's like, I want this function to work to this application, then I forget all the other applications. So having this kind of automatic, it's not a good idea because there are other functions that can do a similar answer. And depending on your problem is the one that you want to use. So it's like, I have to be more like a general, it's a library and with libraries, you just join the pieces to build the application. It's not application focused, it's library focused. Good. So we have another question more related with metrics and comparing PGR routing with other routing solutions. Do you have any kind of benchmarks that you can share? Okay. I don't have a benchmark. I'm more focused on the developing. But PGR routing works on the database with both G's. They are kind of linked together. And once when I started doing PGR routing, it was, I was a user because you cannot code if you don't know what is it about. And we were using OSRM also. And OSRM, you needed to kind of process the OSM data and created this morning file, the afternoon file and the evening file, because the traffic is different between them. And it was terrible. I mean, you couldn't just change things, change the parameters easily to get these traveling times. It was terrible. So by having the data on the database, it makes it more easy because you can have functions that on the fly will create these costs that will be used on the PGR routing. So that is from my experience. But as always, I mean, if the data is wrong, the results will be wrong. So that's why the unit tests are so important. Because with big data, you really get lost on if it is really the shortest path, for example, if that's what you're looking. Because it's a very huge city and maybe, well, I was working with Montevideo data that time and I didn't even have an idea of that city. I didn't even know if it was correct data or if the problem was on the algorithm or on the data. So unit tests, that's why I created those unit tests and test driven just to make sure that things work. Thank you, Vicky. Thank you, Vicky. I think it was clear. I have two more questions if you can go then in just one minute. These are more specific questions. One about the PGR direct CHPP, if it is already in production. Which one? PGR underscore directive CHPP. The Chinese Starlink Postman problem. I guess that's what I mean. I need to really see their name. That is still experimental. That is still experimental. So it's there, but it's experimental. Okay. And the last question, if the graph is big, would the Postgres perform well or the graph need to fit in memory? Okay, it's like I want to route from my house to the store that is in the corner. What do I want to use as my graph data? Whole, complete American continent from Patagonia to Alaska or Mexico only or my state. I live in the state of Mexico or only my city. So that's why it's so important that you use extensively the Poch's functions and you make sure what graph you want. So bound your graph, make it small, otherwise it will take ages to load. I mean, my computer wouldn't hold whole America. So what is your... Okay, that's it. Thanks.
 We are moving to our next presenter.  I'll add Vicky.  Thank you, Felix.  Vicky is preparing his presentation.  I think we will have a presentation directly from Mexico, right?  Right.  So I'm trying to share my screen.  Share.  Share screen.  We still have two minutes, Vicky.  And can you see the screen?  Not yet.  Share.  Share screen.  Oh.  Mm-hmm.  Mm-hmm.  I'm going to share.  Mm-hmm.  Mm-hmm.  I have it here.  So we can see your screen.  Not perfect.  Yeah, if you can hide the browser, maybe do a full screen.  How do I do a full screen?  No.  F11?  F11?  Mm-hmm.  F11.  Yeah, we still see the...  Yeah.  F10, maybe?  No, in my browser, F11 switched to full screen.  Yeah.  F11, F11.  There.  Well, at least you don't see the bottom things.  Yes.  But we still...  Yeah, I can see that you can still see this...  this thing.  No.  Yeah, but don't worry.  It's okay.  Are you showing some code or something like that?  No.  Oh, it's okay right now.  Okay, I can start?  In 15 seconds, yes, you can.  So let's start sharp on the hour.  Oh, now it's full screen.  Yes.  It's full screen.  Okay.  All right.  So, Vicky, the stage is yours.  Thank you very much.  Buenos días, buenas tardes, buenas noches, good morning,  good afternoon, good evening.  I'm going to talk about graph algorithms in the database.  Well, at least that is the title.  And more with PG Rowdy.  This is not going to be too technical.  So, the first thing I want to mention is that  normally in phosphor Gs, I gather signatures from the participants.  And this is a great memory that I have of Malena Lipman  who is her own handwriting the last time I saw her  on 2019 in phosphor G Argentina.  And I'm dedicating this presentation to Malena on her memory.  So, who am I?  I'm an economist.  So, I'm doing PG Rowdy development.  I'm from Mexico and I am an OSG of fun and participants.  And that is my email where you can contact me.  And I will be giving this presentation about PG Rowdy.  So, what are we going to cover today is what is PG Rowdy?  What is Rowdy?  How we develop PG Rowdy?  We're going to mention some of the PG Rowdy products.  We're going to talk about graphs.  And we're going to talk about the student contributions in the last two years.  So, going into topics, what is PG Rowdy?  Well, PG Rowdy is an OSGEO community project.  And it's open source.  It's a library that is, like, it requires post-gis enabled database  on Postgres SQL database.  And it serves to route, that's why the name,  vehicles or pedestrians in, for example, a city.  So, in general, this is what is PG Rowdy.  And it's always your community, open source, library for an enabled database  or geographical enabled database in Postgres for doing routing.  But what is routing?  Routing, well, it's basically these questions.  I am here and I want to go there.  And we're going to go using the shortest distance.  And we know that from elementary school that the shortest distance is in a straight line.  But there we go.  Once we get our route, and oh, surprise, the elephant doesn't have wings.  And it's going above buildings, above crossing streets that shouldn't be crossed on those positions.  And, well, the straight line didn't work quite well when we're putting the routing in context.  So we need to develop PG Rowdy to solve that problem when we have things in context.  And we do it by working on the theory.  The theory is very important for us. And in this presentation, I'm going to present a theory that it's out of the box  to demonstrate how we develop PG Rowdy.  So, in secondary school, we were taught that gravity pulls objects down to the earth.  And probably in high school, we were taught about tension.  So if an object gets pulled down and it's tied up to a string,  well, the string will get tense.  And we're going to use this theory to solve a routing, the problem that we had before.  So, PG Rowdy, we do it by its test-driven development.  So what that means is that we create our tests and we define, this is my testing data,  this is the expected result, and then we develop the algorithm.  So let's start with the testing data.  So suppose that we have this situation.  It's not drawn to scale, as you can see, because like the edge 2, it's very long compared with the edge 14,  which is the, we can think about it of the length of the edges, so this drawing is not up to scale.  But we want to go from node 1 and go to node 5.  So that is our objective.  How do we do it using the shortest path?  So we manually expect a result, we try many things,  and we find out that we need to traverse the blue, like blue segment, the dark segment, and the orange segment.  In this case, it's black because the background is white, but in our algorithm, the segment that it's black,  we're going to color it white.  So let's start with implementing our algorithm.  The previous graph is representing this map.  Okay?  The black segment is under a tunnel.  You can see the tunnel.  So we're going to model this map with our algorithm, which is going to consist on segments represented with the strings,  the color strings, and the vertices represented with these balls.  And we have our red ball on the left and the blue ball on the right.  So let's do test our theory to find the shortest path from the red ball to the blue ball.  And we know that our expected result is using the light blue string,  the white string that it's not seen because it's on a tunnel, and the orange string.  That is our expected result.  So let's see the demonstration.  That is our map.  We remove the tunnel.  And that is the graph that it's representing the map.  We want to go from the red to the blue.  We call the red ball, which is our source, and we get all the strings that are a tense that depart from the blue ball,  which are the orange, the white, and the blue.  And we get our straight line that consists on blue, white, and orange.  Now I have to add there.  So with this demonstration, I hope you liked it,  we prove that our algorithm was correct.  We obtained the expected result, and that is how we developed PG routing.  Right now we have over 30,000 unit tests proving that the algorithms that we are implementing are okay.  So now let's talk about PG routing products.  We not only have PG routing,  but we also have two projects that help people to use PG routing.  The first one is OSM2 PG routing, which will take OSM data and import it to the database so that we can use PG routing with that data.  And the second one is that you cannot use PG routing if you import data with OSM2po, for example.  It needs to be done with OSM2PG routing if you're using OSM data.  We have functions that allow users to use other kind of data,  but we are an open source project, so we developed this for open source data.  The next sub-project that we have is PG routing layer.  It's a very simple plugin for QGIS that allows people to play around with basic PG routing functions and visually see the results.  And this year we started with VRP routing thanks to Ashish Kumar,  and VRP stands for Vehicle Routing Problems.  Right now, PG routing has an experimental function that is for vehicle routing problems, which is pick deliver.  And we decided that we're going to start using a different repository for those kind of routing problems.  So a vehicle routing problem is, for example, to solve problems like you have a set of vehicles  and you need to pick up garbage containers and you need an answer of how the vehicle is going to go from the depot  where the vehicle starts with the driver, how it traverses the city,  and at the end, after it's been full, how it goes to the dump to get emptied and goes back to the depot.  So that could be one vehicle routing problem.  You can have school buses that you need to pick up the students and take them to school,  or vice versa, you get the students from the school and distribute the students along the city.  So those are the kind of problems that we intend to solve on the VRP routing new extension.  The requirement of this new extension is going to be with some projects that are not actually packed.  So it's not going to be a package yet because the dependencies need to be existing there.  And of course, PGU routing.  And the summary of current PGU routing that you can obtain with packages is OSM2 PGU routing, PGU routing, and PGU routing layer.  Now, the topic of the graphs, which is what the title of this presentation was about.  For the graphs, PGU routing actually, it's about graphs, graphs algorithms.  And you can interpret a graph like, for example, a river.  And we have algorithms that make flow analysis.  You can have analysis of flow of vehicles, flow of water, flow of electricity with some of the functionality that we have in PGU routing.  So it's not only about routing cars or pedestrians.  We can also use PGU routing to find out interactions between people, like the six steps from one person to another, how long, how that you don't take more than six steps to get a connection with somebody else in the world kind of problem.  So we can use PGU routing for human connections.  We can use PGU routing also for example for connectivity of computers, routers, servers.  And of course, what we're used to is to use PGU routing for routing vehicles.  But if you interpret the graph, you can interpret it to determine where your sour system would go, where the electricity lines would be placed.  So the graphs, the interpretation of the graphs is not only for vehicles.  That is the point that I want to make sure that it's gone over you. You can use it for much more many things.  Now, in PGU routing, we have several classifications of the functions.  We have official functions proposed and experimental.  Experimental functions are the newest functions and they are written normally by the Google Summer of Code students.  And once we have some feedback from the general users, we can move them to proposed.  And once they are proposed in the next major version, they can go to be part of the official functions.  So basically experimental, please try to use them.  And soon we will release version 3.3. It's not a major release. It's a minor release.  And this will contain new functionality that was done by these student contributions from Google Summer of Code of 2020 and 2021.  Like Ashish, who also helped on VRP routing.  He added a depth first search traversal on a graph and a sequential vertex coloring of a graph.  Vinith Kumar added also a coloring function which is edge coloring, which comes from boost libraries and what this graph does instead, compared with the one that Ashish created, it colors edges.  Prakash also contributed to PG routing, but in his case, he is converting a graph to using the langur target dominator 3 to obtain the dominator 3.  Also, he created a beeper type, which is a coloring graph, coloring algorithm that just tries to color a graph with two colors, if it can be parted in two.  Himanshu Rush created a function to test the planarity of a graph. These graphs, K5 and K33 are not planar graphs.  Basically, like streets would be planar graphs, except when you add bridges, which are crossing.  So that wouldn't be a planar graph. A planar graph you can draw in a two-dimensional space without having segments crossing.  And Hamwu, who created a transcefit closure algorithm for a graph.  For the future, we don't want to be an OSGEO community anymore. That is right.  But don't be sad, because we want to be an OSGEO project.  So we're working hard to make this happen. Hopefully we will have our application to become an OSGEO project before this year ends.  And please, please start using PG routing, start contributing to PG routing. You can fork PG routing on GitHub.  And thanks very much for coming here. I'm going to post some links about PG routing, the documentation, the workshop, support, and my mail.  And you can look for me in walking around in the social gathering or looking at more presentations. Thanks very much.  Thank you very much, Vicky. It was an amazing presentation. Thank you.  I've just shared your presentation on the chat on the venue less, so people can review your presentation.  And we have questions from the audience. Please add your questions on the venue less platform.  But we have already one question, Vicky, on the private chat here. You can have a question about which attributes can be used for routing.  Okay, yes, you can use a speed to get route by time. You can use inclination, like for a pedestrian routing that is going for hiking. Going uphill is more slower than going downhill.  So you can make this cost depend on the angle of the road. You can make the routing depending on the importance of the road.  Like for very wide roads, you want wide pipes for sorts. And for very narrow roads, you want smaller pipes. You can make it depend on the amount of people that are living in the road instead of the length of the road.  So yes, you can use the cost and you can use it on the fly. That means that you don't have to preprocess everything, but you can just change your cost function on the fly.  Thank you, Vicky. We have another question regarding if pedestrian routing can be used to build the Isochron areas.  Yes, with PGR routing, PGR driving distance, you can use this cost to make these areas. And we also have PGR alpha shape that shouldn't be in PGR routing.  It should be in post GIS because that is a geometry function, but for historical things, it's in PGR routing.  But you can also use the results of driving distance with ST convex hull and many other functions in post GIS that can create this area.  Okay. It's not automated, but it can be done.  Yes, it's in many steps. Just like you saw in Regina's presentation, you need many steps to achieve what you really want to achieve.  Okay. Maybe it can be a contribution to PGR routing to make these Isochrons more automatic, right?  Well, one thing that I by experience know is like, if I start thinking as a user, if I start using PGR routing, which I don't like to use it,  then my mind goes, it's like, I want this function to work to this application, then I forget all the other applications.  So having this kind of automatic, it's not a good idea because there are other functions that can do a similar answer.  And depending on your problem is the one that you want to use.  So it's like, I have to be more like a general, it's a library and with libraries, you just join the pieces to build the application.  It's not application focused, it's library focused.  Good. So we have another question more related with metrics and comparing PGR routing with other routing solutions.  Do you have any kind of benchmarks that you can share?  Okay. I don't have a benchmark. I'm more focused on the developing.  But PGR routing works on the database with both G's. They are kind of linked together.  And once when I started doing PGR routing, it was, I was a user because you cannot code if you don't know what is it about.  And we were using OSRM also.  And OSRM, you needed to kind of process the OSM data and created this morning file, the afternoon file and the evening file,  because the traffic is different between them.  And it was terrible.  I mean, you couldn't just change things, change the parameters easily to get these traveling times.  It was terrible.  So by having the data on the database, it makes it more easy because you can have functions that on the fly will create these costs that will be used on the PGR routing.  So that is from my experience.  But as always, I mean, if the data is wrong, the results will be wrong.  So that's why the unit tests are so important.  Because with big data, you really get lost on if it is really the shortest path, for example, if that's what you're looking.  Because it's a very huge city and maybe, well, I was working with Montevideo data that time and I didn't even have an idea of that city.  I didn't even know if it was correct data or if the problem was on the algorithm or on the data.  So unit tests, that's why I created those unit tests and test driven just to make sure that things work.  Thank you, Vicky.  Thank you, Vicky.  I think it was clear.  I have two more questions if you can go then in just one minute.  These are more specific questions.  One about the PGR direct CHPP, if it is already in production.  Which one?  PGR underscore directive CHPP.  The Chinese Starlink Postman problem.  I guess that's what I mean.  I need to really see their name.  That is still experimental.  That is still experimental.  So it's there, but it's experimental.  Okay.  And the last question, if the graph is big, would the Postgres perform well or the graph need to fit in memory?  Okay, it's like I want to route from my house to the store that is in the corner.  What do I want to use as my graph data?  Whole, complete American continent from Patagonia to Alaska or Mexico only or my state.  I live in the state of Mexico or only my city.  So that's why it's so important that you use extensively the Poch's functions and you make sure what graph you want.  So bound your graph, make it small, otherwise it will take ages to load.  I mean, my computer wouldn't hold whole America.  So what is your...  Okay, that's it. Thanks.
FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_0_131.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_132_227.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_228_311.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_312_563.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_564_611.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_612_1631.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_1632_2519.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_2520_3335.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_3336_4403.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_4404_6527.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_6528_7163.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_7164_7415.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_7416_8183.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_8184_10583.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_10584_11147.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_11148_11255.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_11256_15131.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_15132_15671.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_15672_16991.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_16992_17051.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_17052_17123.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_17124_17315.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_17316_18323.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_18324_18395.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_18396_22571.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_22572_26027.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_26028_28787.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_28788_30611.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_30612_30887.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_30888_30935.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_30936_31427.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_31428_32303.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_32304_33131.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_33132_33323.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_33324_33407.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_33408_33671.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_33672_34151.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_34152_35651.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_35652_35711.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_35712_48611.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_48612_49871.png FOSS4G_-_Graph_algorithms_on_the_database_with_pgR_qNyJLh1XtI4_49872_49989.png