Shortest path in the database and more with pgRouting
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 295 | |
| Author | ||
| Contributors | ||
| License | CC Attribution 3.0 Germany: 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. | |
| Identifiers | 10.5446/43351 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
| |
| Keywords |
00:00
Software developerEmailRoutingProduct (business)Graph theoryTime evolutionFamilySoftware developerEmailGraph theoryBitPresentation of a groupWikiRoutingSoftwareProduct (business)Student's t-testProjective planeComputer animation
01:24
Open sourceDirected graphSign (mathematics)Presentation of a groupFunctional (mathematics)Open sourceLibrary (computing)DatabaseMedical imagingSoftwareComputer animation
02:35
MereologyPoint (geometry)Line (geometry)Online helpComputer animationDiagram
03:18
Computer clusterTheoryComputer animation
03:37
ImplementationAlgorithmCASE <Informatik>GravitationRight angleResultantFunctional (mathematics)TheorySlide ruleSoftware testingSign (mathematics)RoutingDiagram
05:30
Data storage deviceGravitationProduct (business)TheoryChord (peer-to-peer)Line (geometry)Lecture/Conference
07:17
RoutingLevel (video gaming)Data conversionDatabaseRoutingInformationForm (programming)1 (number)Plug-in (computing)Electronic visual displayProduct (business)Fault-tolerant systemTotal S.A.Open setComputer animation
08:17
Total S.A.Graph theoryRoutingProduct (business)Basis <Mathematik>DebuggerRaw image formatGraph (mathematics)Computer animation
08:46
Graph theoryRepresentation (politics)Functional (mathematics)Graph (mathematics)Connectivity (graph theory)DataflowVotingComputer animation
09:23
TopologyFunction (mathematics)DistanceVertex (graph theory)Graph (mathematics)Keyboard shortcutAlgorithmAlpha (investment)Shape (magazine)PolygonNormal (geometry)FlagEvolutePoint (geometry)CompilerFunctional (mathematics)Projective planeOpen sourceExecution unitRevision controlNumberError messageTotal S.A.Line (geometry)Unit testing
10:48
Function (mathematics)Graph (mathematics)Solitary confinementCalculationAlgorithmGroup actionGraph (mathematics)Chi-squared distributionoutputCellular automatonDistanceLink (knot theory)Shape (magazine)Alpha (investment)Revision controlPlanningPoint (geometry)Functional (mathematics)Tunis1 (number)FamilyType theorySoftware bugNetwork topologyData conversionUnit testingDesign by contractDistanceExecution unitCategory of beingTravelling salesman problemConnectivity (graph theory)DataflowAlgorithmTerm (mathematics)Bus (computing)Sign (mathematics)System callGraph (mathematics)Direction (geometry)Social classSoftware testingReading (process)BlogProjective planeComputer animation
14:43
CodeGoogolStudent's t-testMachine codeQuicksortRule of inferenceGoogolComputer programmingComputer animation
15:05
Dynamic random-access memoryAlgorithmVertex (graph theory)Complexity <Algorithm>Graph (mathematics)Order (biology)Table (information)Glass floatReverse engineeringDirected graphInterior (topology)QuicksortTopologyAlgebraic closureGroup actionConnectivity (graph theory)Kolmogorov complexityData structurePresentation of a groupAlgebraic closureFunctional (mathematics)Multiplication signGraph theoryGroup actionComputer animation
15:24
Glass floatDirected graphInterior (topology)RoutingDatabaseVisualBASICVideoconferencingLink (knot theory)Coefficient of determinationMultiplication signStudent's t-testComputer fileDot productSlide ruleComputer animation
17:15
Vertex (graph theory)Kolmogorov complexityAlgorithmGraph (mathematics)LengthDirected graphGraph (mathematics)RootContext awarenessLevel (video gaming)Port scannerGlass floatInterior (topology)RoutingFunctional (mathematics)Process (computing)Computer animation
17:34
Vertex (graph theory)AlgorithmDijkstra's algorithmGraph (mathematics)WeightKolmogorov complexityGraph (mathematics)Binary fileLengthIntegerRevision controlDirected graphReverse engineeringNegative numberWeight functionExtension (kinesiology)FLOPSProgrammable read-only memoryCodeGoogolSystem on a chipEmailResultantProcess (computing)VideoconferencingBriefträgerproblemFunctional (mathematics)AlgorithmStudent's t-testBinary codeHypermediaImplementationYouTubeComputer animation
19:42
AlgorithmAlgorithmGoogolComputer animationDiagram
20:00
CodeGoogolCoding theoryInformationPresentation of a groupBitGraph (mathematics)RoutingSoftwareProjective planeProduct (business)View (database)Point (geometry)SimulationComputer animation
21:11
InformationMeasurementNeuroinformatikView (database)Multiplication signPhysical lawComputer animation
21:40
InformationNeuroinformatikMultiplication signSemiconductor memoryArm2 (number)AlgorithmFunctional (mathematics)1 (number)NumberUsabilityInformationWhiteboardAllegorySystem callDatabaseMereologyRow (database)Graph (mathematics)Graph (mathematics)Vertex (graph theory)Graph (mathematics)Directed graphLecture/Conference
23:43
Information
Transcript: English(auto-generated)
00:07
So, who am I? I am Piki Vergara and I am an economist. I'm the main PG routing developer. I am from Mexico. I do a lot of things in OSGO. I consider myself as an octopus and
00:23
that is my mail. If you want to contact me, you can find that mail in GitHub, in wiki of OSGO. Everybody kind of looks like me. So, what are we going to do today? We're going to see what is PG routing. What is routing? We're going to see how
00:47
we develop PG routing and we're going to analyze just a little bit of PG routing products because it's not only one software that we develop. We're going
01:01
to talk very little about graphs and I forgot to translate that sentence from Spanish. We're going to see the evolution and we're going to see the students' contributions. So, what is PG routing? PG routing is an OSGO
01:22
community project. I think that the last update of my presentation is not here, so we're going to work with it. And it's an open source, so you can see and inspect how good or bad we're doing everything. We are a library of
01:44
functions that work with a post-gist enabled database of Postgres database. Okay, and what we do in PG routing is we do routing like you use your
02:06
Google Maps or Waze or whatever software when you are lost. So, that's what is PG routing in one image. Okay, I have to point to where. I'll use the
02:34
arrow. So, what is routing? Well, like the little elephant there says well I am
02:46
here, I want to go there. And when I was in elementary school the teacher always told me that the shortest path between two points is just a straight
03:00
line. So, we go like that. But then we notice that something is wrong, that that is not necessarily true. So, what do we have to do? We have to
03:21
develop something to make that routing be more accurate. It's not that it's not true. A bird can do that kind of trip but not us. And to do that we have to go and look and investigate, do some research and get some theory. So,
03:46
what we're going to be doing right now is we're going to develop a routing function right now. So, we go and look for the theory and in this case we find that. Okay, we are going to use the gravity, we're going to use gravity to
04:08
solve a routing problem. Okay, so we're going to be doing something. I hope it works. So, we find our very amazing theory and we need to make a test. So, we
04:28
have to design a test and in this case this is the design. I made a new slide that is not here but the expected result is to go from one to
04:45
three to six to five. That's the shortest path for this data that we have. So, we're going to implement our algorithm and for doing that, very
05:05
carefully, carefully, carefully, please, so that they can see. So, here he's, everything is with volunteers and he's my compulsory volunteers and everybody
05:24
knows that I ask for compulsory volunteers. So, he's my compulsory volunteer and this is how we're going to use the gravity to solve that problem. Can you hold it please? Maxi Boco. Yes, so we're using gravity. This is our
06:16
destination. From the destination, we find the more tense chord and it takes
06:27
us to six and from six it takes us to three and from three the more tense chord takes us to the green one and are the lines that has a nine, a two, and
06:49
a nine. So, we get our shortest path using gravity. So, the theory works.
07:04
Maxi Boco. So, this was supposed to be there while we were doing that. So, what are the PG routing products? The PG routing products are
07:22
OSM to PG routing. OSM to PG routing, what it allows us to do is to convert data from OpenStreetMap, which is open data, to a post GIS enabled Postgres database. PG routing layer is a QGIS plug-in that
07:52
allows us to see routes. So, it gets the information from the database
08:01
and it is placed in a very human readable form of a map because internally everything is zeros and ones. So, that is a PG routing. You can see the totality of our products right now. You go from OSM to PG routing and
08:27
from PG routing to QGIS. That's QGIS would be our front end and we're going to talk about where can I use PG routing. We're going to use PG routing on
08:43
graphs. What are the graphs? Graphs can be anything. For example, graphs can be represent rivers. We have many functions now, flow functions. The graphs can represent human relationships. Graph can represent data connections and what we
09:09
are used to is that they represent city roads. City roads, they can
09:23
represent city roads. Now, PG routing has been growing since 2013 that I arrived to it. So, let's see our evolution. When I arrived, the version 2.0 was about to be
09:41
released when I made my first open source contribution before this release and that is the total number of functions that were in that release. We had the incredible amount of 65 unit tests and
10:11
unfortunately, like a year and a half later, I noticed that if I put in the
10:22
compiling the flags of W error, W pedantic, I am very pedantic, so there were like 4,000 lines of warnings and what is a warning in one compiler can be an error in another compiler and I said this needs to be fixed. That's
10:43
when I gradually started to be more active in the project and soon that work will be shown in version 3.0 which I plan to release in September. We
11:02
have three classification of functions in version 2.3. We have the official functions which are the ones that you will see in front of the documentation. The proposed functions are the ones that can become official,
11:25
easier and experimental functions which are the ones that are recently created and we need the community to test it with real data, with real problems.
11:41
But in 3.0, we will have many classifications. For example, this you will have the old pairs already are in 2.0, the A star family of functions, the
12:04
bidirectional A star family of functions, the bidirectional Dijkstra family of functions. It's okay, it's working, thanks. The components family of functions, the
12:20
contraction of a graph, the Dijkstra family of functions, the flow family of functions, the spanning tree families that include Kruskal family of functions, Prim family of functions, the k shortest path which is Jens
12:42
algorithm, the turn restrictions shortest path, the travelling salesman problem functions, the driving distance category that include with Dijkstra as a back function to do it, the Prim and Kruskal functions. And we
13:08
now instead of 68 tests, we have 30,810 unit tests. So you saw that we had like
13:22
4,000 warnings and stuff. We still do have them, so you will know, oh yes there's still a bug, yes there's still a bug. During these four years that I've been actively in the project, there is this function that is a turn
13:44
restriction shortest path that is a very complicated to fix. And I decided okay, I mean this warning I can remove it easily, it's just a conversion of types. But if I leave it there, people will know that there are bugs in that
14:06
function when they compile. And if they don't believe that, then from the 30 something thousand function unit tests, you can see that all the failing
14:21
unit tests have to do with the turn restrictions shortest path function that P routing has. And it's going to be our policy that that function will remain like that until someone wants to rewrite that function. So it will be
14:42
like let's keep it there like it is. Now P routing has grown thanks to the students. So we have many contributions and these are the Google Summer of Code students. We have Hangwoo from this year's program. He created the
15:06
topological sort. This documentation that you can see here is the documentation that he created for this presentation. And he also created a
15:20
transitive closure function for graphs. And this is the documentation. It didn't take me to the link. Oh yeah. He also made his video. It's not
15:49
shown. I don't know how to do that. They told me to move it somewhere. Wait let me put it. That is Hangwoo working on this summer. And all those dots
16:24
represent the files he touched. And you can see that he worked. So
16:54
this is important for me for you to show because it's their students efforts. I'm going out and they're coming in. So how do I? I just cross it here. We go to
17:14
the next slide. Now the other student that we have for this year is Akil. And he made a breadth-first search function in in PG routing. That is a
17:29
documentation that he did for this presentation. And that is how P routing results look like when you use it. So it's a long process to use that
17:42
information and make a nice map with it. And he made a binary breadth-first search. And he also made an implementation of Edward Moore's algorithm. So he made a contribution of three functions and he also created his
18:08
his working video. I have to click it only right? You can find the videos in
19:05
YouTube. We have videos of all our students. It's basically the end. So from
19:31
2018 last year we have Mao Wang. He created a solution for the Chinese Postman problem. We have Aditya. He is the one that made Prim's algorithm
19:48
and Kruskal's algorithms. We had the Zurbach which now is was a mentor for the Google Summer of Code. And Ahish, Vidhan, Andrea, Rojiz, Sarfak that
20:11
made the PG routing improvements. And I give you thanks. And that's all. So these are this is my presentation about PG routing. If you have any
20:24
questions, we have five minutes to answer. Questions?
20:50
So we do use PG routing quite a lot for projects. Thank you for this nice product. I have a question about performance. Could you tell us a bit
21:02
about the size of the networks? What is a large network for you? Yeah, a large that always is going to be that will depend on your point of view. Of course, if I want to solve a problem of how do I get from here to
21:21
the corner, I won't put all Europe that it would be too large. But let's say I at least in my computer, which when I made some performance measurements that you can see in the documentation of the old pairs algorithm, there are some times I did some analysis about in my computer
21:45
with a that I have at home, which is actually slower than this one because I built it. And that one took around three seconds per million rows to upload to the algorithm to memory so that the algorithm can use
22:10
that information. So that was three seconds per million rows in my computer. Which means this one is faster. I haven't measured the speed.
22:24
But what it takes more time in PG routing is to upload convert that saved graph in the database into usable information in the algorithm. That was takes a lot of time. In our documentation, we try to put
22:43
the the all of the functions so you can see if I didn't go through the details, but it says the running time was an order of the number of edges plus the number of vertices. But that is when the
23:02
algorithm is running, the slowest part is uploading to memory. But it's only once. And that's why we created functions that go from one to one, one to many, many to one, many to many so that in one call,
23:20
you can solve many problems at the same time. So that is what we're trying to do in all the functions that require a source and a destination. Yes. Thank you. More questions? I'm glad that everything is clear as petrol.