State of 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 | 266 | |
| Autor | ||
| 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/66558 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Abstract |
|
FOSS4G Prizren Kosovo 202346 / 266
10
17
23
44
45
46
47
48
49
50
52
53
80
84
85
91
110
116
129
148
164
167
169
173
174
181
182
183
186
187
199
202
204
206
209
215
241
248
265
00:00
RoutingVorlesung/Konferenz
00:17
System-on-ChipSoftwareentwicklerEinsAvatar <Informatik>Projektive EbeneGrenzschichtablösungTermCodeAggregatzustandProgrammfehlerVorlesung/Konferenz
01:32
Open SourceNP-hartes ProblemProjektive EbeneGrenzschichtablösungRoutingVorlesung/Konferenz
02:10
SoftwareFunktionalProjektive EbeneDokumentenserverVorlesung/Konferenz
02:35
NetzbetriebssystemProgrammbibliothekRoutingVorlesung/Konferenz
02:56
Puls <Technik>Open SourceDatenbankProgrammbibliothekVorlesung/Konferenz
03:32
GraphRoutingOffene MengeSoftwareKartesische KoordinatenVorlesung/Konferenz
04:04
Plug inAutomatische HandlungsplanungElektronische PublikationKartesische KoordinatenMultigraphRoutingVorlesung/Konferenz
05:03
SpeicherbereinigungGraphKartesische KoordinatenSkalarproduktRoutingVorlesung/Konferenz
05:48
Treiber <Programm>SpeicherabzugRoutingSchnittmengePunktrechnungVorlesung/Konferenz
06:36
Topologischer VektorraumGeradeGraphSoftwareAuflösung <Mathematik>SelbstrepräsentationElementargeometrieExistenzaussageInformationKontextbezogenes SystemOrtsoperatorGefangenendilemmaRelativitätstheoriePunktRoutingVorlesung/KonferenzComputeranimation
08:46
DatenflussFunktionale ProgrammierungWasserdampftafelFunktionalVersionsverwaltungMathematikStandardabweichungGrenzschichtablösungCodeBitVorlesung/Konferenz
10:02
Funktionale ProgrammierungDijkstra-AlgorithmusCodeEinsSoftwaretestFunktionalVorlesung/Konferenz
11:11
Funktionale ProgrammierungDijkstra-AlgorithmusFunktion <Mathematik>Ein-AusgabeSchaltnetzPunktInformationsüberlastungFamilie <Mathematik>MatrizenrechnungFunktionalKategorie <Mathematik>TopologieBitDatenflussHochdruckQuellcodeRichtungMultiplikationsoperatorKostenfunktionOffene MengeVorlesung/Konferenz
12:52
CodeKategorie <Mathematik>FunktionalMultiplikationsoperatorGarbentheorieOffene MengeVorlesung/Konferenz
13:11
SpezialrechnerCodeProgrammbibliothekCodeVersionsverwaltungTrennschärfe <Statistik>Vorlesung/Konferenz
14:27
CodeSchaltnetzVorlesung/Konferenz
14:43
CodeMigration <Informatik>Funktionale ProgrammierungBijektionMigration <Informatik>SoftwareentwicklerKnotenmengePunktFolge <Mathematik>Physikalische TheorieAbfrageVerzweigendes ProgrammCodeDijkstra-AlgorithmusSchaltnetzEinsVorlesung/Konferenz
16:24
Funktion <Mathematik>Mengentheoretische TopologieMigration <Informatik>KnotenmengeEinfacher RingVersionsverwaltungAbfrageAusnahmebehandlungTopologieElektronischer ProgrammführerTabelleMigration <Informatik>EinsStichprobenumfangMathematikWeb-SeiteObjekt <Kategorie>QuellcodeCodeSchaltnetzFunktionalMereologieFunktionale ProgrammierungEinfach zusammenhängender RaumVorlesung/KonferenzComputeranimation
Transkript: Englisch(automatisch erzeugt)
00:08
Hello everybody, so we're going to talk about PG Routing and what's going on with it. So this is me, these are my avatars, you can find either on GitHub, LinkedIn or any
00:25
one of these ones, okay? I'm a freelancer developer, I'm the main developer of PG Routing, I'm also a project steering committee member of PG Routing and many other things. Today we're going to talk about the state of PG Routing, which is an OSEO community project,
00:48
but we don't want it to be an OSEO community project, so we're actually doing some incubation because we want to become an OSEO project.
01:01
And you can find the code in GitHub, so don't forget to get it, you are welcome to make contributions in terms of modifying the documentation, bug fixing, even just saying, hey, I found this problem, I don't know how to fix, but I found this problem, everything is welcome.
01:25
And PG Routing has several side projects, we have OSM to PG Routing, we also have PG Routing layer that it can be used in QEIS, we have a project that is starting
01:48
to take off, it's not a community project, it's VRP Routing, which solves several VRP routing problems that are NP-hard, and all of those are open source, and this is
02:11
the main PG Routing and the VRP Routing project is a spinoff of PG Routing, which already
02:23
has a couple of functions that are VRP, like a peak delivery, but they're moved to another repository because this one is using software that is not being packaged yet by Debian or other operative systems, so to keep on PG Routing alive, we need to
02:51
depart for those kind of problems. And both of them are libraries, okay, so these
03:01
are not made up solutions for any routing problems, and they are using, they have to be run on a Postgres, PostG's database, and then you can do your routing, and so basically
03:27
it's an open source, it's a library that runs in a database that is PostG's enabled, and then you have PG Routing. So, let's talk about OSM to PG Routing,
03:43
we use OSM data, open data, open software, we like openness, so OSM to PG Routing, it converts OSM data to something that can be used in PG Routing directly, but don't forget,
04:02
every graph will depend on your application, you still need to do final refinement for your graphs to do a real application, but this helps a lot. Currently, it only works on .osm files,
04:23
one of our plans is that it can also work for .pbf and .05m, so that it's more flexible, but it's a plan. About QGIS, we can plug in, we have the plug-in PG Routing layers that can be
04:51
used in QGIS, and again, it's basically, you have to think about it as it's something simple that you can use, so that you can see how it works, but it's not for a final application,
05:07
for a final application, you need to set up the working graph with all the details, but it helps a lot to see how PG Routing works. And vehicle routing problems,
05:23
like garbage collection, so you can see here, down here, it's a garbage truck, and this is Montevideo, and all the green dots are containers for garbage, and the trucks had
05:40
to go and pick up the containers, and we had to find for a fleet of trucks, they find the containers and make the smaller set of routes, so that is a vehicle routing problem, and it was like, they pick up the containers, the truck gets full, goes to the dump,
06:06
goes back to the depot, maybe to change drivers, and has to go back to the city. Okay, so that can be done with vehicle BRP routing. So, PG Routing, what do we think
06:23
about PG Routing? Well, it's basically, we think about routing, it's a we're here, and we want to go there, how do I do it? Well, in elementary school, they told us, hey, the closest, the shortest path is going to be a straight line between two points,
06:45
so we draw that, and then we put the same thing into context, and we'll say, oh, oh, something's wrong, so this PG Routing elephant has now the feathers, because it's a bird,
07:01
the bird can only do this kind of traversing the city of prison, and therefore, we're using PG Routing in a representation, in a graph representation of a city, which is this idea, this, you can see the intersections of the streets and the streets,
07:30
but the same graph, which is, let's say, we're representing the city with this graph, but the same graph, this is the same graph, with the nodes located in a different position,
07:44
and it can be a representation of the relation of the people, okay, and we don't have a latitude longitude attached to us, and PG Routing allows to find shortest relationships between people, how do I relate from nine to 15,
08:07
the shortest path, for example, that's, so it doesn't need to have a geometry attached, it's to solve graph problems, for example, also here, we want to set up a network,
08:24
how we can do it, we can also represent, it's the same graph, basically, no, this one is different, but we can represent everything with a graph, and you don't necessarily have latitude and longitude attached to this information, the rivers, this one have latitude
08:47
and longitude, we have some functionality that works for flow, flow functions, so you can analyze the flow of the water in this river, which is the Nile,
09:04
and this week, during the code sprint, we will work in 3.5 and soon on September 2023, September this year, November probably, we will have a version 3.6,
09:25
not so soon, we will have a version 4.0, might happen on 24, might happen on 25, originally, I was planning to do it for 23, but it's getting a bit too big,
09:43
and we are doing some improvements, standardization, and let's talk about our functions and what we want to achieve, so we have several classifications, official, proposed, and experimental functions, official functions normally
10:04
don't change, but on 3.5 PGR Dijkstra, which is our main function, the easiest one, the first one that people learn, it's the first one that we teach in the workshop,
10:21
it's changing, has changed already. Proposed are, they're ready, we feel that they do not have bugs, and in the next major release, they might or they might not become official, and experimental, it's normally are functions that were added by other contributors that need
10:49
some refinement and that need code cleanup, that need more tests, because I'm a test freak, so we need to test a lot to become proposed and from proposed to become official, okay,
11:07
so we have those classifications, so the official ones are the more stable ones, but as I mentioned PGR Dijkstra, which is an official one, is changing on 3.5,
11:22
and we have for each function, many overloads, one to one, one to many, many to one, many to many, and combinations, it's from one source, from one departure point to one destination, and so on, okay, so the same function with many overloads, you can do many queries
11:50
with many to many, for example, so we have many families, all pairs, a star,
12:02
with directional a star, Dijkstra, and families flow, for flow, cross code, prim, topology, and reference, so we have them kind of grouped in families, and we want to standardize the input and the output, okay, so I'm going to skip a little bit of other categories, oh,
12:25
we have the cost functions with PGR Dijkstra, PGR Dijkstra cost, PGR a star, PGR a star cost, so the suffix is adding the cost, the cost matrix, and so on,
12:41
and we have the with points are all proposed, they haven't been moved up, because I know they have an issue, if there's an issue open about that, and I haven't got the time to fix that issue, they're usable, but I don't like that section of the code I wrote, and we have the via
13:06
functions also, so Dijkstra via, everything ends with that category, so as I mentioned, we are changing the code, and let's understand first the version that we're using of PGRouting,
13:27
if you run select version and library from PGR full version, you get two values, one is the SQL version, and the second value is the C++ code that is being used by that SQL
13:51
version, so here, and it's saying that the SQL that it's been used is 3.1.3,
14:02
and the library is 3.6.0, which means that you can run anything with this SQL, and with this library, when we make a new release of PGRouting, we're not breaking the major,
14:24
so your code will work, your SQL code will work, you don't need to do anything, it will work, so with that combination of SQL and C++ code, we can do a select,
14:48
and I'm choosing all the columns that come from PGR Dijkstra, so this function is 3.1, and we get the following columns, sequence, path sequence, node, edge, cost, and aggregate cost,
15:04
that will remain the same, it's working perfectly, but let's see what happens if I'm using, for example, 3.6.0 dev, remember this is for September or something, but you can try out 3.6
15:23
dev, it's in the develop branch of PGRouting, with the 3.6 C++ code, and we run the same query, we get these two additional columns that are startVID and endVID,
15:43
the thing is that the many-to-many function and the combinations ones have all these columns, but the one-to-one does not have a startVID and endVID, because in theory, the person that is coding is saying, well, I'm going from vertex one to vertex three,
16:06
I'm remembering it, but in reality, it's not happening, so we're returning that column now, so to prepare for the migration, we recommend not to use the select star and use the exact
16:30
names of the columns, and these query as it is will run with both versions of the
16:41
SQL code, in combination with the C++ code, we have new topological functions, and we are going to be deprecating these ones, I think we're going to be doing that very soon, it's going to be part of 3.6, and actually, since version 3.3.2,
17:08
we're not using any of these functions in the documentation, except on the page of the documentation of the functions, but for the sample data, we're not using any of these functions, so there, with the functions, the new ones, you can work them out, so
17:29
basically, use everything, the new one, pgr, extract vertices, save on a table, and then update source, update target, and then you have a topology, a working topology,
17:47
so also this one is being deprecated, and you have to use different things depending on your objective, you can use connected components, this new function, or any of the
18:02
post GIS functions, and you have a migration guide that you can always check, since we started making these changes, so there is a migration guide, and keep on routing!