„PgRouting” változatai közötti eltérés

Innen: GIS Wiki
(Telepítés, Architektúra)
a
 
(36 közbenső módosítás, amit 4 másik szerkesztő végzett, nincs mutatva)
1. sor: 1. sor:
== Bevezetés ==
+
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++-ban írt bővítmény a PostGIS/PostgreSQL térinformatikai adatbázisokhoz. Gráf szerkezetek kezelését teszi lehetővé, így például legrövidebb utakat, csomópontok távolságát és egyéb hálózati elemzést igénylő feladatokat oldatunk meg vele.
+
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.
  
== Telepítés, Architektúra ==
+
'''OSGeo'''
A PostGIS újabb verziói (2.0+) már tartalmazzák a pgRoutingot, így nem szükséges külön telepíteni, csak aktiválni kell:
 
  
<code>
+
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 ==
 +
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:
 
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
+
* 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.
 
* C++ modulok, amelyek a lekérdezést úgynevezett boost gráffá alakítják, és futtatják az útvonal-választást.
  
16. sor: 41. sor:
  
 
A függvénykönyvtár szerkezete pedig a következőképp néz ki:
 
A függvénykönyvtár szerkezete pedig a következőképp néz ki:
<code>
+
<pre>
cmake/                - cmake fájlok
+
  cmake/                - cmake fájlok
 
   CMakeLists.txt        - Top level cmake  
 
   CMakeLists.txt        - Top level cmake  
   doc/                  - Top level doc, a nem forráslgoritmus-specifikus dokumentáció helye
+
   doc/                  - Top level doc, a nem forrásalgoritmus-specifikus dokumentáció helye
 
     themes/              - Sphinx téma a doc-nak
 
     themes/              - Sphinx téma a doc-nak
 
     static/              - dokumentáció képei
 
     static/              - dokumentáció képei
30. sor: 55. sor:
 
     tsp/                - Utazó ügynök
 
     tsp/                - Utazó ügynök
 
   tools/                - Tesztelési eszközök
 
   tools/                - Tesztelési eszközök
</code>
+
</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:
 
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, inpu és output paraméterek megadásával a felhazsnálók számára érthetővé tegye, hogyan működik az algoritmus.
+
*'''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
+
*'''sql''': Az sql burkolók a C kódhoz.
*'''src''' C/C++ kód az algoritmushoz
+
*'''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.
+
*'''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:
 
Fejlesztési célból a programot klónozhatjuk Git-en keresztül, majd telepítjük a következők szerint:
<code>
+
 
git clone git@github.com:pgRouting/pgrouting.git
+
<syntaxhighlight lang="bash">
cd pgrouting
+
git clone git@github.com:pgRouting/pgrouting.git
cmake -DWITH_TSP=ON -DWITH_DD=ON .
+
cd pgrouting
make
+
cmake -DWITH_TSP=ON -DWITH_DD=ON .
sudo make install
+
make
</code>
+
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 ==
51. 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''': vektoros adatok konverziója
+
* '''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'''
60. 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'''
69. sor: 136. sor:
 
Minden pgRouting lekérdezés az alábbi formátumot követi:
 
Minden pgRouting lekérdezés az alábbi formátumot követi:
  
<code>
+
<syntaxhighlight lang="sql">
 
SELECT pgr_<algorithm>(<SQL for edges>, start, end, <additonal options>)
 
SELECT pgr_<algorithm>(<SQL for edges>, start, end, <additonal options>)
</code>,
+
</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:
  
<code>
+
<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);
</code>
+
</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:
92. 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 ===
101. 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>.  
  
114. 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.
  
=== Kétirányú <math>A^\ast</math> algoritmus ===
+
'''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  
138. 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 ===  
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.
+
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, 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:
+
Ú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 [[Fájl:Osm.png|thumb|450px|Útvonal megjelenítése OSM2PO webszolgáltatásként]]
+
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 (élek)
+
* 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.  
 
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.
 
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.
  
== Hivatkozások ==
+
== Szakirodalom ==
[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 Manual]
+
* 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.
  
[http://workshop.pgrouting.org/index.html pgRouting Workshop]
+
== Külső hivatkozások ==
  
[http://www.bostongis.com/PrinterFriendly.aspx?content_name=pgrouting_osm2po_1 Loading OpenStreetMap with Osm2Po and route querying]
+
* [http://pgrouting.org/ A pgRouting hivatalos honlapja]
 +
* [http://docs.pgrouting.org/latest/en/doc/index.html pgRouting Dokumentáció]
 +
* [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://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.

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.

Útvonal megjelenítése OSM2PO webszolgáltatásként

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

Külső hivatkozások