„PgRouting” változatai közötti eltérés
(→Hivatkozások) |
Mate (vitalap | szerkesztései) a |
||
(43 közbenső módosítás, amit 4 másik szerkesztő végzett, nincs mutatva) | |||
1. sor: | 1. sor: | ||
− | + | A '''pgRouting''' egy <span class="plainlinks">[https://hu.wikipedia.org/wiki/Ny%C3%ADlt_forr%C3%A1sk%C3%B3d%C3%BA_szoftver nyílt forráskódú]</span>, <span class="plainlinks">[https://hu.wikipedia.org/wiki/C%2B%2B C++]</span> nyelven írt bővítmény a [[PostGIS]]/<span class="plainlinks">[https://hu.wikipedia.org/wiki/PostgreSQL PostgreSQL]</span> térinformatikai adatbázisokhoz. Lehetővé teszi <span class="plainlinks">[https://hu.wikipedia.org/wiki/Gr%C3%A1f gráf adatszerkezetek]</span> kezelését, így például legrövidebb utakat, csomópontok távolságát és egyéb hálózati elemzést igénylő feladatokat oldhatunk meg vele. A programcsomag <span class="plainlinks">[https://hu.wikipedia.org/wiki/GNU_General_Public_License GNU GPL v2]</span> licenc alatt használható. | |
− | A pgRouting egy nyílt forráskódú, C++ | + | Elődje volt a pgDijkstra, amelyet később kiterjesztettek és pgRouting-nak neveztek el. Napjainkban a fenntartását a Georepublic, az iMaptools és a felhasználók végzik. |
+ | |||
+ | '''OSGeo''' | ||
+ | |||
+ | A pgRouting az OSGeo Foundation-nek egy OSGeo Labs projektje és része az OSGeo Live-nak, ami egy hordozható szoftver, mellyel ki széles körben ki lehet próbálni térinformatikai szoftvereket installálás nélkül. | ||
+ | Teljesen ingyenes, szabadon használható, módosítható és dokumentációt, valamint mintaadatokat is tartalmaz. | ||
+ | |||
+ | A pgRoutingot sokféle módon tudjuk használni, adatmódosítást is több különböző szoftverrel is végezhetünk, pl. pgAdmin, QGIS használatával, vagy konkrét Pl/pgSQL utasítások használatával. Az adatmódosításokat a routing engine azonnal elvégzi és a "cost" paraméter kiszámítása is működik dinamikusan. | ||
== Telepítés == | == Telepítés == | ||
− | A PostGIS újabb verziói (2.0+) már tartalmazzák a | + | A PostGIS újabb verziói (2.0+) már tartalmazzák a pgRouting csomagot, így nem szükséges külön telepíteni, csak aktiválni kell, a következő módon. |
− | < | + | <syntaxhighlight lang="sql"> |
CREATE EXTENSION pgrouting; | CREATE EXTENSION pgrouting; | ||
− | </code> | + | </syntaxhighlight> |
+ | |||
+ | A teljes telepítési útmutató elérhető a pgRouting honlapján. | ||
+ | Természetesen különböző platformokra is elérhető a csomag: Linux, MAC OS és Windows alá is. | ||
+ | |||
+ | Én a Windows verziót választottam. | ||
+ | A pgRouting honlapján lévő hivatalos telepítési útmutató alapján hosszas, bonyodalmas telepítésre számítottam, de meglepően egyszerűnek bizonyult. | ||
+ | Nem kell más, csak egy PostgreSQL és a hozzá tartozó, megfelelő verziójú PostGIS, amelyet a kapcsolódó StackBuilder-rel automatikusan, könnyen telepíthetünk. | ||
+ | |||
+ | Elérhetőek más kiterjesztések is, én csak a PostGIS-pgRouting kombót választottam. | ||
+ | |||
+ | Telepítés után az úgy nevezett pgAdmin alkalmazást kell elindítani és ebben kell csatlakozni az adatbázisunkhoz. | ||
+ | Az adatbázis futhat localhost-on, sőt, egy kezdeti adatbázist már a PostGIS telepítése során létrehozhatunk. | ||
+ | |||
+ | Az adatbázis jelszóval védett és különböző felhasználókat is létre lehet benne hozni, majd a táblákról megmondani, kiknek van hozzá jogosultsága - tehát itt semmi meglepetés nincs. | ||
+ | |||
+ | Grafikus megjelenítéshez a QGIS programcsomag megfelelő választás lehet. | ||
+ | |||
+ | == Felépítés == | ||
+ | |||
+ | A pgRouting két fő összetevőből áll: | ||
+ | * Egy C modul, amely egy PostgreSQL-ben átadott lekérdezést használ a gráf felépítéséhez. | ||
+ | * C++ modulok, amelyek a lekérdezést úgynevezett boost gráffá alakítják, és futtatják az útvonal-választást. | ||
+ | |||
+ | Hogy mely összetevőt használja a program futása során, az az algoritmus fajtájától függ. | ||
+ | |||
+ | A függvénykönyvtár szerkezete pedig a következőképp néz ki: | ||
+ | <pre> | ||
+ | cmake/ - cmake fájlok | ||
+ | CMakeLists.txt - Top level cmake | ||
+ | doc/ - Top level doc, a nem forrásalgoritmus-specifikus dokumentáció helye | ||
+ | themes/ - Sphinx téma a doc-nak | ||
+ | static/ - dokumentáció képei | ||
+ | src/ | ||
+ | astar/ - A* algoritmus | ||
+ | common/ - pgRouting projektekben szükséges közös fájlok | ||
+ | dijkstra/ - Dijkstra algoritmus | ||
+ | driving_distance/ - Vezetési távolság | ||
+ | trsp/ - Legrövidebb utak kanyarodási korlátokkal | ||
+ | tsp/ - Utazó ügynök | ||
+ | tools/ - Tesztelési eszközök | ||
+ | </pre> | ||
+ | |||
+ | Az src mappa minden könyvtárában <code>doc</code>, <code>sql</code>, <code>src</code>, és <code>test</code> almappák találhatók, melyekbe értelemszerűen a következők kerülnek: | ||
+ | *'''doc''': Az adott algoritmushoz szükséges összes dokumentáció ReStructuredText formátumban. Ennek célja, hogy a függvények leírásával, input és output paraméterek megadásával a felhasználók számára érthetővé tegye, hogyan működik az algoritmus. | ||
+ | *'''sql''': Az sql burkolók a C kódhoz. | ||
+ | *'''src''': C/C++ kód az algoritmushoz. | ||
+ | *'''test''': <code>test.conf</code>, <code>*.data</code>, <code>*.test</code>, és <code>*.rest</code> fájlok az algoritmus teszteléséhez. | ||
+ | |||
+ | Fejlesztési célból a programot klónozhatjuk Git-en keresztül, majd telepítjük a következők szerint: | ||
+ | |||
+ | <syntaxhighlight lang="bash"> | ||
+ | git clone git@github.com:pgRouting/pgrouting.git | ||
+ | cd pgrouting | ||
+ | cmake -DWITH_TSP=ON -DWITH_DD=ON . | ||
+ | make | ||
+ | sudo make install | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | A 2.3 pgRouting library tartalma/leírása <span class="plainlinks">[http://docs.pgrouting.org/2.3/en/doc/index.html itt]</span> található. | ||
== Használat == | == Használat == | ||
13. sor: | 79. sor: | ||
A vektoros térképi adatok adatbázis-táblába betöltésére számos eszköz áll rendelkezésre, például: | A vektoros térképi adatok adatbázis-táblába betöltésére számos eszköz áll rendelkezésre, például: | ||
− | * '''osm2po''': OpenStreetMap (OSM) adatok konvertálása SQL formátumba, pgRouting-nak megfelelő formátumban | + | * '''osm2po''': OpenStreetMap (OSM) adatok konvertálása SQL formátumba, pgRouting-nak megfelelő formátumban (hasonló hozzá az osm2pgrouting is, de ez sajnos egy ideje Windows alatt nem működik). |
− | * '''shp2pgsql''': PostgreSQL shapefile betöltője | + | * '''shp2pgsql''': PostgreSQL shapefile betöltője (az újabb verziójához GUI is tartozik, mellyel könnyen lehet shapefile-okat betölteni). |
− | * '''ogr2ogr''': | + | * '''ogr2ogr''': Vektoros adatok konverziója. |
− | * '''osm2pgsql''': OSM adat betöltése postgreSQL-be | + | * '''osm2pgsql''': OSM adat betöltése postgreSQL-be. |
'''Előfeldolgozás''' | '''Előfeldolgozás''' | ||
22. sor: | 88. sor: | ||
Amikor egy GIS fájlt olvasunk be az adatbázisunkba a pgRouting számára, nem feltétlenül követnek alkalmas topológiát a rekordok. A helytelen topológia hibás útvonalakhoz vezetne. Hogy használható adattáblát kapjunk, csomópontokra van szükségünk minden egyes útkereszteződésnél. Az útvonalhálózat megfelelő topológiájának kialakítását segítheti a pgr_createTopology vagy a pgr_nodeNetwork parancs. Működésük hasonló. Az utóbbi beolvassa a „csúcstalan” hálózat adatbázis-tábláját, majd egy új táblába írja a már felcsúcsozott éleket. Paraméterei | Amikor egy GIS fájlt olvasunk be az adatbázisunkba a pgRouting számára, nem feltétlenül követnek alkalmas topológiát a rekordok. A helytelen topológia hibás útvonalakhoz vezetne. Hogy használható adattáblát kapjunk, csomópontokra van szükségünk minden egyes útkereszteződésnél. Az útvonalhálózat megfelelő topológiájának kialakítását segítheti a pgr_createTopology vagy a pgr_nodeNetwork parancs. Működésük hasonló. Az utóbbi beolvassa a „csúcstalan” hálózat adatbázis-tábláját, majd egy új táblába írja a már felcsúcsozott éleket. Paraméterei | ||
* éltábla neve, | * éltábla neve, | ||
− | * tolerancia: a toleranciaértéken belüli csomópontok egy csomópontot fognak alkotni | + | * tolerancia: a toleranciaértéken belüli csomópontok egy csomópontot fognak alkotni, |
* id, az éltábla elsődleges kulcsa, | * id, az éltábla elsődleges kulcsa, | ||
− | * geometriát tartalmazó oszlop | + | * geometriát tartalmazó oszlop, |
* kimeneti tábla szuffixe. Alapértelmezetten edge_table_noded. | * kimeneti tábla szuffixe. Alapértelmezetten edge_table_noded. | ||
+ | |||
+ | Előfordulhat olyan eset is, amikor a pl. shapefile-ból betöltött táblánkon nem tudunk automatikusan topológiát építeni, mivel csak egy "geometry" típusú oszlopból tudjuk, hol van az elhelyezkedése, azaz nem tudjuk a start és az end csúcsát. | ||
+ | Szerencsére erre is van megoldás: | ||
+ | |||
+ | 1. Létrehozunk egy view-t, amelyikbe kiszámoljuk az adott geom start és end csúcsát (ebben az esetben a road táblán hajtjuk végre az átalakítást). | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | CREATE OR REPLACE VIEW road_ext AS | ||
+ | SELECT *, startpoint(the_geom), endpoint(the_geom) | ||
+ | FROM road; | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | 2. Létrehozunk egy táblát, amelyben az egyes csomópontokat tároljuk, és ezeknek adunk egy unique ID-t is. | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | CREATE TABLE node AS | ||
+ | SELECT row_number() OVER (ORDER BY foo.p)::integer AS id, | ||
+ | foo.p AS the_geom | ||
+ | FROM ( | ||
+ | SELECT DISTINCT road_ext.startpoint AS p FROM road_ext | ||
+ | UNION | ||
+ | SELECT DISTINCT road_ext.endpoint AS p FROM road_ext | ||
+ | ) foo | ||
+ | GROUP BY foo.p; | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | 3. Ahhoz, hogy bejárható hálózatot kapjunk, létrehozunk egy táblát az eredeti és a csomópontok összejoin-olásával. | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | CREATE TABLE network AS | ||
+ | SELECT a.*, b.id as start_id, c.id as end_id | ||
+ | FROM road_ext AS a | ||
+ | JOIN node AS b ON a.startpoint = b.the_geom | ||
+ | JOIN node AS c ON a.endpoint = c.the_geom; | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | 4. Majd, ha akarjuk létrehozunk spatial index-et a lekérdezések hatékonyabb végrehajtása érdekében. | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | CREATE INDEX road_gist ON road USING GIST (the_geom); | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | 5. Már mehetnek is a lekérdezések! | ||
'''Lekérdezés szintaxis''' | '''Lekérdezés szintaxis''' | ||
+ | |||
Minden pgRouting lekérdezés az alábbi formátumot követi: | Minden pgRouting lekérdezés az alábbi formátumot követi: | ||
− | < | + | <syntaxhighlight lang="sql"> |
SELECT pgr_<algorithm>(<SQL for edges>, start, end, <additonal options>) | SELECT pgr_<algorithm>(<SQL for edges>, start, end, <additonal options>) | ||
− | </ | + | </syntaxhighlight> |
− | ahol a <code>pgr_</code>előtaggal hívjuk meg a lentebb ismertetett algoritmusok egyikét. A belső SQL lekérdezéssel adjuk meg a táblát, amelyre az algoritmust futtatjuk, a kezdő- és végponto(ka)t, valamint opcionális további szűrési feltételeket. Például, ha a [http://http://docs.pgrouting.org/latest/en/doc/src/developer/sampledata.html#sampledata pgRouting dokumentációjában] bemutatott mintaadatokkal dolgozunk, az alábbi lekérdezéssel a 2. csúcsból a 3. sorszámúba vezető legrövidebb utat kapjuk meg: | + | ahol a <code>pgr_</code>előtaggal hívjuk meg a lentebb ismertetett algoritmusok egyikét. A belső SQL lekérdezéssel adjuk meg a táblát, amelyre az algoritmust futtatjuk, a kezdő- és végponto(ka)t, valamint opcionális további szűrési feltételeket. Például, ha a [http://http://docs.pgrouting.org/latest/en/doc/src/developer/sampledata.html#sampledata pgRouting dokumentációjában] bemutatott mintaadatokkal dolgozunk, az alábbi lekérdezéssel a 2. sorszámú csúcsból a 3. sorszámúba vezető legrövidebb utat kapjuk meg: |
− | < | + | <syntaxhighlight lang="sql"> |
SELECT * FROM pgr_dijkstra( | SELECT * FROM pgr_dijkstra( | ||
'SELECT id, source, target, cost, reverse_cost | 'SELECT id, source, target, cost, reverse_cost | ||
FROM edge_table', 2, 3); | FROM edge_table', 2, 3); | ||
− | </ | + | </syntaxhighlight> |
== Algoritmusok == | == Algoritmusok == | ||
=== Dijkstra algoritmus === | === Dijkstra algoritmus === | ||
− | A Dijkstra algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Jelölje a súlyfüggvényt <math>w</math>. Az algoritmus mohó módszert használ. Legyen a kiindulási pont <math>s</math>, a célállomás pedig <math>t</math>. Az algoritmus egy <math>H</math> halmazban tárolja azon csúcsokat, amelyeknek már ismerjük az <math>s</math>-ből hozzájuk vezető legrövidebb út hosszát. Ezen kívül minden <math>u</math> csúcsról nyilvántartunk az algoritmus futása során egy <math>D[u]</math> értéket, ami az <math>s</math>-ből <math>u</math>-ba vezető addig megismert legrövidebb út hossza. | + | A <span class="plainlinks">[https://hu.wikipedia.org/wiki/Dijkstra-algoritmus Dijkstra algoritmus]</span> egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Jelölje a súlyfüggvényt <math>w</math>. Az algoritmus mohó módszert használ. Legyen a kiindulási pont <math>s</math>, a célállomás pedig <math>t</math>. Az algoritmus egy <math>H</math> halmazban tárolja azon csúcsokat, amelyeknek már ismerjük az <math>s</math>-ből hozzájuk vezető legrövidebb út hosszát. Ezen kívül minden <math>u</math> csúcsról nyilvántartunk az algoritmus futása során egy <math>D[u]</math> értéket, ami az <math>s</math>-ből <math>u</math>-ba vezető addig megismert legrövidebb út hossza. |
Kezdetben <math>H</math> üres, <math>D[s]=0</math> és minden más <math>v</math> csúcsra <math>D[v]=\infty</math>. Ezután minden iterációban kiválasztunk a <math>V\setminus H</math> halmazból egy olyan <math>x</math> csúcsot, amelyre <math>D[x]</math> minimális, áttesszük <math>x</math>-et <math>H</math>-ba, majd <math>x</math> minden olyan <math>v</math> szomszédjára, amely nincs <math>H</math>-ban frissítjük a <math>D[v]</math> értéket: | Kezdetben <math>H</math> üres, <math>D[s]=0</math> és minden más <math>v</math> csúcsra <math>D[v]=\infty</math>. Ezután minden iterációban kiválasztunk a <math>V\setminus H</math> halmazból egy olyan <math>x</math> csúcsot, amelyre <math>D[x]</math> minimális, áttesszük <math>x</math>-et <math>H</math>-ba, majd <math>x</math> minden olyan <math>v</math> szomszédjára, amely nincs <math>H</math>-ban frissítjük a <math>D[v]</math> értéket: | ||
53. sor: | 159. sor: | ||
Az algoritmus költsége szomszédsági mátrixos gráfábrázolás esetén <math>O(|V|^2)</math>, szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva | Az algoritmus költsége szomszédsági mátrixos gráfábrázolás esetén <math>O(|V|^2)</math>, szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva | ||
<math>O(|E|+|V|\log |V|)</math>. | <math>O(|E|+|V|\log |V|)</math>. | ||
+ | |||
+ | '''A Dijkstra algoritmus pgRouting lekérdezéseket használva:''' | ||
+ | |||
+ | Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között). | ||
+ | Ebben a seq a sorok szekvenciája, | ||
+ | az id1 a startcsúcs azonosítója, | ||
+ | az id2 az él azonosítója (az utolsó sorban -1), | ||
+ | a cost az áthaladás költsége id1-től id2 élen keresztül. | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | pgr_costResult[] pgr_dijkstra(text sql, integer source, integer target, | ||
+ | boolean directed, boolean has_rcost); | ||
+ | /*Ebben a source a startcsúcs azonosítója, | ||
+ | a target a célcsúcs azonosítója, | ||
+ | a directed akkor igaz, ha az él irányított, | ||
+ | a has_rcost akkor igaz, ha negatív élek vannak, ekkor a kapott sorokat az algoritmus visszafelé dolgozza fel.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie: | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT id, source, target, cost [,reverse_cost] FROM edge_table | ||
+ | /* Ebben az id az él azonosítója, | ||
+ | a source: az él startcsúcsának azonosítója, | ||
+ | a target az él célcsúcsának azonosítója, | ||
+ | a cost egy pozitív szám, az élen való áthaladásnak a költsége, | ||
+ | a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Dijkstra algoritmussal kiegészítve az előző lekérdezés reverse_cost nélkül: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT seq, id1 AS node, id2 AS edge, cost | ||
+ | FROM pgr_dijkstra( | ||
+ | 'SELECT id, source, target, cost FROM edge_table', | ||
+ | 7, 12, false, false | ||
+ | ); | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Reverse_cost-tal: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT seq, id1 AS node, id2 AS edge, cost | ||
+ | FROM pgr_dijkstra( | ||
+ | 'SELECT id, source, target, cost, reverse_cost FROM edge_table', | ||
+ | 7, 12, true, true | ||
+ | ); | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Jól látható, hogy a két módszer csak a directed és a has_rcost értékekben különbözik. | ||
=== Kétirányú Dijkstra algoritmus === | === Kétirányú Dijkstra algoritmus === | ||
A kétirányú Dijkstra algoritmus szintén egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont <math>s</math>, a célállomást pedig <math>t</math>. A Dijkstra algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy <math>v</math> csúcs mindkét irányból bekerül a Dijkstra algoritmusnál definiált <math>H</math> halmazba (pontosabban a <math>H_s</math> és a <math>H_t</math> halmazba is). Egy alternatív lehetőség, hogy a <math>H_s</math> és a <math>H_t</math> halmazok közül minden egyes iterációban csak azt bővítjük, amelyiknél <math>D[x]</math> kisebb. Az algoritmus kis módosítással egy legrövidebb utat is megad <math>s</math>-ből <math>t</math>-be. | A kétirányú Dijkstra algoritmus szintén egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont <math>s</math>, a célállomást pedig <math>t</math>. A Dijkstra algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy <math>v</math> csúcs mindkét irányból bekerül a Dijkstra algoritmusnál definiált <math>H</math> halmazba (pontosabban a <math>H_s</math> és a <math>H_t</math> halmazba is). Egy alternatív lehetőség, hogy a <math>H_s</math> és a <math>H_t</math> halmazok közül minden egyes iterációban csak azt bővítjük, amelyiknél <math>D[x]</math> kisebb. Az algoritmus kis módosítással egy legrövidebb utat is megad <math>s</math>-ből <math>t</math>-be. | ||
+ | |||
+ | '''A Kétirányú Dijkstra algoritmus pgRouting lekérdezéseket használva:''' | ||
+ | |||
+ | Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között) úgy, hogy elkezdi megkeresni a legrövidebb utat a startcsúcsból és párhuzamosan a célcsúcsból is. Akkor ér véget, ha a két keresés valahol középen véget ér. | ||
+ | Ebben a seq a sorok szekvenciája, | ||
+ | az id1 a startcsúcs azonosítója, | ||
+ | az id2 az él azonosítója (az utolsó sorban -1), | ||
+ | a cost az áthaladás költsége id1-től id2 élen keresztül. | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | pgr_costResult[] pgr_bdDijkstra(sql text, source integer, target integer, | ||
+ | directed boolean, has_rcost boolean); | ||
+ | /*Ebben a source a startcsúcs azonosítója, | ||
+ | a target a célcsúcs azonosítója, | ||
+ | a directed akkor igaz, ha az él irányított, | ||
+ | a has_rcost akkor igaz, ha negatív élek vannak, ekkor a kapott sorokat az algoritmus visszafelé dolgozza fel.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie: | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT id, source, target, cost [,reverse_cost] FROM edge_table | ||
+ | /* Ebben az id az él azonosítója, | ||
+ | a source: az él startcsúcsának azonosítója, | ||
+ | a target az él célcsúcsának azonosítója, | ||
+ | a cost egy pozitív szám, az élen való áthaladásnak a költsége, | ||
+ | a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Dijkstra algoritmussal kiegészítve az előző lekérdezés reverse_cost nélkül: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT seq, id1 AS node, id2 AS edge, cost | ||
+ | FROM pgr_bdDijkstra( | ||
+ | 'SELECT id, source, target, cost FROM edge_table', | ||
+ | 7, 12, false, false | ||
+ | ); | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Reverse_cost-tal: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT seq, id1 AS node, id2 AS edge, cost | ||
+ | FROM pgr_bdDijkstra( | ||
+ | 'SELECT id, source, target, cost, reverse_cost FROM edge_table', | ||
+ | 7, 12, true, true | ||
+ | ); | ||
+ | </syntaxhighlight> | ||
=== k-Dijkstra algoritmus === | === k-Dijkstra algoritmus === | ||
62. sor: | 262. sor: | ||
Az algoritmus költsége szomszédsági mátrixos gráfábrázolás esetén <math>O(|V|^2)</math>, szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva | Az algoritmus költsége szomszédsági mátrixos gráfábrázolás esetén <math>O(|V|^2)</math>, szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva | ||
<math>O(|E|+|V|\log |V|)</math>. | <math>O(|E|+|V|\log |V|)</math>. | ||
+ | |||
+ | '''A k-Dijkstra algoritmus pgRouting lekérdezéseket használva:''' | ||
+ | |||
+ | Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között), vagy összeadja a költségeket (attól függ, melyik verziót használjuk). | ||
+ | Ebben a seq a sorok szekvenciája, | ||
+ | az id1 a startcsúcs azonosítója, | ||
+ | az id2 az él azonosítója (az utolsó sorban -1), | ||
+ | a cost az áthaladás költsége id1-től id2 élen keresztül. | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | pgr_costResult[] pgr_kdijkstraCost(text sql, integer source, | ||
+ | integer[] targets, boolean directed, boolean has_rcost); -- az összeköltséggel tér vissza | ||
+ | |||
+ | pgr_costResult[] pgr_kdijkstraPath(text sql, integer source, | ||
+ | integer[] targets, boolean directed, boolean has_rcost); -- az útban lévő élek halmazával tér vissza | ||
+ | /*Ezekben a source a startcsúcs azonosítója, | ||
+ | a targets a célcsúcsok azonosítójának tömbje, | ||
+ | a directed akkor igaz, ha az él irányított, | ||
+ | a has_rcost akkor igaz, ha negatív élek vannak, ekkor a kapott sorokat az algoritmus visszafelé dolgozza fel.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie: | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT id, source, target, cost [,reverse_cost] FROM edge_table | ||
+ | /* Ebben az id az él azonosítója, | ||
+ | a source: az él startcsúcsának azonosítója, | ||
+ | a target az él célcsúcsának azonosítója, | ||
+ | a cost egy pozitív szám, az élen való áthaladásnak a költsége, | ||
+ | a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | k-Dijkstra algoritmussal kiegészítve az előző lekérdezés úgy, hogy az úttal tér vissza: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT seq, id1 AS path, id2 AS edge, cost FROM pgr_kdijkstraPath( | ||
+ | 'SELECT id, source, target, cost FROM edge_table WHERE cost >= 0', | ||
+ | 10, array[4,12], false, false | ||
+ | ); | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Költséggel tér vissza: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | Returning a cost result | ||
+ | SELECT seq, id1 AS source, id2 AS target, cost FROM pgr_kdijkstraCost( | ||
+ | 'SELECT id, source, target, cost FROM edge_table WHERE cost >= 0', | ||
+ | 10, array[4,12], false, false | ||
+ | ); | ||
+ | </syntaxhighlight> | ||
=== A* algoritmus === | === A* algoritmus === | ||
− | Az <math>A^\ast</math> algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az <math>A^\ast</math> algoritmus a Dijkstra algoritmus általánosítása, és szintén csak nem negatív élsúlyok esetén működik. Jelölje a súlyfüggvényt <math>w</math>. Az algoritmus mohó módszert használ. Legyen a kiindulási pont <math>s</math>, a célállomás pedig <math>t</math>. Az algoritmus egy <math>H</math> halmazban tárolja azon csúcsokat, amelyeknek már ismerjük az <math>s</math>-ből hozzávezető legrövidebb út hosszát, egy <math>M</math> halmazban pedig azokat, amelyeket már elértünk <math>s</math>-ből, de az <math>s</math>-ből hozzájuk vezető legrövidebb út hosszát még nem ismerjük. Minden <math>u</math> csúcsról nyilvántartunk az algoritmus futása során három értéket: <math>D[u]</math> az <math>s</math>-ből <math>u</math>-ba vezető addig megismert legrövidebb út hossza, <math>C[u]</math> egy nem negatív heurisztikus alsó becslés az <math>u</math>-ból <math>t</math>-be vezető legrövidebb út hosszára, amelyre az is teljesül, hogy az <math>u</math>-ból bármely <math>v</math> csúcsba vezető legrövidebb út hosszára | + | Az [https://en.wikipedia.org/wiki/A*_search_algorithm <math>A^\ast</math> algoritmus] egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az <math>A^\ast</math> algoritmus a Dijkstra algoritmus általánosítása, és szintén csak nem negatív élsúlyok esetén működik. Jelölje a súlyfüggvényt <math>w</math>. Az algoritmus mohó módszert használ. Legyen a kiindulási pont <math>s</math>, a célállomás pedig <math>t</math>. Az algoritmus egy <math>H</math> halmazban tárolja azon csúcsokat, amelyeknek már ismerjük az <math>s</math>-ből hozzávezető legrövidebb út hosszát, egy <math>M</math> halmazban pedig azokat, amelyeket már elértünk <math>s</math>-ből, de az <math>s</math>-ből hozzájuk vezető legrövidebb út hosszát még nem ismerjük. Minden <math>u</math> csúcsról nyilvántartunk az algoritmus futása során három értéket: <math>D[u]</math> az <math>s</math>-ből <math>u</math>-ba vezető addig megismert legrövidebb út hossza, <math>C[u]</math> egy nem negatív heurisztikus alsó becslés az <math>u</math>-ból <math>t</math>-be vezető legrövidebb út hosszára, amelyre az is teljesül, hogy az <math>u</math>-ból bármely <math>v</math> csúcsba vezető legrövidebb út hosszára |
<math>C[u]-C[v]</math> alsó korlát (például egy térkép esetén <math>u</math> és <math>t</math> légvonalban mért távolsága), végül <math>B[u]=D[u]+C[u]</math>. | <math>C[u]-C[v]</math> alsó korlát (például egy térkép esetén <math>u</math> és <math>t</math> légvonalban mért távolsága), végül <math>B[u]=D[u]+C[u]</math>. | ||
75. sor: | 323. sor: | ||
A tapasztalat azt mutatja, hogy az <math>A^\ast</math> algoritmus számos esetben hatékonyabb, mint a Dijkstra algoritmust. | A tapasztalat azt mutatja, hogy az <math>A^\ast</math> algoritmus számos esetben hatékonyabb, mint a Dijkstra algoritmust. | ||
− | === | + | '''Az A* algoritmus pgRouting lekérdezéseket használva:''' |
+ | |||
+ | Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között). Az algoritmus Dijkstra algoritmuson alapszik, heurisztikus kikötéssel, amely hatékonyabbá teszi. | ||
+ | Ebben a seq a sorok szekvenciája, | ||
+ | az id1 a startcsúcs azonosítója, | ||
+ | az id2 az él azonosítója (az utolsó sorban -1), | ||
+ | a cost az áthaladás költsége id1-től id2 élen keresztül (az utolsó sorra 0). | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | pgr_costResult[] pgr_astar(sql text, source integer, target integer, | ||
+ | directed boolean, has_rcost boolean); | ||
+ | /*Ezekben a source a startcsúcs azonosítója, | ||
+ | a target a célcsúcs azonosítója, | ||
+ | a directed akkor igaz, ha az él irányított, | ||
+ | a has_rcost akkor igaz, ha negatív élek vannak, ekkor a kapott sorokat az algoritmus visszafelé dolgozza fel.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie: | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT id, source, target, cost, x1, y1, x2, y2 [,reverse_cost] FROM edge_table | ||
+ | /* Ebben az id az él azonosítója, | ||
+ | a source: az él startcsúcsának azonosítója, | ||
+ | a target az él célcsúcsának azonosítója, | ||
+ | x1 az él start pontjának x koordinátája, | ||
+ | y1 az él start pontjának y koordinátája, | ||
+ | x2 az él end pontjának x koordinátája, | ||
+ | y2 az él end pontjának y koordinátája, | ||
+ | a cost egy pozitív szám, az élen való áthaladásnak a költsége, | ||
+ | a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | A* algoritmussal kiegészítve az előző lekérdezés reverse_cost nélkül: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT * FROM pgr_AStar( | ||
+ | 'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, x1, y1, x2, y2 FROM edge_table', | ||
+ | 4, 1, false, false); | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Reverse_cost-tal: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT * FROM pgr_AStar( | ||
+ | 'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, x1, y1, x2, y2, reverse_cost FROM edge_table ', | ||
+ | 4, 1, true, true); | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | === Kétirányú A* algoritmus === | ||
A kétirányú <math>A^\ast</math> algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont <math>s</math>, a célállomást pedig <math>t</math>. Az <math>A^\ast</math> algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy <math>v</math> csúcs mindkét irányból bekerül az <math>A^\ast</math> algoritmusnál definiált <math>H</math> halmazba (pontosabban a <math>H_s</math> és a <math>H_t</math> halmazba is). Az algoritmus kis módosítással egy legrövidebb utat is megad s-ből t-be. | A kétirányú <math>A^\ast</math> algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont <math>s</math>, a célállomást pedig <math>t</math>. Az <math>A^\ast</math> algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy <math>v</math> csúcs mindkét irányból bekerül az <math>A^\ast</math> algoritmusnál definiált <math>H</math> halmazba (pontosabban a <math>H_s</math> és a <math>H_t</math> halmazba is). Az algoritmus kis módosítással egy legrövidebb utat is megad s-ből t-be. | ||
+ | |||
+ | '''A Kétirányú A* algoritmus pgRouting lekérdezéseket használva:''' | ||
+ | |||
+ | Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között) úgy, hogy elkezdi megkeresni a legrövidebb utat a startcsúcsból és párhuzamosan a célcsúcsból is. Akkor ér véget, ha a két keresés valahol középen véget ér. | ||
+ | Ebben a seq a sorok szekvenciája, | ||
+ | az id1 a startcsúcs azonosítója, | ||
+ | az id2 az él azonosítója (az utolsó sorban -1), | ||
+ | a cost az áthaladás költsége id1-től id2 élen keresztül. | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | pgr_costResult[] pgr_bdAstar(sql text, source integer, target integer, | ||
+ | directed boolean, has_rcost boolean); | ||
+ | /*Ebben a source a startcsúcs azonosítója, | ||
+ | a target a célcsúcs azonosítója, | ||
+ | a directed akkor igaz, ha az él irányított, | ||
+ | a has_rcost akkor igaz, ha negatív élek vannak, ekkor a kapott sorokat az algoritmus visszafelé dolgozza fel.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie: | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT id, source, target, cost, x1, y1, x2, y2 [,reverse_cost] FROM edge_table | ||
+ | /* Ebben az id az él azonosítója, | ||
+ | a source: az él startcsúcsának azonosítója, | ||
+ | a target az él célcsúcsának azonosítója, | ||
+ | a cost egy pozitív szám, az élen való áthaladásnak a költsége, | ||
+ | x1 az él start pontjának x koordinátája, | ||
+ | y1 az él start pontjának y koordinátája, | ||
+ | x2 az él end pontjának x koordinátája, | ||
+ | y2 az él end pontjának y koordinátája, | ||
+ | a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Kétirányú A* algoritmussal kiegészítve az előző lekérdezés reverse_cost nélkül: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT * FROM pgr_bdAStar( | ||
+ | 'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, x1, y1, x2, y2 | ||
+ | FROM edge_table', | ||
+ | 4, 10, false, false); | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Reverse_cost-tal: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT * FROM pgr_bdAStar( | ||
+ | 'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, x1, y1, x2, y2, reverse_cost | ||
+ | FROM edge_table ', | ||
+ | 4, 10, true, true); | ||
+ | </syntaxhighlight> | ||
=== Yen algoritmus === | === Yen algoritmus === | ||
− | A Yen algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf egy adott csúcsából egy adott másik csúcsába vezető legrövidebb út mellett megtalálja a második, harmadik, …, <math>k</math>-adik legrövidebb (egyszerű) utat is. Az algoritmus csak nem negatív élsúlyok esetén működik. | + | A [https://en.wikipedia.org/wiki/Yen%27s_algorithm Yen algoritmus] egy súlyozott élű, irányított <math>G=(V,E)</math> gráf egy adott csúcsából egy adott másik csúcsába vezető legrövidebb út mellett megtalálja a második, harmadik, …, <math>k</math>-adik legrövidebb (egyszerű) utat is. Az algoritmus csak nem negatív élsúlyok esetén működik. |
Az algoritmus költsége | Az algoritmus költsége | ||
<math>O(k|V|(|E|+|V|\log |V|))</math>. | <math>O(k|V|(|E|+|V|\log |V|))</math>. | ||
+ | |||
+ | '''A Yen algoritmus pgRouting lekérdezéseket használva:''' | ||
+ | |||
+ | Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) sorok halmazával tér vissza, melyek utakat hoznak létre (a legrövidebb utat a két csúcs között) összesen az első k darabot. | ||
+ | Ebben a seq a sorok szekvenciája, | ||
+ | az id1 az út azonosítója, | ||
+ | az id2 a csúcs azonosítója, | ||
+ | az id3 az él azonosítója (az utolsó sorban 0) | ||
+ | a cost az áthaladás költsége id2-től id3-at használva. | ||
+ | |||
+ | Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie: | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT id, source, target, cost, [,reverse_cost] FROM edge_table | ||
+ | /* Ebben az id az él azonosítója, | ||
+ | a source: az él startcsúcsának azonosítója, | ||
+ | a target az él célcsúcsának azonosítója, | ||
+ | a cost egy pozitív szám, az élen való áthaladásnak a költsége, | ||
+ | a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Yen algoritmussal kiegészítve az előző lekérdezés reverse_cost nélkül: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost | ||
+ | FROM pgr_ksp( | ||
+ | 'SELECT id, source, target, cost FROM edge_table', | ||
+ | 7, 12, 2, false | ||
+ | ); | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Reverse_cost-tal: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost | ||
+ | FROM pgr_ksp( | ||
+ | 'SELECT id, source, target, cost, reverse_cost FROM edge_table', | ||
+ | 7, 12, 2, true | ||
+ | ); | ||
+ | </syntaxhighlight> | ||
=== Floyd-Warshall algoritmus === | === Floyd-Warshall algoritmus === | ||
− | A Floyd-Warshall algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf bármely két csúcsa közötti legrövidebb út megtalálására szolgáló módszer. Az algoritmus negatív élsúlyok esetén is működik, ha a gráf nem tartalmaz negatív összhosszúságú irányított kört. Jelölje a súlyfüggvényt <math>w</math>. Az algoritmus dinamikus programozást használ. Legyen a gráf csúcshalmaza <math>\{v_1,v_2,\ldots,v_n\}</math>. Az algoritmus minden <math>0\leqslant k\leqslant n</math> esetén meghatározza a <math>v_i</math>-ből | + | A [https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm Floyd-Warshall algoritmus] egy súlyozott élű, irányított <math>G=(V,E)</math> gráf bármely két csúcsa közötti legrövidebb út megtalálására szolgáló módszer. Az algoritmus negatív élsúlyok esetén is működik, ha a gráf nem tartalmaz negatív összhosszúságú irányított kört. Jelölje a súlyfüggvényt <math>w</math>. Az algoritmus dinamikus programozást használ. Legyen a gráf csúcshalmaza <math>\{v_1,v_2,\ldots,v_n\}</math>. Az algoritmus minden <math>0\leqslant k\leqslant n</math> esetén meghatározza a <math>v_i</math>-ből |
<math>v_j</math>-be menő legrövidebb olyan (egyszerű) út <math>T_k[v_i,v_j]</math> hosszát, amelyen a közbülső csúcsok a <math>\{v_1,v_2,\ldots,v_k\}</math> halmazból kerülnek ki: | <math>v_j</math>-be menő legrövidebb olyan (egyszerű) út <math>T_k[v_i,v_j]</math> hosszát, amelyen a közbülső csúcsok a <math>\{v_1,v_2,\ldots,v_k\}</math> halmazból kerülnek ki: | ||
<math>T_0[v_i,v_j]=w(v_i,v_j)</math>, és <math>T_k[v_i,v_j]=\min\{T_{k-1}[v_i,v_j],T_{k-1}[v_i,v_k]+T_{k-1}[v_k,v_j]\}</math> ha <math>k>0</math>. Az algoritmus kis módosítással magukat a legrövidebb utakat is megadja. | <math>T_0[v_i,v_j]=w(v_i,v_j)</math>, és <math>T_k[v_i,v_j]=\min\{T_{k-1}[v_i,v_j],T_{k-1}[v_i,v_k]+T_{k-1}[v_k,v_j]\}</math> ha <math>k>0</math>. Az algoritmus kis módosítással magukat a legrövidebb utakat is megadja. | ||
Az algoritmus költsége <math>O(|V|^3)</math>. | Az algoritmus költsége <math>O(|V|^3)</math>. | ||
+ | |||
+ | '''A Floyd-Warshall algoritmus pgRouting lekérdezéseket használva:''' | ||
+ | |||
+ | Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza minden csúcspárra a súlyozott gráfban, mindegyiknél kiszámolva a legrövidebb utat: | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | pgr_costResult[] pgr_aspsWarshall(sql text, directed boolean, reverse_cost boolean); -- magyarul minden egyes csúcspárra kiszámolja az összes költséget. | ||
+ | /*Ebben a seq a sorok szekvenciája, | ||
+ | az id1 a startcsúcs azonosítója, | ||
+ | az id2 a célcsúcs azonosítója, | ||
+ | a cost az id1-től id2-ig jutás költsége.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie: | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT source, target, cost FROM edge_table; | ||
+ | /* Ebben a source: az él startcsúcsának azonosítója, | ||
+ | a target az él célcsúcsának azonosítója, | ||
+ | a cost egy pozitív szám, az élen való áthaladásnak a költsége, | ||
+ | a reverse_cost ha igaz, akkor a cost értékét az ellentétes irányból vesszük.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Floyd-Warshall algoritmussal kiegészítve az előző lekérdezés: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT seq, id1 AS from, id2 AS to, cost | ||
+ | FROM pgr_apspWarshall( | ||
+ | 'SELECT id, source, target, cost FROM edge_table', | ||
+ | false, false | ||
+ | ); | ||
+ | </syntaxhighlight> | ||
=== Johnson algoritmus === | === Johnson algoritmus === | ||
− | A Johnson algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf bármely két csúcsa közötti legrövidebb út megtalálására szolgáló módszer. Az algoritmus negatív élsúlyok esetén is működik, ha a gráf nem tartalmaz negatív összhosszúságú irányított kört. Jelölje a súlyfüggvényt <math>w</math>. Az algoritmus ritka gráfokon teljesít igazán jól. | + | A [https://en.wikipedia.org/wiki/Johnson%27s_algorithm Johnson algoritmus] egy súlyozott élű, irányított <math>G=(V,E)</math> gráf bármely két csúcsa közötti legrövidebb út megtalálására szolgáló módszer. Az algoritmus negatív élsúlyok esetén is működik, ha a gráf nem tartalmaz negatív összhosszúságú irányított kört. Jelölje a súlyfüggvényt <math>w</math>. Az algoritmus ritka gráfokon teljesít igazán jól. |
Vegyünk fel egy új <math>s</math> csúcsot, és vezessünk <math>s</math>-ből nulla súlyú éleket <math>G</math> csúcsaiba. Jelölje az így kapott gráfot <math>G'</math>. Futtassuk le <math>G'</math>-re a Bellman-Ford algoritmust az <math>s</math> kezdőcsúccsal. Az algoritmus által szolgáltatott távolságérték a gráf egy <math>v</math> csúcsára legyen | Vegyünk fel egy új <math>s</math> csúcsot, és vezessünk <math>s</math>-ből nulla súlyú éleket <math>G</math> csúcsaiba. Jelölje az így kapott gráfot <math>G'</math>. Futtassuk le <math>G'</math>-re a Bellman-Ford algoritmust az <math>s</math> kezdőcsúccsal. Az algoritmus által szolgáltatott távolságérték a gráf egy <math>v</math> csúcsára legyen | ||
99. sor: | 510. sor: | ||
Az algoritmus költsége szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva | Az algoritmus költsége szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva | ||
<math>O(|V|(|E|+|V|\log |V|))</math>. | <math>O(|V|(|E|+|V|\log |V|))</math>. | ||
+ | |||
+ | '''A Johnson algoritmus pgRouting lekérdezéseket használva:''' | ||
+ | |||
+ | Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza minden csúcspárra a gráfban: | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | pgr_costResult[] pgr_aspsJohnson(sql text); -- magyarul minden egyes csúcspárra kiszámolja az összes költséget. | ||
+ | /*Ebben a seq a sorok szekvenciája, | ||
+ | az id1 a startcsúcs azonosítója, | ||
+ | az id2 a célcsúcs azonosítója, | ||
+ | a cost az id1-től id2-ig jutás költsége.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie: | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT source, target, cost FROM edge_table; | ||
+ | /* Ebben a source: az él startcsúcsának azonosítója, | ||
+ | a target az él célcsúcsának azonosítója, | ||
+ | a cost egy pozitív szám, az élen való áthaladásnak a költsége.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Johnson algoritmussal kiegészítve az előző lekérdezés: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT seq, id1 AS from, id2 AS to, cost | ||
+ | FROM pgr_apspJohnson( | ||
+ | 'SELECT source, target, cost FROM edge_table' | ||
+ | ); | ||
+ | </syntaxhighlight> | ||
=== Utazó ügynök probléma === | === Utazó ügynök probléma === | ||
− | Az utazó ügynök probléma a következő. Adott városoknak egy listája, és adott bármely két város között a távolság. Határozzunk meg egy olyan körutat, amely minden városon pontosan egyszer halad át, és a hossza minimális. A problémára nem ismert polinomiális költségű algoritmus. A program ún. simulated annealing technikán alapuló algoritmust használ egy jó közelítő megoldás meghatározására. | + | Az [https://hu.wikipedia.org/wiki/Az_utaz%C3%B3_%C3%BCgyn%C3%B6k_probl%C3%A9m%C3%A1ja utazó ügynök probléma] a következő. Adott városoknak egy listája, és adott bármely két város között a távolság. Határozzunk meg egy olyan körutat, amely minden városon pontosan egyszer halad át, és a hossza minimális. A problémára nem ismert polinomiális költségű algoritmus. A program ún. simulated annealing technikán alapuló algoritmust használ egy jó közelítő megoldás meghatározására. |
+ | |||
+ | '''A vezetési távolság algoritmus pgRouting lekérdezéseket használva:''' | ||
+ | |||
+ | Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) egy seq-id párossal tér vissza, amely azt írja le, mi a legjobb haladási sorrend a mátrixban, hogy eljussunk a start csúcsból a meghatározott csúcsokig. | ||
+ | Ebben a seq a sorok szekvenciája, | ||
+ | az id1 az út azonosítója, | ||
+ | az id2 a csúcs azonosítója, | ||
+ | az id3 az él azonosítója (az utolsó sorban 0) | ||
+ | a cost az áthaladás költsége id2-től id3-at használva. | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | pgr_costResult[] pgr_tsp(sql text, ids varchar, source integer); | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Utazó ügynök algoritmus SQL paraméterrel: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT * FROM pgr_tsp('SELECT id AS source_id, x, y FROM vertex_table','2,7,11',7); | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Távolsági mátrixszal: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT seq, id FROM pgr_tsp('{{0,1,2,3},{1,0,3,2},{2,3,0,4},{3,2,4,0}}',2); | ||
+ | </syntaxhighlight> | ||
=== Legrövidebb utak kanyarodási korlátokkal === | === Legrövidebb utak kanyarodási korlátokkal === | ||
Az algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út meghatározásakor képes figyelembe venni, hogy két csatlakozó él egymás utáni bejárása extra költséggel bírhat. Ezeket a megszorításokat egy külön táblában adhatjuk meg. Tapasztalat szerint az algoritmus közel olyan gyors, mint az <math>A^\ast</math> algoritmus. | Az algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út meghatározásakor képes figyelembe venni, hogy két csatlakozó él egymás utáni bejárása extra költséggel bírhat. Ezeket a megszorításokat egy külön táblában adhatjuk meg. Tapasztalat szerint az algoritmus közel olyan gyors, mint az <math>A^\ast</math> algoritmus. | ||
+ | |||
+ | '''A legrövidebb út kanyarodási korlátokkal algoritmus pgRouting lekérdezéseket használva:''' | ||
+ | |||
+ | Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) sorok halmazával tér vissza, minden sor egy élt tartalmaz, amelyiken átmentünk, plusz az utolsó az utolsó élt. | ||
+ | Ebben a seq a sorok szekvenciája, | ||
+ | az id1 az út azonosítója, | ||
+ | az id2 a csúcs azonosítója, | ||
+ | az id3 az él azonosítója (az utolsó sorban 0) | ||
+ | a cost az áthaladás költsége id2-től id3-at használva. | ||
+ | |||
+ | Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie, attól függően, hogy van-e megszorítás: | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | pgr_costResult[] pgr_trsp(sql text, source integer, target integer, directed boolean, has_rcost boolean [,restrict_sql text]); | ||
+ | |||
+ | pgr_costResult[] pgr_trsp(sql text, source_edge integer, source_pos double precision, target_edge integer, target_pos double precision, directed boolean, has_rcost boolean [,restrict_sql text]); | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT id, source, target, cost, [,reverse_cost] FROM edge_table; | ||
+ | /* Ebben az id az él azonosítója, | ||
+ | a source: az él startcsúcsának azonosítója, | ||
+ | a target az él célcsúcsának azonosítója, | ||
+ | a cost egy pozitív szám, az élen való áthaladásnak a költsége, | ||
+ | a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | TSRP algoritmussal kiegészítve az előző lekérdezés megszorítások nélkül: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT seq, id1 AS node, id2 AS edge, cost | ||
+ | FROM pgr_trsp( | ||
+ | 'SELECT id, source, target, cost FROM edge_table', | ||
+ | 7, 12, false, false | ||
+ | ); | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Megszorításokkal (külön táblában tároljuk): | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT seq, id1 AS node, id2 AS edge, cost | ||
+ | FROM pgr_trsp( | ||
+ | 'SELECT id, source, target, cost FROM edge_table', | ||
+ | 7, 12, false, false, | ||
+ | 'SELECT to_cost, to_edge AS target_id, | ||
+ | from_edge || coalesce('','' || via, '''') AS via_path | ||
+ | FROM restrictions' | ||
+ | ); | ||
+ | </syntaxhighlight> | ||
=== Vezetési távolság === | === Vezetési távolság === | ||
− | + | Az algoritmus egy súlyozott élű, irányított <math>G=(V,E)</math> gráfban a Dijkstra algoritmus felhasználásával megadja azon csúcsokat, melyekbe egy vagy több adott csúcsból egy adott értéknél rövidebb úton el lehet jutni. | |
+ | |||
+ | '''A vezetési távolság algoritmus pgRouting lekérdezéseket használva:''' | ||
+ | |||
+ | Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) sorok halmazával tér vissza, minden sor egy élt tartalmaz, amelyiken átmentünk, plusz az utolsó az utolsó élt. | ||
+ | Ebben a seq a sorok szekvenciája, | ||
+ | az id1 az út azonosítója, | ||
+ | az id2 a csúcs azonosítója, | ||
+ | az id3 az él azonosítója (az utolsó sorban 0) | ||
+ | a cost az áthaladás költsége id2-től id3-at használva. | ||
+ | |||
+ | Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie: | ||
+ | |||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT id, source, target, cost, [,reverse_cost] FROM edge_table | ||
+ | /* Ebben az id az él azonosítója, | ||
+ | a source: az él startcsúcsának azonosítója, | ||
+ | a target az él célcsúcsának azonosítója, | ||
+ | a cost egy pozitív szám, az élen való áthaladásnak a költsége, | ||
+ | a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/ | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Vezetési távolság algoritmussal kiegészítve az előző lekérdezés: | ||
+ | <syntaxhighlight lang="sql"> | ||
+ | SELECT * FROM pgr_drivingDistance( | ||
+ | 'SELECT id, source, target, cost, reverse_cost FROM edge_table', | ||
+ | 2, 3 | ||
+ | ); | ||
+ | </syntaxhighlight> | ||
== Kapcsolódó alkalmazások == | == Kapcsolódó alkalmazások == | ||
− | Útvonal-meghatározásra alkalmas adathalmazt például OpenStreetMap (OSM) térképekből nyerhetünk ki. Ehhez egyik alkalmas segédeszköz az OSM2PO alkalmazás, amely megfelelő topológiájú SQL fájlt állít elő a megadott térképrészlethez, | + | Útvonal-meghatározásra alkalmas adathalmazt például [[OpenStreetMap]] (OSM) térképekből nyerhetünk ki. Ehhez egyik alkalmas segédeszköz az [[OSM2PO]] alkalmazás, amely megfelelő topológiájú SQL fájlt állít elő a megadott térképrészlethez, amely egyből alkalmas a pgRouting-gal vagy QGIS-szel való feldolgozásra. [[Fájl:Osm.png|thumb|450px|Útvonal megjelenítése OSM2PO webszolgáltatásként]] |
− | * koordináták | + | Az OSM2PO révén vizualizálhatjuk is a legrövidebb utakat. A programmal előállított SQL táblákban minden útkereszteződéshez tartozik egy rekord, melyben a következőket tároljuk: |
− | * név | + | * koordináták (<code>x1, x2, y1, y2</code>), |
− | * csomópont azonosító | + | * név (<code>osm_name</code>), |
− | * lehetséges továbbhaladási irány ( | + | * csomópont azonosító (<code>id</code>), |
− | * útszakasz hossza | + | * lehetséges továbbhaladási irány (<code>osm_source_id, osm_target_id</code>), |
− | * megengedett sebesség | + | * útszakasz hossza (<code>km</code>), |
− | * költség | + | * megengedett sebesség (<code>kmh</code>), |
+ | * költség (<code>cost</code>), | ||
+ | * geometria (<code>geom_way</code>). | ||
+ | |||
+ | A <code>demo.bat</code> fájl szerkesztésével specifikálhatjuk térképünk paramétereit, például, hogy mely térképrészleten dolgozzunk. A [https://mapzen.com/data/metro-extracts/ Mapzen] oldalán kész <code>.pbf</code> formátumú városrészleteket találhatunk, melyeket kompatibilisek az Osm2Po-val. A fájl futtatásával előáll egy <code>.sql</code> fájl is, melyet importálhatunk a postGIS adatbázisunkba, és akár pgRouting lekérdezéseket is futtathatunk rajta. | ||
+ | Amíg fut a program, helyi webszerveren (<code>localhost:8888/Osm2poService</code>) jeleníthető meg az importált térképrészlet, melyen az útkeresést is kipróbálhatjuk. | ||
+ | |||
+ | == Szakirodalom == | ||
+ | |||
+ | * Regina O. Obe, Leo S. Hsu. [https://locatepress.com/pgrouting "pgRouting: A Practical Guide"], ''Locate Press'', 2016. | ||
+ | * Regina O. Obe, Leo S. Hsu. [https://www.manning.com/books/postgis-in-action-second-edition "PostGIS in Action (Second Edition)"], ''Manning Publictions'' (ISBN 9781617291395). 2015. pp 286-290. | ||
+ | * Lijing Zhang, Xuanhui He. [http://link.springer.com/chapter/10.1007%2F978-3-642-25349-2_133 "Route Search Base on pgRouting"], ''Software Engineering and Knowledge Engineering: Theory and Practice Vol 2.''. Springer-Verlag Berlin Heidelberg, 2012. pp 1003-1007. | ||
+ | |||
+ | == Külső hivatkozások == | ||
− | + | * [http://pgrouting.org/ A pgRouting hivatalos honlapja] | |
− | [http://http://www.postgresonline.com/journal/archives/362-An-almost-idiots-guide-to-install-PostgreSQL-9.5,-PostGIS-2.2-and-pgRouting-2.1.0-with-Yum.html Fejlesztőkörnyezet telepítési útmutató] | + | * [http://docs.pgrouting.org/latest/en/doc/index.html pgRouting Dokumentáció] |
− | [http://http://docs.pgrouting.org/ | + | * [http://www.postgresonline.com/journal/archives/362-An-almost-idiots-guide-to-install-PostgreSQL-9.5,-PostGIS-2.2-and-pgRouting-2.1.0-with-Yum.html Fejlesztőkörnyezet telepítési útmutató] |
− | [http:// | + | * [http://workshop.pgrouting.org/index.html pgRouting Workshop] |
+ | * [http://www.bostongis.com/PrinterFriendly.aspx?content_name=pgrouting_osm2po_1 OpenStreetMap fájl betöltése Osm2Po-val és útvonalkeresés] | ||
+ | * [http://docs.pgrouting.org/2.3/en/doc/index.html pgRouting v2.3 Manual] | ||
+ | * [http://docs.pgrouting.org/2.3/en/doc/src/developer/sampledata.html Sample pgRouting data] | ||
+ | * [https://anitagraser.com/2011/02/07/a-beginners-guide-to-pgrouting/ pgRouting guide] |
A lap jelenlegi, 2017. május 25., 15:52-kori változata
A pgRouting egy nyílt forráskódú, C++ nyelven írt bővítmény a PostGIS/PostgreSQL térinformatikai adatbázisokhoz. Lehetővé teszi gráf adatszerkezetek kezelését, így például legrövidebb utakat, csomópontok távolságát és egyéb hálózati elemzést igénylő feladatokat oldhatunk meg vele. A programcsomag GNU GPL v2 licenc alatt használható. Elődje volt a pgDijkstra, amelyet később kiterjesztettek és pgRouting-nak neveztek el. Napjainkban a fenntartását a Georepublic, az iMaptools és a felhasználók végzik.
OSGeo
A pgRouting az OSGeo Foundation-nek egy OSGeo Labs projektje és része az OSGeo Live-nak, ami egy hordozható szoftver, mellyel ki széles körben ki lehet próbálni térinformatikai szoftvereket installálás nélkül. Teljesen ingyenes, szabadon használható, módosítható és dokumentációt, valamint mintaadatokat is tartalmaz.
A pgRoutingot sokféle módon tudjuk használni, adatmódosítást is több különböző szoftverrel is végezhetünk, pl. pgAdmin, QGIS használatával, vagy konkrét Pl/pgSQL utasítások használatával. Az adatmódosításokat a routing engine azonnal elvégzi és a "cost" paraméter kiszámítása is működik dinamikusan.
Tartalomjegyzék
Telepítés
A PostGIS újabb verziói (2.0+) már tartalmazzák a pgRouting csomagot, így nem szükséges külön telepíteni, csak aktiválni kell, a következő módon.
CREATE EXTENSION pgrouting;
A teljes telepítési útmutató elérhető a pgRouting honlapján. Természetesen különböző platformokra is elérhető a csomag: Linux, MAC OS és Windows alá is.
Én a Windows verziót választottam. A pgRouting honlapján lévő hivatalos telepítési útmutató alapján hosszas, bonyodalmas telepítésre számítottam, de meglepően egyszerűnek bizonyult. Nem kell más, csak egy PostgreSQL és a hozzá tartozó, megfelelő verziójú PostGIS, amelyet a kapcsolódó StackBuilder-rel automatikusan, könnyen telepíthetünk.
Elérhetőek más kiterjesztések is, én csak a PostGIS-pgRouting kombót választottam.
Telepítés után az úgy nevezett pgAdmin alkalmazást kell elindítani és ebben kell csatlakozni az adatbázisunkhoz. Az adatbázis futhat localhost-on, sőt, egy kezdeti adatbázist már a PostGIS telepítése során létrehozhatunk.
Az adatbázis jelszóval védett és különböző felhasználókat is létre lehet benne hozni, majd a táblákról megmondani, kiknek van hozzá jogosultsága - tehát itt semmi meglepetés nincs.
Grafikus megjelenítéshez a QGIS programcsomag megfelelő választás lehet.
Felépítés
A pgRouting két fő összetevőből áll:
- Egy C modul, amely egy PostgreSQL-ben átadott lekérdezést használ a gráf felépítéséhez.
- C++ modulok, amelyek a lekérdezést úgynevezett boost gráffá alakítják, és futtatják az útvonal-választást.
Hogy mely összetevőt használja a program futása során, az az algoritmus fajtájától függ.
A függvénykönyvtár szerkezete pedig a következőképp néz ki:
cmake/ - cmake fájlok CMakeLists.txt - Top level cmake doc/ - Top level doc, a nem forrásalgoritmus-specifikus dokumentáció helye themes/ - Sphinx téma a doc-nak static/ - dokumentáció képei src/ astar/ - A* algoritmus common/ - pgRouting projektekben szükséges közös fájlok dijkstra/ - Dijkstra algoritmus driving_distance/ - Vezetési távolság trsp/ - Legrövidebb utak kanyarodási korlátokkal tsp/ - Utazó ügynök tools/ - Tesztelési eszközök
Az src mappa minden könyvtárában doc
, sql
, src
, és test
almappák találhatók, melyekbe értelemszerűen a következők kerülnek:
- doc: Az adott algoritmushoz szükséges összes dokumentáció ReStructuredText formátumban. Ennek célja, hogy a függvények leírásával, input és output paraméterek megadásával a felhasználók számára érthetővé tegye, hogyan működik az algoritmus.
- sql: Az sql burkolók a C kódhoz.
- src: C/C++ kód az algoritmushoz.
- test:
test.conf
,*.data
,*.test
, és*.rest
fájlok az algoritmus teszteléséhez.
Fejlesztési célból a programot klónozhatjuk Git-en keresztül, majd telepítjük a következők szerint:
git clone git@github.com:pgRouting/pgrouting.git
cd pgrouting
cmake -DWITH_TSP=ON -DWITH_DD=ON .
make
sudo make install
A 2.3 pgRouting library tartalma/leírása itt található.
Használat
Adatok betöltése
A vektoros térképi adatok adatbázis-táblába betöltésére számos eszköz áll rendelkezésre, például:
- osm2po: OpenStreetMap (OSM) adatok konvertálása SQL formátumba, pgRouting-nak megfelelő formátumban (hasonló hozzá az osm2pgrouting is, de ez sajnos egy ideje Windows alatt nem működik).
- shp2pgsql: PostgreSQL shapefile betöltője (az újabb verziójához GUI is tartozik, mellyel könnyen lehet shapefile-okat betölteni).
- ogr2ogr: Vektoros adatok konverziója.
- osm2pgsql: OSM adat betöltése postgreSQL-be.
Előfeldolgozás
Amikor egy GIS fájlt olvasunk be az adatbázisunkba a pgRouting számára, nem feltétlenül követnek alkalmas topológiát a rekordok. A helytelen topológia hibás útvonalakhoz vezetne. Hogy használható adattáblát kapjunk, csomópontokra van szükségünk minden egyes útkereszteződésnél. Az útvonalhálózat megfelelő topológiájának kialakítását segítheti a pgr_createTopology vagy a pgr_nodeNetwork parancs. Működésük hasonló. Az utóbbi beolvassa a „csúcstalan” hálózat adatbázis-tábláját, majd egy új táblába írja a már felcsúcsozott éleket. Paraméterei
- éltábla neve,
- tolerancia: a toleranciaértéken belüli csomópontok egy csomópontot fognak alkotni,
- id, az éltábla elsődleges kulcsa,
- geometriát tartalmazó oszlop,
- kimeneti tábla szuffixe. Alapértelmezetten edge_table_noded.
Előfordulhat olyan eset is, amikor a pl. shapefile-ból betöltött táblánkon nem tudunk automatikusan topológiát építeni, mivel csak egy "geometry" típusú oszlopból tudjuk, hol van az elhelyezkedése, azaz nem tudjuk a start és az end csúcsát. Szerencsére erre is van megoldás:
1. Létrehozunk egy view-t, amelyikbe kiszámoljuk az adott geom start és end csúcsát (ebben az esetben a road táblán hajtjuk végre az átalakítást).
CREATE OR REPLACE VIEW road_ext AS
SELECT *, startpoint(the_geom), endpoint(the_geom)
FROM road;
2. Létrehozunk egy táblát, amelyben az egyes csomópontokat tároljuk, és ezeknek adunk egy unique ID-t is.
CREATE TABLE node AS
SELECT row_number() OVER (ORDER BY foo.p)::integer AS id,
foo.p AS the_geom
FROM (
SELECT DISTINCT road_ext.startpoint AS p FROM road_ext
UNION
SELECT DISTINCT road_ext.endpoint AS p FROM road_ext
) foo
GROUP BY foo.p;
3. Ahhoz, hogy bejárható hálózatot kapjunk, létrehozunk egy táblát az eredeti és a csomópontok összejoin-olásával.
CREATE TABLE network AS
SELECT a.*, b.id as start_id, c.id as end_id
FROM road_ext AS a
JOIN node AS b ON a.startpoint = b.the_geom
JOIN node AS c ON a.endpoint = c.the_geom;
4. Majd, ha akarjuk létrehozunk spatial index-et a lekérdezések hatékonyabb végrehajtása érdekében.
CREATE INDEX road_gist ON road USING GIST (the_geom);
5. Már mehetnek is a lekérdezések!
Lekérdezés szintaxis
Minden pgRouting lekérdezés az alábbi formátumot követi:
SELECT pgr_<algorithm>(<SQL for edges>, start, end, <additonal options>)
ahol a pgr_
előtaggal hívjuk meg a lentebb ismertetett algoritmusok egyikét. A belső SQL lekérdezéssel adjuk meg a táblát, amelyre az algoritmust futtatjuk, a kezdő- és végponto(ka)t, valamint opcionális további szűrési feltételeket. Például, ha a pgRouting dokumentációjában bemutatott mintaadatokkal dolgozunk, az alábbi lekérdezéssel a 2. sorszámú csúcsból a 3. sorszámúba vezető legrövidebb utat kapjuk meg:
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost
FROM edge_table', 2, 3);
Algoritmusok
Dijkstra algoritmus
A Dijkstra algoritmus egy súlyozott élű, irányított gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Jelölje a súlyfüggvényt . Az algoritmus mohó módszert használ. Legyen a kiindulási pont , a célállomás pedig . Az algoritmus egy halmazban tárolja azon csúcsokat, amelyeknek már ismerjük az -ből hozzájuk vezető legrövidebb út hosszát. Ezen kívül minden csúcsról nyilvántartunk az algoritmus futása során egy értéket, ami az -ből -ba vezető addig megismert legrövidebb út hossza.
Kezdetben üres, és minden más csúcsra . Ezután minden iterációban kiválasztunk a halmazból egy olyan csúcsot, amelyre minimális, áttesszük -et -ba, majd minden olyan szomszédjára, amely nincs -ban frissítjük a értéket: . Az algoritmus véget ér, amikor átkerül -ba, ekkor egy legrövidebb -ből -be vezető út hossza. Az algoritmus kis módosítással egy legrövidebb utat is megad -ből -be.
Az algoritmus költsége szomszédsági mátrixos gráfábrázolás esetén , szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva .
A Dijkstra algoritmus pgRouting lekérdezéseket használva:
Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között). Ebben a seq a sorok szekvenciája, az id1 a startcsúcs azonosítója, az id2 az él azonosítója (az utolsó sorban -1), a cost az áthaladás költsége id1-től id2 élen keresztül.
pgr_costResult[] pgr_dijkstra(text sql, integer source, integer target,
boolean directed, boolean has_rcost);
/*Ebben a source a startcsúcs azonosítója,
a target a célcsúcs azonosítója,
a directed akkor igaz, ha az él irányított,
a has_rcost akkor igaz, ha negatív élek vannak, ekkor a kapott sorokat az algoritmus visszafelé dolgozza fel.*/
Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie:
SELECT id, source, target, cost [,reverse_cost] FROM edge_table
/* Ebben az id az él azonosítója,
a source: az él startcsúcsának azonosítója,
a target az él célcsúcsának azonosítója,
a cost egy pozitív szám, az élen való áthaladásnak a költsége,
a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/
Dijkstra algoritmussal kiegészítve az előző lekérdezés reverse_cost nélkül:
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM edge_table',
7, 12, false, false
);
Reverse_cost-tal:
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
7, 12, true, true
);
Jól látható, hogy a két módszer csak a directed és a has_rcost értékekben különbözik.
Kétirányú Dijkstra algoritmus
A kétirányú Dijkstra algoritmus szintén egy súlyozott élű, irányított gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont , a célállomást pedig . A Dijkstra algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy csúcs mindkét irányból bekerül a Dijkstra algoritmusnál definiált halmazba (pontosabban a és a halmazba is). Egy alternatív lehetőség, hogy a és a halmazok közül minden egyes iterációban csak azt bővítjük, amelyiknél kisebb. Az algoritmus kis módosítással egy legrövidebb utat is megad -ből -be.
A Kétirányú Dijkstra algoritmus pgRouting lekérdezéseket használva:
Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között) úgy, hogy elkezdi megkeresni a legrövidebb utat a startcsúcsból és párhuzamosan a célcsúcsból is. Akkor ér véget, ha a két keresés valahol középen véget ér. Ebben a seq a sorok szekvenciája, az id1 a startcsúcs azonosítója, az id2 az él azonosítója (az utolsó sorban -1), a cost az áthaladás költsége id1-től id2 élen keresztül.
pgr_costResult[] pgr_bdDijkstra(sql text, source integer, target integer,
directed boolean, has_rcost boolean);
/*Ebben a source a startcsúcs azonosítója,
a target a célcsúcs azonosítója,
a directed akkor igaz, ha az él irányított,
a has_rcost akkor igaz, ha negatív élek vannak, ekkor a kapott sorokat az algoritmus visszafelé dolgozza fel.*/
Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie:
SELECT id, source, target, cost [,reverse_cost] FROM edge_table
/* Ebben az id az él azonosítója,
a source: az él startcsúcsának azonosítója,
a target az él célcsúcsának azonosítója,
a cost egy pozitív szám, az élen való áthaladásnak a költsége,
a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/
Dijkstra algoritmussal kiegészítve az előző lekérdezés reverse_cost nélkül:
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_bdDijkstra(
'SELECT id, source, target, cost FROM edge_table',
7, 12, false, false
);
Reverse_cost-tal:
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_bdDijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
7, 12, true, true
);
k-Dijkstra algoritmus
A -Dijkstra algoritmus egy súlyozott élű, irányított gráf adott csúcsából több adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Valójában a Dijkstra algoritmus a gráf egy adott csúcsából az összes többi csúcsba vezető legrövidebb utat megtalálja, így akárhány célállomást megadhatunk. Az algoritmus akkor fejeződik be, amikor minden egyes célállomás bekerült a Dijkstra algoritmusnál definiált halmazba. Az algoritmus kis módosítással magukat a legrövidebb utakat is megadja.
Az algoritmus költsége szomszédsági mátrixos gráfábrázolás esetén , szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva .
A k-Dijkstra algoritmus pgRouting lekérdezéseket használva:
Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között), vagy összeadja a költségeket (attól függ, melyik verziót használjuk). Ebben a seq a sorok szekvenciája, az id1 a startcsúcs azonosítója, az id2 az él azonosítója (az utolsó sorban -1), a cost az áthaladás költsége id1-től id2 élen keresztül.
pgr_costResult[] pgr_kdijkstraCost(text sql, integer source,
integer[] targets, boolean directed, boolean has_rcost); -- az összeköltséggel tér vissza
pgr_costResult[] pgr_kdijkstraPath(text sql, integer source,
integer[] targets, boolean directed, boolean has_rcost); -- az útban lévő élek halmazával tér vissza
/*Ezekben a source a startcsúcs azonosítója,
a targets a célcsúcsok azonosítójának tömbje,
a directed akkor igaz, ha az él irányított,
a has_rcost akkor igaz, ha negatív élek vannak, ekkor a kapott sorokat az algoritmus visszafelé dolgozza fel.*/
Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie:
SELECT id, source, target, cost [,reverse_cost] FROM edge_table
/* Ebben az id az él azonosítója,
a source: az él startcsúcsának azonosítója,
a target az él célcsúcsának azonosítója,
a cost egy pozitív szám, az élen való áthaladásnak a költsége,
a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/
k-Dijkstra algoritmussal kiegészítve az előző lekérdezés úgy, hogy az úttal tér vissza:
SELECT seq, id1 AS path, id2 AS edge, cost FROM pgr_kdijkstraPath(
'SELECT id, source, target, cost FROM edge_table WHERE cost >= 0',
10, array[4,12], false, false
);
Költséggel tér vissza:
Returning a cost result
SELECT seq, id1 AS source, id2 AS target, cost FROM pgr_kdijkstraCost(
'SELECT id, source, target, cost FROM edge_table WHERE cost >= 0',
10, array[4,12], false, false
);
A* algoritmus
Az algoritmus egy súlyozott élű, irányított gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus a Dijkstra algoritmus általánosítása, és szintén csak nem negatív élsúlyok esetén működik. Jelölje a súlyfüggvényt . Az algoritmus mohó módszert használ. Legyen a kiindulási pont , a célállomás pedig . Az algoritmus egy halmazban tárolja azon csúcsokat, amelyeknek már ismerjük az -ből hozzávezető legrövidebb út hosszát, egy halmazban pedig azokat, amelyeket már elértünk -ből, de az -ből hozzájuk vezető legrövidebb út hosszát még nem ismerjük. Minden csúcsról nyilvántartunk az algoritmus futása során három értéket: az -ből -ba vezető addig megismert legrövidebb út hossza, egy nem negatív heurisztikus alsó becslés az -ból -be vezető legrövidebb út hosszára, amelyre az is teljesül, hogy az -ból bármely csúcsba vezető legrövidebb út hosszára alsó korlát (például egy térkép esetén és légvonalban mért távolsága), végül .
Kezdetben üres, -ben csak az csúcs van, és . Ezután minden iterációban kiválasztunk az halmazból egy olyan csúcsot, amelyre minimális, áttesszük -et -ba, majd minden olyan szomszédjára, amely nincs -ban frissítjük először a értéket: , majd a értéket: , végül áttesszük -t -be. Az algoritmus véget ér, amikor átkerül -ből -ba, ekkor egy legrövidebb -ből -be vezető út hossza. Az algoritmus kis módosítással egy legrövidebb utat is megad -ből -be.
A tapasztalat azt mutatja, hogy az algoritmus számos esetben hatékonyabb, mint a Dijkstra algoritmust.
Az A* algoritmus pgRouting lekérdezéseket használva:
Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között). Az algoritmus Dijkstra algoritmuson alapszik, heurisztikus kikötéssel, amely hatékonyabbá teszi. Ebben a seq a sorok szekvenciája, az id1 a startcsúcs azonosítója, az id2 az él azonosítója (az utolsó sorban -1), a cost az áthaladás költsége id1-től id2 élen keresztül (az utolsó sorra 0).
pgr_costResult[] pgr_astar(sql text, source integer, target integer,
directed boolean, has_rcost boolean);
/*Ezekben a source a startcsúcs azonosítója,
a target a célcsúcs azonosítója,
a directed akkor igaz, ha az él irányított,
a has_rcost akkor igaz, ha negatív élek vannak, ekkor a kapott sorokat az algoritmus visszafelé dolgozza fel.*/
Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie:
SELECT id, source, target, cost, x1, y1, x2, y2 [,reverse_cost] FROM edge_table
/* Ebben az id az él azonosítója,
a source: az él startcsúcsának azonosítója,
a target az él célcsúcsának azonosítója,
x1 az él start pontjának x koordinátája,
y1 az él start pontjának y koordinátája,
x2 az él end pontjának x koordinátája,
y2 az él end pontjának y koordinátája,
a cost egy pozitív szám, az élen való áthaladásnak a költsége,
a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/
A* algoritmussal kiegészítve az előző lekérdezés reverse_cost nélkül:
SELECT * FROM pgr_AStar(
'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, x1, y1, x2, y2 FROM edge_table',
4, 1, false, false);
Reverse_cost-tal:
SELECT * FROM pgr_AStar(
'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, x1, y1, x2, y2, reverse_cost FROM edge_table ',
4, 1, true, true);
Kétirányú A* algoritmus
A kétirányú algoritmus egy súlyozott élű, irányított gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont , a célállomást pedig . Az algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy csúcs mindkét irányból bekerül az algoritmusnál definiált halmazba (pontosabban a és a halmazba is). Az algoritmus kis módosítással egy legrövidebb utat is megad s-ből t-be.
A Kétirányú A* algoritmus pgRouting lekérdezéseket használva:
Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza, melyek egy utat hoznak létre (a legrövidebb utat a két csúcs között) úgy, hogy elkezdi megkeresni a legrövidebb utat a startcsúcsból és párhuzamosan a célcsúcsból is. Akkor ér véget, ha a két keresés valahol középen véget ér. Ebben a seq a sorok szekvenciája, az id1 a startcsúcs azonosítója, az id2 az él azonosítója (az utolsó sorban -1), a cost az áthaladás költsége id1-től id2 élen keresztül.
pgr_costResult[] pgr_bdAstar(sql text, source integer, target integer,
directed boolean, has_rcost boolean);
/*Ebben a source a startcsúcs azonosítója,
a target a célcsúcs azonosítója,
a directed akkor igaz, ha az él irányított,
a has_rcost akkor igaz, ha negatív élek vannak, ekkor a kapott sorokat az algoritmus visszafelé dolgozza fel.*/
Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie:
SELECT id, source, target, cost, x1, y1, x2, y2 [,reverse_cost] FROM edge_table
/* Ebben az id az él azonosítója,
a source: az él startcsúcsának azonosítója,
a target az él célcsúcsának azonosítója,
a cost egy pozitív szám, az élen való áthaladásnak a költsége,
x1 az él start pontjának x koordinátája,
y1 az él start pontjának y koordinátája,
x2 az él end pontjának x koordinátája,
y2 az él end pontjának y koordinátája,
a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/
Kétirányú A* algoritmussal kiegészítve az előző lekérdezés reverse_cost nélkül:
SELECT * FROM pgr_bdAStar(
'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, x1, y1, x2, y2
FROM edge_table',
4, 10, false, false);
Reverse_cost-tal:
SELECT * FROM pgr_bdAStar(
'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost, x1, y1, x2, y2, reverse_cost
FROM edge_table ',
4, 10, true, true);
Yen algoritmus
A Yen algoritmus egy súlyozott élű, irányított gráf egy adott csúcsából egy adott másik csúcsába vezető legrövidebb út mellett megtalálja a második, harmadik, …, -adik legrövidebb (egyszerű) utat is. Az algoritmus csak nem negatív élsúlyok esetén működik.
Az algoritmus költsége .
A Yen algoritmus pgRouting lekérdezéseket használva:
Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) sorok halmazával tér vissza, melyek utakat hoznak létre (a legrövidebb utat a két csúcs között) összesen az első k darabot. Ebben a seq a sorok szekvenciája, az id1 az út azonosítója, az id2 a csúcs azonosítója, az id3 az él azonosítója (az utolsó sorban 0) a cost az áthaladás költsége id2-től id3-at használva.
Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie:
SELECT id, source, target, cost, [,reverse_cost] FROM edge_table
/* Ebben az id az él azonosítója,
a source: az él startcsúcsának azonosítója,
a target az él célcsúcsának azonosítója,
a cost egy pozitív szám, az élen való áthaladásnak a költsége,
a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/
Yen algoritmussal kiegészítve az előző lekérdezés reverse_cost nélkül:
SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost
FROM pgr_ksp(
'SELECT id, source, target, cost FROM edge_table',
7, 12, 2, false
);
Reverse_cost-tal:
SELECT seq, id1 AS route, id2 AS node, id3 AS edge, cost
FROM pgr_ksp(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
7, 12, 2, true
);
Floyd-Warshall algoritmus
A Floyd-Warshall algoritmus egy súlyozott élű, irányított gráf bármely két csúcsa közötti legrövidebb út megtalálására szolgáló módszer. Az algoritmus negatív élsúlyok esetén is működik, ha a gráf nem tartalmaz negatív összhosszúságú irányított kört. Jelölje a súlyfüggvényt . Az algoritmus dinamikus programozást használ. Legyen a gráf csúcshalmaza . Az algoritmus minden esetén meghatározza a -ből -be menő legrövidebb olyan (egyszerű) út hosszát, amelyen a közbülső csúcsok a halmazból kerülnek ki: , és ha . Az algoritmus kis módosítással magukat a legrövidebb utakat is megadja.
Az algoritmus költsége .
A Floyd-Warshall algoritmus pgRouting lekérdezéseket használva:
Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza minden csúcspárra a súlyozott gráfban, mindegyiknél kiszámolva a legrövidebb utat:
pgr_costResult[] pgr_aspsWarshall(sql text, directed boolean, reverse_cost boolean); -- magyarul minden egyes csúcspárra kiszámolja az összes költséget.
/*Ebben a seq a sorok szekvenciája,
az id1 a startcsúcs azonosítója,
az id2 a célcsúcs azonosítója,
a cost az id1-től id2-ig jutás költsége.*/
Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie:
SELECT source, target, cost FROM edge_table;
/* Ebben a source: az él startcsúcsának azonosítója,
a target az él célcsúcsának azonosítója,
a cost egy pozitív szám, az élen való áthaladásnak a költsége,
a reverse_cost ha igaz, akkor a cost értékét az ellentétes irányból vesszük.*/
Floyd-Warshall algoritmussal kiegészítve az előző lekérdezés:
SELECT seq, id1 AS from, id2 AS to, cost
FROM pgr_apspWarshall(
'SELECT id, source, target, cost FROM edge_table',
false, false
);
Johnson algoritmus
A Johnson algoritmus egy súlyozott élű, irányított gráf bármely két csúcsa közötti legrövidebb út megtalálására szolgáló módszer. Az algoritmus negatív élsúlyok esetén is működik, ha a gráf nem tartalmaz negatív összhosszúságú irányított kört. Jelölje a súlyfüggvényt . Az algoritmus ritka gráfokon teljesít igazán jól.
Vegyünk fel egy új csúcsot, és vezessünk -ből nulla súlyú éleket csúcsaiba. Jelölje az így kapott gráfot . Futtassuk le -re a Bellman-Ford algoritmust az kezdőcsúccsal. Az algoritmus által szolgáltatott távolságérték a gráf egy csúcsára legyen . Átsúlyozzuk a gráf éleit: legyen minden élre. Most egy nem negatív súlyfüggvény -n. Futtassuk ezzel a súlyfüggvénnyel a Dijkstra algoritmust a gráf minden csúcsából. Egy legrövidebb -ból -be vezető út hossza ezután a kapott érték mínusz . Az algoritmus kis módosítással magukat a legrövidebb utakat is megadja.
Az algoritmus költsége szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva .
A Johnson algoritmus pgRouting lekérdezéseket használva:
Az algoritmus pgr_costResult(seq, id1, id2, cost) sorok halmazával tér vissza minden csúcspárra a gráfban:
pgr_costResult[] pgr_aspsJohnson(sql text); -- magyarul minden egyes csúcspárra kiszámolja az összes költséget.
/*Ebben a seq a sorok szekvenciája,
az id1 a startcsúcs azonosítója,
az id2 a célcsúcs azonosítója,
a cost az id1-től id2-ig jutás költsége.*/
Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie:
SELECT source, target, cost FROM edge_table;
/* Ebben a source: az él startcsúcsának azonosítója,
a target az él célcsúcsának azonosítója,
a cost egy pozitív szám, az élen való áthaladásnak a költsége.*/
Johnson algoritmussal kiegészítve az előző lekérdezés:
SELECT seq, id1 AS from, id2 AS to, cost
FROM pgr_apspJohnson(
'SELECT source, target, cost FROM edge_table'
);
Utazó ügynök probléma
Az utazó ügynök probléma a következő. Adott városoknak egy listája, és adott bármely két város között a távolság. Határozzunk meg egy olyan körutat, amely minden városon pontosan egyszer halad át, és a hossza minimális. A problémára nem ismert polinomiális költségű algoritmus. A program ún. simulated annealing technikán alapuló algoritmust használ egy jó közelítő megoldás meghatározására.
A vezetési távolság algoritmus pgRouting lekérdezéseket használva:
Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) egy seq-id párossal tér vissza, amely azt írja le, mi a legjobb haladási sorrend a mátrixban, hogy eljussunk a start csúcsból a meghatározott csúcsokig. Ebben a seq a sorok szekvenciája, az id1 az út azonosítója, az id2 a csúcs azonosítója, az id3 az él azonosítója (az utolsó sorban 0) a cost az áthaladás költsége id2-től id3-at használva.
pgr_costResult[] pgr_tsp(sql text, ids varchar, source integer);
Utazó ügynök algoritmus SQL paraméterrel:
SELECT * FROM pgr_tsp('SELECT id AS source_id, x, y FROM vertex_table','2,7,11',7);
Távolsági mátrixszal:
SELECT seq, id FROM pgr_tsp('{{0,1,2,3},{1,0,3,2},{2,3,0,4},{3,2,4,0}}',2);
Legrövidebb utak kanyarodási korlátokkal
Az algoritmus egy súlyozott élű, irányított gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út meghatározásakor képes figyelembe venni, hogy két csatlakozó él egymás utáni bejárása extra költséggel bírhat. Ezeket a megszorításokat egy külön táblában adhatjuk meg. Tapasztalat szerint az algoritmus közel olyan gyors, mint az algoritmus.
A legrövidebb út kanyarodási korlátokkal algoritmus pgRouting lekérdezéseket használva:
Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) sorok halmazával tér vissza, minden sor egy élt tartalmaz, amelyiken átmentünk, plusz az utolsó az utolsó élt. Ebben a seq a sorok szekvenciája, az id1 az út azonosítója, az id2 a csúcs azonosítója, az id3 az él azonosítója (az utolsó sorban 0) a cost az áthaladás költsége id2-től id3-at használva.
Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie, attól függően, hogy van-e megszorítás:
pgr_costResult[] pgr_trsp(sql text, source integer, target integer, directed boolean, has_rcost boolean [,restrict_sql text]);
pgr_costResult[] pgr_trsp(sql text, source_edge integer, source_pos double precision, target_edge integer, target_pos double precision, directed boolean, has_rcost boolean [,restrict_sql text]);
SELECT id, source, target, cost, [,reverse_cost] FROM edge_table;
/* Ebben az id az él azonosítója,
a source: az él startcsúcsának azonosítója,
a target az él célcsúcsának azonosítója,
a cost egy pozitív szám, az élen való áthaladásnak a költsége,
a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/
TSRP algoritmussal kiegészítve az előző lekérdezés megszorítások nélkül:
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_trsp(
'SELECT id, source, target, cost FROM edge_table',
7, 12, false, false
);
Megszorításokkal (külön táblában tároljuk):
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_trsp(
'SELECT id, source, target, cost FROM edge_table',
7, 12, false, false,
'SELECT to_cost, to_edge AS target_id,
from_edge || coalesce('','' || via, '''') AS via_path
FROM restrictions'
);
Vezetési távolság
Az algoritmus egy súlyozott élű, irányított gráfban a Dijkstra algoritmus felhasználásával megadja azon csúcsokat, melyekbe egy vagy több adott csúcsból egy adott értéknél rövidebb úton el lehet jutni.
A vezetési távolság algoritmus pgRouting lekérdezéseket használva:
Az algoritmus pgr_costResult(seq, id1, id2, id3, cost) sorok halmazával tér vissza, minden sor egy élt tartalmaz, amelyiken átmentünk, plusz az utolsó az utolsó élt. Ebben a seq a sorok szekvenciája, az id1 az út azonosítója, az id2 a csúcs azonosítója, az id3 az él azonosítója (az utolsó sorban 0) a cost az áthaladás költsége id2-től id3-at használva.
Segítségül egy olyan SQL lekérdezést használunk, amelyiknek a vizsgált gráf éleivel kell visszatérnie:
SELECT id, source, target, cost, [,reverse_cost] FROM edge_table
/* Ebben az id az él azonosítója,
a source: az él startcsúcsának azonosítója,
a target az él célcsúcsának azonosítója,
a cost egy pozitív szám, az élen való áthaladásnak a költsége,
a reverse_cost opcionális, akkor lesz használva, ha a directed és a has_rcost értéke is igaz.*/
Vezetési távolság algoritmussal kiegészítve az előző lekérdezés:
SELECT * FROM pgr_drivingDistance(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
2, 3
);
Kapcsolódó alkalmazások
Útvonal-meghatározásra alkalmas adathalmazt például OpenStreetMap (OSM) térképekből nyerhetünk ki. Ehhez egyik alkalmas segédeszköz az OSM2PO alkalmazás, amely megfelelő topológiájú SQL fájlt állít elő a megadott térképrészlethez, amely egyből alkalmas a pgRouting-gal vagy QGIS-szel való feldolgozásra.
Az OSM2PO révén vizualizálhatjuk is a legrövidebb utakat. A programmal előállított SQL táblákban minden útkereszteződéshez tartozik egy rekord, melyben a következőket tároljuk:
- koordináták (
x1, x2, y1, y2
), - név (
osm_name
), - csomópont azonosító (
id
), - lehetséges továbbhaladási irány (
osm_source_id, osm_target_id
), - útszakasz hossza (
km
), - megengedett sebesség (
kmh
), - költség (
cost
), - geometria (
geom_way
).
A demo.bat
fájl szerkesztésével specifikálhatjuk térképünk paramétereit, például, hogy mely térképrészleten dolgozzunk. A Mapzen oldalán kész .pbf
formátumú városrészleteket találhatunk, melyeket kompatibilisek az Osm2Po-val. A fájl futtatásával előáll egy .sql
fájl is, melyet importálhatunk a postGIS adatbázisunkba, és akár pgRouting lekérdezéseket is futtathatunk rajta.
Amíg fut a program, helyi webszerveren (localhost:8888/Osm2poService
) jeleníthető meg az importált térképrészlet, melyen az útkeresést is kipróbálhatjuk.
Szakirodalom
- Regina O. Obe, Leo S. Hsu. "pgRouting: A Practical Guide", Locate Press, 2016.
- Regina O. Obe, Leo S. Hsu. "PostGIS in Action (Second Edition)", Manning Publictions (ISBN 9781617291395). 2015. pp 286-290.
- Lijing Zhang, Xuanhui He. "Route Search Base on pgRouting", Software Engineering and Knowledge Engineering: Theory and Practice Vol 2.. Springer-Verlag Berlin Heidelberg, 2012. pp 1003-1007.