Shortest path in the database and more with pgRouting
This is a modal window.
Das Video konnte nicht geladen werden, da entweder ein Server- oder Netzwerkfehler auftrat oder das Format nicht unterstützt wird.
Formale Metadaten
| Titel |
| |
| Serientitel | ||
| Anzahl der Teile | 295 | |
| Autor | ||
| Mitwirkende | ||
| Lizenz | CC-Namensnennung 3.0 Deutschland: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen. | |
| Identifikatoren | 10.5446/43351 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Abstract |
| |
| Schlagwörter |
FOSS4G Bucharest 2019232 / 295
15
20
28
32
37
38
39
40
41
42
43
44
46
48
52
54
57
69
72
75
83
85
87
88
101
103
105
106
108
111
114
119
122
123
126
129
130
131
132
137
139
140
141
142
143
144
147
148
149
155
157
159
163
166
170
171
179
189
191
192
193
194
195
196
197
202
207
212
213
214
215
216
231
235
251
252
263
287
00:00
SoftwareentwicklerE-MailRoutingProdukt <Mathematik>GraphentheorieZeitabhängigkeitFamilie <Mathematik>SoftwareentwicklerE-MailGraphentheorieBitCoxeter-GruppeWikiRoutingSoftwareProdukt <Mathematik>t-TestProjektive EbeneComputeranimation
01:24
Open SourceGerichteter GraphVorzeichen <Mathematik>Coxeter-GruppeFunktionalOpen SourceProgrammbibliothekDatenbankBildgebendes VerfahrenSoftwareComputeranimation
02:35
MereologiePunktGeradeHilfesystemComputeranimationDiagramm
03:18
MehrrechnersystemPhysikalische TheorieComputeranimation
03:37
ImplementierungAlgorithmusCASE <Informatik>GravitationRechter WinkelResultanteFunktionalPhysikalische TheorieRechenschieberSoftwaretestVorzeichen <Mathematik>RoutingDiagramm
05:30
InformationsspeicherungGravitationProdukt <Mathematik>Physikalische TheorieChord <Kommunikationsprotokoll>GeradeVorlesung/Konferenz
07:17
RoutingMAPUmsetzung <Informatik>DatenbankRoutingInformationBildschirmmaskeEinsPlug inDatensichtgerätProdukt <Mathematik>FehlertoleranzTotal <Mathematik>Offene MengeComputeranimation
08:17
Total <Mathematik>GraphentheorieRoutingProdukt <Mathematik>Basis <Mathematik>DebuggingRohdatenGraphComputeranimation
08:46
GraphentheorieSelbstrepräsentationFunktionalGraphZusammenhängender GraphDatenflussAbstimmung <Frequenz>Computeranimation
09:23
Mengentheoretische TopologieFunktion <Mathematik>AbstandKnotenmengeMultigraphSchnelltasteAlgorithmusJensen-MaßShape <Informatik>PolygonNormalvektorFahne <Mathematik>EvolutePunktCompilerFunktionalProjektive EbeneOpen SourceRechenwerkVersionsverwaltungZahlenbereichFehlermeldungTotal <Mathematik>GeradeKomponententest
10:48
Funktion <Mathematik>GraphIsolation <Informatik>RechenbuchAlgorithmusGruppenoperationMultigraphChi-Quadrat-VerteilungEin-AusgabeZellularer AutomatAbstandVerschlingungShape <Informatik>Jensen-MaßVersionsverwaltungAutomatische HandlungsplanungPunktFunktionalTUNIS <Programm>EinsFamilie <Mathematik>TypentheorieProgrammfehlerTopologieUmsetzung <Informatik>KomponententestDesign by ContractAbstandRechenwerkKategorie <Mathematik>Travelling-salesman-ProblemZusammenhängender GraphDatenflussAlgorithmusTermBus <Informatik>Vorzeichen <Mathematik>SystemaufrufGraphRichtungKlasse <Mathematik>SoftwaretestLesen <Datenverarbeitung>Web logProjektive EbeneComputeranimation
14:43
CodeGoogolt-TestMaschinencodeQuick-SortSchlussregelGoogolProgrammierungComputeranimation
15:05
Dynamisches RAMAlgorithmusKnotenmengeComplexity <Algorithm>MultigraphOrdnung <Mathematik>TabelleSchwimmkörperReverse EngineeringGerichteter GraphInnerer PunktQuick-SortMengentheoretische TopologieAlgebraisch abgeschlossener KörperGruppenoperationZusammenhängender GraphBeschreibungskomplexitätDatenstrukturCoxeter-GruppeAlgebraisch abgeschlossener KörperFunktionalMultiplikationsoperatorGraphentheorieGruppenoperationComputeranimation
15:24
SchwimmkörperGerichteter GraphInnerer PunktRoutingDatenbankVisualBASICVideokonferenzVerschlingungBestimmtheitsmaßMultiplikationsoperatort-TestElektronische PublikationSkalarproduktRechenschieberComputeranimation
17:15
KnotenmengeBeschreibungskomplexitätAlgorithmusGraphDickeGerichteter GraphMultigraphWurzel <Mathematik>Kontextbezogenes SystemMAPPortscannerSchwimmkörperInnerer PunktRoutingFunktionalProzess <Informatik>Computeranimation
17:34
KnotenmengeAlgorithmusDijkstra-AlgorithmusGraphGewicht <Ausgleichsrechnung>BeschreibungskomplexitätMultigraphBinärdatenDickeGanze ZahlVersionsverwaltungGerichteter GraphReverse EngineeringNegative ZahlGewichtungMaßerweiterungPetaflopsPROMCodeGoogolSystem-on-ChipE-MailResultanteProzess <Informatik>VideokonferenzBriefträgerproblemFunktionalAlgorithmust-TestBinärcodeHypermediaImplementierungYouTubeComputeranimation
19:42
AlgorithmusAlgorithmusGoogolComputeranimationDiagramm
20:00
CodeGoogolCodierungstheorieInformationCoxeter-GruppeBitMultigraphRoutingSoftwareProjektive EbeneProdukt <Mathematik>SichtenkonzeptPunktSimulationComputeranimation
21:11
InformationEinflussgrößeNeuroinformatikSichtenkonzeptMultiplikationsoperatorGesetz <Physik>Computeranimation
21:40
InformationNeuroinformatikMultiplikationsoperatorHalbleiterspeicherARM <Computerarchitektur>ZweiAlgorithmusFunktionalEinsZahlenbereichBenutzerfreundlichkeitInformationWhiteboardAllegorie <Mathematik>SystemaufrufDatenbankMereologieDatensatzGraphMultigraphKnotenmengeHypergraphGerichteter GraphVorlesung/Konferenz
23:43
Information
Transkript: Englisch(automatisch erzeugt)
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.