Route Planning in your Database 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 | 183 | |
| Author | ||
| License | CC Attribution - NonCommercial - ShareAlike 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 and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this | |
| Identifiers | 10.5446/32138 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language | ||
| Producer | ||
| Production Year | 2015 | |
| Production Place | Seoul, South Korea |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
FOSS4G Seoul 2015125 / 183
7
8
47
53
54
65
73
74
79
82
84
92
102
103
105
124
126
127
130
141
142
143
156
161
162
170
176
178
181
183
00:00
DatabaseLine (geometry)Functional (mathematics)Key (cryptography)MereologyExtension (kinesiology)Projective planeField (computer science)Point (geometry)Food energyNumberSoftware developerLengthOpen sourceParameter (computer programming)InformationRevision controlTransformation (genetics)CASE <Informatik>ArmCollisionMultiplication signPresentation of a groupGraph (mathematics)CausalityOnline helpTable (information)WeightCellular automatonRoutingGraph (mathematics)Library (computing)State of matterQuantumSocial classComputer clusterRow (database)Level (video gaming)Computer configurationSequenceLetterpress printingCartesian coordinate systemArithmetic meanMetropolitan area networkPlanningEndliche ModelltheorieIntegrated development environmentFocus (optics)Query languageGodRoutingForm (programming)AngleDifferent (Kate Ryan album)Division (mathematics)Computer animation
07:20
Connected spaceQuery languageVideo gameSemiconductor memoryMereologyLibrary (computing)Process (computing)Food energyGraph (mathematics)Software developerFunctional (mathematics)Augmented realityGraph (mathematics)Revision controlSystem callOrientation (vector space)outputCartesian coordinate systemPairwise comparisonDatabaseMoment (mathematics)Grass (card game)Game controllerLine (geometry)ResultantCodeDistanceNumeral (linguistics)CASE <Informatik>Multiplication signFlagWeb pageReverse engineeringPlanningControl flowGraph coloringIntegerTowerResolvent formalism
14:37
Power (physics)Graph (mathematics)Gene clusterParallel portResultantCondition numberRootSoftware developerCodeReverse engineeringRepresentation (politics)WeightConnected spaceFunctional (mathematics)MassSampling (statistics)AlgorithmFile formatInformationCausalityProcess (computing)Graph (mathematics)Electronic signatureSummierbarkeitLine (geometry)Arrow of timeSystem callFormal grammarFlow separationMoment (mathematics)Duality (mathematics)Degree (graph theory)Default (computer science)Bounded variationDatabaseTable (information)FrequencyMultiplication signCore dumpQuantum gravityInterface (computing)Plug-in (computing)Presentation of a groupFlagSet (mathematics)RoutingDigitizingBefehlsprozessorCoroutineInterior (topology)
21:54
Computer animation
Transcript: English(auto-generated)
00:03
Thank you. I'm going to talk about the shortest path searching your database and more. Part of the more is the love of my work to what I do. So the first thing I'm going to show you is a poem. It's a poem that read in Spanish says
00:27
Which in English, walk. Your footprints are the path and nothing more. Walker, there is no path. The path is made when walking. That poem is
00:41
from Antonio Machado. So after that poem let's start presenting myself. I am Celia Virginia Vergara Castillo. I am an economist. Yes that's why there's a line there that I'm known as Vicky. So please call me Vicky when you find me on the
01:03
way. My name is pretty long. I'm going to talk about the peer routing project. I'm going to give two focuses. One is like for the developer for the end user. The other one is going to be like focusing for the developer of another
01:22
functionality for the peer routing. So the first thing is I'm going to say thank you to all those open source projects that because they are we can be. So thanks to PostgreSQL, PostGIS, the C++ graph library and thanks to
01:46
them we're also proud to be also an open source project. Please don't forget to focus on GitHub. First thing, what's PG routing? PG routing is a library that is
02:03
going to provide functionality in the database for routing. Which by the way took me here. I wanted to route one day from my house to my dad's house and that's why I'm here right now. That was like three years ago. So let's start
02:25
routing. When you want to route you want to see what's your application and then you go to the manual and see oh I have all these options. So right now my application is I want to make this presentation and I'm choosing from all these functions Dijkstra. So let's try to do that routing with Dijkstra.
02:48
The first thing we have to do we have to create our database and because we are an extension of PostGIS we need to create the PostGIS extension and then we create our extension that is peer routing. Once well
03:07
after that we need to load our data maybe do some transformations and we can do an SQL query. In this case we chose Dijkstra and we have in this case four
03:20
parameters. The first parameter is a text that's going to give the information in a form of an SQL about the edges of the graph that we're going to be using to do our routing. Then the 30 is that I want to
03:41
route from point 30 that it's Vicky's house and I want to go to point 60 that is Vicky's father's house using an undirected graph. Maybe we're going walking so it doesn't matter if I go or come through an edge. After that
04:01
whoops that came pretty ugly in here but there's a table you can see we get a sequence of edges or we can get a sequence of nodes we get the cost and we get an aggregate cost so let's analyze a little bit. Going from node
04:24
30 to node 44 we're using edge 53 and the cost of that edge is these 591 10,000 and the aggregate cost you can see that it's all over to the next row
04:42
because the aggregate cost of reaching node 30 because I'm starting from node 30 well it's zero I haven't moved so we should remember this because I'm going to mention that remember that table well it will be this table.
05:04
I'm an economist I told you right so this is like part of my field is everything is linked together costs costs can be virtually anything whatever you want time length energy so let's see first let's say that it's like
05:30
angle my cost will be based on an angle I can see for this edge A that if I go down well even the balls roll so I'm going faster if I go up I
05:49
finish tired so I multiply them by the different number or division also it's the same things just written differently and then I modify the cost
06:02
of the length it's like and go faster it's going I'm going to reduce the cost the next example it's when well the street is not so pretty and it's like kind of muddy so this one is based on the time maybe I have a time parameter
06:23
somewhere in my database and I'm going to multiply it by a wet penalty because it's very muddy okay now we want to route cows and the cows we are not going to route them in a residential area so how are we going to
06:41
tell PG routing that we don't want these cows to go in front of my house we're going to tell it using a negative sign because our functions will not insert edges that have a negative value okay and in this case we're saying that the reverse cost the cows go or the cows come will be
07:04
the same on the rural edges finally well the other day somebody took me hiking and thanks God it wasn't snowing oh we can also use values that
07:22
probably we didn't even think in this case I'm thinking about calories the cost is going to be based on calories so going up more calories going down less calories snowy things good it didn't snow I alive okay so this is
07:41
the end of the first part it's about the the user I'm going to do this routing so this is what's going on it includes something about the final
08:01
that wants to do more functionality in p-routing so it's towers version 3.0 and we have some goals goals for developers the boost functions for the graph aren't very easy to follow so we want to make these use of directed
08:26
undirected graph of boost more clean and more nice for developers that aren't used to coding c++ and we want to create an internal library for goals
08:40
that we have for our users is to support big integer like all the data from OSM have the big integer is like everybody wants big integer there's no problem let's do it and we want to avoid user contradictory input and you
09:02
will see why in a moment and there's this idea we want to keep the graph in memory to speed up subsequence requests that way you won't feel that it takes too long so here's our roadmap we want to minimize and find
09:22
our path to go from 2.0 to the future this is how p-routing works you have your application you make a query to the database the database Mesa connection they with the connection the graph starts to be built and the more edges
09:45
your graph has the more time it's going to take and the more worrying in the talk is going to be and then even pictures got sleeping once the graph finishes loading we can process it we give the result back the connection
10:06
disappears and if we want to make the same query well we have to go through all that process again so that's part of the we want to keep the graph in memory to make subsequence requests without being having to load
10:23
the graph again that is one thing so another thing that is focused on developers we have this cool code and we need I'm doing this new complicated code and I saw that in another routing function there is these
10:43
500 lines of complicated code that I can use so I make a copy well that complicated code it was 500 lines I'm not going to find the
11:03
unresolved issue so what is happening it's that that that unresolved issue has been spreading around now let's talk about the user contradictory input here is the flag that says that I don't have reverse cost column and what do
11:26
you see here reverse cost column so do I have it or I don't have it me as routing well then I can do whatever because you're not decided in here well here's the true and I don't see it so what what do I have to do will remove
11:46
that flag and if they if if I see it then the user wants to use it if I don't see it then the user doesn't want to use it so we have a plan and
12:04
our plan is first of all make precise definitions of graphs and have a gradual creation of that internal library that will avoid that copy paste with a resolve issue and do incremental releases the last time PG routing was
12:27
released was in 2013 well that the previous to the last so in two years nothing was developed because there was this kind of issue that didn't allow us to do more so we are this is 2.0 we want to get here using a
12:48
library approach so PG routing will have a library and if PG routing is a library for for the database so it's kind of a library of a library now 2.1
13:03
2.1 was released like in the 7th of this month so just before coming to the to the orient and this is what it has for this release because it was made
13:23
so fast it was decided that the documentation will remain so that people can have the chance to compare what was it and what's going to be using the functions that were modified the functionality that was modified was KSP
13:44
driving distance and extra so of course for backwards compatibility the functionality remains but the documentation you will be able to see how it was before so that you can make this comparison and say oh yes we
14:04
are getting somewhere and whenever it is possible I will be adding more functionality especially when it doesn't break more so we have here that not only we can make use of begin we can basically make use of any kind of
14:26
integer when it's an ID or any numerical when it's a cost or reverse cost columns and we also did our precise definition of what is a weighted
14:41
undirected graph here it is what does that says that simple we have from 3 to 6 cost 40 and the reverse cost is 38 from 3 to 8 25 so this is how we store
15:01
the information in the database and this is what it's interpreted when we are processing it which are two very different things this is just like the same this is the precise definition of the weight undirected graph and for
15:27
the weighted undirected graph with the same data that I showed you can see that the arrow going and coming are shown in each one I'm going to be
15:41
representing that with a line without arrows and I mentioned that well now also this is the precise definition of what the results of the Dijkstra will be interpreted on the table remember that table that I told you remember the table at the beginning well this is basically saying mathematically what I
16:05
did verbally describing that table now there in the documentation we always use the sample data of the documentation so what I call it and all
16:21
the functions there are examples using that sample data so I actually made all the possibilities for that sample data how it looks weighted with reverse cost unweighted without reverse cost so that you can see what happens
16:42
if you say I want to work my data without a non-directed graph with weighted with reverse cost or what happens if I don't put the reverse cost so now let's see how the signature looks I can see the reverse
17:04
cost here so I want to use it so that says with reverse cost and the only flag I have to worry is the undirected or the directed flag in here it says false so I don't want the directed graph I want the undirected one I don't
17:25
see reverse cost and I'm still working in an undirected graph so let's see what happens with the directed graph the same thing the reverse cost there I want to use it it's not there I don't want to use it there's a true I want
17:43
to use a directed graph but also there is this default if you don't write that true the default is going to be true and the reason for that is that you well I'm going to say the reason the reason for that is that when you have a graph you can represent an undirected graph on a directed graph but
18:05
not the contrary so my time is running out we have many variations one too many many too one many too many and I'm going to say that for 2.2 this will
18:22
be the functionality but the documentation of the 2.0 will disappear so we're keeping the backwards compatibility the eventually we will reach to 3.0 and this is how I want the final thing too that's the
18:46
famous idea okay I think my time is over thank you very much thanks very much thanks for the metaphor for your presentation questions please yes please
19:15
in my opinion some routine algorithm like the a star like the digital slot
19:22
it's hard to be implemented in a parallel style I mean for now for nowadays issue CPU have multi-core but I think we do we have some method to implement the PG routine and all the inner algorithm in parallel in parallel
19:42
way okay basically most of the the algorithms about PG routing there for solving very complex problems and I yes I've been thinking oh I want to use parallelism but if you go to the documentation about the connection with
20:01
Postgres it tells you don't do parallelism don't don't spread out there are reasons that are unknown for me in this moment but one of that's why I want these detachment to be done eventually like okay I call
20:23
Postgres for once and then everything is in there then eventually I will be able to make PG routing to run in parallel and use several cores thank
20:45
you for your effort sorry in the past I've tried to use PG routing on QG's interface and I really not getting any headway but when I try to lay my hand on this particular plugin in QG's graph route and graph route
21:05
you understand the result was quite incredibly that way that we can make this interface oh you're using it with QG's the developer for the QG's layer for PG routing he's not right now I don't know how he developed but
21:24
for sure I'm sure that if you were using a small data set you're noticing very weird things remember the copy the code with an unresolved issue they own results each are still there you don't notice the mistake if you're using
21:45
a large data set okay thank you very much Vicky